A little LISP for OSX
Harold Thimbleby
25 December 2003

This is a simple Java implementation of LISP, an eager tail-recursion-optimised statically-scoped dialect. The LISP is supported in an editor, providing an interactive front end — if you are reading this file in that front-end, you can easily evaluate all examples.

The user interface

Select this expression: (* 2 3 4 5 6 7), between and including the brackets. The expression is a way of calculating 7! in LISP: the function * multiplies the parameters, here 2 to 7. Evaluate the expression by typing ⌘E (or by using the Evaluate>Evaluate after menu). When the expression is selected and evaluated, it will become these two lines, in red and blue: 

(* 2 3 4 5 6 7)
5040

In fact, when you select anything and type ⌘E you'll find what your selection will go red and the answer will be in blue, and the fonts will change to Courier. Select the coloured text below:

(new (fact n) ; define the factorial of n
   (if (≤ n 0) 1
       (* n (fact (- n 1))))
)

and type ⌘E to evaluate the selection. Here, the result will be <closure>, because fact is defined to be a closure (a function you can call, together with any names it uses). 

Having defined it, you can now compute factorials. Select this red text: (fact 6) and type ⌘E to evaluate it. You will get 720, the factorial of 6, written just after the (fact 6) expression. 

Try editing the expression you've just selected, the original(fact 6), say to (fact 7), and evaluate it again with ⌘E. The 720 will be replaced with a new value, in this case 5040, if you'd selected and evaluated (fact 7).

The usual undo command, ⌘Z, will remove the changes to the displayed text, not the changes to the LISP engine. So you can handily type ⌘E⌘Z to check results without messing up the text file.

You can change the fonts between input and output, using short cuts ⌘1 and ⌘2. You'll also find it useful to show the Evaluate>Show messages window (see Evaluate menu), because it also tells you if brackets are mismatched and other errors.

You can change the LISP fonts and colour preferences. If you don't like the colours, fonts, or old results being replaced, you can change things in the LISP>Preferences dialog box. 

You can also change the output format to be on the same line, so if you evaluate (* 2 3 4 5) with ⌘E you get (* 2 3 4 5) ⇒ 120, which uses an arrow rather than a newline to separate input and output. The Evaluate menu has a few other options, for example Evaluate>Evaluate to another window puts the results of the evaluation in another window, so it won't mess up the window you selected the expression in.

More LISP examples

(new (append x y) ; define append
	(if 
		(not x) y
		(not y) x
		(cons (car x) (append (cdr x) y))
	)
) ⇒ <closure>

; try out append
(append '(a b c) '(d e f g)) ⇒ (a b c d e f g) 

