916 papers · page 42 of 46
Abstract Interpreting η-conversion as an expansion rule in the simply-typed λ-calculus maintains the confluence of reduction in a richer type structure. This use of expansions is supported by categorical models of reduction, where β-contraction, as the local counit, and η-expansi…
Abstract This paper describes a flexible type system that combines overloading and higher-order polymorphism in an implicitly typed language using a system of constructor classes —a natural generalization of type classes in Haskell. We present a range of examples to demonstrate t…
Abstract We introduce a λ-calculus notation which enables us to detect in a term, more β-redexes than in the usual notation. On this basis, we define an extended β-reduction which is yet a subrelation of conversion. The Church Rosser property holds for this extended reduction. Mo…
Abstract Monitoring semantics is a formal model of program execution which captures ‘monitoring activity’ as found in profilers, tracers, debuggers, etc. Beyond its theoretical interest, this formalism provides a new methodology for implementing a large family of source-level mon…
Abstract The construction of a parallel vision system from Standard ML prototypes is presented. The system recognises 3D objects from 2D scenes through edge detection, grouping of edges into straight lines and line junction based model matching. Functional prototyping for paralle…
Abstract We study the type inference problem for a system with type classes as in the functional programming language Haskell. Type classes are an extension of ML-style polymorphism with overloading. We generalize Milner's work on polymorphism by introducing a separate context co…
Abstract We present purely functional implementations of queues and double-ended queues (deques) requiring only O (1) time per operation in the worst case. Our algorithms are considerably simpler than previous designs with the same bounds. The inspiration for our approach is the …
Abstract We have built a portable, instrumentation-based, replay debugger for the Standard ML of New Jersey compiler. Traditional ‘source-level’ debuggers for compiled languages actually operate at machine level, which makes them complex, difficult to port, and intolerant of comp…
Abstract We show that any recursively enumerable subset of a data structure can be regarded as the solution set to a Böhm-out problem.
Abstract This paper presents an application of functional programming in the field of molecular biology: exploring the conformations of nucleic acids. The Nucleic Acid three-dimensional structure determination problem (NA3D) and a constraint satisfaction algorithm are formally de…
Abstract Communication lifting is a program transformation that can be applied to a synchronous process network to restructure the network. This restructuring in theory improves sequential and parallel performance. The transformation has been formally specified and proved correct…
Abstract This paper describes a data-intensive application written in a lazy functional language: a server for textual information retrieval. The design illustrates the importance of interoperability, the capability of interacting with code written in other programming languages.…
Abstract Baby Modula-3 is a small, functional, object-oriented programming language. It is intended as a vehicle for explaining the core of Modula-3 from a biased perspective: Baby Modula-3 includes the main features of Modula-3 related to objects, but not much else. To the theor…
Abstract A functional approach presents a fresh perspective on the problem of animation. We present an implementation of a functional animation system written in Haskell, and illustrate how it may be used to create simple and colourful animations.
And Joktan begat Almodad, and Sheleph, and Hazarmaveth, and Jerah, and Handoram, and Uzal, and Diklah, and Obal, and Abimael, and Sheba, and Ophir, and Havilah, and Jobab: all these were the sons of Joktan. — Genesis 10:26–29
Abstract To illuminate the fundamental concepts involved in object-oriented programming languages, we describe the design of TOOPL, a paradigmatic, statically-typed, functional, object-oriented programming language which supports classes, objects, methods, hidden instance variabl…
Abstract Many of the details that a programmer must manage when programming in a procedural language are handled by the implementation in a functional language. In a parallel functional language, we would expect the assignment of processes to processors and the scheduling of proc…
Abstract Large functional programs are often constructed by decomposing each big task into smaller tasks which can be performed by simpler functions. This hierarchical style of developing programs has been found to improve programmers' productivity because smaller functions are e…
Abstract We present here a generalization of A-translation to a class of pure type systems. We apply this translation to give a direct proof of the existence of a looping combinator in a large class of inconsistent type systems, a class which includes type systems with a type of …
In 1979, Klop (1980), answering a question raised by Mann in 1972, showed that the extension of λ-calculus with subjective pairing is not confluent. We refer to Klop (1980) and Barendregt (1981, revised 1984) for a perspective. The term presented by Klop to provide a counterexamp…