UNIVERSITY OF LONDON

M.Sc.DEGREE IN SCIENCE IN COMPUTER SCIENCE 1994
M.Sc.DEGREE IN ENGINEERING IN INFORMATION TECHNOLOGY 1994
For Internal Students of University College London

UNIVERSITY COLLEGE LONDON

DIPLOMA IN INFORMATION TECHNOLOGY 1994

D16:  FUNCTIONAL PROGRAMMING

5 MAY 1994  :  10  to 12.30

Answer QUESTION 1 and any TWO others.

1.a)What is a recursive function? Give two examples of recursive functions 
    in SML which implement the equivalent of the C++ for-loop and the C++ 
    while loop.
                                                                    [6 Marks]

 (b) What is a curried function definition? How is currying being used in 
     the following program?

                 fun times x y = (x * y) : int

                  fun map f [] = []
 I                |   map f (front::rest) = (f front) :: map f rest

                      val main = map (times 3) [1,2,3,4]

                                                                    [8 Marks]

 (c) Explain the difference between a partial application and a partial 
     function.
                                                                    [6 Marks]
  
 (d) Explain, with examples, what is meant by a higher-order function. Your 
     examples should show how such a function might be applied. Illustrate 
     the behaviour of one of your functions by providing a hand-evaluation 
     of the example application.
                                                                    [5 Marks]
                                 
                                                             [Total 25 Marks]

 2. "SML frees the programmer from the mundane issue of how so that she 
    may concentrate on the important issue of what". Discuss this statement 
    with reference to the following:

    - The language features which provide abstraction and encapsulation in SML.
    
    - The distinction between declarative (functional) and imperative 
      (procedural) styles of prograrnming.
    - The significance of types and of the availability of type constructors 
      on programming style.
    
                                                                   [Total 25]

3.  Design and implement a program which solves the following problem.  
    Marks will be given for clearly constructed code, modularity, 
    commenting, and good functional style.
    Minor errors in SML syntax will not be penalised.

    You are given a data structure which is a list of single-character 
    strings. The data is text with embedded comments. The start of a 
    comment is given by the two characters "(" and "*". The end of a 
    comment is given by the two characters "*" and ")". Write a
    function which will take this data structure as input and will
    return the data with the comments deleted. If you use mutual recursion, 
    explain why this is a bad idea.
                                                                  [Total  25]

4.a)  What is a recursive type?
                                                                  [2 Marks]
    
 (b)  Provide an SML data structure wwch wiU hold integers in a sorted tree.
                                                                  [3 Marks]

 (c)  Provide a function to insert a new integer into the above tree, in the 
      correct position such that the tree remains sorted.
                                                                  [6 Marks]

 (d)  Provide a function to test whether a given integer exists in the 
      above tree.
                                                                  [4 Marks]

 (e)  Provide a function which works on the above tree in the same way 
      that the function map works on a list.
                                                                  [4 Marks]

 (f)  Provide a function which will delete a given integer from the above tree.
                                                                  [6 Marks]

                                                                  [Total 25]

5.a) What is the most general type of each of the following functions:

                     fun guesswhat i j k
                         = let
                             fun m n = if (i j) then k else n
                           in
                                 m j
                           end

                    fun mysterious nil y z
                         = 42.0 + z
    I               |    mysterious   (front::rest) y z
                         = mysterious rest y ((front 0 y) z)
                                                                  [8 Marks]
 (b)  Consider the following definitions:

      fun times1 (x,y) = (x * y) :int
 
      fun times2 x y = (x * y) :int

      fun repeats 0 f x = x
      |   repeats n f x = repeats (n-1) f (f x)

      Use the functions repeats and times2 to define a new function called 
      power, which takes two numbers n and x and retums the nth power of x.

      Why is it not possible to do the same thing with times1 ?
                                                                  [5 Marks]
   
 (c)  Given the following definitions:

  fun S f g x = f x (g x)


  fun B f g x = f (g x)


  fun W h x = h x x


  val E = S (B W B) (B W B)

  Explain why the last definition (for E) would produce a type error.

  Notwithstanding the type error, provide a hand evaluation of the 
  application of E to a value x. You should continue far enough to 
  recognize a recurrent pattem and by reverse substitution you should 
  show that (E x) = x (E x).

  Hint:from the above definitions, simple substitution gives
  (B W B) x y = W (B x) y
                                                                  [12 Marks]
  
                                                                  [Total 25]
     
                               [END  OF  PAPER]