pymdl

The MDL Programming Environment

Chapter 5. The Compiler

The purpose of the MDL compiler is to transform interpreted MDL code into assembly language. The compiler comes in several incarnations for various purposes. PCOMP is a program which runs the 'installed' compiler -- that is, the one which is most debugged, supported, and otherwise official. The "P" stands for 'purified,' incidentally. NPCOMP is a program which runs a newer, less well-debugged compiler, if there is one. NPCOMP is often where development work of one sort or another is being debugged. The 'Batch Compiler', often called COMBAT, though strictly speaking the name refers to a different program (see section 5.2) is a program that compiles, at night, those compilations that have been queued for it. The remainder of this chapter describes the specifics of interaction with the compiler, including a section on its internals.

5.1. Interfacing to the Compiler

The operation of the MDL compiler is controlled by a few very high-level functions and a sometimes bewildering array of ATOMs whose values are switches and data. This section will describe each such ATOM and its use. The reader should bear in mind that in the normal case he will be using COMBAT to set up his compilations and thus will not have to deal directly with these ATOMs and calls.

5.1.1. Compiler Functions

<COMPILE source:function-or-list output:channel>

is the lowest level call to the compiler. It compiles exactly one FUNCTION (or a LIST of them) and prints the generated code on the CHANNEL given as the second argument. COMPILE is used primarily for compiler debugging.

<FILE-COMPILE input:string output:string>

FILE-COMPILE attempts to provide a convenient interface between the user and the compiler. The user simply gives FILE-COMPILE the name of an input file, and it can do all the rest. The user may specify other information about output files, compiler modes, etc., but if he doesn't, reasonable assumptions are made. FILE-COMPILE works in the following way. First it reads in the input file and collects into a LIST the names of all of the defined FUNCTIONs that it finds. It sorts this LIST based on which FUNCTIONs call which other FUNCTIONs. The FUNCTIONs which call no other FUNCTIONs are at the beginning of the LIST, followed by those that only call FUNCTIONs that call no other FUNCTIONs, and so on. Groups of FUNCTIONs that are mutually recursive are collected in LISTs subordinate to the main LIST.

Each FUNCTION will produce a separate RSUBR. COMPILE is called successively on each member of the LIST of FUNCTIONs. LISTs of mutually recursive FUNCTIONs are also passed to COMPILE.

After each FUNCTION or LIST of FUNCTIONs is compiled, the resulting RSUBR is written into a temporary file to enable more convenient crash recovery. This file is written in such a way that, no matter when the system crashes, the contents of the temporary file are guaranteed to be in a consistent state.

When all is compiled, FILE-COMPILE writes out an output file which is identical to the input file except that all FUNCTIONs have been replaced with their compiled counterparts. If any of the FUNCTIONs did not compile due to programmer errors or compiler bugs, those FUNCTIONs are left unchanged in the output file.

During its operation, FILE-COMPILE maintains a "RECORD" file which contains all of the messages, warnings and error messages produced by the compiler. It may optionally produce a listing of the object code produced, in MDL assembler format. This is primarily useful for compiler debugging. (Note that a somewhat less complete listing may be made at a later time. See section 7.3.)

On ITS, FILE-COMPILE usually runs as a demon called COMBAT ZONE. In this case another interface called FCOMP resides above FILE-COMPILE. This interface reads files that are compilation specifications and passes them to FILE-COMPILE.

<FCOMP %.INCHAN input-file output-file>

As most compiler usage is based on COMBAT plan files, FCOMP is the most-seen driver of the compiler. (Note that the % in front of .INCHAN causes the CHANNEL the PLAN file is being read from to be passed as one argument to FCOMP.)

<STATUS>

is an informational function; it tells how far the compilation of a given group has progressed, which FUNCTION is being worked on, and how many FUNCTIONs remain to be compiled. It also prints the accumulated real time and cpu time since the beginning of the compilation. Obviously, you must ^G the compilation to use it, but see section 8.3.

5.1.2. Compiler Switches

The calls to the various compiler drivers are rather short, for the simple reason that the controlling information is passed to the compiler as the LVALs of a set of ATOMs.

<SET DEBUG-COMPILE!- boolean>

(by default FALSE) causes the compiler to generate extra information about what it's doing. This information is in the form of 'warnings' produced when the compiler was forced to generate less than optimal code. For example, invocations of the arithmetic SUBRs can be open-compiled if the variables used can be determined to be exclusively FIXes. The debugging compiler will warn you if it is forced to resort to less efficient arithmetic calls.

<SET PRECOMPILED!- file:string>

Often, a file of FUNCTIONs has been compiled before, and now only a few FUNCTIONs have been updated and need to be compiled again. Most of the file is already correctly compiled: it is quite wasteful to recompile the entire thing. If a PRECOMPILED is given, the file is loaded before compilation: any functions which have corresponding RSUBRs in the precompilation, and which are not on the REDO list, are not recompiled. It is appropriate to specify the temporary file as a precompilation if your previous compilation was interrupted by a system crash.

<SET REDO!- list-of-atoms>

REDO is a LIST of FUNCTION names to be recompiled, regardless of whether or not they are compiled in the precompilation. In conjunction with PRECOMPILED and PACKAGE-MODE, REDO allows compilation of precisely those FUNCTIONs which have been changed since the last compilation. Note that COMBAT will set up these values more-or-less automatically in most situations.

<SET PACKAGE-MODE!- string>

This should be the name of a PACKAGE, which is assumed to be the PACKAGE being compiled. FUNCTION names in the REDO LIST will be looked up in the appropriate PACKAGE OBLISTs if this flag is set, thereby saving some typing of trailers.

<SET TEMPNAME!- file:string>

The compiler writes intermediate results to the temporary file, which is normally the file "sname;fnm >" on ITS, where fnm is the first name of the input file. It is rarely (if ever) necessary to change that default.

<SET SOURCE!- file:string>

Setting this switch causes the compiler to write out the assembler input it generates. This is sometimes useful for compiler debugging. On ITS, such output normally goes to "sname;fnm SOURCE", where fnm is the first name of the input file.

