This blog is subject the DISCLAIMER below.

Tuesday, January 06, 2009

Lisp, the ultimate programming experience

It is not a yet-another-programming-language article. Lisp is so different from other “normal” programming languages. One of the core differences that it has “no syntax”.

Of course that claim “no syntax” has a double meaning. There is no programming language without a syntax. To get the trick you have to know how compilers work first.

Compilers first groups the input character stream into tokens (lexical analysis) and then parses the token stream into an abstract syntax tree intermediate representation. Then it either executes the statements (interpreted language) or generates machine instructions (compiled language)*.

The difference is that in Lisp, you directly write the abstract syntax tree. You also can manipulate it (“macros”). And you also can affect how the compiler does the lexical analysis (“reader macros”) !

Since you directly type the abstract syntax tree, there is no need for operator precedence rules. There is also no need for predefined/fixed operators; you can change or add any operator you want. There is also no limit on the number of the parameters of an operator (in Lisp the operator '+' is a function name and can take any number of arguments, not just two).

In Lisp, since you write the syntax tree directly, there is no need for restrictions on identifier names; identifiers (“symbols”) can be made up of any sequence of character (given you provide appropriate escape sequences when necessary (mostly only on space, and parentheses). Any number not valid in the current compile radix is a valid symbol : 1027F is valid identifier under base 10 but not under base 16. (you can change the current compiler radix by code). %@!$^%^@$%^&** is valid identifier too. In fact +,-,*,/ are all function names not “hardcoded-operators”. And you can rebind them too to any other function.

Imagine the possibilities with access to the abstract syntax tree. You can build your own programming language on top of Lisp. Hence Lisp is called the “programmable programming language”. Even the CLOS (Common Lisp Object System); the Lisp's Object Oriented implementation is implemented in pure Common Lisp macros.

Lisp can parse and evaluate Lisp expression if seven fundamental operations are provided by an underlying system. In fact Lisp was originally a mathematical model of computations of very high abstraction level, the counter part of a Turing machine model of computations. It was originally designed to write algorithms on paper, and was never meant to be implemented. It is when a student implemented those seven fundamental operations in machine code when Lisp was first executable around 50s. When the student first done; the professor who invented Lisp wasn't happy because Lisp wasn't mean to be executed; it was very much like executing mathematics.

Lisp was very popular in the research field, esp. for it's fast prototyping and dynamic programming. At one point of time programming language researchers were trying a new compiler every day using Lisp as a development platform. Lisp was so popular that it had it's own hardware that did execute Lisp instead of machine language (lookup Lisp Machines on wikipedia). But that hardware lost the battle for the much faster general purpose computers.

Lisp has many features from many decades that didn't seem to appear but in late 90 and early 21st century. One of those features is “closures”. Which are being discussed at this moment for addition in C++0x and OpenJDK 7.0. Lisp is also the first language to ever incorporate garbage-collection (I think around 80s if not 70s). But then on the hardware available it took hours to run the GC once, so Lisp was usually considered impractical. One funny thing about Lisp GC, people used to use it at day and leave do GC all night till they come back :D :D

Lisp is so fundamental that any language that ever achieves the power of Lisp is only yet-another-Lisp-dialect. Lisp is different is that it has nothing called “statements”. It's all composed of expressions. (Expression always evaluates to something unlike a statement**)

The current Lisp parenthesized notation is the same for instruction and data (of any structure). One of the funny things is that the current Lisp parenthesized notation was meant only for the underlying representation, and another FORTRAN-like syntax was going to be invented for humans but surprisingly the underlying representation won the race !!

+ A point of interest: Lisp is related somehow to the Lambda calculus. Because it's highly functional-oriented languages. Although it is not purely functional language because it allows destructive operations.

++ Another point of interest: I don't consider "Lisp" a language per se but a class of languages that contains all the Lisp dialects. Some stuff of this article only applies for the Common Lisp dialect. Scheme is also another Lisp dialect.

+++ Most Lisp compilers are compilers and not interpreters. Please don't comment that Lisp is slow.

* There is another type which generates an intermediate machine-independent language that would be converted later into specific machine dependent instructions using JIT (Just-In-Time compiler). Or it can be further interpreted. Like Java byte-code or .NET MSIL.

** if(x) 1; 0; is a statement; we can't say y = if(x) 1; 0;. Unlike y = x?1:0. So x?1:0 is an expression.

Sources: Paul Graham's articles (look up Google). Also read his great book : On Lisp. For the compiler every day thing look up "the Lambda papers" to know what the research was about (http://library.readscheme.org/page1.html).

Some people noticed that all languages by incorporating dymanic programming, closures (lexical scopes), GC, and functional programming are eventually turning into Lisp (which were made at the 50s). It's an interesting debate, but I personally see that being a Lisp needs such a transparent access to the syntax tree which is not usuably achievable unless you do something similar to the current Lisp syntax; that makes it yet-another-Lisp-dialect. Here you go: the famous Egg and Chicken paradox :D

If you are geek like me you'd enjoy this "blah blah" programming language history article :)

No comments: