FAD(ID:7883/)Simple functional language, but supporting abstract data types - derived from FP, although APL and Curry are also cited as influences Related languages
References: Extract: Overview of FAD Overview of FAD In structure and style, this section closely follows Backus' description of FP systems. Aside from smaller notational differences, which are mostly concessions to the ASCII character set, FAD deviates more substantially from Backus' system by introducing (i) the notion of a set of items, (ii) the distinction between items and objects, (iii) the encapsulation mechanism, (iv) the type mechanism, and (v) the already mentioned facilities for naming selectors and using infix operators. (i) Items are arranged to form sets. These sets are described by item expressions, a system similar to regular expressions. However, sets of items are not regular sets. Sets of items represent both data and functions. (ii) Whereas items constitute the raw material from which all objects are constructed, objects themselves are pairs of two items called type and value. (iii) Definitions of functions or data can be encapsulated. With a single scope rule, this mechanism provides the import and export facilities needed for the definition of abstract data types. (iv) Abstract data types can be declared and their proper use is enforced by the language translator. Throughout the rest of the paper, comments injected into formal definitions are set off by '//'? The following initial description ignores types and deals in turn with - item expressions and naming, - functions, - functional forms, - encapsulation. Extract: Introduction Introduction Programming restricted to defining and applying functions has a long history. Its theoretical roots reach back to the theory of recursive functions [Kleene36], the lambda calcules [Church41], and the system of combinators [Curry58]. The first well known practical programing language of the functional type (based on the lambda calcules) is LISP [McCarthy60], and a later one is APL [Iverson62]. Both languages, although extensively used by researchers in certain areas, are not among the most popular ALGOL-type languages such as FORTRAN, COBOL, PL/I, or Pascal. However, it has been doubted whether the trade of programming is best served by languages of this conventional type. Experience shows that in particular the ambitious conventional designs that try to embrace the state of the art grow into ever larger, amorphous collections of 'features'. Although this trend may not be technically inevitable, it certainly is conspicuous in practice. Backus [Backus78] calls the conventional languages fat and flabby and points out that a "large increase in size brings only a small increase in power1. In addition to this disproportion of size and power, ALGOL-type languages lack mathematical properties conducive to program analysis and verification. This is due in part to their sheer size and multitude of diverse features, in part to their use of successive state transformations as the model of computation. In fact, the variable, the assignment statement, and the subroutine (in contrast to the function procedure), which are the tools used and needed for transforming the state ot computation, are responsible not only for what is called side effect and alias problems but also for rather awkward appendages to otherwise very concise and elegant description mechanisms. Compare, for example, Guttag's original algebraic specification method for abstract data types [Guttag75] with the form extended to accommodate subroutines and functions with side effects [GHM77]. Backus deals with these questions in great depth and finally concludes that only a radically different language structure can eliminate the trouble. He consequently proposes a new breed of languages called Functional Programming (FP) systems. These systems, though related to LISP and APL, are also distinctly different: simpler. The language FAD outlined here belongs into this category. FP systems basically consist of a mechanism for defining new functions from existing ones. The foundation of any edifice of function definitions is a language defined set of so-called primitive functions. Functions always have exactly one object as a parameter and they return one object as a result. Both objects, the parameter and the result, may be of arbitrary complexity. There are no variables and hence no assignment statements; every valid phrase is an expression or a definition. FP languages have many attractive properties. In particular, they - promote well structured programming, - provide algebraic rules for program analysis and verification, - do not suffer from alias or side effect problems, - are easy to compile, and - facilitate efficient storage management. In addition, FAD supports - abstract data types and allows - parameterized types and - generic functions. The absence of side effects makes automatic sharing of like data objects universally possible and transparent to the user. Copying of entire structures is never necessary. Despite these and other advantages, some feel that the concise and well structured FP system programs are frequently much harder to read, to understand, and hence more difficult to design and to maintain than those written with conventional programming languages. However, the author is convinced that this chiefly syntactic problem is not too difficult to correct. It seems that Backus [Backus78] has designed his notation without extensive 'syntactic sugaring' in order to expose the conceptual simplicity of FP systems. In contrast, one of the objectives of this paper is to show that an FP system can be made into a user friendly programming language. Therefore, questions of syntax and of features serving readability are discussed. An other important point is that FP systems are not history sensitive, that is, they have no means to save definitions or results produced by a computation and to recall them later. Therefore, they must be imbedded into an environment capable of performing these tasks for them. This issue, addressed extensively in [Backus78], is not in the scope of this paper. in Proceedings of the ACM 1980 annual conference January view details |