CMSC22300
Homework 1
Due Wednesday, April 7, 2010

1.[10] (a) Discuss how the selector operation #1 differs from 
the function
    
    fun fst (x,y) = x

(b) Discuss how the selector #a differs from the function

    fun geta {a} = a

[NOTE: This question depends on discussion of record types in class
on Monday, or in various tutorials. The definition above is
equivalent to:

    fun geta {a=x} = x
]


2. [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?


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.]


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

(b) Collectively, what kind of data structure do a, f, g
implement? (I.e. what do they "do"?)

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


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


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.


------------------
Bonus Question [10]: A long time ago, Doug McIlroy asked me how
to implement a particular operation in ML, and I came up 
with the following little program:

    fun conv0(nil,ys) = (nil,ys)
      | conv0(x::xs,ys) = 
	 let val (r,y'::ys') = conv0(xs,ys)
	  in ((x,y')::r, ys')
	 end;

    fun conv(xs,ys) = #1(conv0(xs,ys));

    fun convs0(nil,ys) = (nil,ys)
      | convs0(x::xs,ys) = 
	 let val (r,y'::ys') = convs0(xs,ys)
	     val new = (x,y')
	  in ([new]::map (fn z => new::z) r, ys')
	 end;

    fun convs(xs,ys) = #1(convs0(xs,ys));


But I can't remember what the original question was.
So, what does this program do? 
[Try the hard way first -- read and try to understand
the code.  The easy way is to perform experiments
evaluating the functions on representative arguments
and guess the functionality imperically.]