CMSC22300 Homework 1 Solution 1. [10] Here is a definition of a "conditional" function: fun cond(true, x, y) = x | cond(false, x, y) = y and here is a definition of factorial using cond: fun fact n = cond(n=0, 1, n*fact(n-1)); What happens when you compute "fact 3", and why? ---------------------------------------------------------------------- Ans: The computation of fact 3 will not terminate, because the cond function is strict and when it is evaluated in the body of fact it will have to first evaluate all its arguments, including the expression "n*fact(n-1)", which requires fact to be recursively evaluated, and so on. We are forced to recurse infinitely trying to evaluate the third argument of cond before we can ever test the result of n=0. 2. [15] Here are three declarations: val a = ([],[]) fun f (x, (u,v)) = (u, x::v) fun g (x::u,v) = (x, (u,v)) | g ([], v) = g(rev v, []) (a) What are the types of a, f, and g? (Try to work them out without entering them into the sml interactive system, which will infer their types for you. ------------ Ans: a : 'a list * 'b list f : 'a * ('b * 'a list) -> ('b * 'a list) g : 'a list * 'a list -> 'a * ('a list * 'a list) (b) Collectively, what kind of data structure do a, f, g implement? (I.e. what do they "do"?) ____________ Ans: They implement a FIFO queue datastructure. a represents an empty queue, f represents an "enqueue" operation, which adds an element at the front of the queue, and g represents a "dequeue" operation, which removes an element from the back of the queue, returning the removed element together with the modified queue. This is an example of a "functional data structure". (c) What happens when you evaluate "g a"? What should happen? ------------ Ans: The expression g a attempts to remove an element from the empty queue. We will have g a = g ([],[]) ==> g ([],[]) ==> g ([],[]) ==> ... so the computation will never terminate. There should be a test for this case, and the attempt to remove an element from the empty queue should either raise an exception, or g should be modified to return an option: (1) exception exception EMPTY_QUEUE fun g ([],[]) = raise EMPTY_QUEUE | g ([], v) = g(rev v, []) (* v known to be nonempty *) | g (x::u,v) = (x, (u,v)) (2) option return fun g ([],[]) = NONE | g ([], v) = g(rev v, []) (* v known to be nonempty *) | g (x::u,v) = SOME (x, (u,v)) 3. [20] The old British currency (pre-decimalization), had pence, shillings, and pounds (l.s.d.), with 12 pence to the shilling, 20 shillings to the pound. We can represent a monetary value by the following type: type sterling = int * int * int where we want to maintain the invariant that the three components are non-negative, the third component is between 0 and 11, and the second component is between 0 and 19. Thus (5, ~4, 2) and (5, 0, 12) would be "illegal" values. Define functions compare: sterling * sterling -> order add : sterling * sterling -> sterling subt : sterling * sterling -> sterling option compare(x,y) should return GT, EQ, or LT according to whether x is greater, equal, or less than y as a monetary value. The other functions add and substract sterling values while maintaining the specified invariants. The subt function should return NONE in the case that the second argument is "larger". I.e. in pseudocode, subt(x, y) = SOME(x - y) if compare(x,y) = GT or EQ. In each case, the functions can assume that their argument values are "legal". [The type order is defined in the General module of the Basis library.] ---------------------------------------------------------------------- Ans: -------------------- (* a type for computing with old British currency of pounds, shillings and pence *) (* pound (l) = 20 shillings (s) shilling (s) = 12 pence (p) *) type sterling = int * int * int (* pounds, shillings, pence *) fun compare ((l1, s1, p1), (l2, s2, p2)) = case Int.compare (l1,l2) of LESS => LESS | GREATER => GREATER | EQUAL => (case Int.compare (s1,s2) of LESS => LESS | GREATER => GREATER | EQUAL => Int.compare (p1,p2)) (* the case expressions could be somewhat simplified using OR patterns, for instance, the first case could be rephrased as case Int.compare (l1,l2) of ord as (LESS | GREATER) => ord | EQUAL => ... *) fun add ((l1, s1, p1), (l2, s2, p2)) = let val p = p1 + p2 val p3 = p mod 12 val s = s1 + s2 + (p div 12) val s3 = s mod 20 in (l1 + l2 + (s div 20), s3, p3) end fun subt (d1 as (l1, s1, p1), d2 as (l2, s2, p2)) = case compare(d1,d2) of LESS => NONE | EQUAL => SOME (0,0,0) | GREATER => let val p = p1 - p2 val (p3,s) = if p < 0 then (p+12, s1-s2-1) else (p, s1-s2) val (s3,l3) = if s < 0 then (s+20, l1-l2-1) else (s,l1-l2) in SOME (l3,s3,p3) end -------------------- 5. [20] A simple calculator. Some calculators (particularly some HP models) use a language called rpn, for "reverse Polish notation". Here is a small rpn calculator language (for integers). datatype instruction = PUSH of int (* push an integer on the stack *) | ADD (* add the top two elements of the stack *) | SUB (* substract the top element from the second element *) | MUL (* multiply the top two elements of the stack *) The instructions of this language operate on a stack (i.e. list) of integers. A program is a list of instructions. type stack = int list type program = instruction list Implement the calculator as a function of the following type: val calc : program * stack -> stack (Normally you would expect the initial stack to be empty, and the final stack returned by calc to have a single element, the answer.) ----------------- Ans: datatype instruction = PUSH of int (* push an integer on the stack *) | ADD (* add the top two elements of the stack *) | SUB (* substract the top element from the second element *) | MUL (* multiply the top two elements of the stack *) type stack = int list type program = instruction list exception TOO_FEW_ARGS (* val calc : program * stack -> stack *) fun calc ([],s) = s | calc (PUSH n :: rest, s) = calc(rest, n::s) | calc (ADD :: rest, m::n::s) = calc(rest, (m+n)::s) | calc (SUB :: rest, m::n::s) = calc(rest, (m-n)::s) | calc (MUL :: rest, m::n::s) = calc(rest, (m*n)::s) | calc _ = raise TOO_FEW_ARGS 6. [20] A simple compiler. Here is a datatype defining the abstract syntax of a simple fragment of arithmetic. datatype expr = NUM of int (* integer constants *) | PLUS of expr * expr | MINUS of expr * expr | TIMES of expr * expr write a "compiler" in the form of a function that translates a member of expr to a program from Problem 5. ------------- Ans: datatype expr = NUM of int (* integer constants *) | PLUS of expr * expr | MINUS of expr * expr | TIMES of expr * expr (* comp : exp * program -> program *) fun comp(NUM n, p) = PUSH n :: p | comp(PLUS(e1,e2), p) = comp(e2, comp(e1,ADD::p)) | comp(MINUS(e1,e2), p) = comp(e2, comp(e1,SUB::p)) | comp(TIMES(e1,e2), p) = comp(e2, comp(e1,MUL::p)) (* val compile : expr -> program *) fun compile(e) = comp(e,[]) ------------------