Meta-
Circularity
Didier Verna
Introduction
S-expressions
7 Axioms
Functions
Some utilities
The Miracle
Labels
Scoping
Wrap-up
Meta-circularity
Self-interpreter (meta-interpreter):
written in the language it interprets
I
Bootstrapping problem
I
But not so surprising for a turing-complete language
Meta-circular evaluator: special case where the
language is restated in terms of itself (no additional
implementation required)
Homoiconicity (code is data):
Program representation in a primitive data structure
4/60
Meta-
Circularity
Didier Verna
Introduction
S-expressions
7 Axioms
Functions
Some utilities
The Miracle
Labels
Scoping
Wrap-up
The essence of an interpreter
Expression evaluation: evaluate the arguments, then
apply the operator’s value to their evaluation
Operator application: augment the environment with
the formal parameters, then evaluate the operator’s
value
5/60
Meta-
Circularity
Didier Verna
Introduction
S-expressions
7 Axioms
Functions
Some utilities
The Miracle
Labels
Scoping
Wrap-up
Lisp Nativity
MIT, Artificial Intelligence Laboratory, 1958
I
Project “Advice Taker”
I
John McCarthy’s founding paper: “Recursive Functions
of Symbolic Expressions and their Computation by
Machine”
I
IBM 704
Intentional simplifications
I
Apply and eval mixed up
I
Lisp dialect modernized
I
No error checking (and stuff)
7/60
Meta-
Circularity
Didier Verna
Introduction
S-expressions
7 Axioms
Functions
Some utilities
The Miracle
Labels
Scoping
Wrap-up
S-expressions (Sexp)
Sexp = Atom or list of expressions
Atom = sequence of letters
List = parenthesized, space-separated sequence of
expressions
Examples
foo
( )
( fo o )
( fo o bar )
( ( t h e ca t ) ( ea t s ( the mouse ) ) )
11/60
Meta-
Circularity
Didier Verna
Introduction
S-expressions
7 Axioms
Functions
Some utilities
The Miracle
Labels
Scoping
Wrap-up
Sexp values
Mathematical background (Cf. λ-calculus)
Pure functional programming
Atoms: self-evaluating or environmental
Non atomic sexp: (OP ARG1 ARG2 ...) where
I
OP is an operator
I
ARGx is an argument
7 primitive operators (axioms)
12/60
Meta-
Circularity
Didier Verna
Introduction
S-expressions
7 Axioms
Functions
Some utilities
The Miracle
Labels
Scoping
Wrap-up
Digression: argument evaluation
atom evaluates its argument (6= quote)
Examples
> ( atom ( atom ’ a ) )
t
> ( atom ’ ( atom ’ a ) )
n i l
quote is LISP-specific.
code ⇐⇒ data
Structural reflexivity
But note: DANGER, WILL ROBERTSON !!
16/60
Meta-
Circularity
Didier Verna
Introduction
S-expressions
7 Axioms
Functions
Some utilities
The Miracle
Labels
Scoping
Wrap-up
Operator #3: eq
Equality operator
Returns t if both arguments are the same atom
Returns nil otherwise
Examples
> ( eq ’ a ’ a )
t
> ( eq ’ a ’ b )
n i l
> ( eq n i l ( ) )
t
> ( eq ’ ( a b c ) ’ ( a b c ) )
n i l
17/60
Meta-
Circularity
Didier Verna
Introduction
S-expressions
7 Axioms
Functions
Some utilities
The Miracle
Labels
Scoping
Wrap-up
Operators #4 and #5: car and cdr
car returns the first element of a list
cdr returns the rest of a list
Examples
> ( ca r ’ ( a b c ) )
a
> ( cd r ’ ( a b c ) )
( b c )
> ( ca r ( ) )
n i l
> ( cd r n i l )
n i l
18/60
Meta-
Circularity
Didier Verna
Introduction
S-expressions
7 Axioms
Functions
Some utilities
The Miracle
Labels
Scoping
Wrap-up
The truth about car, cdr and lists
IBM 704’s hardware architecture
car: Contents of Address Register
cdr: Contents of Decrement Register
A list only has a car and a cdr
The car and the cdr are separated by a dot
(car . cdr)
The space notation is just syntactic sugar
19/60
Meta-
Circularity
Didier Verna
Introduction
S-expressions
7 Axioms
Functions
Some utilities
The Miracle
Labels
Scoping
Wrap-up
Some examples
a nil
(a) <=> (a . nil)
nil nil
(nil . nil)
()
a b c
a
nilb
c nil
a b nil
(a b) <=> (a . (b)) <=> (a . (b . nil))
(a b . c) <=> (a . (b . c))
(a (b) c) <=> (a . ((b) c)) <=> (a . ((b) . (c)))
<=> (a . ((b . nil) . (c . nil)))
20/60
Meta-
Circularity
Didier Verna
Introduction
S-expressions
7 Axioms
Functions
Some utilities
The Miracle
Labels
Scoping
Wrap-up
Operator #6: cons
Canonical list operator
Constructs a list by car and cdr
Examples
> ( cons ’ a ’ ( b c ) )
( a b c )
> ( cons ’ a (cons ’ b ( cons ’ c ( ) ) ) )
( a b c )
> ( ca r ( cons ’ a ’ ( b c ) ) )
a
> ( cd r ( cons ’ a ’ ( b c ) ) )
( b c )
21/60
Meta-
Circularity
Didier Verna
Introduction
S-expressions
7 Axioms
Functions
Some utilities
The Miracle
Labels
Scoping
Wrap-up
Operator #7: cond
Conditional branching
Multiple test/body clauses
Examples
> ( cond ( ( eq ’ a ’ b ) ’ f i r s t )
( ( atom ’ a ) ’ second ) )
second
> ( cond ( ( eq ’ a ’ b ) ’ f i r s t )
( ( eq ’ c ’ d ) ’ second )
( t ’ d e f a u l t ) )
d e f a u l t
22/60
Meta-
Circularity
Didier Verna
Introduction
S-expressions
7 Axioms
Functions
Some utilities
The Miracle
Labels
Scoping
Wrap-up
Functional denotation
The mathematical term “function” is ambiguous:
Both forms x + y
2
and f (x, y) are called “functions”
But x + y
2
(3, 4) = 13 or 19?
Church’s λ notation (1941):
λ ((x
1
, . . . , x
n
), ε)
λ ((x, y), x + y
2
)(3, 4) = 19
25/60
Meta-
Circularity
Didier Verna
Introduction
S-expressions
7 Axioms
Functions
Some utilities
The Miracle
Labels
Scoping
Wrap-up
Application to LISP
LISP functions:
I
(lambda (p
1
...p
n
) e)
I
p
i
are atoms (parameters)
I
e is an sexp
LISP function call:
I
((lambda (p
1
...p
n
) e) a
1
...a
n
)
I
a
i
are evaluated
I
e is evaluated with every p
i
substituted with a
i
’s value
Note: The value of a
i
may very well be a function. . .
26/60
Meta-
Circularity
Didier Verna
Introduction
S-expressions
7 Axioms
Functions
Some utilities
The Miracle
Labels
Scoping
Wrap-up
Examples
> ( ( lambda ( x ) ( cons x ’ ( b c ) ) )
’ a )
( a b c )
> ( ( lambda ( x y ) ( cons x ( cdr y ) ) )
’ z ’ ( b c ) )
( z c )
> ( ( lambda ( f ) ( f ’ ( b c ) ) )
’ ( lambda ( x ) ( cons ’ a x ) ) )
>> ( ( lambda ( x ) ( cons ’ a x ) )
’ ( b c ) )
( a b c )
27/60
Meta-
Circularity
Didier Verna
Introduction
S-expressions
7 Axioms
Functions
Some utilities
The Miracle
Labels
Scoping
Wrap-up
Recursive functions
The lambda notation is inadequate (Rochester):
fact = (lambda (n) (
*
n (fact??? (-1 n))))
New denotation:
I
(label f (lambda (p
1
...p
n
) e))
I
(defun f (p
1
...p
n
) e)
I
Same behavior as a lambda-expression, but every
occurrence of f evaluates to the lambda-expression
itself.
Example
( defun f a c t ( n ) (∗ n ( f a c t (−1 n ) ) ) )
28/60
Meta-
Circularity
Didier Verna
Introduction
S-expressions
7 Axioms
Functions
Some utilities
The Miracle
Labels
Scoping
Wrap-up
Convenience shortcuts
(cadr e): (car (cdr e))
(cdar e): (cdr (car e))
(c[ad]+r e): . . .
(list e
1
. . . e
n
): (cons e
1
...(cons e
n
()))
Examples
> ( cadr ’ ( ( a b ) ( c d ) e ) )
( c d )
> ( cdar ’ ( ( a b ) ( c d ) e ) )
( b )
> ( l i s t ’ a ’ b ’ c )
( a b c )
30/60
Meta-
Circularity
Didier Verna
Introduction
S-expressions
7 Axioms
Functions
Some utilities
The Miracle
Labels
Scoping
Wrap-up
Logical operators
null:
( defun n ul l ( x )
( eq x n i l ) )
not:
( defun not ( x )
( cond ( x n i l )
( t t ) ) )
and:
( defun and ( x y )
( cond ( x ( cond ( y t )
( t n i l ) ) )
( t n i l ) ) )
31/60
Meta-
Circularity
Didier Verna
Introduction
S-expressions
7 Axioms
Functions
Some utilities
The Miracle
Labels
Scoping
Wrap-up
append
( defun append ( x y )
( cond ( ( n ul l x ) y )
( t ( cons ( car x ) ( append ( cd r x ) y ) ) ) ) )
Examples
> ( append ’ ( a b ) ’ ( c d ) )
( a b c d )
> ( append n i l ’ ( a b ) )
( a b )
> ( append ’ ( n i l ) ’ ( a b ) )
( n i l a b )
32/60
Meta-
Circularity
Didier Verna
Introduction
S-expressions
7 Axioms
Functions
Some utilities
The Miracle
Labels
Scoping
Wrap-up
pair
Create an “association list” (alist) from two lists
( defun p a i r ( x y )
( cond ( ( and ( nu ll x ) ( nu l l y ) )
n i l )
( ( and ( not ( atom x ) ) ( not ( atom y ) ) )
( cons ( l i s t ( ca r x ) ( car y ) )
( p a i r ( cdr x ) ( cd r y ) ) ) ) ) )
Examples
> ( p a i r ’ ( a b c ) ’ ( d e f ) )
( ( a d ) ( b e ) ( c f ) )
33/60
Meta-
Circularity
Didier Verna
Introduction
S-expressions
7 Axioms
Functions
Some utilities
The Miracle
Labels
Scoping
Wrap-up
assoc
Return the cadr of the first matching alist entry
( defun assoc ( x y )
( cond ( ( eq x ( caar y ) ) ( cada r y ) )
( t ( assoc x ( cdr y ) ) ) ) )
Examples
> ( assoc ’ x ’ ( ( x a ) ( y b ) ) )
a
> ( assoc ’ x ’ ( ( x one ) ( x two ) ( y b ) ( x t h r e e ) ) )
one
34/60
Meta-
Circularity
Didier Verna
Introduction
S-expressions
7 Axioms
Functions
Some utilities
The Miracle
Labels
Scoping
Wrap-up
LISP can be written in itself
Stephen B. Russell and Daniel J. Edwards
Here it is. . .
( defun e v a l ( exp env )
( cond
( ( atom exp ) ( assoc exp env ) )
( ( atom ( ca r exp ) )
( cond ( ( eq ’ quo te ( ca r exp ) ) ( cadr exp ) )
( ( eq ’ atom ( car exp ) ) ( atom ( eval ( cadr exp ) env ) ) )
( ( eq ’ eq ( ca r exp ) )
( eq ( eval ( cadr exp ) env ) ( eval ( ca ddr exp ) env ) ) )
( ( eq ’ car ( ca r exp ) ) ( ca r ( ev a l ( cadr exp ) env ) ) )
( ( eq ’ cdr ( ca r exp ) ) ( cd r ( ev a l ( cadr exp ) env ) ) )
( ( eq ’ cons ( car exp ) )
( cons ( eval ( cadr exp ) env ) ( eval ( ca ddr exp ) env ) ) )
( ( eq ’ cond ( car exp ) ) ( condeval ( cdr exp ) env ) )
( t ( eval ( cons ( assoc ( ca r exp ) env ) ( cd r exp ) ) env ) ) ) )
( ( eq ( caar exp ) ’ l a b e l )
( eval ( cons ( caddar exp ) ( cd r exp ) )
( cons ( l i s t ( cadar exp ) ( ca r exp ) ) env ) ) )
( ( eq ( caar exp ) ’ lambda )
( eval ( caddar exp )
( append ( p a i r ( cadar exp ) ( l i s t e v a l ( cdr exp ) env ) ) env ) ) ) ) )
36/60
Meta-
Circularity
Didier Verna
Introduction
S-expressions
7 Axioms
Functions
Some utilities
The Miracle
Labels
Scoping
Wrap-up
Explanations
eval takes two arguments:
I
exp is an sexp to evaluate
I
env is the evaluation environment
(alist of atoms and their corresponding values)
eval has 4 evaluation clauses:
I
atoms
I
lists (beginning with an atom)
I
label expressions
I
lambda expressions
37/60
Meta-
Circularity
Didier Verna
Introduction
S-expressions
7 Axioms
Functions
Some utilities
The Miracle
Labels
Scoping
Wrap-up
Clause #1: atom
Seek out its value in the environment
( ( atom exp ) ( assoc exp env ) )
Example
> ( eval ’ x ’ ( ( a b ) ( x v a l ) ) )
>> ( assoc ’ x ’ ( ( a b ) ( x v a l ) ) )
v a l
38/60
Meta-
Circularity
Didier Verna
Introduction
S-expressions
7 Axioms
Functions
Some utilities
The Miracle
Labels
Scoping
Wrap-up
Clause #2: (op ...) (1/2)
op is a primitive operator: call the operator on the
evaluation of its arguments
( ( eq ’ cons ( car exp ) )
( cons ( eval ( cadr exp ) env )
( eval ( caddr exp ) env ) ) )
Example
> ( eval ’ ( cons x ’ ( b c ) ) ’ ( ( x a ) ) )
>> ( cons ( eval x ’ ( ( x a ) ) )
( eval ( quote ( b c ) ) ’ ( ( x a ) ) ) )
( a b c )
39/60
Meta-
Circularity
Didier Verna
Introduction
S-expressions
7 Axioms
Functions
Some utilities
The Miracle
Labels
Scoping
Wrap-up
Exceptions
quote does not evaluate its argument:
( ( eq ’ quot e ( ca r exp ) )
( cadr exp ) )
cond is also treated in a special way (lazy):
( ( eq ’ cond ( car exp ) )
( co n d e val ( cd r exp ) env ) )
condeval
( defun c o n deval ( conds env )
( cond ( ( ev a l ( caar conds ) env )
( eval ( cadar conds ) env ) )
( t
( co n d e val ( cd r conds ) env ) ) ) )
40/60
Meta-
Circularity
Didier Verna
Introduction
S-expressions
7 Axioms
Functions
Some utilities
The Miracle
Labels
Scoping
Wrap-up
Clause #2: (op ...) (2/2)
op is an atom: replace it by its value (must be a label or
lambda) and evaluate the call
( t ( eval ( cons ( assoc ( ca r exp ) env )
( cd r exp ) )
env ) )
Examples
> ( eval ’ ( f ’ ( b c ) ) ’ ( ( f ( lambda ( x ) ( cons ’ a x ) ) ) ) )
>> ( eval ( ( lambda ( x ) ( cons ’ a x ) ) ’ ( b c ) ) ’ ( ( f ( lambda ( x ) ( cons ’ a x ) ) ) ) )
( a b c )
41/60
Meta-
Circularity
Didier Verna
Introduction
S-expressions
7 Axioms
Functions
Some utilities
The Miracle
Labels
Scoping
Wrap-up
Clause #3: labels
((label f (lambda (p
1
...p
n
) e)) a
1
...a
n
)
Add the lambda-expression in the environment, and
evaluate it
( ( eq ( caar exp ) ’ l a b e l )
( eval ( cons ( caddar exp ) ( cd r exp ) )
( cons ( l i s t ( cadar exp ) ( ca r exp ) ) env ) ) )
> (eval ((label f (lambda (p
1
...p
n
) e)) a
1
...a
n
)
env)
>> (eval ((lambda (p
1
...p
n
) e) a
1
...a
n
)
((f (label f (lambda (p
1
...p
n
) e))) env))
42/60
Meta-
Circularity
Didier Verna
Introduction
S-expressions
7 Axioms
Functions
Some utilities
The Miracle
Labels
Scoping
Wrap-up
Clause #4: lambdas
((lambda (p
1
...p
n
) e) a
1
...a
n
)
Evaluate e with associations (p
i
(eval a
i
)) added to the
environment
( ( eq ( caar exp ) ’ lambda )
( eval ( caddar exp )
( append ( p a i r ( cadar exp )
( l i s t e v a l ( cdr exp ) env ) ) env ) ) )
> (eval ((lambda (p
1
...p
n
) e) a
1
...a
n
) env)
>> (eval e ((p
1
a
1
) ...(p
n
a
n
) env))
43/60
Meta-
Circularity
Didier Verna
Introduction
S-expressions
7 Axioms
Functions
Some utilities
The Miracle
Labels
Scoping
Wrap-up
listeval
Returns the list of all arguments evaluated in the
environment
(a
1
. . . a
n
) =⇒ (a
1
. . . a
n
)
( defun l i s t e v a l ( args env )
( cond ( ( n ul l a r g s ) n i l )
( t ( cons ( ev a l ( car args ) env )
( l i s t e v a l ( cdr a r g s ) env ) ) ) ) )
44/60
Meta-
Circularity
Didier Verna
Introduction
S-expressions
7 Axioms
Functions
Some utilities
The Miracle
Labels
Scoping
Wrap-up
It’s even simpler than that (but less readable)
eval only requires the 7 primitive operators
But don’t forget to add exp and env to the environment!
Example
( assoc ( ca r exp ) env )
( eval ’ ( ( l a b e l assoc ( lambda ( x y )
( cond ( ( eq ( ca r ( ca r y ) ) x )
( ca r ( cd r ( car y ) ) ) )
( t ( assoc x ( cdr y ) ) ) ) ) )
( ca r exp ) env )
( cons ( cons ’ exp ( cons exp ( ) ) )
( cons ( cons ’ env ( cons env ( ) ) ) env ) ) )
45/60
Meta-
Circularity
Didier Verna
Introduction
S-expressions
7 Axioms
Functions
Some utilities
The Miracle
Labels
Scoping
Wrap-up
The label notation is unnecessary
Anonymous recursion possible
Idea: pass the (anonymous) recursive function as a
parameter!
Let’s switch to Scheme syntax. . .
Factorial function
( define f a c t
( lambda ( n )
( i f ( zer o? n )
1
(∗ n ( f a c t (− n 1 ) ) ) ) ) )
47/60
Meta-
Circularity
Didier Verna
Introduction
S-expressions
7 Axioms
Functions
Some utilities
The Miracle
Labels
Scoping
Wrap-up
Passing the procedure as a parameter. . .
fact-maker, take 1
( define fact−maker
( lambda ( procedure )
( lambda ( n )
( i f ( zero? n )
1
(∗ n ( procedure (− n 1 ) ) ) ) ) ) )
Hoping for: ((fact-maker fact-maker) 5). . .
to work. NOT!
48/60
Meta-
Circularity
Didier Verna
Introduction
S-expressions
7 Axioms
Functions
Some utilities
The Miracle
Labels
Scoping
Wrap-up
Let’s try again. . .
fact-maker, take 2
( define fact−maker
( lambda ( procedure )
( lambda ( n )
( i f ( zero? n )
1
(∗ n ( ( procedure p r o c e d u r e ) (− n 1 ) ) ) ) ) ) )
((fact-maker fact-maker) 5) => 120
It works! But we still have a name. . .
49/60
Meta-
Circularity
Didier Verna
Introduction
S-expressions
7 Axioms
Functions
Some utilities
The Miracle
Labels
Scoping
Wrap-up
Using the lambda on itself directly. . .
That’s it at last
( ( ( lambda ( procedure )
( lambda ( n )
( i f ( zero? n )
1
(∗ n ( ( procedure p r o c e d u r e ) (− n 1 ) ) ) ) ) )
( lambda ( procedure )
( lambda ( n )
( i f ( zero? n )
1
(∗ n ( ( procedure p r o c e d u r e ) (− n 1 ) ) ) ) ) ) )
5)
But can we generalize to any function?
50/60
Meta-
Circularity
Didier Verna
Introduction
S-expressions
7 Axioms
Functions
Some utilities
The Miracle
Labels
Scoping
Wrap-up
Abstracting procedure away (1/3)
(procedure procedure) is boring
( lambda ( n )
( i f ( zer o ? n )
1
(∗ n ( ( procedure p r o c e d u r e ) (− n 1 ) ) ) ) )
A nice little trick
f <=> ( lambda ( x ) ( f x )
( f a r g ) <=> ( ( lambda ( x ) ( f x ) ) a rg )
51/60
Meta-
Circularity
Didier Verna
Introduction
S-expressions
7 Axioms
Functions
Some utilities
The Miracle
Labels
Scoping
Wrap-up
Abstracting procedure away (2/3)
Let’s plug the trick in
( lambda ( n )
( i f ( zer o ? n )
1
(∗ n ( ( lambda ( arg ) ( ( procedure procedure ) arg ) ) (− n 1 ) ) ) ) ) )
And parametrize the function
( ( lambda ( fu nc )
( lambda ( n )
( i f ( zero? n )
1
(∗ n ( fu nc (− n 1 ) ) ) ) ) )
( lambda ( arg ) ( ( procedure proc e d u r e ) arg ) ) ) )
52/60
Meta-
Circularity
Didier Verna
Introduction
S-expressions
7 Axioms
Functions
Some utilities
The Miracle
Labels
Scoping
Wrap-up
Abstracting procedure away (3/3)
Let’s plug the new form in
( ( ( lambda ( procedure )
( ( lambda ( fu nc )
( lambda ( n )
( i f ( zer o ? n )
1
(∗ n ( fu nc (− n 1 ) ) ) ) ) )
( lambda ( arg ) ( ( procedure proc e d u r e ) arg ) ) ) )
( lambda ( procedure )
( ( lambda ( fu nc )
( lambda ( n )
( i f ( zero? n )
1
(∗ n ( fu nc (− n 1 ) ) ) ) ) )
( lambda ( arg ) ( ( procedure proc e d u r e ) arg ) ) ) ) )
5)
53/60
Meta-
Circularity
Didier Verna
Introduction
S-expressions
7 Axioms
Functions
Some utilities
The Miracle
Labels
Scoping
Wrap-up
Where is fact now ?
Fact is here:
( define d of ac t
( lambda ( fu nc )
( lambda ( n )
( i f ( zero? n )
1
(∗ n ( fu nc (− n 1 ) ) ) ) ) ) )
And we can just plug it in:
( define f a c t
( ( lambda ( procedure )
( do fa c t ( lambda ( ar g ) ( ( p rocedure procedure ) arg ) ) ) )
( lambda ( procedure )
( do fa c t ( lambda ( ar g ) ( ( p rocedure procedure ) arg ) ) ) ) ) )
54/60
Meta-
Circularity
Didier Verna
Introduction
S-expressions
7 Axioms
Functions
Some utilities
The Miracle
Labels
Scoping
Wrap-up
Bingo!
The famous Y combinator:
( define Y
( lambda ( X )
( ( lambda ( procedure )
(X ( lambda ( arg ) ( ( procedure procedure ) a r g ) ) ) )
( lambda ( procedure )
(X ( lambda ( arg ) ( ( procedure procedure ) a r g ) ) ) ) ) ) )
And the final factorial:
( define f a c t ( Y d o f a ct ) )
Reminder: dofact was not so difficult to get
( define d of ac t
( lambda ( fu nc )
( lambda ( n )
( i f ( zero? n )
1
(∗ n ( fu nc (− n 1 ) ) ) ) ) ) )
55/60
Meta-
Circularity
Didier Verna
Introduction
S-expressions
7 Axioms
Functions
Some utilities
The Miracle
Labels
Scoping
Wrap-up
Dynamic Scoping
What’s the real name of this function?
( defun my s ter i ous ( func l s t )
( l e t ( e l t n )
( wh i l e ( se t q e l t ( pop l s t ) )
( push ( fu n c a l l f unc e l t ) n ) )
( nreverse n ) ) )
( defun i n c r e m e n t − l i s t ( n l s t )
( my s ter i ous ( lambda ( e l t ) ( + e l t n ) )
l s t ) )
Very first example of higher-order function
In McCarthy’s original paper (1958)
Doesn’t work ;-)
57/60
Meta-
Circularity
Didier Verna
Introduction
S-expressions
7 Axioms
Functions
Some utilities
The Miracle
Labels
Scoping
Wrap-up
What Lisp brought to the picture
From the λ-calculus
I
Homoiconicity
I
Meta-circularity
I
Structural reflexivity
I
Functional paradigm
I
Expressions
I
Recursion
I
Dynamic typing
And also (less relevant)
I
Conditional branches
I
Garbage collection
59/60
