Lisp idioms: s-expressions, car/cdr/cons, and recursion

Why Lisp, briefly

The COMP 456 exam lets you answer programming questions in Prolog *or* Lisp, and the expert-system project may be built in either. You do not need to *write* Lisp fluently, but you must be able to read it — and the genetic-programming material in M8 represents evolving programs as Lisp trees, so a reading-level grasp pays off twice.

Everything is an s-expression

Lisp code and data share one syntax: the s-expression (symbolic expression), a parenthesised, prefix form (operator arg1 arg2 ...). The operator comes first, so (* 4 6) means $4 \times 6 = 24$ and (+ 1 2 3) means $6$. A nested expression like (* (+ 1 2) 4) is evaluated inside-out: (+ 1 2) → 3, then (* 3 4) → 12. Because code *is* a list, programs can be manipulated as data — the property genetic programming exploits.

The three list primitives

Lisp lists, like Prolog lists, are head-and-tail — just with different names:

- car returns the head (first element): (car '(a b c)) → a. - cdr returns the tail (rest): (cdr '(a b c)) → (b c). - cons builds a list by prepending an element: (cons 'a '(b c)) → (a b c).

car/cdr/cons are exactly Prolog's [H | T] decomposition and construction, renamed. (The quote ' says "treat this list as data, do not evaluate it".)

Worked example — factorial in Lisp

defun defines a function; if chooses a branch; recursion replaces loops — the same base-case-plus-recursive-step shape as the Prolog fact/2:

(defun factorial (n)
  (if (= n 0)
      1
      (* n (factorial (- n 1)))))

Read it: define factorial of n; if n = 0 return 1 (base case), else return n * factorial(n-1) (recursive step). (factorial 5) evaluates to 120 — the very same computation as the Prolog and Python versions, just in prefix s-expression form.

Programs as trees (preview of M8 genetic programming)

Because an s-expression is a tree, genetic programming (Koza) evolves programs by treating each program as a Lisp tree and swapping subtrees between two parents. If one parent has the subtree (* 4 6) at a chosen node and another has (cos 3), crossover exchanges those subtrees to build new programs. The payoff: a subtree swap always yields a syntactically valid program (given a *closed* function/terminal set), which is why trees are the natural representation for evolving code.