Lisp - breaking a program into pieces

, updated

한국어: Lisp - 프로그램을 조각내기

A while ago I wrote a small Lisp interpreter in Haskell. It only has define, lambda, cond, ' (quote), eq?, car, cdr, cons, and basic arithmetic built in. Even with almost nothing built into the language, defining small functions one by one and combining them into the next ones makes it straightforward to put together the tools needed.

Basic functions

The first things needed are null? to check whether a list is empty, and not for logical negation. null? compares its argument against the empty list '() with eq?. not returns #t when its argument is #f, and #f otherwise. This interpreter has no else keyword for cond, but since any value other than #f is treated as true, putting #t as the condition of the last clause does the same job.

> (define null? (lambda (x) (eq? x '())))
> (null? '())
#t
> (null? '(1))
#f

> (define not (lambda (x) (cond
	((eq? x #f) #t)
	(#t #f))))
> (not #f)
#t
> (not 3)
#f

Working with lists recursively

Functions that work on lists generally follow the same recursive shape. If the list is empty (null?), the recursion stops; otherwise, the function processes the first element (car) and passes the rest of the list (cdr) back into itself.

map walks through a list to the end, applying fn to each element and joining the results back together with cons. filter has almost the same structure, except it only keeps an element when fn returns true and skips it otherwise. Passing a combination of not and null? defined earlier leaves only the elements that are not empty lists.

> (define map (lambda (fn l) (cond
	((null? l) '())
	(#t (cons (fn (car l)) (map fn (cdr l)))))))
> (map (lambda (x) (* x 2)) '(1 2 3))
(2 4 6)
> (define filter (lambda (fn l) (cond
	((null? l) '())
	((fn (car l)) (cons (car l) (filter fn (cdr l))))
	(#t (filter fn (cdr l))))))
> (filter (lambda (x) (not (null? x))) '(1 () (2) () 3))
(1 (2) 3)

list-ref, which takes the element at a given index, works the same way. Each recursive step drops the first element of the list and decrements the index n by 1, returning the first element once n reaches 0. Since the interpreter had no = for comparing numbers, I used eq? here to compare against 0.

> (define list-ref (lambda (l n) (cond
	((eq? n 0) (car l))
	(#t (list-ref (cdr l) (- n 1))))))
> (list-ref '(11 22 33 44 55 66) 3)
44

2D lists

With a similar recursive structure, replicate builds a list that repeats a value x n times, decrementing n down to 0 while prepending x with cons.

> (define replicate (lambda (x n) (cond
	((eq? n 0) '())
	(#t (cons x (replicate x (- n 1)))))))
> (replicate 0 7)
(0 0 0 0 0 0 0)

A list of lists can be treated like a two-dimensional array. Writing map-2d to apply a function to every element of a 2D list does not require writing a new recursive function from scratch. Nesting the map function from earlier twice is enough, with the outer map walking the rows and the inner map walking the elements of each row.

> (define map-2d (lambda (fn ll)
	(map (lambda (l) (map fn l)) ll)))
> (map-2d (lambda (x) (* x 10)) '((1 2) (3 4)))
((10 20) (30 40))

The same applies to replicate. Passing the single row (0 0 0) from (replicate 0 3) into an outer replicate produces a 3×3 board filled with 0. Applying map-2d to it updates the value of every cell at once.

> (define board (replicate (replicate 0 3) 3))
> board
((0 0 0) (0 0 0) (0 0 0))
> (define board (map-2d (lambda (x) (+ x 9)) board))
> board
((9 9 9) (9 9 9) (9 9 9))