UNIVERSITY COLLEGE LONDON University of London EXAMINATION FOR INTERNAL STUDENTS For the following qualifications B. A. , B. Sc. COURSE CODE : COMEP B11A TITLE OF EXAMINATION CompSci B11A: Introductory Progranmiing I -- RESIT PAPER UNIT VALUE : 0.50 DATE : 05-A4AY-95 TIME : 14.30 TIME ALLOWED : 2 hours 30 minutes Answer Question 1 and Question 2 and any TWO other questions. The use of Electronic Calculators is NOT permitted. You may find the following definitions useful throughout this paper: id x = x const x y = x converse f x y = f y x length [] = 0 length (front : rest) = 1 + (length rest) append a [] =a append [] b =b append (front rest) b = front : (append rest b) foldr f def [] = def foldr f def (front : rest) = f front (foldr f def rest) foldl f acc [] = acc foldl f acc (front : rest) = foldl f (f acc front) rest filter pred [] = [] filter pred (front : rest) front : filter pred xs, if pred front = filter pred xs, otherwise 1.This first question is designed to test your practical programming skill; it will be marked separately from the rest of the exam paper and will be counted as the practical contponent (i.e. in place of your coursework) for Blla. You should not spend more than one hour answering this question. 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. Write a Miranda program to play this game with a user. Your program should use an abstype to represent the board and the legal operations on the board. Hint: The implementation of the abstype can represent the board as a 7 x 7 square and 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 (because in reality the board is not a square - it is a cross shape as shown on the previous page). The underlying implementation of the abstype should use an algebraic type with three alternatives to represent the three possible states of a position in the square: (i) an invalid position, (ii) an empty hole and (iii) a hole filled with a peg. The movements should 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". Your abstype should provide at least the following operations: - init board, which returns a board whose elements have been set to the correct initial values. - show board, which takes a parameter which is a board and returns a printable representation. - 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. - setpeg which puts a peg into a given hole. You should pay particular attention to the types of all functions, and provide appropriate comments. Your program will be marked for correctness, clarity, style, robustness and documentation. [Marked separately] 2.a) What is a recursive function? Give example function definitions in Miranda for both a stack recursive function and an accumulative recursive function. For each function, provide an example application and give a hand evaluation of that application. [7 Marks] (b) What is a recursive type? Give an example of a built-in recursive type in Miranda. How can you define your own recursive type? Give an example in Miranda of a user-defined type which is recursive. [5 Marks] (c) Evaluate each of the following Miranda expressions. If you think that an expression gives an error, say why (if there is more than one error in an expression, explain all of them): [ [ ] ] : [ [ [ ] ] ] [ [ [ ] ] ] : [ [ ] ] [] : [] : [] ((3-3)=O) & ((23 / 0) = 0) ((3-3)=O) \/ ((23 / 0) = 0) exp1 where exp1 = 25, if (3 < 5 < 27) = False, otherwise exp2 5 where exp2 = 3, if True = 5, otherwise exp3 5 where exp3 = id, if False = const 3, otherwise [11 Marks] (d) Explain, with examples, what is meant by the following terms: higher-order function currying partial application Explain how the above terms are related. [10 Marks] [Total 33 Marks] SECTION A 3.Here are three versions of a function which takes a list of items and produces a list with the same items in reverse order: || auxiliary functions: rcons a f b = f (a : b) || three versions of reverse: rev1 [] = [] rev1 (front : rest) = append (rev1 rest) [front] rev2 items = foldr rcons id items [] rev3 = foldl (converse (:)) [] Give the type definitions for rev1, rev2 and rev3 (use polymorphic types where appropriate to give the most general type). Provide hand evaluations for the following three applications: (rev1 [1,2,3,4]) (rev2 [1,2,3,4]) (rev3 [1,2,3,4]) Which of the three versions is the slowest (i.e. takes the most evaluation steps)? In terms of the length n of an arbitrary input list, how many evaluation steps are required for each version? Explain why the slowest version takes so many evaluation steps. [Total 33] 4."Pointers and assignment are not necessary in a high-level language". Discuss this statement with reference to the following: - Proving properties of programs. - Modularity and encapsulation. - Performance. [Total 33] 5. A double-ended queue is similar to a list, except that it is possible to take the head or the tail of either end. For example, the function hdL will return the leftmost element whereas hdR will return the rightmost element. Provide an abstype for a double-ended queue, including definitions (with types) for the following functions: hdL (which gives the leftmost element) hdR (which gives the rightmost element) tlL (which gives the list minus the leftmost element) tlR (which gives the list minus the rightmost element) consL(which puts an element on the left end) consR(which puts an element on the right end) nildeq (this value is the empty double-ended queue) isemptydeq (this tests whether its argument is nildeq) Write a function called insertdeq which accepts two parameters: a double-ended queue of integers and an integer. The function should insert the integer into the double-ended queue so that negative numbers are on the left (in ascending order towards the centre) and positive numbers are on the right (in ascending order towards the centre). In the centre of the double-ended queue there should always be a zero. Your function should ignore insertions of the integer zero unless the queue is empty. Thus, the double-ended queue should look something like this: [-32,-20,-3,0,29,3,2,1] Hint: write your function using the abstype interface functions given above. insertdeq is not an interface function and therefore should not know how a double-ended queue is implemented. [Total 33] 6.a)What is the type of the following expression and what does it do? (foldr (+) 0) . (foldr ((:) . (length . (converse (:) [] ))) [] ) [8] (b)The following function 'foldiftrue' reduces only those elements of a list which satisfy a given predicate: foldiftrue pred ff def [] = def foldiftrue pred ff def (front : rest) = ff front (foldiftrue pred ff def rest), if (pred front) = foldiftrue pred ff def rest, otherwise Give the type definition for foldiftrue (use polymorphic types where appropriate to give the most general type). Rewrite foldiftrue in terms of foldr and filter [13] (c)What is the most general type of each of the following functions: lotsoffun a b f x = ((a f) . (b f)) x morefun [] j acc = acc morefun f [] acc = acc morefun (x : xs) (y : ys) acc = morefun xs ys (x y acc) mysterious [] y z = 42.0 + z mysterious (front : rest) y z = mysterious rest y ((front . y) z) [12] [Total 33] SECTION B These questions are primarily of interest to Psychology/Cognitive Science and Linguistics/Cognitive Science students. 7. (a) Explain the function of a parser. Explain the difference between the lexical analysis phase and the syntactic analysis phase. [6] (b) Why are algebraic data types appropiate for constructing the representation of parse-trees? [5] (c) Explain why the following type definition is flawed: > expression ::= Phrasetype1 word expression > | Phrasetype2 expression word expression > word == [char] [7] (d) Why is the following type not flawed? > expression ::= Phrasetype1 word [expression] > | Phrasetype2 expression word expression [7] (e) Explain the role of the algebraic data type which includes the elements Succeed-with and Fail, in the construction of parsers using the parser kit. Give an example of a situation in which a function should return Fail during an attempt to parse an input. [8] [Total 33] 8. Consider the following (BNF) grammar: expression ::= people at location | people with object people ::= person | person and people person ::= Darmuk | Jelad | Picard | Egruk | Spock location ::= Tanagra | Niagara object ::= eyes open | knife extended | hands empty Given the following Miranda data type definitions, and assuming that the input is already lexed into a list of words (which include the "compound words" such as ""eyes-open"), define a parser for expressions of this grammar. > expression ::= At people location > | With people object > | Person name > | People people > | Location name > | Object word > location == expression > object == expression > people == [person] > person == expression > name == [char] > word == [char] You may assume the use of the following functions: - then, else in parser combination; - combine_into for parse-tree construction; - look_for to treat terminals; - literally for identifying literal tokens in the input; - Succeed_with, Fail and member. [Total 33] 9. Consider the following grammar: expression ::= expression blob | blip (a)Explain why the following parser will not successfully parse these expressions: > expression ::= Sequence [expression] > | Blip word | Blob word > word == [char] > sentence = (combine_into a_sequence (sentence $then blob)) > $else blip > blob = look_for a_blob Blob > blip = look_for a_blip Blip > a_blob x = x = "Blob" > a_blip x = x = "Blip" > a_sequence [exp,Sequence exps] = Succeed_with > (Sequence (exp:exps)) > a_sequence [exp1,exp2] = Succeed_with (Sequence [expl,exp2]) [8] (b) Explain why the following modification will produce a behaviour in which the input ["Blip","Blob"] successfully produces a correct parse-tree, but the parser fails to terminate in its search for alternative parse-trees for this same expression. Indicate what the parse-tree the parser returns for this input will be. > sentence = blip $else > (combine_into a_sequence (sentence $then blob)) [14] (c) Propose a different grammar which expresses the same collection of expressions, but for which a parser can be built which both correctly parses the expressions and terminates. Construct a parser for your new grammar. [Total 33] [END OF PAPER]