Informatik-Kolloquium: Keller, Stack und automatisches Gedächtnis – eine Struktur mit Potenzial

Ein Kolloquium der Friedrich-Schiller-Universität Jena und der Gesellschaft für Informatik

Zeitraum: 14.11.2014 00:00 Uhr - Uhr

Ort: UHG · Fürstengraben 1, Senatssaal

Flyer als PDF herunterladen

KellerProgramm

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.

17:00 Uhr Ende des Kolloquiums