Kurs:Programmieren in Aleph/Grundlagen Listprocessing

Listprocessing in Aleph

Aleph besitzt auch Fähigkeiten der Listenverarbeitung. Die Datei "lists.vvm" stellt die Commands für ein Listprocessing bis zur Unification bereit. Weil Aleph-Variablen auch mit Listen "klarkommen" (sie können ungebunden sein), ist es bestimmt interessant hier mehr zu machen. Weil Aleph noch relativ "jung" aber trotzdem recht verbreitet ist, werden entsprechende Erweiterungen ncht lange auf sich warten lassen.

Die Listenverarbetung ist in einer Aleph-Datei "lists.vvm" vorhanden. Nach dem "laden" werden einige Anweisungen ausgeführt. Sie dienen nur zur Überprüfung der Funktionsfähigkeit. Einfach entfernen, um nicht jedesmal mit einer Demonstration des Listenverarbeitung belästigt zu werden.

Aufbau einer Liste

Die Anweisung zur Erstellung einer Liste lautet einfach "list". Der Aufbau erfolgt direkt aus der Eingabe. Um Listen als Text zu formulieren, müssen Regeln vorhanden sein. Diese Regeln beschreiben Anfang und Ende von Listen und die Unterscheidung der enthaltenen Elemente.

" ( " ist Listenanfang (Leerzeichen nicht vergessen).
" ) " ist Listenende

Jede andere Zeichenfolge ist ein atomares Element. Atomare Elemente sind Zeichen(ketten). So bleibt die Flexibilität von Aleph innerhalb der Listen bestehen. Nur der Aufbau (die Struktur) von Listen unterliegt der allgemeinen Syntax des Listprocessings.

Eine sehr wichtige Eigenschaft von Listen ist ihre Fähigkeit Listen als Elemente zu enthalten. Diese Elemente sind dann natürlich nicht mehr atomar. Der Begriff atomar wird im Abschnitt "Listen zerlegen" genauer besprochen. Listen können leer sein, sie enthalten dann einfach keine Elemente.

list ( a b c )
list ( )
list ( a ( 1 2 ) b c )

Diese Zeilen erzeugen drei Listen und legen sie auf dem Stack ab. Um eine Liste anzuzeigen ist die Anweisung "show" vorhanden. Für das "."-Command (dot) ist eine Liste nur ein Objekt und die Ausgabe wird dann entsprechend "kyptisch" ausfallen.

Aufgabe:

Wie wird eine Liste erzeugt?

