Last friday, second year students following my Programming Languages class had a test on Scheme and Prolog. I asked them eight relatively straightforward questions which they had to complete in 45 minutes. I hope that most of them managed to get most of the answers right (I could see some students struggling though…) As I am a nice guy, I’m posting the questions and possible answers. I want to make it 100% clear that alternative answers (if they are correct of course) are also perfectly acceptable.
[2 marks] Write as a Scheme expression. Assume that sin and tan exist as predefined functions.
My answer is
(/ (sin (* x x)) (+ 1 (tan x)))
[2 marks] Complete the following Scheme predicate (one line only!) which returns true if the list l is a palindrome i.e. it is the same either read forward or backward (the list (a b c b a) is a palindrome):
(define (palindrome? l) (equal? l _________________________________________________))
My answer is
A geekish answer would be (foldl cons ‘() l) which is how reverse in implemented in the Scheme library. foldl is what other programming languages call a reduction operation.
Incidentally, this is one of the questions I was asked when I was interviewed by Google.
[2 marks] Complete the following Scheme function (one line only!) to find the last but one element of a list l. Assume that l is long enough to have a last but one element. The last but one element of (1 2 3 4) is 3 i.e. the element just before the last one in the list.
(define (last-but-one-element l) (__________________________________________________________))
A possible answer is simply
car (cdr (reverse l))
Notice that one can also use the list-ref function to directly access the last but one element (it is at position (- (length l) 2) as, in Scheme, the first element is at position 0 — thanks to Shrikaant for pointing this to me).
[2 marks] Given the following Scheme function:
(define (f a b) (cond ((> a b) '()) ((= a b) (list a)) (else (cons a (f (add1 a) b)))))
What is the value of (f 5 10)?
The answer is obviously (for me at least)
(5 6 7 8 9 10)
f is what is called a range function in other programming languages like Python and Ruby.
[4 marks] Given the following additional Scheme function where (modulo a b) is the remainder when a is divided by b:
(define (g a) (foldl (lambda (p1 p2) (and p1 p2)) #t (map (lambda (b) (> (modulo a b) 0)) (f 2 (sub1 a)))))
What is function g?
A possible answer is:
g is a function that takes a positive integer, a, as parameter and returns true if that integer is a prime number and false otherwise.
It works by mapping (lambda (b) (> (modulo a b) 0)) on the list (2 3 4 … a-1) produced by the same function f as seen in Question 4. The result of this mapping is a list of boolean values (false if the number is a divisor of a). For example:
(map (lambda (b) (> (modulo 10 b) 0)) '(2 3 4 5 6 7 8 9))
(#f #t #t #f #t #t #t #t)
The foldl (which is a reduction operation) then combines all those boolean values using the AND logical operator with #t as initial value. The result will be false if at least one of the numbers from 2 up to a-1 is a divisor for a. The result will therefore be true only if a is a prime number.
The reason I gave 4 marks for that question was that I knew many students would have to spend a lot of time to understand what the function really was. I did not expect them to write a detailed explanation… even though those who did that will not be penalized :-)
[1 mark] The following diagram shows the Procedure Box Model of Prolog. Label the three remaining arrows correctly:
The answer is: “Fail” on the left and “Exit” and “Redo” (top to bottom) on the right.
A functor fails when Prolog cannot satisfy a query. For instance, given the only fact, boy(john)., Prolog will fail when asked boy(albert). Exit is when Prolog has managed to satisfy a query. And redo occurs when the user asks Prolog to satisfy a query that exited before (i.e. the user wants an additional answer).
[4 marks] The Ackerman function is recursively defined thus:
Complete the implementation of the third case (i.e. m>0 and n>0) in Prolog by writing the four missing lines:
A possible answer is:
M1 is M-1,
N1 is N-1,
Lines 3-4 are used to calculate M-1 and N-1 using the is operator. The two last lines recursively call the Ackerman function as per the definition. Prolog is somewhat inflexible here as we are forced to invent a new variable PartialAnswer to hold what is “returned” by A(M,N-1).
Here also, I gave four marks, but in retrospect I should have given less because the complexity was much less than the previous question. I guess this is what is called “points cadeau” (gift marks…)
[3 marks] What is a closure?
A possible answer is:
A closure is a function that is evaluated in an environment containing one or more variables. I spent around 15-20 minutes explaining closures to my students when I showed them this diagram by Peter Van Roy:
Consider this higher-order function in Scheme:
(define (addn n)
(lambda (x) (+ n x)))
addn is a function which takes a parameter n and returns a function which takes any x and adds n to it. For instance, addn can be used as such:
(define one 1)
(define increment (addn one))
and consequently increment can be used as a normal function even though the variable one might be out of scope. It is as if the addn has internally memorized the value of the variable one. This capability for a function (which is code) to remember values is what makes a closure.
A closure is therefore behavior (the body of the function) as well as state (the memorized variables). Hence, it is an object in the object-oriented sense. In classical OO languages, an object can have a set of behaviors (a set of methods). This is easy to implement using a closure with one of the variables becoming a behavior selector and the function being just a massive cond statement (similar to a switch) which does different things depending on the value stored in the behavior selector.
A colleague remarked that this test was cool as it tested programming skills and also whether the student had really acquired important concepts. I also think that this is a cool test (and I would love to have had one like this when I was a student – I reckon I would have done really well…) I just hope that my 187 students have found it interesting too.
Now I only have to correct the 187 answer sheets… Hell!