Kurs:Programmieren in Aleph/Mit Aleph Probleme lösen

Aus Wikiversity

Mit Aleph Probleme lösen[Bearbeiten]

Die bis jetzt gezeigten Beispiele waren vielleicht für elementare Formulierungen hilfreich, echten Nutzen hatten sie kaum. Das "Denken in Aleph" ist noch schwierig. Konventionelle Sprachen sind geläufiger, einfacher zu lesen und überhaupt war alles bisher in Aleph irgendwie umständlicher.

Es fehlt ein echtes Problem, dessen Lösung in Aleph von eingetretenen Pfaden abweicht. Ein, im wahrsten Sinne der Wortes, echtes Schulbeispiel wird hier gegeben. Es entstand aus einer Präsentation von Aleph vor Schülern und einem anschließenden Kurs. Die Gruppe verband der Leistungskurs Mathematik und das geringe Interesse an Informatik. Als Problem wählte der Kurs das "nervige Problem der römischen Zahlen" (O-Ton der Schüler) gewählt. Es gehört praktisch in jeden Informatikunterricht.

Nach einiger Zeit wurde als Lösungsvorschlag ein Entwurf präsentiert, der an Einfachheit selbst die Kursleiter verblüffte. Die Schüler hatten die Idee das "Wissen" um die Zahlendarstellung zu programmieren und so die römische Zahl selbst als Programm zu verwenden.

Ergänzende Worte[Bearbeiten]

Die folgenden Punkte zeigen andere Ansätze zur Problemlösung. Es gibt kein Problem das durch die Entscheidung für einen bestimmen Lösungsweg nicht noch komplizierter werden kann. Im Folgenden wird hier ein Weg beschrieben, der in herkömmlichen Sprachen nicht gangbar ist. Es ist nicht nach einer eleganten Lösung und auch nicht nach einer kurzen gesucht. Es wird eine unkonventionelle Lösung präsentiert. Am auffälligsten ist dabei nicht der Code oder die Vorgehensweise, sondern die Herangehensweise. Hier liegt der seltene Fall vor, dass die Aufgabe bereits die Lösung ist. Deshalb fällt es schwer nach alternativen Ansätzen zu suchen und deshalb lohnt der relative Mehraufwand in der Vor- und Nachbereitung.

Natürlich hätten reguläre Ausdrücke in Kombination mit Fallunterscheidungen und/oder StringTokenizer mit StringBuffern wahrscheinlich zu einer kompakteren Lösung geführt. Aber dann hätten sehr mehr Kenntnisse in der Java-Programmierung vorhanden sein müssen. Die Herangehensweise wäre auf die Programmiersprache fixiert und nicht auf das Problem selbst. Das Ziel, die Maschine als reines Hilfsmittel zur Realisation eigener Vorstellungen einzusetzen, wäre verfehlt worden. Die Aversion gegenüber dem Programmieren geblieben.

Römische Zahlendarstellung[Bearbeiten]

Statt einen lexikalischen Scanner für die römischen Ziffern zu diskutieren, wurden die Zahlen in einem "größeren Zusammenhang" gesehen; ähnlich dem Betrag eines Schecks "in Worten". "Da steht eigentlich immer eine Addition mit und statt plus.", wie es ein Schüler formulierte.

Römische Zahlen bestehen zwar aus Ziffern, aber manchmal muss subtrahiert statt addiert werden. Wenn aber bestimmte "Zerlegungen" benutzt werden, ist nur noch die Addition erforderlich. Diese Zerlegungen stellen das "Wissen" dar und werden als Comands programmiert.

Die Zahl "MVII" wird zerlegt in "M" und "VII". Weil vor über 2000 Jahren die Null als Zahlenwert unbekannt war, ergibt sich folgender Lösungsansatz:

: M   1000 + ;
: VII    7 + ;

0 M VII .

Die Idee ist, die Fragmente im Eingabestring zu erkennen und um ein Leerzeichen zu erweitern. Mit dem vorprogrammierten Wissen der einzelnen Fragmente steht die um Leerzeichen erweiterte Zahl als fertiges Programm bereit.

Aufgabe:

Gibt es Parallelen zu heutigen Zahlenangaben?

Die Zerlegung[Bearbeiten]

