Compilers, amongst other programs, often work with data that (slowly) changes over time. When the changes between subsequent runs of the compiler are small, one would hope the compiler to incrementally update its results, resulting in much lower running times. However, the manual construction of an incremental compiler is very hard and error prone and therefore usually not an option.

Many computer programs work with data that changes over time. Computations done over such data usually are repeated completely after a change in the data. For complex computations such repetitive recomputation can become too inefficient. When these recomputations take place on data which has only changed slightly, it often is possible to reformulate the computation to an incremental version which reuses the result of the computation on previous data. Such a situation typically occurs in compilers and editors for structured data (like a program) where program analyses and transformations (for example error checking) are done while editing.

Type inference is the process of constructing a typing derivation while gradually discovering type information. During this process, inference algorithms typically make subtle decisions based on the derivation constructed so far.

In this paper we describe the architecture of the Utrecht Haskell Compiler (UHC).

Attribute Grammars (AGs), a general-purpose formalism for describing recursive computations over data types, avoid the trade-off which arises when building software incrementally: should it be easy to add new data types and data type alternatives or to add new operations on existing data types? However, AGs are usually implemented as a pre-processor, leaving e.g. type checking to later processing phases and making interactive development, proper error reporting and debugging difficult. Embedding AG into Haskell as a combinator library solves these problems.

Abstract We present two implementations of Oppen's pretty-printing algorithm in Haskell that meet the efficiency of Oppen's imperative solution but have a simpler and a clear structure. We start with an implementation that uses lazy evaluation to simulate two co-operating processes. Then we present an implementation that uses higher-order functions for delimited continuations to simulate co-routines with explicit scheduling.

The Haskell definition and implementation of read is far from perfect. In the first place read is not able to handle the associativities defined for infix operators. Furthermore, it puts constraints on the way show is defined, and especially forces it to generate far more parentheses than expected. Lastly, it may give rise to exponential parsing times. All this is due to the compositionality requirement for read functions, which imposes a top-down parsing strategy.

We present techniques for representing typed abstract syntax trees in the presence of observable recursive structures. The need for this arose from the desire to cope with left-recursion in combinator based parsers. The techniques employed can be used in a much wider setting however, since it enables the inspection and transformation of any program structure, which contains internal references. The hard part of the work is to perform such analyses and transformations in a setting in which the Haskell type checker is still able to statically check the correctness of the program representations, and hence the type correctness of the transformed program.

A permutation phrase is a sequence of elements (possibly of different types) in which each element occurs exactly once and the order is irrelevant. Some of the permutable elements may be optional. We show how to extend a parser combinator library with support for parsing such free-order constructs. A user of the library can easily write parsers for permutation phrases and does not need to care about checking and reordering the recognized elements. Applications include the generation of parsers for attributes of XML tags and Haskell's record syntax.

To improve the quality of type error messages in functional programming languages, we propose four techniques which influence the behaviour of constraint-based type inference processes. These techniques take the form of externally supplied type inference directives, precluding the need to make any changes to the compiler. A second advantage is that the directives are automatically checked for soundness with respect to the underlying type system. We show how the techniques can be used to improve the type error messages reported for a combinator library. More specifically, how they can help to generate error messages which are conceptually closer to the domain for which the library was developed. The techniques have all been incorporated in the Helium compiler, which implements a large subset of Haskell.

We present the derivation of a space efficient parser combinator library: the constructed parsers do not keep unnecessary references to the input, produce online results and efficiently handle ambiguous grammars. The underlying techniques can be applied in many contexts where traditionally backtracking is used.We present two data types, one for keeping track of the progress of the search process, and one for representing the final result in a linear way. Once these data types are combined into a single type, we can perform a breadth-first search, while returning parts of the result as early as possible.

Even when programming in a statically typed language we every now and then encounter statically untypable values; such values result from interpreting values or from communicating with the outside world. To cope with this problem most languages include some form of dynamic types. It may be that the core language has been explicitly extended with such a type, or that one is allowed to live dangerously by using functions like unsafeCoerce. We show how, by a careful use of existentially and universally quantified types, one may achievem the same effect, without extending the language with new or unsafe features. The techniques explained are universally applicable, provided the core language is expressive enough; this is the case for the common implementations of Haskell. The techniques are used in the description of a type checking compiler that, starting from an expression term, constructs a typed function representing the semantics of that expression. In this function the overhead associated with the type checking is only once being paid for; in this sense we have thus achieved static type checking.

Abstract The design and verification of distributed and concurrent algorithms is highly complex, and thus error-prone. It is our experience that the intertwined use of an informal description as well as a formal method in designing and studying an algorithm, is a fruitful one. The advantage of the informal description is the ease with which algorithms can be produced, studied and discussed. In contrast with formal methods however, errors are easily made in informal arguments about programs that seem to be correct, but in fact are not. In this paper we use an informal argument, carefully augmented with the use of the UNITY formalism, in the design of a distributed algorithm for maintaining the maximum value of a bag of frequently changing integers on a hierarchically divided network. The resulting algorithm is obtained by first designing an abstract algorithm on a virtual datastructure. Next, the abstract algorithm is transformed into the distributed algorithm.

A new kind of attribute grammars, called higher order attribute grammars, is defined. In higher order attribute grammars the structure tree can be expanded as a result of attribute computation. A structure tree may be stored in an attribute. The term higher order is used because of the analogy with higher order functions, where a function can be the result or parameter of another function. A relatively simple method, using OAGs, is described to derive an evaluation order on the defining attribute occurrences which comprises all possible direct and indirect attribute dependencies. As in OAGs, visit-sequences are computed from which an efficient algorithm for attribute evaluation can be derived.