John McCarthy and LISP
by Lewis Berman
John McCarthy joined the ranks of giants such as Steve Jobs and Dennis Ritchie who passed away during October 2011. John McCarthy created the LISP programming language way back in 1958 at MIT. LISP was (and is) the vehicle for much work in artificial intelligence, and it was the predecessor of F#, Scala, and other functional programming languages gaining popularity today.
McCarthy's research and mentorship career spanned six decades, from the late 1950's through the mid 2000's. He became a professor at Stanford University in 1962, where he stayed until his formal retirement in 2000. Reasoning (in humans and machines) was an ongoing topic of his research. He defined the frame problem in 1969 and advanced non-monotonic reasoning in support of a possible solution. He founded the Formal Reasoning Group at Stanford, which is working today on self-aware systems. He commented publicly on social issues, some long-term in nature such as the sustainability of human progress. Many, many programmers today will recognize McCarthy's lasting contribution to programming languages: garbage collection, in which previously allocated but currently unused memory is automatically reclaimed. LISP was the first language to employ garbage collection.
A simple LISP expression looks like this:
(+ 9 7)
which returns 16. That's the basic syntax of a LISP expression: symbols enclosed in parentheses. In this case, we have a symbol representing a function (here a mathematical operator) followed by its arguments (here numeric). The arguments might themselves be LISP expressions:
(+ (+ 9 7) (* 5 3))
which returns 31. Variables can contain the numeric values:
(define x 9)
(define y (* 5 3))
(define result (+ (+ x 7) y))
The variable result now contains the value 31.
We are not restricted to numerical calculations. We have symbols and lists, the primary data structures in LISP. Here we assign a symbol to the variable m, then we construct a list of symbols using the function cons, extending the list (bb cc dd):
(define m 'aaa)
(cons m '(bbb ccc ddd))
This returns a list whose value is (aaa bbb ccc ddd). The head of a list is a symbol, which we can extract using the function car, so named for obscure historical reasons:
(car '(aaa bbb ccc ddd))
returns aaa. The function cdr, so named for the same obscure historical reasons, returns the rest of the list:
(cdr '(aaa bbb ccc ddd))
returns (bbb ccc ddd).
What does the following expression return?
(+ (car '(9 7 3 1 2)) (car (cdr '(1 2 3 4 5)))))
Answer: 11. It added 9 (the head of the first list) and 2 (the head of the tail of the second list).
Suppose we define a vehicle as a list containing the vehicle's name, manufacturer, and type. For example,
'(dakota dodge truck)
All the vehicles appear in a list provided by some source of data:
'((dakota dodge truck) (300M chrysler car) (volt chevrolet car) ... )
Suppose the entire list is assigned to the variable the-list. We can get the first vehicle's type:
(car (cdr (cdr (car the-list))))
(I can't resist: this particular LISP car actually returns truck.)
We could iteratively (or recursively) loop through the outer list, get the manufacturer or type of each vehicle, and perform some processing related to it. Also, we could embed a lot of knowledge for each vehicle, for example a set of characteristics, in no particular order, with a description for each subassembly:
(dakota dodge truck 4wd (engine piston (part-no 18774)) (colors standard-color-set) ...
Note that standard-color-set is itself a list (not shown) of color names and codes.
List processing is the basis for knowledge representation systems. LISP is in use today, in production, at institutions such as the Space Telescope Science Institute here in Maryland. Mark Giuliano, whose team at the Institute uses LISP to implement scheduling algorithms for the Hubble space telescope, points out an advantage of its syntax:
"The LISP syntax, based on balanced lists delimited by parentheses, is well defined and regular, and it makes explicit the equivalence of program and data." A symbol can represent numeric data, string data, symbolic data, or a function. A symbol might be used as data on minute and a function or set of functions the next. The equivalence of program and data can be leveraged to write self-modifying programs.
Giuliano lists other advantages:
"LISP has a powerful macro system that lets you the programmer extend the progamming language with structures that match the desired program domain.
"LISP is an interactive language that allows you to build, test, and run programs in an interactive and incremental fashion.
"LISP provides automatic garbage collection."
Part of the power of LISP is that functions are first-class citizens. For example, the following includes a nameless function via the lambda binding:
(lambda (x) (+ 1 x) 41)
Try to write nameless functions in Java! This feature supports AI systems, as they can learn by learning new functions.
There are different dialects of LISP. The examples in this article were written in MIT/GNU Scheme. It can be freely downloaded from the site listed below. The Space Telescope Science Institute employs ANSI Common LISP. As a musician, my personal favorite was Franz Lisp, Opus 38.
1. McCarthy, John. The Implementation of LISP. http://www-formal.stanford.edu/jmc/history/lisp/node3.html.
2. MIT/GNU Scheme language: http://www.gnu.org/s/mit-scheme/
3. Sitaram, Dorai. Teach Yourself Scheme in Fixnum Days. http://www.ccs.neu.edu/home/dorai/t-y-scheme/t-y-scheme.html.
4. Graham, Paul. Revenge of the Nerds. http://www.paulgraham.com/icad.html.
5. Land of Lisp - the Music Video!