Normalerweise verlangt eine Zerlegung dieser Art die Einbeziehung von Indizes. Sonst könnte bei "MMVII" nicht zwischen dem ersten und zweiten "M" unterschieden werden. Trotzdem gelang es, auf Indizierung zu verzichten. "Einfach alle groß geschriebenen durch klein geschriebene Fragmente ersetzen." lautete die nächste Idee.

Aus "MVII" wird einfach "m vii". Die entsprechenden Comands müssen dann natürlich ebenfalls klein geschrieben werden. Die Methode "toLowerCase()" ist in jeder String-Instanz. Sie kann direkt auf das oberste Stackelement angewendet werden, wenn es ein String ist. An das klein geschriebene Fragment wird noch ein Leerzeichen angehängt und das Command

: lowcase
   dup                     // STR     --> STR STR
   "toLowerCase { }" call  // STR STR --> str STR
   " " +                   // str STR --> str STR
  ;

ist fertig. Auf dem Stack liegen nun das zu ersetzende Fragment und darüber der klein geschriebene Ersatz.

Damit auch alle Vorkommen eines Fragments ersetzt werden, wird die Methode "replaceAll(...)" auf den String "rom" mit der römischen Zahl angewendet. Auch diese Methode ist Bestandteil jeder String-Instanz und kann deshalb sofort angewendet werden.

: replace
   "replaceAll {String String}" call // rom str STR --> rom
  ;

Mit diesen beiden Commands ergibt sich aus der Eingabe

"M" lowcase "MMVII" replace .S

Die Ausgabe

Stack = [ m m VII ]

Jetzt kam den Schülern ein weiterer Einfall, der den Kursleitern ein "Gefühl des vorgeführt werdens" gab. Der Aleph-"loop" wurde bereits besprochen und es wurde eine mühselige Separation der zu ersetzenden Fragmente aus einer Liste oder einem Array erwartet. Die Schüler dachten überhaupt nicht daran. Sie legten einfach eine 0 (Null) und dann alle möglichen Fragmente auf den Stack. In einem "loop" werden die einzelnen Fragmente "abgearbeitet", bis die Null erreicht ist. "Die brauchen wir sowieso." lautete die Mitteilung an die Kursleiter.

Der Test auf Null stieß auf Schwierigkeiten. Ein Vergleich von Zahl und String schlägt fehl. Die Kursleiter wussten Rat und schlugen die Methode "toString()" vor. Wenn die Zahl 0 vorhanden ist liegt hinterher der String "0" vor. Ist es ein String, liegt er hinterher eben wieder vor. Der Vergleich erfolgt dann statt auf 0 eben auf "0". Es dauerte, die entsprechenden Reihenfolge der Elemente zu erstellen, aber dann sah es so aus:

rom ist die römische Zahl.
FRG...0 sind die möglichen Fragmente bis zur 0 (Null).
FRG/0 ist eines der möglichen Fragmente oder 0 (Null).
FRG ist eines der möglichen Fragmente.
frg ist ein klein geschriebenes Fragment.
: lowcase
   dup                     // STR     --> STR STR
   "toLowerCase { }" call  // STR STR --> str STR
   " " +                   // str STR --> str STR
  ;

: replace
   "replaceAll {String String}" call // rom str STR --> rom
  ;

: test
   loop
    swap            // rom FRG...0         --> FRG rom FRG...0
    lowcase         // FRG rom FRG...0     --> frg FRG rom FRG...0
    swap            // frg FRG rom FRG...0 --> FRG frg rom FRG...0
    1 nswap         // FRG frg rom FRG...0 --> rom FRG frg FRG...0
    replace         // rom FRG frg FRG...0 --> rom FRG...0
    1 ndup          // rom FRG...0         --> FRG/0 rom FRG...0

 // *-------------------*
 // * Vergleich auf "0" *
 // *-------------------*

    "toString { }" call
    "0" =           // FRG/0 rom FRG...0   --> flg rom FRG...0

    leave           //                     --> rom 0
   endloop          //                     --> rom FRG...0
  ;                 //                     --> rom 0

0
"I" "II" "III"
"V" "IV" "VI" "VII" "VIII"
"X" "IX" "XX" "XXX"
"L" "XL" "LX" "LXX" "LXXX"
"C" "XC" "CC" "CCC"
"D" "CD" "DC" "DCC" "DCCC"
"M" "CM"

"MMVII" test .S

Die Anzeige ist

Stack = [ "m m vii " 0 ]

