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