Monday, February 20, 2006

Chinese Ring Puzzle, Recursion and My First Programming Language Course

It was nostalgic to see the subtleties of Chinese Ring Puzzle make its royal comeback in Fascicle 2 of Volume 4 of Knuth's classic The Art of Computer Programming. The Chinese Ring Puzzle is one of the classic examples used in undergrad CS classes to teach recursion and presents one of the most elegant algorithms incorporating two mutually recursive routines. Grady G Early had long recommended teaching Chinese Ring Puzzle as the framework for recursion to undergrad classes, since it "is not only a master example of recursion and interesting in its own right. It can also be used to generate Gray codes". It is precisely the subject of generation of Gray codes with this toy that has been treated with the usual brilliance by the master himself.

This brings me to the last part of the title of my post - has the paradigms of functional programming and recursion lost their relevance in today's Programming Language Basics course ? People coming out of undergrad CS schools all seem to have mastered Java - this is the language that they learn in the 101 course on Programming Languages. Cornell's Computer Science Program has this up in their undergrad page for Programming Languages. Among the myriads of programmers coming out of CS schools and being absorbed in the milieu of Java shops, knowledge of the basic principles of functional languages like recursion, higher order functions, function currying, closures etc. are mostly missing. Similar thoughts and apprehensions have also been expressed by Joel in one of his posts. In the current era of agile development, multi-paradigm designs, we definitely need to think flexibly - OO is not the panacea and definitely not the "fit-all" for all software designs. Many modern langugages (Scala) have combined OO with functional programming, and not without a reason - programmers need to learn with an open mind to come up with abstractions at the entity level as well as the function level. MIT Press has done a wonderful job in putting the classic Structure and Interpretation of Computer Programs by Hal Abelson and Jerald Jay Sussman online.

No comments: