Chapter 1

Front End Modules

1.1 Introduction

Unlike some compilers which generate low-level code directly, the Id compiler uses parse-trees as one of its intermediate representations for programs. More detailed documentation about the parse-tree data structure can be found in [5]. The front end of the Id compiler is the group of modules which operates on the parse-tree representation.

Id Source File ↓

                           file-parser or stream-parser

↓

                          pre-scope-analysis-desugaring

↓

                                  scope-analysis

↓

                                  type-checking

↓

                             overloading-translation

↓

                                   lambda-lift

↓ Id Compiler Middle End

Figure 1.1: Structure of Current Id Compiler Front End (3/18/91)

1.2 The Modules

Each module description briefly describes some high-level characteristic of the module, including:

Module: The defcompiler module definition.

Options: A description of the module’s options.

Description: A declarative description of the module’s effect on the parse tree.

Strategy: The algorithms used by the module.

Author: Primary person responsible for coding.

Caveats: Known limitations, warnings, points of interest, etc.

Each module in the front end of the compiler reads or modifies a number of global data structures in addition to its explicit parse-tree argument and result. The following entries, for each module, provide information about its usage of global data structures:

Parse-Tree Properties: Parse-tree node properties.

Parse-Tree Slots: Parse-tree node slots.

Not each module has all the entries filled in. If a module is the first to define an entry in a global structure or is the exclusive user of an entry then the entry’s name is in boldface followed by a description. Otherwise, just the name is listed.

1.2.1 Parsing

Module:

(defcompiler-module file-parser id-compiler
  (:output parse-tree def)
  (:levels-marked program)
  (:before-function initialize-lexical-analyzer-for-file)
  (:function parse-def)
  (:wrapper-macro file-parser-wrapper)
  (:options input-file))
(defcompiler-module stream-parser id-compiler
  (:output parse-tree def)
  (:levels-marked program)
  (:before-function initialize-lexical-analyzer-for-stream)
  (:function parse-def)
  (:wrapper-macro stream-parser-wrapper)
  (:options input-stream initial-character
            initial-line initial-column input-stream-truename))

Options:

• input-file is the filename of the Id file to be compiled. This is a positional argument which has the highest importance (meaning that this argument will appear first in the argument list of the compile function). This option is only used for file-compiles.

• input-stream is the stream that is passed to the compiler. This is a positional argument which also has the highest importance. (This argument will also appear first in the argument list of the compile function. However, there is no conflict with the input-file option, because only one of these two options is ever specified for any compile function.) This option is only used for editor-compiles.

• initial-character is the initial setting for the counter that the parser uses to keep track of where each lexeme comes from in the editor buffer. Eventually, this information is used for error messages and source debugging information. This option is only used for editorcompiles, and the editor calculates the character offset from the beginning of the buffer. (For file-compiles, the character counter is automatically set to 0, so there is no need for an option.)

• initial-line is similar to the initial-character option, except that this is the line offset from the beginning of the buffer.

• initial-column is similar to the previous two options, except that this is the column offset from the current line.

• input-stream-truename is only used for editor-compiles. This is the truename of the file which is associated with the buffer in which the region or definition is being compiled.

Description: Only one of these two modules (file-parser and stream-parser) are used, depending upon whether we are compiling a file or an editor buffer. file-parser reads from a file stream, and stream-parser reads from an editor stream.

The two modules are similar: they read the parser tables generated by PAGEN and parse the input stream. The only function of these modules is to produce parse-trees from Id source.

Strategy: The parser is a LALR(1) parser. More information about parsing can be found in [1].

The chapter on PAGEN describes how to change the grammar of the language. Both file-parser and stream-parser are just interpreters for the parser tables generated by PAGEN.

Author: Ken Traub, May 1986

1.2.2 Desugaring

Module:

(defcompiler-module pre-scope-analysis-desugaring id-compiler
(:input parse-tree def)
(:output parse-tree def)
(:options loop-bound-mode)
(:function pre-scope-analysis-desugar-def))

Options:

• loop-bound-mode selects whether for loops will be bounded or unbounded. This option

is set to either :bounded-for-loops or :unbounded-for-loops. If the option is set to

:bounded-for-loops, then the compiler will generate the bounded loop schema, which has slightly more overhead than the unbounded loop schema.

The default is :unbounded-for-loops.

Description: Several types of desugaring are done in this module:

1. List comprehensions, array comprehensions, accumulator comprehensions, and stream comprehensions are translated into loops.

2. Array literals are desugared into either a while loop or a list of assignments, depending upon whether its bounds are known at compile time.

3. Managers are desugared to abstract types.

4. Multi-clause def’s are desugared to case statements.

5. Lambda’s (fun’s) are desugared to be internal def’s (which are eventually lifted to the toplevel by the lambda lifting module).

6. for loops are transformed into while loops.

