Note that 'not requiring a parser' is only true iff you limit the expression language you transform to one that has no syntactical constructs (i.e. can't introduce new bindings). If you want to allow those then you need a "parser" on top of s-expressions which maintains a bindings context (usually called a code walker in the context of Lisp).
So not requiring a 'parser' in that sense is not really a feature of full (modern) Lisp. (Early Lisps didn't use lexical scoping, and used f-expressions or similar i.e. less of a compile- vs. run-time separation, so it may have worked better back then for what seems to have been the original purpose of Lisp, but they may also have squinted and limited themselves via convention, not sure.)
This doesn't mean that there's no usefulness for the 'first-level parsing step' that gives you s-expressions: in some cases you might be handling a context insensitive language like yours. Also, it makes extending the language much more painless (macros easily compose, or more to the point, you can easily invent ad-hoc new languages on top of s-expressions used as inputs for macros, and won't (ever, I think) have problems with their boundaries becoming ambiguous).
I thought I was playing somewhat loose with the term parser. The code I used from SICP is walking the code, after all. More accurate to just say no lexing and tokenization?
Hmm, true you're walking the code already. What you don't do is look at the lexical context or maintain it while walking.
S-expressions in full Lisp don't specify lexical constructs, it is only the pre-cursor of such (people often say that S-expressions are the AST of Lisp, that's not true if by AST one understands to mean that each element's functionality is clear, e.g. if it's a function call or function abstraction or constant etc.; an S-expression only specifies a computation given a lexical compile time context).
What you (and SICP) are doing is look for symbols like +, regardless of whether + is bound to the addition function or something else. That is fine if that's your intention (it's certainly easier to implement a code walker for and you can often get away with it). If playing/deriv received
(+ (flet ((* #'+)) (* x 2)) 12)
instead of
(+ (* x 2) 12)
then it would need to be able to handle the flet form, and maintain the aliasing of * to + in a lexical context that playing/product? has to inspect to know if it's dealing with multiplication (and return false in this case). (Caveat: I'm a Scheme, not Common Lisp user, I hope I got the syntax right above.-- Edit: I didn't; this apparently violates CL because it tries to shadow a standard function name, additionally the flet form apparently requires function definition syntax not just value, i.e. (flet ((* (a b) (+ a b)))..). So, my argument becomes a bit moot in CL as the basic operators can't be shadowed anyway, except I'm told that you can define them in a new package then import them, but then I'm not sure you can rebind them lexically. Scheme is beautifully simple in comparison, it doesn't try to prevent you from shooting your foot but of course encourages to learn to deal with the consequences, which is why I wanted to write my post. It will still be true for the general case in CL, too.)
Most programming languages parse from strings (possibly via tokens) to an AST. Lisp parses from strings (possibly via tokens) to S-expressions then to an AST. I just want to point out that one has to be careful here, and want to point out that Lisp isn't fully parsed in the sense that one has got an AST, when you're at the s-expression stage.
> More accurate to just say no lexing and tokenization?
The read function does more than tokenization, it doesn't give you a stream of tokens (that includes open and close paren token), instead it does give you a hierarchical expression representation. Yes, you don't need to tokenize, but even don't need to do more than that. I don't know if there's some CS term for that, in Lisp it's just "read".
Here's a perhaps better CL example as it side-steps the non-shadowability of the common-lisp math operators:
(+ (flet ((f (a) (* a a))) (f 10)) 2)
This would, as I already mentioned, require the code walker to support flet, and also pass around a lexical context so that the additional bindings are known. (And then handle such functions, probably by inlining them.)
(I had some discussion on #lisp on freenode.)
Anyway, the point I wanted to make in all of this is just to remind people that the meaning of S-expressions is context sensitive, more so than ASTs in most languages. Actually Wikipedia[1] puts contextual analysis as a step after ASTs, so given that, perhaps I was wrong saying that S-expressions are not ASTs, but still it's important to keep in mind that there's a difference from ASTs in most languages. Macros do implement syntax that languages without them would need special parser support for; hence I think of macros as being kind of a continuation of parsing (first step: string to sexpr, second step: macros, then the compiler does the syntactical analysis; if you want to implement derivation of a language enriched with context dependent stuff, then you'd have to hook into the compiler, or do the same context analysis that the compiler is doing).
That all makes sense, and I tried to talk towards this when I referred to putting the rest of the syntax required to define a function.
That is, I have fallen to the trap of claiming lisp has little syntax before. The idea being that I can walk the tree, so I'm walking an AST. But i realize now that is abusing the S in AST. There is plenty of syntax there that can be checked.
I would like to not steer others down that trap. Thanks for expanding in it here!
Lisp languages have lots of abstract syntax. What is lacking is the proliferation of surface syntax.
Typically, programming languages have some dedicated phrase structure rule for recovering each kind of AST node shape out of tokens. Moreover, AST node shapes for which there is no phrase structure in the grammar cannot be instantiated from source text.
Lisp languages tend to have a small surface syntax that is general, and expresses all possible AST node shapes, including ones that have no assigned meaning.
So, Lisps have plenty of abstract syntax; but abstract syntax is better because it is a data structure that usually no longer exhibits representational issues that require parsing.
Sometimes it does. Lisp parameter lists like (a b &optional c &key d e) require a bit of parsing; they are a flat list that has to be scanned for the lambda list keywords like &optional and &key. Nothing stops Lisp programmers from creating similar parsing problems of their own, in the arguments of a macro. Usually it's a far cry from having to deal with a full blown grammar.
Recovering an AST representation from the source code doesn't require parsing in general, only in some specific cases. By parsing I mean "recovering of nested syntactic units from a flat stream of tokens". E.g. when a compiler is processing let, it doesn't have to first process phrase structure rules to obtain let as a unit out of a stream of tokens, and identify its constituent pieces like the bindings and body. It has those pieces already in a fixed tree shape. In some constructs, the arguments of a form do have to be treated like tokens and subject to parsing actions to identify the constituent pieces, though usually nothing like a full blown LALR(1) grammar. loop has to parse its clauses; lambda lists have to be parsed; CL's defun needs some light parsing due to some design quirks in the syntax; formatter has to parse the format string and such. Identifying the optional declarations at the start of a body is a piece of light parsing.
But it does not know what it is. It has to know the structure of the LET. The LET expression has no tagging of the parts. Is that list after the binding list a declaration or not? How many of them? Is the symbol in the list after a LET a variable? The s-expression does not say what a symbol is: a variable or not. We also don't know what the relationship of the declaration to this variable is: is there a declaration for this variable?
The relatively simple syntax of LET: let ({var | (var [init-form])}) declaration form*
We then see that the syntax for 'declaration' is quite a bit more complex.
An AST will usually represent such information.
> parsing I mean "recovering of nested syntactic units from a flat stream of tokens
in Lisp this is: recovering of nested syntactic units from a nested list of tokens.
This, together with taeric's question about tokenization made me realize that we can think of it this way:
Macros are not receiving AST nodes [1]. They are not receiving tokens either, though. But something in-between: how many tokens it receives is strictly delimited (by the end paren which ends the macro form, but the macro doesn't see an end paren token, just doesn't get more items in the list, thus can't violate the scoping). Lisp forces open and end parens to be understood as hierarchical grouping indicators for (any kind of) syntax. This simple change over a stream of tokens seems to happen to simplify language creation via macros a lot.
[1] quite definitely not before macro-expanding their arguments. After macro-expansion, by grouping the resulting s-expr with a context and a correct tree-walker, I guess it could be said to be one.
Macros are expanded by a correct tree walker: the macro expander. It recognizes all special forms, and maintains an environment representing information about the lexical scope (at least in any Lisp dialect worth a damn, with lexical macros that can shadow lexical functions and variables and vice versa).
Macros can also receive that environment as an argument, which provides the possibility that there can be an API by which macros can query the lexical environment.
Furthermore, if macros are given an API for fully expanding an expression, with detailed information about what free references occur in that form, that creates a lot of possibilities for macros to do all sorts of clever things correctly, far beyond just "sticking pieces into a code template with a sprinkling of gensyms".
I was talking about macro-expanding the form first so that the result to be walked consists of only "core" lisp forms.
Do you mean that there are macro-expander APIs in CL that offer all ingredients to do the derivation as part of the macro-expansion step? (I'd welcome some pointer to study.)
The macro expander is a code walker. Whenever it encounters a macro, it expands it (repeatedly, if necessary). Then when all that is left is a special form or function call, or when such a thing is encountered in the first place, it walks that form in the manner appropriate to that form. So by the time macros are expanded, a code walk has taken place over all the special forms and function calls that have emerged.
CL doesn't standardize any API for doing anything with the &environment parameter, other than using it as an argument in macroexpand and macroexpand-1, which is a pity. There is information in there such as "is this symbol a lexical variable in this macro's scope".
Steele's Cltl2 describes such features, but these didn't make it into ANSI CL. It describes accessors variable-information, function-information and declaration-information. Also an augment-environment function and some other things like enclose.
I don't think you're using AST right. An abstract syntax tree in computer science is a lower level, barer representation than you seem to think. It is just the raw syntax, without surface details.
A "parse tree" still has the commas, semicolons and parentheses and whatnot: all the tokens that appear in the BNF. The nodes in the parse tree correspond to the nonterminal symbols in the grammar, and the leaves are the tokens.
An "abstract syntax tree" is just the next level which abstracts away from those details. There are no more nonterminal and terminal symbols, but some sort of logical units. Lisp's abstract syntax tree is the object structure from the reader: the parentheses, consing dots, and other details are gone.
The further processing of the AST where it is transformed into some much more semantically annotated tree or something else entirely is the "intermediate representation", IR.
See the example picture in the article. Lisp s-expressions have no concept like 'variable name: a'. The s-expressions simply does not represent that some symbol is a variable. In an AST this is common.
In an AST the elements are already classified according to some syntax. In S-expressions this is not the case.
I know. Sorry for my messy terminology. (Not sure whether the points I'm making here are useful or just wasting your time, I'll try to explain just to clarify what I meant.)
I didn't mean calling the individual functions implementing macros (apparently called "macro functions"), but something like macroexpand-all (I didn't realize that this is apparently not portable). What I am thinking of is something like:
(defmacro foo (expr var &environment env)
(let ((expr* (macroexpand-all expr env))
(var* (macroexpand-all var env)))
(derive-by expr* var*)))
where derive-by is a code walker that understands core CL, and does derivation as part of the walk (perhaps implemented with the help of one of the code walker libraries).
expr* (same for var* ) is not an AST in the sense of e.g. a tree of CLOS objects where each one determines a syntactical construct even when standing by itself; only together with env and a walker that understands the "core" CL syntax correctly, it could, "I guess", be considered an AST--sure, maybe let's avoid confusion and call it proto-AST instead.
where protoAST->AST is a code walker that converts expr* to a tree of objects from a CLOS hierarchy representing each kind of node unambiguously without the need for env. protoAST and AST hold the same information content, which is why I said "could be said to be the same".
> protoAST and AST hold the same information content
Not really. protoAST lacks the knowledge the specific code walker adds. For example there is no way to find out whether FOO is a variable or a function without actually 'parsing' the code. If one uses a different syntax in the code walker, then the conversion generates a different parse.
to be explicit. core-CL-walker changes only when the definition of the "core-CL" [1] changes, though, so it's probably a constant for practical purposes.
[1] I don't know whether there is any standardization of such a thing. Probably not since macroexpand-all also isn't standard.
Lisp nested expressions are AST. A CLOS-sified representation of the program with additional semantic info is more of an IR: intermediate representation.
Note that you also aren't using "token" in the usual way it appears in computer science.
ANSI Lisp's Glossary gets it right:
> token n. a textual representation for a number or a symbol. See Section 2.3 (Interpretation of Tokens).
"1234" and "A1234" are tokens: chunks of accumulated token-constituent characters inside the reader. These are turned into values, which are no longer tokens. We never have a "tree of tokens"; for that to be true you have to abuse the word "token" to denote "Lisp value".
The Lisp AST consists of nodes which are typed values. (Some of those values are aggregates that are not lists: let's not forget vectors and structure literals.)
When non-Lisp-programmers write parsers for non-Lisp-languages, they crank out AST's which imitate the concept. A typical approach is for the parser rules to produce nodes based on a discriminated union of types: in its essence, an implementation of dynamically typed objects.
What can we look at for a real example? How about GNU Awk. This has a Yacc grammar:
Okay, so that would be our GNU AWK AST node. What is it? Why, just a grotesque Greenspunning of some dynamic typing. The two unions in there are like car and cdr. The semantics actions of the Yacc parser do a whole lot of list_create and list_append involving this INSTRUCTION type, often behind various wrapper functions like mk_assignment or mk_expression_list and whatnot,
The main difference is that the Lisp way of representing AST's is just cleaner and smarter, like the Lisp way of doing pretty much anything.
> Note that you also aren't using "token" in the usual way it appears in computer science
I use the word such that we can talk about parsing, syntax, and syntax trees at all. Lisp works different from most languages (the Lisp syntax is working over a data representation, syntax can depend on runtime state in the case of macros and a Lisp interpreter, ...), so I try to use related words to map that a bit.
We can look at the textual representation:
(let ((x '(* x x)))
(progv '(x) '(2)
(eval x)))
If we look at that code as text and/or as an S-expression, we have no idea what each X is. We have to construct that information by parsing or even by executing it. The s-expression is no AST (abstract SYNTAX tree), because it has no syntactic information represented, besides some structural information and on a textual level we can construct data objects from the tokens. Each token has a direct data representation (unless we have the reader re-programmed).
An AST OTOH has already been constructed as a tree, based on a syntax grammar for a programming language. To reach to an AST we need a parser + language syntax + a tree representation mechanism. The Lisp s-expression representation lacks the parser and the language syntax. All the s-expression represents is the data - internal and external. For an s-expression there is no difference between: (* x y) and (x y ). READ accepts externally represented data - it has no idea if the thing it successfully reads is a valid Lisp program or not. Only the parsing/interpretation of a that code snippet on the Lisp language level makes it possible to see if is a function or a variable. For that we need a grammar which says if that code is prefix, infix, postfix or something else. For Lisp it is much worse, since the interpretation of (foo (* x y)) depends on what foo actually does at runtime. In a Lisp interpreter, FOO could be a macro, which interprets the enclosed expression differently each time it gets executed.
If we look at an AST, we need to combine the s-expression + a syntax + plus something which acts similar to a parser to create an AST. Without that syntax, we can not generate that AST from the s-expression. IF we take a slightly different syntax, we are able to create different ASTs from an s-expression.
Note that the meaning of words like token, parser, lexer, scanner, ast, syntax has to be adjusted for Lisp. For example the ANSI CL standard contains EBNF-based syntax descriptions. But this syntax is actually over s-expressions (data - since we also need to be able what is a valid program as data) and not for textual representations of programs.
A token has two usual meanings: on the textual side it is the characters which form a basic element in the language, for example a number. In a representation, a scanner/lexer generates, it is then the data object which represents that thing. Think (defclass token () (text type ...)) and (defclass number-token (token) (numeric-value)). For Lisp the textual tokens are mapped to a more direct representation - each token gets translated into a typed data object (which has its type encode and which has a procedure to generate a textual representation back).
I need to make slides and a better write up for it, but the program is a math quiz with equation editing and graphing capabilities for X. It includes a simplifier which will take derivatives if they are in the form: D(x^2)/D(x)
The simplifier also combines terms, reduces fractions, etc. I was shooting for something like Macsyma.
Equations are parsed into LISP-like lists, defined in box.h. There are list nodes, numbers and symbols. They are allocated in aligned pages. To distinguish between them, you look at the page header. Some of the classic LISP implementation used this same technique- I was interested in it at the time, but wouldn't use it today.
As you type equations in, they are typeset in standard math notation on the screen. You can edit the tree by selecting any part of the equation with the mouse. Once something is selected, you can type in a replacement, or click simplify, distribute, or factor. I had fun correlating mouse coordinates with tree locations.
I don't remember SICP, but I read lots of similar books.
Actually the advisor wanted me to do this in Prolog, with the idea that we would try to prove equivalency between the entered answer and known answer. The problem is that I saw no way to do all of the mundane tasks in Prolog. LISP would have been a far better choice (perhaps with a unification library), but even LISP at the time did not have great support for X. I already knew C, and had to get the project done...
It occurred to me later, that the first volume of Art of Computer Programming has a derivative calculator algorithm. Even implements part in its assembly language.
Regardless of any of that, really cool project. Being for a class underscores the deadline you did that in. Thanks for sharing!
- It seems like the difficulty level ramps up really quickly starting with the "So, what makes the lisp example different?" section. This was jarring enough that I pretty much glossed over it (too much effort required to process all the definitions at once).
As a more meta point, I wonder if symbolic differentiation is in fact a good example of highlighting lisp's differentiating features? One could write the same code in python/javascript with using lists and strings and recursion in a similar way, no?
Not that I have a better example to highlight lisp's differences, which I understand to be macros. I've read SICP and have written a fair amount of elisp and still have not once identified a good use case for writing a DSL nor even a macro for myself.
> One could write the same code in python/javascript with using lists and strings and recursion in a similar way, no?
Then you're implementing a Lisp (just one with square instead of round brackets, and commas between list elements) within Python/JS.
Edit: to explain, you also need to either translate the result of the derivation back into Python/JS code (via stringification and eval or perhaps AST manipulation--i.e. a compiler of the list structures (Lisp) to Python/JS), or write an interpreter for the list structures (i.e. Lisp interpreter).
One thing I’ve done recently in Common Lisp with macros was write a suite of macros to make working with objective-c in Common Lisp less burdensome: with a couple reader macros, I can almost copy-paste objective-c code samples into my Common Lisp program and have them work.
Also, some of the biggest complaints about redux and other JavaScript libraries is the amount of boilerplate you have to write, leading to really complicated scaffolding and code generation utilities: Babel, for example, is essentially just a big macroexpander for JavaScript enabling, among other things, the use of language features as soon as they are standardized rather than having to wait years until a sufficient portion of the available browsers support the new feature.
> One could write the same code in python/javascript with using lists and strings and recursion in a similar way, no?
That point is made in the article. You'd need to invent a language for writing the formulas as strings, and handle it with a scanner, parser (for which you pick an output tree format). Then do the differentiation on the tree format, and finally reformat the transformed code back to a string to be passed to the character-based "eval".
The homoiconicity is important. Python and ECMAScript (don't use "JavaScript", it's a trademark of Oracle's) are not homoiconic. Consider this Monte translation of OP's blog post: https://github.com/monte-language/typhon/blob/master/mast/fu... The main feature present in Lisps and in Monte but not in Python nor ECMAScript is quasiquotation. ES has template literals, and Python 3 has f-strings, but neither language can use them for pattern-matching, only value-building.
Yeah, I thought of saying more on the code I used from SICP, but don't feel i could add much to their treatment.
I think you could write something in other languages, but it would likely be incumbent to you to lex/tokenize the data. And then to convert back to a string to send back to eval.
You can also do something similar with annotation processing in Java. Or the macro languages in newer languages. Much more difficult to me, though.
For highlighting the features, I don't know of much. I like lisp because i find it fun. In large from the parsimony of the language. Though, i think it is layered in ways we often gloss over in that phrase.
To circle back on this, I found that I have a bit of bad interaction between some overrides of the CSS I did and the "htmlization" of my buffers to make the output.
Regardless, did a quick rerun with a theme that should have been a bit more compatible. Will have to see about fully fixing up the general export some time. Again, thanks for the feedback!
That is a much more comprehensive treatment! For anyone that is curious on how you could inspect a program in python, I think that is a great article to compare the two. (Indeed, I didn't know the syntactic tree api.)
So not requiring a 'parser' in that sense is not really a feature of full (modern) Lisp. (Early Lisps didn't use lexical scoping, and used f-expressions or similar i.e. less of a compile- vs. run-time separation, so it may have worked better back then for what seems to have been the original purpose of Lisp, but they may also have squinted and limited themselves via convention, not sure.)
This doesn't mean that there's no usefulness for the 'first-level parsing step' that gives you s-expressions: in some cases you might be handling a context insensitive language like yours. Also, it makes extending the language much more painless (macros easily compose, or more to the point, you can easily invent ad-hoc new languages on top of s-expressions used as inputs for macros, and won't (ever, I think) have problems with their boundaries becoming ambiguous).