Lisp Question
This
project involves completing an interpreter for an imperative language written
in a functional language--LISP. A copy of the skeleton interpreter is attached.
To
understand this program, it is essential to understand the program state that
is carried from one statement to the next as the interpreter executes a
program. Consider the sample program that was provided in the requirements:
((assign
x to 1) (assign y to (x * 2)) (write x) (write y))
Show
what is in the three-element list that contains the program state after the
execution of each of the four statements in the above program.
Requirements:
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.
Answer
; 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)))
