[ Up | HLL | Sitemap | CLiki ]
The language, in order to be the adaptible medium that the Tunes project requires to be a properly unified system, has to have an open generic architecture that can encompass both the most complicated formal systems and the least complicated simple evaluation and encoding schemes.
The intent is to generalize the canonical Lisp read-eval-print loop and apply Tunes principles as uniformly across the resulting stages as possible. Here are the proposed new stages:
The concept to keep in mind about these phases is that they are ignorant of what is compiled and what occurs at run-time. That is, it works in the sense that it is subjectable to Tunes partial evaluation in various ways. So this is an abstract chain of phases.
Furthermore, these phases can be somewhat overlapping in the case of movement of binding of various parts of a whole language. Also a single language environment built with from this system may define several grammars or dispatch mechanims, and in each case, these may be defined to have static or dynamic binding independently. So this architecture is not really one that encompasses everything at once, but it defines re-usable components for a language to combine per-feature, and as a result these phases may overlap between compilation time and evaluation time (but not per expression). Finally, Tunes promises that partial evaluation will be applicable wherever possible, and that this can further re-define the staging within the allowances of the particular resulting language's semantics.
Overall, the major shift is that the phases have been divided into further parts. Also important is that reading and evaluating are divided by a run-time boundary instead of Lisp's boundary where the output of the read phase enters evaluation which is then divided between compile- and run-times. So the major phases are now "input", "run-time", and "output" where input and output are interfaces to other contexts, such as text entry or some encoding for transport.
Readtakes in a stream of character objects and dispatches on them according to a flat table. Other tables may be substituted, particularly by the reader-macros indexed by this table, but this is not usually done, and a general architecture for it is not commonly known or looked into. The Tunes substitution for this idea employs the generalized concept of Dispatch noted below (but applied to parse-level inputs) to give this a more expandable architecture. The overall intent here is to provide a framework at least as general as that for syntax in Maude, which means as much as context-free grammar parsing, with control over precedence and fixity of specifications. In summary, applying dispatch together with Maude's (meta-)parsing library architecture is what makes Parse so unique and powerful.
At each level, there are varying degrees of expressiveness, partially-ordered. That means that some means of expression can quite easily express others, but there's no strictly upward direction for this relation. In general, this relationship should be captured explicitly within the system, so that a partial-evaluator may use contextual information to determine how to structure the phases to adapt them to each task.
This is really intended to cover the spectrum of complexities of grammars and their application. The Chomsky hierarchy defines 4 major categories of these grammars, and defines what kind of program is required to comprehend them. Maude's meta-parser handles up to and including Context-Free Grammars, and of course a full programming language is required in general, with no real system for predicting which language from the language examples themselves.
Hundreds of language types have been enumerated, so the main task here is merely to catalog and provide the major convenient types of syntax parsers and the information that relates their specializations.
Ideally, a system for embedding expressions from one language to a less-expressive language should be available, though each method per pair may have to be made manually. It is nevertheless useful to have them fit into a single functionality abstraction.
Code expansion expressiveness depends on the level of information provided by the previous Parse phase, as detailed by these following methods of expansion or semantics-preserving transformation:
In some sense, it seems that this phase could successfully contain non-trivial Dispatch, depending on the topology of the type relations of the Parse phase's output. Also, Rewrite is obviously being employed here, in most systems in a non-side-effecting sense (macros replace themselves usually). Whether more general Rewrite would be beneficial and safe if allowed has not been explored.
The amount of evaluation that can be done on the input argument terms (the extent of eager evaluation) is limited by the particular dispatch semantics chosen for the context. Search parameters only really become non-trivial when the dispatch/rewrite combination is lazy in some way; if some information is not relevant immediately. Otherwise, an evaluation order is implied or a lazy evaluation policy is prescribed.
The following outline the aspects of this phase which are relevant and separate concepts:
The freedom specified for the search phase within an environment or context limits the amount of polymorphism and overloading that is logically allowable for the same context; conversely, the amount of freedom desired in overloading limits the range of search allowed, since the search results must conform to the dispatcher's requirements for an appropriate answer. (Editor's Note: Provide some specific examples about that.)
As described in the Glossary entry for dispatch, there are several algorithms and environment semantics associated with multiple bindings of a function name, and their proper choice. There is a general partial ordering among them, and in more realistic cases, a multiplicity of combinations of these semantics, so that the general case for specialization will be quite complex to automate.
Nevertheless, we will outline here some common reductions in expressiveness among those major methods:
Each of these has their own research areas in terms of algorithms, data structures and storage, and their efficiency. The use of each is commonly capable of expressing some class of dispatch, and the choice is determined by what kind is possible or occurs in practice. This means that the optimization can be chosen because a domain isn't allowed to exceed some semantics or because it has been observed and verified not to do same.
To summarize, these methods are distinguished from each other not by implementation, but by the nature of how names are organized. In a certain sense, this is about the shape of the namespaces' organization.
The object-attribute relation mechanism is the fundamental concept underlying this phase. However, the core semantic primitive of abstraction of terms (lambda abstraction) has to fit into this category, and the category of rewrite is separate from dispatch. So, the semantics of an abstraction must include the search, dispatch, and rewrite semantics in order to be migrated successfully, but the basic specification means will be identical within the environments' differing dispatch semantics.
A rewrite rule, then, is a pair of quoted terms in the most general when its associated dispatch is unification. The nature of the quotation will be considerably significant to this definition. The quoted terms are essentially objects describing the "Situation" of objects required in order to perform a successful match.
As an example of the range of such terms' nature, for each type of dispatch, we will associate the structure shape needed. In each example, a common base of a conglomeration of objects to pass as a single input is implicit. We do not specify the shape of the passed configuration: Lisp's argument lists or other languages' tuples for argument passing are too specific a structure. Positional or keyword passing may be specified separately. The core point here is that the arguments and inputs are matchable in some way. With that in mind, here are the examples, in increasing orders of complexity:
In any case, rewrite reduces to the simplest idea of the object-attribute annotations discussed in the HLL General Concepts outline, since the conglomeration reduces to a single object. In that case, the selector for the attribute is the function's name (a key to a binding, in a sense).
Since our means of specifying rewrites in its most general form uses configurations as outputs, with annotations, there is no longer a trivial answer to the question of how to respond to the listener with a representation of the answer that can be read/parsed back in. For this reason, the migration concept is employed.
The simplest case is common, where the director of the interactive session is in the same scope and interacts with the same environment, so there is no difference in semantics to adapt. However, even in this case, there is the question of what to represent and what to leave implicit, so migration still applies (even if trivial null-migration is applied).
See the HLL Examples area.
This architecture seems to represent a regular organization scheme reflected in a significant spectrum of the programming languages and systems that are considered useful to Tunes in its sense of the word. This architecture answers the question of whether this usefulness can be reflected in practice, while also allowing the HLL design to be a flexible framework instead of a "One True Language".
This document last modified on Sunday, 29-Oct-2006 13:02:07 PST. See the ChangelogWebmaster