LispForum

Posted: **Mon Dec 27, 2010 8:59 am**

So i'm writing a simple LISP program to interpret statements, for example in the form: ((interpret-program '(read x) (write x) '(21))
But i can't get any meaningful output, so i can't figure out what's going wrong. I'm completely new to functional languages; Though i've done plenty of reading, and can use the statements properly on their own, writing a program has been a huge hardship. Can anyone provide some useful tips, pointers, even (another) tutorial (i've read 2 from end to end). Thanks in advance. Here's the code i've worked through so far:

Code: Select all

; main function creates state containing supplied input and empty
; memory and output, returns output

(defun interpret-program (program input)
    (third (interpret-statement-list program (list '(()) input nil))))

; interprets a single statement if statement-list is a single statement
; recursively interprets all statements if it is a list

(defun interpret-statement-list (statement-list state)
    (cond
        ((null statement-list) state)
        ((atom (first statement-list)) 
            (interpret-statement statement-list state))
        (t (interpret-statement-list (rest statement-list)
            (interpret-statement (first statement-list) state)))))

; determines the type of statement based on the first word
; and calls the appropriate function to interpret it

(defun interpret-statement (statement state)
    (cond
        ((eq (first statement) 'assign)
            (interpret-assignment-statement (second statement)
            (fourth statement) state))
        ((eq (first statement) 'write)
            (interpret-write-statement (second statement) state))
	((eq (first statement) 'read)
	    (interpret-read-statement (second statement) state)))
	((eq (first statement) 'if)
	    (interpret-if-statement (second statement) state))
	((eq (first statement) 'while)
	    (interpret-while-statement (second statement) state)))


; interprets the write statement by evaluating the expression
; and appending its value to the output stream

(defun interpret-write-statement (write-expression state)
    (let
        ((memory (first state))
        (input (second state))
        (output (third state)))
    (list memory input (append output 
        (list (evaluate-expression write-expression state))))))

;interprets the read statement by removing the first item from the list
; and putting it into a variable.

(defun interpret-read-statement (read-expression state)
    (let
        ((memory (first state))
        (input (second state)
        (output (third state))
     	(set-value (memory) (input) (output))
        (list (evaluate-expression read-expression state)))))




; interprets the assignment statement by evaluating the expression
; and assigning the value to the specified variable

(defun interpret-assignment-statement (variable expression state)
    (let
        ((memory (first state))
        (input (second state))
        (output (third state)))
    (list (set-value memory variable 
        (evaluate-expression expression state)) input output)))

; evaluates an expression by checking whether it is a literal, a
; variable, a binary or unary expression

(defun evaluate-expression (expression state)
    (cond
        ((numberp expression) expression)
        ((atom expression) (get-value (first state) expression))
        ((eq (length expression) 3)
            (evaluate-binary-expression expression state))))

; evaluates a binary expression by first evaluating the subexpressions
; and then applying the operator to those subexpressions

(defun evaluate-binary-expression (expression state)
    (let
        ((left-operand (evaluate-expression (first expression) state))
        (operator (second expression))
        (right-operand (evaluate-expression (third expression) state)))
    (apply operator (list left-operand right-operand))))

; adds the variable-value pair to the head of the association list
; that comprises the current state of the memory.  Previous 
; occurences of that variable are not removed.

(defun set-value (memory variable value)
    (cons (list variable value) memory))

; retrieves the value of a variable from the association list
; that comprises the current state of the memory 

(defun get-value (memory variable)
    (second (assoc variable memory)))

;handles if statements
;if the expression is null, then its false, so skip it
;if the expression is true, then we do whatever is in state
;the final statement must evaluate to true
(defun interpret-if-statement (expression state)
	(cond
        	((null statement-list) state)
		(expression (statement-list) state)
	
		((t first state))
		
	
;handles while statements.  all it does is evaluate.  If its true, we've reached the condition
;and so we stop. Otherwise, recursively evaluate itself again, until we reach a false value.  Uses
;simple tail recursion.

(defun interpret-if-statement (expression state)
	(cond
        	((null statement-list) state)
		(expression state)
		(interpret-if-statement(expression state))
		(expression (statement-list) state)

Posted: **Mon Dec 27, 2010 3:21 pm**

Let me clarify: For starters, I'd just like to get the "read" portion working, so I can get some meaningful input and output from xlisp. Thanks.

Posted: **Mon Dec 27, 2010 8:12 pm**

I'm not familiar with XLisp. A quick search indicates there are several variants, some closer to Common Lisp and some closer to Scheme.

Here's some CL code that might interest you. You might also read some of the (free!) books listed in this forum's FAQ.

Code: Select all

(defun do-something (string)
  (eval (read-from-string string)))
(do-something "(+ 1 2)") ;; returns the number 3

When trying to figure out what code is doing, the TRACE macro can be very helpful.

Posted: **Mon Dec 27, 2010 9:03 pm**

Programs of this type are usually called meta-circular evaluators (http://en.wikipedia.org/wiki/Meta-circular_evaluator). SICP (http://mitpress.mit.edu/sicp/) has a chapter on it.

Your code is a bit obtuse to me... hold on...

You have three types of statements
- Numbers (self evaluating)
- Symbols (memory lookup)
- 2-arg function calls.
- (currently, anything else will just NIL, not even throw an error --- so (read x) does nothing, as does (write x) and '(21)...) -- problem is in evaluate-expression.
You keeping an assoc list of bindings (for memory)

Do you mind if I take a crack at this?

First, I took memory off the parameter stack and put it into a global variable. Some people hate global variables, but in this case it really cleans up the parameter stack and lets important details shine through.

Next I bundled everything into a singe COND statement in myeval. Factorization is good and all, but if the called function is only used once (and is short) it can be easier to read this way. If the called function is not short, I'll usually define it with FLET (http://www.ai.mit.edu/projects/iiip/doc ... rolet.html).

Lastly, I made function invocation (interpret-binary in your code and the T case of myeval's cond in mine) generic enough to work with any amount of arguments by using mapcar and apply. Note, my code doesn't handle important things like IF and WHILE, those would need to be added to myeval.

Does this help? I do have one question, and it might sound mean, but why did you have the program almost totally finished before you noticed it didn't produce output in the simple cases?

Code: Select all

(defvar *memory* nil)

(defun read-mem (var) (cdr (assoc var *memory*)))
(defun unquote (var) (second var))
(defun write-mem (var val) (setf *memory* (acons (unquote var) val *memory*)) val)

(defun myeval (stmt)
  (cond ((null stmt) nil)
	((eq stmt t) t)
	((symbolp stmt) (read-mem stmt))
	((atom stmt) stmt)
	((eq (car stmt) 'quote) stmt)
	(t (apply (car stmt) (mapcar #'myeval (cdr stmt))))))

(defun interpret (stmts)
  (if (null (cdr stmts)) ;; Avoid a needless recursion because then our return value would be from it.
      (myeval (car stmts)) 
      (progn (myeval (car stmts)) (interpret (cdr stmts)))))

(interpret '((write-mem 'aa (+ (- 3 2) 5 6)) (write-mem 'bb aa) (* bb bb))) ;; Gives 144, correct.

Posted: **Tue Dec 28, 2010 6:20 am**

Actually, its an extra-credit project for a 300 level class. I've been having a lot of trouble with it -- the skeletal portion included everything except the read, if, and while handlers. I also modified the statement that determines which function to call. I'm required to use recursion instead of iteration. I'd really just like to get the read statement working, so I can puzzle out the rest myself -- the xlisp interpreter gives zilch for feedback, so debugging is nigh impossible. While I don't honestly feel i'll likely ever use lisp again, I'd still like to learn about it.

Posted: **Tue Dec 28, 2010 1:09 pm**

Okay, well that helps then. I'll walk you through the code skeleton, and maybe that will help you understand what to change... but first, let me point out that this skeletal code isn't what I would call 'good lisp code', don't let a bad example turn you off a good language.

Code: Select all

; main function creates state containing supplied input and empty
; memory and output, returns output

(defun interpret-program (program input)
    (third (interpret-statement-list program (list '(()) input nil))))

Interpret-program calls interpret-statement-list after mangling input: (list '(()) input nil) is the same as (list '(nil) input nil). That '(nil) is the initial state of the program memory (i.e. empty). The last nil is the programs current return value. This three-argument list they're calling 'state'. Interpret-statement-list receives a 'state' and is expected to return a 'state'. By taking the THIRD of the returned state, you take the programs final return value.

Code: Select all

; interprets a single statement if statement-list is a single statement
; recursively interprets all statements if it is a list

(defun interpret-statement-list (statement-list state)
    (cond
        ((null statement-list) state)
        ((atom (first statement-list)) 
            (interpret-statement statement-list state))
        (t (interpret-statement-list (rest statement-list)
            (interpret-statement (first statement-list) state)))))

This routine is pretty straight forward, but probably not correct.
Statement-list will be like this: (instruction1 instruction2 ... instructionN).

If the list is null, than we've done everything, so just return state.
if instruction1 (i.e. (first statement-list)) is an atom, we call interpret-statement with all of our instructions. This is not what I would expect. (It essentially will cause (... write 1 (read 2)) to be treated the same as (... (write 1 (read 2))) ... I think.)
Otherwise instruction1 must be a list itself, so you call interpret-statement with that list. The rest of the program after this instruction is silently dropped.

Code: Select all

; determines the type of statement based on the first word
; and calls the appropriate function to interpret it

(defun interpret-statement (statement state)
    (cond
        ((eq (first statement) 'assign)
            (interpret-assignment-statement (second statement)
            ([b]fourth[/b] statement) state))                                               ;; should be third maybe?
        ((eq (first statement) 'write)
            (interpret-write-statement (second statement) state))
   ((eq (first statement) 'read)
       (interpret-read-statement (second statement) state))[b])[/b]       ;; extra ) 
   ((eq (first statement) 'if)
       (interpret-if-statement (second statement) state))
   ((eq (first statement) 'while)
       (interpret-while-statement (second statement) state)))

This looks pretty good, I've highlighted a few things I think to be in error, You could make it easier to read like so:

Code: Select all

(defun interpret-statement (statement state)
    (case (first statement)
        (assign  (interpret-assignment-statement (second statement) (fourth statement) state))
        (write     (interpret-write-statement (second statement) state))
        (read     (interpret-read-statement (second statement) state))
        (if          (interpret-if-statement (second statement) state))
        (while    (interpret-while-statement (second statement) state)))

I've got to run at the moment, but that might help you get started. Once you've looked this over and made changes you think are appropriate, try your program on REALLY simple expressions like (+ 1 1) and (+ (* 2 4) 3), etc. See if you get proper results there before we go onto more difficult tasks.

Posted: **Tue Dec 28, 2010 5:17 pm**

Even with your simplificiations, will the read statement function? It still does not seem to respond to output when i try to read in a variable/value pair and then write it out. It does respond to math, but can't the LISP interpreter do that on its own?

The important step for me is getting it to read a variable/value pair, then have it write back out. If I can do that much, I can get the rest working, I believe.

--Sir, I did try the read-mem version with a global variable, but can't seem to get it to function. I'm working on that now.

Posted: **Tue Dec 28, 2010 8:17 pm**

Yes the Lisp interpreter can do math on its own, but in this case it should be going through your routines.
Lets look at the read statement. We know it should return a 'state', and given that you've said it works like this: "(read x)", I believe you want it to take input and bind it to the variable X.

Code: Select all

(defun interpret-read-statement (read-expression state)
    (let
        ((memory (first state))
        (input (second state)
        (output (third state))
        (set-value (memory) (input) (output))
        (list (evaluate-expression read-expression state)))))

I'm not entirely sure, but I would think you would want something like this:

Code: Select all

(defun interpret-read-statement (read-variable state)
    (let ((memory (first state))
           (input (second state)
           (output (third state))
        (list (set-value memory read-variable "this is a phony read value!!!") input output)))

In my code above, I don't actually do any reading, I just fake it by assigning the string "this is a phony read value!!!" to the variable. Get the program working until you read and get that string back, and then we can work on actually getting something from the user.

Also, where is the skeleton code? I want to know what the skeleton code's original intentions were.

Posted: **Tue Dec 28, 2010 8:28 pm**

The skeleton code looked like the first post, minus the interpret-statement for if, while, and read. the read statement also did not exist -- I based it upon the write statement and added another atom, then tried to place that atom into variable. Clearly, it doesn't work. I'll give yours a try. Thanks for your help so far, everyone. I really appreciate it.

Posted: **Wed Dec 29, 2010 7:28 am**

I tried the read statement with the dummy line and its still not outputting -- I'm really stuck here. I did replace the statement-selection with the case statement, as it does read clearer. I just don't understand why the application of the variable/value pair refuses to be made. Perhaps what I really need is an explanation of how I should be debugging this. All i'm familiar with is the backtrace. In java, I can look back at the stack and the line number it failed, ultimately revealing which command failed. Does something similar exist in a functional language?

LispForum

A simple Lisp program

A simple Lisp program

Re: A simple Lisp program

Re: A simple Lisp program

Re: A simple Lisp program

Re: A simple Lisp program

Re: A simple Lisp program

Re: A simple Lisp program

Re: A simple Lisp program

Re: A simple Lisp program

Re: A simple Lisp program