Fun with Symbolic Derivatives in Lisp

http://taeric.github.io/CodeAsData.html

by taeric • 8 years ago

84 40 8 years ago

taeric.github.io

taeric9• 8 years ago

This came from a thought I had after posting https://news.ycombinator.com/item?id=18312529

Any feedback is greatly welcome. Both in areas I have wrong in the programming, and in general presentation. Thanks!

basil-rash• 8 years ago

Only tiny comment is that your syntax highlighting makes the names in function definitions almost impossible to read.

taeric9• 8 years ago

Thanks! I think it picked up the theme i had active at the time. Will pick a different one when back at that computer.

meken• 8 years ago

Great post! A few observations.

- 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.

fiddlerwoaroof2• 8 years ago

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.

pflanze8• 8 years ago

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).

myWindoonn• 8 years ago

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.

taeric9• 8 years ago

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.

kazinator8• 8 years ago

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".

S4M• 8 years ago

Not really a feedback, but I wrote something very similar a bit more than two years ago: http://eskatrem.github.io/Newton-Raphson.html

taeric9• 8 years ago

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.)

pflanze8• 8 years ago

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).

taeric9• 8 years ago

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?

pflanze8• 8 years ago

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".

jhallenworld2• 8 years ago

For comparison, here is symbolic derivatives in C. I wrote this in 1990 for school project:

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.

taeric9• 8 years ago

Nicely done! I'm curious if you used the SICP or similar literature as inspiration, or if this was just a natural way that you thought to do it.

jhallenworld2• 8 years ago

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...

Fun with Symbolic Derivatives in Lisp

Related Stories