[SOLVED] CS Department of Computer Science University College London

Department of Computer Science University College London
Cover Sheet for Examination Paper to be sat in May 2006
COMP3C11: Functional Programming
Checked by First Examiner: Approved by External Examiner:

Copyright By Assignmentchef assignmentchef

Date: Date:
COMP3C11 1
Time allowed 2.5 hours
Calculators are allowed Answer THREE questions

COMP3C11: Functional Programming, 2006
Answer any THREE questions
Marks for each part of each question are indicated in square brackets. Calculators are permitted
1. (a) Give the syntax for the untyped lambda calculus without constants and give the definitions for the reduction rules that are used to evaluate expressions in that calculus. [10 marks]
(b) Explain how a lambda calculus expression is evaluated, including an explanation of the term reducible expression. [11 marks]
(c) What is a recursive function? Give examples of function definitions in Miranda for both a stack recursive function and an accumulative recursive function. For each function, provide a sample function application and give the reduction steps (using any reduction order, to any normal form) for that application. [7 marks]
(d) 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 that is recursive. [5 marks]
[Total 33 Marks]
COMP3C11 2 Continued

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 empty 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 empty], Node B [Node D empty] ]
[23 marks] [Total 33 marks]
COMP3C11 3 Turn Over

3. (a) Give the types for the following five function definitions:
nil f = f (error head of nil) (error tail of nil) True cons a b f = f a b False
habc=a tailx =xt
tabc=b isnil x = x g
g a b c = c
(b) Use hand evaluation to demonstrate the following two equalities:
head (cons a b) = a tail (cons a b) = b
(c) Use hand evaluation to demonstrate the following equality:
head (tail (cons a (cons b c))) = b
(d) Explain why the following function definition is wrong:
newmap f nil = nil
newmap f (cons a b) = cons (f a) (newmap f b)
[10 marks]
(e) Consider the following alternative definition for the function newmap that maps a function over the elements of the cons as defined in this question (above)
newmap f x = nil, if (isnil x) = x g, otherwise
g a b c = cons (f a) (newmap f b)
Show how this function would correctly map a function over the elements of a cons, by providing a hand evaluation of the following expression:
head (tail (newmap (+ 1) (cons 3 (cons 4 nil)))
COMP3C11 4 Continued

[Total 33 marks]
4. (a) Explain how a tree of binary application nodes can be used to represent a functional program and how this representation naturally supports both curried function definitions and can be extended to support recursive functions. [6 marks]
(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]
COMP3C11 5 Turn Over

5. Given a heap memory with the following characteristics:
heap size = 2Mbytes
block header size = 4 bytes
minimum allocatable block size = 128 bytes
maximum allocatable block size = 16Kbytes
free-list allocator using LIFO first-fit allocation
(a) What is the maximum number of live blocks that can exist in this heap?
(b) What is the minimum information that needs to be stored in each block header and what extra information would each header need to include in order to support coalescing?
(c) How would the performance of the allocator be affected if address-ordered first-fit allocation were used instead of LIFO first-fit allocation? [2 marks]
(d) What problem is solved by Knuths boundary tags mechanism? Give a detailed explanation of how boundary tags could be implemented in the above heap to provide a comprehensive solution to the stated problem. Specific attention should be paid to the contents of the block headers, the procedures involved, and the performance implications. [15 marks]
(e) If the maximum block size were to be increased to 127Kbytes, how would this affect the block header (assume coalescing is supported)? Suggest two solutions and state the factors that would determine which solution would be preferable in a given context. [10 marks]
[Total 33 marks] END OF PAPER
COMP3C11 6 Continued

CS: assignmentchef QQ: 1823890830 Email: [email protected]