• Skip to primary navigation
  • Skip to main content
  • Skip to primary sidebar

Noulakaz

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

  • Home
  • About
  • People
    • Christina & Avinash Meetoo
    • Avinash Meetoo
    • Christina Meetoo
    • Anya Meetoo
    • Kyan Meetoo
  • General
    • News
    • Mauritius
    • Politics
    • Education
    • Business
    • Travel
  • Computing
    • Apple
    • Linux
    • LUGM
    • Programming
    • Web
    • Technology
    • Knowledge Seven
  • Entertainment
    • Music
    • Movies
    • Photography
    • Sports

Answers for my Scheme and Prolog test

7 April 2008 By Avinash Meetoo 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!

Filed Under: Education, Programming, Technology

Reader Interactions

Comments

  1. xd says

    7 April 2008 at 19:59

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

  2. avinash says

    7 April 2008 at 21:14

    Why?

    And what types of questions would you prefer? I’m (very) curious about this.

  3. Qwerty says

    7 April 2008 at 21:17

    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. Qwerty says

    7 April 2008 at 21:24

    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. Gavin says

    7 April 2008 at 22:14

    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

  6. Eddy Young says

    7 April 2008 at 23:01

    Is Scheme stack-based? The code is very easy and natural to read. I’ll have to learn more about it.

    Eddy

  7. avinash says

    7 April 2008 at 23:18

    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. prithvish says

    7 April 2008 at 23:45

    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. girish says

    8 April 2008 at 10:34

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

  10. jo says

    8 April 2008 at 14:28

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

  11. k says

    9 April 2008 at 09:27

    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. Reehas says

    9 April 2008 at 15:08

    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. Helios says

    10 April 2008 at 07:29

    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. Kervin says

    10 April 2008 at 09:23

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

  15. avinash says

    10 April 2008 at 10:42

    So #5 (like #7) was an opportunity for you to get “gift marks” (points cadeau) ;-)

  16. ¥@$# says

    10 April 2008 at 20:42

    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. avinash says

    10 April 2008 at 22:10

    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. selven says

    15 April 2008 at 23:31

    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. avinash says

    16 April 2008 at 00:39

    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. reehas says

    19 April 2008 at 01:45

    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. avinash says

    19 April 2008 at 08:26

    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. ict/ecs says

    27 April 2008 at 17:24

    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. avinash says

    28 April 2008 at 06:00

    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. jt says

    6 May 2008 at 15:04

    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. ICT says

    6 May 2008 at 20:47

    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. reehas says

    9 May 2008 at 12:35

    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 *

Primary Sidebar

Our Personal Websites

Avinash Meetoo
Christina Meetoo
Anya Meetoo
Kyan Meetoo

You may also like

Default ThumbnailScheme is a good language for beginners Default ThumbnailLearning Scheme with me Default ThumbnailWhy are there so many programming languages? Default ThumbnailLearning by experimenting (with Scheme)

Random Posts

This is Anfield !

Firefox extensions that I use

World class football players

Recent Comments

  • Memento Mori by Depeche Mode on My Top 50 Depeche Mode songs
  • Memento Mori by Depeche Mode on I have my dream HiFi setup: Audiolab and Elac
  • Avinash Meetoo on High-End Hi-Fi Audio Companies

