CS 2360 Lecture 16: February 7
Building Languages
Brutally swiped from Kurt Eiselt.
A Little Digression On Property Lists
Since in this lecture I am going to be using Peter Norvig's code
which makes use of property lists I thought I'd explain them a little.
A property list is associated with every symbol in lisp. (This
is one of the "weirdages" of lisp symbols.) A property list is
a set of key-value pairs that the Lisp interpreter maintains
on each symbol. This is not the value of the symbol,
but is something that is associated with the name. You
can retrieve the value of property list key by using the function
GET:
>(get 'foobar 'frik)
8
>
Note: This gets the value of the property frik on the
symbol foobar. If you evalute foobar at the interpreter
you get the value of the symbol, which is different. To set a
property you use SETF and GET in combination:
>(setf (get 'foobar 'frik) 8)
This is set the property value that we retrieved before. Note that
properties are destructively modified! When you change the value of
a property, you affect its property list and the old value is gone.
The value of the property may be any lisp object and you may have
any number of properties associated with any symbol.
A couple of useful utility functions on property lists are REMPROP
and SYMBOL-PLIST which remove a property and get the list
of properties and values respectively. We'll continue our example
from above:
> (setf (get 'foobar 'frak) 'babe-ruth)
BABE-RUTH
> (symbol-plist 'foobar)
(FRAK BABE-RUTH FRIK 8)
> (remprop 'foobar 'frak)
(FRAK BABE-RUTH FRIK 8)
> (symbol-plist 'foobar)
(FRIK 8)
Another Little Digression On Parameters To Defun Or Lambda
If you want to take optional parameters in Lisp, you can use the
&OPTIONAL syntax when you do DEFUN or LAMBDA.
Thus the following has an optional argument of bar:
> (defun my-cons (foo &optional bar) (cons foo bar))
MY-CONS
> (my-cons 'two)
(TWO)
> (my-cons 'two 'three)
(TWO . THREE)
>
If you want to take any number of parameters, you can use &REST
which puts all the paramters following the &REST in a list
and binds them to the parameter supplied.
> (defun my-math (operator &REST args)
(apply operator args))
MY-MATH
> (my-math #'+ 1 2 3 5 6)
17
> (my-math #'- 1 2 3 5 6)
-15
Note: Apply takes a lexical closure and a list of arguments and calls
the function with the arguments, but not with the arguments in a
list. Thus, in our first example above we are calling the function
+ with the arguments 1 2 3 5 6 not with one argument
of ( 1 2 3 5 6).
Back to our regularly scheduled programming
One of the oft-mentioned advantages of LISP is its
extensibility---it's very easy to add new things to the
language, and it's also very easy to build whole new
languages on top of LISP. One language that has been built
on top of LISP is called "Scheme". Scheme is used primarily
as a teaching language, and is close enough to LISP to be
considered a dialect of LISP. In fact, it's the only dialect
of LISP in current widespread use besides Common LISP.
Scheme tries to offer a minimal set of very powerful features
that can be used to implement other features.
Here are some of the ways in which Scheme is simpler than
Common LISP:
- Fewer built-in functions and special forms.
- No special variables, only lexical variables. (i.e., no
dynamic scoping)
- No optional parameters.
- No special forms for looping---the programmer must use
recursion, and count on Scheme to implement it
efficiently.
- Scheme evaluates the function part of a function call in
exactly the same way as the arguments.
Huh? What was that last one? Function calls in Scheme and
LISP are different? Yes, exactly. Here's how:
In LISP, (f x) means 1) look up the function body bound to f,
2) evaluate x, and 3) apply the retrieved function body to
the value of x. LISP doesn't evaluate f.
In Scheme, (f x) means 1) evaluate f (and we hope that will
return a function body), 2) evaluate x, and 3) apply the
result of evaluating f to the result of evaluating x. This
is a more consistent approach to evaluating an expression
than in LISP. Any expression can be in the function position
(the first of the list), and it is evaluated just like any
other argument. It's a subtle but important difference.
Nota bene: This difference is the origin of the function FUNCALL
which you have all seen before. Since Lisp doesn't evaluate its
first argument you need a way to compute the value of a function
to call and then call it. In Scheme, you just put the computation
of the function to call in the first position in the parenthesis
and go for it! In Lisp, you need the placeholder FUNCALL.
The mini-Scheme interpreter
A simple interpreter for Scheme is pretty easy to construct
in LISP. Here's an example of an interpreter for a subset of
Scheme (taken from Peter Norvig's book):
(defun interp (x &optional env)
(cond
((symbolp x) (get-var x env))
((atom x) x)
((case (first x)
(QUOTE (second x))
(SET! (set-var! (second x) (interp (third x) env) env))
(LAMBDA (let ((parms (second x))
(code (maybe-add 'begin (rest (rest x)))))
#'(lambda (&rest args)
(interp code (extend-env parms args env)))))
(t ;; a procedure application
(apply (interp (first x) env)
(mapcar #'(lambda (v) (interp v env))
(rest x))))))))
(defun set-var! (var val env)
(if (assoc var env)
(setf (second (assoc var env)) val)
(set-global-var! var val))
val)
(defun get-var (var env)
(if (assoc var env)
(second (assoc var env))
(get-global-var var)))
(defun set-global-var! (var val)
(setf (get var 'global-val) val))
(defun get-global-var (var)
(let* ((default "unbound")
(val (get var 'global-val default)))
(if (eq val default)
(error "Unbound scheme variable: ~a" var)
val)))
(defun extend-env (vars vals env)
(nconc (mapcar #'list vars vals) env))
(defparameter *scheme-procs*
'(+ - * / = < > <= >= cons car cdr not append list read member
(null? null) (eq? eq) (equal? equal) (eqv? eql)
(write prin1) (display princ) (newline terpri)))
(defun init-scheme-interp ()
(mapc #'init-scheme-proc *scheme-procs*)
(set-global-var! t t)
(set-global-var! nil nil))
(defun init-scheme-proc (f)
(if (listp f)
(set-global-var! (first f) (symbol-function (second f)))
(set-global-var! f (symbol-function f))))
(defun maybe-add (op exps &optional if-nil)
(cond ((null exps) if-nil)
((length=1 exps) (first exps))
(t (cons op exps))))
(defun length=1 (x)
(and (consp x) (null (cdr x))))
(defun last1 (list)
(first (last list)))
(defun scheme ()
(init-scheme-interp)
(loop (format t "~&==> ")
(print (interp (read) nil))))
Let's go back and take a look at the basic evaluator
function, called "interp":
(defun interp (x &optional env)
(cond
((symbolp x) (get-var x env))
((atom x) x)
((case (first x)
(QUOTE (second x))
(SET! (set-var! (second x) (interp (third x) env) env))
(LAMBDA (let ((parms (second x))
(code (maybe-add 'begin (rest (rest x)))))
#'(lambda (&rest args)
(interp code (extend-env parms args env)))))
(t ;; a procedure application
(apply (interp (first x) env)
(mapcar #'(lambda (v) (interp v env))
(rest x))))))))
The interp function works on two arguments. The first is an
expression simply called "x", which is the expression to be
evaluated. The second is called "env" (for "environment")
which is merely an association list of variable names and
their bindings or values.
This Scheme interpreter is ready to deal with six different
cases. From top to bottom, they are:
- If the expression is a symbol, look up its value in the
environment.
- If the expression is an atom other than a symbol, such as
a number, just return it. Otherwise, the expression must
be a list.
- If the list starts with QUOTE, return the quoted
expression.
- If the list starts with SET! (same as the LISP setq),
interpret the value and then set the variable to that
value.
- If the list starts with LAMBDA (no need for #' here),
then build a new procedure---a closure over the current
environment.
- Otherwise, this must be a procedure application.
Interpret the procedure and all the arguments, and
apply the procedure value to the argument values.
Show me that factorial thing one more time
To get the mini-Scheme interpreter to work, load the file
containing the mini-Scheme code, and then call the function
named "scheme". The prompt will change from "?" to "==>":
Welcome to Macintosh Common Lisp Version 2.0!
?
SCHEME
? (scheme)
==>
Now you can interpret a subset of Scheme code. Some Scheme
code looks just like LISP code:
==> (+ 2 2)
4
==>
But not all Scheme code looks exactly like LISP code. Here's
how we define a new function in Scheme:
==> (set! square (lambda (x) (* x x)))
#
==>
Invoking a Scheme function is pretty much the same as
invoking a LISP function:
==> (square 2)
4
==>
We can extend the mini-Scheme interpreter easily. For
example, if we want to add a conditional like "if", we merely
add another chunk to the "case" expression in the
interpreter. This new chunk says that if the expression
being evaluated begins with IF, then evaluate the second part
of the expression by calling "interp" recursively on that.
If the value is non-nil, then call "interp" on the third part
of the expression, else call "interp" on the fourth part of
the expression. And in order to make that all happen, we
just use the LISP version of "if":
(defun interp (x &optional env)
(cond
((symbolp x) (get-var x env))
((atom x) x)
((case (first x)
(QUOTE (second x))
(SET! (set-var! (second x) (interp (third x) env) env))
(LAMBDA (let ((parms (second x))
(code (maybe-add 'begin (rest (rest x)))))
#'(lambda (&rest args)
(interp code (extend-env parms args env)))))
(IF (if (interp (second x) env) ;; <
(interp (third x) env) ;; < added stuff
(interp (fourth x) env))) ;; <
(t ;; a procedure application
(apply (interp (first x) env)
(mapcar #'(lambda (v) (interp v env))
(rest x))))))))
With that addition, we can define (what else?) the factorial
function:
==> (set! fact (lambda (x) (if (equal? x 0)
1
(* x (fact (- x 1))))))
#
==> (fact 5)
120
==>
The read-eval-print loop
One interesting side note that all you budding young LISP
hackers should be aware of is that the interactive capability
of LISP derives from something called the "read-eval-print
loop". The "read" function accepts and expression typed at
the terminal. The "eval" function is the LISP evaluator,
which evaluates the expression obtained by "read". And
"print" prints the result of the evaluation. If you nest
these three functions and stick them in the middle of a loop,
you'll get the interactivity that we've come to associate
with LISP. We can see exactly the same thing done explicitly
in our mini-Scheme interpreter, except that "eval", as noted
before, is called "interp" here:
(defun scheme ()
(init-scheme-interp)
(loop (format t "~&==> ")
(print (interp (read) nil))))
So, now that you know this, if you can build an evaluator, an
input function, and an output function, you too can create
your own interpreted programming language. This will be
handy to know if, say, you're stranded on a desert island
with a computer but no software. Well, ok, you'd need a
power source too. And maybe a big supply of Coke Classic and
a truckload of Doritos.
Back To The CS2360 Home Page
Ian Smith (iansmith@cc.gatech.edu)
Last Modified 27 Feb 95 by Ian Smith (iansmith@cc.gatech.edu)