Mixing Languages

Introducing mixed languages

In this section, we look at the idea of having different languages at different levels of the tower---a possibility mentioned in earlier work on reflection [Danvy And Malmkjær 88], but not investigated further there, as, for simplicity in describing reflective interpretation, the languages were taken to be the same at all levels. However, in the Mix system [Jones, Sestoft And Søndergaard 87] the languages are taken to vary between the different programs being mixed together.

The desirability of mixed languages

Mixed-language systems have been around for a while now, often for specific tasks. They are used when specific features of several languages are all combined. Typically, use of one language is nested within use of another. This may be done as a way of extending an existing language, or as a way of developing a new language without having to develop the parts of it that are already done adequately by an existing one. There are several such language combinations in common use on Unix systems, for example:

Other language systems which in effect combine languages are those in which different areas of one language are so dissimilar that they are handled separately, or are separated for convenience of implementation. Examples of this include:

Such arrangements, being well-established in practice, have shown themselves to be powerful and effective. They are, perhaps, examples of the best tools being selected for particular jobs, making elegant combined tools available. This may also take some other forms, such as merging pieces of assembly-language code in-line in FORTRAN or C (asm statements) or use of such a feature as the unix system(2) call, which allows a C (or other compiled language) program to interpret a line of shell, which might run any form of program---either a shell script or a program in any compiled (or interpreted) language---while also using the shell's own features, such as wildcard expansion.

When languages occur in groups or pairs like these, often one of them is being used as a higher-level language than the other---closer to its application domain. For example, in YACC, the YACC parts of the program are a higher-level description of what the program has to do, while the C is used for low-level actions. In many of these cases, the higher-level of the two is also more specific to its application field, and the lower is a relatively general language, for example tbl is specialized for typesetting tables, whereas troff, with which tbl works, is a general-purpose typesetting language.

It is interesting to note that Unix---a system designed, or allowed to evolve, more on practical considerations than for abstract theoretical elegance---includes, in its model of loading and executing programs, a device for allowing program files to be interpreted automatically by an interpreter specified in the file. When a file is about to be loaded for execution, its first few bytes are examined for being a particular magic number (representing the ASCII string \#! or \#! /). If this is found (instead of the magic number value that indicates an executable machine-code file), the program in the file named in the following bytes of the original file is run instead, using the original command line arguments but with the original filename and optional flags (from the original file) prepended. This mechanism, originally provided to allow a choice of shell languages with automatic selection of the right one for each shell script, allows an interpreted program (in any language) to be run in place of a compiled one---with the one restriction that the interpreted language must allow \# as a comment character! This is a tower of interpretation, although one which does not necessarily provide a program with means to access itself or its interpreter.

Another way in which mixed-language working is useful is in the provision of libraries of useful routines (for example, numerical algorithms); with cross-language calling being available, a library written in one language (chosen for its suitability for that use) may be used by programs written in any language, thus avoiding the need either for writing a version of the library for (and in) each language from which it is to be used, or for writing an interface library (typically written in assembler) to perform the adaptations from one language's calling protocol to another's. A practical example of this is that the NAG FORTRAN library is now provided with a set of C header files, to enable it to be called directly from C programs.

With truly first-class mixed-language working, there need be no visible seams where routines written in different languages fit together.

Here, we attempt to formalize mixed-language working, and provide a general means for describing languages.

The requirements of mixed-language working

A system in which mixed-language working is available as a first-class feature has several requirements on its design not usually taken into consideration when designing an ordinary, single-language, program execution system.

A common framework for interpretation must be found into which a wide variety of languages may be fitted. At the same time, this framework must be suitable for reification and reflection---programs, program state, and languages must be in forms that can be manipulated readily: everything should be decomposable (or destructurable) to a suitably fine level---for example, it should be possible to extract the representation of a variable binding, a statement in a program, a term in an expression, a construct in a language---and all these representations should be the same in all languages.

There are two areas in this design task: a suitable representation for the static parts of the system---program and interpreter; and one for the dynamic parts---the program's state and the interpreter's state.

It turns out that the most flexible representation for the procedures of a program leads naturally to a representation for languages which has a suitable granularity for picking out individual language constructs and manipulating them. We weave this representation into the basic structure of closures (as described in clochap), and in doing so find a solution to storing the dynamic part of the system: the application data and application state data, which are stored in the variable storage (value list and environment) of the program and its interpreter respectively. This form of data storage fits many languages' models of variable access very well.

A common program representation

Using a program representation based on parse trees and a state representation based on stacks or continuations, our mechanisms can support a wide range of languages. Lisp in some form (Scheme being perhaps the best example [Rees And Clinger 86]) is perhaps the language that is closest to our model---also having the advantage of very little syntax. Scheme is the dialect most commonly used for reflection experiments so far, but the differences are not significant in the examples given. Being a simple representation of a parse tree, a Lisp expression is a convenient way of representing constructs parsed from other languages, and so we use it here as our main language for describing features relevant to languages in general. Since the core of Lisp is a particularly simple language, we will also give special attention to how it maps onto our reflective system, taking it as the primary example language.

Also, Lisp is both a functional language and an algorithmic one, and thus its structure is able to receive conveniently mappings from either of these types of language. The form of Lisp that we use here includes state-dependent operators such as while loops, and assignment.

Much of the code given in examples in this thesis could be run on almost any Lisp system; the parts that are not in the languages provided within Platypus are actually Common Lisp [Steele 84].

In our representation, node (expression, or statement) in the parse tree is identified by its first element, a leaf (symbol or name, rather than a further branching sub-tree) which we call the operator of that node. This is always the case, no matter how the construct appears in the textual form of the language. For example, the expression written in many languages as a + ( b / c ) is stored here in the form (+ a (/ b c))---its Lisp-like representation.

How Various Languages Fit This Model

Different languages map onto this common structure with varying degrees of ease: the model was designed for flexibility, but paradigms of computation vary widely, including pattern replacement languages such as SNOBOL and constraint languages, for example, along with the normal Turing Machines and algorithmic and functional languages.

Mapping Lisp onto our model of interpretation is trivial, since, as explained above, the model is so similar to Lisp.

The block-structured algorithmic languages also fit the model quite well, since their block structure is naturally easy to represent as a parse tree, and our model of interpretation has much in common with them. Those languages, such as Pascal and Algol, which are quite careful about type conversions and coercions fit in cleanly; C, with its freeer typing system, fits the control structure easily, but is not so comfortable on the tagged type system.

The non-block-structured languages such as FORTRAN, COBOL and BASIC can be fitted in, although slightly awkwardly. Their procedures must be written in terms of sequential execution operators which work their way through a series of statements (sub-trees) and which also provide facilities to switch (jump) to specified sub-expressions. (This switching may be done by a separate GOTO operator, or by the sequence operator directly.)

Stack Languages such as FORTH and PostScript fit in as block-structured algorithmic languages; their stack-based data storage is not a significant difference as far as we are concerned, although these languages are not usually regarded as being in the Algol group.

Logic Languages, such as Prolog [Clocksin And Mellish 81], are one of the worst matches to our model; their definitions must be procedurized (as explained in section 8.8) to produce something that we can store in terms of ors, ands and bindings. However, once procedurized, they fit our model of environments well, particularly in how they can then share bindings/instantiations with non logic-based languages, as explained in section 3.1.

One complication that occurs here is backtracking, which may be handled using continuation passing [Jackson]. In the committed-choice variety of logic languages, this problem is obviated by not providing backtracking.

A further problem in interfacing logic languages to other languages (a general problem, not unique to this system) is that logic languages may return a choice of results, rather than a single result. This is part of quite a general difference between families and languages.

Object-Oriented languages, which may be regarded as a variety of algorithmic language, can fit this model comfortably, using a closure to represent each object. The language and type-evaluators of the closure are then the method dispatch table for that object. A variety of object-oriented language that is clearly suited to constructing this way is the actor languages described in [Agha 86].

Reflection is commonly associated with object-oriented languages, perhaps largely because of the fame of the reflective object-oriented language SmallTalk80 [Goldberg And Robson 83]. In developing Platypus, I have been careful to avoid an object-based style, to show that reflection and object are entirely separate facilities in a language system.

One interpreter, many languages

This thesis is about a system in which languages are values that can be passed around---which inherently has the ability to be a mixed-language system. We have described in section 4.4 a system using one standard interpreter. How can we extend a single interpreter to handle a variety of languages? The ability to do this (and many other benefits) depends on a suitable abstraction for a language interpreter, and constructing that interpreter is a central part of this thesis.

An abstraction for programming language interpreters

Our abstraction for language interpreters is based around the parse tree abstraction for procedure representation. The language is arranged as a collection of named operators, where the names of the operators are those that appear in the nodes of the parse tree, and the definitions referred to by those names are the closures of the procedures used to implement each named language construct. Thus, a language---as we represent it---is a mapping from operator names to operator definitions. This mapping is done by binding operator names to operator implementations in an environment. We sometimes will refer to such environments as languages from here onwards, and any references to languages in programs are to this kind of value. In mixed-language interpretation, each part of the program must be interpreted in the appropriate language. We take the closure as a suitable unit for linguistic atomicity (if nothing else, the syntactic considerations would make a finer grain cumbersome!) and so we include in each closure the language of that closure, stored as an environment binding operator names to the corresponding definitions.

Such a use of environments other than the variable binding environment(s) assumes the provision by the substrate system of multiple environments [Padget And Ffitch] and environments as first-class values. The way we may acheive this is described in section 6.3.

As well as the language (environment of operators) an interpreter contains the evaluator, a procedure that glues the rest of the language implementation together. It is the evaluator that starts each step of program interpretation, by finding the operator name for the current node, looking it up in the language, and calling the result of that lookup, with the node as one of the arguments of the call. Operator definitions, in turn, use the evaluator to evaluate their sub-expressions as required.

Although unnatural for some languages (such as awk), this simple representation makes representation of many languages (perhaps most current languages) simple and concise, and I consider that it has proved its worth in practice. This is supported by the common use of Lisp as a basis for implementing other languages.

In the preceding s, we have used the term interpreters as a general term for what, from here on, we call evaluators, and what we had called the standard interpreter is now called the standard evaluator. The evaluator-and-language model is just one specific model for constructing an interpreter, and so interpreter is the more general term. We will still use it sometimes when referring to interpreters but not specifically to evaluators.

An evaluator is a closure called with two arguments: the evaluand that it is to process, and the level which provides the context (environment, language etc) for that evaluation. Since the closures in the argument level have closed over all the information needed to interpret the program it contains, no other information is needed by the evaluator. The program, arguments, environment, language, and even the evaluator itself are all included in the closure.

In section 7.1 we will see that this evaluation function is performed by one case of a more general level-based evaluator procedure. This is because the fundamental evaluator rôle is not the only part of a level's evaluator that must be thus changeable. The cleanest, most concise, implementation of a tower level evaluator turns out to be that in which each level has a general evaluator rather than an evaluator just for closures.

The interpretive closure

Reflective tower evaluation adds some new requirements to the conventional closure operation, since more information is now available in the current state of a program. To hold the extra information, we add some new components to our closures. The closures we use in this system contain all the usual parts of a closure:

and also two new parts:

The implementation of an operator is a procedure which interprets occurrences of that operator when applied to a level containing that operator as the operator of its continuation expression. The mechanism performing this application is explained in detail in standprocchap. The operator definition procedure is itself represented as a closure, and hence starts a new tower. Like an evaluator closure, an operator closure takes as its first argument the level containing the closure on which it is to operate, and

Independence and interdependence of closures

This organization of the interpreter into evaluator and language brings several benefits:

This leads to a very simple standard evaluator, with a clean structure to it, that is flexible for implementation of a variety of languages (as discussed in section 5.2), and that makes it easy to modify and extend languages through reflection.

It also means that the same evaluator, being a parameterized interpreter, may be used to interpret programs in a variety of languages by providing the appropriate operator definitions. Here, for example, are some possible combinations. Note that the language must match the program---that is, it must provide all the operators that the program uses---whilst either evaluator may used with either language and program.

Mixing Languages And Evaluators

Also, different evaluators may be used with the same language, calculating the same results in a different manner. For example, a level could be evaluated strictly or lazily, with or without tracing or single-step and so on. All this can be done without altering or needing to understand the operator definitions. This is possible because the interface between evaluators and languages and operators is well-defined and fixed.

Modifying several interpreter levels allows changes to be composed together. For example, Facilities such as unusual evaluation orders and traced evaluation may be combined by adding independently several special evaluators. For example, tracing of a lazily evaluated program may be done by adding a tracing evaluator next to the program, and a lazy-evaluation evaluator next to that. Were the two added evaluators to be the other way around, the effect would be to trace how the lazy-evaluation works; thus, combination of tower levels is non-commutative. Such a change in the processing of one level may affect all lower levels. For example, it is impossible for a level to do strict evaluation if a level anywhere above it interprets its subject lazily. This is an example of a property being propagated pervasively through the tower. Likewise, the results of adding a tracing level will be affected by the programs of all levels below it---this really means that the tracedness affects all the lower levels, although the visible effect will be only in the tracing output---the semantics of the traced levels should not be affected.

Combining Evaluator Effects

Furthermore, since each closure has its own evaluator and language, the properties can be changed per closure, so individual closures can be interpreted differently, allowing such things as tracing of specific procedures or operators.

Including the language in the closure also makes inter-language calling identical to intra-language calling. Inter-language procedure calls depend on having a common data representation between the languages. This is covered in typechap.

Writing interpreter components

Defining new operators is straightforward, because the implementation of an interpreter is divided into small parts (the evaluator and operators) with a simple, clearly-defined interface between them. This interface hides decisions about the implementations of other operators and the evaluator, while providing all the information that is needed to interact with them.

An operator definition, as bound to an operator name in a language, is a closure, called in the same way as an evaluator, that is, with the level it is to evaluate as its argument. Thus, both evaluators and operators are written as ordinary procedures, taking each one argument. The argument is the closure that is to be evaluated, and has all the information needed for the evaluation closed into it, stored in a standard form. Operator and evaluator closures have no other interface to the rest of the system.

Since it is a closure, each evaluator or operator contains the definition of the language in which it is written, and contains an evaluator to evaluate it, evaluators and operators can be written in any language available on the system. A base language, containing operators shadowed by the meta-evaluator (see section 4.4) is provided and is designed to be suitable for use in evaluator and operator definitions. When interpreted by the standard evaluator, procedures written in the base language are shadowed, and so run faster than any other part of the tower. The base language is described in baselanguage. The base language operators provide basic flow control and provide for locating parts of a closure such as the argument list of the procedure being interpreted, and provide reflective and other primitive features.

A closure is an interpreter sufficient for interpreting the level below it if it provides all the operators needed by the evaluator of that level. To maintain also the integrity of the tower for reification, it must include a full set of reflective operators. When these reflective operators are provided in each level, code reflected into a level can then reflect into the next level, allowing reflective procedures to capture and pass back reified data through any number of tower levels:

Passing Code Between Levels

Here, the actual action of reify has taken place through something running in the interpreter, but returning its result to the interpreted program.

baselanguage has more detail about requirements for languages used by evaluators.

This closure-based structure for calling parts of interpreters simplifies writing reflective interpreter components, because all the information needed is reachable through the level passed as the argument to that part of interpreter. Also, since each level is the base of a tower by virtue of having a pointer to its evaluator, the information in the level also includes all the levels above it.

We now give some example operator definitions. They are written as procedures each taking one argument, the level which they are to evaluate.

(defun if (level)
  (let ((expr (closure-continuation-expression
                 (level-continuation-closure level))))
    (if (eval (substitute-expression level (second expr)))
        (eval (substitute-expression level (third closure)))
      (eval (substitute-expression level (fourth closure))))))

(defun + (level)
  (reduce #'+
   (map 'list
    #'(lambda (x) (eval
                   (substitute-expression
                     (level-continuation-closure
                        level) x))))))

