- 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 listHere'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 [] endWhich of these two definitions is more efficient? Why?
- 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 -> 'bStudying 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 : intShow 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
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 * arithExpNote 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 : arithValueEvaluating 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.