CMSC 22300, Spring 2012
Homework 1
Due 11:00pm, Wednesday, April 4, 2012

The following homework consists of two short answer written
exercises and three programming exercises.  The answers to (1) and
(2) should be provided in a plain text file sol1.txt.
The code for the programming exercises (3), (4), and (5) should
be provided in a file sol1.sml in your phoenixforge repository,
in the directory homework1.


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?


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?  (First try to work them out
yourself before entering them in sml interactive system, which
will infer their types for you.)

(b) Collectively, what kind of data structure do a, f, g
implement? (I.e. what do they "do"?)  Run some experiments to
see how they behave (e.g using ints and int lists).

(c) What happens when you evaluate "g a"?  What should happen?


3. [20] The old (pre-decimalization) British currency, 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 the three components represent the numbers of pounds, shillings,
and pence, respectively.  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),
(5, 0, 12), and (2, 24, 0) would be "illegal" values.

Define three functions

   compare: sterling * sterling -> order
   add : sterling * sterling -> sterling
   subt : sterling * sterling -> sterling option

compare(x,y) should return GREATER, EQUAL, or LESS 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) = GREATER or EQUAL.

In each case, the functions can assume that their argument
values are "legal".

[GREATER, EQUAL, and LESS are data constructors for the predefined type order,
which is defined in the General module of the Basis library. Various
types (like int) have a binary compare function that returns a value
of type order.]


4. [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.)

Test your calculator by evaluating:

    val result = calc([PUSH 2, PUSH 3, PUSH 4, ADD, MUL], [])


5. [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 4. Your compiler
should take the form of a function compile of the type.

    val compile: expr -> program

Then test by compiling and evaluating the following expression:

    val e1 = TIMES(MINUS(NUM 5, NUM 2), PLUS(NUM 3, NUM 4))

    val result = calc(compile e1, [])