MIT Scheme plus

Es ist Übung Nr. 1.9 im Buch "The Structure and Interpretation of Computer Programs", bei dem ich damals, als aufwachsendes Kind, das erste mal meine Liebe zu Computern spürte - vorhanden war sie schon vorher. Es geht in dieser Übung darum, zwischen zwei Implementationen einer Funktion, die nur mithilfe eines Inkrement-Operators und eines Dekrement-Operators das Addieren realisiert, zu entscheiden, welche iterativ, und welche rekursiv ist.

Dies wird im Dialekt Scheme der Programmiersprache Lisp realisiert.

Voller Ehrgeiz schaute ich also, welche MIT Scheme Implementation denn aktuell sei:

apt-cache search scheme | grep scheme

und erschrak:

mit-scheme - MIT/GNU Scheme development environment

Es existiert also noch immer die originale Implementation des MIT's im Debian Repository. Als ein

apt-cache show scheme

mir nun sagte, das die letzte Versionsnummer 7.7.90+20070909-1 sei, also ziemlich aktuell, fragte ich mich tatsächlich, was denn an dieser Implementation noch zu ändern sei...

Ich startete den Interpreter...

% scheme
MIT/GNU Scheme running under GNU/Linux
Type `^C' (control-C) followed by `H' to obtain information about interrupts.

Copyright (C) 1986, 1987, 1988, 1989, 1990, 1991, 1992, 1993, 1994,
1995, 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005,
2006, 2007 Massachusetts Institute of Technology
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

Image saved on Friday September 28, 2007 at 10:24:17 PM
Release 7.7.90.+ || Microcode 15.1 || Runtime 15.7 || SF 4.41
LIAR/i386 4.118 || Edwin 3.116

Ich starte die Programmierung folgendermassen:

Inkrement und Dekrement:	erste Variante:	zweite Variante:
(define (inc x) (+ x 1)) (define (dec x) (- x 1))	(define (plus a b) (if (= a 0) b (inc (+ (dec a) b))))	(define (plus2 a b) (if (= a 0) b (+ (dec a) (inc b))))

Man mache sich klar, wie simpel und doch genial zugleich diese Funktionen sind; zwar ist die rekursive Variante in diesem Beispiel unheimlich ineffizient, zeigt aber das Modell, bzw. den Geist einer Addition recht deutlich.

Sie macht es sich zunutze, das 4 plus 5 = 3 plus 6 = 2 plus 7 = 1 plus 8 = 0 plus 9 ist - und sagt sich - das wenn der linke Operand bei 0 angekommen ist, der rechte Operand das Ergebnis sein muss! Er zählt also den linken Operanden a solange herunter, während er den anderen hochzählt.

Die andere Funktion realisiert dies recht ähnlich.

Nun die Frage an die technisch interessierten Leser: Welche dieser Funktionen ist iterativ, welche rekursiv? Oder sind beide rekursiv bzw. iterativ?