HOME | ENGLISH | IMPRESSUM | KIT

Praxis der Softwareentwicklung - λ-IDE

Ein Projekt von „Praxis der Softwareentwicklung“ (PSE)

Worum geht es?

Das λ-Kalkül ist ein rein auf Termersetzung begründetes turingmächtiges Kalkül.
(Das bedeutet insbesondere, man kann darin Programme schreiben, die beliebige Dinge ausrechnen.)
Dieses Kalkül ist nicht nur von historischer Bedeutung, sondern bietet immer noch das theoretische Fundament für funktionale Programmiersprachen.1
Trotz seiner Mächtigkeit ist es extrem simpel: es gibt nur Funktionsdefinition und Funktionsanwendung.
Leider ist es erfahrungsgemäß sehr schwierig, Studierenden die Funktionsweise und Bedeutung vom λ-Kalkül klar zu machen.
Das wollen wir ändern, und dazu sollt ihr nun ein Programm ähnlich einer Entwicklungsumgebung schreiben, das Leuten das λ-Kalkül näherbringt.

Keine Angst, ihr seid da nicht auf euch allein gestellt, wir erklären euch das nötige Vorwissen (das Kalkül, Reduktionsstrategien, wie man darin programmiert, etc.).

Was muss das Programm können?

Da das Programm für die Lehre gedacht ist, muss es einigermaßen intuitiv sein.
Am besten wäre eine Webanwendung, da es nunmal sehr viel einfacher ist, Studierende dazu zu bringen, kurz einen Link im Browser anzuklicken, als eine Java-Applikation herunterzuladen.
(Jedoch gelten auch hier die üblichen Einschränkungen: Objektorientierter Entwurf, statisch typisierte Sprache!2)
Vom Benutzer geschriebene λ-Terme einlesen, darstellen und auswerten muss das Programm auf jeden Fall können, darüber hinaus sind wir offen für eure Ideen, wie man eine solche Entwicklungs-/Lernumgebung am besten gestaltet.
Hier eine Liste an Ideen, wie man dieses Grundgerüst erweitern könnte, um daraus eine sinnvolle Lernumgebung zu machen:

  • Verschiedene Auswertungsstrategien. Neben der geforderten Normalreihenfolge könnte man noch Call-by-name, Call-by-value, und eine Heuristik-basierte Strategie anbieten.
  • Animation der Auswertungsschritte, bei denen man sieht, welche Teilausdrücke wohin kopiert werden, welche verschwinden, etc. Färbung, Bewegung, das volle Programm.
  • Darstellung der Zwischenausdrücke könnte man ausschaltbar machen (Auswertungen werden sehr schnell sehr lang).
  • Alternativen in der Darstellung von λ-Termen:
    • Als geklammerter Ausdruck
    • Nach Variablengültigkeit gefärbt ("Syntax-highlighting")
    • Mouse-over über Variablenbindung könnte alle Vorkommen der Variable hervorheben, oder hervorheben, welche Teilausdrücke von einem Auswertungsschritt an der Stelle modifiziert werden.
    • Andere, möglichst intuitive Darstellungen, die klar macht, wie die Ausdrücke strukturiert sind (Umformung zu de-Bruijn-Indices, als Baum, mit Färbung hinterlegt, etc.)
  • Eine Standard-Bibliothek an Definitionen, die es komfortabler machen, im λ-Kalkül zu programmieren. Natürliche Zahlen, Tupel, Listen, etc.
  • Auswerten von Teilausdrücken durch draufklicken
  • (Sofern als Webanwendung umgesetzt) Permalinks, die zu bereits "vorausgefüllten" Sessions führen
  • Project-Euler-ähnliche eingebaute Datenbank an Übungsaufgaben
  • LaTeX-Export für ganze Ableitungen


[1] - Man kann es selbst wie eine primitive, aber mächtige funktionale Programmiersprache benutzen. Die interne Zwischensprache von Haskell, "Core", ist beispielsweise eine Art λ-Kalkül.
[2] - Das GWT würde sich anbieten. Dieses von Google entwickelte Toolkit erlaubt es einem, ganze Webanwendungen in Java zu schreiben. Der Client-Teil wird nach JavaScript compilet und im Browser ausgeführt, es sind also auch echte, reaktive Anwendungen möglich.


Bewertung

Die Benotung Ihres Systems richtet sich nach folgenden Kriterien:

  • Qualität aller abgegebenen Dokumente und Artefakte

  • Qualität der Kolloquien (10 Minuten Vortrag)

  • Qualität der Abschlusspräsentation

  • Erfüllung der minimalen Leistungsmerkmale (s.o.)

  • sinnvolle Erweiterungen über diese Merkmale hinaus

  • Robustheit des erstellten Programms

  • Teamarbeit (TSE)

Diese Liste hat keine Reihenfolge, die einer Gewichtung entspricht. Es gibt sicherlich weitere Punkte, die als selbstverständlich gelten und sich bei Nichterfüllen negativ auswirken (z.B. ist die Geschwindigkeit der implementierten Algorithmen sekundär, aber jedem sollte klar sein, dass das Errechnen einer Lösung oder das Generieren nicht 10 Tage dauern darf).

Weitere Pflichten

  • Anmeldung per Studienportal für PSE und TSE

  • Anwesenheit bei den wöchentlichen Treffen mit dem Betreuer

  • Team-internes Management (z.B. Phasenverantwortliche, Versionskontrolle)

  • Artefakte 1–2 Tage vor Kolloquium beim Betreuer

Dokumente

Dokument Datum
Tipps & Tricks 2015-10-18

Veranstalter

Wissenschaftliche Mitarbeiter
Denis Lohner
Maximilian Wagner