<SET SPECIAL!- boolean>

The compiler normally assumes that variables which aren't declared SPECIAL aren't SPECIAL. This means that they will be available only to the RSUBR in which they are declared: SPECIAL variables are bound on the control stack, just as all variables are in interpreted code. If this flag is T (by default FALSE), all variables will be assumed to be SPECIAL unless declared otherwise. This is analogous to SPECIAL-MODE being SPECIAL, and it is not recommended that any code be written using this convention.

<SET EXPFLOAD!- boolean>

If true, FLOADs in the file being compiled will be expanded at load time: what was FLOADed before will be treated as part of the file. EXPFLOAD is examined by GROUP-LOAD, and not the compiler itself. The default is FALSE.

<SET EXPSPLICE!- boolean>

If true, objects of type SPLICE (PRIMTYPE LIST) which are encountered in the course of EVALing the forms processed by GROUP-LOAD will be spliced directly into the group; it is therefore a lot like EXPFLOAD. EXPSPLICE is examined by GROUP-LOAD, and not the compiler itself. The default is therefore FALSE. Its only known use has been to make functions at load time and have them compiled.

<SET CAREFUL!- boolean>

Defaults to T. If FALSE, the compiler will omit most of the bounds-checking code it normally generates for NTHs, PUTs, and so on. This obviously will make the compiled code run faster, but also makes debugging the compiled code nearly impossible.

<SET REASONABLE!- boolean>

Defaults to T. If FALSE, the compiler will generate reasonable code only if everything ever called from the functions being compiled is loaded into the compiler. A call to a function not loaded produces an EVAL of a FORM, thereby ensuring that such constructs as "CALL" in the called function will work correctly. This is admittedly pretty unreasonable (if not paranoid), whence the name of the switch.

<SET GLUE!- boolean>

Defaults to T. If FALSE, the compiler will not generate GLUE bits. As you always want GLUE bits, there is no reason to ever change this.

<SET MACRO-COMPILE!- boolean>

Defaults to FALSE. If non-FALSE, the compiler will compile MACROs into RSUBRs. This doesn't change anything produced by macro expansions, but does cause the expansion to speed up. Since the compiler expands the macro and then compiles the expansion, this is rarely useful.

<SET MACRO-FLUSH!- boolean>

Defaults to FALSE. If non-FALSE, MACROs which appear in the file being compiled will not appear in the resulting NBIN. This saves space, at the expense of making debugging harder.

<SET MAX-SPACE!- boolean>

Defaults to FALSE. If non-FALSE, the compiler flushes from core most of each RSUBR once it has been compiled; only the DECL is needed to help compile other functions. Since the entire RSUBR is written out in the temporary file, no information is lost. This can, for compilations which are too large, result in considerable improvements in speed, primarily because more space is available in the MDL and less time is spent in the garbage collector.

<SET HAIRY-ANALYSIS!- boolean>

Defaults to T. If this is not set, the compiler will not perform the complex type checking it usually does. If HAIRY-ANALYSIS is FALSE, the code will be generated faster, as type-analysis is expensive, but will not execute as fast.

5.2. COMBAT

The usual method of dealing with the compiler is through the program COMBAT, whose specialty is the preparation of 'plan files' to be loaded by the compiler. COMBAT is a program which knows about each of the previously described compiler switches and the interactions among them. It has an easy-to-use interface, an ability to store commonly used 'plan files' as compilation types, and in general is designed to make using the MDL compiler a less-cumbersome task.

5.2.1. User Interface

COMBAT's user interface is patterned after, though not identical to, a CALICO interface [1]. In particular, it expects in response to any given prompt a particular type of input from the user, which may be a file name, a 'symbol', or text. Ordinarily, the type of input expected is indicated by the 'syntactic prompt' which follows the normal prompt; this is one of '(FILESPEC)', '(SYM)', and '(TEXT)'. The 'Toggle verbosity' compilation type turns the printing of the syntactic prompt on and off, and causes a tailor file to be written out when used. A number of special characters are defined for any of these types of input:

  • ^@: Clears the input buffer, as in MDL.
  • ^D: Redisplays the input buffer, as in MDL.
  • ^L: Clears the screen and redisplays the input buffer, as in MDL.
  • ^G: When given as the first character of an answer, allows one to get the answer from a user-defined type. See the section on tailoring.
  • ^Q: Has special effects when a compilation plan is being made (see below). See also the section on file name input.
  • ^R: Causes COMBAT to 'back up'. Typically this means go to the previous question asked, but in certain modes it may have a slightly different effect. When a MUDCOM is running, this kills it and backs up to the last question asked.
  • ^S: Abnormally ends whatever is being done, and returns to the 'Type of compilation' question. If a MUDCOM is running, it will be killed. When a long compilation plan ('How to run' is 'Many') is being made, the portions already made will be saved. See the 'Flush many' compilation type.
  • ?: When given as the first character of an answer, this causes a more detailed description of what is expected to be printed, along with the current default and how to obtain it.
  • \: This quotes whatever character follows it, including DEL, ESC, etc. It does not have the effect of quoting strange characters in file names: see the section on file name input. \, used as a quote character, never echoes, and cannot be rubbed out.

In addition, when the syntactic prompt is (SYM), ^F is useful (see below).

5.2.1.1. Symbolic Input

If you are familiar with CALICO, this section can probably be skipped. When entering symbolic input, one need only type the characters required to uniquely specify the desired choice: the interface will complete the response, and in addition can display the available choices at any point.

SPACE completes the response as far as it can. If the response is uniquely specified, it will be displayed in its entirety, followed by '!'; if more than one choice is still possible, then the portion of those choices which is unambiguously specified will be displayed, followed by '?'. For instance, if 'Expand floads' and 'Expand splices' are among the choices, and "Ex SPACE" has been typed, 'Expand ?' will be displayed if the "Ex" reduces the choices to those two.

In some cases, if SPACE is the first character typed, it will select the default (first) choice and terminate.

When ^F is typed, all remaining choices will be displayed.

To terminate responses in this mode, either ESC or CRLF may be used. In either case, the current response is completed as far as it can be. If only one choice then remains, the answer is terminated and the single choice will be used. If more than one choice is possible, it is just as if SPACE had been typed.

Typing ESC or CRLF before any other characters have been entered causes the default answer to be used.

5.2.1.2. Filenames

File names are expected in the standard dev:sname;fname1 fname2 format on ITS; on Tenex/TOPS-20, standard file name recognition is used. Typically, typing simply ESC or CRLF answers 'no' to the question, while SPACE ESC says 'use the default'. In certain special cases ('Input file' and 'Output file'), when some answer to the question is imperative, the default will be used in either case. File names should not be surrounded by quotes in this mode; they are not MDL STRINGs!

It is rather painful to get funny characters (such as SPACE) into file names. When the file-name parser sees ^Q, it uses the following character in the name being generated regardless. Unfortunately, the ^Q must be quoted to get it past the reader, since it has special effects in the normal case. Thus, the file name given to MDL as "AA; FOO>" has to be typed to COMBAT as AA: ^Q FOO>.

5.2.1.3. Text

Text is just that: relatively arbitrary characters, terminated by ESC. Since CRLF is allowed in text, it does not terminate input. Text type input is used in a number of cases where it isn't quite appropriate, such as the 'Redo list' and 'Package mode' questions. If it is known that the expected response is a LIST of STRING, as in those cases, the appropriate brackets or quotes should never be typed.

5.2.2. Combat Questions

This section discusses the questions that can be asked of the user during the preparation of a COMBAT plan file, which is FLOADed by the COMBAT demon or by PCOMP to effect a compilation. The perceptive reader will notice a strong resemblance to section 5.1.2, in which the switches relevant to the compiler are listed. Questions asked by the pre-existing compilation types ('Verbose' and 'Short') are so indicated. All questions are available in user-defined compilation types (see section 5.2.5).

'Sname': sets the default directory for questions that want a file name as an answer; also causes the FORM <SNAME sname>, where sname is the answer given, to be included in the plan. This sets the default directory for files referenced by the compiler; it also causes the temporary file (see below) to go to the sname directory.

'Use new compiler?' (Verbose and Short): specifies whether the 'new' compiler or the 'old' compiler should be used. Often, when there is only one compiler, this question will not be asked. If answered affirmatively, it causes the FORM <OR <GASSIGNED? EXPERIMENTAL!-> <NEWCOMP!->> to be included in the plan. This FORM will load a new compiler on top of the old if necessary.

'Debugging compiler?' (Verbose): causes DEBUG-COMPILE!- to be set to T, which causes the new compiler to generate extra information about what it's doing. This currently is asked only if the new-compiler question is answered affirmatively.

'Input from' (Verbose and Short): the file to be compiled. This appears in two places in the plan: as <SETG COMBAT!- input-file> and in the call to FCOMP described below.

'Output to' (Verbose): the file name to be used for the NBIN. The default is the input file name, with NBIN as the second file name instead of whatever it was for the input. This completes the call to FCOMP that ends every plan:

<FCOMP %.INCHAN input-file output-file>

This call is what actually invokes the compiler.

'Precompilation from' (Verbose): specifies a file containing a previously compiled version of the input file. Any FUNCTIONs which have corresponding RSUBRs in the precompilation, and which are not on the 'Redo' list, are not recompiled. It is appropriate to specify the temporary file as a precompilation if your previous compilation was interrupted by a system crash. Sets PRECOMPILED!-.

'Compare with' (Verbose): This question is asked only if a precompilation file is specified. If answered affirmatively (user types either SPACE ESC or a file name) MUDCOM (see section 8.1) will be run with jcl of the input file name, and the file name provided here (the default is as for precompilation), plus some extra stuff specified below. If 'FOO NBIN' is given here, then MUDCOM will look for the newest revision of FOO which was created before the NBIN. MUDCOM determines which FUNCTIONs in the file have changed and therefore need to be recompiled. It also determines whether the file is a PACKAGE, and answers the 'Package mode' question appropriately. It is therefore not usually necessary for the user to answer the 'Redo' and 'Package mode' questions directly.

'Check macros?' (Verbose): asked only if 'Compare with' is answered affirmatively. This adds '/M' to the jcl passed to MUDCOM, which causes it to check for MACROs and MANIFESTs which have changed: if a FUNCTION uses a MACRO or MANIFEST which has changed, the FUNCTION will be listed as changed. MUDCOM does not normally check for this.

'Extra JCL' (Verbose): asked only if 'Compare with' is answered affirmatively. Whatever is supplied here will be passed to MUDCOM as jcl, before the files to compare. This can be used to load macro files: see section 8.1.

'Redo' (Verbose): asked only if a precompilation file was given. Takes a bunch of FUNCTION names, which will be recompiled. Note that the names supplied here will be appended to the list returned by MUDCOM, if any, and that duplications in the list are ignored. Sets REDO!-.

'Package mode' (Verbose): asked if a precompilation file was given and MUDCOM was not run (MUDCOM will set this if run). This should be the name of a PACKAGE, which is assumed to be the PACKAGE being compiled. FUNCTION names in the 'Redo' list will be looked up in the appropriate PACKAGE OBLISTs if this flag is set, thereby saving some typing of trailers. Sets PACKAGE-MODE!-.

'Temporary file to': The compiler writes intermediate results to the temporary file, which is normally

"sname;fname1 >"        (on ITS)
"<sname>fname.TEMP"     (on Tenex/TOPS-20)

You may change that by answering this question; there is rarely a good reason to do so. Sets TEMPNAME!-.

'Source file to': The compiler can be caused to write out the assembler input it generates by answering this question. Assembler output normally goes to

"sname;fname SOURCE"     (on ITS)
"<sname>fname.SOURCE"    (on Tenex/TOPS-20)

which is the default for this question; another name may be provided if desired. Sets SOURCE!-.

'Special?': The compiler normally assumes that variables which aren't DECLed SPECIAL aren't SPECIAL. If this flag is T (defaults to FALSE), all variables will be assumed to be SPECIAL unless declared otherwise. Sets SPECIAL!-.

