Hi,
I'd like to receive comments and criticism about the following code
(which is a complete file). It's my first lisp program (although its
fourth evolution).
It's a little interpreter for a lisp-like language in which I've
implemented
partial (curried) function application.
I'd particularly like to have pointers on the implementation of the
partial
evaluation. It's implemented as (nested) literal lambda abstractions.
Same request about the implementation of built-ins (which are literal
lambdas).
The code is common lisp, tested in clisp.
Here's an example execution (with blank lines removed):
~/projets/lisp> clisp s3l-04.lisp
Eth-El ith lithtening.
sl> (+ 1 2)
3
sl> (+ a 3) <----- `a` will be evaluated to 1 because of very
simplistic environment.
4
sl> (+ 1)
(LAMBDA (A) (APPLY-BUILT-IN '(LAMBDA (A B) (+ A B)) (APPEND '(1) (LIST
A))))
sl> ((+ 1) 1)
2
sl> (+)
(LAMBDA (A) (APPLY-BUILT-IN '(LAMBDA (A B) (+ A B)) (APPEND 'NIL (LIST
A))))
sl> +
(LAMBDA (A B) (+ A B))
sl> (+ 1 2 3)
*** - too many arguments
~/projets/lisp>
Thank you; code follows,
--thu
;;;; Simple Lisp-Like Language (S3L)
;;;
;;; Add environment and lambda abstractions
;;; to s3l-03.
;;;
;;; - Any form that can be evaluated as a function
;;; can be used as the first element of a list to perform
;;; function application on the rest of the list
;;; (as in Scheme IIRC -- lisp-1).
;;; - Partial (curried) application.
;;;
;;; - TODO add lambda abstractions.
;;; - TODO add lambda marker syntax.
;;;
;;; - For now, the environment is useless.
;;; It provides 1 for any unknown atom.
;;; - *built-ins* provide the .. built-ins.
;;; Maybe should I merge it with the environment ?
;;;
;;; vo minh thu
;;; began 2006.11.29 as a copy of s3l-03.lisp.
;;; last mod. 2006.11.30
;;;
; The read-eval-print loop.
(defun repl ()
(format t "~%sl> ")
(let ((form (read)))
(if (eq form ':q)
(format t "Bye.")
(progn (print (evaluate form nil))
(repl)))))
; 'built-in' functions -- only addition for now.
; The 'implementation' is given as data (textual lambda)
; -- 'eval' is used to turn them in actual functions.
; I find it nice and I can retrieve the arity by inspection.
; But is it really a good idea ? In particular, 'eval' has
; to process a potentially long list of nested lambda's.
; What would be the alternative ? (That list is the result
; of the curried function application, see apply-built-in.)
(defparameter *built-ins* '((+ . (lambda (a b) (+ a b)))))
; Check if a symbol is an built-in
(defun built-in? (a) (assoc a *built-ins*))
; Curried function application of built-ins.
; In fact, I think I can keep this function to apply
; user-defined (i.e. lambda expressions) too.
; Oh wait, no. User-defined functions will be lambda
; expressions in sl, but they will not be represented
; as cl lambda expressions.
(defun apply-built-in (op args)
(let ((la (length args))
(arity (length (cadr op))))
(cond
((< la arity) `(lambda (a) (apply-built-in (quote ,op) (append
(quote ,args) (list a)))))
((= la arity) (apply (eval op) args))
(t (error "too many arguments")))))
; The eval part of the repl.
(defun evaluate (form environment)
(cond
((atom form) (evaluate-atom form environment))
(t (evaluate-list form environment))))
; Evaluate a form which is an atom.
(defun evaluate-atom (form environment)
(cond
((eql form t) t)
((eql form nil) nil)
((numberp form) form)
((built-in? form) (cdr (assoc form *built-ins*))) ; .. performs the
lookup twice.
(t (read-variable form environment))))
; Evaluate a form which is not an atom.
(defun evaluate-list (form environment)
(cond
((eq (car form) 'quote) (cadr form))
((eq (car form) 'cond) (evaluate-cond (cdr form)))
(t (apply-built-in (evaluate (car form) environment)
(map-evaluate (cdr form) environment)))
(t (error "can't evaluate the list"))))
; Evaluate a cond expression.
(defun evaluate-cond (clauses environment)
(cond ((null clauses) (error "no clause evaluates to true"))
((evaluate (caar clauses)) (evaluate (cadar clauses)))
(t (evaluate-cond (cdr clauses)))))
; Evaluate each argument of an argument list.
(defun map-evaluate (args environment)
(cond ((null args) nil)
(t (cons (evaluate (car args) environment)
(map-evaluate (cdr args) environment)))))
; Look up the value of a variable in an environment.
; Really silly for now.
(defun read-variable (form environment) 1)
; Print a nice banner and enter the repl.
(format t "Eth-El ith lithtening.")
(repl)
······@gmail.com wrote:
> ~/projets/lisp> clisp s3l-04.lisp
> Eth-El ith lithtening.
> sl> (+ 1 2)
> 3
> sl> (+ a 3) <----- `a` will be evaluated to 1 because of very
> simplistic environment.
> 4
> sl> (+ 1)
> (LAMBDA (A) (APPLY-BUILT-IN '(LAMBDA (A B) (+ A B)) (APPEND '(1) (LIST
> A))))
This is broken; it's returning the source code of a function, rather
than a function object. You read-eval-print loop is missing part of the
eval; it's transforming the syntax, but not evaluating it to produce
the object that it represents.
I would expect something looking like #<FUNCTION ...> to come out.
> sl> ((+ 1) 1)
> 2
So here you must have some gross compensating hack to get it working,
involving EVAL. If (+ 1) returns a lambda expression, the evaluation
semantics of ((+ 1) 1) must be that (+ 1) is passed through EVAL to
produce an function object, which is then funcalled.
And so here, you would have a function object in the first position of
the list, which according to the rules of this dialect, would be called
with the specified argument, i.e. this would translate to
(funcall <function-object> 1)
> ; The read-eval-print loop.
> (defun repl ()
> (format t "~%sl> ")
> (let ((form (read)))
> (if (eq form ':q)
> (format t "Bye.")
> (progn (print (evaluate form nil))
> (repl)))))
Common Lisp implementations are not required to perform tail call
optimization. So this is actually blowing the stack.
> ((< la arity) `(lambda (a) (apply-built-in (quote ,op) (append
> (quote ,args) (list a)))))
See, here is the problem. This case in your evaluator returns
unevaluated source code generated by the backquoted template. You've
covered up for this elsewhere.
> ((= la arity) (apply (eval op) args))
Namely here, where you appeal to Lisp's EVAL to reduce OP to a
function. OP is not actually an operator, but Lisp source code.
What you can do is allow the lambda expression to be evaluated normally
rather than backquoted. Then it will be reduced to a function, which
you can then APPLY to your args.
An interesting exercise would be for your evaluator to translate the
entire expression to Lisp, and then use Lisp to evaluate (or compile!)
it.
First, let me thank you for your answer.
> > (LAMBDA (A) (APPLY-BUILT-IN '(LAMBDA (A B) (+ A B)) (APPEND '(1) (LIST
>> A))))
>This is broken; it's returning the source code of a function, rather
>than a function object. You read-eval-print loop is missing part of the
>eval; it's transforming the syntax, but not evaluating it to produce
>the object that it represents.
But I was wondering if it was really broken. I meant,
is it really better to fall back on the underlying #<FUNCTION ...> ?
Can't I just say that it's *my language* representation of function and
that I don't use cl one ?
But, I will try the way you point.
>I would expect something looking like #<FUNCTION ...> to come out.
>> sl> ((+ 1) 1)
>> 2
>So here you must have some gross compensating hack to get it working,
>involving EVAL. If (+ 1) returns a lambda expression, the evaluation
>semantics of ((+ 1) 1) must be that (+ 1) is passed through EVAL to
>produce an function object, which is then funcalled.
Indeed...
>And so here, you would have a function object in the first position of
>the list, which according to the rules of this dialect, would be called
>with the specified argument, i.e. this would translate to
> (funcall <function-object> 1)
>> ; The read-eval-print loop.
>> (defun repl ()
>> (format t "~%sl> ")
>> (let ((form (read)))
>> (if (eq form ':q)
>> (format t "Bye.")
>> (progn (print (evaluate form nil))
>> (repl)))))
>Common Lisp implementations are not required to perform tail call
>optimization. So this is actually blowing the stack.
Right. I will use a loop.
>> ((< la arity) `(lambda (a) (apply-built-in (quote ,op) (append
>> (quote ,args) (list a)))))
>See, here is the problem. This case in your evaluator returns
>unevaluated source code generated by the backquoted template. You've
>covered up for this elsewhere.
Cont'd 'indeed'.
>> ((= la arity) (apply (eval op) args))
>Namely here, where you appeal to Lisp's EVAL to reduce OP to a
>function. OP is not actually an operator, but Lisp source code.
Yes I knew.
>What you can do is allow the lambda expression to be evaluated normally
>rather than backquoted. Then it will be reduced to a function, which
>you can then APPLY to your args.
Ok.
>An interesting exercise would be for your evaluator to translate the
>entire expression to Lisp, and then use Lisp to evaluate (or compile!)
>it.
I'm not sure I understand this. Is it a re-phrased of the above ?
The 'entire expression' is the quoted lambda that need to be turned
into #<FUN...> ?
Thanks, I'll post again the improvement.
--thu
Hi,
Sample execution is now:
~/projets/lisp> clisp s3l-05.lisp
Eth-El ith lithtening.
sl> (+ 1 2)
3
sl> (+ 1)
(1 . #<FUNCTION :LAMBDA (A) (APPLY-BUILT-IN OP (APPEND ARGS (LIST
A)))>)
sl> +
(2 . #<FUNCTION :LAMBDA (A B) (+ A B)>)
sl> ((+ 1) 2)
3
sl> :q
Bye.
~/projets/lisp>
> > [snip]
> >This is broken; it's returning the source code of a function, rather
> >than a function object. You read-eval-print loop is missing part of the
> >eval; it's transforming the syntax, but not evaluating it to produce
> >the object that it represents.
Now, *built-ins* is
(defparameter *built-ins* (list (cons '+ (cons 2 (lambda (a b) (+ a
b))))))
i.e. its element is ('+ . (2 . #<FUNCTION ..>))
So it's both a function object and its arity.
> > [snip]
> >> ; The read-eval-print loop.
> >> (defun repl ()
> >> (format t "~%sl> ")
> >> (let ((form (read)))
> >> (if (eq form ':q)
> >> (format t "Bye.")
> >> (progn (print (evaluate form nil))
> >> (repl)))))
> >Common Lisp implementations are not required to perform tail call
> >optimization. So this is actually blowing the stack.
> Right. I will use a loop.
The loop is now:
(defun repl ()
(loop
(format t "~%sl> ")
(let ((form (read)))
(if (eq form ':q)
(progn (format t "Bye.")
(return))
(print (evaluate form nil))))))
Other changed parts (which simply follow the change of function
representation):
; Curried function application of built-ins.
(defun apply-built-in (op args)
(let ((la (length args))
(arity (car op)))
(cond
((< la arity) (cons (- arity la) (lambda (a) (apply-built-in op
(append args (list a))))))
((= la arity) (apply (cdr op) args))
(t (error "too many arguments")))))
; The eval part of the repl.
(defun evaluate (form environment)
(cond
((atom form) (evaluate-atom form environment))
(t (evaluate-list form environment))))
; Evaluate a form which is an atom.
(defun evaluate-atom (form environment)
(cond
((eql form t) t)
((eql form nil) nil)
((numberp form) form)
((built-in? form) (cdr (assoc form *built-ins*))) ; .. performs the
lookup twice.
(t (read-variable form environment))))
; Evaluate a form which is not an atom.
(defun evaluate-list (form environment)
(cond
((eq (car form) 'quote) (cadr form))
((eq (car form) 'cond) (evaluate-cond (cdr form)))
(t (apply-built-in (evaluate (car form) environment)
(map-evaluate (cdr form) environment)))
(t (error "can't evaluate the list"))))
Thanks, bye,
Thu