;;; Sample solutions for MP10 Tasks 3, 4, and 5


Task 3.
=======

    define length = proc (list)
                      if null?(list)
                         then 0
                         else +(1,(length cdr(list)))

(The call to length was omitted in the original sample
solution.  This bug was pointed out by Priyadarshan Vyas.)


Task 4.
=======

Although there are many notations generated by the grammar
that describe a type of the null expression, no one notation
describes the type of the null expression.  For example, the
following program would not be well-typed using the types
generated by that grammar:

    cons(cons(1,null),
         null)

The problem above is that the first occurrence of null would
have to have type list[int], but the second occurrence would
have to have type list[list[int]].

Although there are many notations generated by the grammar
that describe a type of the cons operator, no one notation
describes the type of the cons operator.  For example, the
above program would not be well-typed using any type for
cons that is generated by the grammar.

Although there are many notations generated by the grammar
that describe a type of the length procedure defined in
Task 3, no one notation describes the type of that procedure.
    

Task 5.
=======

The problems identified in Task 4 would be solved by adding
type variables and universal types to the grammar, e.g.

    sigma  ::=  tau
           ::=  forall beta sigma
    tau  ::=  int
         ::=  bool
         ::=  list[tau]
         ::=  ( -> tau)
         ::=  ( alpha -> tau )
         ::=  beta
    alpha  ::=  tau
           ::=  tau * alpha
    beta  ::=  tvar1  |  tvar2  |  tvar3  |  ...

(That last production should be regarded as an abbreviation
for productions that generate an infinite set of type
variables.)