Archives for April 2008

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.

 

Question 1

[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)))

 

Question 2

[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

(reverse l)

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.

 

Question 3

[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).

 

Question 4

[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.

 

Question 5

[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))

produces

(#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 :-)

 

Question 6

[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).

 

Question 7

[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(M,N,Answer) :-

  M>0,

  N>0,

  __________________________________________________________

  __________________________________________________________

  __________________________________________________________

  __________________________________________________________

A possible answer is:

A(M,N,Answer) :-

  M>0,

  N>0,

  M1 is M-1,

  N1 is N-1,

  A(M,N1,PartialAnswer),

  A(M1,PartialAnswer,Answer)

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…)

 

Question 8

[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.

 

Conclusion

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!