Enno Scholz

A Framework for Programming Interactive Graphics in a Functional Programming Language

Ein Framework für die Programmierung interaktiver Graphik in einer funktionalen Programmiersprache

Abstract:

We have presented a framework called Pidgets for programming interactive graphics in the purely functional programming language Haskell. The contribution of the Pidgets framework is to provide a uniform, high-level notation for the definition of (i) static pictures, (ii) dynamic interactive graphics animations, and (iii) graphical user interface elements, which in previous research on purely functional programming have been addressed by separate approaches.

The Pidgets framework was built on top of a monadic combinator library for constructing interactive synchrononous programs called imperative streams. In two ways, our new St monad is a generalization of Haskell's IO monad for performing imperative actions. First, an object in the St monad denotes an imperative program that may produce multiple values at different points during its execution, whereas an object in the IO monad denotes an imperative program returning one value on termination. Second, the St monad's bind operation allows programs to be composed concurrently, whereas the IO monad's bind operation is restricted to sequential composition. We have presented two executable semantical descriptions of imperative streams, one for a restricted version in which streams cannot perform side-effects and another one for the general case. We have shown how, due to the leverage provided by the functional language's abstraction mechanisms, the small number of primitive combinators on imperative streams give rise to an elegant and expressive programming formalism for deterministic, synchronous, concurrent programming.

We have extended the combinator library of imperative streams with a number of additional combinators for programming interactive graphics, using graphical streams. Here, the main challenge was to integrate the synchronous programming model with a scheme for supplying a graphical stream with information about its current transformation matrix and about what parts of it are currently obscured by other graphical streams. For this purpose, context sensor streams were introduced, to which events are not delivered from the event queue but rather from their context. These context events were dispatched through the stream graph using a scheme adapted from object-oriented GUI frameworks. A number of programming techniques were presented that show how interactive graphics abstractions can be written concisely using our combinators. To demonstrate that these techniques scale to non-trivial applications, a full-fledged widget library was implemented, in which widgets are represented as higher-order functions on imperative streams A substantial part of the dissertation was of a practical nature. Based on Display PostScript, Xlib, and the Boehm-Weiser garbage collector, Pidgets was completely implemented as a C++ extension to the Hugs interpreter. This implementation is freely available. Although too slow and memory-hungry for serious applications, it is sufficiently fast to develop and test realistic interactive graphics programs.

German Summary:

Die Arbeit präsentiert ein Framework Pidgets für die Programmierung interaktiver Graphik in einer rein funktionalen Programmiersprache. Pidgets liefert eine einheitliche, abstrakte Notation für (i) statische Bilder (ii) dynamische interaktive graphische Animationen und (iii) graphische Bedienelemente. Bisher sind diese Anwendungsgebiete in der Forschung über rein funktionale Programmierung in getrennten Ansätzen behandelt worden.

Pidgets baut auf einem neuen Typkonstruktor St und einem dazugehörigen Satz von funktionalen Kombinatoren auf, die die Konstruktion interaktiver, synchron nebenläufiger Programme, sogenannter imperativer Ströme, ermöglicht. Der Typkonstruktor St ist eine Monade. Sie verallgemeinert in zweierlei Hinsicht die in der funktionalen Programmier-sprache Haskell zur Ausführung imperativer Aktionen verwendete Monade IO: Erstens bezeichnet ein Objekt in der Pidgets baut auf einem neuen Typkonstruktor St und einem dazugehörigen Satz von funktionalen Kombinatoren auf, die die Konstruktion interaktiver, synchron nebenläufiger Programme, sogenannter imperativer Ströme, ermöglicht. Der Typkonstruktor St ist eine Monade. Sie verallgemeinert in zweierlei Hinsicht die in der funktionalen Programmier-sprache Haskell zur Ausführung imperativer Aktionen verwendete Monade IO: Erstens bezeichnet ein Objekt in der St-Monade ein imperatives Programm, das mehrfach im Laufe seiner Ausführung Werte erzeugt, während ein Objekt in der IO-Monade ein imperatives Programm bezeichnet, das einmal bei seiner Termination einen Wert erzeugt. Zweitens ermöglicht der Kombinator bind in der St-Monade auch eine nebenläufige Zusammensetzung von Programmen, während er in der IO-Monade auf eine Sequentialisierung beschränkt ist. Die Arbeit zeigt, wie sich aus nur wenigen Kombinatoren für imperative Ströme durch die Abstraktionsmöglichkeiten der funktionalen Sprache ein eleganter und ausdrucksstarker Programmierformalismus für die deterministische, synchron nebenläufige Programmierung ergibt. Zwei ausführbare Semantiken werden für imperative Ströme angegeben, eine für eine eingeschränkte, seiteneffektfreie Form von Strömen und eine für den allgemeinen Fall.

Durch Erweiterung der St-Monade um einige weitere Kombinatoren wird die Anwendung auf das Gebiet der interaktiven Graphik - mittels sogenannter graphischer Ströme - möglich. Das wichtigste hierbei gelöste Problem ist die Integration des synchronen Programmiermodells mit einem Verfahren zur Versorgung eines graphischen Stroms mit Informationen über seine sichtbare Fläche und seine aktuelle Transformationsmatrix. Dieses Verfahren ist angelehnt an Techniken, die aus objektorientierten Frameworks bekannt sind.

Eine Reihe von Programmiertechniken werden präsentiert, die zeigen, wie mit Hilfe der entwickelten Kombinatoren Abstraktionen zur Kapselung interaktiv graphischen Verhaltens definiert werden können. Um zu zeigen, daß sich mit diesen Techniken realistische Probleme lösen lassen, wurde eine komplett ausgestattete Bibliothek graphischer Bedienelemente implementiert. Graphische Bedienelemente manifestieren sich dabei als Funktionen höherer Ordnung auf imperativen Strömen.

Ein wesentlicher Teil der Arbeit an der Dissertation war praktischer Natur. Um die Anwendbarkeit der vorgestellten Konzepte unter Beweis zu stellen, wurde Pidgets, basierend auf Display PostScript, Xlib und dem Boehm-Weiser-Speicherplatz-deallokator, als C++-Erweiterung des Haskell-Interpreters Hugs implementiert.

Keywords: interactive graphics, synchronous programming, functional programming, monads, combinator libraries, streams, concurrency

CR: ?

Language: eng

Date of Disputation: 98-07-01

First Referee = Advisor: Prof. Dr. Peter Löhr

Second Referee: Prof. Dr. Peter Pepper

Third Referee: Prof. Dr. Simon Peyton Jones

Publisher: folgt

Online Available: not

Source: folgt

ISBN: folgt

Contact (Candidate): scholz@dbag.bln.daimlerbenz.com

Contact (Advisor): lohr@inf.fu-berlin.de

- Created: 1998-10-12 -