Doctoral thesis for the degree of Doctor of Philosophy

Fudgets --

Purely Functional Processes
with applications to
Graphical User Interfaces

Magnus Carlsson
Thomas Hallgren


Department of Computing Science
Chalmers University of Technology
Göteborg University
S-412 96 Göteborg, Sweden
Göteborg 1998

ISBN 91-7197-611-6
ISSN 0346-718X

Department of Computing Science

Göteborg 1998


The main result of this thesis is a method for writing programs with graphical user interfaces in purely functional languages. The method is based on a new abstraction called the fudget. The method makes good use of key abstraction powers of functional languages, such as higher order functions and parametric polymorphism.

The Fudget concept is defined in terms of the simpler concept of stream processors, which can be seen as a simple, but practically useful incarnation of the process concept. Programs based on fudgets and stream processors are networks of communicating processes that are built hierarchically, using combinators. Communication is type safe. The basic combinators provide serial compositions, parallel compositions, and loops. A key difference between previous work on stream processing functions and our approach is that we deliberately abstract away from the streams. We obtain a system that can be implemented deterministically, entirely within a purely functional language, but which also makes it possible to take advantage of parallel evaluation and indeterminism, where such is available within the functional language. The purely functional approach makes processes first class values and makes it easy to express process cloning and process migration.

The practical viability of the approach is demonstrated by the Fudget library, which is an implementation of a graphical user interface toolkit in the purely functional language Haskell, together with a number of small an large applications that have been implemented on top of the library.

In addition to GUI programming, fudgets are suitable for other forms of concurrent I/O programming. We demonstrate how client/server based applications can be we written, with type safe communication between client and server. We show a web browser as an example where GUI programming and network communication come together.

We view fudgets as one example of a more general combinator-based approach to promote the idea that a functional language together with combinator libraries is a good alternative to using less expressive languages propped by application-specific tools. We describe a set of combinators, reminiscent of parsing combinators, for building syntax-directed editors.


This monograph acts as theses for both authors. Most of the work behind has been carried out in close cooperation between the authors, but some chapters present work of a more individual nature:
Thomas Hallgren:
Chapters 19, 27, and 39. He has also developed the applications in Part V (some contributions are due to Magnus Carlsson in Chapters 36 and 37, though).
Magnus Carlsson:
Chapters 24, 25, 28, and 29.

Historical reflections

Table of Contents

I Introduction

1 Programming by combination
2 Combinator libraries replace tools
3 Declarative programming and input/output
4 I/O in functional languages?
5 What is a Fudget?
6 Contributions of the thesis
7 Road-map

II Programming with Fudgets

The fudget concept and the Fudget library was first conceived and designed as an aid in constructing graphical user interfaces in a lazy functional language. Although the Fudget library now supports other kinds of I/O, the main part of the library still relates to GUI programming.

In the Fudget library, each GUI element is represented as a fudget. The library provides fudgets for many common basic building blocks, like buttons, pop-up menus, text boxes, etc. The library also provides combinators that allow building blocks to be combined into complete user interfaces.

This section introduces the Fudget library by presenting a number of GUI programming examples. They illustrate the basic principles of how to create complete programs from GUI elements and application-specific code. After the examples follows an overview of the library. We show

8 A brief introduction to Haskell
9 Your first 8 Fudget programs
10 Fudget library GUI elements
11 Specifying layout
12 Abstract fudgets
13 Fudget plumbing
14 Fudgets for non-GUI I/O
15 Parameters for customisation

III Stream processors -- the essence of Fudgets

The starting point of the work described in this thesis was the idea of the fudget as a process that communicates with other fudgets through the high-level streams and with the I/O system through the low-level streams. A fudget thus has two input streams and it is not known in advance in which order the elements in the two streams will become available. Fudgets should be able to listen to either the high-level input or the low-level input, but also choose to react to the first input to become available, irrespective of what stream it becomes available on. We expected that the former case would be the exception and the latter case would be the rule, so rather than providing some operator for indeterministic choice that the programmer could use in the definition of fudgets, we choose to merge the high- and low-level streams before feeding them to the fudget, thus moving the indeterministic choice outside the fudget.

So, we started out thinking of fudgets as the primitive concept, but soon saw them as being derived from a simpler concept, the stream processor, which is a process that communicates with its surroundings through a single input stream and a single output stream.

This part of the thesis is devoted to stream processors.

16 Stream processors
17 Plumbing: composing stream processors
18 Pragmatic aspects of plumbing
19 Application programming with plain stream processors

