22 Fudget I/O: the gory details

In this chapter, we will dive into some of the gory details in the Fudget library implementation. We will see how the GUI fudgets are designed to fit with X Windows in Section 22.1, using the hierarchical windows that X provides.

Asynchronous I/O is necessary to handle events from many sources such as the X server, standard input, and sockets. The implementation of asynchronous I/O is described in Section 22.2.

The communication between a fudget program and the X server uses the library Xlib [Nye90], which is written in C. Xlib defines a number of data types and calls for creating and maintaining windows, drawing in windows and receiving input events.

There is no standardised foreign-language interface for Haskell, so Haskell programs cannot directly call Xlib. To solve this problem, we have implemented a number of interfaces to Xlib: one of which is compiler independent, and three which are specific for HBC, NHC, and GHC. These interfaces are described in Section 22.3.

22.1 GUI Fudgets

The implementation of GUI fudgets uses the possibility to create hierarchical windows in X Windows, a feature that works as follows.

In X Windows, an application program creates one or more shell windows. We have already seen in Chapter 9 how the fudget shellF is used to create a shell window. These windows appear on the user's desktop and are decorated with a title bar by the window manager. The window manager allows the user to manipulate shell windows in various ways, for example, they might be resized and moved around on the desktop. A shell window thus corresponds to the user's concept of a window.

From the point of view of the application programmer, a shell window provides an area which can be filled with graphics, and which can ``react'' to events such as mouse clicks, which the X server can report to the application as events. The window has its own coordinate system which has its origin in the upper left corner, regardless of the window's position on the desktop. The window system also ensures that when the application draws in a shell window, only areas that are visible are updated. This implies a simplification for the application programmer, since he does not have to consider other applications that the user has started.

So far, this story holds for most window systems. X Windows goes one step further, and allows the programmer to create more windows within the shell window. These can in turn contain even more windows. Each window has its own coordinate system, and can be moved and resized (but not directly by the user of the application, as was the case with shell windows). If a window is moved, all windows inside it will follow, keeping their position in the local coordinate system. In addition, each window is associated with an event mask, which allows the programmer to control how ``sensitive'' the application should be to user input when the pointer is in the window.

The simplification that the concept of shell windows brought us as application programmers can be carried over to hierarchical windows. If each GUI element is put in its own subwindow, the application program does not need to know the element's position in the shell window when drawing in it, for example. It is also possible to have a large subwindow inside a smaller window. By moving the large window, we get the effect of scrolling an area.

Since each GUI fudget has its own window (possibly containing subwindows), we have also used the possibility to associate each GUI fudget with its own event mask, something that we use to limit the network traffic of events from the server to the application. This was initially an important aspect in Fudgets (see Section 22.3.1), and is still an advantage when running programs over low-bandwidth links.

Using one window per GUI fudget also simplifies the routing of events inside the application, which receives one single stream of events from the X server. The handling of events is not centralised, instead the GUI fudgets handle events by themselves. When the X server reports a mouse click, the event contains information about what subwindow was clicked, and the position uses the local coordinate system of the subwindow. The window information is used in fudlogue, which maintains a mapping from window identifiers to GUI fudget paths.

22.1.1 Data types for the X Windows interface

The GUI fudgets uses four datatypes for their communication with the X server via Xlib. First, we have the datatypes XRequest and XResponse (which can be seen as extensions to Request and Response), which allow us to communicate with the X server.
data XRequest
  =  OpenDisplay DisplayName
  |  CreateSimpleWindow Path Rect
  |  CreateRootWindow Rect
  |  CreateGC Drawable GCId GCAttributeList
  |  LoadFont FontName
  |  CreateFontCursor Int
data XResponse
  =  DisplayOpened Display
  |  WindowCreated Window
  |  GCCreated GCId
  |  FontLoaded FontId
  |  CursorCreated CursorId
