Transcript Logic

Lisp, Then and Now
History


John McCarthy invented
Lisp in 1958 as both a
programming language and
as a formalism for doing
recursive function theory
The first two
implementations were
written by a graduate
student, Steve “Slug”
Russell


McCarthy is famous for
inventing Lisp
Russell is famous for
inventing Spacewar!, the
first widely-known video
game
2
Why is Lisp important? I

Lisp is a language that “got it right the first time”



Lisp is homoiconic—there is no distinction between the way
data is represented, and the way programs are represented



Consequently, there have been no changes to the core language in over
50 years!
Later variants—Common Lisp, Scheme, Racket, Clojure—have been
additions and minor name changes
Programs are data, and data are programs
Lisp is superb for metaprogramming—programs that write programs (or
even rewrite themselves)
Lisp is functional—functions are just another kind of data, to
be stored, passed around, and manipulated

Functional programming is much better for concurrent and distributed
programs
3
Why is Lisp important? II

Lisp is an instantiation of the lambda calculus


Lisp is a kind of math implemented as a programming
language, just as Prolog is a kind of logic implemented as a
programming language
You don’t need to understand lambda calculus to use Lisp


But knowing Lisp really helps you understand lambda calculus!
Other languages get compiled into an Abstract Syntax
Tree (AST), but Lisp’s syntax is the AST

What you see is what you get!
4
Lisp syntax




An S-expression (symbolic expression) is an atom or a
list
An atom is a variable or a number
A list is zero or more S-expressions enclosed in
parentheses
… and that’s it!
5
Lisp semantics


Lisp has functions and special forms, with the syntax
(function-or-form arg1 arg2 … argN)
For a function: The arguments are evaluated and their values
passed to the function


There are a large number of predefined functions
For a form: The arguments are passed unevaluated to the form


The form decides when/whether to evaluate them
There are a large number of predefined forms




defn defines a new function
if and cond select among alternatives
quote returns its argument unevaluated (i.e. it is treated as data)
The names of forms and functions vary somewhat between
different versions of Lisp (head, front, first, car), but the
behavior changes very little
6
Lisp example


A non-empty list has a head (first element) and a tail
(the remainder of the list)
Here’s how to find the last value in a list:
(defun last (list)
(if (empty (tail list))
(head list)
(last (tail list)) ) )
7
The End
“We were after the C++ programmers.
We managed to drag a lot of them
about halfway to Lisp.”
--Guy Steele, co-author of the Java spec
8