IV Design and implementation

In this part, we will describe the design and implementation of the Fudget library itself, as well as some extensions we have done. The organisation of the first chapters can be summarised in the words the library, extensions and programming methods:
The library.
These chapters describe the fundamental principles behind the Fudget library. Chapter 20 discusses different implementations of stream processors. The implementation of the fudget combinators is based on stream processors, and allows them to communicate with different kind of I/O systems (Chapter 21). Chapter 22 describes the mechanism behind the GUI fudgets, asynchronous I/O and the low-level interfaces to X Windows.

The automatic layout system in Chapter 23 can be seen as a sub-library of combinators, which is used not only for placing the GUI fudgets, but also to compose graphics.

Two examples of filter fudgets (combinators that modify the effect of fudgets) are presented in Chapter 24. The cache filter makes fudget programs run faster using less memory, and the focus filter modifies the input model of GUI fudgets that use the keyboard.

The next chapters describe extensions that we do not consider absolutely essential for the library, although some of them reside in the library itself, and others have at least prompted modification of the library in order to work.

A distinguishing feature of stream processors and fudgets is that they can be detached from their original position in the program, passed as messages, and attached at another position. Chapter 25 describes how this can be used to program drag-and-drop applications, where GUI fudgets actually move inside the program when dragged.

Chapter 26 shows how the fudget concept can be used for programming client/server applications. Server programs do usually not have any graphical interface, but it is can be advantageous to program servers in a concurrent style so that they can serve many clients simultaneously.

The library contains a class of types that has a graphical appearance, which can be manipulated by the user. Chapter 27 presents the Graphic class and its implementation.

Programming methods.
These chapters describe our experiments in programming methods using Fudgets. Chapter 28 describes combinators for creating syntax-oriented editors in a style similar to parsing combinators, and Chapter 29 shows how Haskell's class system can be used to automatically generate simple GUIs. As we have already seen in the previous part, the class system has also been used to program functions that use named parameters with default values. The implementation is described in Chapter 30.
Finally, Chapter 31 describes an implementation of the functional toolkit Gadgets on top of the Fudget library. This includes a functional implementation of the process concept in Gadgets, and allows Gadget programs to be incorporated in Fudgets. As a bonus, a profiling utility was added which provides a graphical monitor of the message queues.
20 Implementing stream processors
21 Fudgets as stream processors
22 Fudget I/O: the gory details
23 Automatic layout
24 Filter fudgets
25 Moving stream processors
26 Typed sockets for client/server applications
27 Displaying and manipulating graphical objects
28 Combinators for syntax-oriented manipulation
29 Type directed GUI generation
30 Parameters for customisation
31 Gadgets in Fudgets

V Applications

One strong motivation behind the development of Fudgets was practical usefulness, that is, we wanted to be able to write serious applications with graphical user interfaces in a declarative style, in a pure functional language. Hand in hand with the development of the library, we have therefore developed a number of small and large applications.

To give you some idea of what the potential of the fudget library is, and to discuss various practical programming considerations, this part presents, in varying detail, some applications we have implemented using Fudgets.

32 WWWBrowser -- a WWW client
33 Alfa -- a proof editor for type theory
34 Humake -- a distributed and parallel make tool for Haskell
35 Space Invaders -- real-time and simulation
36 FunGraph
37 A mobile data communication protocol prototyping tool
38 Two board games

VI Discussion

39 Efficiency and program transformations
40 Comments on Haskell and other language design issues
41 Related work
42 Evaluation and conclusions
43 Future work

A Online resources

A.1 The Fudgets Home Page
A.2 Supported platforms, downloading and installation
A.3 Compiling Fudget programs

B Fudget library quick reference guide

This is an brief index of the Fudget library, listing the things that have appeared in the examples throughout the text.

A more complete description of the contents of the Fudget library is provided in the reference manual, which is available on-line via

B.1 Top level, main program
B.2 GUI building blocks (widgets)
B.3 Combinators, plumbing
B.4 Adding application-specific code
B.5 Layout
B.6 Graphics
B.7 Alphabetical list

Production notes

This thesis was written in an extended version of Haskell, called HacWrite, developed by the authors. The extension consists of a new string type, that can wrap over many lines, and that can contain embedded Haskell code for specification of mark-up. HacWrite consists of a preprocessor that converts HacWrite source into Haskell, and a library of mark-up combinators, written in HacWrite. The library also has back-ends for generating LaTeX and HTML.