;
;
per Definition gilt
.Aleph ist funktional. Eine wiederholte Feststellung, die des Beweises bedarf. In den folgenden Abschnitten wird eben dieser Beweis erbracht. Als Grundlage wird das gängiste und wohl am häufigsten bemühte Problem der Fakultät herangezogen.
Kaum ein Problem der Mathematik wird so oft benutzt um Rekursion zu zeigen. Weil genau das der Fall ist, werden auch hier einige Beispiele zu diesem Problem herangezogen. Diese Beispiele zeigen auch die elementaren Unterschiede zu herkömmlichen Sprachen.
Fakultät 5, oder 5! ist 5 * 4* 3* 2 *1. Der Algorithmus für n! ist:
;;
per Definition gilt.
Die Umsetzung in klassische Programmiersprachen ist so mit
int fak ( int n) {
if (n = 0)
return 1;
else return n * fak( n-1);
}
|
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 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"!
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 "x" is
x 0 = if 1 else x 1 - fak x * endif
"x" find if forget endif
;
|
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 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.
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 kompilierte Variable ist leer, weil die Zuweisung über "is" die Variable x betrifft, welche vor der "fak"-Definition bekannt ist.
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, weshalb genau n Einträge vorhanden sind wenn n! zu berechnen ist.
Auch "normale" Sprachen erzeugen bei jedem Rekursionschritt einen neuen lokalen Stack. Bei Aleph ist dieses Verfahren nur viel vordergründiger und fällt deshalb auch unerfahrenen Programmierer auf.
Dieser Weg erscheint nicht nur umständlich, er ist es auch. 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.
Irgendwie erscheint der gesamte 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 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.
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 (short) fak .
ergibt denn auch das Ergebnis 120. Das Casting mit (long) ist erforderlich, weil Aleph stets den kleinst mächtigen Datentyp der untergeordneten Maschine (JVM) 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 nicht mehr int, sondern 120.0. Weil Fakultät eigentlich nur für die Menge der natürlichen Zahlen mit 0, alsodefiniert ist und der Typ long die mächtigste (vordefinierte) Teilmenge von
und
ist, lautet die korrektere Definition
: 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 Stellen sind wenig aussagekräftig.
Wer es genauer haben möchte, programmiere einfach mit den BIG-Instanzen. Multiplikation uns Subtraktion sind als Methoden bereits vorhanden, nur die Stellenanzahl muss festgelegt werden.