UNIVERSITY OF LONDON M.Sc. DEGREE IN SCIENCE IN COMPUTER SCIENCE 1993 M.Sc. DEGREE IN ENGINEERING INFORMATION TECHNOLOGY 1993 For Internal Students of University College London UNIVERSITY COLLEGE LONDON DIPLOMA IN INFORMATION TECHNOLOGY 1993 D16 : FUNCTIONAL PROGRAMMING D16R: FUNCTIONAL PROGRAMMING - RESIT PAPER 3 JUNE 1993 : 2.30 to 5 Answer QUESTION ONE and TWO other questions. 1.a) Explain, with examples, what is meant by the following terms: partial application partial function higher-order function [6 marks] (b)Evaluate the following SML expressions and give their types: [] :: [] :: [] [1] :: [ [1] ,[2] ] :: [] [] @ [1] @ [] "a" ^ "b" :: ["1"] (op @) ( [1] , 1 :: [] ) [6 marks] (c) Explain briefly the terms case analysis and structural induction and use them to design a prefix curried version of the built-in SML append operator @. [8 marks] (d) Given the following function definition: fun reduce f def nil = def | reduce f def (front :: rest) = f front (reduce f def rest) Write your own version of the SML built-in function map, using reduce and any other functions that you think are necessary. [5 marks] [Total 25] 2.(a) Given the following datatype definition for positive numbers, write a function called 'plus' which will add two such numbers and a function called 'times' which will multiply together two such numbers: datatype POS = Zero | Succ of POS [7 marks] (b) Given the following function definitions which represent the first four positive integers as functions, and assuming similar definitions for every positive integer,write a function (with its source and target types) called 'plus' which will add two such integers: fun one f x = f x fun two f x = f (f X) fun three f x = f (f (f x)) fun four f x = f (f (f (f x))) [8 marks] (c) Given the following two definitions 'fnil' and 'fcons' which represent the empty list and the list constructor as functions using an 'untyped' version of SML, write appropriate 'untyped' functions 'fhd' and 'ftl' inspect the head and tail of a list constructed in this way. You may make use of the combinators K and c, also defined below: fun K x y = x fun C f x y = f y x exception Fnil fun fnil () = let fun result f = raise Fnil in result end fun fcons a b = let fun result f = f a b in result end [10 marks] [Total 25] 3.Discuss the possibility and desirability of programming in a functional style using an imperative programming language such as C++. You should include in your answer a discussion of the use of variables, loops and conditional evaluation, pattern matching, higher-order functions and mechanisms for abstraction, together with any other features which you think are important. [Total 25] 4.The game of solitaire is played on a board with holes and pegs.The holes have the following formation: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 The game starts with pegs in all holes except the central hole. During the game, a peg may jump another peg by moving North, South, East or West (but not diagonally).A peg may only jump another peg if there is an empty hole on the other side of the peg being jumped over. The peg which has been jumped over is removed from the board.The aim of the game is to use a succession of jumps to remove all the pegs from the board except one, which must end up in the central hole. This game may be approximated by an SML program which uses an abstype to represent the board: the imnplementation of the abstype will allow a hole to be referenced by two indices each ranging from 1 to 7, but some positions will be invalid for the purposes of the game. The movements may be described by two integers to specify a starting peg and a string parameter which takes one of the values "N", "S", "E" or "W". On the following page you are given the top-level functions (deliberately un-commented)for this game. You should provide an appropriate abstype called 'Board' to represent the board and the following operations upon the board: 'init_board' , which returns a BOARD whose elements have been set to the correct initial values, 'show_board' , which takes a parameter of type 'Board' and returns a printable representation of type (int list) list , 'okpeg' , which determines whether a peg exists at a given position, 'okmove' , which determines whether the proposed move is legal, 'delpeg' , which removes a peg from a given hole, and 'setpeg' , which puts a peg into a given hole. You should pay particular attention to the types of all functions (you should always include type specifications) and provide appropriate comments.Minor errors in SML will not be penalised. exception Xdo-Move exception Domove local fun jump (xl,yl) (x2,y2) (x3,y3) bd =( (setpeg xl yl) o (delpeg x2 y2) o (delpeg x3 y3) bd) fun xdo_move (x,y,"N") bd = jump (x,y-2) (x,y-1) (x,y) bd | xdo_move (x,y,"S") bd = jump (x,y+2) (x,y+l) (x,y) bd | xdo_move (x,y,"E") bd = jump (x+2,y) (x+l,y) (x,y) bd | xdo_move (x,y,"W") bd = jump (x-2,y) (x-l,y) (x,y) bd | xdo_move (x,y,_) bd = raise Xdo_move in fun do_move (x,y,ch) bd = if ((okpeg (x,y,ch) bd) andalso (okmove (x,y,ch)bd) then xdo-move (x,y,ch) bd else raise Domove end fun xgame bd nil = show-board bd | xgame bd (move :: rest) = xgame (do_move move bd) rest fun game moves = xgame init_board moves [Total 25] 5.a)What is meant by the terms 'applicative order' and 'normal order' evaluation? What are the advantages and disadvantages of each? [10 marks] (b)Why is it not possible for an SML programmer to write a function which exactly mimics the built-in conditional operator? [5 marks] (c)What is a 'combinator' and why are combinators important? Give the definitions of two combinators which form a computationally complete set, and show how they may be used to mimic the action of the Identity combinator given below: fun I x = x [10 marks] [Total 25] [END OF PAPER]