Home > Lisp, Scheme > Spirit of Lisp

Spirit of Lisp

While working on my “Scheme interpreter made in Java” I often thought about Lisp language itself. My interpreter is very small and simple, yet very powerfull, so I was trying to understand: where lies the core of it’s power. Since I’m learning OCaml now it is interesting to compare both languages, and to understand what makes Lisp different. At the beginning there were a lot of confusion in my head, so this article is an attempt to bring an order in my chaotic thoughts.

People often hear about very important feature of Lisp which is “code is data”. But, my impression is that this feature is rather secondary. My current interpreter doesn’t have any macro facility yet, it even doesn’t have car and cdr, and it’s still very capable. So, I think that core of the Lisp lies elsethere, not even in ability to process lists.

I think that Lisp was started as a functional programming language, so Lisp programs should be a set of function definitions and one expression to evaluate. Expression is a combination of function invocations, where result of one function is passed as argument to another. A distinguishing feature of Lisp is that function invocation is written as (func arg1 arg2 … arg3) instead of mathematical notation func(arg1, arg2, …, arg3). Mathematical notation is preferrable if used in expressions like y=func(arg1, …), but Lisp’s notation is preferrable if result of one function is directly passed to another : (func1 (func2 argX) argY). Lisp’s notation is also preferrable if function itself should be evaluated: ((lambda (x) (+ x 1)) 2). Compare with mathematical-like notation used in C for invocation of function referenced by pointer: (*func) (2, 5), which is more confusing for me.

Then I started learning Lisp, lambda looked like a magic for me: function is “produced”. Now it’s more simple: lambda is just a delayed expression. My implementation doesn’t analyze “expression” part of lambda, it is just stored as is. Then function returned by lambda is evaluated, it my implementation just maps function arguments to their values in environment, then evaluates lambda-expression. Other implementations may perform some optimizations, but they are not nesessity. If runtime itself supports recursion, then lambda will be automatically recursive.

Parentheses-based syntax, together with define, lambda and cond provide expressive, simple and clean functional core which is, in my opinion, a spirit of Lisp. My current inperpreter has implemented just that core, and I believe that provided language could already be called “Lisp”. It is definetely not OCaml because of syntax and also because expressions are evaluated dynamically. Dynamic evaluation makes implementation very simple. Note that there are no single mention of lists in language defined above: parentheses are used only to group functions and their arguments, in other words: to define structure of expression. Implementation decides how to represent parsed expression structure internally. I use ArrayLists, for example.

For more complex programs language should provide compound data structures. There are two basic choices: arrays and lists. For funcitonal programming lists are preferrable. “cons” creates lists, “car” returns content, “crd” advances to the tail of list. For functional programming sharing of data is safe. Introduction of lists also means that some memory management like garbage collection should be provided

Now I come to the main source of confusion. Then Lisp prints list objects, it uses the same parentheses-delimeted format as for entering expressions. I don’t know who made that choice, but it made Lisp both powerful and confusing. Next step was (quote), which allows to input list structure using the same syntax as used for output of lists, which is the same syntax as used for specifying program structure. From this very moment it becomes clear that single parser is used to create data lists and program, so internal representation of program and lists are the same. Starting from this moment it is possible to write “eval” in Lisp: parser will get parentheses-separated expression as data and will turn it into internal representation, then list-based functions will allow to traverse that expression. And this is a foundation of macros.

All written above is just my current opinion. Now I start to remember that good books like “HtDP” avoid mixing lists and expressions. Bad books such as “The Scheme programming language” start mixing lists and expressions very early. I think it is important to understand the difference, because it makes all things simple and straitforward. Paul Graham also thinks the same.

Categories: Lisp, Scheme
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: