The Symbol Table.
Before building the prototype for ColorWindow, the interpreter needs to type-check its source code. During this process, the symbols used in the denition of ColorWindoware resolved | their corresponding symbol-table entries are located. The user of the interpreter has indicated, by passing the pattern closure of the to-be-extended pattern, the lexical scope in which she/he wants this source code to be processed. The check must be performed as if the source code appeared in this lexical scope.In order to do this, the interpreter must have access to the symbol table of the program being extended. In order to get the eect of processing the extension in this scope, the
interpreter must be able to get access to all symbol-table entries visible in this scope.
Furthermore, it must be able to restrict the access, of the extension, to these and only these entries.
These requirements mean that the symbol table, generated when the original application was compiled, be available in some form. In addition, it should support the mapping from any scope to the set of symbols visible in that scope. Furthermore, if extensions are to be visible to future extensions, the table must be updatable with new entries.
In the Beta system, programs are stored as Abstract Syntax Trees (ASTs). Symbol-table information is stored as annotations to the nodes of these trees. So, the symbol table is available to the interpreter in the form of annotated ASTs of the original application.
Given this representation, it is possible to denote a scope by a node in this tree. Given a node in the tree, it is possible to determine the set of symbols visible from that node. It is worthwhile to note that although the entire source code of the original program is part of the tree and hence, is available to the interpreter, only the symbol-table information is actually used. One could imagine trimming these ASTs so that only symbol-table information remained. These trimmed trees would be adequate for installing extensions.
In fact, a prototype implementation of these trimmed trees is available. Thus, the original requirement that the source code of the application being extended need not be necessary in order to install extensions, has not been violated.
The extension must be processed in the same scope as that in which the to-be-extended pattern was processed. So, in order to nd the extension-processing scope, one must nd the to-be-extended pattern's scope. This can be found by examining its pattern closure.
This contains the prototype, which contains information identifying a le containing an AST, and a node within this AST. This node is the declaration of the to-be-extended pattern. Its enclosing block is the desired extension-processing scope.
The interpreterloads this AST, locates the node corresponding to the extension-processing scope, parses the extension source into an AST, attaches the extension AST at this node, and then type-checks the extension AST, annotating it with symbol-table information.
Attaching the extension AST has the eect of installing the new extension into the symbol table.
In the example, the pattern closure forWindowis passed as an input argument. It is used to locate the node forDisplayin the AST of the original program. The AST forColorWindow
is then attached to the original program's AST as if it appeared within Display.
Type Checking.
Once the extension has been setup in the correct scope, the type checking process performs some standard type-consistency checks. The details of thesechecks are beyond the scope of this paper; see [MMMP90] for details. Only some of the results of this process are summarized here:
1. The reference to Window as the super pattern of ColorWindow gets resolved to the
Windowdened within Display.
2. Within the denition of ColorWindow, there is a further-binding of refresh. This gets resolved to the virtual pattern refresh declared within Window.
3. Within the further binding of refresh, there is a reference to the variablecontents. This gets resolved to the contents variable declared within Window. It is also recorded that in order to resolve this reference at runtime, one must follow one envi-ronment link to go from therefreshinstance to theColorWindowinstance (contents is inherited byColorWindowand hence is part of aColorWindowinstance), and access the eld at X bytes oset. Here, X is determined from the symbol-table entry for
contents.
This shows how accesses from an interpreted extension to the state dened by its super pattern are handled.
4. The reference to screen, also appearing within the refresh further binding, gets resolved to the screen declared within Display. Its runtime resolution involves following two environment links (from arefreshinstance to aColorWindowinstance to a Display instance), and then accessing the eld at X bytes oset. Here X is obtained from the symbol-table entry for screen.
This shows how accesses from an interpreted extension to the state dened by its enclosing patterns are handled.
Building the prototype for
ColorWindow.
As ColorWindow is a specialization ofWindow, its prototype is built using Window's prototype as a starting point. The pro-totype for Window is located by getting its memory address from the symbol-table entry for Window. In Beta, this is actually a two-step process: (1) from the symbol-table entry for Window, obtain an assembly-level symbol name which identies the prototype in the executable, (2) using the linker-generated symbol table, which is in the executable, map this name into an address.
At this point, before proceeding with the construction of a prototype forColorWindow, it is possible to complete the type checking of the call to the interpreter (rst referred to in the beginning of this section). It remains to be ensured that the extension pattern is indeed a sub-pattern of the to-be-extended pattern. The prototype of the super-pattern of
the extension pattern has been obtained from the symbol table. The prototype of the to-be-extended pattern can be obtained from its pattern closure. Using these prototypes, it is possible to check if the extension's super-pattern is a sub-pattern of the to-be-extended pattern. This implies that the extension pattern is a sub-pattern of the to-be-extended pattern.
The prototype for ColorWindow is built incrementally by taking a copy of Window's pro-totype and extending it. It is not the purpose of this paper to document propro-totypes;
see [Mad93] for that. Only the interesting aspects of the prototype, especially those that dier betweenWindow and ColorWindow, are elaborated.
Window has a do-part and a virtual declaration. Hence, its prototype will have an Inner Dispatch Table (IDT) and a Virtual Dispatch Table (VDT). This discussion will focus on these tables.
The IDT.
This is the basis for the implementation of Beta's INNER imperative.For a pattern P with do-parts, the number of entries in its IDT is one greater than the number of patterns in its super-pattern chain. In general, it has the following structure:
RETURN P do-part
immediate-super-pattern do-part ...
base-pattern do-part
Here, base-pattern do-part is the do-part of the root pattern of P's super-pattern hi-erarchy chain, immediate-super-pattern do-part is the do-part of P's immediate super pattern, and P do-part isP's own do-part. RETURN results in a return from subroutine.
In the case of Window, there is no super-pattern; hence only one do-part, and an IDT with two entries. In the case of ColorWindow, Window is a super-pattern; hence it has an IDT with three entries. Figure 4.2 shows the IDTs for both patterns. Observe how
ColorWindow's IDT is constructed out of parts of Window's IDT.Window's do-part is com-piled into code and Entry 1 of both IDTs point to the entry-point for this object-code. Entry 2 of Window, and Entry 3 of ColorWindow point to code that executes a return-from-subroutine instruction. Entry 2 of ColorWindow points to \object-code" for the do-part of ColorWindow.
The object-code for the do-part of ColorWindowis interesting in that it is an interpreter-generated stub which serves the purpose of disguising interpreted code as compiled code.
It is structured as follows:
access 1
2
1 2 3
IDT IDT
Window Prototype ColorWindow Prototype
Return
Window do part
ColorWindow do part
Interpreter
ColorWindow AST invoke
Figure 4.2: The Inner Dispatch Tables 1. Save registers
2. Get address of current object from a machine register 3. Locate AST for ColorWindow
4. Invoke interpreter with the current object and a reference to the AST 5. Restore registers
6. Return from subroutine
Notice that it has encoded within it a reference to the AST ofColorWindow.
When an instance of Window is executed, control will ow into Entry 1 of Window's IDT.
When the INNER imperative is encountered, the next entry (Entry 2) in the table will be invoked as a subroutine. As this is a return-from-subroutine instruction, the INNER will have the eect of a no-operation.
When an instance of ColorWindow is executed, control will ow into Entry 1 of
ColorWindow's IDT, which is object-code shared with Window's IDT. At the INNER it will ow into Entry 2. This is the interpreter-generated stub; it will invoke the interpreter with the current object and the ColorWindow-AST as arguments. When during interpretation, the INNER imperative is encountered, the interpreter will treat it like a no-operation as there are no further specializations to branch to. When the interpreter nishes with the do-part of ColorWindow, it will return to the stub. Here the registers will be restored and execution will continue where it left o in Entry 1.
The VDT.
A pattern, with one or more virtual patterns declared within it, will have a VDT. The VDT is the basis for the implementation of virtual patterns in Beta. The size of the VDT will be equal to the number of virtual patterns. The purpose of the VDT is to allow dynamic binding of virtual patterns | for a virtual pattern, the corresponding VDT entry will contain the current binding. A VDT entry is essentially a reference to the prototype of the pattern which is the current binding.For example, the Window prototype will have a VDT with one entry, i.e. for the refresh virtual. This will contain a reference to the prototype for the refresh pattern declared within Window. All clients of refresh will be dispatched through its VDT-entry in order to get its current binding in the form of a prototype. This prototype will then be used to execute or instantiate an instance of refresh. If refreshis invoked on a Windowinstance, its current binding will be therefresh pattern declared withinWindow.
ColorWindowintroduces a further binding of refresh i.e. it specializes refresh by dening a sub-pattern of it. In the prototype forColorWindow, the VDT-entry forrefreshis updated by the interpreter to refer to the prototype for the further binding of refresh. This prototype is also built by the interpreter in the same way as the prototype forColorWindow
is built. Invoking refresh on a ColorWindow instance will result in the execution of the further binding.
Other prototype parts.
Other parts of Window's prototype that get copied intoColorWindow's prototype, possibly with modication, are the Static Objects Table, the Dynamic Reference Table, and some other information describing the size of the object etc. In this manner a prototype for ColorWindowis built from the prototype for Window.