Lisp Question

The fourth project
involves completing a LISP program hat is provided in the case study of module
5. That program interprets a simple imperative language. The skeleton version
provided interprets assignment and write statements and evaluates binary
expressions. The following dialog illustrates the execution of a simple program
with that version.

>(interpret-program '((assign x to 1) (assign y to (x * 2)) (write x) (write y)) nil)

(1 2)

The complete grammar of the language is provided below in extended BNF:

program ::=

statement_list

statement_list::=

statement|

   ({statement})

statement ::=

assignment_statement|

write_statement|

read_statement|

if_statement|

while_statement

assignment_statement::=

   (assignvariable to expression)

write_statement::=

   (writeexpression)

read_statement::=

   (readvariable)

if_statement::=

   (ifexpression then statement_list1else statement_list2)

while_statement::=

   (whileexpression do statement_list)

expression ::=

variable|

literal|

(unary_operator expression) |

(expressionbinary_operator expression)

Nonterminals are shown in red, terminals in blue and BNF metasymbols are black. You must add the functions to interpret the read, if and while statements and the function to evaluate unary expressions and modify the necessary functions to call them. You are not required to perform any syntax checking on the input. You may assume that the programs are syntactically correct. Explicit input and output should not be used in this program. The main function should accept the input as a parameter. The output should be the value of the main function. In addition, no explicit iteration should be used, recursion must be used in its place.

; 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)
                                    (fourth statement)
                                    (sixth statement)
                                    state))
        ((eq (first statement) 'while)
            (interpret-while-statement (second statement) (fourth 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 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)))

; interprets the read statement, taking first value from input list
; and assigning the value to the specified variable

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

; interpets the while statement, evaluating its expression and, if its
; value is true, interpeting statement list and interpeting while
; statement again.

(defun interpret-while-statement (expression statement-list state)
  (let
        ((memory (first state))
         (input (second state))
         (output (third state)))
      (let ((condition (evaluate-expression expression state)))
        (cond
          (condition
           (interpret-while-statement expression statement-list
                                      (interpret-statement-list statement-list
                                                                state)))
          (t
           state)))))

; interprets the if statement, evaluating its expression, and if its value
; is true, interprets true-statement-list, and false-statement-list otherwise

(defun interpret-if-statement (expression
                               true-statement-list
                               false-statement-list
                               state)
  (let
        ((memory (first state))
         (input (second state))
         (output (third state)))
      (let ((condition (evaluate-expression expression state)))
        (cond
          (condition
           (interpret-statement-list true-statement-list state))
          (t
           (interpret-statement-list false-statement-list state))))))


; 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) 2)
            (evaluate-unary-expression expression state))
        ((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))))

; evaluates an unary rexpression by evaluating the subexpression
; and then applying the operator to the subexpression

(defun evaluate-unary-expression (expression state)
  (let
      ((operator (first expression))
       (operand (evaluate-expression (second expression) state)))
    (apply operator (list 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)))