The remaining two datatypes are XCommand, which can be seen as a set of requests without responses, and XEvent, which encode events that the X server asynchronously reports to the application.
data XCommand
  =  CloseDisplay Display
  |  DestroyWindow
  |  MapRaised
  |  LowerWindow
  |  UnmapWindow
  |  Draw Drawable GCId DrawCommand
  |  ClearArea Rect Bool
  |  ClearWindow
  |  CreateMyWindow Rect
data XEvent
  =  KeyEvent { time::Time, 
                keyLookup::KeyLookup }

  |  ButtonEvent { time::Time, 

  |  MotionNotify { time::Time, 
                    state::ModState }

  |  EnterNotify  { time::Time, 
                    mode::Mode }

  |  LeaveNotify  { time::Time, 
                    mode::Mode }

  |  Expose { rect::Rect, 
              count::Int }
The datatypes correspond more or less closely to Xlib calls and X events, with one important difference: The Xlib calls and events deal with additional display (a display is a connection to an X server) and window arguments, which are added by fudlogue (see Section 22.2.2).

A number of auxiliary data types that also correspond more or less directly to definitions found in the Xlib library are shown in Figure 50.

-- Resource identifiers
newtype Display = Display Int
-- and similarly for Window, PixmapId, FontId, GCId, CursorId,
-- ColormapId, ...

-- Type synonyms for readability:
type FontName = String
type ColorName = String
type Time = Int
type Depth = Int

-- GC and Window attributes:
data WindowAttributes
  =  CWEventMask [EventMask] 
  |  CWBackingStore BackingStore 
  |  CWSaveUnder Bool

type GCAttributeList = [GCAttributes Pixel FontId]
data GCAttributes a b = ... -- See Section 27.4.3

-- Various enumeration types:
data EventMask
  =  KeyPressMask | KeyReleaseMask | ButtonPressMask | ButtonReleaseMask
  |  EnterWindowMask | LeaveWindowMask | PointerMotionMask
  |  ExposureMask

data BackingStore  = NotUseful | WhenMapped | Always

-- Geometry
data Point = Point{xcoord::Int, ycoord::Int}
data Rect = Rect{rectpos::Point, rectsize::Size} -- upper left corner and size
type Size = Point
data Line = Line Point Point -- coordinates of the two end points

Figure 50. Some of the auxiliary types used by the interface to Xlib.

22.1.2 groupF: the primitive window creation fudget

GUI fudgets are created with the group fudget:

groupF :: K a b -> F c d -> F (Either a c) (Either b d)
The type of groupF resembles >+<, and indicates that it puts two stream processors in parallel. It will also create a window which will be controlled by the first stream processor, which is a kernel (see Section 21.4). All X commands that the kernel outputs will go to the group fudget's window, and the X events from the window will go to the kernel.

As the name indicates, groupF also groups the GUI fudgets in its second argument, in the following sense. Assume we have the group g:

g = groupF k f
All the windows that are created by groups inside f will be created inside the window created by g, and thus grouped. A consequence is that if the kernel k decides to move its window, all groups inside f will follow.

The atomic GUI fudgets are constructed along the pattern groupF k nullF, that is, they do not have any internal fudgets, just a kernel controlling a window. As an example, consider a group fudget of the form

groupF k1 (groupF k2 (groupF k3 nullF) >+< groupF k4 nullF)
It will have a window with two subwindows, one of which will have yet another subwindow, as is illustrated in Figure 51.

Figure 51. Four group fudgets. Each group has a kernel stream processor controlling an X window.

A group fudget starts by outputting the command CreateMyWindow r, where r is a rectangle determining the size and position of the window in its parent window. This is a command that does not correspond to any Xlib call. Instead, it will be intercepted by the closest containing group fudget, which will see it as a tagged command of the form (p,CreateMyWindow r). The containing group fudget will convert this to the request CreateSimpleWindow p r. When this request reaches fudlogue, it will be of the form (q,CreateSimpleWindow p r). From this information, fudlogue will be able to deduce in which window the new window should be created, and new window's path is found by concatenating q and p (see also the end of section Section 22.2.2).

The observant reader now asks ``What if there is no containing group fudget?'' The answer is that shellF also counts as a kind of group fudget, and we know that a shellF is always wrapped around GUI fudgets. The main difference between groupF and shellF is that the latter starts by outputting CreateRootWindow instead of CreateMyWindow. The request CreateRootWindow is used to create shell windows.

The group fudget concept can be used for structuring complex fudgets. One example is buttonGroupF:

buttonGroupF :: F (Either BMevents a) b -> F a b
data BMevents = BMNormal | BMInverted | BMClick
It is used in the Fudget library to program push buttons. The enclosed fudget will get messages which indicate what visual feedback is appropriate to give, and when the user actually has clicked in the window. This is an example of a group fudget which is invisible to the user--it only deals with input.

As an example of a group fudget which only deals with output, we can have a look at buttonBorderF,

buttonBorderF :: F a b -> F (Either Bool a) b
which is used to draw the three-dimensional border around push buttons, which can look either pressed or released. The familiar button fudget buttonF is a combination of these two group fudgets and a labelF.

One would think that the buttonBorderF always is used immediately inside a buttonGroupF, but this is not necessary. A good counter example is toggleButtonF, in which a buttonGroupF is wrapped around two fudgets: a buttonBorderF which has a little onOffDispF in it indicating its state, and a labelF. The user can control the toggle button by clicking anywhere in the buttonGroupF, including the label. Note that the group structure in the toggle button coincides with Figure 51.

22.2 Synchronous versus asynchronous I/O

The implementation of stream processors in the Fudget library gives us cooperative multitasking, which implies that stream processors should be programmed in a reactive style. This means that the normal state for a stream processor is to be idle, waiting for input. When such input comes, the stream processor reacts by more or less immediately outputting zero or more messages, and then goes back to the waiting state.

Moreover, fudgets must be cooperative when performing I/O tasks. As we have seen in Chapter 21, the I/O requests from all fudgets in a program are performed in fudlogue. We must make sure that these requests are of a transient nature and can be carried out more or less immediately.

For these reasons, the Fudget library makes a distinction between synchronous and asynchronous I/O. Synchronous I/O, where the whole fudget program must wait for the I/O operation to complete, is only used for transient operations. Its implementation is straightforward, as we saw in Section 21.3. Since synchronous I/O is simple to implement, the Fudget library currently uses it when reading and writing to files, and when writing to sockets, standard output and the X server. (In most cases, but not all, these operations are transient, and a future improvement of Fudgets would be to use asynchronous I/O even for these.) When it comes to reading from standard input or sockets, or waiting for events from the X server, asynchronous I/O is used, since these are operations that are likely to block for arbitrary long periods of time.

22.2.1 Fudgets for asynchronous I/O

The fudgets timerF (Section 14.3) and socketTransceiverF (Section 26.1) are examples of fudgets that must use asynchronous I/O to avoid blocking the whole program. Both of them create descriptors as a first step.
data Descriptor =  SocketDe Socket
                |  TimerDe Timer
                |  DisplayDe Display
A socket descriptor (of type Socket) is returned as a response to the request OpenSocket h p which opens a socket connection to the port p on host h. Similarly, a request CreateTimer i d results in a timer descriptor associated with interval i and delay d.

Simply creating a descriptor does not result in any asynchronous I/O. A fudget can use the special request

Select :: [Descriptor] -> Request
to signal to fudlogue that it is interested in asynchronous input from a specified set of descriptors.

22.2.2 The asynchronous fudlogue

To handle asynchronous I/O, fudlogue maintains a mapping between descriptors and paths to fudgets. We have just seen that fudlogue can receive messages of the form (p, Select ds), which announce that there is a fudget with path p which waits for the asynchronous input associated with the descriptors in ds. The function fudlogue collects all descriptors received in this way from all fudgets in the program. When the main fudget evaluates to getSP without an outstanding request, fudlogue knows that it is time to wait for some asynchronous event to happen. It emits a Select request, with all collected descriptors as an argument. The effects of this request are
  1. a call to the UNIX function select, which will wait for input to arrive on any of the descriptors, or a timeout, and
  2. a read operation on the corresponding descriptor (unless it was a timeout).
The response generated is of type AsyncInput:

type AsyncInput = (Descriptor, AEvent)

data AEvent =  SocketAccepted Socket Peer
            |  SocketRead String
            |  TimerAlarm
            |  XEvent (WindowId, XEvent)
As the type AEvent indicates, the response of Select is the descriptor which became ready, paired with the data read.

Using the descriptor table, fudlogue is able to route the received asynchronous input to the waiting fudget.

In addition, fudlogue performs the following translations to handle events to the GUI fudgets:

22.3 The interfaces to Xlib

We have already seen in Section 22.1 that we have extended the Request and Response datatypes with constructors divided in XRequest, XResponse, XCommand, and XEvent, that correspond to Xlib calls and X events. (These data types do not provide a complete interface to Xlib. We have implemented those calls that we found useful and extended the interface by need. Also, some parameters have been omitted from some constructors.) Somewhere, the actual I/O that these requests and commands represent must be carried out, and this is done in what we call the interface to Xlib. We have implemented a number of different such interfaces, and they are described in what follows.

22.3.1 A compiler independent interface

The first implementation of Fudgets was done in LML in 1991, and used Landin's stream I/O model (see Chapter 4). A program in LML is a function of type String->String. The first interface to Xlib was done by outputting the calls and receiving the return values and events in text form via the standard output and input channels. The program was connected by a bidirectional pipe to an external C program that performed the actual Xlib calls. The type of the function fudlogue was F i o -> String->String.

The advantage with this method is that it is portable. No changes need to be made to the compiler or its associated run-time system. The same C program can be used with another compiler or even another programming language.

The disadvantage with this method is that it is inefficient because of the parsing and printing of commands, return values and events. By printing them in a simple format, the overhead can be kept down, though. Also, for most user-interface tasks, the throughput need not be very high.

22.3.2 The interface for HBC

To avoid the overhead of the text communication with a separate process, Lennart Augustsson integrated the interface to Xlib with the run-time system of LML. LML uses the synchronised stream I/O (see Section 21.1), so the integration was done by adding new constructors to the request and response types. The extensions are shown in Figure 52. They handle commands and requests corresponding to Xlib calls, requests for socket I/O, and the asynchronous I/O described in Section 22.2.2. The type of the function fudlogue was changed to F i o -> Dialogue.
type Dialogue = [Response] -> [Request]

data Request =  ReadFile       String         
             |  WriteFile      String String
             |  ... 
             -- Extensions
             |  XCommand       (XDisplay,XWId,XCommand)
             |  XRequest       (XDisplay,XWId,XRequest)
             |  SocketRequest  SocketRequest
             |  Select         [Descriptor]
             |  ...

data Response =  Success
              |  Str String 
              |  Failure IOError
              |  ...
              -- Extensions
              |  GotSelect AsyncInput
              |  SocketResponse SocketResponse
              |  XResponse XResponse
              |  ...

Figure 52. Extending the Haskell 1.2 dialogue I/O types with requests for the interface to Xlib

The part of HBC's run-time system that handles dialogue I/O is implemented in C. The procedure that implements the Requests was modified to handle the XRequest and XCommand requests by calling a new procedure doxcall outlined in Figure 53. As can be seen in Figure 54, a few lines of C code per supported Xlib call are needed.

PTR doxcall(t, p)
int t; /* tag of the Request */
PTR p; /* pointer to the argument of the Request */
  PTR response;

  p = evaluate(p);
  switch(t) {
  case XCommand: /* (Display, Window, XCommand) */
    p = evalArgs(p,3);
    xdocommand((Display *)INTOF(GET1OF3(p)), 
  case XRequest: /* (Display, Window, XRequest) */
      PTR xresp;
      p = evalArgs(p,3);
      xresp=doxrequest((Display *)INTOF(GET1OF3(p)), 

    fprintf(stderr, "Unknown X I/O request ...", ...);
  return response;

void xdocommand(display, wi, p)

Figure 53. The C function doxcall was added to HBC's run-time system to handle the extra requests XCommand and XRequest.

     Display *display;
     Window wi;
     PTR p;
  PTR rp;
  Window parent;

  switch(getcno(p)) {
  case XRqOpenDisplay: /* DisplayName */
      char displayname[BUFSIZE];
      Display *display;

      evalstring(EARG1(p), displayname, sizeof displayname);
      display=XOpenDisplay(displayname[0] ? NULL : displayname);
      return MkPtrXResp(XRDisplayOpened,display);
  case XRqCreateRootWindow:     /* Rect */


Figure 54. The C function doxrequest analyses the XRequest constructor and carries out the corresponding call to Xlib.

22.3.3 The interface for NHC

In the summer 1996, the Fudget library was ported to NHC [Röj95b] for Haskell 1.3 [PH96], to allow fudget programs to take advantage of the new heap profiling features available in NHC [RR96a][RR96b].

The Fudget library could be ported to NHC by a relatively small effort: Support for two-pass heap profiling
Heap profiling can help you improve the memory behaviour of your programs. For example, you may find out using a biographical heap profile that a large portion of the data in the heap is drag, that is, a lot of nodes that are kept in the heap after their last use. You may then use a combination of a biographical profile and a retainer profile to find out which set of functions in the program that are responsible for retaining the drag. This may give you a clue as to how you should change the program to get rid of the drag.

The implementation of certain combined profiles, as described in [RR96b], collects the needed information in two passes, that is, the program is run twice. In order to create two identical runs, the return values of all I/O operations must be recorded during the first run and then played back during the second run.

In order to allow fudget programs to take advantage of the latest heap profiling technology, Niklas Röjemo added the necessary code for recording and playing back the results of the Xlib calls and other extended I/O operations used by the Fudget library. As a typical example, the glue code for the Xlib procedure XOpenDisplay (which we have already seen in Figure 54) was changed as shown in Figure 55.

case XRqOpenDisplay: /* DisplayName */
    char displayname[1000];
    Display *display;

    evalstring(EARG1(p), displayname, sizeof displayname);
      display=XOpenDisplay(displayname[0] ? NULL : displayname);
    return MkPtrXResp(XRDisplayOpened,display);

Figure 55. Changes to the Xlib glue code for two pass heap profiling.

The macros RECORD_ONE and REPLAY_ONE_AND_SKIP expand to code that records the result during the first run and recalls it and skips the actual call during the second run. Their definitions are shown in Figure 56. The variables replay, record and inputFILE are set by NHC's run-time system as appropriate.

#define REPLAY_ONE_AND_SKIP(x) if(replay) { REPLAY(x); } else
#define RECORD_ONE(x) if(record) { RECORD(x); }

#define RECORD(x) fwrite((void *)&(x),sizeof(x),1,inputFILE)
#define REPLAY(x) fread((void *)&(x),sizeof(x),1,inputFILE)

Figure 56. Macros for two pass heap profiling.

22.3.4 The interface for GHC

As a consequence of the NHC implementation, the Fudget library did not depend on a Haskell 1.2 I/O system anymore. This opened the door for an interface to Xlib using the I/O monad and the C-interface in GHC [J{\etalchar{+}}97]. By using this port, it is possible to take advantage of GHC's time profiling tools and possibility to generate efficient code.

The interface to Xlib in GHC is written in a rather ad hoc style using _ccall_ and _casm_ statements. Today, a nicer interface could be created using the foreign-language interface support of Green Card [JNR97].