6 ms·
Fun with Symbolic Derivatives in Lisp
- taeric 8y agoThis came from a thought I had after posting https://news.ycombinator.com/item?id=18312529 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 8y agoOnly tiny comment is that your syntax highlighting makes the names in function definitions almost impossible to read.
- taeric 8y agoThanks! I think it picked up the theme i had active at the time. Will pick a different one when back at that computer.
- taeric 8y agoTo 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!
- meken 8y agoGreat 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.
- fiddlerwoaroof 8y agoOne 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.
- fiddlerwoaroof 8y agoAlso, 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.
- pflanze 8y 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 8y agoThe 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/fun/symbolic.mt.md 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.
- taeric 8y ago
- S4M 8y agoNot really a feedback, but I wrote something very similar a bit more than two years ago: http://eskatrem.github.io/Newton-Raphson.html http://eskatrem.github.io/Newton-Raphson.html
- taeric 8y agoThat 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.)
- pflanze 8y agoNote 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).
- taeric 8y agoI 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?
- pflanze 8y agoHmm, 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".
- jhallenworld 8y agoFor 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 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/simplify.c#L208 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.
- taeric 8y agoNicely 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.
- jhallenworld 8y agoI 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...
- taeric 8y ago