Functions, Frames, and Interactions

completing a λ-calculus-based purely functional language with respect to programming-in-the-large and interactions with runtime environments

Claus Reinke


Thesis Abstract:

The original aim of the work that led to this dissertation was to extend an existing, purely functional language with facilities for input/output and modular programming. The language is based on an untyped λ-calculus, i.e., program execution is defined as program transformation according to a fixed set of reduction rules including β-reduction. Consistently, the implementation comprises an interactive reduction system which is integrated with a syntax-oriented editor: any sub-expression or program result can be submitted for (stepwise) reduction. There is no distinguished main program, no `global' environment and no explicit static part of the language -- in particular, there is no static type system. It is therefore not clear how to add one of the known solutions for input/output or modular programming to such a programming environment. Furthermore, simply adding features to the language would lead to a complex language design with weakly integrated parts, thus losing much of the appeal of purely functional languages.

Help with the latter problem comes from the history of general programming language design: when formal language description techniques were developed and applied to early high-level programming languages, various inconsistencies in the designs of those languages were discovered. To avoid such defects, language design methods based on semantic principles were proposed, such as the principles of abstraction, correspondence and data type completeness. These semantic principles are not biased towards technical details, but rather guide the way from the basic constructs of a language towards a simple and elegant overall language design.

To isolate the fundamental language constructs needed for our particular design problem, we review the support for input/output and modular programming in current functional languages. Surprisingly, we find that most of these languages fall short of adhering to the principles of language design in several respects. We identify some of the problems that result from this fact and argue that, by consistently following the design principles both for the design of the extensions and for the integration of the extensions into the complete language, the weaknesses found to exist in other languages can be avoided. To support this claim, we present a simple language design: we start with a purely functional core based on the λ-calculus, extend it with input/output-facilities and record-like data structures called frames, and complete the language with respect to the design principles.

We go on to show how the resulting design supports a wide range of modular programming techniques and identify the various special purpose constructs used in other languages as instances of a general scheme of abstraction (high-level programming languages also follow this scheme and provide advantages similar to libraries of pre-defined program components). We conclude that modules, objects and other language constructs for modular programming need only be provided as built-in features in languages which are restricted in their support for general abstraction. This leads to a slightly different view of our proposed language design: λ-calculus should not be seen as a part of the functional core language, but rather as providing the means for abstraction over all available language primitives which in our case are not only functions, but also frames and interactions.

Our language design features functions, interactions, and modules as first-class data objects, and the input/output-facilities are not restricted to strings of characters, but are applicable to any valid language expression. The latter feature opens a connection between the research areas of purely functional languages and persistent systems, and we argue that both research communities could profit from closer cooperations, avoiding a lot of duplicated work where interests are shared and stimulating and complementing each other where interests differ.


Comments: The dissertation was submitted to the Faculty of Engineering at the University of Kiel. The thesis defense took place in November 1997. The dissertation was published as technical report no. 9804, Department of Computer Science, University of Kiel. For hardcopies, please contact
-- Insitutsberichte --
Institut fuer Informatik und Praktische Mathematik
Olshausenstrasse 40
Christian-Albrechts-Universitaet
24098 Kiel
Germany
or the author (i.e., me;-). Online versions are also available: PostScript (Kiel) PDF (local)