Fun with Symbolic Derivatives in Lisp
taeric.github.io
taeric.github.io
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).
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)
(+ (* x 2) 12)
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".
(+ (flet ((f (a) (* a a))) (f 10)) 2)
(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).
[1] https://en.wikipedia.org/wiki/Abstract_syntax_tree
(Perhaps also see https://en.wikipedia.org/wiki/Abstract_semantic_graph )
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!
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.
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.
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 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".
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.)
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.
macros just return s-expressions - no AST data
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*)))
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.
(let* ((protoAST (cons expr* env))
;; could do:
(AST (protoAST->AST protoAST)))
..)
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.
Yes, that's why I actually had said "by grouping the resulting s-expr with a context and a correct tree-walker". True, you could make that
(let* ((protoAST (list expr* env core-CL-walker))
..)
...)
[1] I don't know whether there is any standardization of such a thing. Probably not since macroexpand-all also isn't standard.
No, they are nested lists of tokens.
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:
http://git.savannah.gnu.org/cgit/gawk.git/tree/awkgram.y
in which the YYSTYPE is of type "INSTRUCTION *", a pointer to the structure defined here:
http://git.savannah.gnu.org/cgit/gawk.git/tree/awk.h?id=e24c...
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.
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)))
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).
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.
https://en.wikipedia.org/wiki/Abstract_syntax_tree pretty much nails it.
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.
In an AST the elements are already classified according to some syntax. In S-expressions this is not the case.
https://github.com/jhallen/joes-sandbox/tree/master/x/xquiz
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.
The derivative taking function is here: https://github.com/jhallen/joes-sandbox/blob/master/x/xquiz/...
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.
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...
Regardless of any of that, really cool project. Being for a class underscores the deadline you did that in. Thanks for sharing!
Any feedback is greatly welcome. Both in areas I have wrong in the programming, and in general presentation. Thanks!
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!
- 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.
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).
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.
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".