COP 4555 - Homework 4

Due Monday, March 28.

Here is a function that 'flattens' a list of lists:

  - fun flatten1 []      = []
      | flatten1 (x::xs) = x @ flatten1 xs;
  val flatten1 = fn : 'a list list -> 'a list
  - flatten1 [[1,2],[],[3],[4,5,6]];
  val it = [1,2,3,4,5,6] : int list

Here's another way to define the same function:

  fun flatten2 xs =
    let fun flat_aux []      acc = acc
          | flat_aux (y::ys) acc = flat_aux ys (acc @ y)
    in
      flat_aux xs []
    end

Which of these two definitions is more efficient? Why?

SML provides a function called foldr that is quite handy for list processing. It can be defined as follows:

  - fun foldr f e []      = e
      | foldr f e (x::xs) = f (x, foldr f e xs);
  val foldr = fn : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b

Studying this definition, we can see that foldr f e [x1,x2,x3,...,xn] computes

  f(x1,f(x2,f(x3,...f(xn,e)...)))

As an example, we can add up all the elements of a list quite easily using foldr:

  - foldr op+ 0 [1,2,3,4,5];
  val it = 15 : int

Show that we can use foldr to define append in one line, without any need for recursion:

  - fun append(xs,ys) = foldr ? ? ?;
  val append = fn : 'a list * 'a list -> 'a list
  - append([1,2,3],[4,5]);
  val it = [1,2,3,4,5] : int list

Interpreter 0 In this problem, you will write an ML program which evaluates simple arithmetic expressions. Our expression language is very simple. It involves expressions written in the language given by the following simple BNF grammar:
```
  e ::= n | ~e | e + e | e - e | e * e | e / e | (e)
```
In the above, n is an integer literal, ~e is the negation of e, the next four terms are the sum, difference, product, and quotient of expressions, and (e) is used to control the order of evaluation of expressions (e.g. 3 *(5 - 1)).
Rather than working directly with the concrete syntax above, we will imagine that we have a parser which parses input into an abstract syntax tree, which your interpreter should use. Abstract syntax trees are just a convenient method of expressing parsed expressions; the definition of the ML datatype is
```
  datatype arithExp =
      AST_NUM of int
    | AST_NEG of arithExp
    | AST_PLUS of arithExp * arithExp
    | AST_MINUS of arithExp * arithExp
    | AST_PRODUCT of arithExp * arithExp
    | AST_QUOTIENT of arithExp * arithExp
```
Note how this definition mirrors the BNF grammar given above; for instance, the constructor AST_NUM makes an integer into an arithExp, and the constructor AST_PLUS makes a pair of arithExp's into an arithExp representing their sum. Interpreting abstract syntax trees is much easier than trying to interpret concrete syntax directly.
Note that we no longer need parentheses to group terms, as the example given above would simply be represented by
```
  AST_PRODUCT(AST_NUM 3, AST_MINUS(AST_NUM 5, AST_NUM 1))
```
which represents the parse tree which looks like

You are to write an ML function evaluate that takes an abstract syntax tree representing an arithExp and returns the result of evaluating it. Most of the time when you evaluate the tree, you will get an integer, but if evaluating the expression results in a division by zero, it should return an error message. To allow both of these to be returned, we define
```
  datatype arithValue = NUM of int | ERROR;
```
Thus you will define evaluate: arithExp -> arithValue where, as usual, a parse tree whose root is a binary operator is evaluated by evaluating the left and right subtrees and then performing the appropriate operation on the results. For example,
```
  - evaluate (AST_PRODUCT(AST_NUM 3, AST_MINUS(AST_NUM 5, AST_NUM 1)));
  val it = NUM 12 : arithValue
```
Evaluating AST_NUM expressions should be trivial, and AST_NEG's aren't much harder. Notice that if any subtree evaluates to ERROR, then the whole tree should evaluate to ERROR.
To get you started, here is the beginning of the definition of evaluate:
```
  fun evaluate (AST_NUM n) = NUM n
    | evaluate (AST_NEG e) = ...
```
Also, you will probably find it useful to make use of ML's case expression.

Back to

smithg@cs.fiu.edu