Lispin - The Lisp Interpreter

Quick Start

Launch lisp.exe and write
(car '(a b c))
First line is what is understood by the interpreter and second line is result.
(file-exec "test.lsp")
(quicksort '(5 6 7 1 2 4 5 9))
Look inside the test.lsp file for some intersting function

Lisp Introduction

When we think about the best way to describe the Lisp there is 2 things that comes in mind :
- The annoying parenthesis
and
- The elegance
To be convinced, a simple example:
The min function which can be written as "(label min (lambda (x y) (cond ( (< x y) x ) ( t y ) ) ))"
For a neophyte it could be a problem to consider the evil parenthesis.
But on the other hand how to not be under the charm of a quicksort written in a bunch of lines.
And the concept is so simple that it is simply beautiful: all rely on a cell with 2 part.
The cell is a memory cell. It is defined as ( ).
The 2 parts are called car and cdr. The historical reason is that the first computer implementing lisp was formed with 2 registers: Address and Decrement. So the Content of the Address Register gave the first function C.A.R. and the Content of Decrement Register gave the second one C.D.R.
So a memory cell composed with 2 registers can be noted like that: ( car-part . cdr-part )
This language is based on simple linked list structure (the cdr-part is often used as a pointer).
A list of element is so a linked list of element.
For instance a simple list ( a b c ) is in fact ( a . ( b . ( c . nil ) ) )

Notation

a cell is defined as: ()
the cell has 2 part the car and the cdr defined as: ( car-part . cdr-part )
abreviation list are defined as: ( x y z ... )
( a . nil ) is the same as ( a )
( a . ( b . nil ) ) is the same as ( a b )
( a . ( b . c ) ) is the same as ( a b . c )
( a . ( b . ( c . nil ) ) is the same as ( a b c )
( a . ( ( b . ( c . nil ) ) ) is the same as ( a ( b c ) )
( a . ( ( b ) . ( c . nil ) ) ) is the same as ( a ( b ) c )
() is the same as nil
t is the same as true
The meaning for the code is the same as the one for the data.
A function call is defined as: ( func arg1 arg2 ... )
For script functions, the evaluator starts by evaluating arguments and then call the func symbol.
For native functions, each function has the choice to evaluate its arguments or not.
For instance, quote does not evalute its arguments.
(quote car (quote x y)) evaluates to ( car ( quote x y ) )
But ( car ( quote x y ) ) evaluates to x
"Evaluates to" is defined as: =>
A number evaluates to a number: 5 => 5
A string evaluates to a string: "a5" => "a5"
t and nil evaluates to t and nil. Moreover () => nil
asymb is a symbol and so evaluates to nil if not bound to anything. (Bind a symbol with label native function)
(label asymb 11)
asymb now evaluates to 11

Evaluation

The lisp interpreter evaluates a SExpr in the following way:
- if the SExpr is a cons cell
- - Evaluate the car
- - If it evaluates to a function
- - - Evaluates all arguments (the rest of the list)
- - - Pass all the arguments to the function : the interpreter binds all arguments with all parameters of the function.
- - - Evaluate the function body and return its result
- else the SExpr is not a cons cell
- - if it is a symbol
- - - look for its value and return it
- - else return the SExpr untouched

For example:
( (lambda (x y) (+ x y)) 5 6)
To evaluates this SExpr firstly we evaluates the car that is "(lambda (x y) (+ x y))".
The lamda native function put unevaluated arguments "(x y)" and  "(+ x y)" in a cons cell (parameters body)
This is a non-native function so we evaluates arguments 5 and 6 which are numbers and so evaluated to their respective value.
Now x is bound to 5 and y to 6 according to the parameters of the function.
Now we evaluates the body of the function, each occurence of x will be replaced by its value 5, the same is done for y and 6.

Each time a function is called, a new environment is created. This environment holds bindings between parameters and their values.
This permits to override the same parameter name with different values depending on the function call stack.

Because the lambda doesn't evaluates the body of the function, generating parametrized function on the fly is done by evaluating it.
For example:
(label createFunction (lambda (param) (lambda () (+ param 5))))
(createFunction 5) => <lambda params:nil body:( + param 5 )> ; This is not what we wants
((createFunction 5)) => nil ; because param is unknown
; a more correct way of doing this is:
(label createFunction (lambda ( param ) (eval ( + "(lambda () (+ " param " 5)" ))))
(createFunction 3) => <lambda params:nil body:( + 3 5 )>
((createFunction 3)) => 8

Supported instruction
• car
• cdr
• cons
• quote (or ')
• lambda
• label, set
• eval
• cond
• eq
• < >
• prog1, progn
• +,-,*,/
• and, or, not
• while
• math-floor
• file-exec
Not supported
• Backquote
• Variadic argument for non native function
• Closure not done (The lambda native function doesn't analyse the body part)

Some Example

*** car
-------
Brief: return the first sexpr of the list
Form : (car l)
Param: l is a list (if atom return nil). l is evaluated.
Ret  : the first sexpr of the list
Examples:
(car '(A B C))
=> A
(car '())
=> nil
(car ())
=> nil
(car t)
=> nil
(car 'xyz)
=> nil

*** cdr
-------
Brief: return the rest of the list without the first sexpr
Form : (cdr l)
Param: l is a list (if atom return nil). l is evaluated.
Ret  : the rest of the list without the first sexpr
Examples:
(cdr '(a . b))
=> b
(cdr '(a b c))
=> ( b c )
(cdr 'a)
=> nil
(cdr nil)
=> nil

*** cons
--------
Brief: return the cell with the car x and the cdr y
Form : (cons x y)
Param: x and y are sexpr. x and y are evaluated.
Ret  : the cell constructed with x and y (x being the car and y the cdr)
Examples:
(cons 'x 'y)
=> ( x . y )
(cons '(1 2) '(3 4))
=> ( ( 1 2 ) 3 4 )
(cons 'x (cons 'y ( cons 'z '() ) ) )
=> ( x y z )
(cons 'x nil)
=> ( x )
(cons nil 'x)
=> ( nil . x )

*** quote or '
--------------
Brief: return the parameters without evaluating it
Form : (quote x) or 'x
Param: x is a sexpr. x is not evaluated.
Ret  : x without evaluating it.
Examples:
'x
=> x
'(x y z)
=> (x y z)
(quote x y z)
=> (x y z)
'()
=> nil
't
=> t
'(car '(x y))
=> ( car ( quote x y ) )
(car '(x y))
=> x

*** lambda
----------
Brief: lambda is an anonymous function
Form : (lambda (x y ... ) body)
Param: x,y,... are the parameters of the function (a list of symbols) and body is a sexpr representing
the function. In the body, the parameters has the value passed to the function. When the body
is called, a new environment is defined (linked to the previous one). Parameters and body are not evaluated.
Ret  : a function (specific type)
Exmaples:
; lambda evaluates to a function:
(lambda (x y) (cons x (cdr y)))
=> <lambda params: x y  body: cons x ( cdr y ) >
; We can call this function, putting its parameters
( (lambda (x y) (cons x (cdr y))) 'z '(a b c))
=> (z b c)
; parameters can be functions
( (lambda (f) (f '(b c))) (lambda (x) (cons 'a x)) )
=> (a b c)
( (lambda (f) (f 'a)) (lambda (x) (cons x '(b c))) )
=> (a b c)
( (lambda () (cons 'a ())) ) ; no parameters
=> ( a )

*** label
---------
Brief: label binds an atom to a value in the current environment
Form : (label x y)
Param: x is the atom to bind and y the value. The atom x is not evaluated. The value y is evaluated.
Ret  : nil
Examples:
(label XXX 56.23)
=> nil
XXX
=> 56.23 ; XXX appear in the global environment
; label is local to a function because the function call is done in a new environment:
( (lambda (x y) (eval '(label ZZZ (cons x (cdr y))) '(car ZZZ))) 'RR '(AAA BB CC) )
=> RR
ZZZ
=> nil ; ZZZ does not appear in the global environment

*** set
-------
Brief: set act as label but look in all environments
Form : (set x y)
Param: x is the atom to bind and y the value. The atom x is not evaluated. The value y is evaluated.
Ret  : nil
Examples:
(label XXX 5)
=> nil
((lambda (x) (label XXX x)) 33)
=> nil
XXX
=> 5
; This is ok as label is local to a function
((lambda (x) (set XXX x)) 33)
=> nil
XXX
=> 33
; Set look into all environment and find the symbol to be replaced by the new value (if not found act as label)

*** eval
--------
Brief: evaluate all the s-expr or the strings following
From : (eval [s-expr1 or string1] [s-expr2 or string2] ...)
Param: are sexpressions or strings (arguments are evaluated before being evaluated (again))
Ret  : the value of the last evaluated sepression or string
Exmaples:
(eval '(car '(1 2 3)))
=> 1
(eval (cons 'cdr '('(1 2 3))))
=> ( 2 3 )
(eval "(cdr '(1 2 3))")
=> ( 2 3 )
(eval "(cons 'a '(b c))" '(car '(1 2 3)))
=> 1

*** cond
--------
Brief: cond test each condition and if not nil executes all s-expr following
Form : (cond ( t1 se11 se12 ... ) ( t2 se21 se22 ... ) ... )
Param: t1,t2,... are boolean values (t or ()) they are sexpr evaluated sequencially while they are false.
If one is true then the seXX are evaluated sequencially.
Ret  : return the value of the last sexpr (seXX ...) of the first true test (t1,t2...) or nil if no test true.
Exmaples:
(cond ( () (car '(1 2 3)) ) (t (cdr '(1 2 3)) )
=> ( 2 3 )
(cond ( t (car '(1 2 3)) (cdr '(A B C)) ) (t (cdr '(1 2 3)) )
=> ( B C )
; car '(1 2 3) has been evaluated but the last s-expression is cdr '(A B C)
; number evaluates to number that is not a nil value so:
(cond (0 (car '(1 2 3))) (t (car '(A B C))))
=> 1
(cond ('a (car '(1 2 3))) (t (car '(A B C))))
=> 1
; but :
(cond (a (car '(1 2 3))) (t (car '(A B C))))
=> A
; This is because a is a symbol bound to nothing and so evaluates to nil

*** eq
------
Brief: eq compare 2 sexpr, if they are equals output t else nil
Form : (eq x y)
Param: x,y are s-expression
Ret  : t if x is equal to y, () otherwise.
Examples:
(eq '1 '1)
=> t
(eq t t)
=> t
(eq t ())
=> nil
(eq () ())
=> t
(eq 'ABC 'ABC)
=> t
(eq '(A B C) '(A B C))
=> t
(eq '(A . B) '(A . B))
=> t
(eq 0 nil)
=> nil
(eq 1 t)
=> nil
(label func (lambda (x) (cons x '(b c)))
=> nil
(func 'a)
=> ( a b c )
(eq func func)
=> t
(eq func (lambda (x) (cons x '( b c ))))
=> t
(eq func (lambda (y) (cons y '( b c ))))
=> nil
; compare 2 functions:
(eq func (eval (car '(func func2 func3))))
=> t
; compare 2 symbols:
(eq 'func (car '(func func2 func3)))
=> t
; compare the function result:
(eq (func 'a) '(a b c))
=> t
(eq (func 'a) '(b c))
=> nil

Back to matthPage