Examination for
Bachelor of Computer Science, Bachelor of Mathematical and Computer Science, Bachelor of Business Information Technology, Bachelor of Engineering, Graduate Diploma in Computer Science, Masters of Information
Technology, Masters of Computer Science, Masters of Software Engineering.
Semester 2, November 2010
9811 Advanced Programming Paradigms COMPSCI 3009, 7031
Official Reading Time: Writing Time:
Total Duration:
Questions
Answer all 8 questions
10 mins 120 mins 130 mins
Instructions
• Begin each answer on a new page
• Examination material must not be removed from the examination room • No Calculators Allowed
• Dictionaries for translation only
Materials
• 1 Blue book
DO NOT COMMENCE WRITING UNTIL INSTRUCTED TO DO SO
Time 120 mins
Marks 120 marks 120 Total
Advanced Programming Paradigms
Semester 2, November 2010
Question 1
(a) The exponent function can be defined as:
exp(x, n) = x * exp(x, n-1) , if n > 0
= 1 , if n = 0
Page 2 of 11
i. Write a Scheme function which implements exp as defined above. Your function must generate a Recursive process.
[4 marks]
ii. Write another version of exp which generates an Iterative process.
[5 marks]
- (b) WriteaSchemeprocedure,calledenum-downfrom,thattakesapositive integer n and returns a list of integers from n down to zero inclusive. So, for example:
(enum-downfrom 4) returns the list (4 3 2 1 0).
[3 marks]
- (c) Write a Scheme procedure, called drop, which takes a positive integer parameter n and a list parameter ls and returns a list consisting of all but the first n elements of ls. If ls is less than n elements long then drop should just return the empty list. So, for example:
(drop 3 (list 3 4 5 6 7 8)) will return the list (6 7 8) and:
(drop 10 (list 1 2 3)) will return the empty list: ().
(d) Write a Scheme procedure called sfunc which takes in two procedural values: f and g and returns a procedure which takes a value x and returns: f(x) + g(x). So, for example, given the following definitions:
(define (square x) (* x x))
(define (inc x) (+ x 1))
(define si (sfunc square inc))
Thecall: (si 4)=(+165)=21
Please go on to the next page. . .
[4 marks]
[4 marks]
Advanced Programming Paradigms
Semester 2, November 2010 Page 3 of 11
(e) Considerthefollowingdefinitionofsum,aproccedurewhichcomputes the sum of all numbers in the range a to b.
(define (sum a b)
(if (> a b)
0
(+ a
(sum (+ 1 a) b))))
An analogous procedure can also be written for product:
(define (product a b)
(if (> a b)
1
(* a
(product (+ 1 a) b))))
Write a higher-order Scheme procedure, called accumulate, that can generalize these types of series by taking in an operator and identity value thus:
(accumulate operator identity a b)
So that we can re-define the above series as:
(define (sum a b) (accumulate + 0 a b))
(define (product a b) (accumulate * 1 a b))
Please go on to the next page. . .
[Total for Question 1: 25 marks]
[5 marks]
Advanced Programming Paradigms
Semester 2, November 2010 Page 4 of 11
Question 2
Appendix 1 shows a Scheme definition for a simple Item object which could be used in an inventory system. An item object consists of a name and stock which tracks how many of that particular item are in the inventory.
(a) Write down a Scheme expression to create an item, B1 with a name of ”Ale”, and an inital stock of 10. Please note that you can represent the name using either a String or a quoted-literal. That is, as ”Ale” or ’Ale
[2 marks]
(b) To increase the stock of item B1 by five, the following expression is needed:
( (B1 ’addItems) 5)
Many people find this notation confusing: write a scheme procedure, increaseStock, which accepts two arguments: an item name and an amount. It can then be used thus:
(increaseStock B1 5)
[3 marks] (c) i. Draw an environment diagram which shows the state of the sys-
tem after B1 from part (a) has been defined.
ii. Now extend your diagram from part (i) to depict the evaluation
of (define adder (B1 ’addItems)).
iii. Finally, extend your diagram to depict the evaluation of (adder
5) which will increase the stock of item B1 by five.
[Total for Question 2: 14 marks]
Please go on to the next page. . .
[4 marks] [3 marks]
[2 marks]
Advanced Programming Paradigms
Semester 2, November 2010 Page 5 of 11
Question 3
(a) Examine each of the following four expressions, and state whether or not it is a syntactically valid lambda-expression:
• (x.x)
• x
•xy
• a.(a.a)
[4 marks]
(b) Reduce, using normal order evaluation, the following lambda expres- sion. Show your working, identifying the binding variable, argument and substitution made at each step, and stating the lambda reduction rule used.
(((x.y.x)z)((r.r r)(s.s s)))
Please go on to the next page. . .
[4 marks]
[Total for Question 3: 8 marks]
Question 4
- (a) State, and briefly explain, the three reduction rules of the lambda cal- culus. Use examples in your answer.
[6 marks]
- (b) Consider these Scheme definitions, each of a function of one argument that always produces a constant value:
(define (consta x) ’a) (define (constb x) ’b)Now consider the Scheme expression
( (compose consta constb) ’c))
Write this expression in -notation, and use the rules of the -calculus to illustrate how evaluation of the expression takes place. To do this, you will need to first define compose in the -calculus: the composition of two one-argument functions f and g is defined as the function that maps an argument x to f(g(x)).
[7 marks]
[Total for Question 4: 13 marks]
Question 3
- (a) What is the most important characteristic of streams in Scheme, that distinguishes them from lists?
[2 marks]
- (b) Explain, with a simple example, why it is not possible to implement
streams in Scheme using the pre-defined operations cons, car and cdr.
[4 marks] - (c) Write a Scheme procedure, called even-stream, that takes an infi- nite stream of integers, and produces a stream containing only the even elements of the stream. In your answer, you must define any stream-processing procedures that you use. You may assume that the predicate even? has been defined.
(d) The Fibonacci numbers may be defined in Scheme as:
(define fib (cons-stream 1 f2))
(define f2 (cons-stream 1 f3))
(define f3 (addL fib f2))
Draw a process network corresponding to this definition. On your diagram, label the arcs corresponding to fib, f1, and f2.
[4 marks]
[Total for Question 3: 16 marks]
[6 marks]
Advanced Programming Paradigms
Semester 2, November 2010
Appendix 1 – Scheme definition of item object
(define (make-item name stock)
(define (addItems n)
(set! stock (+ stock n)))
(define (removeItems n)
(set! stock (- stock n)))
(define (dispatch m)
(cond ( (eq? m ’name) name )
( (eq? m ’stock) stock)
( (eq? m ’addItems) addItems)
( (eq? m ’removeItems) removeItems)
(else (error "Unknown request" m))))
dispatch)
Page 11 of 11
End of exam