Noulakaz

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

Programming

Scripting with Ruby and Audioscrobbler

By 7 Comments

My Year II students are currently learning scripting with Ruby, my favorite programming language (ex aequo with Scheme I think…). Today I thought about what could be the difference between scripting and programming and I came up with:

Scripting is the same as programming except that you don’t have to worry about unnecessary details like deciding upon types, declaring classes and handling exceptional conditions. In other words, you only focus on the fundamentals.

Ruby is an excellent scripting language because it has been designed correctly. My students have had no problems understanding Ruby code that they were seeing for the first time. In fact, Ruby is a very elegant language.

Ruby is also very powerful thanks to the predefined functionalities in Ruby Core and the Ruby Standard Library. I have naturally spent some time explaining the likes of strings, regular expressions, etc. to my students but also libraries like OpenURI (used to access resources likes files, images and web services found on the Internet) and REXML (used to extract parts of an XML file.)

Consider the following Ruby script for instance:

require "open-uri"
require "rexml/document"   

artist = gets
artist.chomp!
artist.gsub!(" ","+")

input = open("http://ws.audioscrobbler.com/1.0/artist/#{artist}/toptracks.xml")
doc = REXML::Document.new(input)

puts
puts "The 10 greatest tracks are:"
puts

count = 1

doc.elements.each("mostknowntracks/track") { |track|
  puts "(#{count}) #{track.elements["name"].text}"
  count += 1
  break if count > 10
}

This simple Ruby script prompts the user for the name of an artist and queries Audioscrobbler for his/her top music tracks using OpenURI. The XML file returned is parsed using REXML and the top 10 tracks are displayed on screen. This is what I get when running it:

$ ruby top-10-tracks.rb 
Depeche Mode 

The 10 greatest tracks are:

(1) Enjoy the Silence
(2) Personal Jesus
(3) Precious
(4) Just Can't Get Enough
(5) Policy of Truth
(6) Never Let Me Down Again
(7) It's No Good
(8) Dream On
(9) Strangelove
(10) World in My Eyes

and also

$ ruby top-10-tracks.rb 
Avinash Meetoo 

The 10 greatest tracks are:

(1) This is real
(2) Play
(3) Beautiful sea
(4) Helium
(5) The myst
(6) Zygma
(7) Seduction
(8) Deception
(9) Eternity
(10) Lion Heart

Not bad for a 20-lines long script! Incidentally, I deeply believe that Ruby is a great language to learn programming.

This is a great quote from one of my heroes, Mr Steve Yegge!

Ruby‘s one of the easiest languages for just about anyone to learn — it’s maybe a 3-day exercise, and after a week or so of using Ruby, you just may never look back. It’s like getting a new car: it still gets you from A to B, but without your old car’s flaky transmission, cracked windshield, and 5-year-old french-fry remnants under the driver’s seat.

Who am I to argue?

Scheme is a good language for beginners

By 7 Comments

I am currently teaching programming languages to second year students. I spent about 4 weeks introducing Scheme to them and I covered the following topics:

  • Expressions
  • Functions
  • Scope
  • Recursion and tail-recursion optimization
  • Pairs and lists
  • Higher-order function

Each lecture was followed by a lab session where students practiced what they saw in class.

I then gave the students an assignment to do where they had to write moderately complex higher-order functions. Last week, I asked the students to demonstrate to me what they had done. During the demo, I asked them a couple of questions.

What did they think about the assignment

Most students told me that they liked the assignment even if it was moderately tough. This was a surprise to me as I did not expect the students to like assignments. But this might be normal as I devised the assignment to appeal to the social networking generation. Another possibility is that many students managed to do a substantial part of the assignment without having to copy from a friend as Scheme is so beginner-friendly and powerful at the same time.

What did they think about Scheme

Many of them told me they found Scheme (and the DrScheme IDE) easier to understand than C++ which they used in Year I. Some said that higher-order function were very powerful and made their functions very compact yet powerful and easy to understand. A few didn’t use higher-order functions at all and relied on plain old recursion to solve the problems (that’s ok with me).

Interestingly, some students told me that Scheme should have been used in Year I instead of C++.

My opinion

I agree with them and I think there are two important reasons why Scheme is better than C++ for teaching programming:

  • Scheme, when used as a functional language, is waaaaaay simpler than C++. The only keywords we used were define, let*, lambda, cond, cons, car, cdr, add1, sub1 and null? With those, students managed to build very powerful functions. Compare this to the complexity of ISO C++.
  • Scheme has DrScheme which is, quite simply, the best Integrated Development Environment for students. It has fantastic stepping and tracing facilities (which are pretty much essential when one is learning…) and also provides a very powerful read-eval-loop. I learned programming around 1987 using a BASIC interpreter and I guess I would have become a poorer programmer if I only had a compiler at that time.

Of course, Scheme can be replaced by something like Haskell or even by the disciplined use of Ruby or Python.

The point is to use a simple (subset of a) language with a beginner-oriented IDE featuring a read-eval-loop. This is the exact opposite of using the most complex programming language ever with an IDE designed for professional software developers.

The top five universities in the world can’t all be wrong after all :-)

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!