·············@gmail.com (gewoon.iemand) writes:
> Hi
>
> I'm implementing a LISP interpreter in JAVA. I have made a structure
> of classes to express, parse and evalute LISP elements. There is an
> SExpression base class and, among others, a Symbol and a Functor sub
> class.
This is strange.
If you're writing a lisp, you should have types such as:
nil cons symbol integer float string array function structure object class
but nothing like SExpression.
The reader would parse input text and provide the interpreter with a
list, that is a cons.
> When I parse a list, the parser expects the first element to be a
> functor (I deal with operators in the same way as I deal with
> functions).
Actually, functions cannot be read. The reader reads lists, symbols,
and literal values such as integer, string, arrays.
For example, when you enter (sin (/ pi 3)) the reader parses the
string "(sin (/ pi 3))" and returns the following list, where all
non-cons box is either a number (3) or a symbol:
+-----------------------------------------------+
| (sin (/ pi 3)) |
| |
| +---+---+ +---+---+ |
| | * | * |-->| * |NIL| |
| +---+---+ +---+---+ |
| | | |
| v v |
| +-----+ +---+---+ +---+---+ +---+---+ |
| | SIN | | * | * |-->| * | * |-->| * |NIL| |
| +-----+ +---+---+ +---+---+ +---+---+ |
| | | | |
| v v v |
| +---+ +----+ +---+ |
| | / | | PI | | 3 | |
| +---+ +----+ +---+ |
+-----------------------------------------------+
> When the list is evaluated, it evaluates every element and
> then feeds it to the functor, which searches for the function to use
> (dynamic), and executes.
That's a strange evaluation algorithm.
Modern lisp distinguish between:
- functions all arguments are evaluated before passing
their value as parameter to the function.
- macros no argument is evaluated, all arguments are
passed unevaluated as parameter to the macro.
- special operators the rule for evaluation of arguments depends
on the special operator, but basically you
can take it as for macros, and let the
implementation of the special operator to
explicitely evaluate the arguments.
> So, when I enter (+ 1 2 3) i get 6. When I enter (+ a b c) I get a
> number, because the + function gets the value of the symbols a b and c
> when they get evaluated (assuming they're bound to a value).
> However, I'm running into a problem when I parse quoted lists. I could
> enter '(aVariable 1 2 3) or '(aFunction 1 2 3). When it gets parsed,
> the parser cannot know whether its a variable or a functor. I could
> also enter '(1 2 3 4), and the first element is neither.
As Randall said, ' is a reader macro that substitute (quote x) for 'x.
quote is a special operator that returns its argument unevaluated.
> How should I deal with this? Is my implementation wrong and should I
> make the determination of whether to treat the first element as a
> symbol, functor or constant at run time, when a list is evaluated?
Forget about that Sexpression class.
First implement (in java) a REPL = Read Eval Print Loop:
(LOOP (PRINT (EVAL (READ))))
Next implement:
- a READ function that takes input and returns an atom or
a list (no evaluation!).
- an EVAL function that takes an atom or a list and evalutes it.
In summary that eval function works like this:
(defun EVAL (x)
(cond
((atom x) x) ; atoms are self evaluating 1 ==> 1, "x" ==> "x"
((special-operator-p (car x)) (eval-special-operator (car x)
(cdr x)))
((macro-p (car x)) (eval-macro (car x) (cdr x)))
((primitive-function-p (car x)) (apply-primitive (car x)
(cdr x)))
((function-p (car x)) (apply (car x) (cdr x)))
(t (error "~A is not a function" (car x)))))
- implement a few special operators. You need at least IF or COND and LOOP.
- implement a few primtive functions. You need at least: CONS CAR CDR NULL.
- implement the APPLY function that interprets the function call.
- implement the PRINT function.
- implement the LOOP special operator.
For example, usually in lisp, a function call can take either a symbol
naming a function or a lambda expression as CAR:
(+ 2 3)
((lambda (x y) (* 2 x y)) 2 3)
So your function-p function could be defined as:
(defun function-p (x) (or (and (symbolp x) (fboundp x))
(and (listp x) (eq (quote lambda) (car x)))))
> Also, the setq function seems illogical. Suppose I make a function for
> setq. Then the elements get evaluated and they are fed to the setq
> function. But in the case of the example (setq a 1), a is evaluated
> and becomes a value (or throws an error if it's not bound). The setq
> function does not need a value, it needs the variable! I tought of
> making the parser translate setq into set ' , but that feels wrong.
Congratulation, you've discovered that SETQ cannot be a function.
It's the reason why it must be a special operator. You'll have a java
function that will take as argument a symbol and a value and assign
the value to the variable the symbol names.
> This leads me to the idea that evaluating before the function gets
> executed is wrong. My implementation does not have a problem with set.
> When (set 'a 1) gets evaluated, 'a evaluates into a, which is what the
> set function needs to know in order to do what it's supposed to do
> (namely binding "a" to the value 1). How do other implementations deal
> with this?
>
> Does anyone know what I'm doing wrong, maybe give some suggestions?
> Thanks in advance.
--
__Pascal Bourguignon__