(Colin Runciman)
Explode is a game for two or more players, in which each player has an inexhaustible supply of stones of their own distinctive colour. The game is played by placing the stones on the nodes of a finite connected graph, according to the rules below (in which we say a node is `full' when it holds as many stones as it has incident arcs).
Initially there are no stones on the graph. Players take it in turns to make a move. Each move increases the number of stones on the graph by one. A player takes a stone from their supply and places it on any node n not already containing stones of another colour. If this does not make n full, the move finishes. If it does make n full, then n `explodes': each adjacent node is invaded by one of the stones. The colour of any stones already in the invaded nodes turns to that of the invaders. Any of the invaded nodes that is now full also explodes in turn, and so on until either this move has caused every node in the graph to explode (and the player who made the move wins) or there are no more full nodes (and it is the next player's turn to move).
Explode is often played on a rectangular board divided into squares. The squares are the nodes, and there is an arc between squares with a common edge (ie., assuming at least a 3x3 board, corner squares have two arcs, other edge squares three, and non-edge squares four).
An `explode program' should provide a purely graphical interface to a rectangular board, depicted on the screen, with a height and width in squares set when the program is run. The program should support a contest between two players, displaying the effect of each move.
(Sigbjørn Finne & Simon Peyton Jones)
Take an existing application and replace one of its buttons with a "combination lock"; that is, a combination of buttons which you have to press in the right order to complete one "press" of the button you are replacing.
(Sigbjørn Finne & Simon Peyton Jones)
Enclose your entire Explode game in a viewport, so that you can deal with a board that doesn't fit on the screen. Did you have to change anything about the description of the Explode game?
(Sigbjørn Finne & Simon Peyton Jones)
Change the "finger" in a slider (the bit you drag) so that it displays in numerical form where the slider is. How easy is it to change the feedback form? Eg instead of displaying a number, change the colour of the slider; or make the number display in application-specific units (eg kbytes) rather than interface-specific units (eg percentage of full-scale).
(Sigbjørn Finne & Simon Peyton Jones)
A bigger task: an HTML forms processor
This challenge is to build an HTML browser for HTML documents. The documents are not required to be loaded using the HTTP protocol, but can be assumed to exist in a file. A very open-ended challenge, but an HTML browser for visualising HTML-documents is not only a Cool application with considerable Superhighway street cred., but it shows up some interesting issues from a user interface architecture point of view:
<HEAD>...</HEAD>)
<BODY>...</BODY>)
<TITLE>...</TITLE>)
<BR>)
<A >...</A>)
start or destination of hypertext link, the following
anchor attributes should be handled:
<P>...</P>)
<PRE>..</PRE>)
<ADDRESS>..</ADDRESS>)
<BLOCKQUOTE>...</BLOCKQUOTE>)
<H1>...</H1> through to <H6>..</H6>)
no distinction between the different header levels.
<OL>..</OL>)
<UL>..</UL>)
<LI> items contained within the list elements.
<DL>..</DL>)
<DIR>...</DIR>)
<MENU>...</MENU>)
http://www.w3.org/hypertext/WWW/MarkUp/html-spec/L2index.html
for overview of the elements that should be supported. Minimally, the browser could just handle text-input fields and command buttons.
If you get this far and want more, add support for the <META> tag and use it to add some whizzy Netscape-like features special to your browser. Now start your own company..:-)
(Peter Aachten)
Challenge: 'Concurrent' interactive components with global state.
This challenge concerns a program based on the Game of Life. For those who are not familiar with the Game of Life a brief explanation can be found below.
The features of our challenge program are:
(Emden Gansner)
I. One class of application that capitalizes on GUIs consists of structured browsers and editors. A typical instance involves some collection of "model" data, such as abstract graphs, documents, system specifications or a program. Usually, the model data is stored in some abstract, structured representation, often with semantic connections between various parts. For example, in a programming environment, there would be a way to go from the use of a variable to the definition of the variable.
The application then allows the user to view and interact with the underlying data in a variety of ways. For example, again using a programming environment example, a piece of a program may be displayed in one view in the standard concrete syntax and edited as text. In another window, the same piece might be presented as an abstract syntax tree, drawn and edited as a tree. A third view might offer a relational database view of the code, drawn and edited as a table or form. Using any view, the user should be able to alter the underlying data and have the change reflected in the remaining views. Of course, there might be multiple views of the same type open at the same time. An additional feature that is sometimes supported allows another layer between the model data and the view. For example, there might be multiple, different layouts of an abstract graph in the plane, and then multiple windows on each layout.
As a challenge, build a simple graph editor for creating, viewing and editing directed acyclic graphs. The program should support at least two different types of concrete representations of a graph. Representations can be either textual or graphical. Changes to the graph should be propagated to all of the views.
II. Despite how easy we know it is to put together a GUI using our respective toolkits, there will always be those people who will feel that our toolkits are too complex and require too much typing. To help these people and prevent them from just using TCL/TK and getting their work done, create a prototype interface builder that supports some subset of your toolkit's components. The interface builder should allow the user to construct an interface graphically, picking components and inserting them into the layout. In addition, the user needs to be able to customize the look of the components, dynamically setting colors, fonts, labels, etc. If desired, the interface builder could be extended to handle semantic actions and component interconnections, even becoming a Visual{FP}, where FP is your favorite functional language.
This challenge is probably too broad and open-ended, but I believe it is significant, even as a thought experiment, in that it addresses a major concern in building a GUI using certain functional languages, namely the tension between the flexibility and fluidity required for tailoring interfaces easily and dynamically, and the strong typing and immutability propelled by the language.
(Phil Gray)
My challenge has to do with changes and their costs (not a million miles from Roger's concerns). That is, if I have built my interactive system in a particular way, what will it cost me to change it? For the purposes of creating some challenges, I suggest the following application area, types of changes, and cost measures:
(Roger Took)
The problems of interactive system design that engage me are architectural ones: how is a system best modularised so that we maximise the possibility of code (or concept) reuse? Coming from an imperative, object-oriented background, principally in C++, appears to give me a powerful means of expressing modularity and incremental development. My basic challenge therefore is the same as is implicit in Goguen's paper*: demonstrate that a functional approach to the construction of interactive systems is as flexible and expressive as an object-oriented one (or more so!).
Even using object-orientation, you will be glad to hear, not everything is resolved. The fundamental problem of GUI design, it strikes me, is to support both logical and physical separation, particularly between the GUI component (which I call the `surface') and the application semantics, at the same time as providing highly granular direct manipulation of the objects on the surface. By logical separation I mean relationships of inheritance between modules or classes, typically expressed statically. By physical separation I mean relationships of instantiation between classes and objects, and messaging and containment relationships between objects, typically expressed dynamically. The problems of merging these two are especially acute over a distributed network, where the user interface may run locally on a workstation and the application on a server (maybe on the other side of the world via WWW!). In addition to this, providing separated direct manipulation is difficult since on the one hand we can regard the details of the display layout as an implementation of the more abstract application, or, on the other hand, we can regard the application as a set of concrete constraints on the behaviour of a more general display management system. Either way suggests the two should be tightly coupled or encapsulated. But then it is difficult to reuse either the application with a new interface or the GUI with a new application. There are also issues of control and input channeling: where does the interactive initiative lie? - with application objects, with surface objects, with a surface IO manager, or with the application as a monolithic whole. All sorts of synchronisation problems arise.
I am particularly interested in exploring the design space here: what are the fundamental approaches? I would be good if a functional approach could clarify the distinctions (that are still woolly to me). I would like to see examples of the following four approaches:
Roger Took
*J. A. Goguen, "Higher-order functions considered unnecessary for higher-order programming", in "Research Topics in Functional Programming", pp. 309-352, ed. D. A. Turner, Addison-Wesley, 1990.
(Ian Holyer, Pascal Serrarens)
The idea is based on the following scheme:
,-----------. Meanings:
| display 1 |
`-----------' display 1 : a field displaying a number; the
| value can be changed by the user.
,----^----.
| | func 1 : a button connected to a complex
v v function which takes as input the
,--------. ,--------. value in display 1 and produces
| func 1 | | func 2 | a number
`--------' `--------'
| | func 2 : a button connected to a function
`----&----' which takes the value in display 1
| and immediately returns it.
v
,-----------. display 2 : a field displaying the results of
| display 2 | func 1 and 2.
`-----------'
The problem lies in merging the inputs into display 2 (marked & above).
Suppose the user first clicks on the 'func 1'-button and immediately after on the 'func 2'-button. The result of func 2 will be available very quickly, but the result of func 1 takes significantly more time to return. Merges based on availability will fail here, because with those, the result of func 2 will be displayed first, before that of func 1. Of course, users expect to see result 1 first, because they clicked on the 'func 1'-button first.
To make things just a bit more complicated, we will introduce a loop into the system:
,-----------.
| display 1 |<-----. Meanings:
`-----------' |
| | display x : see above
,----^----. |
| | | func x : see above
v v |
,--------. ,--------. | copy : copies the value displayed in
| func 1 | | func 2 | | display2 to display 1
`--------' `--------' |
| | |
`----v----' |
| |
v |
,-----------. ,------.
| display 2 |-->| copy |
`-----------' `------'
Besides the construction of the loop itself, this may introduce some more
complications. When copy is pressed, and after that one of the func-buttons,
will the old or new value of display 2 be copied into display 1?
Without concurrency, this little system can be quite hard to program neatly, though it should give correct results. With concurrency, most systems rely on nondeterminism, which makes it difficult to predict what results will be given. We would like to see a construction which is both programmed neatly and gives deterministic results.
(Magnus Carlsson & Thomas Hallgren)
The idea is to find a set of combinators for constructing "dialog boxes", .i.e., those windows that pop up and ask the user to enter some information.
The starting point when designing a dialog box is a data type. The dialog box allows values of this type to be edited by the user.
As an example, consider a dialog box for entering a user name and a password when logging in to a computer:
+------------------------------------+ | +---------------------+ | | Username: | | | | +---------------------+ | | | | +---------------------+ | | Password: | | | | +---------------------+ | | | | +----+ +--------+ | | | OK | | Cancel | | | +----+ +--------+ | +------------------------------------+The data type:
data Login = Login UserName Password type UserName = String type Password = StringFrom this we would like to construct a fudget (or whatever):
loginPopupF :: F Login (Maybe Login)The input of the fudget is of type Login so that the program can set default values that will be displayed when the dialog box first pops up. The output is
Nothing if the user presses the Cancel button and
Just (Login name password), where name and password are the contents of
the respective fields, if the user presses the Ok button.
As another example, consider the following piece from a dialog, with a radiogroup of two buttons:
| | | /\ Print all pages | | \/ | | | | | | +---+ +---+ | | /\ Print only pages | | to | | | | \/ +---+ +---+ | | |If "Print all pages" is selected, then the integer input elements are inactive. If one tries to enter something in them, the radiogroup flips over to "Print only pages".
This corresponds to the datatype
data Pages = PrintAll | PrintPages Int IntNow, we would like to have a set of combinators by which we easily could assemble such dialogs (confer parsing combinators, for example).
Either _ _,
() and
(_,_), as well as a few basic types. (Can type classes be used?)