Sunday, February 26, 2006

LISP

Programming experts such as Paul Graham and Alan Kay are saying that modern languages like Ruby and Python are converging towards LISP (list processing), one of the first languages, invented 0ver 40 years ago!
If you look at these languages in order, Java, Perl, Python, you notice an interesting pattern. At least, you notice this pattern if you are a Lisp hacker. Each one is progressively more like Lisp.
- Revenge of the Nerds
You can download a free copy of Paul Graham's book, On LISP, here. I noticed a wonderful explanation of bottom up programming (despised by top downers) in his introduction.

In a recent talk, Alan Kay (who invented SmallTalk) identifies the two most important things about LISP as its metasystem and late binding. I don't fully understand this but am working on it. He said that LISP is the most important idea in computer science.

btw Alan Kay is part of the Squeak team which is a modern implementation of these ideas.

Paul Graham summarises the nine new ideas of LISP (when it appeared) in his Revenge of the Nerds essay. Ideas 1-5 are now widespread but the last 4 have by and large still not entered the mainstream:
The nine ideas are, in order of their adoption by the mainstream,
  1. Conditionals. A conditional is an if-then-else construct. We take these for granted now, but Fortran I didn't have them. It had only a conditional goto closely based on the underlying machine instruction.

  2. A function type. In Lisp, functions are a data type just like integers or strings. They have a literal representation, can be stored in variables, can be passed as arguments, and so on.

  3. Recursion. Lisp was the first programming language to support it.

  4. Dynamic typing. In Lisp, all variables are effectively pointers. Values are what have types, not variables, and assigning or binding variables means copying pointers, not what they point to.

  5. Garbage-collection.

  6. Programs composed of expressions. Lisp programs are trees of expressions, each of which returns a value. This is in contrast to Fortran and most succeeding languages, which distinguish between expressions and statements.

    It was natural to have this distinction in Fortran I because you could not nest statements. And so while you needed expressions for math to work, there was no point in making anything else return a value, because there could not be anything waiting for it.

    This limitation went away with the arrival of block-structured languages, but by then it was too late. The distinction between expressions and statements was entrenched. It spread from Fortran into Algol and then to both their descendants.

  7. A symbol type. Symbols are effectively pointers to strings stored in a hash table. So you can test equality by comparing a pointer, instead of comparing each character.

  8. A notation for code using trees of symbols and constants.

  9. The whole language there all the time. There is no real distinction between read-time, compile-time, and runtime. You can compile or run code while reading, read or run code while compiling, and read or compile code at runtime.

    Running code at read-time lets users reprogram Lisp's syntax; running code at compile-time is the basis of macros; compiling at runtime is the basis of Lisp's use as an extension language in programs like Emacs; and reading at runtime enables programs to communicate using s-expressions, an idea recently reinvented as XML.
MIT students take a course in LISP, The Structure and Interpretation of Computer Programs, which is available on line.

I guess I should have paid more attention to Brian Harvey. I have his books on logo (cut down LISP) but didn't go the next step, he has also co-authored a book on Scheme, a dialect of LISP.

1 Comments:

Anonymous Chris Harvey said...

Hey Bill,
I'm a GNU emacs user and I've occasionally been trying to learn more lisp/elisp using GNU Emacs and sometimes Xemacs.
If you look closely at the Xemacs screenshot on Wikipedia you'll see the lisp tab. The Introduction to Programming in Emacs Lisp is a good place to start.
I put together some screenshots quite a while a back, they don't show much of what GNU emacs can do but they may give you some ideas.

9:25 AM  

Post a Comment

Links to this post:

Create a Link

<< Home