Department of Computer Science University College London
Cover Sheet for Examination Paper to be sat in May 2009
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, 2009
Answer any THREE questions
Marks for each part of each question are indicated in square brackets. Calculators are permitted
1. (a) Briefly explain, with examples, what is meant by the following terms:
partial application case analysis structural induction
(b) Give the value computed by each of the following seven 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)=0) & ((23 / 0) = 0) ((3-3)=0) \/ ((23 / 0) = 0)
exp1 = 25, if (3 < 5 < 27)
= False, otherwise
exp2 = 3, if True
= 5, otherwise
(c) Given the following Miranda function definition:
bizarre f x = f x (f x)
[11 marks]
Explain why this definition would produce a type error in Miranda. By contrast, provide a lambda calculus expression that when evaluated will loop forever.
[11 marks] [Total 33 Marks]
COMPGC16 2 Continued
[11 marks]
2. (a) What are algebraic data types? Give examples of the different kinds of algebraic type and how they might be used.
(b) Define a type structure to represent binary trees in which the nodes of the tree hold number values and the leaves also hold number values.
(c) Define a function to determine the height of a tree represented using your type, where the height of a tree is the number of nodes along the longest path from the root to a leaf.
(d) Consider the following function defined for lists:
map_on_tails f [] = []
map_on_tails f xs = (f xs) : (map_on_tails f (tl xs)
Define a function that works like “map_on_tails” but instead of being applied to a list it is applied to one of the trees represented by your type, i.e. a function is applied to every sub-tree within a tree.
[11 marks]
(e) Define a function which will take a tree and return a tree containing at each node the height of the corresponding sub-tree in the input tree.
[4 marks] [Total 33 marks]
COMPGC16 [Turn over]
3. Given the definitions:
s f g x = f x (g x)
b f g x = f (g x) whx=hxx
e = s (b w b) (b w b)
and given that the Y fixpoint combinator is defined axiomatically as
Y f = f (Y f)
(a) show that e is equivalent to Y by illustrating that partial reduction of the expression (e f) produces an expression that is equivalent to (f (e f))
[12 marks]
(b) In fact the definition for e given above is not a valid Miranda definition. Explain
why the definition of e gives rise to an error in Miranda.
(c) What is the most general type of each of the following functions:
fun1 (a:b) f x = a ((x f b) . f)
fun2 [] j acc = acc
fun2 f [] acc = acc fun2(x:xs)(y:ys)acc=y (fun2xsys(xyacc))
mysterious [] y z = z
mysterious (front : rest) y z
= (front z) & mysterious rest y ((y . front . y) z)
COMPGC16 4 Continued
[12 marks] [Total 33 marks]
You are told that a novel memory allocator preferentially allocates large blocks at the top end of available memory and small blocks at the bottom end of available memory. In all other respects the allocator is conventional. The allocator uses a double-linked free list in a heap memory of size H bytes (See Figure 1). The allocator maintains two pointers – one to the start of the double-linked free list and one to the end of the double-linked free list.
If each block’s header contains its size, what is the size of a block header and what is the minimum size of an allocatable block?
How many blocks of memory (and of what size) are there on the free list when the program starts (before any allocation)?
Give the details of how the very first allocation could be achieved if the requested block size is (i) small, and (ii) large. Give a diagram to illustrate the heap and the free list both before and after allocation in each case.
Give details of an allocation mechanism which would, for multiple successive block allocation requests, place small blocks at the bottom end and large blocks at the top end of available memory. Do this for two cases: (i) where the free list is held in Address Order; and (ii) where the free list is held in First-In-First-Out (FIFO) order.
[14 marks] [Total 33 Marks]
Free list pointer
Free list pointer
COMPGC16 [Turn over]
5. (a) Explain how a tree of binary application nodes can be used to represent a functional program and how this representation both naturally supports curried function definitions and can be extended to support recursive functions.
(b) Illustrate with diagrams how a beta-reduction is performed in a graph reduction system, and use your illustration to demonstrate how garbage may be produced.
[10 marks]
(c) Give a detailed description of 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.
(d) Give three limitations of reference-counting garbage collection, in terms of its functionality and its performance, and suggest possible solutions for two of these limitations.
[9 marks] [Total 33 marks] [END OF PAPER]
COMPGC16 6 Continued
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com