Strategy: Recursively descend the parse tree. When you find a pattern that matches one that you wish to desugar, cut and paste that pattern.

Author: Ken Traub, January 1987

1.2.3 Scope Analysis

Module:

(defcompiler-module scope-analysis id-compiler
  (:input parse-tree program)
  (:output parse-tree program)
  (:function scope-analyze-program))

Description: variable objects are added to parse tree nodes relating valriable definitions and their uses (def-use information). This analysis is done using the attribute grammar which is described in more detail in [5]. More information about attribute grammars can be found in [1] and in the previous chapter.

Strategy: To compute def-use information, a synthesized pt-node attribute is defined for the definition point of each variable use, and an inherited attribute is defined for the use point of each variable definition. Each node is then touched to calculate the value of each attribute variable.

The type inference system also uses attribute grammars to calculate the types.

Author: Ken Traub, January 1987

1.2.4 Type Inference and Checking

Module:

(defcompiler-module type-checking id-compiler
  (:input parse-tree program)
  (:output parse-tree program)
  (:function type-check-program)
  (:options type-check))

Options:

• type-check determines whether the compiler will type infer and type check. If this option is set to t, then the compiler will infer and check the types of the program; if this option is set to nil, then the parse tree will pass through this module without alteration.

The default is t.

Description: The type-inference system determines the type of each variable and function. A more detailed description of the type-inference system can be found in Shail Aditya’s Master’s thesis [4]. The type-inference system is based upon the Hindley/Milner type-inference system used in ML, and has been extended to work with separate compilation. A clear exposition of the Hindley/Milner type-inference algorithm can be found in [3].

Strategy:

Author: Shail Aditya, July 1988

Caveats: The type-inference module has the same limitations that the Hindley-Milner system has. It has exponential complexity, and limits the polymorphism of let-block assigned variables.

In addition, in order to resolve the type of certain functions, sometimes separate compilation will not work appropriately. Although information is preserved between separate compilations, if that information changes, then enough context must be compiled in order to resolve the types of the changed functions.

1.2.5 Overloading Resolution

Module:

(defcompiler-module overloading-translation id-compiler
  (:input parse-tree program)
  (:output parse-tree program)
  (:function translate-overloaded-program))

Description: Most of the work for this module is actually done in the type-checking module. This module takes the information deduced in the type-checking module and cuts and pastes parse tree nodes so that each overloaded operator is transformed into the correct type instance of that operator.

After this module, each operator has an unambiguous type. For example, all + operators will be translated to either plus~ float or plus~ int. If the operator cannot be resolved, an error message is printed.

Strategy: With the type information calculated in the type-checking module, the context of each overloaded operator resolves the type of the operator. Each node is visited, and if that node is an overloaded operator, the type of the operator is looked up from information calculated in the type-checking module and that operator is replaced with the correct type instance of the operator.

Author: Shail Aditya Gupta, July 1990 Caveats: The overloading-translation module does not have much more functionality than the type-checking module. These two modules are separate because the type-checking module does not do any cut and paste on the parse tree, and overloading-translation only does cut and paste. In the future, this module may be incorporated into the type-checking module.

1.2.6 Lambda Lifting

Module:

(defcompiler-module lambda-lift id-compiler
  (:input parse-tree def)
  (:output parse-tree def)
  (:function lambda-lift-def))

Description: Nested def’s are lifted to the outermost scope, making every function definition a top-level function. Extra arguments are added to the previously internal function definition to pass along variables that the internal function references from its lexical scope.

Strategy: The algorithm for lambda lifting is taken from [2].

Author: Ken Traub, October 1986

Caveats: Lambda lifting is implemented to support nested function definitions. Scheme and Lisp use environments in order to support nested function definitions. It is not clear that lambda lifting is more efficient than environments. Perhaps we should do an environment-based implemention in order to clarify the various issues involved in the relative efficiency of these two implementations.

Bibliography

[1] Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. Compilers: Principles, Techniques and Tools. Addison Wesley, Reading, Massachusetts, USA, 1986.

[2] Lennart Augustsson. A compiler for lazy ml. In Proc. 1984 ACM Conf. on Lisp and Functional Programming, Austin, Texas, pages 218–227. ACM, August 1984.

[3] L. Damas and R. Milner. Principle Type Schemes for Functional Programs. In Proceedings of the 9th ACM Symposium on Principles of Programming Languages, pages 207–212, 1982.

[4] Gupta, Shail Aditya. An Incremental Type Inference System for the Programming Language Id. Technical Report MIT/LCS/TR-488, Laboratory for Computer Science, 545 Technology Square, MIT, Cambridge, MA 02139, November 1990. First published as the author’s Master’s thesis.

[5] Kenneth R. Traub. A dataflow compiler substrate. Technical Report CSG Memo 261, MIT Laboratory for Computer Science, 545 Technology Square, Cambridge, MA 02139, January 1991. Revised by Jamey Hicks and Shail Aditya.