Kurs:Programmieren in Aleph/Rekursion

Rekursion

Aleph ist funktional. Eine wiederholte Feststellung, die des Beweises bedarf und der hier erbracht wird. Grundlage bildet wird das bekannteste Beispiel – die Fakultät. Auch hier werden sich die Unterschiede zu den herkömmlichen Sprachen zeigen.

Klassischer Ansatz

Fakultät 5, oder 5! ist 5 * 4* 3* 2 *1. Allgemein ist der Algorithmus für n!:

$n\in \mathbb {N} ;\;n!=fak\left(n\right)=1\cdot 2\cdot 3\cdot ...\cdot \left(n-1\right)\cdot n$

per Definition gilt:

$0!\ {\stackrel {\mathrm {def} }{=}}\ 1$

Die Umsetzung in klassischen Programmiersprachen ist mit

int fak ( int n) {
 if  (n = 0)
      return 1;
 else return n * fak( n-1);
}

schnell gemacht.

In diesen "herkömmlichen" Sprachen (Pascal, C, Java) finden Betrachtungen der Speichers kaum statt. Argumente (Parameter) werden als "call by value" angesehen (wehe dem Java-user), der Stack wird sowieso lokal erzeugt. Alles geht seinen informationstechnischen Gang, denn Rückgabe und Argument wurden als "int" vereinbart. Natürlich wird nach einigen Versuchen der Typus "long" verwendet.

Aleph kann das alles nicht. Zumindest wird dem Programmierer in Aleph mehr Überlegung abverlangt. Variablen und Methoden (Sammelbegriff für alle Unterprogramme) sind auch als Datenelemente verfügbar. Einen Stack für private Nutzung gibt es nicht (es sei denn, er wird vereinbart). In Aleph gilt als Aufruf nur der Name. Damit existiert nur ein "call by name"!

Erster, scheiternder Versuch

Der erste Versuch wird über die einfache Umsetzung der Prefix-Notation unternommen. Wegen der "fehlenden" Argumentliste wird die erforderliche Variable einfach lokal vereinbart.

: fak
    "x" variable             // Variable erzeugen (bei jedem Aufruf)
    "x" is                   // Fakultärswert "speichern"
    x 0 = if   1             // erste Benutzung der Variablen
          else x 1 - fak x * // zweite und dritte Benutzung
          endif
   "x" find if forget endif  // Variable vergessen
  ;

Das Ergebis ist ernüchternd. Gleich dreimal wird das Objekt 'x' als unbekannt angesehen:

Command 'x' is unknown.

Wie kann das sein? Die Variable 'x' wird doch vor ihrer Benutzung definiert. Warum ist sie in der folgenden Zeile unbekannt?

Hier tritt der eigentliche Unterschied von Aleph zu anderen Sparachen hervor. Die Compiler "herkömmlicher" Sprachen arbeiten mit vagen Annahmen. Eine lokale Variable wird erst einmal als existent angenommen. In irgend einem der weiteren Durchläufe wird die Korrektheit der Variablen (Typus) überprüft. Aleph geht dagegen von harten Fakten aus. Ein "Etwas" namens "x" soll benutzt werden. Der colon-Compiler geht also von der Existenz dieses "Etwas" aus. Jedoch wird die Variable "x" erst beim Start von "fak" erzeugt. Zur Zeit der Kompilierung existiert kein "x" und der Colon-Compiler gibt eine entsprechnde Fehlermeldung aus.

Die Lösung erscheint einfach. Die Variable muss vor der Compilierung von "fak" vorhanden sein.

Zweiter, scheiternder Versuch

Kompilierung in Aleph geht von der Existenz eines Objektes aus. Sicher ist ein Objekt vorhanden, wenn es einen Namen hat – sollte die schlüssige Annahme sein. Also kann doch einfach die entsprechende Variable vor der Kompilierung erzeugt werden.

"x" variable
: fak
    "x" variable "x" is
    x 0 = if 1 else x 1 - fak x * endif
   "x" find if forget endif
  ;

Der colon-Compiler kennt also ein "Etwas" namens "x". Die Kompilierung erfolgt nun auch ohne Probleme. Der Start über

3 fak .

