Miniproject.

The goal of the course Programming Language Implementation and Formalisation, is that the student should be able to take a concept from programming language theory, and implement it.

As such, we will be teaching you some implementation techniques, and also some programming language formalisations -- To make a connection between the two, we will also ask you to do small projects.

This first project is to write an interpreter for the Boa programming language. Boa is a tiny subset of python3, with the intent that valid Boa programs behave equivalent when run using the boa or python3 interpreter.

Credits

The Boa programming language was designed by Andrzej Filiniski, and this project is based on two weekly assignments from the course Advanced Programming, where Andrzej is course responsible at the time of writing.

The Boa Language

Boa works with a type of structured Values given by the following algebraic datatype:

data Value =
    None
  | Boolean Bool
  | Number  Integer
  | Text    String
  | List    [Value]

That is, a Boa value is one of the three special atoms None, True, or False, an integer, a character string, or a (possibly empty) list of values.

A Boa expression has one of the following forms:

data Expression =
    Constant  Value
  | Variable  VariableName
  | Operation OperationSymbol Expression Expression
  | Not Expression
  | Call FunctionName FunctionInput
  | ListExpression    [Expression]
  | ListComprehension [Expression] [Clause]

The intended semantics of expressions should be unsurprising, with the following notes:

1. Constant v evaluates to the value v
2. Variable x evaluates to the value currently bound to the variable x
3. Operation o e1 e2 applies the operator o to e1 and e2, and the meanings of the arithmetic operators Plus|...|Mod are the obvious ones, with the arguments required to be integers. The comparison operators, Eq|Less|Greater return Boa atoms True or False depending on the corresponding relation and the arguements.
4. Not returns the logical negation of the value of its arguement. For this purpose, the atoms None and False, the integer 0, the empty string and the empty list are considered to represent falsehood, and all other values represent truth.
5. Call f [e1, ... en] evaluates the arguments e1..en to values v1..vn and then calls the built-in function f on the resulting values. There are two built-in functions in Boa. The built-in function range may be called 1-3 integer values. print can be called with as many arguments as the programmer likes.
6. ListExpression [e1..en] valuates e1..en to values v1..vn and returns the value List [v1..vn].
7. ListComprehension e_0 [c0..cn] is essentially analogous to Haskell's [e_0 c0 .. cn ] in python. As an example,

   ListComprehension
     (Operation Times (Variable "x") (Variable "x"))
     [ For "x" (Call "range" (Constant (Number 10)))
     , If $ Operation Greater (Variable "x") (Constant (Number 5))
     ]
   

   corresponds to the comprehension

   [ x for x in range(10) if x > 5 ]
   

Finally, a Boa program consists of a sequence of statements:

type Program = [Statement]

data Statement =
    Define  VariableName Expression
  | Execute              Expression

A definition statement Define x e evaluates e to a value, and binds x to that value for the remaining statements in the sequence. An expression statement Execute e just evaluates e and discards the result (But any printing and/or errors arising from evaluating e still take effect.)

Whenever an error is signaled, evaluation or execution stops immediately with an error message, and all current variable bindings are discarded. However, any lines of output successfully generated before the error occurred are still kept.

Implementation (Interpreter)

The main type constructor for Boa computations is the following:

type Environment = [(VariableName, Value)]
type Runtime a   = Environment -> (Either RuntimeError a, Output)

newtype Boa a = Boa {run :: Runtime a}

Boa computations have (read-only) access to the environment, and return either a runtime error or a result of the expected type, together with (in either case) a possibly empty list of output lines produced by the computation.

We ask you to make Boa an instance of the Monad type class (and Functor and Applicative as well, but you can use the provided boilerplate code for that). Then, define the following associated operations for the monad:

abort  :: RuntimeError -> Boa a
look   :: VariableName -> Boa Value
bind   :: VariableName -> Value -> (Boa a -> Boa a)
output :: String -> Boa ()

Here, abort re is used for signaling the runtime error re, look x returns the current binding of the variable x. Conversely, the operation bind x v b runs the computation b with x bound to v in addition to any other current bindings (Any previous previous binding for x is temporarily inaccessible while running b). Finally, output s appends the line s to the output list. s should not include a trailing newline character (unless the line arises from printing a string value that itself contains an embedded newline).

The rest of your code should not depend on the exact definition of the type Boa a; that is, it should neither directly use the value constructor Boa nor the projection run, but always go through one of the above functions.

Next, define the following helper functions:

truthy  :: Value -> Bool
operate :: OperationSymbol -> Value -> Value -> Either ErrorMessage Value
apply   :: FunctionName -> FunctionArguments -> Boa Value

truthy v simply determines whether the value v represents truth or falsehood. operate o v1 v2 applies the operator o to the arguments v1 and v2, returning either the resulting value, or an error message if one or both arguments are inappropriate for the operation. Similarly, apply f [v1,...,vn] applies the built-in function f to the argument tuple v1,...,vn, possibly signaling an error if f is not a valid function name (BadFunction), or if the arguments are not valid for the function (BadArgument).

Finally, define the main interpreter functions,

eval    :: Expression -> Boa Value
exec    :: Program -> Boa ()
execute :: Program -> (Output, Maybe RuntimeError)

eval e is the computation that evaluates the expression e in the current environment and returns its value. Likewise, exec p is the computation executing the program (or program fragment) p. Finally, execute p explicitly returns the list of output lines, and the error message (if relevant) resulting from executing p in the initial environment, which contains no variable bindings.