'Expand floads?' (Verbose): If true, FLOADs in the file being compiled will be expanded at load time. Sets EXPFLOAD!-.

'Expand splices': If true, objects of type SPLICE (PRIMTYPE LIST) will be expanded and inserted into the group. Sets EXPSPLICE!-.

'Careful?' (Verbose): By default T, but if FALSE, the compiler will omit most of the bounds-checking code it normally generates for NTHs, PUTs, and so on. This obviously will make the compiled code run faster; it also makes debugging the compiled code nearly impossible. Sets CAREFUL!-.

'Reasonable': By default T, but if FALSE, the compiler will generate reasonable code only if everything you call from the functions being compiled is loaded into the compiler. Sets REASONABLE!-.

'Glue?': By default T, but if FALSE, the compiler will not generate GLUE bits. There is no good reason to ever answer this. Sets GLUE!-.

'Macro compile': By default FALSE, but if true, the compiler will compile MACROs. Sets MACRO-COMPILE!-.

'Macro flush': By default FALSE, but if true, MACROs which appear in the file being compiled will not appear in the NBIN. Sets MACRO-FLUSH!-.

'Max space?': By default FALSE, but if true, the compiler flushes from core most of each RSUBR once it has been compiled; only the DECL is needed to help compile other functions. This can, for compilations which are very large, result in considerable improvements in speed. Sets MAX-SPACE!-.

'First things to do', 'Things to do' (Verbose), and 'Last things to do': It frequently is necessary to perform some actions before a compilation can be run: definitions files must be loaded, special environment setup might have to be performed, and so on. All three of these questions are designed to allow that: whatever you supply is put out after everything else in the plan but before the call to FCOMP. There are three questions, instead of one, to allow some things to be specified in a tailored compilation type, while others are provided at compile time, or possibly from another tailored type. The three questions do not depend on each other, they are asked in the order given here, and the answers appear in the plan in the same order.

5.2.3. Requesting Compilations

The first question asked by COMBAT is 'Type of compilation'. In addition to a number of special possibilities described later, there are two answers to this question (in addition to any provided by the user through the tailoring facility) which request pre-defined tailored compilation types. These are 'Verbose' and 'Short'. 'Verbose' causes all the normal questions to be asked: 'New compiler?', 'Input file', 'Precompilation', switches, 'Things to do', and so on. 'Short', on the other hand, defaults the answers to all questions except 'New compiler', 'Input file', and 'How to run'. When requesting a compilation, one may type ^Q at any time. This has the same immediate effect as an ESC, but in addition causes all questions between the one just answered and the 'Things to do' question to be defaulted. This is particularly useful in the 'Verbose' sequence of questions. If 'Many' was given as 'How to run' for a previous compilation request, and the resulting plan has not yet been written out, subsequent plans will be appended to it. Using 'Many' will sometimes effect a major savings of time if several compilations wish to perform the same environmental setup; if they USE many of the same PACKAGEs, for example. When using 'Many' in combination with predefined compilation types, it is useful to remember that whatever is specified under 'Things to do' may end up being performed for each plan. You might modify your compilation types to reflect this, or alternatively, edit the plan file produced by COMBAT to remove redundant operations.

The only way to get rid of the 'Many' plan is to answer 'Many flush' to the 'Type' question. Typing ^S or answering 'Abort' to the 'How to run' question will abort the current portion of the 'Many' compilation, but not the whole thing. If 'Many' was mistakenly given as 'How to run', and you don't wish to destroy the plan you have already generated, it is possible to (in essence) go back to the 'How to run' question by answering 'Many print' for the compilation type. In this case, you are not back in the plan-making loop; ^R acts just like ^S. ^R, here, backs up to the last question asked. There are two qualifications. First, if ^Q has been typed, then it backs up to the last question that would have been asked if ^Q had not been typed. Second, the four questions 'Precompilation', 'Compare', 'Redo', and 'Package mode' are treated as a group: if the 'Package mode' question has not yet been answered, it is possible to back up normally; but once that question has been answered, backing up to it will go to the first member of the group, 'Precompilation'. ^G allows one to obtain the answer to the current question from any user-defined compilation type. It requests a type name, and uses the answer or default supplied therein, printing the information so obtained. The ^G must be typed as the first character of the answer for this to occur. This allows one to use parts of a defined type without either using the type itself or altering it for the occasion. For 'Text' type input (such as 'Things to do'), the string is placed in the input buffer but not completed, so it may be edited before an ESC is typed. See also the 'Xerox type' command. Note that there is a distinction made between 'Compare' and 'Redo': the former causes a MUDCOM to be run, and the latter asks for the names of FUNCTIONs to be recompiled. It is possible to do both, in which case the two groups of FUNCTIONs are appended to form the 'Redo' list for the compilation. Note also that if a MUDCOM has been run, the 'Package mode' question will not be asked, since the answer is supplied by the MUDCOM. Either ^R or ^S may be used to kill a running MUDCOM. One of the responses to the 'How to run' question is 'Abort', which returns directly to the 'Type of compilation' question without writing out a plan, starting up a PCOMP, or anything else. Its effect is exactly that of a ^S. In particular, if you are making a long plan, only the portion just completed, not the entire compilation, will be aborted. It is also possible at the 'How to run' question to supply an answer to any of the compilation questions (Input file, etc.). The 'Question' response asks for the name of a question, then asks that question. Any number of questions can be asked in this manner, one at a time. This is particularly useful for filling in the blanks left by a 'Short' type compilation, or by user-defined compilation types. When a compilation request has been finished, COMBAT normally loops back to the 'Type of compilation' question, but changes the default from 'Verbose' to 'None' (meaning 'Quit'), unless another compilation may reasonably be expected. Thus, one may leave by typing a single ESC. It is possible to modify COMBAT's behavior such that it either kills itself after finishing the compilation plan, or loops back with 'Verbose' as the default for the 'Type of compilation' question. COMBAT first decides whether a long compilation plan is being made; if so, the default remains 'Verbose'. If not, it then examines the current compilation type: if 'Another compilation?' has been set to 'Yes', the question will be asked with default 'Verbose'; if it has been set to 'No', COMBAT will kill itself; if to 'Ask', further consideration is required. If the user is in 'Multiple' mode (the 'Multiple' compilation type), the type of compilation will be asked with the 'Verbose' default. Otherwise, COMBAT examines the state of two tailorable switches, set by the 'Another compilation?' compilation type. If 'Another compilation?' has been set to 'No', COMBAT will die; if to 'Yes', the type question will be asked with default 'Verbose'; if to 'Ask', the type question will be asked with default 'None'. Normally this is 'Ask'.

