I started four weeks ago with a general introduction on programming paradigms and on the necessity to at least know the most important ones in order to become a decent programmer. As my students had already studied imperative and object-oriented programming become coming to my class, I offered them to teach functional programming (using Scheme), logic programming (using Prolog in principle) and scripting (using Ruby). This first lecture can be downloaded here.
The following week, I introduced Scheme by putting a lot of accent on the evaluation of expression and the definition of simple (mathematical functions). The lecture, which is available here, was followed by a lab sheet where the students were introduced to DrScheme and were asked to write a number of simple functions (like fahrenheit->celcius).
The next lecture was on recursion and I focussed on a number of mathematical functions like factorial, fibonacci, square root using Newton’s successive approximation etc. I spent some time introducing the concept of tail-recursion to them as well as the tail-recursion optimization that Scheme has to do.
As an example, this:
(define (o+ n m)
(cond ((zero? m) n)
(else (o+ (add1 n) (sub1 m)))))
runs in constant space (i.e. there are no recursive function calls at runtime) even though it is expressed recursively. During the lab, the students implemented and traced a number of recursive functions (using the tracing facilities found in MzScheme). They implemented o+’s friends, o-, o*, o/, o^, o=, o< and o> (corresponding, of course, to our usual +, -, *, /, ^, =, < and >) using tail-recursion so that they run as quickly as possible.
The last lecture which I had last Friday was on pairs and lists, the most fundamental compound data structures found in Scheme. I introduced them to car and cdr and showed them a number of fundamental algorithms acting on lists (like length). During the lab, I asked the students to implement a simple database of students and marks and this is inspired by what I read in Practical Common Lisp.
My lectures have been cool up to now. The students are lively and responsive to my jokes and “parentheses”. The labs also are going on nicely with students who are really learning new things and having fun in the process.
It’s too early to say whether they’ll become better programmers eventually but I feel they are on the right track…