Integrating Functional and Imperative Programming

We present a class of programming languages that enables the advantages of functional and imperative computation to be combined within a single program. These languages, which we call fluent languages, have distinct sublanguages for functional and imperative programming. Sublanguage invariants are verified by a static checking system that simultaneously determines the type and the effect cla~8 of every expression. Effect checking is similar to type checking, but it is used to guarantee side-effect invariants instead of value invariants. Effect checking also makes it po~ible to implement polymorphism in a general, type-safe and efficient manner despite the presence of side-effects. Preliminary simulation results suggest that fluent programs are well suited for parallel processing. This work was supported in part by DARPA/ONR contract number N00014-83-K-0125 Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specfic permission. 1. I n t r o d u c t i o n Functional languages are widely recognized for their expressive power and straightforward semantics. Their mathematical simplicity makes them a suitable vehicle for formal analysis and program verification. Moreover, the semantics of a functional language typically permit many different implementations, including normal order, applicative order, lazy, and eager evaluation and memoization [Abelson851. These advantages have motivated a great deal of research into functional languages [Backns78], functional programming [HendersonS0], and the design of computers that can execute functional programs rapidly and efficiently [Gurd85]. Imperative languages, on the other hand, retain certain advantages over functional languages. First, some programming tasks, for example input and output, are most naturally viewed in terms of operations with sideeffects. Second, the implementations of most imperative languages are still more efficient than those of functional languages.  This paper describes a class of programming languages that offers the benefits of both functional and imperative programming by permitting programmers to mix functional and imperative computation in a single program. We call a programming language that directly supports both functional and imperative programming a fluent language. One of the premises behind fluent languages is that sideeffect information is important enough to be declared as part of the type of a program. Such side-effect declarations document a programmer's intent and  28 provide valuable information for optimization and parallel execution. Fluent languages support this programming methodology by verifying the type and side*effect assertions provided by the programmer. In a fluent language side*effects are described in terms of e f fec t cla88~. Every expression has an effect class; just as the type of an expression describes the value computed by the expression, the e f fec t class of an expression describes how that value is computed. Effect classes will be defined in detail below. Examples of effect classes include "OBSERVER" and "FUNCTION": an expression that is an OBSERVER can observe side*effects, but it can not cause them, while a FUNCTION can neither cause nor observe side*effects. The effect class of an expression determines the sublanguage to which the expression must be confined, which in turn determines which language facilities the expression may use and what subroutines it may call. At the same time, the side*effect specification of a subroutine determines which sublanguages may call it. Restricted approaches to mixing functional and imperative programming have previously been suggested as a way to mitigate some of the shortcomings of functional programming, in particular the difficulties with persistent objects and input /output . For example, Backus suggested the notion of Applicative State Transit ion Systems [Backus78]. In an AST system all computation must occur in the functional language; the imperative part of a program consists of transition rules that are used to select functions that update the system state. The designers of the programming language Euclid [Lampson78] also recognized the power of mixing imperative and functional programming. In Euclid, procedures are executed solely for their side*effects (they return no result value) and functions are executed solely for their result value (they can cause no side*effects). This strict separation between procedures and functions is intended to simplify program correctness proofs. However Euclid's s tatement oriented style and its lack of higher order functions and procedures limit its use for constructing substantial functional program components. A third approach for mixing functional and imperative computation is to employ an inference system to determine which portions of an imperative program are functional. This approach has been used to decompose imperative programs for parallel processing [lVlarti83]. Effect classification systems tha t are based exclusively on inference have three limitations: • Express ive Power Ful ly automatic, 'hidden' effect inference leaves the programmer with no way to document or verify in tended side*effect invariants, such ~ referential transparency. In the absence of documentation or verification small changes to a program may result in a dramatic change in performance. • Separate Compi la t ion Separate compilation forces the inference system to make worst-case assumptions about external subroutines. The inductive nature of side-effect inferences tends to cause suboptimal side-effect classifications to propagate throughout the program. • Subroutine Variables ~ It is difficult to determine the side*effects of calls on subroutine variables. In cases where da ta flow analysis fails to identify the subroutine(s) being called, the side*effect inference system must sasume the worst. Another viewpoint on the lat ter two limitations is that effect classification systems based exclusively on inference are sometimes unable to compute a t ight bound on the effect class of an expre~ion without additional information. I t is precisely this additional information that fluent languages are designed to provide. Unlike the three other approaches presented above (AST systems, Euclid and effect inference), fluent languages are designed to support a programming methodology in which programmers can freely mix functional and imperative programming. The proper mix is determined by the requirements of the application. A program written in a fluent language can be written in a completely functional style, in a completely imperative style, or in any combination of styles. Our discussion of fluent languages is organized into' the following topics: • Section 2 effect .cis~ses; • Section 3 a specific fluent language; • Section 4 effect checking; • Section 5 applications to polymorphism; • Section 6 implementation issues; • Section 7 simulation results; and • Section 8 ~ conclusions and future work.