Note that 'Another compilation?' is like 'Toggle verbosity' in that it will have no effect unless user-defined compilation types exist.

5.2.4. 'How to Run' Options

There are four options available when answering the 'How to Run' question which determine where your plan file will be written and when the compilation it specifies will be run.

'Pcomp' places the plan file on the directory, and names it "". Additionally, COMBAT will start a PCOMP (or NPCOMP, as appropriate) process if it is exited after writing the <PCOMP file. 'Pcomp' is the standard method for running a compilation in one's own process.

'COMBAT' writes the plan file to "COMBAT;PLAN>". The COMBAT demon successively compiles all such plans at night, informing the persons who submitted them of the result.

'Waste' is like 'COMBAT', except that the plan is written to "COMBAT;WASTE>". The 'waste' queue is only run after midnight, which is usually sufficient for those who are doing 'overnight' compilations. 'Waste' is the answer used by default for 'How to Run'.

'File' places the plan file on the directory, and names it "". This means that it will not be run until you explicitly load it into a compiler process.

5.2.5. User Tailoring

It is often the case that a particular file is compiled quite often, or that some sequence of actions must be performed as the 'Things to do' before many compilations. COMBAT allows the user to define his own 'Compilation types', each of which specifies exactly those questions which should be asked and the answers for those which should not. For example, one could have a type named 'Esign', which says that the input file is always "SEND;ESIGN>" and in addition provides for the FLOADing of two files in 'Things to do'.

Further, since most questions are defaulted, one might choose to answer only those questions which are interesting, such as 'Precompilation'. It is also possible to supply a default answer for a question which will be asked.

In addition, there are some questions which are not asked by the 'Verbose' compilation type, but which nevertheless are available to user-defined types. These are: 'Macro compile', 'Macro flush', 'Max space', 'Expand splices', 'Special mode', 'Glue', and others.

One can select any of one's own defined compilation types as an answer to the 'Type of compilation' question, just like 'Verbose' and 'Short'. Except that the questions asked may differ, user-defined types are identical to the predefined types.

5.2.5.1. Tailor Files

User-defined types are saved (and loaded) from the file "sname;%COMBT TAILOR". It is possible to load other tailor files, but the "%COMBT" file in sname is loaded during startup. Tailor files are quite similar to MDL GC-DUMPed files and thus cannot be edited other than with COMBAT.

5.2.5.2. Create Type

This special compilation type requests a name for the type being made, then enters a loop with the prompt 'Question'. One may choose any of the available questions, and either supply an answer or (by default) request that the question be asked when a compilation of this type is being submitted. Note that only the 'How to run' and the following 'Type of compilation?' questions will be asked unless others are explicitly supplied; but one may supply answers to 'How to run' when creating a type.

In this mode, ^R will return to the 'Question' loop if one is about to supply an answer; otherwise, it returns to the 'Type of compilation' loop, aborting the type creation.

^G behaves exactly as it does in the normal loop. To indicate that one is finished, one should answer 'Finis' to the 'Question' prompt. It is possible to supply several different versions of the answer to a particular question: the last one given will be used. One may wish to default a particular question, after specifying that it was to be asked or after supplying some different default. This may be done by answering 'Delete question' to the 'Question' prompt, whereupon one will be asked for a particular question to ignore. This question will then be completely ignored. Note that all interesting questions are initially in this state.

There is also a 'Set question default' 'Question'. This requests a question name, then asks the user to supply an answer. The question will be asked, with the default supplied. Thus default settings of switches can be changed, and one can supply a file name for the precompilation while still being asked whether precompilation is desired. Unfortunately, user-supplied defaults for 'Text'-type questions are used if ESC is answered; to get rid of the default, type SPACE ESC. Note that this is exactly the inverse of the convention for defaulting file names.

When 'Finis' has been typed, a new copy of one's tailor file is written out. This may, in combination with 'Load tailor' and 'Replace tailor', have undesirable side effects.

5.2.5.3. Print Type

This requests the name of one of the types currently loaded, and prints out for it all questions which either will be asked when a compilation is being submitted or which have user-supplied defaults. If a particular question has been globally 'turned off' (such as the 'New compiler?' question, when there is no new compiler), an asterisk will be printed on the appropriate line to indicate that the information there is currently not used.

5.2.5.4. Delete Type

This requests the name of one of the currently-loaded types, and deletes it. A new copy of the tailor file is written out so all trace of the type will vanish when this command is used.

5.2.5.5. Alter Type

This requests a type name, then becomes identical to 'Create type', except that some questions already have answers. Again, 'Finis' must be typed to leave the loop and cause the modifications to be filed; typing ^R or ^S will leave the loop, but the modifications will be forgotten.

5.2.5.6. Load Tailor, Replace Tailor

Both of these request a file name, defaulting to the last one used for either a 'Load tailor' or 'Replace tailor' command. Initially this is "sname;%COMBT TAILOR". 'Load tailor' appends the types defined in the specified file to those already loaded, while 'Replace tailor' first throws away those already loaded. The types defined in this way are not distinguished from those loaded from one's own COMBAT tailor file; in particular, using 'Toggle verbosity' or any of 'Create', 'Alter', and 'Delete type' will cause all the types currently loaded to be written out to the COMBAT tailor file. If, therefore, one has done a 'Replace tailor', one can easily lose all of one's own types in this manner. I.e., it is very easy to destroy yourself.