The overall structure of the tower

Although each individual level is simple, the overall structure of the system is complicated. Not only is each level the base of a tower which stretches through and beyond the evaluator, but it also has in the language an environment of closures, each of which also starts a tower.

Side Towers

In fact, the structure is more complex than this, as each level of each of those side towers will start a new side tower from each of its operator definition closures, and so will each of those in turn---so as well as having infinitely many levels, a tower built on this basis has a number of branches---or new towers---coming into existence at each level. As can be seen in the text and diagrams of section 4.5, and as shown again in section 10.1, all of these are connected with the meta-evaluator just as the main tower is (and all those which are ever used must be grounded---as the details, presented later, of the meta-evaluator will show, in practice they all have the same meta-evaluator).

It is through the grounding of all these side towers that the whole tower is evaluable, and so we can see that all of these towers must use the standard interpreter at some stage. Since the retreating shadow technique described earlier (see section 4.4) is used when needed, the towers do not need to rejoin into a single tower at the standard interpreter. Instead, as the standard interpreter is infinitely far away from each level, all the towers go off to the same infinity, in parallel lines.

Many Infinite Towers

The meta-evaluator arranges that these parallel lines do meet at infinity, or at least just past the horizon. This is a good way to think of the meta-evaluator. Although it makes the lines meet at infinity it also makes sure that that infinity is just a little further than the furthest away that we can see or touch without moving from our present position. Although the diagram here shows all these towers as being of the same length and form, their lengths cannot really be compared (all being infinite) and their forms may vary as long as they are all grounded.

