University College London
Cover Sheet for Examination Paper to be sat in May 2010
COMPGC16: Functional Programming
Time allowed 2.5 hours
Copyright By PowCoder代写 加微信 powcoder
Calculators are allowed Answer THREE questions
Checked by First Examiner: Date: Approved by External Examiner: Date:
COMPGC16: Functional Programming, 2010
Answer any THREE questions
Marks for each part of each question are indicated in square brackets. Calculators are permitted
1. (a) What is a Higher Order Function? Give three examples to illustrate your answer.
(b) Explain how a Curried Function can be partially applied. Give an example to illustrate your answer. [4 marks]
(c) Sometimes a function may appear to be applied to too many arguments. Explain how this can occur without any error – i.e. where the function and its application are correctly typed and there is no compile-time or run-time error. Give an example to illustrate your answer. [6 marks]
(d) You are given the following function definitions, where number is the name of a type synonym:
one :: number one f x = f x
two :: number
two f x = f (f x)
three :: number
three f x = f (f (f x))
operator a b = h where
h c x = a c (b c x)
i) Give a polymorphic type synonym definition for number. [6 marks]
ii) Give the polymorphic type of the function operator. [5 marks]
iii) Explain the operation of the function operator (in the context of the other definitions given above) by giving the evaluation steps of a simple application such as (operator one two). Then explain in general terms what the function operator does (for example, could it be given a more descriptive name?). [6 marks]
[Total 33 Marks]
COMPGC16 1 [Turn over]
2. (a) Explain what the following Miranda algebraic type represents:
fred * ::= Empty | Node * [fred *]
[4 marks] (b) Consider the following Miranda code (the ! operator provides an index into a
list counting from zero, for example [1,2,3]!0 returns the value 1): t_graph * ::= Emptygraph | Node * [t_graph *]
glist :: [t_graph char]
glist = [ Node ’A’ [glist!2, glist!1],
Node ’B’ [glist!3],
Node ’C’ [glist!0, glist!3], Node ’D’ []
graph :: t_graph char
graph = hd glist
Give a diagram to illustrate the data structures glist and graph.
(c) The predefined Miranda function member is defined as:
member :: [*] -> * -> bool
member [] x = False
member (x:xs) y = (x=y) \/ member xs y
Using the function member, give the definition for a Miranda function printgraph which takes an argument of type t_graph char and returns a list of characters representing the data structure. The word “nil” should be used to signify an empty graph node. Your program must not loop forever; if a Node has been encountered previously, the word “seen” should be printed instead of its list of successor nodes.
For example, the application (printgraph graph) should return the following result (NB a node that is shared and appears in different branches may appear multiple times in the output):
Node A [Node C [Node A seen, Node D nil], Node B [Node D nil]]
[23 marks] [Total 33 marks]
COMPGC16 2 Continued
3. (a) Explain, in words, how the recursive type [*] could be defined. Your definition should itself be recursive. [3 marks]
(b) Either explain what the following function does, or explain what is wrong with it:
f (‘1’ : rest) = 1 : (f rest) f (2 : rest) = 2 : (f rest)
f (x : rest) = f rest
(c) Give a Miranda algebraic type definition for a new type called numchar with two legal values, one of which contains a number and the other contains a character.
(d)Give a Miranda algebraic type definition for a binary tree called numchartree that contains one data value (only) in each node, and where that data value can contain either a number or a character (but no other type).
(e) Give the Miranda function definition, including its type, for a function called insertnum which inserts a number into a numchartree such that the tree contains only numbers and such that the numbers in the tree are sorted; i.e. for each node containing value v, all the numbers held in its right subtree are greater than or equal to v, and all the numbers held in its left subtree are less than v.
(f) Give the Miranda function definition, including its type, for a function called deletenum which deletes a number from a numchartree such that the numchartree contains only numbers and such that the numbers in the tree are sorted (as defined in part (e) of this question) both before and after the deletion. Give definitions for any auxiliary functions that you require (except functions that exist in the Miranda standard environment).
[12 marks]
[Total 33 Marks]
COMPGC16 3 [Turn over]
(a) 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:
[10 marks]
(b) Explain how a “free list” memory allocation algorithm operates. Give three different examples of sequential fit algorithms and compare their behaviour.
[13 marks]
(c) Explain how a “pointer increment” memory allocation algorithm might work together with sliding compaction to provide an automatic memory management system.
[10 marks] [Total 33 Marks]
(a) State briefly what garbage collection is and why it is necessary for both Miranda and Java. Give a pictorial example of the creation of garbage in a graph reduction system. [8 marks]
(b) Describe briefly the operation of three different garbage-collection techniques and compare their advantages and disadvantages. [14 marks]
(c) What is fragmentation and how can it be cured? Your explanation should make reference to the three garbage collectors described in your answer to part (b) of this question. [11 marks]
[Total 33 Marks]
[END OF PAPER]
COMPGC16 4 Continued
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com