Reference no: EM132978145

COMP3000 Programming Languages - Macquarie University

Assignment - Interpreter

Overview
The assignment code bundle provides a Scala skeleton program for constructing an interpreter for a simplified LISP-like language. For example, the input:

(+ 3 5) produces 8
(* (+ 3 4) 5) produces 35 ( = 7 * 5)
(setq x (+ 3 5)) assigns the value 8 to the variable x
(quote (a b c)) produces the list (a b c)
(car (quote (a b c))) gets the head of the list (a b c), producing a
(cdr (quote (a b c))) gets the tail of the list (a b c), giving the list (b c) (If you want to see more about LISP then visit clisp.org.)
Language basics
As can be seen above, the language has a very simple syntax that relies heavily on brackets and prefix notation (i.e. the function/operator comes before the arguments).

In our simplified language, the only things to be manipulated are:
• symbols, e.g. +, setq, x, quote, car, cdr
• numbers, e.g. 3, -5; these are always only integers (without +; e.g. +4 not allowed)
• lists

In the language, expressions and statements are lists and data items can also be lists. In the fourth example line above, the list (a b c) was produced. It might seem that we could write just:

(a b c)

and it would give us that list; but whenever the language is given a list to evaluate, it treats the first thing in the list as a function name or operator, e.g.

(+ 3 5) + is the operator
(car (quote (a b c))) car is the function

To override this default behaviour, the special form quote is used which treats its argument literally rather than trying to evaluate it; e.g.
(quote (+ 3 5)) produces the list (+ 3 5) We have two special symbols in the language:
• nil which always evaluates to nil
• t which always evaluates to t nil is equivalent to the empty list.
In the language, if a condition evaluates to nil then it is considered to be false; any other value means true and t is conventionally used to represent true.

Language functionality
You will need to implement the following.

Usually in the language, if an expression has the form:

(a b) or (a b c) [where b, c could also be expressions] then a is interpreted as the function and b, c are interpreted as the arguments.
It will be evaluated by:
1. evaluating the argument expressions
2. passing the values of the evaluated arguments to the function

Functional programming
While the aim of the programming is write the interpreter, you will also be assessed on how well your program is written in the style of functional programming. For example:
• use val instead of var for variable declarations
• try to avoid iterative loops (for/while); use map, filter, reduce, ...
• use match instead of multiple Ifs; in particular, use a single match in eval with a case for each of the different kinds of expressions

Running the program
The skeleton for this assignment is designed to be run from within sbt. In the command prompt for sbt, there are four relevant commands:
• test - runs the test suite (tests are in src/test/scala/iInterpretTests.scala
• run - executes the main function in src/main/scala/Main.scala which repeatedly prompts you to enter an expression to be executed; an empty input line will terminate it
• compile - compiles any changed source files; there is no need to separately compile because the run and test commands always do any required compilation
• console - this is used for impromptu testing (after you have done a compile); it will bring up a "scala>" prompt; then enter:
import org.mq.interpret.Interpret._
now you will be able to access the Scala functions and classes in Interpret.scala; e.g.
LSymbol("fred")
or:
eval(LSymbol("nil"))

What you must hand in and how
A zip file containing:
• Interpret.scala
• InterpretTests.scala

Your submission should include all of the tests that you have used to make sure that your program is working correctly. Note that just testing one or two simple cases is not enough for many marks. You should test as comprehensively as you can.

Attachment:- Programming Languages.rar