13870178
Simplifying and improving qualified types
Qualified types provide a general framework for constrained type systems, with applications including type class overloading, subtyping and record calculi. This paper presents an extended version of the type inference algorithm used in previous work, that can take account of the satisfiability of constraints to obtain more accurate principal types. The new algorithm is obtained by adding two new rules, one for simplification and one for improvement of constraint sets. In particular, it permits a better treatment for the previously troublesome multiple parameter extensions of Haskell type classes. For example, a form of parametric type classes, proposed by Chen, Hudak and Odersky, can be viewed as a special case of this work.
1424753
Monad transformers and modular interpreters
We show how a set of building blocks can be used to construct programming language interpreters, and present implementations of such building blocks capable of supporting many commonly known features, including simple expressions, three different function call mechanisms (call-by-name, call-by-value and lazy evaluation), references and assignment, nondeterminism, first-class continuations, and program tracing.
The underlying mechanism of our system is monad transformers, a simple form of abstraction for introducing a wide range of computational behaviors, such as state, I/O, continuations, and exceptions.
Our work is significant in the following respects. First, we have succeeded in designing a fully modular interpreter based on monad transformers that incudes features missing from Steele's, Espinosa's, and Wadler's earlier efforts. Second, we have found new ways to lift monad operations through monad transformers, in particular difficult cases not achieved in Moggi's original work. Third, we have demonstrated that interactions between features are reflected in liftings and that semantics can be changed by reordering monad transformers. Finally, we have implemented our interpreter in Gofer, whose constructor classes provide just the added power over Haskell's type classes to allow precise and convenient expression of our ideas. This implementation includes a method for constructing extensible unions and a form of subtyping that is interesting in its own right.
6608650
Dictionary-free overloading by partial evaluation
One of the most novel features in the functional programming language Haskell is the system oftype classes used to support a combination of overloading and polymorphism. Current implementations of type class overloading are based on the use ofdictionary values, passed as extra parameters to overloaded functions. Unfortunately, this can have a significant effect on run-time performance, for example, by reducing the effectiveness of important program analyses and optimizations.This paper describes how a simple partial evaluator can be used to avoid the need for dictionary values at run-time by generating specialized versions of overloaded functions. This eliminates the run-time costs of overloading. Furthermore, and somewhat surprisingly given the presence of multiple versions of some functions, for all of the examples that we have tried so far, specialization actually leads to a reduction in the size of compiled programs.
15051631
Type Classes with Functional Dependencies
Type classes in Haskell allow programmers to define functions that can be used on a set of different types, with a potentially different implementation in each case. For example, type classes are used to support equality and numeric types, and for monadic programming. A commonly requested extension to support 'multiple parameters' allows a more general interpretation of classes as relations on types, and has many potentially useful applications. Unfortunately, many of these examples do not work well in practice, leading to ambiguities and inaccuracies in inferred types and delaying the detection of type errors. 
 
This paper illustrates the kind of problems that can occur with multiple parameter type classes, and explains how they can be resolved by allowing programmers to specify explicit dependencies between the parameters. A particular novelty of this paper is the application of ideas from the theory of relational databases to the design of type systems.
9087296
Using Types to Parse Natural Language
We describe a natural language parser that uses type information to determine the grammatical structure of simple sentences and phrases. This stands in contrast to studies of type inference where types and grammatical structure play opposite roles, the former being determined by the latter. Our parser is implemented in Haskell and is based on a linguistic theory called applicative universal grammar (AUG). Our results should be interesting to computer scientists in the way in which AUG relates to types and combinatory calculus, and to linguists in the way in which a very simple, brute force parsing strategy performs surprisingly well in both performance and accuracy.
14189118
A Theory of Qualified Types
• The ability to include local constraints as part of the type of an object. This enables the definition and use of polymorphic overloaded values within a program. ∗An earlier version of this paper was presented at the European Symposium on Programming, Rennes, France, February 1992 and appears in the conference proceedings published in Springer Verlag LNCS Volume 582. †Address from September 1992: Yale University, Department of Computer Science, P.O. Box 2158 Yale Station, New Haven, Connecticut 06520-2158, USA.
12348986
Dynamic Digital Library Construction and Configuration
This paper describes a digital library architecture and implementation that is configurable, extensible and dynamic in the way it presents content and in the services it provides. The design manifests itself as a network of modules that communicate in terms of XML messages. All modules characterize the functionality they implement in response to a “describe yourself” message, and can transform messages using XSLT to support different levels of configurability. Traditional library values such as backwards compatibility and multiplatform operation are combined with the ability to add new collections and services adaptively. The paper describes the new design and shows how it can be used to build four different digital library systems. We conclude by showing how the design fits existing interoperability frameworks.
7924764
Organizing digital music for use: an examination of personal music collections
Current research on music information retrieval and music digital libraries focuses on providing access to huge, public music collections. In this paper we consider a different, but related, problem: supporting an individual in maintaining and using a personal music collection. We analyze organization and access techniques used to manage personal music collections (primarily CDs and MP3 files), and from these behaviors, to suggest user behaviors that should be supported in a personal music digital library (that is, a digital library of an individual’s personal music collection).
13294915
Voxelisation: Modelling for Volume Graphics
Voxelisation is the term given to the process of converting data from one source type into a three dimensional volume of data values. The techniques known collectively as volume visualisation can then be applied to the data in order to produce a graphical representation of the object. This paper gives a new practical approach to the voxelisation of data which fills the entire volume. Its use is demonstrated on various datasets such as triangular mesh objects, CT data, and objects defined by trivariate functions.
6148133
Wild Things
The children's book Where the Wild Things Are by Maurice Sendak was animated using Alice version 2.0 for an introductory undergraduate 14-week programming course at Immaculata University. Using the software development lifecycle, the designers/developers collaborated on the requirements and design phases while the implementation phase was completed individually. The animation was designed and developed with the intent of applying objectoriented principles and reusing objects where appropriate.
 Three individual scenes were created using Alice version 2.0. Upon the completion of the scenes, a screen capture tool (Hypercam2), and an audio capture tool (River Past) were used to break down the animation. Those components were synchronized using Windows Movie Maker and then the animation was converted to a Flash file.
 • Scene 1 - Tommy's Bedroom: Tommy is sent to his room and his imagination creates a jungle that grows around him.
 • Scene 2 - Sailing the Ocean: Tommy imagines sailing across the sea towards an island and encounters wild things along the way.
 • Scene 3 - An Island Encounter: Tommy reaches the island and meets the wild things only to awaken back in his bedroom as his mother calls him for dinner.
9636203
Two case studies in predictable application scheduling using Rialto/NT
This paper analyzes the results of two case studies in applying the Rialto/NT scheduler to real Windows 2000 applications. The first study is of a soft modem-a modem whose signal processing work is performed on the host CPU, rather than on a dedicated signal processing chip. The second is of an audio player application. Both of these are frequently used real-time applications-ones running on systems that were not designed to support predictable real-time execution. To function correctly, both applications require that ongoing computations be performed in a timely manner. In both cases, we first measured an original version designed to run on Windows 2000, and then modified the application to take advantage of ongoing CPU reservations provided by the Rialto/NT scheduler. We report on the benefits and problems observed when using reservations in these real-world scenarios. In both cases, we found that a real-time scheduler can provide the needed predictability for the application in the presence of competing applications, while also providing other benefits, such as minimizing the soft modem's impact on the scheduling predictability of other computations in the system. We also describe the methodologies we used to analyze the real-time behavior of the operating system and applications during these studies, including the use of instrumented kernels to produce execution traces.