Matt's Blog

Learning Lisp (1)

Wed Aug 2 21:01:16 BST 2006

Learning Lisp has been on my to-do list ever since I read "The Art of Unix Programming" by ESR. Probably even before that, when I realized that most of the power of Mathematica comes from the functional programming aspects. The ability to define higher order functions that act on complex objects rather than just different types of data is empowering. Once I became aware of functional programming I started with Ocaml, a dialect of ML (Meta Language - originally used to write proof proving systems). Ocaml is great because it is strongly typed and the language itself checks that the program obeys the typing. This means that many errors are detected at compile time rather than run time, speeding up the debugging process (see the SPARK programming language for the logical extension of this process to a language that is very robust due to the enforcement of information flow constraints at compile time, but this is another entry).

Lisp is not strongly typed, and the syntax of Lisp initially seems ugly due to the large number of brackets. An intelligent editor is required to correctly match brackets together, or extreme discipline in indentation. Fortunately vim does the bracket macthing quite well, highlighting the matching bracket for whichever bracket the cursor is currently on.

Chapter 1: Introduction

Start learning Lisp using the [Practical Common Lisp] book, available both online and in dead tree form. In the first chapter the author explains his motivation for learning Lisp as it is "the programmable programming language". You can write languages in Lisp for whatever purpose that you need at that time, using Lisp's macro capabilities. This is also possible in Ocaml using the ocamllex and ocamlyacc tools to write a compiler for a domain specific langauge, so it is not immediately obvious that Lisp is the default choice. Quite probably learning Lisp will only serve as an introduction to the methods of thought required to write domain specific langauges in Ocaml, but it does seem to be the fundamental starting point.

The main modern variants of Lisp are Common Lisp (CL) and Scheme. The latter was originally designed as a teaching language and the core language has been kept as small as possible (think Pascal versus Delphi?). This makes it an easy tool to keep in the mind, you can be aware of all of its capabilities at once, at the expense of not omitting a number of useful features of CL. The author also claims that Scheme uses recursion more than CL, I'm not sure how true this is - I know that in Ocaml a lot of recursion is hidden in the definition of standard higher order function such as fold. Perhaps something similar happens in CL.

Chapter 2: the read-eval-print loop (REPL)

The book talks about using a particular IDE for learning Lisp, SLIME which uses Emacs as the editor. Emacs makes my hands hurt (too much chording to get the required commands), plus it doesn't play that well with Ion window manager. Ok, it is just that I like vim, and I can simulate the "code in one window, eval loop in the other" behaviour of Emacs fairly well by having two virtual desktops and switching between them.

Use gcl (GNU Common Lisp) as the Lisp eval loop. File extension is .cl or .lisp for vim to do the syntax highlighting correctly.

"Hello world!" in the lisp REPL. Either enter the string directly in the input, to define the atom "Hello world!", or use the format function. This function takes a variable number of arguments, the simplest case is two args, the output channel and the string to be output. If the output channel is "t" (true) then the output goes to stdout.

(format t "Hello word!")

This prints "Hello world!" as a side effect, the actual return value of the function is NIL.

Make the "print hello world" function into an actual function with

(defun hello-world () (format t "Hello world!"))

In the above "hello-world" is the name of the function, called by (hello-world), the empty brackets after that are the arguments of the function (nothing here), then the function definition.

Load files into the REPL using (load filename) where filename includes the extension eg "". Or the compiled file can be loaded using

(load (compile-file filename))

Chapter 3: Practical - a simple database

This chapter introduces the reader to the power of Lisp by writing a database application, introducing some powerful Lisp capabilities as it does so. "Functions", "macros" and "special operators" are all types of operators, differentiated in latter chapters.

Create a list with the list function: (list 1 2 3) creates the list [1;2;3] in Ocaml syntax. Create a property list or plist using the syntax (list :a 1 :b 2 :c 3). This is equivalent to creating an Erlang record with fields labelled a, b, c which are accessible using

(getf l a)

for example to get the value of the field named a of the list l.

Make a function that creates a plist representing the four fields of a record in a CD database:

(defun make-cd (title artist rating ripped)
  (list :title title :artist artist 
        :rating rating :ripped ripped))

For interest, this would be done in Ocaml as

type cd = {title :string; artist:string; rating:int;
let makeCD t a r rp = {title=t; artist=a; rating=r; ripped=rp};;

The extra complexity of defining the types of the fields in the record is weighed against the added robustness for error detection at compile time.

Define a global variable *db* to hold the list of CD records that comproses the database

(defvar *db* nil)

Then use the push macro to add records to the database

(defun add-record (cd) (push cd *db*))

This macro updates the global variable *db* by adding another CD record to the list. This is not trivial to do in Ocaml without using mutable variables or global hashtables (if these are used it does become trivial - define an initially empty hashtable for the database then update it as record are added). In a single assignment language such as Ocaml or Erlang the database state must be carried around in a state variable, which is updated when the event loop calls itself.

In Erlang the database could be a process with state consisting of the list of CDs, that is added to whenever a "{addCD, details}" message is recived by the process.

Enough for one night, more later.

[code] [lisp]


code (24)

erlang (5)
ideas (19)
lisp (1)
me (11)
notes (4)
ocaml (1)
physics (45)
qo (7)
unix (6)
vim (3)