Home
the-dark-batpup-returns
Eric TF Bat's Journal
It's People Like You What Causes Unrest
Why Lisp 
14th-May-2008 01:13 pm
the-dark-batpup-returns
[info]jeff_duntemann commented "Lisp ties my head in knots", so I thought I'd help him out. The Aha! moment for me with Lisp came from seeing the association with Abstract Syntax Trees, which are a language compiler's internal representation of a line of code. Consider, for example, the quadratic equation, which can be expressed in Pascal syntax as (-b + sqrt(b*b - 4*a*c))/(2*a), where sqrt() is the square root function and * is the multiplication operator. (Note that this deliberately misses out the plus-or-minus part; I'll get to that later.) If you feed this into a compiler, what you get looks a bit like my illustration at right: a tree of operations, rearranged so that each operator has its operands as branches. If you were to convert an AST like this into text, using parentheses to show the tree structure, it would look like this:

(÷ (± (- 0 b) (√ (- (× b b) (× 4 a c)))) (× 2 a))

Lisp is, in essence, the textual form. The syntax is different - it doesn't use × and ÷ because it started in the 1950s with typewriter terminals, just like Fortran, but the differences are trivial. It takes some concentration to see how we get from the diagram to the Lisp form, but it makes sense. And once you have that sorted out, whole new vistas open up.

One significant step is the idea that you can define functions that operate on code as if it were data. I could write a function called expand-plus-minus, for example, that took a list like the above and turned it into two lists, one with a plus in place of the ±, and the other with a minus. Thus, without knowing anything about the quadratic equation, my function can create two new pieces of code. Compiling and interpreting blur into irrelevance, and it becomes a genuinely powerful tool.

That's really the key to Lisp. It's what makes the Lots of Irritating Superfluous Parentheses necessary and valuable, rather than irritating. Any time anyone refers to Lisp as like oatmeal with fingernail clippings, or asks me "how can you read it with all those parentheses?", I have to agree with whoever it was who replied by opening up a book, pointing to a page and asking, "How can you read the words in among all those spaces?"
Comments 
14th-May-2008 03:51 am (UTC)
[info]tedeisenstein
I grew up on Fortran, Basic, and Cobol, but my father had an early HP calculator, for which he carefully wrote out the calculation before typing it all in, so something looks vaguely familiar in that formula: is that Reverse Polish Notation I see?
14th-May-2008 03:57 am (UTC)
[info]etfb
Reverse Polish is used in languages like Forth and Postscript, and it's the other way round. To convert a tree to RPN, start with the leaves and do the operators last, so the equation in question would be this in Forth:

0 b - b b * 4 a * c * - sqrt + 2 a * /

... Well, except for the fact that you're dealing with floating-point numbers so you need to use F+ and F* instead of the integer-only + and *, and of course sqrt is really called FSQRT. Oh, and b FNEGATE is more efficient than 0 b F-. But you get the idea.
14th-May-2008 03:59 am (UTC)
[info]tedeisenstein
Oh. So it's reversed Reverse Polish?
14th-May-2008 04:12 am (UTC)
[info]etfb
Yes, it's called Reversed Hsilop.
14th-May-2008 04:22 am (UTC)
[info]catsidhe
LISP is prefix notation, RPN is postfix, and regular algebra is infix. That is, in regular algebra the operator is in the middle: a + b.

In LISP, the operator is the head of a list (treat the first element as the operator, and do it to the rest of that list): (+ a b), which has the benefit of it being easy to notate a long list of things to do things to (such as (* a b c d e ...)), but it requires some special treatment when this doesn't make sense, ie., (/ 3 2 17). Does it return 3/2 and ignore the 17, or does it return (3/2)/17?

RPN is the single best option for using a stack to keep track of your calculation. You push a certain number of numbers on to the stack, then the operation, which pops the requisite numbers off again and does the operation on them, then pops the answer in their place. If you turn a stack sideways, so that the top is ---> that way, then the operation 3 4 * 4 + goes:
3
3 4
3 4 *
12
12 4
12 4 +
16
The downside is that you can't trivially operate on a long list of numbers, you need some way of specifying how many to pop. The simplest way is to enter, say, a b c d + + + (= ((d+c)+b)+a)
14th-May-2008 04:32 am (UTC)
[info]etfb
Some languages have a secondary stack that holds nesting levels, so you can define a word like { that says "save the current data stack depth on the nesting stack", and } that says "calculate how many items have been pushed on the data stack since the last matching { command and do something with the resulting list". So with a facility like that, you could do something like { 1 2 3 4 } + and end up with 10 on the stack. That would require either a special set of list operators, or else a change to how the language works... both of which are perfectly normal in Forth, because If you've seen one version of Forth, you've seen... one version of Forth, and Forth programmers agree: standards are a good thing -- everyone should have one!
14th-May-2008 05:10 am (UTC)
[info]jwm

"How can you read the words in among all those spaces?"

This is rather disingenuous. It's the need to track scope that makes the amount of parentheses so awkward to work with. If it were easy, we wouldn't need crutches like code indentation and parentheses highlighting in our editors.

14th-May-2008 05:22 am (UTC)
[info]etfb
Not really. The context becomes fairly obvious. I'd say it's no worse than the args to a typical Windows or X-Windows system call, which I'd hate to have to read without tooltips.
Leave a Comment to the Entry
Profile
User: [info]etfb
Name: Eric TF Bat
Page Summary
Latest Month
October 2008
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Search
This page was loaded Oct 6th 2008, 8:52 pm GMT.