Archives

  • March 2023 (5)
  • February 2023 (1)
  • December 2022 (1)
  • November 2022 (1)
  • October 2022 (4)
  • August 2022 (3)
  • July 2022 (3)
  • June 2022 (5)
  • May 2022 (5)
  • January 2022 (3)
  • December 2021 (2)
  • November 2021 (1)
  • October 2021 (1)
  • September 2021 (4)
  • August 2021 (2)
  • July 2021 (14)
  • May 2021 (2)
  • April 2021 (4)
  • March 2021 (9)
  • February 2021 (2)
  • January 2021 (1)
  • October 2020 (1)
  • September 2020 (1)
  • August 2020 (2)
  • July 2020 (5)
  • June 2020 (3)
  • May 2020 (5)
  • April 2020 (6)
  • March 2020 (2)
  • February 2020 (2)
  • January 2020 (2)
  • October 2019 (1)
  • September 2019 (2)
  • July 2019 (2)
  • June 2019 (1)
  • May 2019 (3)
  • April 2019 (2)
  • March 2019 (1)
  • February 2019 (1)
  • January 2019 (3)
  • December 2018 (1)
  • October 2018 (3)
  • August 2018 (2)
  • July 2018 (2)
  • June 2018 (1)
  • May 2018 (1)
  • April 2018 (1)
  • February 2018 (1)
  • December 2017 (1)
  • October 2017 (1)
  • September 2017 (1)
  • August 2017 (1)
  • July 2017 (1)
  • May 2017 (4)
  • April 2017 (3)
  • March 2017 (4)
  • February 2017 (5)
  • January 2017 (3)
  • October 2016 (1)
  • September 2016 (1)
  • August 2016 (4)
  • July 2016 (1)
  • June 2016 (1)
  • March 2016 (3)
  • February 2016 (3)
  • January 2016 (1)
  • December 2015 (1)
  • November 2015 (2)
  • September 2015 (1)
  • August 2015 (3)
  • March 2015 (1)
  • December 2014 (1)
  • November 2014 (4)
  • October 2014 (1)
  • March 2014 (2)
  • February 2014 (3)
  • December 2013 (1)
  • October 2013 (1)
  • September 2013 (1)
  • August 2013 (1)
  • July 2013 (1)
  • June 2013 (2)
  • May 2013 (1)
  • March 2013 (3)
  • January 2013 (2)
  • December 2012 (3)
  • November 2012 (4)
  • September 2012 (3)
  • August 2012 (2)
  • July 2012 (3)
  • June 2012 (2)
  • May 2012 (1)
  • April 2012 (2)
  • February 2012 (1)
  • January 2012 (4)
  • December 2011 (2)
  • November 2011 (1)
  • October 2011 (4)
  • September 2011 (2)
  • August 2011 (1)
  • July 2011 (2)
  • June 2011 (4)
  • April 2011 (7)
  • March 2011 (2)
  • February 2011 (1)
  • January 2011 (3)
  • November 2010 (3)
  • October 2010 (1)
  • September 2010 (2)
  • August 2010 (4)
  • July 2010 (2)
  • June 2010 (1)
  • May 2010 (3)
  • April 2010 (4)
  • March 2010 (3)
  • February 2010 (3)
  • January 2010 (5)
  • December 2009 (2)
  • November 2009 (3)
  • October 2009 (1)
  • September 2009 (5)
  • August 2009 (3)
  • July 2009 (1)
  • June 2009 (3)
  • May 2009 (2)
  • April 2009 (7)
  • March 2009 (12)
  • February 2009 (10)
  • January 2009 (5)
  • December 2008 (4)
  • November 2008 (11)
  • October 2008 (6)
  • September 2008 (7)
  • August 2008 (3)
  • July 2008 (8)
  • June 2008 (6)
  • May 2008 (5)
  • April 2008 (7)
  • March 2008 (6)
  • February 2008 (3)
  • January 2008 (6)
  • December 2007 (11)
  • November 2007 (10)
  • October 2007 (7)
  • September 2007 (9)
  • August 2007 (3)
  • July 2007 (7)
  • June 2007 (8)
  • May 2007 (14)
  • April 2007 (11)
  • March 2007 (18)
  • February 2007 (14)
  • January 2007 (15)
  • December 2006 (16)
  • November 2006 (10)
  • October 2006 (7)
  • September 2006 (8)
  • August 2006 (8)
  • July 2006 (6)
  • June 2006 (4)
  • May 2006 (13)
  • April 2006 (10)
  • March 2006 (11)
  • February 2006 (7)
  • January 2006 (14)
  • December 2005 (8)
  • November 2005 (6)
  • October 2005 (7)
  • September 2005 (2)
  • August 2005 (6)
  • July 2005 (2)
  • June 2005 (6)
  • May 2005 (15)
  • April 2005 (12)
  • March 2005 (3)
  • February 2005 (8)
  • January 2005 (3)
  • December 2004 (1)
  • November 2004 (2)
  • October 2004 (2)
  • September 2004 (3)
  • August 2004 (3)
  • July 2004 (3)
  • June 2004 (3)
  • May 2004 (6)
  • April 2004 (10)
  • March 2004 (12)
Creative Commons License This work is licensed by Avinash Meetoo under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 Unported License.