Noulakaz

The blog of Avinash, Christina, Anya and Kyan Meetoo.

Answers for my Scheme and Prolog test

By 26 Comments

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!

Reader Interactions

Comments

  1. It was indeed a cool test sir and i hope each class will have the chance to get such a test
    but 4 the exams sir,don’t give such question plz……….

  3. Question 3: Last-but-one element

    The first element in a list is at position 0 and not 1! .:. We must subtract 2 from length to get the desired result. Try this:
    (list-ref ‘(1 2 3 4) (- (length ‘(1 2 3 4)) 2))

    If you’ve cut my mark in the test, I hope you’ll restore it ;-)

  4. Btw Sir, I’ve personally liked the test very much, though my prolog part was blank(shh! dnt tell any1) :P

    I hate those test which asks us to vomit tonnes of theories onto paper. Hope to see more questions like the one on prime number in the exams!

  5. I personally find the test cool, as i told you before!

    Its a bit like the questions in Programming Pearls.

    Once you understand the concepts, its just childplay. We have to make them think out of the box!

    They probably expected a function like ‘Write a function in Scheme’ which evaluates to true if a number is Prime and False if otherwise.

    However, given the function they can’t recognize it!

    Many students can memorise complex logic and massive blocks of codes. But if you give them a simple program to write…they find it hard!

    G@V!N

  7. Scheme is not stack-based in the sense of Forth or Factor. It’s a simple version of Lisp designed for beginners. But being a Lisp, it is extremely powerful. My students for instance found higher-order functions (like map, foldl and filter) extremely powerful as you can see in function 5.

    Scheme is both a proper functional programming language and also can be used imperatively. Incidentally, major portions of The Gimp are written in Scheme.

    I first tasted Scheme in Year I in Réunion and it was love at first sight :-)

  8. the test was quite good..we had to think well to get those answers..actually only for scheme..question 5 was quite difficult though..for prolog its a disaster..

    its practically impossible to learn scheme by heart with all those car’s and cdr’s..1 example is the assignment..if you don’t understand the logic, there’s no way you do it right..

    prithvish

  9. Thanks for correcting the 3rd one. I thought my answer was not good…though it was working when I coded it. ;)

  10. the test was cool but did silly mistakes in all questions n the closure thing went just blank

  11. the test was cool.. and it was short but a complete test and it really needed some thinking without having to write too many theories on paper…

  12. The test was simple (but easy :s) as you predicted it for us in the lab :P

    but, we, as usual took more stressed than was necessary.

    i was even transpiring b4 the test, but immediately cooled down upon getting the test paper :D

    cant tell that i will be cooled again wen marks r given back :P

    your tests had always been quite unique n i must congratulate u for that.

    i was expecting ‘fill in the blanks’, as usual, but i was disapointed a litle ;)

    hmm finally, good luck for correcting the paper, though it will be very quick, bekoz of only right wrong, no need for long reading :P

    me, wenever i need to korek test papers, i get head aches, hope it wont be same in your case.

    Cheers

  13. The test was indeed cool… Well frankly i knew such kinds of questions would appear, so simple yet unexpected questions. This is the unique style of our dear lecturer… ;) I smiled :D when i saw the answer of number two and eventually three. During the test i was so stressed that i was not able to think about any answer… so just logically i put (reverse l) not sure whether it was the right answer in terms of syntax. Just hoping to pass this test… :D That was a nice one…

  14. Number 5 was pretty nice. however, 4 points just to describe a function and there was only 1 line given in the question sheet.

  16. Well as far as I know, this module is not called “CSE20XX Scheme, Prolog and Ruby”… Or maybe they renamed it since we did it last year as “Programming Languages”…

    The module seems to have been converted to a Programming Methodology (3) & (4) as a continuity from the CSE 1st Yr’s Programming Methodology (1) & (2).

    Now the syllabus seems to have shifted from : “Overview of programming languages; language design and implementation issues; language evaluation and selection issues; programming paradigms; programming environments; programming constructs, compilation process…” as said in the previous years’ syllabus… to now, well, Programming with a small part of Theory about the concepts of Programming Languages…

    I’ve checked online for the syllabuses of Programming Languages online for other universities as well… and they are more like the former than the current one…

    But yeah, they do include functional languages, LISP, Prolog, and blah blah blah… but they are there as a week’s lecture or so… Not the central part of the module.

    Well I’m not saying that the tests/exams should not assess the students on programming skills in those languages… But, IMHO, that should not be the core of it.

    As it is, the module is just a programming module. Not Programming Languages. Just my opinion.

    P.S. Yeah, the test was cool! Like a programming test! I agree :P

  17. Nice observation.

    And you are perfectly right. I did not teach Programming Languages. Instead I taught Functional programming (using Scheme), Logic programming (using Prolog) and Modern programming (aka scripting) (using Ruby).

    There are two reasons why I did that:

    (1) Many students do not know how to program because they couldn’t relate to C++ during the first year (which I fully understand – C++ is a crap programming language to teach programming…). Therefore, I decided to do Programming Methodology II and I believe that some students who disliked programming now find it comprehensible at least.

    (2) (real) Programming Language modules introduce students to the syntax and semantics of programming languages for one reason: to make them build their own compilers and interpreters. Unfortunately, even if there is a Compilation elective in Year III, it has been taught only once (as far as I know) and only by a visiting professor. It’s a waste of time learning about syntax and semantics if you don’t have the chance to apply the knowledge somewhere.

    Ideally, the Programming Language part should be combined with the Compilation part into a mega super Syntax and Semantics of Programming Languages yearly module. This would be a great module to teach but I guess that someone else would have to do it…

  18. since when have you started posting answers to your tests after a test??

    “Therefore, I decided to do Programming Methodology II and I believe that some students who disliked programming now find it comprehensible at least.”

    but still that is supposed to be PL… wouldn’t that mean causing a lost of what was supposed to be learnt in a classical PL module? [that also for the sake of people who didn’t understand programming methodology? [i’d rather suggest ‘un cour de rattrappage’, rather than hyjack the module’s content… hmm maybe i might be wrong] (that said, i still find the new pl more fun.. but still …

    “(2) (real) Programming Language modules introduce students to the syntax and semantics of programming languages for one reason: to make them build their own compilers and interpreters. Unfortunately, even if there is a Compilation elective in Year III, it has been taught only once (as far as I know) and only by a visiting professor. It’s a waste of time learning about syntax and semantics if you don’t have the chance to apply the knowledge somewhere.”

    but still.. some might argue that they are not getting what they signed up for…

    “It’s a waste of time learning about syntax and semantics if you don’t have the chance to apply the knowledge somewhere.”
    and… isn’t that supposed to make academics academics?

    Ideally, the Programming Language part should be combined with the Compilation part into a mega super Syntax and Semantics of Programming Languages yearly module.

    computer science students who don’t even have micro processors in their syllabus, now you want to insert compilation? :p it will be considerred as illegal, because “there won’t be many who will come out with degrees” and that… mr our prime minister won’t be happy about.

    $3|v3n

  19. Selven,

    As a lecturer, I decide what to teach and what to examine. This is called academic freedom :-)

    As for Compilation, read this from my hero, Steve Yegge.

  20. Sir, i took courage to go from here to the site of steve, but almost instantly was discouraged… lol

    toooooo much thing to read sir. I’m sure if i start to read, and when i finally arive at the end, i will forget what was said at the beginnig.. lol

    li ti pu pli korek, si nek ou met ban main points la laem, in your own words, ti pu pli simple pu compran sir…

  21. Unfortunately, life is not that simple :-)

    If you want to know what Steve Yegge said, you’ll have to read the thing by yourself.

    Don’t forget what I said during my lecture. I am a guide. I only show you where knowledge is. Assimilating it is your job.

  22. The test was indeed away from being a conventional one but very challenging… unfortunately the ict/ecs batch didn’t work quite well… we are sorry to disappoint you sir…
    we’ll try our very best for the exams…
    thank you for giving “UOM teaching style” a new direction… you are one of the best lecturers around the planet ;-)
    we had a great time working with you sir… thank you… god bless… good luck for life ahead…

  23. Hi,

    Thanks for the compliment :-)

    It’s nice to know that you have liked what you have learned with me. As a matter of fact, I enjoyed teaching that module a lot. It was the first time I taught Scheme and Ruby (and, of course, Prolog) and I really had a lot of fun preparing the lectures and labsheets. In fact, I learned a lot myself…

  24. Yep indead best lecturer i ve worked with during my 4 years at uom.. System software, Parallel programming and PL now..Uom badly need lecturers like you.. Friendly and lively in classe such that we want to come to your lectures and not bunk them..LOL :D

  25. HI Sir,
    its really sad to knw zat UOM will lose a lecturer like u..but am sure u’ll b back some d…hopefuly….loll…
    just wanted to let u knw zat ict/ecs students r really new to this subject…as u may have seen in class, we r really out of subject..and our marks provides the best evidence…they speak of themselves….so SIR could u plz consider our case and b lenient on our corretion……thx n plz stay as u r…….always cheerful and full of life….was glad to knw u……….plx pity us……………………

  26. If u deserve to fail.. you will fail…. We cannot compromise with quality.
    [Kavi Khedo]

Leave a Reply

Your email address will not be published. Required fields are marked *