Remember also that the meta-evaluator is alongside all these towers, rather than just meeting them at their infinitely far far ends. One might perhaps choose to regard the meta-evaluator as the paper on which the towers are drawn.

Meeting At Infinity

There is the multi-dimensional form of reflection, mentioned in section 4.5, in which a program can access its tower's meta-evaluator as the base of another tower, perpendicular to the first tower. This is useful for thinking about the implementation of the first tower, because it connects the tower to the tower's implementation in much the same way that tower reflection connects a closure to the implementation of its interpretation. Also, each of these grounded parallel towers described above meets its meta-evaluator (meta-tower) at all points along its length.

To include the meta-evaluator in the system, we must give up the first tower's pretence that there is no meta-evaluator, and provide a means for going from one tower to the next. This can be done in defining a type for towers, by making the type connect a tower with its meta-evaluator/orthogonal tower, and allowing any program to find the larger tower of which it is part, as described in section 4.5.

Links To The Meta-Evaluator

Since these links lead to the next meta-level, access to further dimensions of the spiral of towers can be made possible if that is provided in the type of data used to represent towers.

What can we do using this model?

This model for interpretation and interpreters brings in several new possibilities.

An unusual feature of this model of execution is the flexibility of its variable storage. The values list may be used as an open stack for stack languages, or used as though a framed stack for languages with stack frames. Using it for procedure arguments and results )as well as for the procedure's local workspace) is done in such a way that the arguments and results for a callee procedure in one language are handled correctly by the caller whatever the caller's language---even when the call goes between framed- and open-stack languages.