; try the member function
(member 1 '(7 8 9)) ⇒ Ø

(member 1 '(7 8 1 9)) ⇒ (1 9)  

Definition of the LISP

The LISP is a basic eager, lexically-scoped, tail-recursion LISP (like Scheme) as follows:

; introduces comment to the end of line

'x is an abbreviation for (quote x)as is conventional. However, the LISP>Preferences provides an option so that a name x can be auotmatically treated as 'x rather as an error if it is unbound. Note that if the option is set, all correct LISP programs are still correct, but some 'incorrect' programs — ones that did not define names — become correct.

Numerals are atoms that are bound to the number value of the numeral. In other words, 23 is an atom, and when evaluated you get the usual value, namely the number 23. In standard terms, “numbers self-evaluate,” and so (quote 3) can be written as just 3 (this is like the Preferences option available for atoms generally). You can write (+ 1 2) which is far easier than (+ (quote 1) (quote 2))or even (+ '1 '2). Numerals are decimal digits, optionally preceded by a single + or - sign. Note that --1 would be treated as - followed by -1. The number +1 and the number 1 are considered the same.

Nil self-evaluates, and can be written Ø, which you can type easily by using ⌘0 (i.e., command-zero, not command-O, which opens a file).

An atom can be written in quotes, as in "hello world". Within quotes, \n and \" mean newline and a quote, respectively. Most times I write "x" I usually mean '"x" (i.e., (quote "x")). An atom is not printed in quotes, so '"\n" will give you a newline.

Special forms 

Normally, every parameter — including the function itself — in a list is evaluated. Thus (f a b c) will evaluate all of the forms f, a, b, and c, then apply the function (that f evaluates to) to all the evaluated values of a, b, and c. Note that the order of evaluation is not defined, merely that everything is evaluated.

If the function position does not evaluate to a function, this is an error. However, LISP>Preferences provides an option to treat non-functions as identity functions. So, for example (1 2) would have value (1 2) if the option is selected, as if replacing the list with (list 1 2).

Special forms, however, do not evaluate parameters in a standard way. Thus (if a b c)is a special form, because b or c is not evaluted if they are not needed. The order and nature of evaluation depends on the special form; for example, λ does not evaluate its second parameter at all. Quoting is such a commonly used special form that there is a handy notation for it: instead of writing (quote a) you may write 'a — in either case, quote does not evaluate its parameter at all.

Here follows an alphabetical list of all special forms.

(and a b c d…)
Evaluates parameters in order (i.e., left to right), and returns the logical and of their values. If any value is Ø, the and returns Ø immediately.

(from n)
Returns a list of parameters, starting at parameter n. If the actual list is not Ø, so (car (from n)) ≡ n, where n is a local parameter. For example, (new (list s) (from s)) gives the standard definition of list.

(if a b c) 
If a is not Ø, the result is b; if it is Ø, the result is c. Can also take more parameters:  (if a b c d e …) ≡ (if a b (if c d (if e …)))

(λ (args…) body)
(lambda (args…) body)
Both forms have the same meaning, and define a closure with parameters args; the two forms are synonyms. You can type λ easily by using ⌘L. See also from.

(let e declarations)
Evaluates e in the scope of the declarations. Declarations are of the form (name.value). Example: (let (cons e e) (e.4)) has value (4.4).

(letrec e declarations)
Like (let…) except the declarations are in their own scope. Used for defining recursive functions. 

(new n e)
Declares n and assigns value of e to n. The semantics are: (new n e).s = ((λ (n) s) e)If n is a list, a function is defined: (new (n a b…) e) ≡ (new n (λ (a b…) e)), or (new (n a b…) e) ≡ (new n (letrec n (n.(λ (a b…) e)))) if the function is recursive.

(or a b c d…)
Evaluates parameters in order (i.e., left to right), and returns the logical or of their values. If any value is not Ø, the or returns that value immediately — it is a short-cut operator like and. 

quote 
Standard definition: (quote x) is x unevaluated. (quote a b c) is an abbreviation for (quote (a b c)). As usual, quote can be abbreviated using '.

(set n e)
Evaluates e and assigns to n. The name may be a name declared by new or may be a local variable (e.g., a parameter). Like new, set can be used to define functions easily.

(seq a b c d e…)
Evaluates left to right and has value of the right-most term

Functions

(= a b) (≠ a b)
Strict equality and inequality tests. Equal numbers and equal atoms are =. Lists are only = if they are the same list. Compare this function with equal. If two things are = they are always equal.

<, >, ≥, ≤
Numeric comparison (see also = and ≠).

(+ s) (* s)
Add and multiply; take any number of parameters. For example, (* 2 3 4) ⇒ 24.

(/ a b) (% a b)
Divide and remainder. b must be non-zero.

(apply f list)
Evaluates (f list)

(atom s)
Return true if s is an atom, Ø otherwise. Note that Ø is an atom.

(boot-code)
Evaluates to the built-in bootstrap code. Useful if you lose the boot file!

(car s)
Head of list s.

caar cadr cdar cddr
The usual combinations of car and cdr, defined by, e.g., (new (cadr s) (car (cdr s))).

(cdr s)
Tail of list s.

(cons a b)
Returns (a.b), a list with head a and tail b.

(equal s t)
Standard definition of equal. Note that = compares for identically equal, equal compares for structurally equal.

(fold f i s)
Standard definition of fold. (Used to define arbitrary length + and * functions.)

(language f)
Change the language from LISP to f. The function f should take a single parameter, namely the expression it is compiling and running, and it should return the output of that program. The value returned by language is f.

(list a b c…)
Return the list (a b c…). An abbreviation for (cons a (cons b (cons c… Ø))). Defined as (new (list s) (from s)): see from

(map f s)
Standard definition of map. Make a list by applying f to each element of s.
	
(member a s)
If a is in s (according to =) return the first list starting a, otherwise return Ø. See the examples earlier in this note.

(memberf f a s)
If a is in s, as defined by f, return the first list starting a, otherwise return Ø. memberf is a generalisation of member, using a parameter f rather than =. You may like to use (memberf equal a s), which is more general than member but slower.
	 
(not s)
Return true if s is Ø otherwise Ø. It is of course a convenient test for whether a list is Ø.

(number s)
Return s if s is a number, Ø otherwise. Note that 0 is treated as true by (if …) because it is not Ø.

(open-window url)
Opens the URL in a new window. Naturally, the URL can be anywhere on the internet. Note that as most URLs have got dots in them, you have to write something like (open-window '"http://www.uclic.ucl.ac.uk/harold/lisp/boot.rtf") — note the use of both sorts of quote! If you use a partial URL, it will be taken in the context of the window running the LISP command.

(print s t u…)
Prints its arguments, and has value (list s t u…). 

Variables

A variable boot counts the number of reboots. (See the Evaluate menu.)

Booting

The LISP>Preferences dialog defines a boot file, which is read when LISP is booted. When the special form (booted version) is executed the LISP compiler stops recognising all built-in functions except special forms (like λ and from). The boot file defines apparently 'recursive' functions, such as (new (car s) (car s)) because the compiler treats the second use of (car) as a built-in function call, but the first use as a definition of a new name. When booted is called the special forms disappear, and then car behaves as a first class function.

The LISP>Preferences dialog allows you to choose and open the boot file. If no boot file is specified a built-in boot sequence is run, which defines the LISP described here.

If you lose the LISP boot file, (boot-code) gets you the code to evaluate: you'd reformat it and save it to a new boot file.

Semantic features

Numbers are implemented as Java ints, so they are –2,147,483,648 to +2,147,483,647 inclusive. Overflow, but not division by zero, is ignored.

Parameter lists are evaluated right-to-left (as the cons cells building the list are constructed), which means that if you do, say, (fcn (set u 1) u), the last parameter to fcn will be u before the set is executed, so it will possibly be undefined. If you want to evaluate left-to-right, use the special form seq.

Closures are printed as <closure>.  

All errors 'undefine' values, which are printed as ☹…. Thus, an unbound variable x becomes ☹x. Unbound local parameters (i.e., after calling a function with too few parameters) become ☹unbound — at run time we don't know the names anymore! 

Numeric functions require numbers. Division by zero causes an error, so (/ 3 0)  results in ☹(/ 3 0).

Note that (if ☹… … …) evaluates to ☹(if […])], without the second and third parameters shown, to save space in the error result. However, if, as a special form, is not strict; so (if 'true 1 […]) evaluates to 1. 

Curious features

3a is two atoms, but a3 is one atom.

A list containing a dotted pair effectively ends the list. Thus (1 2.3 4) will ignore the 4. (Recall that (1 2.Ø) is (1 2), so there can't be anything beyond the 3.) You should probably have typed (1 (2.3) 4) if that's what you meant. Such errors are reported in the Messages window, which you can display at any time using the menu Window>Show messages.

BUGS

The message window does not pop up when errors are reported.

Errors tend to get very long.

My definition of (new …) does not permit straightforward definition of mutually recursive functions. For example,

(new (f) …g…)
(new (g) …f…)

will take the first mention of g  as unbound, where it is treated as ☹g in the body of f. 

The solution is to make an initial declaration, so g is bound, then rebind it:

(new (g) Ø)
(new (f) …g…)
(set (g) …f…)

When the SECD machine runs out of memory (e.g., too much recursion) nothing can be recovered: it has to be rebooted.

Reference

Henderson, P. (1980) Functional Programming — Application and Implementation, Hoare, C. A. R. , ed., Prentice-Hall International Series in Computer Science.

↪ More examples ↩

; flatten removes all brackets
(new (flatten s)
	(if
		(not s) s
		(atom (car s)) (cons (car s) (flatten (cdr s)))
		(append (flatten (car s)) (flatten (cdr s)))
	)
)

(new (range n) ; makes a range, so (range 3) -> (1 2 3)
	(seq
		(new (auxrange c n) 
			(let
				(if (≤ head 1)
					c
					(auxrange (cons (- head 1) c) n)
				)
				(head . (car c))
			)
		)
		(auxrange (cons n Ø) n)
	)
)

; another way to define factorials; (f n) = n!
(new (f n) (apply * (range n)))

(new (format n) (list (if (< n 10) '" " '"") n))

; make a list of factorials
(flatten 
	(map 
		(λ (n) (list (format n) '"! =" (f n) '"\n"))
		(range 10)
	)
) 

And we should get this result:

(  1 ! = 1 
   2 ! = 2 
   3 ! = 6 
   4 ! = 24 
   5 ! = 120 
   6 ! = 720 
   7 ! = 5040 
   8 ! = 40320 
   9 ! = 362880 
  10 ! = 3628800 
)