Fachprojekt
Rapid Prototyping mit Haskell & Expander2 (Expro)
  • Wahlpflichtveranstaltung INF-BSc-254 im SoSe 2017
  • für Studierende der Bachelorstudiengänge Informatik und Angewandte Informatik
    Wahlveranstaltung im Hauptstudium der Informatik-Diplomstudiengänge für die Schwerpunktgebiete 1, 4 und 5
    Teilnahmevoraussetzung ist der erflogreiche Abschluss der Module Logik für Informatiker und Funktionale Programmierung, nicht jedoch - wie in der Modulbeschreibung angegeben - eines Wahlplicht-Moduls im Katalog "Konzepte für Software".
  • 4 SWS - 6 Credits
  • Termin: Di+Fr 14:15-15:45 im OH 12, Raum 3.031
  • Beginn: 18. 4. 2017
  • Inhalt: Dieses Fachprojekt richtet sich an Studierende, die funktionale Modellierung und Programmierung deren Grundlagen in der Bachelor-LV FP vermittelt werden - zur Lösung nichttrivialer Aufgaben einsetzen wollen. Haskell ist auf der FP-Seite beschrieben. Expander2 ist ein in O'Haskell codiertes (und mit einer Tcl/Tk-Schnittstelle versehenes) interaktives Präsentations-, Test- und Beweiswerkzeug für regelbasierte (logische, nichtdeterministische) wie auch streng funktionale Programme. Einige Features von Expander2 stellt auch das reine Haskell-Modul Painter zur Verfügung. Beide Systeme können leicht so erweitert oder verändert werden, dass sie die Entwicklung und Ausführung bestimmter formaler Modelle unterstützen. Das bedeutet manchmal den Einbau des Modells in das System und ein anderes Mal eher die Repräsentation des Modells als logisch-algebraische Spezifikation, auf die Expander2 bzw. das Painter-Modul seine Rechen-, Beweis- und Visualisierungsregeln anwenden kann. Letztere dienen der problemnahen graphischen Darstellung von Eingabedaten, Programmabläufen, Zwischenergebnissen, Lösungsmengen, etc.
    Die konkrete Projektaufgabe wird in Abstimmung mit den TeilnehmerInnen und deren jeweiligen Voraussetzungen, Studienschwerpunkten und Programmiererfahrungen festgelegt. Hier sind einige Vorschläge:
    • Entwurf und Implementierung eines generischen LL- oder LR-Compilers für eine bestimmte DSL (domain-specific language) nach dem Schema, das in der Bachelor-LV Übersetzerbau vermittelt und dort u.a. auf an Java orientierte imperative Sprachen (JavaLight und JavaLight+) angewendet wird. Im letzten Sommersemester wurden im Rahmen dieses Fachprojekts LL-Compiler für eine Baumnavigationssprache entwickelt, deren Syntax und Semantik in Kapitel 29 (XPath and CTL on trees) des Foliensatzes Fixpoints, Categories, and (Co)Algebraic Modeling definiert sind.
    • Erweiterungen der Datenmodelle von Expander2 bzw. des o.g. Painter-Moduls zur Spezifikation von Vektorgraphiken und deren Animation. Z.B. könnte der bisher implementierte Baukasten zur Erzeugung ausschließlich zweidimensionaler Graphiken auf polygonale Netze, Polyeder und dreidimensionale Lindenmayer-Systeme ausgedehnt werden.
    • Ausgewählte Algorithmen aus den Bereichen Geometrisches Modellieren, Algorithm Engineering, Bioinformatik oder Computational Intelligence, die auf komplexen Datenstrukturen und umfangreichen musterorientierten Fallunterscheidungen basieren, könnten in Haskell oder O'Haskell implementiert und mit Expander2 visualisiert werden. Ggf. lohnt sich auch ein Vergleich der Ergebnisse mit Programmen, die in der in den genannten Bereichen häufig verwendeten Sprache Python geschrieben wurden.
    • Transitionssysteme (Automaten,Prozessmodelle, Petrinetze, Kripke-Strukturen, Coalgebren,...) mit strukturierten Zuständen können in Expander2 regelbasiert spezifiziert und modallogisch sowie mit allgemeineren Beweisregeln wie (Co-)Resolution und (Co-)Induktion verifiziert werden; siehe Expander2 as a Prover and Rewriter und From Modal Logic to (Co)Algebraic Reasoning. Die Beispiele in diesen Arbeiten stammen aus verschiedenen Anwendungsbereichen und bieten Ansatzpunkte für eine umfassendere Analyse der jeweils zugrundeliegenden Modelle mit Hilfe von Expander2 bereitgestellten Test-, Beweis- bzw. Darstellungsmethoden. Einige dieser Methoden wurden inzwischen auch in das Painter-Modul bzw. dessen Abkömmlinge integriert. Andere könnten im Rahmen des Fachprojekts übertragen werden.
    • Im Rahmen einer gerade fertiggestellten Diplomarbeit wurde Expander2 in reine Haskell-Module übersetzt, die anstelle der Tcl/Tk-Schnittstelle das GIMP Toolkit verwenden. Diese Version von Expander2 bedarf noch umfangreicher Tests und ggf. Korrekturen, von denen einige im Rahmen des Fachprojekts vorgenommen werden könnten.
  • Kompetenzen: Die Studierenden lernen, komplexe Aufgabenstellungen in funktionallogischer Sprache zu formulieren und ihre Lösungen in einer entsprechenden Programmierumgebung zu testen und zu optimieren. Hier muss Wissen aus mehreren LVs des 1. bis 5. Semesters in Zusammenhang gebracht werden. Geeignete Datenmodelle müssen gefunden bzw. benutzt werden, um die Problemstellung funktionallogisch darzustellen und das heißt vor allem, die für jeden Softwareentwurf zentrale Abstraktion zu üben: nicht mehr und nicht weniger als das darzustellen, was die jeweilige Aufgabenstellung ausmacht. Danach müssen genau die Konstrukte von Haskell und Komponenten von Expander2 gefunden und verstanden werden, die zur Bearbeitung der Aufgabe gebraucht werden. Schließlich geht es um konkrete Programmierung, die Lösung damit verbundener programmiertechnischer Teilprobleme und die adäquate Auswahl von Testfällen. Möglichkeiten und Grenzen von Abstraktion, Reduktion, Verständlichkeit, Wiederverwendbarkeit, Eleganz und Effizienz eines Softwareentwurfs (er)kennen lernen erlaubt dieses Projekt u.a. dadurch, das es zwischen eigenständiger Problemlösung und Anpassung an eine vorgegebene Sprachumgebung pendelt.
  • Das Fachprojekt kann ggf. als Bachelor- oder Masterarbeit fortgesetzt werden.