GL(ID:2066/gl:001)for Graduate Level language Gregory F. Johnson and Dominic Duggan Department of Computer Science University of Maryland References: The programming language GL and its environment, in particular the notions of stores and (partial) continuations as dynamically obtainable first-class objects, serve as the basis for an interesting new paradigm for writing, reasoning about, and debugging programs. GL is essentially lambda calculus augmented with several data types and functions to manipulate elements of those types. It is in the tradition of languages such as ML [Milner78], Scheme [Sussman75], [Rees86], and Gedanken [Reynolds70]. In addition to the usual data types such as integer and cb.aracter string, GL basic values include l-values, continuations and partial continuations, and stores. The novel notion that stores can be assigned as values of variables or subjected to other similar manipulations implies that several different versions of “computer memory” during a program’s execution may exist in the interactive program environment simultaneously. This capability turns out to be quite useful in an environment for purposes of interactive program testing and debugging. Multiple stores are implemented efficiently using the persistent data structure concepts of [Driscoll86]. Full and partial continuations offer a similar, complementary capability in the language and environment. A continuation is a function that represents the remainder of execution of a partially executed program, and a partial continuation reflects execution to some future program state possibly before program termination. A full continuation can be decomposed into a sequence of partial continuations, each representing a part of the remaining computation. One useful decomposition is that which corresponds to the sequence of pending function calls. The continuation semantics of GL makes this decomposition explicit. Continuations appear as first-class objects in Scheme; see for instance [Friedman871 for an indication of the range of subtle uses to which continuations can be put. We feel that continuations are particularly useful as a prominent feature of a debugging environment. Several languages have had their designs influenced by the desire for clear or elegant denotational definitions; denotational semantics (c.f. [Scott76)) has had a wideranging influence on programming language research. In a language design effort, the discipline of creating a denotational or perhaps some other formal description of the developing language’s semantics forces a certain care and clarity of thought that typically results in a better language than might otherwise have been obtained. Our hypothesis in the the GL research effort was that similar results might be obtained if the design of certain aspects of the programming environment, in particular the debugger, were subjected to a similar discipline. In carrying out a design effort based on this surmise, we found that a healthy tension developed between the design of the debugger, the language, and the denotational definition of the language. The desire to have an acceptably efficient implementation also played a significant role. (An early version of GL has been used successfully to teach graduate level language and semantics, and a prototype implementation of the research reported herein is now complete.) We have found interactively accessible partial and full continuations and multiple co-existing stores to be particularly useful from the standpoint of the debugger. The major impact of integrating debugger considerations into the overall design process, in fact, was on the definition and semantics of partial and full continuations. In a previous paper ([Johnson87]) we reported on interpreter implementation considerations and semantics for continuations, but at the time of writing of that paper only partial continuations, and not full continuations, appeared explicitly in the denotational definition of the language. In the design of the debugger it became clear that full continuations in addition to partial continuations were necessary. It is quite convenient, when an executing program is stopped, to dynamically capture the full continuation extant at that point and experimentally apply it to different stores. Similarly, it is often convenient to apply the partial continuation representing completion of the most recently invoked function or the most recent few functions to a variety of different stores. The motivating desire to have powerful and flexible partial and full continuation facilities in the debugger prompted a significant recasting of the denotational semantics for the language. A typical continuation semantics for a language may be thought of as compositional: One extends a continuation (i.e., takes a “tail” of a program execution and makes a longer tail by prefixing to the original tail what happens in the program’s execution im mediately prior to it) by composing the continuation with a function representing the effect of the program fragment that immediately precedes it during program execution. in [ACM SIGACT-SIGPLAN] Proceedings of the Fifteenth Annual ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, San Diego, California (January 1988) view details |