A simple Lisp program

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:

; 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)

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.

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.

(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.

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?

(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.

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.

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.

; 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.

; 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.

; 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:

(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.

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.

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.

(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:

(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.

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.

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?

Oh, try this:

Replace this:

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

With this version:

(defun interpret-program (program input)
   (destructuring-bind (memory input output) (interpret-statement-list program (list '(()) input nil))
      (format t "~%DONE...~%MEMORY: ~s~%INPUT: ~s~%OUTPUT: ~s" memory input output)))

The new version doesn't change anything, but it does tell you what the programs state was when its finished. That might help you track down the problem. What I think is happening, is that we are binding the variable X to the string "this is a phony string" --- but because interpret-program only returns the output, we don't see that we've successfully made a memory binding.

I think you'll see something like:
MEMORY: ((x . "this is a phony string"))

So. My TA has responded with the following, in reference to the read statement:

(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)))

"This is almost correct except value must be extracted from the input list. Then, input list must be adjusted to contain the remaining elements (values)."

and the following BNF grammar for the other two pieces:


if_statement ::=
(if expression then statement_list1 else statement_list2)

For if-statement, you must pass expression, statement_list1, statement_list2 and the state, then evaluate in the interpret-if-statement.
while_statement ::=
(while expression do statement_list)
For while-statement, you must pass expression, statement_list and the state.
- Show quoted text -
So. For starters. would the following be correct for the read statement, making the following assumptions. The command put to the interpreter is:
((interpret-program '(read x) (write x) '(21))

Which would make the "value" portion of "state" the third item in the list. Correct?

Then, in the return statement, we need to remove "value" from state. so it would be a list containing everything except the third value:

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

How does that look?

Warren Wilkinson wrote:Oh, try this:

Replace this:

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

With this version:

(defun interpret-program (program input)
   (destructuring-bind (memory input output) (interpret-statement-list program (list '(()) input nil))
      (format t "~%DONE...~%MEMORY: ~s~%INPUT: ~s~%OUTPUT: ~s" memory input output)))

The new version doesn't change anything, but it does tell you what the programs state was when its finished. That might help you track down the problem. What I think is happening, is that we are binding the variable X to the string "this is a phony string" --- but because interpret-program only returns the output, we don't see that we've successfully made a memory binding.

I think you'll see something like:
MEMORY: ((x . "this is a phony string"))

Tried this. No dice
Still getting no output. Grumble.

How does that look?

It would give you a compilation error because (state) isn't a function [hint: it's a variable].

Heres what I want you to do. Add, as the first line, this line of code to every function:

(format t "~%Function: xxx")

Replace xxx with the name of the function. Then when you run your program, you will see where its going (and help you figure out what it is really doing). Please include that output in your next post.

Sir, part of the problem I have is the interpreter only gives errors for unmatched parens. That's it. I'm using Xlisp-plus 3.04. If you have suggestions for some other interpreter, that would be wonderful. The project is due tonight, unfortunately. Trying your code now, will report back.

Still nothing. Does Lisp have any kind of IDE available anywhere?

According to the Xlisp documentation, (format t "a string") should print the string. The reason I had you add format statements everywhere was so that we could trace the flow of execution. If XPlus isn't printing the format statements, and you don't know why, you should probably seek face time with your TA.

TA doesn't give enough of a shit to do such things. You guys were my last hope. Thanks for trying though.