liefert jedoch keine Ausgabe. Wird die GUI beendet, erscheint im Protokoll-Fenster eine "lllaaannngggeeeee" Fehlermeldung. Sie ist, wie alle derartige Meldungen, wenig aussagekräftig. Wichtig sind nur die ersten Zeilen.

Errors:
java.lang.NullPointerException

Der ganze Rest der Meldung beschäftigt sich mit der Verfolgung dieser Meldung. Dabei sind außer den Entwicklern von Java selbst sind nur Wenige an der Tatsache interessiert, dass in der Zeile 1839 des ActionEvents eines abstrakten Buttons die Ausnahme

javax.swing.AbstractButton$ForwardActionEvents.actionPerformed(AbstractButton.java:1839)

entstand, wie aus der Meldung zu entnommen werden kann.

Irgendwie ergibt die Verwendung der Variablen "x" ein "null"-Objekt. Weitere Überlegungen bringen auch schnell die Ursache hervor, denn die Kompilierung von x ist eine "Referenz" auf die freie (leere) Variable x, die außerhalb von "fak" deklariert wurde. Die kompilierte Variable ist ungebunden. Sie wird aber in der Relation vor "if" benutzt und liefert - nein, nicht "null", sondern gar nichts. Ihre Benutzung hat wortwörtlich nichts gemacht, auf dem Stack liegt kein Vergleichswert. Die Zuweisung über "is" betrifft erst die Variablen, die innerhalb der "fak"-Sequenz erzeugt werden.

Rekursion scheint "nicht das Ding" von Aleph zu sein. Die Variablen sind schwieriger zu benutzen und für den lokalen Einsatz völlig ungeeignet. Deshalb hier eine

Aufgabe:

Wie müssen lokale Variablen aufgebaut sein, um sie in herkömmlicher Art und Weise zu benutzen?

Dritter, funktionierender Versuch

Statt von Annahmen auszugehen sollte lieber von Kenntnis ausgegangen werden. Denn Aleph kennt nur, was auch einen Namen hat. Unbekannt im Sinne von namenlos ist die Variable x. Wird sie über ihren Namen verwendet (called by name), kann auch der colon-Compiler die erforderlichen Voraussetzungen erstellen. Die Definition der Variablen bleibt erhalten, jedoch erfolgt die Verwendung über den Namen.

: fak
   "x" variable "x" is
   "x" find if execute endif
   0 = 
   if   1 
   else "x" find if execute endif
        1 - fak 
        "x" find if execute endif
        * 
   endif
   "x" find if forget endif
  ;

Diese "Lösung" arbeitet einwandfrei. Wichtig ist dabei die letzte Zeile, denn sie entfernt die während der rekursiven Aufrufe von "fak" gemachten Definitionen von x. Diese werden bei jedem Aufruf neu erstellt. Das Command "find" begnügt sich mit dem zuletzt gemachten Eintrag. Bei n Rekursionen sind auch n Variablen vorhanden. Das Command kehrt n mal zurück und entfernt jedesmal eine Variable.

Auch "normale" Sprachen erzeugen bei jedem Rekursionschritt einen neuen lokalen Stack. Bei Aleph ist dieses Verfahren nur viel vordergründiger und fällt deshalb dem unerfahrenen Programmierer schwer. Insgesamt erscheint dieser Weg nicht nur umständlich, er ist es auch.

Scheinbare Verbesserung

Statt dreimal die Variable "x" über ihren Namen aufzurufen, wird einfach ein entsprechendes Command namens "get" erstellt.

: get
   find if execute endif
  ;

: fak
   "x" variable "x" is
   "x" get
   0 = 
   if   1 
   else "x" get
        1 - fak 
        "x" get
        * 
   endif
   "x" find if forget endif
  ;

Die Sequenz für "fak" erscheint jetzt zwar kürzer, aber ihre Ausführung benötigt mehr Zeit. Jetzt muss statt der einfachen Sequenz immer das Command "get" aufgerufen werden, was natürlich Zeit für die Verwaltung beansprucht. Das eigentliche Problem wurde nicht beseitigt, denn es werden immer noch neue Variablen für jeden Rekusionsschritt erzeugt.

Aufgabe:

Ist das umständliche Vorgehen bei der Verwendung lokaler Variablen allein durch die Rekursion bedingt?

