Department of Computer Science University College London
Cover Sheet for Examination Paper to be sat in May 2017
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, 2017
Answer any THREE questions
Marks for each part of each question are indicated in square brackets. Calculators are permitted
1. (a) Give the Miranda code for an algebraic type called ¡°expr¡± that defines the values for an expression in the untyped lambda calculus without constants.
(b) Based on your answer to part (a), give the Miranda code for a function called ¡°substitute¡± with type ¡°[char] -> [char] -> expr -> expr¡± whose output is a modification of the third argument where all free occurrences of the first argument have been replaced with the second argument. Thus, (substitute ¡°x¡± ¡°y¡± e) will replace all free occurrences of the name ¡°x¡± found inside e with the name ¡°y¡±.
[13 marks]
(c) What is a combinator? Give lambda-calculus expressions for the three combinators known as S, K, and I (also known as ¡°distribute¡±, ¡°cancel¡± and ¡°identity¡±).
(d) Give an alternative lambda calculus definition of the combinator known as ¡°identity¡± (I), using only the functions ¡°distribute¡± (S) and ¡°cancel¡± (K) in the function body. Then give an example application of this alternative definition to the number 23, showing step by step how the reduction proceeds, and how it results in the final answer.
[7 marks] [Total 33 Marks]
COMPGC16 1 Turn Over
2. (a) What operation does the following code perform (assuming the function is type-correct)?
f Empty = 0
f (Node x a b) = x + (f a) + (f b)
Choose one of the following answers (choose the most accurate answer):
(i) it resets to zero all the values in a data structure
(ii) it counts how many elements exist in a list
(iii) it adds all the values in a list of numbers
(iv) it sums all the values in a tree of numbers
(v) it counts the number of levels in a tree
(vi) it applies a function argument to all the values in a tree
(b) Which of the following are correct algebraic type definitions, and which are incorrect? For each incorrect definition, also say why it is incorrect.
(i) dicevalues::=1|2|3|4|5|6 (ii) Fluid := Litres |Gallons
(iii) Fruit == Apples | Oranges
(iv) Tree :: Empty | Node x left right
(v) list ::= Nil | Cons * (list *)
(vi) cards ::= King | Queen | Jack | Other num
(vii) circle == Circle circle (viii) circle :: Circle circle
(ix) circle ::= Circle circle
COMPGC16 2 Continued
(c) Given the following Miranda definitions, what does the expression (f test) return?
mytype * ** ::= Fred * | Mary [mytype ** *] test :: mytype num bool
test = Mary [ , Mary [Fred 34]]
f :: mytype num f (Fred x)
f (Mary [])
f (Mary [x])
bool -> [char] =showx
= “(“++(show x)++”)”
f (Mary (x:xs)) = “{“++(f (Mary xs))++”}”
Choose one of the following answers (choose the most accurate answer): (i) 34
(iii) ¡°Mary [Fred 34]¡±
(iv) ¡°[Fred 34]¡±
(v) ¡°{(Mary [Fred 34])}¡±
(vi) ¡°({Mary (Fred 34)})¡±
(vii) ¡°{Mary []}¡±
(d) A recursive function called ¡°rightmost¡± is required to take as input a value of type ¡°(tree *)¡± as defined below and return the value of the rightmost leaf of that tree. The function is required to use a pattern-matching style of definition, in Miranda. Give the type and the code for two versions of this function: one using exactly four patterns and the second using exactly five patterns, and comment on their relative efficiency.
tree * ::= Leaf * | BinaryNode * (tree *) (tree *) | MultiwayNode * [tree *]
[16 marks] [Total 33 marks]
COMPGC16 3 Turn Over
3. (a) Which of the following function definitions would be correct if the function were specified to have the type num -> (num,num) -> bool ? For each function say whether it is correct or incorrect. If a function is incorrect, say why.
(i) fxy=True (ii) f (x,y) = False
(iii) f x (a,b) = (a=b) (iv) fx(a,b)=(=a)
(v) fxy=(x=y)
(b) What is the result calculated by the following program?
functions one, two and three are intended to represent, and give a more descriptive name for the function called ¡°op¡±
one f x = f x
two f x = f (f x)
three f x = f (f (f x))
op a b f x = a f (b f x) main = op two one
[10 marks]
(c) What is the type of ¡°g¡± defined below? What does it do and how does it do it?
g = (foldr (+) 0) . (foldr ((:) . ((#) . (:[]))) [])
[10 marks]
(d) What type would Miranda give to each of the following functions?
f1 (a:b) f x = a ((x f b) . f)
f2 [] y z = z f2 (a : b) y z
= (a z) & (f2 b y ((y . a . y) z))
COMPGC16 4
Suggest what the
[8 marks] [Total 33 marks]
4. The Miranda functions ¡°rcons¡±, ¡°rnil¡± and ¡°id¡± are defined below, together with the definition of a function ¡°rev¡± that reverses a list:
rcons a f b = f (a : b)
rev items = foldr rcons rnil items []
(a) Give the Miranda type definitions for ¡°rev¡± and ¡°rcons¡±.
(b) Provide a hand evaluation, giving all intermediate evaluation steps, for the
following application of ¡°rev¡±: rev [1,2,3]
(c) Will ¡°rev¡± correctly reverse any list? Explain your answer. [4 marks]
(d) In the context of ¡°rev¡±, explain in detail how ¡°rcons¡± and ¡°rnil¡± work, with examples. [10 marks]
[Total 33 marks]
COMPGC16 5 Turn Over
[10 marks]
5. (a) (b)
Explain how a ¡°free list¡± memory allocation algorithm operates.
For the First Fit sequential fits algorithm explain the following:
a. What is the minimum number of administrative pointers required to implement this algorithm?
b. From what position in the list does the search start?
c. When does the search stop?
d. Explain one disadvantage with this technique.
Describe the contents of a cell in a graph reduction system that uses binary application cells, and explain how the cell could be augmented to accommodate a reference-counting garbage collector.
Give three limitations of reference-counting garbage collection, and suggest a possible solution for one of these limitations.
[7 marks] [Total 33 marks]
a. What is the minimum number of administrative pointers required to implement this algorithm?
b. From what position in the list does the search start?
c. When does the search stop?
d. Explain one disadvantage with this technique.
For the Next Fit sequential fits algorithm explain the following:
a. What is the minimum number of administrative pointers required to implement this algorithm?
b. From what position in the list does the search start?
c. When does the search stop?
d. Explain one disadvantage with this technique.
For the sequential fits algorithm explain the following:
END OF PAPER COMPGC16 6 Continued
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com