# Interpreter

A video on this section can be found here.

`module Interpreter where`

import AbstractSyntax

We explain how to run programs written in abstract syntax:

` | initial`

| storage

v final

program tree +-------+--------+ storage

-------------------->| run | -------->

(AbstractSyntax.hs) +----------------+

## Representation of the storage

There are several ways to represent the storage:

As a list

`m :: [(Identifier,Integer)]`

describing a table associating integers to identifiers.- In this case, to find the value of an identifier
`i`

, we use the`lookup`

function from the prelude:

`lookup i m`

- To update the storage
`m`

means to define a new*list*`m'`

from the list`m`

. - Unused program variables are simply not listed in
`m`

.

- In this case, to find the value of an identifier
Again as a table but using hashing, or a tree or other efficient data structures.

As a function

`m :: Identifier -> Integer`

, again associating integers to identifiers.- In this case, to find the value of an identifier, we apply the function to the identifier.

`m i`

- To update the storage
`m`

means to define a new*function*`m'`

from the function`m`

. - Unused program variables are given the value
`undefined`

or`error`

.

**Here we adopt option 3:**

`type Storage = Identifier -> Integer`

### Empty storage

At the beginning, no storage location is initialized:

`emptyStorage :: Storage`

emptyStorage i = error ("Uninitialized variable " ++ i)

### Updating the storage

To update a variable named `i`

to the value `x`

in `m :: Storage`

means to produce a new `m' :: Storage`

with `m' i = x`

and `m' j = m j`

for `j`

distinct from `i`

:

`update :: Identifier -> Integer -> Storage -> Storage`

update i x m = m'

where

m' :: Storage

m' j | i == j = x

| otherwise = m j

## Booleans are represented as integers

We convert between numbers and booleans, so we only have the type of integers in our little language, like in the programming language `C`

:

`number :: Bool -> Integer`

number False = 0

number True = 1

boolean :: Integer -> Bool

boolean 0 = False

boolean _ = True

**Remark:**

Notice that the above two functions don't form an isomorphism. We only have the equation `boolean(number b) = b`

for all `b :: Bool`

, or `boolean . number = id`

where `id`

is the identity function defined in the prelude, but not the other way round. Technically, one says that the above two functions exhibit the type `Bool`

as a *retract* of the type `Integer`

, with the function `boolean`

the retraction and the function `number`

the section. Then the type `Bool`

is isomorphic to the set of fixed points of the function `number . boolean`

, namely `0`

and `1`

.
See also the section on retracts in the lecture on data types.

## Evaluating expressions

We aim to evaluate expressions relative to a given storage:

An expression is either

- a constant (an integer), or
- a variable, or
- an operator together with a list of sub-expressions.

To evaluate, relative to storage `m :: Storage`

,

- a
**constant**means simply to extract the integer from it. - a
**variable**, say,`"x"`

, simply means to look up the value, via`m "x"`

. - an
**operator**and its sub-expressions, means to apply a Haskell operation associated to the operator to the evaluated sub-expressions. This is done in the following Haskell code, assuming that we evaluate operators through the auxiliary function`opEval`

discussed below:

`eval :: Storage -> Expr -> Integer`

eval m (Constant x) = x

eval m (Var i) = m i

eval m (Op o es) = opEval o [eval m e | e <- es]

We look in detail at the last pattern, evaluating an operator `o`

with sub-expressions `es`

(a list of expressions, `[Expr]`

).

Given an `OpName`

(defined in the module AbstractSyntax) and the correct number of arguments (one or two here), we evaluate it:

`opEval :: OpName -> [Integer] -> Integer`

opEval Add [x, y] = x + y

opEval Sub [x, y] = x - y

opEval Mul [x, y] = x * y

opEval Div [x, y] = x `div` y

opEval Mod [x, y] = x `mod` y

opEval Eq [x, y] = number(x == y)

opEval Leq [x, y] = number(x <= y)

opEval Less [x, y] = number(x < y)

opEval Geq [x, y] = number(x >= y)

opEval Greater [x, y] = number(x > y)

opEval And [x, y] = number(boolean x && boolean y)

opEval Or [x, y] = number(boolean x || boolean y)

opEval Not [x] = number(not(boolean x))

opEval op xs = error ("Interpreter bug. "

++ "Please contact the software maintainer. "

++ "Tried to apply " ++ show op

++ " to " ++ show xs)