5.2.5.7. Xerox Tailor

This requests the name of an existing user-defined type, and a new type name. The new type becomes an exact copy of the previously-existing type. This is particularly useful when one has several different types which do almost the same thing.

5.3. The Compiler (Internals)

The compiler's job is to take an MDL FUNCTION or group of FUNCTIONs and produce an operationally equivalent machine-language subroutine (RSUBR) using whatever information can be extracted from the source code and whatever additional information the user wishes to supply. The efficiency of the output code produced is directly proportional to the amount of information supplied by the programmer and inversely proportional to the generality of the source program. The information supplied by the programmer is usually in the form of optional data-type declarations (DECLs) and the use of programmer-defined data types (NEWTYPEs) that have built-in declarations. Unlike many programming languages, however, declarations are never required. The compiler will compile programs with no declarations at all, but the resulting output will not run as fast as with well-declared code. The current compiler can achieve speed-up factors of anywhere from about 4 to 100. The factor of 4 represents the speed-up for a very general program with very poor declarations. On the other hand, the factor of 100 represents a program with a very narrow range of application that has very good (that is, restrictive) declarations. Typical programs can expect to achieve factors of 20-40.

5.3.1. How It Works

The compiler as it currently exists is really two distinct programs. GETORDER is basically an interface between files of MDL functions and the compiler. It is a relatively small program that reads in the file, sets up the various compiler switches, calls the compiler one or more times and writes out the final file of RSUBRs. COMPILE itself is basically a compiler with three major and three minor passes. Pass 1 builds a model of the program, pass 2 analyzes each node of the tree and does data type analysis, pass 2.5 (minor) allocates stack space for variables and temporaries, pass 3 generates output code, and two minor passes do final stack allocation and peep-hole optimization.

5.3.1.1. COMPILE and COMPILE-GROUP

There are two distinct modes of compilation available. They are simple and multiple. Simple compilation occurs when COMPILE is called with one FUNCTION. It simply compiles that FUNCTION and returns. Multiple compilation occurs when COMPILE is called with a list of FUNCTIONs. It compiles each FUNCTION into a separate RSUBR. It differs from multiple calls to COMPILE in that it sometimes partially compiles a FUNCTION out of order to determine its calling sequence and do argument type-checking. This behavior is necessary when compiling mutually recursive FUNCTIONs. In all modes of compilation, COMPILE-FUNCTION is called to actually compile the individual FUNCTIONs. It calls the various compiler passes.

5.3.2. Modeling Pass

The first pass of the compiler takes the input FUNCTION and builds an expanded model of it. In the process of doing this, it produces a symbol table entry for every local variable bound and/or declared in the FUNCTION, any of its PROGs/REPEATs or MAPF/MAPR FUNCTIONs. It also produces the RSUBR DECL for the final output. Pass 1 also tries to decide if an internal entry (that is, an entry which can be called efficiently (see section 6.1)) can be used with this FUNCTION. If an internal entry turns out to be possible, Pass 1 generates an appropriate calling sequence for internal calls to use. The model built by Pass 1 looks like the original FUNCTION with all of the nodes in the FUNCTION's structure replaced with objects of type NODE (a new type defined for the compiler). A node in the model may have anywhere from 5 to 30 elements; the 5 element node is for simple quoted objects like fixed-point numbers, ATOMs etc. The 30 element nodes are for major elements of the program such as the node for the FUNCTION itself and nodes for PROGs and REPEATs. The majority of the nodes are general SUBR nodes, which have 10 elements. The Pass 1 structure is built in the following way. The top level program in Pass 1 generates a node for the entire FUNCTION. This node gets the following information put into it:

  1. A code specifying that this is a FUNCTION node.
  2. The data type that this FUNCTION is declared to return (or ANY).
  3. A LIST that will eventually contain the nodes comprising the body of the FUNCTION.
  4. A UVECTOR of internal names for internal calls to this FUNCTION.
  5. A symbol table for the variables declared and/or bound in this FUNCTION.
  6. A list of entries in the symbol table specifying how the arguments are to be set up (whether they are optional, QUOTEd, TUPLE etc.).
  7. The final RSUBR DECLs.
  8. A specification of how to pass arguments to this FUNCTION when it is compiled (whether the arguments should be in registers or on the stack).
  9. The number of required arguments and the total number of possible arguments.

In addition to the above information, slots exist in the node for additional information to be supplied by later compiler passes.

After the main node for the FUNCTION is built, the sub-nodes for the FORMs comprising the body of the FUNCTION are built. This is done by first dispatching to special Pass 1 code for the first element of the FORM. If no special code exists for this first element, a dispatch is made on the TYPE of the first element of the FORM (that is, ATOM, FIX, FUNCTION etc.). If no special code exists for either the first element or its TYPE, a general FORM node is built. In the case of an ATOM as the first element of the FORM, the normal lookup rules are invoked on the ATOM and it is dispatched again based on its value. ATOMs with no values either cause compilation warnings or are assumed to be RSUBRs (depending on compiler switch REASONABLE). All FSUBRs (COND, AND, OR, FUNCTION, PROG, REPEAT, UNWIND, etc.) have special Pass 1 code and produce very specific nodes. Most SUBRs don't dispatch to specific code during this pass. The exceptions are things like MAPF, ILIST, GET etc., which have somewhat non-standard treatment of their arguments. (Actually, MAPF and MAPR don't treat their arguments non-standardly, but they are treated specially in Pass 1 so that the inner FUNCTION may be open compiled.) As mentioned previously, all nodes have at least 5 elements. These are as follows:

  1. A node type code.
  2. A pointer to the parent node (if one exists).
  3. A specification of the data type the node will generate.
  4. A list of sub-nodes referred to as Kids.
  5. A name for the node, which may have different meanings for different nodes.

In addition, nodes other than nodes for QUOTEd objects have additional elements that are filled in during later passes of the compiler. After Pass 1 all additional passes work on the model built during Pass 1. The original FUNCTION is no longer even considered.

5.3.3. Analysis Pass