Mit dem Command "list?
Durch das syntaktische Zeichen "("?
Durch die Kombination aus "list und das unmittelbar folgende Zeichen "("?
Durch die Kombination aus "list und "("?

Listen zerlegen

Für Listen gilt eine sehr einfache Definition ihres Aufbaus. Eine Liste ist leer oder nicht. Wenn sie nicht leer ist, besteht die aus einem Kopf (head) und einem Schwanz (tail). Für eine komplette Zerlegung sind zwei Anweisungen erforderlich. Mit "head" wird der Kopf einer Liste ermittelt, mit "tail" der Schwanz.

list ( X Y Z ) dup dup
"Liste " . show "
hat den Kopf " .
head show
" und den Schwanz " .
tail show

Die oben stehende Eingabe erzeugt die Ausgabe

Liste ( X Y Z )
hat den Kopf X und den Schwanz ( Y Z )

In Prolog wird das Aufspalten einer Liste in Kopf und Schwanz über den Operator "|" erreicht. In Aleph erfolgt sie einfachüber das Command "split". Die folgenden Sequenzen zeigen im Ergebnis den "|"-Operator aus Prolog als Trennzeichen zwischen Kopf und Schwanz.

list ( ( A B ) C )
dup "Liste " . show " \"gesplittet\" " .
split show "|" . show

ergibt:

Liste ( ( A B ) C ) "gesplittet" ( A B )|( C )

Um ein "Gefühl" für die Arbeit mit Listen zu bekommen, noch ein paar Eingaben.

list ( ( X Y Z ) ) dup "Liste " . show " \"gesplittet\" " .
split show "|" . show

hat in der Anzeige

Liste ( ( X Y Z ) ) "gesplittet" ( X Y Z )|( )

zur Folge. Der Kopf einer Liste kann wieder eine Liste aber auch ein Atom sein. Der Schwanz ist immer eine Liste. Deshalb kann eine leere Liste auch nicht in zwei Teile zerlegt werden, wohl aber eine Liste die mit einer leeren Liste enthält.

list ( ( ) ) dup "Liste " . show " \"gesplittet\" " .
split show "|" . show

In der Ausgabe findet sich denn auch

Liste ( ( ) ) "gesplittet" ( )|( )

Die Kombination von Listen und Variablen kann zu sehr leistungsfähigen Anwendungen führen. Weil Aleph-Variablen mit gleichen Namen mehrfach erzeugt werden können und sich trotzdem voneinander unterscheiden (siehe Beispiel Rekursion in Aleph), kann die Unifikation sehr einfach realisiert werden. Zweifellos werden die folgenden Versionen von Aleph mehr zum Thema Listen bereitstellen.

Aufgabe:

Was bedeutet das Zeichen " $|$ " in Aleph?

Es trennt den Kopf iner Liste von ihrem Schwanz?
Es hat überhaupt keine Bedeutung in Aleph?
Es veranschaulicht die mögliche Trennung von Kopf und Schwanz?

Die Commands der Listenverarbeitung

Die Erstellung und Verarbeitung von Listen benötigt Syntax. Diese Voraussetzung ist Aleph zunächst fremd. Deshalb existieren zwei Fehlermeldungen. Es handelt sich um reine Mitteilungen, ohne weitere Konsequenzen. Die Feststellung, ob eine Meldung ausgegeben wird ist Aufgabe der betroffenen Commands.

Dieses abweichende Verhalten von Aleph ermöglicht es, eigene Erweiterungen in die meldenden Commands zu integrieren. So können auch Maßnahmen zur Korrektur oder alternativen Sequenzen programmiert werden. Die hier vorgestellten Comands sind als Basis für weitere Programme gedacht.

Öffnen einer Liste

Jede Liste ist im Speicher der virtuellen Maschine V2M abgebildet. Die Organisation des Speichers ist selbst listenorientiert. Die Unterteilung des Speichers ist beliebig. Deshalb kann jede Liste als abgeschlossener Speicherbereich angesehen werden.

Der folgende Quelltext geht davon aus, dass ein "("-String auf dem Stack liegt. Es handelt sich um eine syntaktische Zeichenkette, zu Einleitung einer neuen Liste. Deshalb ist das verantwortliche Element auch der Verarbeitung des folgenden Commands unterworfen.

: openList
   drop                               // "(" cnt  --> cnt      // Klammer-auf entfernen
   1 +                                // cnt      --> cnt      // Zähler für Listenelemente incrementieren
   "memory.List" classify instantiate // cnt      --> list cnt // Liste instaziieren
   swap                               // list cnt --> cnt list // Zähler an oberste Stelle des Stacks positionieren
;

Das Command "openList" erwartet auf dem Stack einen "("-String, der ja die neue Liste einleitet. Darunter wird ein Zähler erwartet, der die Tiefe der Verschachtelungen zählt. Er wird um 1 erhöht, weil das Öffnen einer neuen Liste in jedem Fall eine weitere Ebene der Verschachtelung edeutet. Danach wird ein Objekt der Kasse "List" erzeugt. Damit der Zaähler wieder ganz oben auf dem Stack liegt, werden die beiden obersten Elemente vertauscht.

Schließen einer Liste

Auch das Schließen einer Liste erfolgt über ein syntaktisches Element - ")". Der Zähler für die Verschtelungstiefe wird nun natürlich dekrementiert. Soweit besteht Übereinstimmung mit dem Öffnen. Wenn aber die jetzt geschlossene Liste selbst ein Element einer Liste ist, so muss es an die vorhandenen Elemente angehängt werden. Eine Liste ist immer dann ein Element einer Liste, wenn die Tiefe der Verschachtelung nicht nicht 0 (Null) ist.

: closeList
   drop      // ")" cnt list_n (... list_0)         --> cnt list_n (... list_0)
   1 -       // cnt list_n (... list_0)             --> cnt list_n (... list_0)
   dup 0 >   // cnt list_n (... list_0)             --> flg cnt list_n (... list_0)
   if
    swap     // cnt list_n (... list_0)             --> lobj cnt list_n-1 (... list_0) // Listenelement nach TOS
    append   // lobj list_n cnt list_n (... list_0) --> cnt list_n (... list_0)        // Listenelement anhängen
   endif
;

Die in dem Kommentarem als "(... list_0)" bezeichneten Objekte sind geöffnete, aber nicht abgeschlossene Listen. Sie werden der Reihe nach mit ")" geschlossen und als Elemente angehängt.

Aufgabe:

Welche Liste wird durch das Command "closeList" gschlossen?

Immer die Schwanzliste?
Immer die Kopfliste?
Immer die Innerste?
Immer die Äußerste?

Listen erweitern

Dieses Command erweitert Listen. Auf dem Stack muss das Objekt liegen, welches als Element in die Liste eingefügt werden soll. Darunter der Tähler für die Verschachtelungstiefe, gefolgt von der zu erweiternden Liste.

: append
   1 ndup                              // obj cnt list           --> cnt obj cnt list
   0 >                                 // cnt obj cnt list       --> flg obj cnt list
   if
    2 ndup                             // obj cnt list           --> list obj cnt list
    swap                               // list obj cnt list      --> obj list cnt list
    1 ndup                             // obj list cnt list      --> list obj list cnt list
    "append {memory.List Object}" call // list obj list cnt list --> cnt list
   else
    drop                               // obj cnt list           --> cnt list
    drop                               // cnt list               --> list
    err02                              // list                   --> list
   endif
;

Wenn die Tiefe der Verschachtelung 0 (Null) ist, kann zwar eine Liste vorhanden sein, aber sie ist geschlossen. An diese Listen kann kein Element angehängt werden. Natürlich ist diese Einschränkung rein syntaktisch. Jede Liste steht in Aleph zur Bearbeitung bereit, aber hier wurde der Listenaufbau einer Syntax unterworfen, die enau das verbietet. Deshalb ist hier auch die Fehlermeldung "err02" vorhanden.

: err02
   "No (valid) list for append." .
;

Sollte dieser syntaktische Fehler auftreten, befreit das Command den Stack vom Objekt und dem Zähler der Verschachtelungstiefe. Beide machen keinen Sinn und nur die abgeschlossene Liste bleibt zurück.

Neue Liste formulieren

Bis jetzt sind zwar die Commands zum Aufbau von Liste vorhanden, es fehlt aber eine Möglchkeit Listen "einzutippen". Dabei ist die Beachtung der Syntax das Wichtigste. Weil Listen rekursive Strukturen sind und die Behandlung der einzelnen Rekusionen allein Sache des Programms, ist hier nur die "Formulierung" wichtig. Tiefe der Rekursion(Verschachtelung), Listen- oder atomares Element unterliegt nur dem Programm und nicht der Eingabe.

: list
   0                        //                         --> cnt
   loop
    word                    // cnt (list)              --> flg (str) cnt (list)
    not if err01 exit endif // flg (str) cnt (list)    --> cnt (list)              // Nichts gelesen
    handleElement           // str cnt (list)          --> cnt list_n (... list_0) // Element behandeln
    dup 1 < leave           // cnt list_n (... list_0) --> cnt list_n (... list_0) // fertig?
   endloop
   drop                     // cnt list_n (... list_0) --> list_0                  // Zähler entfernen
;

Das Command "<tt<list gestattet die "Formulierung" einer neuen Liste. Der interne Aufbau, die Verkettung der Elemente, erolgt innerhalb einer Schleife. wenn der Zähler "cnt für die Tiefe der Verschtelung (Klammertiefe) 0(Null) ist, wird die Schleife verlassen, der Zähler entfernt und das Command beendet.

Die Formulierung ist rein textuell. Es werden solange "words" gelesen, bis die Tiefe der Verschschtelung 0 ist. Die Unterscheigung zwischen den möglichen Elementen wird im Command "handleElement" vorgenommen. Ist keine Zeichenfolge vorhanden, so liegt ein syntaktischer Fehler vor und das Command

: err01
   "No or incomlete input." .
;

gibt die entprechende Meldung aus.

Liste oder Atom

Die Formulierung einer Liste lässt drei Möglichkeiten zur Auswahl:

Atom
Irgendeine Zeichenfolge außer "(" oder ")".
Listenanfang
Genau die Zeichen(folge) "(".
Listenende
Genau die Zeichen(folge) ")".

Jede dieser drei Möglichkeiten verlangt unterschiedliche Handlungsweisen. Die Koordinierung übernimmt das Command

: handleElement
   dup "(" = if openList  exit endif // str cnt (list) --> cnt list_n (... list_0)
   dup ")" = if closeList exit endif // str cnt (list) --> cnt list_n-1 (... list_0)
   append                            // str cnt (list) --> cnt list_n (... list_0)
;

Es werden nur die bereits besprochenen Commands zum Öffnen, Erweitern und Schließen von Listen verwendet. Welches Connand benutzt wird ist abhängig von den beiden syntaktischen Elementen "(" und ")".

Aufgabe:

Welche der folgenden Aussagen sind richtig:

Die Elemente einer Liste sind stets Objekte.
Atome sind keine Elemente.
Listen 'können Elemente sein.
Ein Listenkopf ist immer ein Element.
Ein Listenschwanz ist immer ein Atom.
Eine leere Liste ist als Element ein Atom.

Anzeigen einer Liste

Für das Verständnis der Listenverarbeitung ist die Ausgabe einer Liste sehr wichtig. Die Besprechung wird sich an den Listen und nicht an der Speicheroganiastion orientieren. Die in der Datei "tt>lists.vm" vorhandenen Commands sind sehr detailiert und haben oft unmittelbarem Bezug auf die V2M-interne Speicherstrukturen. Sie zu besprechen würde wenig zum Verständnis beitragen.

Das Command

: showList
  "(" . content " )" .
;

zeigt den Inhalt (content) einer Liste an. Die syntaktischen Elemente "(" und ")" werden als String-Objekte dierekt in die Anzeige integriert. Die eigentliche Anzeige ist im Comand

: content
   empty? if drop exit endif  // list (tail)      --> list (tail)          // Wenn leer, dann fertig
   split                      // list (tail)      --> head tail (tail)
   list?                      // head tail (tail) --> flg head tail (tail)
   if
    " (" . content " )" .     // head tail (tail) --> list tail (tail)
   else
    " " . .                   // head tail (tail) --> tail (tail)
   endif
   empty?                     // tail (tail)      --> flg tail (tail)
   if
    drop exit                 // tail (tail)      -->  (tail)
   endif
   content                    // tail (tail)      --> tail (tail)
;

untergebracht. Der Ablauf ist schnell erklärt:

Ist die Liste leer (Command "empty?"), wird das Command beendet, denn es gibt nichts anzuzeigen.
Die Liste In "Kopf" und "Schwanz" zerlegen. Dabei liegt der Kopfganz oben auf dem Stack.

Ist der Kopf wieder eine Liste (Command "list?"), dann rekursiiver Aufruf dieses Commands mit den syntaktischen Elementen.

Ist der Kopf ein Atom, dann einfach mit führendem Leerzeichen anzeigen.

Ist die Liste leer Command beenden
Rekursiver Aufruf dieses Commands für den Schwanz. Diesmal ohne die syntaktischen Elemente.

Es zeigt sich, dass hier die klassische Vorgehensweise (Prolog, LISP) bei der Listenanzeige angewendet wird. Die Liste wird in Kopf und Schwanz aufgeteilt solange es geht. Nur die atomaren Elemente werden angezeigt. Die Notwendigkeit für Klammern wird aus dem Kontext ermittelt und die entsprechenden Zeichen direkt ausgegeben.

Kurze Zusammenfassung

Die Listenverarbeitung ist in Aleph sehr einfach. Es ist möglich beliebige Objekte in Listen zu organisieren. Daraus ergeben sich neue Möglichkeiten zur Programmierung von Abläufen. Für Beweissysteme stehen die Aleph-Variablen bereit, die ungebunden sein können. Die Möglichkeiten von Aleph sind durch die Listenverarbeitung sehr erweitert worden.

Es ist Zeit, ein paar tiefergehende Aufgaben zu stellen. Das hier eingeleitete Listprocessing ist noch nicht das Ende des Kurses. Eigentlich geht es jetzt erst richtig los, mit der Aleph-Programmierung.

Aufgabe:

Wenn es stimmt, dass Listen beliebige Objekte enthalten können, dann sollten die folgenden Punkte leicht zu bewältigen sein:

Aufbau einer Liste mit den Symbolen für 123, 45.67 und 987.
Addieren aller Elemente der eben aufgebauten Liste.

Sonst erklären warum die beiden Punkte nicht zu realisieren sind.

wird fortgesetzt

„Kurs:Programmieren in Aleph“

<< Infix-Notation | Grundlagen Listprocessing