Functional Programming (Lisp, Scheme, Clojure, etc.)

Lisp is an old yet adaptable programming language with its roots in early artificial intelligence work. It's a very flexible language, though it's often closely associated with functional programming. The two most popular Lisp camps these days are Common Lisp (which is an ANSI standard that unified lots of earlier Lisp dialects) and Scheme (which is more of a pure/academic dialect heavily focused on functional programming and recursion). Clojure is a lisp-like language that compiles for the JVM, and can access Java's libraries.


Comments in Lisp, Scheme, and Clojure begin with a semi-colon (;).

Scheme files usually have the extension .scm. Lisp files might have the extension .lisp or .lsp. Clojure uses the file extension .clj.

A good multi-platform lisp is clisp, and a good scheme is guile.

This is a Rosetta Stone between lisp, scheme, and clojure, with content like:

Common LispSchemeClojure
(atom x)(not (pair? x))(not (list? x))
eq, equal, =eq?, equal?, ==
car, firstcarfirst
cdr, restcdrrest, next
(lambda (x) (* x x)(lambda (x) (* x x))#(* % %) (fn [x] (* x x)
set, setq, defundefinedef, defn

Lessons from the Little Schemer

First, go buy The Little Schemer by Dan Friedman and Matt Felleisen. It's not only a good initial intro to functional programming, but also one of the best instructional books of any kind.


foo is an atom. 42 is an atom. *uck_!0u is an atom. All of those are also S-expressions. () is not an atom; it's an empty list.


(foo bar bat) is a list. (Nerf) is a list. ((pizza pie) garlic breath) is a list. These are all S-expressions.


car returns the first element of a list. (car '(ice cream sandwich) returns (ice). (car '((a b c) x y z)) returns (a b c). (car '()) has no answer, because car only works on non-empty lists. (car 'elephant) has no answer, because car doesn't do anything with atoms.


cdr is pronounced "could-er" (although I always say it to myself as "cedar").

cdr takes a list, and returns all but the first element. (cdr '(a b c d)) returns (b c d). (cdr '((rabbit fox) (bear eagle) pterodactyl) returns ((bear eagle) pterodactyl). (cdr '(hedgehog)) returns (). (cdr 'Lamp) give no answer, because cdr only works on lists not atoms. (cdr ()) is also gives no answer, because cdr doesn't work on empty lists.


cons takes two arguments—any S-expression, and a list—and returns a combined list. (cons 'happy '(trails again)) returns (happy trails again). If the first argument is not an S-expression or the second argument is not a list, cons gives no answer.


(null? '()) returns True. (null? '(x y z)) returns False. (null? Sandwich) gives no answer, because null? only works on lists.


This is not a built-in—it's code from LS:

(define atom?
    (lambda (x)
        (and (not (pair? x)) (not (null? x)))))


It works as expected. (eq 'foo foo) if True. Both the arguments of eq? must be non-numeric atoms.


lat? is a function in LS that returns true if a list contains only atoms. It demonstrates recursion.

(define lat?
    (lambda (l)
            ((null? l) #t)
            ((atom? (car l)) (lat? (cdr l)))
            (else #f))))

rember (building lists with cons)

The rember function takes two arguments—an atom and a list—and returns a list with the first instance of the specified atom removed.

(define rember
    (lambda (a l)
            ((null? l) (quote ()))
            ((eq? (car l) a) (cdr (l))
            (else (cons (car l)    ;Describes expected first element
                (rember a (cdr l))))))))    ;Recurse through list

So, it may not be obvious what's going on here. I don't totally understand it myself yet, but believe it has to do with evaluation rules: cons effectively "holds" until the value of its arguments are evaluated to their full depth (i.e.—through all the recursive calls to rember.

That's why rember works as it should rather than returning a truncated or otherwise mangled list. The values from all the recursive calls to rember basically queue-up for cons until they're all fully evaluated.

Here's another example of list building. The function firsts recurses through a list of lists, building a new list that contains only the first atoms in each of the original sublists.

(define firsts
    (lambda (l)
            ((null? l) quote())
            (else (cons (car (car l))    ;Describes expected first element
                (firsts (cdr l)))))))    ;Recurse through list

The thing of interest about these (apart from the recursion) is that the first argument to cons should describe the expected first element (LS call this The Third Commandment).


People who write Lisp tend to do so using Emacs. SLIME is an Emacs IDE for Common Lisp. To start SLIME in Emacs: ALT-x slime. To quit SLIME, type a comma at the REPL prompt, then quit on the Emacs command line.

I tried this. Looks like I'm still a vim guy.