"Das als Eingabe für Aleph erklären und die Aufgabe ist gelöst." war die korrekte Feststellung. Der Kurs war sowieso beendet und Mathematiker (auch Solche in spe) begnügen sich mit der (bewiesenen) Feststellung: "ist lösbar".

Aufgabe:

Ist hier bereits die Lösung vorhanden?

  1. Nein. Aber Mathematiker sagen schnell "ist lösbar", ohne weitere Erläuterung.
  2. Ja. Weil der String eine ausführbare Sequenz ist und mehr war nicht verlangt.
Aufgabe:

Warum wird das "call"-Command für die Manipulationen der Strings verwendet und nicht eine Methode definiert?

Sequenzen aus beliebigen Quellen ausführen[Bearbeiten]

Als beliebige Quellen sind in Aleph alle Objekte gemeint, die der Klasse Reader genügen. Damit ist praktisch alles was Bytes liefert lesbar. Vom Array mit Zeichen, über den String bis zur URL-Verbindung. Hier ist es eben ein String.

Aktuelle Quelle sichern[Bearbeiten]

Wenn die Sequenz im String (oder einer anderen Quelle) abgearbeitet wurde, sollte wieder die ursprüngliche vorhanden sein. Herkömmliche Programme werden also eine Variable zur Speicherung nutzen. Das ist nicht ohne Probleme. Was wenn die Sequenz wieder die Quelle ändert um noch eine Sequenz auszuführen. Und diese dann wieder usw.

Generell gilt in Aleph: Auf den Stack damit!

Die Quelle aller Eingaben ist Bestandteil der virtuellen Maschine von Aleph – der V2M. Es ist ein Java-Programm und der Name des Fields lautet "inp". Die Instanz der gerade arbeitenden V2M wird mit dem Command "environment" bereitgestellt. Also übergibt

"inp" environment fetch  // --> reader

den Inhalt des Fields auf dem Stack. In der gegenwärtigen Situation ergibt sich auf dem Stack "reader rom 0". Der "reader" muss nach unten, denn er wird ja erst nach Abarbeitung der Sequenz in "rom" wieder an die V2M zurückgegeben. Damit ergibt sich

"inp" environment fetch  // rom 0        --> reader rom 0
1 nswap                  // reader rom 0 --> 0 rom reader
swap                     // 0 rom reader --> rom 0 reader

Alte Quelle wiederherstellen[Bearbeiten]

Der "reader" ist erst mal gesichert. Aber er muss auch wieder zurück. Nach der Sequenz in "rom" muss der "reader" an des Field "inp". Die Sequenz in "rom" liefert den Zahlenwert "value" auf dem Stack. Die Befehlsfolge um den "reader" an die V2M zurückzugeben ist

swap                    // value reader --> reader value
"inp" environment store // reader value --> value

Leider wird diese Befehlsfolge nie ausgeführt, denn sie kann nicht gelesen werden. Aleph liest nur den String "rom" und nachdem der Wert der römische Zahl feststeht gibt es nichts mehr zu lesen. Die Befehlsfolge muss also irgendwie an die Sequenz in "rom" angehängt werden bevor sie ausgeführt wird.

"swap \"inp\" environment store" // rom 0    --> str rom 0
+                                // str rom 0 --> seq 0

Auf dem Stack liegt jetzt ein String mit der Sequenz aus der römischen Zahl und der Befehlsfolge den gesicherten "reader" an die V2M zurückzugeben. Ganz genau sieht das Stringobjekt mit der Befehlsfolge "seq" so aus:

"m m vi swap \"inp\" environment store"

Sollten jetzt Schwierigkeiten m Verständnis auftreten, weil der "reader" auf dem Stack nicht (mehr) vorhanden ist, war das beabsichtigt. Der "reader" ist noch gar nicht auf dem Stack. Bisher wurde erst überlegt

  1. wie kommt der "reader" auf den Stack?
  2. wie kommt der "reader" zurück zur V2M?

Zusamenfassung[Bearbeiten]

Beide Überlegungen müssen getrennt erfolgen, denn die Sequenzen befinden sich in unterschiedlichen Bereichen der Verarbeitung. Punkt-2 wurde geklärt und im String "seq" auf dem Stack. Der erste Punkt muss nun so gelöst werden, dass er mit dem in "seq" formulierten zusammen arbeitet. Das "etwas andere Denken" in Aleph wird jetzt deutlicher.

  1. Elementare Commands realisieren.
  2. Stack mit Initialisierung belegen.
  3. Eingabe in Commands wandeln und in einem Objekt zusammenfassen.
  4. Objekt um Rückspeichern des Eingabebereichs erweitern.
  5. Aktuellen Eingabebereich sichern.
  6. Objekt mit Commands zum neuen Eingabebereich erklären.
  7. Commands im Objekt ausführen.

