CSC412  Functional Programming Practical (30%)  semester 1  1994

Submit a single text file containing your solution to each exercise,
FP1 and FP2, and submit two text files for FP3, using the Unix  `submit'
command  (*** give the unit as csc4000 ***)  by the appropriate deadline.
All solutions will be marked at demonstrations of 20-30 minutes
at times to be arranged.

You will be marked on the programs and *** your understanding *** of
lambda calculus, functional programming, LML and polymorphic type systems.

-------------------------------------------------------------------------------

FP1: Use the toy lambda-calculus interpreter FP:
(by end of week 4  25/3/94)

     a) examine the programs that implement `+ints' and `bool' values and
        operations,  const.int.fp and const.bool.fp,  "from first principles"
        ie. not as predefined constants.
        Try to improve them and add more operations.
        eg. define multiplication and maybe negative ints & full minus.

     b) Define   head, tl, cons, isnull  "from first principles" in a similar
        style to +int and bool above,
        ie. not using the built-in operators  hd, tl, ::, null.
        Write some simple expressions to demonstrate their use.

-------------------------------------------------------------------------------

FP2: Write LML programs to do the following:
(by end of week 7  22/4/94)

     a) Generate all Thue sequences of length n.
        These are sequences over the alphabet {1, 2, 3} s.t. no
        substring is immediately repeated   eg. 1 2 1 3 2 1 2 3
        but not 1 2 1 3 2 1 3 as (2 1 3) is immediately repeated.
        Be efficient  ie. do not generate all sequences and delete
        invalid ones!
        Provide a written explanation through the program as comments.

     b) Generate all sequences of n matched parentheses
        eg. n = 3  -->  ((()))  (()())  (())()  ()(())  ()()()
        The order of generation does not matter.
        Be efficient  ie. do not generate all sequences over {(, )} and
        delete invalid ones.
        Provide a written explanation through the program as comments.

-------------------------------------------------------------------------------

The next two are closely related and have the same deadline:
(by end of week 11  20/5/94).
They will be brought together by  `interp.cont.m'.
see /u/staff/lloyd/FP/LML/semantics/...

FP3:  This is in 2 parts, complete the first before doing the second!

(i)   Extend the denotational semantics parser   `syntax.cont.m'
      to allow the following syntax for procedure declarations and calls:

         dec ::= proc procid(paramid) = cmd | ... other decs as before ...
         cmd ::= procid(exp) | ... other cmds as before ..,

(ii)  Extend the denotational semantics "interpreter"   `sem.m'
      to give meaning to these new syntactic forms.
      Parameters are passed by-value.
      Allow recursive procedure calls and allow proc B to call proc A
      provided that A's heading has been encountered, ie. B occurs
      after A or within the body of A.

-------------------------------------------------------------------------------