During Pass 1, very little information is determined regarding the resulting data types of various nodes. Indeed, with the exception of nodes produced by quoted objects, structured objects which will produce code to build copies of themselves, and FUNCTIONs, PROGs and REPEATs with declared values, no type information is produced. Even in the cases where type information is produced during Pass 1, it is usually not as detailed as other passes would like. The Analysis Pass has the job of refining the result type of each individual node based on various criteria:

  1. The declared types of the variables used in the program including GDECLs and MANIFESTs.

  2. The known type transformations produced by various SUBRs. (For example, it is known that LENGTH always produces a FIX result.)

  3. Some analysis of the context of the nodes within the program. (For example, in the following code:

     <COND (<AND <TYPE? .X LIST> <NOT <EMPTY? .X>>>
        <1 .X>)>

    regardless of how X is declared, it is obviously a LIST when the EMPTY? is run, and it is obviously not empty when the <1 .X> is run.)

The Analysis Pass performs a standard depth-first left-to-right tree walk on the Pass 1 model. The main dispatch function during this pass is called ANA. It does an initial dispatch based on the node type of each node. Since most nodes are still considered 'SUBR nodes', most of the dispatches end up at the SUBR call analyzer. The SUBR call analyzer has two types of further dispatch available. First it looks in a table for SUBRs that are capable of being completely open-coded: if it finds an entry in the table, the analyzer for that SUBR is invoked. If this SUBR is incapable of being open-coded, ANA checks another table to see if this SUBR has an internal entry available. If it does, the node is changed from a SUBR node to an internal SUBR node. If both dispatches fail, another table is checked to see if the object type returned by this SUBR is known, and if it is the result is put into the SUBR node.

Most of the work done by the Analysis Pass happens when the first dispatch occurs and special SUBR analyzers are invoked. Generally speaking, these analyzers check to see if they know enough about their arguments to transform their nodes to an open-code specification. For example, an invocation of the SUBR REST only transforms to an open-code node if both the PRIMTYPE of the first argument is known at compile time and there are no SEGMENTs in the call to REST. If a special SUBR analyzer decides that it can't open-compile in this case, it either leaves the node as a SUBR node or transforms it to an internal SUBR node.

5.3.4. The Type Analysis Model

In addition to the model of the FUNCTION built in Pass 1, the Analysis Pass adds additional information to the model concerning the current states of local variables. As the analyzer plunges down into the tree, it tries to keep track of the current DECL of each variable. Specifically, there's a slot in each symbol table entry called CURRENT-TYPE. The analyzer updates that slot based on its current knowledge. A call to SET causes the CURRENT-TYPE slot to be changed to the analyzed type of SET's second argument. When multiple control paths meet, the CURRENT-TYPE slots of a variable are OR'd together at the joining point. Conditional control structure nodes for COND, AND and OR also maintain two lists of transient information. These are called TRUTH and UNTRUTH. They specify what information will be valid if the true or false branches are taken respectively. For instance, a COND clause compilation can assume that any TRUTH information generated in the predicate of the COND will be valid for the rest of the clause. Some of the analyzers for the more widely used predicates have special code in them to add information to the current TRUTH and UNTRUTH values. These predicates include TYPE?, EMPTY?, LENGTH? and NOT. Looping control structures pose additional problems for the type analysis model. The approach taken by the type analyzer is to build a copy of the current types of all variables before analyzing the loop structure. This copy of the local type information constitutes the assumptions currently in effect. After the loop analysis is complete, the assumptions are checked against the current state of the variables. If any of the assumptions have been violated, the assumptions are updated and the loop is re-analyzed.

5.3.5. Life-and-Death Analysis

The Analysis Pass also performs a life-and-death analysis on the local variables. This is done by assuming that the variable's value is dead at each LVAL node for that variable. If another LVAL node for this variable is discovered that is reachable from this one before any intervening SET nodes for this variable, the original node is updated to be alive. This life-and-death information is used during the Code Generation Pass.

5.3.6. The Variable Allocation Pass

The Variable Allocation Pass (VAP) is a relatively simple one. Its purpose is to allocate stack space for all of the variables bound in the FUNCTION, its PROGs and REPEATs and its MAPF/MAPR FUNCTIONs. There are various switches that control the manner in which this allocation is performed.

The most important switch specifies whether or not this FUNCTION needs a FRAME or not. The VAP always starts out assuming it does not need to build a FRAME. This assumption will be changed if it is discovered that externally accessible named ACTIVATIONs exist in the FUNCTION or any of its inner blocks (PROGs or REPEATs or FUNCTIONs) or if at any time it is discovered that the address of a variable cannot be specified as a fixed offset from the top of the stack. Whenever this assumption is changed, the VAP starts over again with the new assumption in effect.

Another switch that controls the behavior of the VAP specifies whether or not the stack slots for inner blocks will be pre-allocated because the stack will be in a 'fuzzy' state when these blocks are running. The stack is said to be in a 'fuzzy' state when the number of slots currently being used cannot be determined at compile time. This usually occurs when a TUPLE is being constructed for a MAPF. For instance, in

<DEFINE F (X Z)
   <MAPF ,VECTOR <FUNCTION (Y) <G? .Y .Z>> ...>>

the elements of the VECTOR will be between the top of the stack and the location of variable Z. Even if F has a FRAME, the location of Y will not be known relative to the FRAME pointer at compile time. Therefore, the initialization code for F will pre-allocate the stack space for Y.

During the VAP, each symbol table entry gets its address field set based on where that variable will be on the stack. Also nodes for PROGs, REPEATs and MAPF/MAPR FUNCTIONs that have bound variables get additional information inserted in themselves. This information includes where the SPECIAL variables start and where the UNSPECIAL variables start.

5.3.7. The Code Generation Pass

The Code Generation Pass (CGP) is probably the most complicated of all the passes. Fortunately, the Analysis Pass has already refined the model so that the CGP can dispatch immediately to the special-purpose code generators. Besides building a list of assembly-language instructions as output, the CGP keeps track of the current state of the stack, the contents of the registers, the current state of variables (whether they are in registers or on the stack or both) and the contents of the temporaries.

