HOME | ENGLISH | IMPRESSUM | KIT

Aufgabenstellung: Lambda

Zurück zur Übersicht

image In diesem Praktikum sollen Sie eine Android-Lernapp realisieren, bei der eine graphische Variante des Lambdakalküls gelehrt wird. Hierbei stellen Alligatoren λ-Ausdrücke und Eier die Variablen dar. Der Ausdruck rechts entspricht beispielsweise λx.(λy.y)x, wobei x durch Rot und y durch Gelb dargestellt ist.

Eine kurze Bemerkung vorab

Dies ist ihr Projekt. Dieses Dokument ist kein Katalog von Aufgaben, der Punkt für Punkt abgearbeitet werden muss, um nachher den Schein zu bekommen, sondern lediglich eine Reihe von Hinweisen, was wir erwarten. Wie ihr Programm nachher aussieht, müssen sie selbst entscheiden.

Motivation

Der λ-Kalkül ist die Grundlage funktionaler Programmierung. Funktionale Programmierung wird gerade in den letzten Jahren wichtiger, da Parallelisierung auf Multicorearchitekturen unter Beachtung von funktionalen Prinzipien (no side effects, higher-order functions) einfacher ist. An Einfachheit mit einer Turing-Maschine vergleichbar, bietet bereits der einfache untypisierte λ-Kalkül gute Möglichkeiten zu Abstraktion an, so dass erstaunlich gut damit programmiert werden kann.

Die formale Notation (λx.x) und die Mächtigkeit täuschen eine hohe Komplexität vor. Im Kern ist der λ-Kalkül, aber eigentlich so einfach, dass selbst ein Grundschüler in verstehen kann. Eine Darstellung durch Alligatoren erleichtert den Zugang. Begriffe wie „Alligatorfamilie“ statt „λ-Term“ sind für Kinder vertrauter und bauen Hürden ab.

Ein Spiel von Bret Victor zeigt eine spielerische Variante. Unter anderem Philip Wadlers 8-jährige Tochter konnte erfolgreich die Beispielaufgabe lösen. Die Verpackung als Puzzlespiel verwandelt trockenen Stoff in eine spannende Herausforderung.

Aufgabe

Am Ende soll eine funktionsfähige Android App stehen, die spielerisch den λ-Kalkül für Grundschüler vermittelt.

Spielregeln

Abweichungen von den offiziellen Spielregeln sind möglich. Offen ist auch die Frage, wie das Programm mit Termination umgeht. Der λ-Kalkül erlaubt potentiell unendlich laufende Programme und gerade der hier relevant sogenannte Y-Kombinator ist ein interessantes Konstrukt. Insbesondere könnten weitere Konzepte vermittelt werden, wie Call-by-Value, Call-by-name, Call-by-reference, Lazyness, oder typisierter λ-Kalkül.

Der λ-Kalkül ist für weitergehende Spielereien benutzbar. Möglich wäre also auch eine Art Sandbox-Modus, in dem der Anwender relativ frei selbst programmieren kann. Das entfernt sich allerdings von dem Spielprinzip und ist rein optional zu sehen.

Android

Android existiert mittlerweile in der Version 4.4 (Kit Kat), allerdings sind auch ältere Versionen noch recht verbreitet. Sie sollten Android 4.2 oder neuer (API level 17+) unterstützen, da dies auch von den Google Play for Education Guidelines empfohlen wird. Optional kann auch Android 2.3 (Gingerbread) unterstützt werden, welches immer noch 20% Marktanteil hat. Das übliche Interface für Android ist Touch, weshalb dieses auch unterstützt werden muss. Andere Modi sind optional.

Spaß

Der Spaß ist wichtig, um Kinder länger für das Lernprogram zu motivieren. Kleine Belohnungen wie beispielsweise Erfolgsanimationen oder Highscores sind eine Möglichkeit. Recheriere doch mal nach dem Stichwort „gamification“.

Wichtig in diesem Punkt ist auch das Interface, das altersgerecht und intuitiv sein sollte. Bedienkonzepte müssen von Grundschülern (und Grundschullehrern) verstanden werden können. Animierte Übergänge statt ruckartiger Bewegung ist ein Aspekt. Ein gute Wahl für Symbole ein anderer. Mechanismen wie Achievements oder Highscores sind erprobt.

Die Alligatoranalogie ist nicht gefordert. Bessere Vorschläg sind höchst willkommen. Auch das Genre ist nicht vorgegeben, also mal ein kreatives Brainstorming machen: Jump'n'Run? First Person Shooter? Text Adventure? Tetris? Poker? Schach? Minecraft?

Lernziele

Es muss natürlich definiert werden, was genau durch die App vermittelt werden soll. Mögliche Lernziele wären einfache Ausdrücke, unendliche Auswertung, funktionen höherer Ordnung und Bindung. Ideen finden sich beispielsweise auch in unserer Vorlesung „Programmierparadigmen“.

Minimale Leistungsmerkmale

Folgende minimale Leistungsmerkmale soll Ihr Programm erfüllen:

  • muss in der Simulationsumgebung von Android laufen

  • komplett über das dort simulierte Touchinterface bedienbar sein

  • eine modulare Architektur besitzen (z.B. Model-View-Controller-Prinzip)

Organisatorisches

Für jede Phase des Praktikums muss ein Phasendokument abgegeben werden. Dieses Dokument ist Grundlage für das Kolloquium am Ende jeder Phase, in dem die Gruppe die Ergebnisse der Phase vorträgt.

Erste Schritte

  • Einarbeitung Android: http://developer.android.com
    Je besser man sich mit Android auskennt, desto besser wird der Entwurf und desto reibungsloser die Implementierung.

    Alternativ kann auch ein Framework wie LibGDX benutzt werden, das von Android abstrahiert.

  • Einarbeitung λ-Kalkül

  • Werkzeuge sichten:
    Versionsverwaltung mit Subversion oder Git? Eclipse als IDE oder das experimentelle Android Studio (IntelliJ IDEA)? Dokumente mit LaTeX oder Office schreiben? UML-Diagramme?

  • Funktionale Anforderungen überlegen:
    Markt sichten, Muss-Kriterien, Wunsch-Kriterien und Abgrenzungs-Kriterien.

  • Tipps-Dokument lesen. Siehe Website.

Literatur

Wir empfehlen folgende Quellen zur Vorbereitung auf die Aufgabe.

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 Minuten 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