The environment variables are suitable for most procedural and functional languages, and are also usable by deductive languages such as Prolog to hold their bindings (instantiations) in. When a procedure in a deductive language calls one in a functional or procedural language, instantiations made by the former are visible as ordinary variable bindings to the latter. Likewise, a deductive procedure called from a non-deductive one will see as instantiations any non-local variable bindings that the latter (and its callers) may have made.


Summary of mixing languages

As well as being a reflective system, our system is a mixed-language one, making reified languages into part of the evaluation data that is available for manipulation by application programs running on the system.

To make the language a variable part of the context of a closure, we divide the interpreter into two parts, the evaluator, which is language-independent, and the language.

To do this, we need an abstraction for languages. The abstraction must be general enough to handle most languages reasonably well, and to handle all languages to some extent. Such an abstraction can be devised only in conjunction with an abstraction for the programs in the languages. For the programs, we choose to use parse trees, with each node being identified by its operator such as if or +, and for the languages, we use environments binding operator names to operator definitions.

This abstraction makes it easy to add new operators to a language, and also keeps separate the general evaluator, thus making it possible to redefine the evaluator independently from the language.

By making the language (the environment binding operator names to operators) of each tower level an explicit part of that level, we extend tower reflection from being a tool for reasoning about interpretation of programs to also being one for reasoning about languages and their interpretation.


``When I use a word,'' Humpty Dumpty said, in rather a scornful tone, ``it means just what I choose it to mean---neither more nor less.''

Alice Through the Looking Glass, Chapter 6



Submitted, Examined And Accepted: 1991
Contact me