In this assignment you will implement an interpreter for the programming language Small Lisp as described in class. You may carry out this assignment in groups of at most 3 students, with the number of items required to complete dependent on group size.

All students working in groups or alone, must implement all components of the basic interpreter. Students working alone may use association lists for both value and function environments, but students working in groups of 2 or more must choose a better representation for function environments.

Additional requirements for students working in groups are to implement extensions to Small Lisp. Students working in groups of 2 must implement the language extension for the Small Lisp "map" operator @ as described below. Students working in groups of 3 must implement both the "map" extension, as well as the "reduce" operator !.

Students working alone may choose to implement one or both of these extensions. If the percentage mark on an extension is better than the base mark, it will be treated as a bonus to replace 15% of the base mark (your mark can only improve). This also applies to students working in groups of 2 who do both extensions.

Parsing

Implement a full parser for Small Lisp following the notes on Lexical Analysis and Parsing.

In addition to the recursive parsing functions that return parsed structures and remaining lists of tokens, you should implement a main parsing function that a parses a list of definitions from a file and ensures that all input is consumed.

Interpreter Environments

You should choose appropriate Haskell data structures for implementing environments suitable both for Small Lisp variable and Small Lisp functions.

In general, you can expect that the number of variables to look up at any point is small, but that your program may be looking up function names from a large set of functions. You may use association lists to implement variable environments. However, if you are working in groups of 2 or more, you should choose a better data structure.

See the notes on Symbols and Environments.

Interpreter Core

You should implement Haskell functions sl_eval and sl_apply following the semantic requirements of the Small Lisp reference manual. You can also follow the logic of the Small Lisp Interpreter in Small Lisp, but you should use Haskell programming style as follows.

• Use equations with pattern matching for all the Small Lisp domains.
• Implement the sl_evlis function using map.
• Implement sl_evcond using a suitable predicate iteration function from the Haskell library.
• Implement setup_envs_then_eval using a suitable fold function of the Haskell library.

Further Notes

• Use underscores, not hyphens in your function names.

• The term "bottom" (\(\bot\)) is used for undefined or erroneous computations in the Small Lisp reference manual. In Haskell, this corresponds to Nothing of the Maybe monad.

• You must define a Haskell function implementing each of the Small Lisp primitive functions.
  • For example, for the Small Lisp primitive "first", define Haskell function apply_first.

apply_first [List (sexpr:more)] = Just sexpr
apply_first _                   = Nothing

The pattern checks that the argument list for first has exactly one argument, that the argument is a List, not an atom, and that the list has at least one element. The RHS of the equation is easy.

Language Extensions

Students working in groups must implement the following language extensions: map operator @ for groups of 2, and both map and reduce ! for groups of 3.

Map Operator

The grammar of Small Lisp is extended to add <map-expression> as a new type of <expression>.

<map-expression> ::= @ <function-name> [ <arguments-list> ]
<arguments-list> ::= <expression> {; <expression>}

Each expression in the arguments list is evaluated to produce a list (it is an error if the evaluation does not produce a list). The named function is then applied iteratively to elements taken from the evaluated argument lists. In the first iteration, the function is applied to the first elements of each of the argument lists, in the second iteration, the function is applied to the second elements of each of the argument lists, and so on. The result of the map-expression is the list of results producing from these function calls.

For example, @plus[(2 3 4); (1 1 1)] = (3 4 5).

It is an error if the argument lists are not all of the same length, or if the number of argument lists does not equal the number of arguments expected by the function being mapped.

You must extend both your parser and your evaluator to handle map-expressions.

Reduce Operator

The grammar of Small Lisp is extended to add <reduce-expression> as a new type of <expression>.

<reduce-expression> ::= ! <function-name> [ <expression> ]

The expression is evaluated to produce a non-empty list (it is an error if the evaluation does not produce a list, or the list is empty). If the list has one element, that element is returned. Otherwise the list is successively reduced as follows. The first element is chosen as the initial accumulator value. Then subsequent elements are each combined into the accumulator value using the named function until there are no elements.

For example, !plus[(2 3 4)] = 9.

You must extend both your parser and your evaluator to handle reduce-expressions.

Test Data

• A Small Library of Small Lisp Utility Functions

• Algebraic Expressions in Small Lisp
• Symbolic Differentiation in Small Lisp

• S-Lisp: Lisp Programs as Lisp Data Objects
• Small Lisp Interpreter

Due Date

Your assignment is due Thursday March 15 2018, 14:00. Your interpreter must work correctly for both the symbolic differentiation program in Small Lisp, as well as the Lisp-in-Lisp Small Lisp interpeter!