## Running programs

A video on this section can be found here

When we run a program we start with an initial storage and, if the program terminates, we get a final storage:

`run :: Program -> Storage -> Storage`

The assignment statement evaluates the expression `e`

and stores it in the identifier `i`

of the storage `m`

:

`run (i := e) m = update i (eval m e) m`

To run an if-else-statement, we evaluate the expression `e`

, and if its boolean value is true, we run the `then`

branch `p`

and otherwise we run the `else`

branch `q`

, with the given storage `m`

:

`run (IfElse e p q) m`

| boolean(eval m e) = run p m

| otherwise = run q m

Similarly, to run an if-statement, we evaluate the expression `e`

, and if its boolean value is true, we run the `then`

branch with the given storage `m`

, and otherwise we leave the given storage unchanged:

`run (If e p) m`

| boolean(eval m e) = run p m

| otherwise = m

To run a while-statement, we evaluate the condition `e`

. If it is false, we leave the given storage `m`

unchanged. If it is true, we run `p`

on the storage `m`

to get a new storage `m'`

, which we use to recursively run the while-statement, to get a storage `m''`

, which is the result, if this recursion terminates (it need not to):

`run (While e p) m`

| boolean(eval m e) = m''

| otherwise = m

where

m' = run p m

m'' = run (While e p) m'

To run a block consisting of `n`

program statements, starting from a storage `m_1`

, we apply the first statement to get `m_2`

, the second to get `m_3`

, and so on, until we apply the last statement to get the final storage `m_n`

. We express this recursively in the following definition, where the base case is when we have zero programs, in which no transformation to the storage takes place:

`run (Block []) m = m`

run (Block (p : ps)) m = m''

where

m' = run p m

m'' = run (Block ps) m'

## An alternative approach to running programs

This approach shows that imperative programming is functional programming.

Now we define an alternative variant of the function `run :: Program -> Storage -> Storage`

, using a different perspective.
Specifically, we think of a program as a **storage transformer**, i.e., a map `Storage -> Storage`

.
Every program construction corresponds to a function that returns a storage transformer, i.e., that returns a function `Storage -> Storage`

.

Firstly, the assignment statement is a storage transformer with two parameters `i`

and `e`

:

`assign :: Identifier -> Expr -> Storage -> Storage`

assign i e = \m -> update i (eval m e) m

Next, the if-else-statement takes three functions as arguments, and produces one function as the result. The first argument is a property `p`

of the storage. The second and third arguments are two storage transformers, and the result is a storage transformer.

`ifElse :: (Storage -> Bool) -> (Storage -> Storage) -> (Storage -> Storage) -> (Storage -> Storage)`

ifElse p f g = h

where

h m = if p m then f m else g m

Although we use `Storage`

for interpreting imperative programs, this function makes sense for any type `s`

:

`ifElse :: (s -> Bool) -> (s -> s) -> (s -> s) -> (s -> s)`

ifElse p f g = h

where

h m = if p m then f m else g m

Similarly, the functions below are defined with an arbitrary type `s`

rather than the specific type `Storage`

.

We don't need to consider an if-statement, because `ifElse p f id`

does the job, where `id`

is the identity function, defined in the prelude.

Next, the while-statement takes a property `p`

of states, and a storage transformer `f`

. The result is a storage transformer `g`

that repeatedly applies `f`

to a given storage `m`

until it fails to satisfy `p`

:

`while :: (s -> Bool) -> (s -> s) -> (s -> s)`

while p f = g

where

g m = if p m then g(f m) else m

The block-statement is simply the composition of finitely many functions: first apply the first function to the given storage, then the second function, etc., and finally the last function.
For example, `block [f,g,h] m = h(g(f m))`

:

`block :: [s -> s] -> s -> s`

block [] m = m

block (f:fs) m = block fs (f m)

Boolean expressions represent predicates of the storage:

`booleanValue :: Expr -> (Storage -> Bool)`

booleanValue e = \m -> boolean(eval m e)

Finally, with these definitions, the function `run`

defined above is equivalent to the following:

`run' :: Program -> Storage -> Storage`

run' (i := e) = assign i e

run' (IfElse e p q) = ifElse (booleanValue e) (run' p) (run' q)

run' (If e p) = ifElse (booleanValue e) (run' p) id

run' (While e p) = while (booleanValue e) (run' p)

run' (Block ps) = block (map run' ps)