Informatik-Kolloquium: Keller, Stack und automatisches Gedächtnis – eine Struktur mit Potenzial
Veranstaltungsort
Universität JenaFürstengraben 1
07743 Jena, Deutschland
Beschreibung
Ein Kolloquium der Friedrich-Schiller-Universität Jena und der Gesellschaft für Informatik
Zeitraum: 14.11.2014
Ort: UHG · Fürstengraben 1, Senatssaal
Programm
11:00 - 11:15 Uhr
Begrüßung
Prof. Dr. Birgitta König-Ries, Dekanin der Fakultät für Mathematik und Informatik der Friedrich-Schiller-Universität Jena
Prof. Dr. Thomas Wilke, Sprecher des GI-Fachbereichs "Grundlagen der Informatik"
11:15 - 12:00 Uhr
Der Keller - ein fundamentaler Baustein der Informatik
Prof. Dr. Martin Mundhenk, FSU
Die Datenstruktur Keller begegnet Informatik-Studierenden gleich am Beginn des Studiums als eine fundamentale informatische Denkweise. Wir machen einen Ausflug durch die Grundlagen der Algorithmik und sehen, wie ein Keller beim Auswerten von Formeln oder beim Durchsuchen von Graphen hilft. Neben einzelnen Algorithmen gibt es auch algorithmische Prinzipien, die auf dem Keller basieren. Das wird am Beispiel des Teile-und-Herrsche-Prinzips verdeutlicht.
12:00 - 12:45 Uhr
"Friedrich L. Bauers und Klaus Samelsons Arbeiten in den 1950er-Jahren zur Einführung der Begriffe Kellerprinzip und Kellerautomat"
Prof. Dr. Dr. h.c. Hans Langmaack, Christian-Albrechts-Universität zu Kiel
Schon 1955 (Dresdner Vortrag) ist aus Sicht der beiden Informatikpioniere Informationsaustausch zwischen verschiedenen Rechenzentren und -maschinen nur über höhere Programme (Pseudoprogramme) praktikabel und sinnvoll. Deren Sprache (universeller Pseudocode) sollte sich um die seit Jahrhunderten geläufige mathematische Formelsprache mit den bekannten Klammer- und Klammereinsparungsregeln ranken, und höhere Programme sollten sequentiell von links nach rechts (ohne Hin- und Herlesen) durch ein Übersetzerprogramm (einen Superplan) in Maschinencode übertragen (compiliert) werden können. Die bisher gelesenen und zunächst zurückgestellten und abgespeicherten Programmvorderteile, deren Symbole aus Operatoren und Operanden bestehen, werden dabei nur am obersten, rechtesten Ende verändert, ergänzt bzw. verkürzt. Ein in dieser Weise pulsierendes Speichern nennen die Autoren Kellern. Folgendes kennzeichnet Bauer-Samelsons Kellerprinzip und Kellerautomat: Jedes Paar <oberster Operator im Keller, gerade gelesenes Symbol> entscheidet über die nächstfolgende Handlung, d.h., ob und wie oberste Kellereinträge modifiziert werden, ob und welche Maschinenbefehle erzeugt oder diese bei auswertendem/interpretierendem Vorgehen gleich ausgeführt werden, ob weitergelesen wird oder ob der (Übersetzungs-/Auswertungs-)Prozess als erfolgreich beendet angesehen werden kann. Das Kellerprinzip wird zur Rechen- oder Laufzeit eines generierten Maschinenprogramms sichtbar in Gestalt des Laufzeitkellers, des sog. Zahlkellers bei Verarbeitung arithmetisch-logischer Formeln (Patentanmeldung 1957, Sequentielle Formelübersetzung 1959).
12:45 - 13:45 Uhr
Mittagspause
13:45 - 14:30 Uhr
"Wilhelm Kämmerers Ideen vom automatischen Gedächtnis"
Prof. Dr. Michael Fothe, Denny Steigmeier, FSU
Wilhelm Kämmerer habilitierte sich 1958 an der Friedrich-Schiller-Universität Jena mit der Arbeit "Ziffern-Rechenautomat mit Programmierung nach mathematischem Formelbild". In der Habilitationsschrift finden sich Ideen zum Keller; Kämmerer sprach vom automatischen Gedächtnis. Im Vortrag werden grundlegende Ideen der Habilitationsschrift vorgestellt und eingeordnet. Den von Kämmerer entwickelten Algorithmus zum Aufbrechen von Formeln setzte D. Steigmeier im Rahmen einer studentischen Projektarbeit in ein Java-Programm um, das Bestandteil des Vortrags ist.
14:30 - 15:15 Uhr
"Keller im Übersetzerbau"
Prof. Dr. Dr. h.c. Reinhard Wilhelm, Universität des Saarlandes Saarbrücken; Mitglied der Leopoldina
Keller sind im Übersetzerbau allgegenwärtig: Deterministische Kellerautomaten werden zur Syntaxanalyse verwendet. Jede Programmiersprache mit Rekursion benutzt einen Laufzeitkeller, um Inkarnationen von rekursiven Prozeduren oder Funktionen effizient zu verwalten. Sprachspezifische virtuelle Kellermaschinen wurden und werden entworfen, um die semantische Lücke zwischen höheren Programmiersprachen und Zielmaschinen zu überbrücken. Solche Kellermaschinen wurden sogar mehrfach in Hardware realisiert. Um das Anlegen und das Freigeben von Funktionsinkarnationen effizient zu unterstützen, werden in etlichen Architekturen Registerkeller angeboten.
15:15 - 15:45 Uhr
Kaffeepause
15:45 - 16:30 Uhr
"Die Analyse von Kellerstrukturen: Eine Reise durch 50 Jahre Forschung"
Prof. Dr. Dr. h.c. Wolfgang Thomas, RWTH Aachen
Vor 50 Jahren bewies J. Richard Büchi, dass die erreichbaren Kellerinhalte eines Kellerautomaten eine reguläre Sprache bilden. Nur fünf Jahre später eröffnete Michael O. Rabin mit seiner Theorie endlicher Automaten auf unendlichen Bäumen eine weiter greifende Perspektive. Sie hat in neuester Zeit zu überraschend starken algorithmischen Ergebnissen geführt, insbesondere für Systeme mit geschachtelten Kellern. Wir geben eine informelle Darstellung dieser Entwicklung und skizzieren aktuelle Forschungsfragen.