Suggested Answers to Midterm1

1a)  ( 'a * 'b) -> 'c -> 'a -> 'b -> 'c

1b)   (int * int) -> (int * int)

1c)  int -> int -> int

2)   fn / x / => / if / ( x / >= / 0 / ) / then / true / else / false / ;

3)  Grammar:

S -> ab | aSb

Derivation (not required) and trees (required):

S -> ab

    S 
   / \
  a   b

S -> aSb -> aaSbb -> aaaSbbb

           S
         / | \
        a  S  b
         / | \
        a  S  b
          / \
         a   b

4) structure Queue :>  struct

datatype queue = 'a list

val empty = [];

fun first empty = raise NULLQ |
     first (X::empty) = X |
     first (X::Q) = first(Q);

fun remove empty = empty |
     remove (X::empty) = empty |
     remove (X::Q) = X::(remove Q);

fun insert(empty,X) = X::empty |
     insert(A::Q,X) = A::(insert(Q,X));
end

5)  Compound -> begin Stmtlist end
    Stmtlist -> Stmt |
                Stmt Stmtlist
    Stmt -> Var = Var Op Var
    Op -> and |
          or |
          xor |
          impl

6) fun f (a,b) = f a b;

7) Referential transparency is the idea that the meaning of the code is
only dependent on its syntactic context, not the state of the surrounding
computation.  Simply put, it means that the there are no side-effects to
consider.
This makes it far easier to determine the meaning of programs and to reason
about them.  It is particularly useful in languages that support features
(like ADTs) that allow various implementations to be swapped in and out,
but is helpful in the general case.

8) Here are two different left-most derivations of the same sentence:

S -> B -> B op B -> id op B -> x op B -> x op B op B -> x op id op B ->
x op y op B -> x op y op id -> x op y op z

S -> B -> B op B -> B op B op B -> id op B op B -> x op B op B -> x op id
op B -> x op y op B -> x op y op id -> x op y op z

9) "in my bag."