Reversible Arithmetic as a Pedagogical Tool

Appeared in Volume 7/3, August 1994

Keywords: teaching.

Peter B. Reintjes

I watched with some amusement as reversible arithmetic was discussed in the comp.lang.prolog newsgroup. I found it somewhat interesting, and got something out of the discussion, but I must comment on the suggestion that this would make a very good programming assignment (i.e. because it was non-trivial and becomes more difficult as you examine it more closely).

I think that this kind of student assignment is a big reason why nearly everyone exposed to Prolog concludes that it is an academic toy. I mean, really now, successor arithmetic? Instead, I suggest teaching Prolog (and have done so) with small interactive graphical programs, filters in the style of Software Tools, or question-answering systems with facts of a practical nature, such as computer configurations or medicine interactions. Examples like these leave students with the strong impression that Prolog can get you to a practical, finished, tool faster than most other languages. That is the message we want to communicate.

In fact, the zebra problem is about the only puzzle that I like because it contains such a varied and unlikely collection of information. It strongly suggests how to create an application which must deal with a very complex set of relationships. Even so, one must make sure that the duller students make the connection between the Zebra problem and airline or classroom schedulers (come to think of it, maybe a classroom scheduler is too "academic" :-). N-queens on the other hand strikes me as hopelessly game-specific. In fact, it doesn't even have that much to do with chess! The sad fact is that poorly chosen examples can send the wrong message about Prolog.

Even talking about permutation sort does a major disservice to the cause of education. Quicksort is a perfectly acceptable way to present naive sorting. Showing programming students the permutation sort is the same as earnestly lecturing in a literature class on the monkeys who eventually write the books in the British Museum.

It is also very difficult to explain the declarative meaning of permutation sort. Intuitively, it doesn't seem declarative because the algorithm will only work in Prolog if you first permute and then test the order. Norbert Fuchs showed me that it does have a declarative model, in the form of a Herbrand model, but the level of sophistication needed to appreciate this is beyond most programmers.

I do agree that naive reverse is worth mentioning, but only as an example of bad Prolog programming. It is very likely that a beginning programmer would spontaneously write something like nrev/2.

I'm not saying that the discussion of reversible arithmetic wasn't interesting or worthwhile for comp.lang.prolog, just that Computer Science students are surrounded by editors, compilers, and operating systems written in C and if there only contact with Prolog is the N-queens and successor arithmetic, who can blame them for dismissing it as an academic novelty.

Peter B. Reintjes
IBM, T.J. Watson Research Center
P.O.Box 704, Yorktown Heights, NY 10598, USA
Email: reintjes@watson.ibm.com