Magma2(ID:1094/mag013)Language that allows programmability of the control environment, e.g. recursion, backtracking, coroutines, nondeterminism, etc. Related languages
References: Extract: INTRODUCTION 1. INTRODUCTION Magma2 is an experimental language aimed at providing an environment where control is programmable in an orderly way. Indeed the key idea of the design is not only to provide user programmability of control regimes but also to separate this activity from the design of application programs. The user programs in Magma2 - First by selecting from a library of control environments the most suitable one for the task at hand. If the environment is not available, the user'should be able to realize it with minimal effort and independently from the development of the application program. - Second, by developing the application program in this new language, that is, the Magma2 application language enriched by the selected control environment. The benefits of programmability of control regimes can be justified by the many recent proposals of new control regimes, each of which is claimed to be more suited for certain classes of tasks. The benefits of encapsulating away the implementation of control regimes should be clear: - reusability of the modules implementing control abstractions; - complete separation between the tasks of realizing a control environment and the task of using it in application programs; - verifiability of the correctness of control regimes independently from application programs. In other words, the same benefits that are claimed for the encapsulation principle of abstract data types can be claimed for the encapsulation principle of control abstractions. Magma2 is not the first language to allow control programmability. Here, Magma2 is compared with its natural parent, MagmaLISP [13], with other proposals discussed later on. The panorama surrounding the design of MagmaLISP was the effort of the international AI community to design software development systems amenable to the construction of large AI systems: natural-language understanding systems, theorem provers, program verifiers, etc. The prototypical model for this kind of systems was Planner [7]. Planner was never implemented as such, but its progeny soon became numerous [1, 21]. The common features among these languages are that they are LISP based and that they provide unconventional control structures, principally nondeter- ministic ones. LISP was the first choice because it was the official language of the AI community; it was the official language because it is both oriented to nonnumerical computations and naturally interactive. Thus our language was Magma... LISP, too. The goal of MagmaLISP was, as expected, to create an environment where control features like funargs, funvals, coroutines, and backtracking were not built in, but programmable. The strength of the design was the recognition that extensions to the standard recursive regime (e.g., coroutining) and nondetermin- istic features have to be kept independent as much as possible. For instance, coroutines should not necessarily be used to represent computations originated by the traversal of a choice point, and vice versa. If the application at hand demands that regime, it can be programmed, but it is not embedded in the language. The idea was to define in the language two data types, applications (roughly, activation frames) and contexts (a basic object for implementing state- saving mechanisms), and operations for manipulating them. The two data types are kept as orthogonal as possible, and this was the real strength. The deficiencies of MagmaLISP are essentially that the programmability of applications is limited by an underlying structure (a tree) and the complete lack of an encapsulation mechanism. Indeed, concepts like abstraction and encapsulation were then nascent. Furthermore the concepts of abstraction and encapsulation have been developed in the realm of defining new types in programming languages [11, 17, 24] and of minimizing interfaces among different modules of the same system [16]. The idea of generalized abstractions of control has been pursued with much less vigor, the exceptions being [6] and Hewitt's Actors system [8]. The basic claim of this paper is that the paradigm of programming via abstractions can be used both for control and data. The problem to solve is to provide a programming language, where all possible data types (control regimes) useful to organize application programs can be defined. The solution is to provide some very low-level data types (control objects) and elementary operations plus a structured way of defining, abstracting, encapsulating, and protecting new data types (control regimes). For example, Alphard's inventors [24] propose the data type rawstorage as the only built-in data type in the language. All the data types necessary for a specific application are abstracted, level by level, from rawstorage via the mechanism of form definitions. The paper by Shaw [18] gives an example of this process. CLU's inventors stress the necessity of libraries of abstract data types so that the shape of the language can be tailored by picking up the appropriate clusters from a library. Magma2 owes as much to these new ideas as to the original design of MagmaLISP. Extract: A FORMAL MODEL OF MAGMA2 2. A FORMAL MODEL OF MAGMA2 This section presents a model capturing the notions necessary to define abstractions of control. The model is not developed in full detail, but it should be precise enough to make the basic principles of Magma2 more rigorously understandable. The model adapts to any programming language in which the execution of a program is defined to be the cooperation of computation agents via linkage requests. For example, in ALGOL-like languages computation agents are procedure instantiations, and the set of linkage requests are calling a procedure and returning from a procedure. The ultimate goals of this paper are, on the one hand, to define a semantic model able to describe programming languages with unusual control features, and, on the other hand, to realize the model as a programming language. The net result will be a language where control can actually be programmed. The semantic model is based on three classes of objects: (1) Behaviors, that is, the denotations of computation agents. A behavior is a function that maps value domains to value domains and structures, named closures, that contain behaviors. This is the key idea underlying the design of Magma2 and its semantic model. In fact, a behavior can be regarded as an entity performing some computation and then offering some intermediate results and a new behavior to the surrounding control environment. Thus, it is in the surrounding control environment that the general strategy of control can be organized via sequencing behaviors. (2) Linkage request values. It is via linkage requests that computation agents communicate results and closures to the control environment. (3) Control environments. Very informally, the control environment is the runtime support of the language. The idea is that linkage requests must be kept at a very high level, that is, they must not choose which behavior has to take control next. It is the task of the control environment to retain enough bookkeeping information to be able to integrate the linkage request and compute such a behavior. Hence, a control environment is defined to be a bookkeeping data structure ("control structure," from now on) and a set of functions implementing the linkage requests ("linkers," from now on). A program is the combination of a set of computation agent definitions and a control environment. Since the control environment is, in general, common to several application programs, it has to have a semantic description independent of the application programs themselves. The semantics of a control environment is formally given as the algebraic semantics of the control structure and the denotational semantics of the linkers. Computation agent definitions are written in a language termed Application Language, whereas control environments are coded in a language termed Control Language. Both languages have a LISP-like syntax. Syntax and semantics of the two languages are given according to a denotational style [3]. in TOPLAS 6(4) October 1984 Lecture Notes in computer science Vol. 174 view details |