I am trying to get my hands on this book, does any one know some one
or place that has it for sale?
Lisp: A Portable Implementation/Book and Disk
Sharam Hekmatpour
Prentice Hall/ 1989-07/ 0135374901
Has any one read it is it any good?
Steve
On Feb 10, 1:21 am, "Steve" <···········@gmail.com> wrote:
> Lisp: A Portable Implementation/Book and Disk
> Sharam Hekmatpour
>
> Prentice Hall/ 1989-07/ 0135374901
>
> Has any one read it is it any good?
Fortunately I was able to obtain a copy of this book from a second-
hand bookstore.
It describes an implementation of a Lisp dialect in around 5000 lines
of C. According to the preface, the intended audience is made up of
those wishing to learn about implementing Lisp-like languages, and
those interested in a symbol manipulation language on which portable
software systems can be written.
The implementation is explained step by step, with first a clear
description of the functionality followed by the relevant fragment of
source code. The full source code is provided on a 5.25" floppy.
Hekmatpour manages to include a broad range of features; let me try to
summarize it to give an impression.
Chapter 1 introduces the Lisp read-eval-print loop and supported data
types: integer, real, string, symbol, channel (like stream), list,
set, vector.
Then the four different function types in this dialect are explained.
Besides the counterparts to defun, you can define a "variable lambda"
which takes a variable number of arguments. The book gives function
'mean as example:
(fun mean vlam (n)
(prog [(sum 0) (count 0)]
(and (= n 0) (return 0)) ;; no numbers
loop
(and (>= count n) (return (/ sum count)))
(setq count (++ count) ;; increment count
sum (+ sum (arg count))) ;; add next number
(go loop)))
So 'n is bound to the number of supplied arguments, and with (arg <i>)
you get the i'th argument. Now 'fun is a macro, and the above expands
into:
(def mean
(vlam (n) (prog ...)))
with 'vlam defining an anonymous function of type 'vlambda.
As example of "unevaluated lambda", the third function type, an incf-
like macro is given:
(fun increment ulam (vars)
(prog [last]
loop
(cond [(null? vars) (return last)])
(setq last (set (car vars) ;; increment variable
(++ (eval (cars vars)))))
(setq vars (cdr vars))
(go loop)))
with this interaction:
=> (setq x 10 y 20)
20
=> (increment x y)
21
=> x
11
=> y
21
The fourth kind of function is a "macro lambda", with 'if as example:
(if <condition> <expression> else <expression>)
(fun if mlam (expr)
`(cond [,(car expr) ,(cadr expr)]
[ t ,(cadddr expr)]))
Chapter 2 explains how symbols are implemented as structures, kept in
a hashtable, with functions like lookup and intern. Symbols have
fields for a binding and a property list, and a symbol can be flagged
as a constant.
Atoms are represented by a C struct where the first member denotes the
type, and the second member is of union type. The mark-and-sweep
garbage collector is explained. Like everything, it is written in
compact and clear C.
Chapter 3 might be the most interesting chapter, as it explains
evaluation. There are stacks for function arguments, (lexical)
variables and expressions. The evaluation rules for the different
kinds of functions are described along with the code.
Chapter 4 describes the reader, which supports backquote: `(a @b ,c)
and even read-time evaluation; and the pretty printer that optionally
prints escape characters for strings and symbols.
In chapter 5 arithmetic, string operations like strcmp and strcat, and
symbol operations like gensym, boundp and symbol-value are
implemented.
Chapter 6 is about lists and sets, with familiar names like car, c{a,d}
+r like cdadr, rplacd, destructive and non-destructive versions of
subst, remove and reverse, and different equality predicates. Sets are
a separate data type represented the same as list, with functions like
union and subsetp defined on it.
Chapter 7 describes conditionals like cond and not, and higher level
functions like 'exist:
(exist (x '{1 2 3} y '{10 20 30}) (= (+ x y) 23))
=> t
and 'one, which resembles CL's 'some:
=> (one (x '{10 20 30} 'ERROR) (= (/ x 10) 2))
20
Chapter 8 describes functions for property lists and alists, with both
'assoc (equal) and 'assq (eq). Some vector manipulation:
=> (setq x (vector 5))
vector[5]
=> (store (x 0) '(a b c))
(a b c)
=> (x 0)
(a b c)
Chapter 9 introduces control flow, starting with catch/throw,
implemented using setjmp/longjmp:
=> (catch (list 'a (list (throw 'b) 'c) 'd))
b
=> (catch (list (throw 'a 'tag1) (throw 'b 'tag2)) 'tag1)
a
which incidentally shows the implementation has left-to-right
evaluation. Errors can be raised and caught; left uncaught the user
ends up in a debugger repl. Chapter 10 (Miscellaneous) gives an
example if in the above function 'mean a typo has been made ('inc
instead of '++):
=> (mean 10 20 30)
ERROR, val: undefined function: inc
=1=> (ss)
[06] error
[05] (inc count)
[04] (setq count <**> sum (+ sum (arg count)))
[03] (prog ((sum 0) (count 0)) (and (= n 0) (return 0)) loop ...)
[02] (mean 10 20 30)
[01] (eval (read))
[00] (toplevel)
t
Here <**> in 04 stands for the frame in the next level, 05.
There is a function to load a file, which optionally takes a verbose
argument that prints out every function defined.
To interface with Unix, there is (! <str>).
The book ends with a kind of compiler, that translates a Lisp program
into a C program which upon loading recreates the Lisp objects. Let me
finish this summary with a quote from that section which I think
captures Hekmatpour's careful way of both explaning and implementing:
compaux ()
This is the actual compilation function. It first opens
the source file for reading, and the target file for
writing. Having evaluated each form in the source file,
it reopens the source file for reading (this is equivalent
to resetting the file). The reason for evaluating the
forms in the souce file is to allow potential
macro-definitions to be established. Such
macro-definitions are later used to macro-expand calls
to macros at compile time. This will result in more
efficient code and will reduce memory consumption.
Having reopened the source file, `compaux' reads each
form in the source file, and processes that form by
calling `procform'. Processed forms are collected in
`forms'; this is simply a long list. The source file is
then closed and the forms in `forms' are reversed to
reflect the order of the forms in the source file.
I think Hekmatpour has written a really nice book about a non-trivial
implementation of a Lisp dialect. It is a pity that it is not easy to
get your hands on it...
- Willem