The general dispatch routine during the CGP is called GEN. It takes two arguments: a NODE and a specification of where to leave the result. The second argument can be any of the following:

  1. The ATOM FLUSHED, meaning that the code will be executed for effect rather than value.
  2. The ATOM DONT-CARE, meaning that the caller of GEN is leaving the decision up to the specific generator as to where to leave the result.
  3. An object of type DATUM which specifies a place for the type and value of the result to be left.

Type DATUM is of PRIMTYPE LIST and contains two elements, one for the type and the other for the value. The elements of a DATUM may take on a variety of values in different circumstances. These include:

  1. A TYPE name. This can only occur in the type slot and it means that the type of the object is known at compile time and this is it. It indicates that the code generator need not put the type-code anywhere.
  2. The ATOM DONT-CARE. This means that the caller doesn't care where the result for this field is left.
  3. The ATOM ANY-AC. This tells the generator to leave the result in any available AC.
  4. An object of type AC. This tells the generator to force the result into a specific AC.
  5. An object of type ADDRESS:C or ADDRESS:PAIR. Both of these specify addresses on the stack or in the interpreter.
  6. An object of type OFFPTR. An OFFPTR has three fields: a DATUM, an offset (a FIX), and a PRIMTYPE. An OFFPTR tells the generator to leave the result in the word pointed to by the inner DATUM and offset by the offset.

If an element of a DATUM is ANY-AC or DONT-CARE, the generator is required to update the DATUM to reflect the actual location of the result. If the element is a TYPE, the generator may change it to an AC which means that it happened to end up with the TYPE in that AC. The generators always return a DATUM specifying where the result was actually left, unless the caller wanted the result FLUSHED. There is one special DATUM that can be returned. It is the GVAL of the ATOM NO-DATUM and it means that the specified node will not return a value (that is, it is a RETURN or an AGAIN or something). There are six objects of type AC in the compiler, corresponding to ACs 0, A, B, C, D and E. AC 0 is special since it can't be used as a pointer, and it always contains very transient information. It is never used to fill in an ANY-AC slot in a DATUM. The other five ACs are in the pool of available ACs. Objects of type AC have about ten different slots associated with them. They are used for finding available ACs and generating output code that uses them. The slots used in AC allocation are as follows:

  1. ACLINK. If this is FALSE, the AC contains no temporary value for the current computation. Otherwise, it is a list of active DATUMs that contain it.
  2. ACAGE. This is only used when the ACLINK is non-FALSE. It is updated to a higher number at each use of the AC and is used in an LRU algorithm when an active AC must be flushed.
  3. ACRESIDUE. If this AC is currently equivalent to some local variables, this slot contains a list of the symbol-table entries for these variables. The symbol-table entries themselves have a slot called INACS that points back to the ACs that contain its type and/or value. They also contain a slot called STORED that specifies whether the only copy of the variable is in the ACs or it is also in memory.
  4. ACPROT. This slot is a boolean saying whether this AC is protected or not. If the AC is protected, it can't be allocated for any reason. Protection is only invoked for very short stretches of code.
  5. ACPREF. This slot says that this AC deserves slightly preferential treatment. It means, all other things equal, don't choose this AC. The AC allocation algorithm consists primarily of trying to find the best possible candidate when an AC is needed. The routine GETREG is used to find an available AC. First it rejects all ACs that are protected (if they all are protected, the compiler generates an internal error since this should never happen). If there are one or more ACs with their ACLINKs FALSE, GETREG will choose from among them. It will prefer ACs with no ACRESIDUE, that are numerically adjacent to another free AC (because some PDP-10 instructions destroy the next AC), and which do not have their ACPREFs on. If the AC chosen has an ACRESIDUE, code is generated if necessary to store any of the variables that are only in ACs. If no AC exists with an ACLINK that is FALSE, GETREG finds the AC with the smallest ACAGE. Code is generated to store the contents of the AC in a temporary so that it is available. The DATUMs that were in the ACLINK are updated to indicate that they are now pointing to temporaries as opposed to ACs. Thus it is possible that a generator could need sub-results in ACs, and after causing one to be generated in an AC, find that while generating the second one the first slipped back into a temporary. The generator would then have to generate code to reload an AC from the temporary. The CGP invokes various special-case optimizations by passing information up and down the tree as code is generated. The generators for conditional branching FSUBRs like OR, AND and COND employ a predicate generator whenever possible. This generator is like GEN except that it takes three additional arguments: a label to branch to, a flag saying whether to branch on truth or falseness, and a flag saying whether this predicate is being NOTed. The general predicate generator then looks at the predicate node to see if it can take the additional arguments for predicate generation. If it can, the general predicate generator just passes all the arguments down; otherwise it calls GEN and generates the additional testing and branching code itself. Currently AND, OR, COND, ==?, N==?, G?, G=?, L?, L=?, 0?, 1?, TYPE?, NOT, ASSIGNED?, MEMQ, LENGTH? and EMPTY? have special predicate code associated with their generators. Others may be added as the need develops. Other optimizations are invoked by simply recognizing common patterns of MDL code. For instance, the compiler recognizes <SET X <+ .A 1>> as a PDP-10 AOS instruction and it generates very efficient code for <REST .X <- <LENGTH .X> 1>> by recognizing the pattern of code. The compiler always takes advantage of as much knowledge as it has about the types generated by particular nodes to generate good code. This is especially the case when it is handling the code for NTH, REST and PUT in structures. It uses type information concerning the length of the structure and the amount being RESTed for the NTH, REST or PUT, to figure out whether or not to generate bounds checks in the compiled code. It also uses information about the current type of the slot being read or written to decide whether or not to read or write the type word. Obviously, a lot of this type information was the same information obtained during the Analysis Pass of the compilation.

Some code generation routines are capable of changing the order of generation of the sub-nodes. This is done to try to get the node requiring the most ACs compiled first so that it won't interfere with any AC requirements of the current node. This obviously requires that the commuted nodes have no interacting side effects.