<<>> <> <> <> Introduction We posed ourselves the problem of translating a fairly large piece of Cedar code (the Imager) into Lisp. It quickly became clear that doing this entirely by hand would be a formidable, error-prone job, and not a whole lot of fun. So we set out to build some translation aids to do a significant part of this work for us. The form that the translator took is rather unusual in that the first half is done in the Cedar environment, and the second half is done in the Lisp environment. The first (Cedar) half is called the "Crank" (since the phrase "turning the crank" kept coming up), and the second (Lisp) half is called the "Grinder" (since initially we expected it to produce hamburger). These notes are concerned mostly with the Crank, but we may also have something to say about the whole translation process. Overview of the Crank The Crank's job is to take a correct Cedar program, construct an abstract syntax tree for it, perform enough type analysis on it for the Grinder to make reasonable sense of it, and write it out in a textual representation of a Lisp structure. Note that it does not promise to catch all type errors; it is assumed that the source code has successfully compiled. The first phase, constructing an abstract syntax tree, required almost no new code, since the Cedar Interpreter already provides this functionality. The Crank merely calls the appropriate parse routine to build the abstract syntax trees from the source code, and alters it to provide places to hang attributes on the nodes. Note I said source code; in fact, the Crank does not rely on .bcd files for its input. We considered the possibility of using the Cedar Abstract Machine to get the type information from interfaces, but since the Crank is already doing the required type analysis, it is quite straightforward to have it call itself recursively to analyze an interface from the source code when required (and cache the result). The type analysis is the largest and most interesting part of the Crank. To give an example of the kind of things the type information is required for, consider the expression m.first This notation could stand for any of these: m is a record: m.first selects the appropriate field. m is a REF or POINTER to a record: m.first means m^.first m is a LIST: m.first means the first element of m the type of m is defined in an interface that has a procedure named "first": m.first means Interface.first[m]; m is a variant record type, one of whose variants has a tag of "first"; m.first means the same as the obsolete notations "first m" and "m[first]" The context may be {OPEN m: P[]; ... }, where P is of type PROC RETURNS [n: INT, first: REAL] : m.first means call P and select the appropriate return value. When you consider that the abstract syntax tree is the same no matter which of these interpretations are appropriate, it becomes clear that some kind of type analysis is required to do a meaningful translation. The final phase of the Crank is to write the (decorated) syntax tree as a textual representation of a Lisp structure. This is comparitively straightforward; the only tricky part is passing on enough of the information from the type analysis, without making the intermediate files too large to be manageable. The approach is to provide only that information from the type analysis which is needed to make a reasonable translation. This was done was largely by waiting until we discovered the Grinder needed some piece of information before changing the Crank to provide it. One useful way of providing such information is by changing the name of the locally ambiguous syntax nodes, i.e., RECORDFIELDSELECT instead of DOT. The other way is via attributes, encoded as a property-list on each node of the syntax tree.
head
body