Dieses komplizierte Vorgehen muss einmal nachvollzogen werden. Es ist so etwas wie die Voraussetzung zum Verstehen der letzten Vereinfachung. Hier also die Schritte im Quelltext:

// ***********************
// * Elementare Commands *
// ***********************

: cm   900 + ; : m   1000 + ;
: dccc 800 + ; : dcc  700 + ; : dc   600 + ; : cd   400 + ; : d 500 + ;
: ccc  300 + ; : cc   200 + ; : xc   90 + ;  : c    100 + ;
: lxxx 80 + ; : lxx  70 + ; : lx   60 + ; : xl   40 + ;     : l  50 + ;
: xxx  30 + ; : xx   20 + ; : ix    9 + ; : x    10 + ;
: viii  8 + ; : vii   7 + ; : vi    6 + ; : iv    4 + ;     : v   5 + ;
: iii   3 + ; : ii    2 + ; : i     1 + ;


// *******************
// * Initialisierung *
// *******************

: init
   0
   "I" "II" "III"
   "V" "IV" "VI" "VII" "VIII"
   "X" "IX" "XX" "XXX"
   "L" "XL" "LX" "LXX" "LXXX"
   "C" "XC" "CC" "CCC"
   "D" "CD" "DC" "DCC" "DCCC"
   "M" "CM"
;


// ********************************
// *  Eingabe in Commands wandeln *
// ********************************

: commandobject
   loop
    swap                              // rom FRG...0         --> FRG rom FRG...0
    dup                               // FRG rom FRG...0     --> FRG FRG rom FRG...0
    "toLowerCase { }" call " " +      // FRG FRG rom FRG...0 --> frg FRG rom FRG...0
    swap 1 nswap                      // frg FRG rom FRG...0 --> rom FRG frg FRG...0
    "replaceAll {String String}" call // rom FRG frg FRG...0 --> rom FRG...0
    1 ndup                            // rom FRG...0         --> FRG/0 rom FRG...0
    "toString { }" call "0" =         // FRG/0 rom FRG...0   --> flg rom FRG...0
    leave                             //                     --> rom 0
   endloop                            //                     --> rom FRG...0
  ;                                   //                     --> rom 0


init              // 0 (Null) und alle Fragmente auf den Stack legen.
word MMVII   drop // Römische Zahl direkt aus Stream lesen                //              --> rom
commandobject     // Umwandeln der römischen Zahl in eine Command-Sequenz // rom          --> seq 0

// *-----------------------*
// * Sichern des "readers" *
// *-----------------------*

"inp" environment fetch // Reader der V2M auf den Stack // seq 0        --> reader seq 0
1 nswap swap            // Reader ganz nach unten       // reader seq 0 --> seq 0 reader

// *----------------------*
// * seq-Objekt erweitern *
// *----------------------*

"swap \"inp\" environment store" + // Sequenz zum rückspeichern des readers  // "m m vi " 0 reader --> "m m vi swap "inp" environment store" 0 reader

// *------------------------------------*
// * seq zum neuen Eigabebereich machen *
// *------------------------------------*

environment "reader {Object}" call // seq 0 reader            --> SEQUENCEreader 0 reader
"inp" environment store            // SEQUENCEreader 0 reader --> 0 reader

// *-----------*
// * Ausführen *
// *-----------*

environment "process { }" call     // 0 reader --> value

Ein großer Aufwand der Vor- und Nachbereitung. Trotzdem lohnt es sich. Denn jetzt wird noch die versprochene Vereinfachung gezeigt.

Einfach noch eine Maschine[Bearbeiten]

Die Aufgabe war eigentlich mit "commandobject" gelöst. Die Sicherung und Rückgabe des "readers" war jedoch fast ebenso umfangreich wie die eigentliche Aufgabe. Es geht auch anders.

Statt den "reader" zu sichern kann auch einfach eine neue V2M-Instanz erzeugt werden. Diese nutzt den vorhandenen Stack und das oberste Element als Eingabe. Mit Abarbeitung des obersten Objekts übergibt die neue V2M die Kontrolle an die alte und entfernt sich.