Nein. Auch in der "normalen" Verwendung ist das so, nur wird es durch den Compiler kaschiert.
Ja. Denn es muss ja immer die "letzte" Variable benutzt werden.
Nein. Lokale Variablen müssen immer so umständlich verwendet werden.

Neuer Ansatz

Irgendwie erscheint der gemachte Ansatz umständlich. Diese Erkenntnis resultiert aber nur aus dem (neuen) Wissen um die Arbeitsweise herkömmlicher Compiler. Diese Arbeitsweise wurde durch den anfänglich gemachten Ansatz praktisch für Aleph erzwungen. Die "Richtung" der mathematischen Formulierung wurde einfach umgekehrt (wozu gibt es das Assoziativgesetz?), nur um die Funktion immer wieder neu mit geänderten Argumenten aufzurufen. Dieser Weg ist bequem, langsam und wenig effektiv. Nicht nur in Aleph.

Aleph verarbeitet vorhandene Daten direkt. Wenn eine Sequenz eine bestimmte Anzahl von Datenelementen benötigt, wird auch genau diese Anzahl benutzt. Es ist daher unnötig, diese Elemente erst aus Variablen zu entnehmen, sie in neu angelegten Bereichen zu speichern, den belegten Speicher wieder freizugeben, nur um das Ergebnis einer weiteren Variablen abzulegen. Der Aufwand an Verwaltung ist immens.

Freiheit für die Programme, nieder mit den Variablen!

Übersetztes Zitat: Rochester Forth Conference 1987

Aleph ist im Ansatz frei von Variablen. Die einfache Lösung dieses rekursiven Problems erfolgt denn auch ohne Variablen mit.

: fak
   dup 
   0 = 
   if   drop 1 
   else dup  1 - fak * 
   endif
  ;

Ein Test mit

5 (long) fak .

ergibt denn auch das Ergebnis 120. Das Casting mit (long) ist erforderlich, weil Aleph stets den kleinst mächtigen Datentyp der untergeordneten Maschine (Java) wählt. Bei 5 ist das eben byte und nicht short. Es funktioniert aber auch mit 5.0 fak . Das Ergebnis ist dann natürlich 120.0 und damit falsch! Es gibt keine Fakultät außerhalb der natürlichen Zahlen, denn im klassischen Ansatz ist der Definitions- und (weil nicht explizit genannt) auch der Wertebereich auf diese Zahlenmenge beschränkt. In der Programmierung stören derartige Feinheiten aber nur. Also einfach das Casting ins Command

: fak
   (long)
   dup 
   0 = 
   if   drop 1 
   else dup  1 - fak * 
   endif
  ;

Hier ist mit 20! Schluss.

Wird ein Casting nach (double) durchgeführt, geht zwar noch 170!, aber 16 angezeigte von insgesamt 307 signifikanten Stellen sind wenig aussagekräftig. Wer es genauer haben möchte, programmiere einfach mit den BIG-Instanzen. Multiplikation und Subtraktion sind als Methoden bereits vorhanden, nur die Stellenanzahl muss festgelegt werden.

Zusamenfassung

Es zeigt sich, dass Aleph mit Ansätzen aus der herkömmlichen Programmierung zwar "zurechtkommen" kann, aber nur unzureichend. Alle versteckten Maßnahmen der Verwaltung von Variablen (lokal oder nicht) werden aufgedeckt und müssen umgesetzt werden. Der zweite Ansatz zeigt dann wie einfach die Umsetzung ist, wenn die Gegebenheiten von Aleph berücksichtigt werden.

Zum Abschluss dieses Abschnitts kann gesagt werden:

Lokale Variablen sind möglich.
Platzhalter ist nicht der Anspruch von Aleph-Variablen.
"Denken in Aleph" führt meist zu einfacheren und effektiveren Lösungen.
Daten sind stets "verpackt", sie in Variablen abzulegen bedeutet Verwaltung.

Probleme sollten stets so angegangen werden, dass erst die Systematik von Aleph und dann die der herkömmlichen Programmierung betrachtet werden.

„Kurs:Programmieren in Aleph“

<< ein Compiler | Rekursion | Infix-Notation >>