![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to paper.ms CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10dc / cmd / sml / doc / papers / compiler|
Return to paper.ms CVS log | Up to [Research Unix] / researchv10dc / cmd / sml / doc / papers / compiler |
1.1 root 1: .EQ
2: delim $$
3: define |-> ' down 3 size -3 | back 25 -> '
4: .EN
5: .nr PS 11
6: .nr VS 13
7: .fp 5 CW
8: .ND August 5, 1987
9: .TL
10: A Standard ML Compiler
11: .AU
12: Andrew W. Appel \fR*\fP
13: .FS
14: * Supported by NSF Grant DCR-8603453 and by
15: a Digital Equipment Corporation Faculty Incentive Grant.
16: .FE
17: .AI
18: Dept. of Computer Science
19: Princeton University
20: Princeton, NJ 08544
21: .AU
22: David B. MacQueen \fR\(dg\fP
23: .FS
24: \(dg Part of this author's work was done while an SERC Senior Visiting
25: Fellow at the University of Edinburgh.
26: .FE
27: .AI
28: AT&T Bell Laboratories
29: Murray Hill, NJ 07974
30: .AB
31: .LP
32: Standard ML is a major revision of earlier dialects of the functional
33: language ML. We describe the first compiler written for Standard ML
34: in Standard ML. The compiler incorporates a number of novel features
35: and techniques, and is probably the largest system written to date in
36: Standard ML.
37: .LP
38: Great attention was paid to modularity in the construction of the
39: compiler, leading to a successful large-scale test of the modular
40: capabilities of Standard ML. The front end
41: is useful for purposes other than compilation, and the back end is
42: easily retargetable (we have code generators for the VAX and MC68020).
43: The module facilities of Standard ML were taken into account early in
44: the design of the compiler, and they particularly influenced the
45: environment management component of the front end. For example, the
46: symbol table structure is designed for fast access to opened
47: structures.
48: .LP
49: The front end of the compiler is a single phase that integrates
50: parsing, environment management, and type checking. The middle end
51: uses a sophisticated decision tree scheme to produce efficient pattern
52: matching code for functions and case expressions.
53: The abstract syntax produced by the front end is translated into a simple
54: lambda-calculus-based intermediate representation that lends itself to
55: easy case analysis and optimization in the code generator. Special
56: care was taken in designing the runtime data structures for fast
57: allocation and garbage collection.
58: .LP
59: We describe the overall organization of the compiler and present some
60: of the data representations and algorithms used in its various phases.
61: We conclude with some lessons learned about the ML language itself and
62: about compilers for modern functional languages.
63: .AE
64: .pn 1
65: .nr VS 17
66: .np
67: .NH
68: Introduction
69: .LP
70: The ML language is a typed functional language roughly based on
71: Landin's ISWIM [1].
72: It was originally designed in the
73: mid-1970s as the metalanguage of Edinburgh LCF, a machine-assisted
74: reasoning system, and its features were in part motivated by its
75: intended use to express proof tactics. However, these features made
76: it an attractive vehicle for general purpose symbolic programming, and
77: it wasn't long before free-standing implementations appeared, such as
78: Cardelli's compiler[2],
79: which was written in Pascal. In 1983 a
80: group of interested parties began work on an extensive revision of the
81: language design that lead to Standard ML [3,\|4,\|5,\|6].
82: Standard ML
83: extended the earlier versions in certain ways and incorporated ideas
84: from Hope[7],
85: another language developed in Edinburgh in the late 1970s.
86: It also included a module facility that significantly extends the
87: basic polymorphic type system of earlier ML versions and supports
88: large-scale program development.
89:
90: Several implementations of Standard ML have been under development in
91: recent years.
92: Luca Cardelli's compiler was modified to be partially
93: compatible with Standard ML. Meanwhile, Cardelli's original compiler
94: had been reimplemented in its own variant of ML by Kevin Mitchell and
95: Alan Mycroft at Edinburgh, and this compiler was also modified with
96: the help of Robert Harper to make it conform fairly closely to the
97: Standard ML definition. A new compiler was developed in Cambridge by
98: David Matthews, using his Poly language [8,\|9]
99: as the implementation
100: language, and sharing the Poly back end.
101: At INRIA, a group headed by Gerard Huet and Guy Cousineau
102: have been implementing an ML variant called CAML[10]
103: that is intermediate
104: between the LCF version and Standard ML.
105:
106: Yet there was still justification for another Standard ML
107: compiler. One of the main motivations was to build a compiler that
108: would itself be implemented in Standard ML. Such a compiler would
109: have several advantages. It would be a good basis for building
110: meta-level tools (pretty-printers, program analyzers, debuggers, etc.)
111: that could share data types and code with the compiler itself and
112: might be used in ML application programs or in an ML programming environment.
113: It would also serve as a large-scale test of the Standard ML design,
114: particularly the module facility, which was the most novel and untested
115: part of the language. Finally, a new compiler provides an
116: opportunity to try out new implementation strategies (for code
117: generation, optimization, type checking, and modules, for instance).
118: A simple lambda-calculus intermediate representation
119: makes the compiler much cleaner, and could also
120: provide a base for
121: research in evaluation algorithms (call-by-value, normal-order, lazy,
122: combinator-based, parallel, and others) for lambda-calculus.
123:
124: As a call-by-value, higher-order functional language, many of the
125: conventional compilation techniques for functional languages apply to
126: Standard ML. The distinguishing features of ML are its polymorphic
127: type system, the notion of concrete data types for expressing disjoint
128: unions and recursion, the use of pattern matching based on the
129: constructor-functions associated with data types, the use of typed,
130: value-carrying exceptions, the fact that all updateable variables are
131: introduced explicitly by application of the
132: .B ref
133: constructor, and
134: modular programming based on signatures (interface specifications),
135: structures (implementations of interfaces) and functors (functions
136: from structures to structures). These features, singly or in combination,
137: produce novel challenges in compiler design. They also, it turns
138: out, can be effectively exploited in the writing of a compiler.
139:
140: The compiler was written using the Edinburgh Standard ML compiler and
141: then bootstrapped to compile itself. However, the compiler shares
142: no code with previous compilers; and the runtime system,
143: written in C with the help of Peter Weinberger, is also completely
144: new.
145: .NH
146: Architecture
147: .LP
148: The ML compiler described here consists of three phases. The front
149: end consists of a recursive descent parser into which environment
150: management (determining scopes, associating binding and applied
151: occurrences of variables) and type checking are integrated. The
152: output of the front end is a fully typed abstract syntax tree.
153: The front end makes no decisions about runtime
154: locations of variables. It simply assigns them unique identifiers,
155: and the back end makes representation decisions.
156:
157: The middle end performs a simple translation of this abstract tree
158: into an untyped lambda calculus representation,
159: and produces an optimized representation of pattern-matching as one-dimensional
160: switch expressions.
161:
162: The back end transforms the lambda
163: form into target machine code using a largely machine-independent code
164: generator based on an ``abstract machine'' interface. The expressions
165: given to the back end never contain free variables; this simplifies
166: the interface between the code generator and the runtime system.
167: .NH
168: The Front End
169: .LP
170: The front end of the compiler consists of a conventional lexical
171: analyzer, abstract syntax datatypes, environment management machinery,
172: a type checker, and a recursive descent parser that drives the lexical
173: analysis, environment management and type checking.
174: .NH 2
175: Abstract syntax
176: .LP
177: The abstract syntax is implemented in two layers. There is a
178: collection of data types defining the ``bare'' abstract syntax
179: that forms a minimal kernel of the language. For instance, the
180: \fIexpression\fP data type is defined as follows:
181: .DS
182: .ft CW
183: .vs 13
184: datatype exp = VARexp of var ref
185: | CONexp of datacon
186: | INTexp of int
187: | REALexp of real
188: | STRINGexp of string
189: | RECORDexp of (numberedLabel * exp) list
190: | SEQexp of exp list
191: | APPexp of exp * exp
192: | CONSTRAINTexp of exp * ty
193: | HANDLEexp of exp * handler
194: | RAISEXexp of exp
195: | LETexp of dec * exp
196: | CASEexp of exp * rule list
197: | FNexp of rule list
198: .vs 17
199: .ft R
200: .DE
201: The full abstract syntax consists of these bare syntax types augmented
202: with a small number of derived forms, such as clausal function definitions.
203: These derived forms are implemented as functions that generate the
204: appropriate expansion into bare syntax forms.
205: .NH 2
206: Environment management
207: .LP
208: We separate the idea of symbol-table manipulation
209: from the details of the kinds of bindings found in ML.
210: There is a generic environment mechanism that performs binding,
211: lookup, and scope management functions; it
212: is implemented as a functor that takes the
213: binding type as a parameter.
214: The binding type is a disjoint union of the specific categories of identifiers
215: (variables, constructors, type constructors, etc.):
216: .DS
217: .ft CW
218: .vs 13
219: datatype binding
220: = VARbind of var \fI(* variables *)\fP
221: | CONbind of datacon \fI(* data constructors *)\fP
222: | EXNbind of datacon \fI(* exceptions *)\fP
223: | TYCbind of tycon ref \fI(* type constructors (patchable) *)\fP
224: | TYVbind of tyvar \fI(* type variables *)\fP
225: | SIGbind of signatureVar \fI(* signatures *)\fP
226: | STRbind of structureVar \fI(* structures *)\fP
227: | FCTbind of functorVar \fI(* functors *)\fP
228: | FIXbind of fixity \fI(* infix attributes of variables *)\fP
229: .vs 17
230: .ft R
231: .DE
232: The generic environment uses hash tables, which we call binding tables
233: or simply tables, to map symbols to bindings. The environment
234: consists roughly of a stack of tables to hold the actual bindings and
235: a stack of ``remarks'' that records information about bindings and
236: scopes. Only the stack of tables is used when looking up symbols,
237: while the remarks are used when entering and leaving scopes and when
238: binding symbols. There are two types of tables in the stack of
239: tables: those representing the bindings in a previously defined
240: structure that has been ``opened'', and those representing bindings in
241: currently open scopes (i.e. top-level, let-bound, and function
242: parameter bindings).
243:
244: As indicated above, the binding type is a union of all the
245: various kinds of bindings a symbol may have. The tables therefore
246: hold bindings of all kinds, and the specialized access functions for
247: variables, constructors, etc. search only for bindings of the desired
248: kind. Thus it is possible for a symbol to simultaneously have several
249: bindings of different kinds, e.g. as a variable, a type constructor,
250: and an exception. However, variables and constructors share the same
251: name space, so it is not possible for a symbol to be simultaneously
252: bound as a variable and a constructor, despite the fact that these are
253: two disjoint kinds of bindings. The information associated with a
254: symbol, such as the type of a variable or the signature of a
255: structure, is contained in the projected value of its binding (e.g. the
256: var or structureVar).
257: .NH 2
258: Parsing
259: .LP
260: The lexical analyzer is conventional, turning the input
261: character stream into a stream of tokens, recognizing keywords,
262: identifiers, and string and numeric literals.
263: The parser reads tokens from the lexical analyzer and produces an
264: abstract syntax tree containing type and binding information.
265: Parsing is done by recursive descent, with a precedence parser
266: for infix operators in expressions. Unlike previous ML compilers, but
267: like most compilers for Algol-like languages, management of the
268: compile-time environment is done at the same time as parsing: identifiers
269: are entered into the environment as they are defined, and looked up
270: in the environment as they are used.
271:
272: Two particular problems crop up in parsing ML: identifiers may be declared
273: infix, or have their precedence changed, in lexically-scoped declarations;
274: and constructors cannot be syntactically distinguished from identifiers.
275: To handle the infix-operator problem, the lexical analyzer makes no distinction
276: between ordinary identifiers and identifiers that are declared as infix operators.
277: Instead, the operator-precedence expression-parser looks up each identifier
278: in the symbol table to determine if it has a fixity binding, and if it does,
279: what its precedence is. Recognizing constructors can be done similarly
280: by looking up identifiers
281: in the environment.
282: This scheme works nicely in the presence of
283: modules and
284: .B open
285: declarations: if a module $A$ is opened in a scope (even a local scope),
286: and an infix identifier $i$ is used from $A$, the precedence parser will
287: automatically find the precedence declaration of $i$ in the environment.
288:
289: Forward reference to identifiers is legal in mutually recursive definitions.
290: For example, in the function declaration:
291: .DS
292: .ft CW
293: .vs 13
294: fun f(a,b) = if a=0 then b else g(a-1)
295: and g(x) = f(x,x)
296: .vs 17
297: .ft R
298: .DE
299: the first occurrence of the identifier \f5g\fP is in the body of \f5f\fP,
300: which is before the function \f5g\fP is declared. To handle this problem,
301: all free identifiers found in the body of a recursive function definition are
302: kept on a ``backpatch list;'' when the mutually recursive declarations
303: are completely parsed, any references to identifiers defined in those
304: declarations are patched. This extends straightforwardly to nested
305: mutually recursive definitions. Note that constructors are not treated
306: this way; constructors cannot be redefined by
307: .B fun
308: or
309: .B
310: val rec
311: .R
312: definitions, so they are not put on the backpatch list. This means, of course,
313: that all identifiers must be looked up just to determine if they are constructors.
314: .NH 2
315: Type Checking
316: .LP
317: The conventional polymorphic type checking algorithm[11,\|12]
318: is used at present.
319: The basis of the algorithm
320: is the unification of type terms by destructively instantiating type
321: variables so that they become indirections to other types. The
322: administration of generic or bound type variables is done more
323: systematically than in the Cardelli and Edinburgh compilers, but
324: generic types are still copied for each applied occurrence of a
325: variable. A new type representation and type checking algorithm based
326: on structure sharing (in the Boyer-Moore sense [13])
327: has been prototyped with the help of Nick Rothwell. In this new scheme,
328: a polymorphic type is represented as a scheme whose bound variables are
329: indices into an environment vector; different instantiations share the
330: scheme but have different environment vectors.
331:
332: Overloading is accommodated to a limited extent. Currently only
333: certain predefined primitives such as ``+'' are overloaded, and there
334: are no facilities provided by the language for defining new overloaded
335: identifiers. Overloading is implemented as in the Edinburgh compiler,
336: where a type scheme is associated with the overloaded identifier and
337: each overloading (variant) has a type that is an instance of that
338: scheme. The contextual type of an occurrence of the identifier is
339: matched against the scheme and the resulting instantiations of the
340: scheme type variables is used to choose the appropriate variant.
341: This is simpler though more restrictive than the technique used in Hope[7],
342: where variants could have arbitrary types, as long as they
343: were incomparable (i.e. one was not an instance of another).
344: .NH 2
345: Reference and exception types
346: .LP
347: The treatment of references and exceptions with ``open'' types
348: is new, and is based on the fact that the contents of a reference
349: cell cannot be constrained to be polymorphic, and so must be considered
350: to be monomorphic. The following example illustrates the problem.
351: .DS
352: .ft CW
353: .vs 13
354: let val s = ref (fn x => x)
355: in s := (fn x => x+1); (!s) true
356: end
357: .vs 17
358: .ft R
359: .DE
360: If s were given the polymorphic type
361: $roman "ALL"^ alpha "." ( alpha -> alpha ) bold roman "ref"$, then this
362: expression would type check, permitting an obvious type error. To prevent
363: this, we insist that the type of an applied occurrence of the ref
364: constructor should always be given a ``ground'' type (one with no locally-bound
365: type variables).
366:
367: However, functions whose application can create
368: reference variables can still have polymorphic types of a restricted
369: kind. Consider the declaration
370: .DS
371: .ft CW
372: .vs 13
373: val F = fn x => let val r = ref x
374: in !r
375: end
376: .vs 17
377: .ft R
378: .DE
379: Here the function F can be given polymorphic type
380: $roman "ALL"^ alpha sup 1 roman "."
381: alpha sup 1 -> alpha sup 1$ where $alpha sup 1$
382: is a special kind of type variable
383: called a \fIweak\fP type variable (the superscript ``1'' indicates that
384: there is one lambda abstraction suspending the creation of the
385: ref cell). When F is applied to an argument, a reference value
386: of type $alpha sup 1$ is created, and hence this weak type
387: variable must be instantiated to a ground type. This means that
388: an expression like (F nil) would not be properly typed. In contrast,
389: the type
390: $alpha sup 1 bold roman "ref"$
391: assigned to r is permissible because $alpha sup 1$ is implicitly
392: bound in an outer scope and within the scope of its binding is treated as
393: a constant type.
394:
395: Exception declarations raise similar problems, which are handled
396: by an analogous use of weak type variables.
397:
398: The Cardelli and Edinburgh compilers used an earlier form of this
399: treatment proposed by Damas[14].
400: This earlier version was looser in one respect (it allowed unbound
401: weak type variables in types) and more restrictive
402: in another (multiple levels of lambda abstraction were not
403: allowed), and it had some rather counterintuitive effects.
404: .NH 2
405: Modules
406: .LP
407: The simplest kind of module in Standard ML is called a structure. It is
408: most simply defined as an encapsulated set of declarations, as in
409: .DS
410: .ft CW
411: .vs 13
412: structure S =
413: struct
414: type t = int * int
415: val x = (13, 18)
416: end
417: .vs 17
418: .ft R
419: .DE
420: The compile-time symbol table representation of such a structure is
421: a binding table containing a binding for each identifier
422: declared in the structure. There is also an abstract syntax tree for
423: the structure, from which code is generated.
424:
425: A signature is an interface specification for a structure. For
426: instance, the structure above will match the following signature:
427: .DS
428: .ft CW
429: .vs 13
430: signature SS =
431: sig
432: type t
433: val x : t
434: end
435: .vs 17
436: .ft R
437: .DE
438: Signatures are also represented by binding tables, but an abstract
439: syntax tree is not needed since there is no code generated for
440: signatures.
441:
442: A functor is a structure abstracted with respect to one or more
443: structure parameters, which are characterized by signatures. It
444: follows that the representation of a functor consists of a structure
445: representation (the body) and a parameter specification. As part of
446: the parameter specification one can impose sharing constraints among
447: the parameters; these constraints are represented by transforming the
448: parameter specification into a directed acyclic graph of parameter
449: structures.
450:
451: Functors introduce some additional forms of structures, namely formal
452: parameter structures and structures defined by functor applications.
453: For formal parameters, the parameter signature serves as a virtual
454: template defining the components of the structure. In the case of
455: functor applications, the functor body (which may itself be a functor
456: application) is closed with respect to the environment formed by
457: binding actual parameters to the formals.
458:
459: Functor application in principle involves a beta-reduction in which
460: the actual structure parameters are substituted for the formal
461: parameters in the functor body to create the result structure. This
462: beta-reduction acts at two levels\(emthe static level, involving the
463: type aspects of the structures involved, and the dynamic level,
464: involving the value and exception components. The dynamic aspect of
465: the reduction is realized by generating code that performs an ordinary
466: function application. The static aspect is performed at compile time,
467: producing a static representation of the result structure by
468: ``instantiating'' the body of the functor using the formal/actual
469: parameter binding environment.
470:
471: .NH 3
472: Naive copying
473: .LP
474: This static instantiation of functor bodies can be implemented in
475: several ways. The simplest and most direct is to perform a
476: straightforward nondestructive substitution, copying the
477: representation of the functor body in the process. This is roughly
478: the approach followed by Harper and Matthews in their implementations,
479: but the space consumed has been found to be excessive.
480: .NH 3
481: Functor application closures
482: .LP
483: A second
484: alternative initially employed in our compiler was to represent
485: structures formed by functor applications as closures, consisting of
486: the unmodified functor body structure together with the parameter
487: binding environment. This approach saves some copying, but it turns
488: out to be rather unwieldy because functor applications can appear
489: within the body of a functor definition, and consequently the actual
490: parameters may be expressions that themselves refer to other formal
491: parameter variables. For instance, consider
492: .DS
493: .ft CW
494: .vs 13
495: functor F(X:sigX) = bodyF
496:
497: functor G(Y:sigY) =
498: struct
499: structure S = F(Y)
500: ...
501: end
502:
503: structure B = G(A)
504: .vs 17
505: .ft R
506: .DE
507: In this example, the interpretation of \f5B.S\fP is given in terms of the
508: closure of \f5F(X)\fP, which is a pair $< bodyF , ~ roman "{" X |->
509: Y roman "}" > $. Since the
510: binding of \f5X\fP involves \f5Y\fP, this must be interpreted in the additional
511: context of the binding environment
512: $ roman "{" Y |-> A roman "}" $ produced by the
513: application \f5G(A)\fP. In general, a functor application closure may need
514: several layers of such contexts to be properly defined.
515:
516: Another drawback of this approach
517: is that it still performs the
518: copying that is inherent in the naive implementation
519: of signature matching, where a declaration such as
520: .DS
521: .ft CW
522: .vs 13
523: structure S': sig1 = S
524: .vs 17
525: .ft R
526: .DE
527: may cause a partial copy of \f5S\fP to be constructed and bound to \f5S'\fP.
528: .NH 3
529: Structure-sharing
530: .LP
531: The final approach is inspired, like Harper's prototype implementation,
532: by the semantic model developed by Harper, Milner, and Tofte[15].
533: We return to the straightforward idea of
534: actually performing the static reductions to obtain instantiated
535: copies of the functor body, but a structure-sharing representation is
536: used to minimize the amount of copying. In this representation, which
537: is similar in principle to the structure-sharing representation of
538: polytypes alluded to above, the statically ``interesting'' components
539: of each structure (i.e. types and substructures) are represented by
540: indices into an environment vector that is associated with the binding
541: table in another, simpler form of closure. The copying of structures that is
542: entailed by functor application and signature matching can then be
543: reduced to copying the closure objects and their associated
544: environment vectors, leaving the binding tables themselves unaffected.
545:
546: Each type or structure component also has an identifying ``name'',
547: which is basically just a unique number or time stamp. These names
548: serve a couple of purposes: representing sharing constraints, and
549: identifying two sorts of ``bound'' components. To capture sharing
550: specifications in signatures, components that are required to ``share''
551: (i.e. represent views of the same structure)
552: are given the same name. There are two forms of bound components:
553: those incorporated in functor parameter structures, and those
554: representing the components of a functor body that are created each
555: time the functor is applied. All other names are free, and represent
556: actual structures. The first sort of bound names are mapped to
557: components by the process of signature matching between formal and
558: actual functor parameters. The second sort are replaced by new unique
559: names during the static elaboration of functor applications.
560:
561: This third approach is currently under development and will eventually
562: replace the implementation based on functor application closures.
563: .NH
564: Translating abstract syntax into lambda calculus
565: .LP
566: The middle end of the compiler translates type-checked abstract
567: syntax trees into lambda-calculus trees. Because all of the environment
568: and scope manipulation has been done by the front end, and all of the
569: abstract-machine manipulation will be done by the back end, the
570: translator is simple, small, and fast.
571:
572: Though most optimization is purposely left for the back end, some
573: simplification
574: is done in the middle end. Formally recursive
575: .B fun
576: definitions are examined to see if they really contain references to
577: themselves;
578: if not they are replaced by (simpler) nonrecursive definitions.
579: The composition of structure-creation and structure-thinning is evaluated
580: at compile-time rather than run-time.
581: The ML equality predicate is a special
582: function that can be applied to any concrete data type (one built up from
583: primitive types and reference types using record and datatype constructors).
584: The algorithm for testing equality is a recursive tree traversal that varies
585: in its details for each type to which it is applied.
586: For each such occurrence, the translator builds an equality predicate
587: appropriate to the instance.
588:
589: Recent changes to Standard ML will require the use of an ``equality
590: interpreter'' which traverses arbitrary structures in the runtime system,
591: distinguishing certain kinds of cells (like
592: .B ref
593: cells) by special descriptor tags. The present implementation can still
594: be used as an optimized version in those cases where enough is known about
595: the type at compile time.
596: .NH 2
597: Translation of pattern-matching
598: .LP
599: One important and nontrivial job of the middle end
600: is to select optimal comparison
601: sequences for the compilation of pattern-matching. A \fImatch\fP in ML
602: is a sequence of pattern-expression pairs, called \fIrules\fP. When
603: a match is applied to an argument, the argument is matched against the
604: patterns, and the first rule with a matching pattern
605: is selected and its expression
606: is evaluated. A pattern is either a constant, which must match the argument
607: exactly; a variable, which matches any argument (and is bound to it for
608: the purposes of evaluating the expression); a tuple of patterns, which matches
609: a corresponding tuple argument whose components match the components of the
610: pattern-tuple; or a constructor applied to a pattern, which matches
611: an argument built using that constructor if the rest of the pattern matches.
612:
613: As an example, consider the case statement:
614: .DS
615: .ft CW
616: .vs 13
617: case a
618: of (false, nil) => nil
619: | (true, W) => W
620: | (false, cons(X, nil)) => cons(X, cons(X, nil))
621: | (false, cons(Y, Z)) => Z
622: .vs 17
623: .ft R
624: .DE
625: The argument (false, cons(4,nil)) matches the third pattern, while the
626: argument (true, cons(4,nil)) matches the second pattern.
627:
628: One could imagine a naive compilation of matches just by testing the
629: rules in turn as called for by the semantics. Our approach is to transform a
630: sequence of patterns into a decision tree[16].
631: Each internal node of the decision tree corresponds to a matching test and
632: each branch is labeled with one of the possible results of the matching test
633: and with a list of the patterns that remain potential candidates in that
634: case.
635: It is then straightforward to translate the decision tree into code for
636: pattern matching. During the construction of the decision tree it is also
637: easy to determine whether the pattern set is ``exhaustive,'' meaning that
638: every possible argument value matches at least one pattern; and whether
639: there are any ``redundant'' patterns that only match arguments covered
640: by previous rules. Nonexhaustive and redundant patterns result in warning
641: messages by the compiler.
642:
643: Our goal in constructing the decision tree is simply to minimize the total
644: number of test-nodes. This minimizes the size of the generated code and
645: also generally reduces the number of tests performed on value terms.
646: However, finding the decision tree with the minimum number of nodes is
647: an NP-complete problem[16];
648: so a set of efficient heuristics is used that in practice produces an optimal
649: decision tree in almost all cases.
650:
651: In the example above, testing the first component of the pair for truth
652: or falsity suffices to distinguish the second rule from the others;
653: then testing the second component to see whether it is \f5cons\fP or
654: \f5nil\fP distinguishes the first rule from the last two; one more test
655: suffices to separate the last two rules. Thus, in just two or three
656: tests, the appropriate rule can be selected; instead of two or three
657: tests \fIper rule\fP that the naive algorithm would use.
658:
659: The details of this algorithm were originally worked out by Marianne Baudinet
660: and have been implemented in our compiler by Trevor Jim.
661: .NH 2
662: The Lambda Language
663: .LP
664: The front end of the compiler translates ML source into
665: lambda calculus; the back end translates lambda-calculus into machine
666: code for the VAX or MC68020.
667: A significant advantage of having a very simple lambda-calculus
668: as the intermediate representation is that many compiler
669: optimizations can be cleanly described. This is the approach
670: successfully taken in the Rabbit[17]
671: and Orbit[18]
672: compilers for Scheme.
673:
674: The ``lambda language'' is simply an
675: ML datatype, as follows:
676: .DS
677: .ft CW
678: .vs 13
679: datatype lexp
680: = VAR of lvar
681: | FN of lvar * lexp
682: | FIX of lvar list * lexp list * lexp
683: | APP of lexp * lexp
684: | CON of con * lexp
685: | DECON of con * lexp
686: | SWITCH of lexp * (con*lexp) list * lexp Option
687: | RECORD of lexp list
688: | SELECT of int * lexp
689: | RAISE of lexp
690: | HANDLE of lexp * lexp
691: .vs 17
692: .ft R
693: .DE
694: The elements of the lambda language are variables (VAR),
695: abstraction (FN), simultaneous recursive definition (FIX),
696: application (APP), constructors (CON, DECON, and SWITCH),
697: tuples (RECORD and SELECT), and exception handling (HANDLE and
698: RAISE).
699: Exception names, and integer, real, and string literals,
700: are represented as constructors.
701:
702: There are no built-in library functions, at least from the point of
703: view of the compiler; instead, the library module is lambda-bound
704: at top level to some variable $v$, and functions from the
705: library are just components of the structure $v$. Certain functions
706: that are compiled in-line are represented as fields of a special structure
707: bound to a distinguished variable $v sub 0$.
708:
709: Constructor-expressions are explicitly represented in the lambda
710: language using $roman "CON" ( c, e) $ representing the application
711: of the constructor $c$ to the expression $e$, and $roman "DECON"
712: (c,e)$ representing the removal of $c$ from the constructed
713: expression $e$.
714: The lambda language could be simplified by
715: representing constructor-expressions as pairs of (tag,value),
716: and removing the CON and DECON operators. The advantage of using
717: CON and DECON is that the lambda language can be a typed lambda
718: calculus; the disadvantage is that the code generator is somewhat
719: more complicated. Since it's not clear why the low-level
720: representation needs to be typable, we may change the representation
721: of constructors in the lambda language.
722:
723: A structure resembles a record of components;
724: in the lambda language, it is treated exactly as a RECORD. There
725: are no special forms in the lambda language for structures and functors.
726: Functors are treated as functions from structures (RECORDs) to structures.
727: Actually, a structure definition is not just a record; it is an expression
728: that \fIevaluates\fP to a record.
729:
730: Structure $A$ may refer to an element of structure $B$; in the lambda language
731: this will mean that $B$ is a free variable of the expression representing
732: $A$. To keep things simple, it is important to eliminate all free variables
733: from an expression before code is generated for it; so the variable $B$ will
734: be lambda-bound at top level in the definition of $A$, and the runtime system
735: will be instructed to apply the resulting pseudo-functor to the structure
736: $B$ to initialize it.
737: This is a form of automatic,
738: compiler-controlled link-loading. For a link-loading scheme
739: it is extremely simple; our runtime structure-manager and link-loader
740: is less than a page of ML code.
741: .NH
742: Code generation
743: .LP
744: The back end of the compiler is organized as the composition of
745: functors; these functors are most naturally described starting at the end and working
746: toward the front. The last phase is the back-patching of jumps and
747: other relative addresses in a machine-language program. Relative
748: jump instructions on many machines are of different sizes depending on the distance
749: jumped, and several iterations of estimating jump sizes may be
750: required before a fixed point is found[19].
751: This is handled in a machine-independent way by the Backpatch
752: functor:
753: .DS
754: .ft CW
755: .vs 13
756: signature RelativeAddresses =
757: sig type JumpKind
758: val sizeJump : JumpKind -> int
759: val emitJump : (int -> unit) -> JumpKind -> unit
760: end
761: .ft R
762: .vs 17
763: .DE
764:
765: .DS
766: .ft CW
767: .vs 13
768: signature BackPatch =
769: sig
770: type Label
771: val newlabel : unit -> Label
772: type JumpKind
773: val emitbyte : int -> unit
774: val align : unit -> unit
775: val define : Label -> unit
776: val jump : JumpKind*Label -> unit
777: . . .
778: end
779:
780: functor Backpatch( Rel : RelativeAddresses ) : BackPatch
781: = struct
782: . . .
783: end
784: .vs 17
785: .ft R
786: .DE
787: For a given machine with a particular kind of relative address, one
788: builds a small structure explaining what size of relative address can
789: reach what distance, and how to emit code for that sort of relative
790: address. For example, on the Vax, a short conditional branch
791: takes 2 bytes, but a medium-size conditional
792: branch requires 6 bytes (a short conditional branch around a longer
793: unconditional jump), and a longer conditional jump takes 8 bytes.
794:
795: When the Backpatch functor is applied to a structure of type RelativeAddresses,
796: a new structure is created that understands how to
797: backpatch the code for a particular machine. A code generator for
798: that machine can make use of the \fIemit\fP and \fIlabel\fP primitives provided
799: by the specialized Backpatch structure.
800:
801: The signature VaxCode (not shown here)
802: provides an interface to a useful subset of the
803: Vax instruction set. The various instructions and addressing modes
804: are defined in this signature. There are two structures that
805: implement the VaxCode signature in different ways: one that
806: generates machine code when the instructions in the signature are
807: called for, and one that generates assembly code.
808: The VaxMcode structure matches the VaxCode signature, and
809: makes use of the Backpatch functor:
810: .DS
811: .ft CW
812: .vs 13
813: structure VaxMcode : VaxCode =
814: struct
815: structure R : RelativeAddresses =
816: struct
817: . . . functions to compile relative jumps, etc.
818: end
819: structure B = Backpatch(R)
820: datatype AddressMode = . . .
821: fun movl (src : AddressMode, dst: AddressMode) = . . .
822: end
823: .vs 17
824: .ft R
825: .DE
826: There is a peephole optimization module that operates on abstract Vax
827: instructions. It is implemented as a functor taking any VaxCode
828: structure into an ``optimized'' VaxCode structure:
829: .DS
830: .ft CW
831: .vs 13
832: functor Peephole ( V : VaxCode ) : VaxCode = struct . . . end
833: structure OptVaxMcode = Peephole(VaxMcode)
834: .vs 17
835: .ft R
836: .DE
837: If some other structure asks the module OptVaxMcode to produce
838: a particular instruction sequence, it may be that some optimized version of
839: the sequence will be generated instead.
840:
841: The code generator translates programs from
842: lambda language into machine code by
843: means of an abstract machine intermediate form. The abstract machine
844: is similar in spirit to Cardelli's[20].
845: The abstract machine interface is written as a signature in ML:
846: .DS
847: .ft CW
848: .vs 13
849: signature machine =
850: sig type Label
851: val select : int -> unit
852: val apply : unit -> unit
853: val tailrecur : int -> unit
854: val startrecord : int -> unit
855: val endrecord : unit -> unit
856: . . .
857: end;
858: .vs 17
859: .ft R
860: .DE
861: Each of these functions, when called, generates machine code for the
862: corresponding operation.
863:
864: There is a functor Vax that transforms a VaxCode structure into
865: a Machine structure:
866: .DS
867: .ft CW
868: .vs 13
869: functor Vax(C : VaxCode) : Machine =
870: struct
871: fun select j = C.movl(Displace(r0,4*j),Direct(r0))
872: .
873: .
874: .
875: end
876:
877: structure VaxM = Vax(OptVaxMcode)
878: structure VaxA = Vax(OptVaxAcode)
879: .vs 17
880: .ft R
881: .DE
882: This Vax functor can be applied to the structure OptVaxMcode, which will
883: result in an abstract machine that generates machine code for the
884: Vax; or to the structure OptVaxAcode, which generates assembly
885: language. We have a similar set of structures and functors that generate
886: code for the Motorola MC68020 architecture.
887:
888: Finally we can take this implementation of the abstract Machine, and
889: apply the Codegen functor to it:
890: .DS
891: .ft CW
892: .vs 13
893: functor Codegen(M : Machine) =
894: struct
895: fun codegen(APP(a,b)) = (codegen a; codegen b; M.apply())
896: | codegen(FN(v,b)) = . . .
897: \fI(The codegen function is not quite as simple as this, of course.)\fP
898: end
899:
900: structure VaxMCodegen = Codegen(VaxM)
901: structure M68MCodegen = Codegen(M68M)
902: .vs 17
903: .ft R
904: .DE
905: Now the function VaxMCodegen.codegen, when given a lambda expression,
906: generates optimized, backpatched machine code for the Vax.
907:
908: This arrangement of functors is quite satisfactory. However, the
909: details of the Machine signature might
910: be changed to make
911: it less like a stack machine. This might improve the generated
912: code, especially for architectures that are not naturally
913: stack-oriented. We are considering a re-implementation of the
914: code generator using continuation-passing style[17]
915: and Orbit[18].
916: .NH 2
917: Pattern-matching in code generation
918: .LP
919: Many
920: modern code generators are written in the form of tree-pattern matchers[21,\|22].
921: By writing the lambda-calculus
922: tree data structure as an ML datatype (with constructors),
923: the tree pattern matching can be directly specified as an ML function.
924: There is one pattern for each constructor, e.g.
925: .DS
926: .ft CW
927: .vs 13
928: | APP(f,a) => (gen(f); gen(a); machine.apply())
929: .vs 17
930: .ft R
931: .DE
932: but there are also cases that match certain ``idioms;'' like
933: .B let
934: expressions, which are represented as the application of a lambda-function:
935: .DS
936: .ft CW
937: .vs 13
938: | APP(FN(w,b), a) => \fIgenerate code for \fBlet \fIw\fB=\fIa\fB in \fIb\fP
939: .vs 17
940: .ft R
941: .DE
942: There are about a dozen simple cases that handle small patterns with just one
943: constructor, and a dozen more complicated cases that recognize idioms.
944:
945: Some of these cases are applicable in only certain situations. For example,
946: the pattern \f5APP(VAR\ w,\ a)\fP can be compiled without a closure only if
947: \fIw\fP refers to a ``known'' function. One might like to write the
948: clause for this case as:
949: .DS
950: .ft CW
951: .vs 13
952: | APP(VAR w, a) => if knownfunc(w) then applyknown(w,a) else ???
953: .vs 17
954: .ft R
955: .DE
956: The problem is that if $w$ is not a known function, then this pattern-match
957: is not useful, and the pattern \f5APP(f,a)\fP should be matched. By
958: the time the else clause is reached, it is impossible to transfer control
959: to the \f5APP(f,a)\fP clause.
960:
961: One solution to this problem is to attach boolean conditions to patterns,
962: as is done in Miranda[23]:
963: .DS
964: .ft CW
965: .vs 13
966: | APP(VAR w, a) when knownfunc(w) =>
967: .vs 17
968: .ft R
969: .DE
970: Though would add some ``syntactic sludge'' to the language, it is worth
971: considering as a future extension.
972: .NH 2
973: Flat versus linked environments
974: .LP
975: An
976: .I environment
977: is a mapping from some sort of
978: .I identifiers
979: to some sort of
980: .I bindings,
981: on which the fundamental operations are
982: .EQ
983: update ~~ ":" ~~ roman "Env" ~ times ~ roman "Ide" ~ times ~ roman "Bdg" ~~
984: -> ~~roman "Env"
985: .EN
986: .EQ
987: overlay ~~ ":" ~~ roman "Env" ~ times ~ roman "Env" ~~ -> ~~ roman "Env"
988: .EN
989: .EQ
990: access ~~ ":" ~~ roman "Env" ~ times ~ roman "Ide" ~~ -> ~~roman "Bdg"
991: .EN
992: The update function adds an identifier and binding to an
993: environment; the access function looks up an identifier; and the
994: overlay function
995: adds all of the bindings of one environment to
996: another. The overlay function might be used to implement the ML
997: .B open
998: primitive, for example.
999:
1000: Environments occur both in the compiler, where the identifiers are
1001: those of the source text, and the bindings are types and other
1002: information; and at runtime, in the form of function closures.
1003: A function closure, in implementations of lambda calculus, is a pair
1004: consisting of a function-code and the values to be associated with
1005: all of its free variables.
1006: Though these two kinds of environments are used in different ways,
1007: they share many of the same problems of implementation.
1008:
1009: We know of no data structure that implements environments with both a very
1010: fast \fIaccess\fP function and a very fast \fIoverlay\fP function.
1011: For compile-time environments,
1012: a fast \fIaccess\fP can be achieved by using a hash table; but
1013: then to overlay one hash table onto another takes time proportional
1014: to the size of the smaller table. A fast \fIoverlay\fP can be
1015: achieved by representing environments as trees of \fIoverlay\fP
1016: operations, but then \fIaccess\fP requires a tree search.
1017: In the compiled code, closures can be represented as flat
1018: or linked structures. A flat closure[2]
1019: is just a vector with one slot
1020: for each free variable, containing the value to which it is bound.
1021: A linked closure[17]
1022: has the binding of one free variable at the
1023: innermost level, along with a pointer to the closure for the
1024: enclosing scope.
1025: Flat closures have a fast \fIaccess\fP, but to build the vector takes
1026: time proportional to the number of free variables in the function.
1027: Linked closures can be built quickly: since the enclosing linked
1028: closure has already been built, just one \fIcons\fP operation is required.
1029: However, linked closures have a slower \fIaccess\fP function.
1030:
1031: The question of whether to make \fIaccess\fP or \fIoverlay\fP fast
1032: is a difficult one, since examples can be found to support either
1033: decision. Consequently, we have adopted a compromise: a mixed
1034: representation will be used, so that the time required for a typical
1035: sequence of \fIaccess\fP and \fIoverlay\fP operations will probably be
1036: smaller than if either the flat (hash-table) or linked (tree)
1037: representation were used.
1038:
1039: In the front end, environments are represented as linked lists of
1040: hash tables. The operation of \fBopen\fPing a structure just adds
1041: the (already-built) hash-table for that structure onto the list, but
1042: a typical \fIupdate\fP operation just adds a binding to an existing
1043: hash table.
1044: In the generated code, closures are represented as trees\(em
1045: a compromise between flat and linked closures. For each free variable
1046: in a closure, the back end heuristically decides whether to add
1047: another slot to the closure for this variable, or to access this
1048: variable through the (already existing) linked closure. The former
1049: is more expensive to build, but cheaper to use. When we have more
1050: experience with this compiler, we hope to measure the relative
1051: efficiencies of flat and linked closures in practice.
1052: .NH 2
1053: Data structures in the run-time system
1054: .LP
1055: The representations of ML structures in the compiled code are designed
1056: to be simple and general. We took care to avoid arbitrary restrictions
1057: on the size of the address space, or of individual objects. Except for
1058: .B ref
1059: cells, the graph of runtime objects is acyclic\(em
1060: even mutually recursive closures are represented without cycles.
1061:
1062: Because of ML's polymorphic type system, all values must be the same size.
1063: We take this size to be one 32-bit word (this discussion of runtime
1064: data structures is specific to implementations on 32-bit computers).
1065: Any value that is naturally represented in more than one word will
1066: be manipulated as a (one-word) pointer to a (multi-word) object;
1067: this is known as a
1068: .I boxed
1069: value. An
1070: .I unboxed
1071: value is one which fits in one word and is not a pointer.
1072: The garbage collector must be able to tell which words are boxed (pointers)
1073: and which words are not. We use the low-order bit of the word as the
1074: indicator. Since all of our pointers (on byte-addressable machines)
1075: point to word boundaries, the low-order bit of any pointer is zero.
1076: Unboxed values are represented with their low-order bits turned on.
1077: Unboxed values include constructor tags,
1078: one-character strings, and integers (the integer $k$ is
1079: represented as $2k+1$).
1080:
1081: All records in the runtime system contain an integral number of 32-bit words,
1082: and are prefaced by a descriptor describing their size and type. There are two
1083: types of records: those that contain pointers (and unboxed values), and
1084: those that contain no pointers. All ML tuples and closures are of the
1085: former variety (Figure 1);
1086: strings and machine-code fragments are of the latter.
1087: The fact that machine-code fragments contain no pointers is a consequence
1088: of the fact that the back-end code generator is never applied to any
1089: lambda-expression with free variables.
1090: .KF
1091: .PS
1092: boxht = .2; boxwid = .35; a = .4
1093: [down; A: box; B: box; C: box; D: box
1094: "desc" at A.c
1095: spline -> from B.c right a then up a/2 then right a+a
1096: "78" at C.c
1097: spline -> from D.c right a then down a/4 then right a
1098: line <- from B.w left a
1099: "Figure 1. A triple of two" "pointers and an integer" \
1100: at 2.2 between A.c and D.c
1101: ]
1102: move right 4*a
1103: [down; A: box; B: box; C: box; D: box; E: box
1104: "desc" at A.c
1105: line <- from B.w left a
1106: line <- from C.w left a
1107: line <- from D.w left a
1108: spline -> from B.c right a then up a/2 then right a+a
1109: spline -> from C.c right a then up a/4 then right a
1110: spline -> from D.c right a then down a/2 then right a+a
1111: "62" at E.c
1112: "Figure 2. Three mutually recursive" \
1113: "functions with one free variable" \
1114: at 2.2 between A.c and D.c
1115: ]
1116: .PE
1117: .KE
1118:
1119: There are several different representations used for constructors,
1120: just as in Cardelli's compiler[2].
1121: Constructors that carry values are usually represented as pairs of
1122: (tag, value). Constant constructors (link \fBnil\fP) are represented
1123: as small unboxed integers. Value-carrying constructors can be
1124: represented completely transparently if they carry an always-boxed value,
1125: and there are no other value-carrying constructors in the datatype
1126: (like \fBcons\fP), or if there is only one constructor in the datatype.
1127: Finally, \fBref\fP cells look like one-word records.
1128:
1129: Earlier ML compilers[20]
1130: represented mutually recursive functions as a set of closures that point
1131: to each other in a cyclic data structure. We wanted to avoid gratuitous
1132: circularity, because many garbage collection algorithms are more efficient
1133: on acyclic data structures[24].
1134: We represent mutually recursive functions with just one closure
1135: record that has
1136: several function-part entries (Figure 2). To represent function $i$,
1137: one just uses a pointer to the $i sup roman "th"$ field. If the
1138: $i sup roman "th"$ function wants to refer to the closure for the $j sup
1139: roman "th"$ function, it just adds $ j - i $ to the pointer value for
1140: its own closure. This creates no cycles of pointers; although there
1141: is an implicit cycle because each segment of machine code can refer
1142: to the machine's registers, which in turn point to the closure.
1143:
1144: Several machine-code fragments may be stored in the same record.
1145: Because the record may be moved by the garbage collector, references within
1146: the block must be by relative addresses. Many computers have PC-relative
1147: addressing modes to facilitate this; for other machines, a pointer to
1148: the currently-executing block would have to be kept in a register.
1149: A typical record contains all of the function and string-literal fragments
1150: for an entire ML structure (module). In order not to confuse the garbage
1151: collector, just before the start of each fragment within the record
1152: is a (relative) pointer back to the beginning of the record, where
1153: the record's descriptor may be found; and all fragments must begin
1154: on even byte addresses, so that pointers to fragments within the record
1155: won't look like unboxed values.
1156: .NH 2
1157: Fast consing
1158: .LP
1159: The operation of allocating and initializing a record\(em
1160: known in Lisp
1161: as \fIcons\fP\(em
1162: is a fundamental operation in ML. The creation of a tuple value,
1163: the application of a constructor, and the creation of a function-closure
1164: all rely on this operation. Our implementation strives to make this operation
1165: as fast as possible.
1166:
1167: We use a copying (and compacting) garbage collection algorithm. One
1168: consequence of this is that the free space available for storage
1169: allocation is a contiguous region of memory. We reserve a register
1170: to point at the lowest address in the free region. To allocate an
1171: $n$-word initialized record, the $n sup roman "th"$ word is stored
1172: first, followed by the other words and the descriptor. Then the
1173: free-space register is incremented by $n$ words.
1174:
1175: At some point the free space is exhausted. We arrange to have an
1176: inaccessible page of the address space immediately beyond the free
1177: space region. When there is an attempt to allocate a record that
1178: crosses into this page, a page fault occurs; and since the page is
1179: marked as inaccessible, the operating system transfers control to the
1180: ML runtime system instead of handling the page fault itself. Because
1181: the last word of a record is stored first, the creation of
1182: any record that crosses
1183: the boundary into the inaccessible region will fault at the beginning
1184: (where it is easy to patch things up and recover) rather than halfway
1185: through its initialization. (A special case is required for those
1186: records larger than a page; but these are rare and identifiable at
1187: compile-time.)
1188: Thus, the creation of an $n$-word record takes just $n$ stores
1189: (plus one for the descriptor) and an
1190: add instruction; the $n$ stores are required in any case to do the
1191: initialization. This is an extremely low-overhead
1192: .I cons
1193: operation.
1194:
1195: A fast
1196: .I cons
1197: is not helpful if garbage collection is slow. When physical memory
1198: is large, then the cost of copying garbage collection, amortized over
1199: the
1200: .I cons
1201: operations, can come to less than one instruction per \fIcons\fP $~~$[25].
1202: We are using a variant of generational garbage collection[24,\|26,\|27]
1203: that promises to be very fast even in moderate-size memories.
1204:
1205: In writing our compiler, we have aimed for clarity and
1206: straightforwardness; we have eschewed the coding tricks that enable
1207: programmers to avoid using dynamically allocated memory. As a
1208: result, our compiler probably \fIcons\fPes a lot more than other compilers;
1209: it is fortunate that we have made
1210: .I cons
1211: so fast.
1212: .NH 2
1213: Exception Handling
1214: .LP
1215: Exception names in Standard ML behave a bit like constructors, except that
1216: they are generatively (dynamically) defined. The statements
1217: .DS
1218: .ft CW
1219: .vs 13
1220: exception E : int and R : real
1221: \fIand\fP
1222: ... handle E with 0 => 10
1223: | i => 2*i
1224: || R with 0.0 => 10
1225: | r => 2*floor(r)
1226: .vs 17
1227: .ft R
1228: .DE
1229: are, if one considers $E$ and $R$ to be constructors,
1230: a bit like the (hypothetical) statements
1231: .DS
1232: .ft CW
1233: .vs 13
1234: datatype exception = . . . E of int | R of real . . .
1235: \fIand\fP
1236: ... handle E(0) => 10
1237: | E(i) => 2*i
1238: | R(0.0) => 10
1239: | R(r) => 2*floor(r)
1240: .vs 17
1241: .ft R
1242: .DE
1243: Generative data constructors cannot be given small integer tags like ordinary
1244: constructors. The tag for the constructor \f5E\fP must be constructed
1245: at run time. Its representation will be that of a
1246: .B ref
1247: cell: \f5ref("E")\fP. Any match applied to the exception type can
1248: compare the address of the ref cell against the tag of the exception
1249: object; and if the exception is propagated out of the user program into
1250: the bootstrap system, then the name of the exception can be determined
1251: (for debugging) by dereferencing the tag.
1252:
1253: The ML statement \f5raise e with v\fP is compiled into the lambda language
1254: as \f5RAISE(CON(e,v))\fP; and the handle statement applies a match
1255: (with exceptions as constructors) to the exception raised. That is,
1256: \f5HANDLE(e,h)\fP executes expression \f5e\fP; if any exception is raised
1257: in \f5e\fP, then the handler \f5h\fP (which is a
1258: \fImatch\fP as above) is applied to that exception.
1259: If \f5e\fP has type $t$, then \f5h\fP must have type $"exception" ^ -> ^ t$.
1260:
1261: The implementation of \f5HANDLE(e,h)\fP in the code generator is
1262: straightforward. An exception handler is pushed on the stack;
1263: expression \f5e\fP is executed; if no exception is raised, the
1264: exception handler is popped from the stack. An exception handler
1265: has two components: the address of the machine-code for the match
1266: \f5h\fP, and the address (on the stack) of the enclosing
1267: exception handler. Thus, entering the scope of a
1268: .B handle
1269: takes about two instructions, as does leaving its scope.
1270:
1271: To raise an exception \f5E(v)\fP, first the constructor-expression
1272: \f5E(v)\fP is evaluated and put into a register;
1273: then the stack pointer is reset to the position
1274: of the current exception handler; the current handler is removed; and
1275: control passes to the text address found in the current handler.
1276: The match \f5h\fP found at this address is thereby applied to the
1277: exception \f5E(v)\fP previously evaluated. Raising an exception
1278: therefore takes just three or four instructions, not including the
1279: match that may have to be done upon arrival at the handler to determine
1280: which exception was raised.
1281:
1282: The constructor view of exception
1283: names is not just a convenience in implementation.
1284: After some discussion in the Standard ML community, exceptions-as-constructors
1285: have been incorporated into the language.
1286: We no longer need
1287: an awkward notation (using \f5|\fP and \f5||\fP) for exception matches;
1288: and such things as re-raising an arbitrary expression are now possible:
1289: .DS
1290: .ft CW
1291: .vs 13
1292: handle e => (clean up; raise e) \fI(e is a variable of type ``exception'')\fP
1293: .vs 17
1294: .ft R
1295: .DE
1296: .NH
1297: The runtime system
1298: .LP
1299: The ML standard library is implemented as a single module in the runtime
1300: system. The library functions are mostly written in ML, with some
1301: references to primitive functions written in assembly language.
1302: All references to library functions are treated as references
1303: to fields of this structure. Thus, a typical expression might have
1304: only one free variable\(em
1305: the library structure itself. In order to ensure that the code generator
1306: is given only closed expressions, this variable is lambda-bound; the
1307: machine code resulting from this closed expression can then be treated as
1308: a function whose argument will be the standard library. Access to user-defined
1309: structures is handled similarly.
1310:
1311: This general plan is used both for the ``bootstrap'' system (in which
1312: the machine code for each
1313: structure is written to an external file), and
1314: the ``interactive'' system
1315: (in which the code for each structure or expression is
1316: put in memory and executed). In the interactive system, each expression
1317: when compiled is represented as a function whose argument is the
1318: current top-level environment, and whose result is the new binding.
1319: Thus, the interface between the compiler and the runtime system is
1320: very narrow and clean.
1321: .NH
1322: Conclusion
1323: .LP
1324: Standard ML is a complicated language. We manage the complexity by using
1325: a sequence of well-defined intermediate representations: tokens, abstract
1326: syntax, lambda-calculus, abstract machine, symbolic machine instructions.
1327: The datatypes and signatures of ML allow these interfaces to be cleanly
1328: specified, which is a great help.
1329:
1330: Lexical analysis\(em
1331: the translation from source programs to tokens\(em
1332: we make as simple as possible (760 lines). All complications of recognizing
1333: constructors and infix operators are handled in the parser, which
1334: has better access to the environment mechanisms.
1335:
1336: The translation from tokens to
1337: fully typed abstract syntax is the most complicated phase of our
1338: compiler (4500 lines).
1339: Because compile-time environments have some effect on parsing
1340: (constructors and infix operators), we merged the compilation
1341: of syntax, scopes, and types.
1342: This is where most of the complexity of the module features
1343: appear. But since structures and functors impinge on scopes and types
1344: in fundamental ways, we decided to build them into this phase from the
1345: beginning.
1346:
1347: Since the abstract syntax is so well-digested and complete, the next phase\(em
1348: translation into lambda-calculus\(em
1349: is relatively simple (1480 lines).
1350: The major task of this phase is the compilation of patterns into
1351: decision trees.
1352:
1353: A simple lambda-calculus representation of programs allows a simple
1354: and consistent code generator that can recognize idioms in lambda calculus
1355: and optimize them (750 lines).
1356: The lambda-calculus can also be useful for other kinds
1357: of analysis, like in-line function expansion.
1358: The back end needs to know very little about front-end data structures;
1359: thus, we found it simplest to have an environment manager for the back
1360: end that is completely separate from the front-end environment manager.
1361: Back-end environments map applied occurrences of variables
1362: in the lambda-calculus to their bindings, just as the front-end environment
1363: does that job for abstract syntax trees.
1364:
1365: The last two phases\(em
1366: translation from abstract machine instructions into
1367: symbolic (Vax or MC68020) instructions, and the translation of those
1368: into backpatched byte sequences\(em
1369: are the only machine-dependent phases.
1370: These phases have a largely straightforward structure (950 lines per machine).
1371: In the current
1372: implementation, our code generators do not make adequate use of registers,
1373: and we may redesign the abstract machine interface.
1374:
1375: Finally, the runtime system is kept very simple (450 lines of C,
1376: including the garbage collector; 300 lines
1377: of assembly language).
1378: As a statically-typed
1379: language, ML by its nature is oriented to compile-time analysis rather
1380: than complicated runtime systems; and we push this as far as possible.
1381: Our standard library is mostly implemented in ML
1382: (750 lines), and those parts
1383: implemented in assembly language are arranged to match a Standard ML
1384: signature. We pay particular attention to fast allocation of dynamic
1385: storage, since the features of ML (constructors, function closures) necessitate
1386: an efficient memory allocator and garbage collector.
1387:
1388: Our compiler is concise, efficient, and (we think) well-designed.
1389: It should prove to be a useful tool for the functional programming community.
1390: .sp 2
1391: .nr PS 10
1392: .nr VS 12
1393: .LP
1394: .]<
1395: .ds [F 1
1396: .]-
1397: .ds [A P. J. Landin
1398: .ds [U landin
1399: .ds [K ISWIM
1400: .ds [T The next 700 programming languages
1401: .ds [J Comm. ACM
1402: .ds [V 9
1403: .ds [N 3
1404: .ds [P 157-166
1405: .nr [P 1
1406: .ds [D 1966
1407: .nr [T 0
1408: .nr [A 0
1409: .nr [O 0
1410: .][ 1 journal-article
1411: .ds [F 2
1412: .]-
1413: .ds [A Luca Cardelli
1414: .ds [U cardelli
1415: .ds [T Compiling a functional language
1416: .ds [I ACM
1417: .ds [J 1984 Symp. on LISP and Functional Programming
1418: .ds [P 208-217
1419: .nr [P 1
1420: .ds [D 1984
1421: .nr [T 0
1422: .nr [A 0
1423: .nr [O 0
1424: .][ 1 journal-article
1425: .ds [F 3
1426: .]-
1427: .ds [K milner84
1428: .ds [K SML
1429: .ds [U milner
1430: .ds [A Robin Milner
1431: .ds [T A proposal for Standard ML
1432: .ds [I ACM
1433: .ds [J ACM Symposium on LISP and Functional Programming
1434: .ds [P 184-197
1435: .nr [P 1
1436: .ds [D 1984
1437: .nr [T 0
1438: .nr [A 0
1439: .nr [O 0
1440: .][ 1 journal-article
1441: .ds [F 4
1442: .]-
1443: .ds [K milner85
1444: .ds [K SML
1445: .ds [u milner
1446: .ds [A Robin Milner
1447: .ds [T The Standard ML Core Language
1448: .ds [J Polymorphism
1449: .ds [V 2
1450: .ds [N 2
1451: .ds [D October 1985
1452: .nr [T 0
1453: .nr [A 0
1454: .nr [O 0
1455: .][ 1 journal-article
1456: .ds [F 5
1457: .]-
1458: .ds [A David MacQueen
1459: .ds [T Modules for Standard ML
1460: .ds [I ACM
1461: .ds [J Proc. 1984 ACM Conf. on LISP and Functional Programming
1462: .ds [C Austin, Texas
1463: .ds [P 198-207
1464: .nr [P 1
1465: .ds [D 1984
1466: .nr [T 0
1467: .nr [A 0
1468: .nr [O 0
1469: .][ 1 journal-article
1470: .ds [F 6
1471: .]-
1472: .ds [A David MacQueen
1473: .ds [T Modules for Standard ML
1474: .ds [J Polymorphism
1475: .ds [V 2
1476: .ds [N 2
1477: .ds [D October 1985
1478: .nr [T 0
1479: .nr [A 0
1480: .nr [O 0
1481: .][ 1 journal-article
1482: .ds [F 7
1483: .]-
1484: .ds [A R. Burstall
1485: .as [A ", D. MacQueen
1486: .as [A ", and D. Sannella
1487: .ds [T Hope: an Experimental Applicative Language
1488: .ds [D 1980
1489: .ds [P 136-143
1490: .nr [P 1
1491: .ds [K burstall80
1492: .ds [C Stanford
1493: .ds [J Proceedings of the 1980 LISP Conference
1494: .nr [T 0
1495: .nr [A 0
1496: .nr [O 0
1497: .][ 1 journal-article
1498: .ds [F 8
1499: .]-
1500: .ds [A David C. J. Matthews
1501: .ds [T The Poly manual
1502: .ds [J SIGPLAN Notices
1503: .ds [D September 1985
1504: .nr [T 0
1505: .nr [A 0
1506: .nr [O 0
1507: .][ 1 journal-article
1508: .ds [F 9
1509: .]-
1510: .ds [A David C. J. Matthews
1511: .ds [T An implementation of Standard ML in Poly
1512: .ds [D May 1986
1513: .nr [T 0
1514: .nr [A 0
1515: .nr [O 0
1516: .][ 0 other
1517: .ds [F 10
1518: .]-
1519: .ds [A G. Cousineau
1520: .as [A ", P. L. Curien
1521: .as [A ", and M. Mauny
1522: .ds [T The Categorical Abstract Machine
1523: .ds [P 50-64
1524: .nr [P 1
1525: .ds [I Springer-Verlag
1526: .ds [B Functional Programming Languages and Computer Architecture, LNCS Vol 201
1527: .ds [E J. P. Jouannaud
1528: .ds [D 1985
1529: .nr [T 0
1530: .nr [A 0
1531: .nr [O 0
1532: .][ 3 article-in-book
1533: .ds [F 11
1534: .]-
1535: .ds [K milner78
1536: .ds [A Robin Milner
1537: .ds [U milner
1538: .ds [T A Theory of Type Polymorphism in Programming
1539: .ds [J J. CSS
1540: .ds [V 17
1541: .ds [P 348-375
1542: .nr [P 1
1543: .ds [D 1978
1544: .nr [T 0
1545: .nr [A 0
1546: .nr [O 0
1547: .][ 1 journal-article
1548: .ds [F 12
1549: .]-
1550: .ds [A Luca Cardelli
1551: .ds [U cardelli
1552: .ds [T Basic polymorphic typechecking
1553: .ds [J Polymorphism
1554: .ds [V 2
1555: .ds [N 1
1556: .ds [D January 1985
1557: .nr [T 0
1558: .nr [A 0
1559: .nr [O 0
1560: .][ 1 journal-article
1561: .ds [F 13
1562: .]-
1563: .ds [A R. S. Boyer
1564: .as [A " and J Moore
1565: .ds [U boyer
1566: .ds [T The sharing of structure in theorem-proving programs
1567: .ds [B Machine Intelligence 7
1568: .ds [E B. Meltzer
1569: .ds [E D. Michie
1570: .ds [I Edinburgh University Press
1571: .ds [D 1972
1572: .nr [T 0
1573: .nr [A 0
1574: .nr [O 0
1575: .][ 3 article-in-book
1576: .ds [F 14
1577: .]-
1578: .ds [A Luis Damas
1579: .ds [T Type Assignment in Programming Languages
1580: .ds [R PhD Thesis
1581: .ds [I Department of Computer Science, University of Edinburgh
1582: .ds [D 1985
1583: .nr [T 0
1584: .nr [A 0
1585: .nr [O 0
1586: .][ 4 tech-report
1587: .ds [F 15
1588: .]-
1589: .ds [A Robert Harper
1590: .as [A ", Robin Milner
1591: .as [A ", and Mads Tofte
1592: .ds [T A type discipline for program modules
1593: .ds [U harper
1594: .ds [I Univ. of Edinburgh
1595: .ds [R ECS-LFCS-87-28
1596: .ds [D 1987
1597: .nr [T 0
1598: .nr [A 0
1599: .nr [O 0
1600: .][ 4 tech-report
1601: .ds [F 16
1602: .]-
1603: .ds [A Marianne Baudinet
1604: .as [A " and David MacQueen
1605: .ds [T Tree Pattern Matching for ML
1606: .ds [D 1986
1607: .nr [T 0
1608: .nr [A 0
1609: .nr [O 0
1610: .][ 0 other
1611: .ds [F 17
1612: .]-
1613: .ds [K steele78
1614: .ds [A Guy L. Steele
1615: .ds [T Rabbit: a compiler for Scheme
1616: .ds [U steele
1617: .ds [I MIT
1618: .ds [R AI-TR-474
1619: .ds [D 1978
1620: .nr [T 0
1621: .nr [A 0
1622: .nr [O 0
1623: .][ 4 tech-report
1624: .ds [F 18
1625: .]-
1626: .ds [A D. Kranz
1627: .as [A ", R. Kelsey
1628: .as [A ", J. Rees
1629: .as [A ", P. Hudak
1630: .as [A ", J. Philbin
1631: .as [A ", and N. Adams
1632: .ds [T ORBIT: An optimizing compiler for Scheme
1633: .ds [P 219-233
1634: .nr [P 1
1635: .ds [D July 1986
1636: .ds [J Proc. Sigplan '86 Symp. on Compiler Construction
1637: .ds [V 21 (Sigplan Notices)
1638: .ds [N 7
1639: .nr [T 0
1640: .nr [A 0
1641: .nr [O 0
1642: .][ 1 journal-article
1643: .ds [F 19
1644: .]-
1645: .ds [A W. Wulf
1646: .as [A ", R. K. Johnsson
1647: .as [A ", C. B. Weinstock
1648: .as [A ", C. B. Hobbs
1649: .as [A ", and C. M. Geschke
1650: .ds [T Design of an Optimizing Compiler
1651: .ds [I Elsevier North-Holland
1652: .ds [C New York
1653: .ds [D 1975
1654: .ds [k wulf75
1655: .nr [T 0
1656: .nr [A 0
1657: .nr [O 0
1658: .][ 2 book
1659: .ds [F 20
1660: .]-
1661: .ds [A Luca Cardelli
1662: .ds [U cardelli
1663: .ds [T The functional abstract machine
1664: .ds [J Polymorphism
1665: .ds [V 1
1666: .ds [N 1
1667: .ds [D January 1983
1668: .nr [T 0
1669: .nr [A 0
1670: .nr [O 0
1671: .][ 1 journal-article
1672: .ds [F 21
1673: .]-
1674: .ds [A R. G. G. Cattell
1675: .ds [T Formalization and automatic derivation of code generators
1676: .ds [I Carnegie-Mellon University
1677: .ds [C Pittsburgh, PA
1678: .ds [D April 1978
1679: .ds [K cattell78
1680: .ds [R Ph.D. Thesis
1681: .nr [T 0
1682: .nr [A 0
1683: .nr [O 0
1684: .][ 4 tech-report
1685: .ds [F 22
1686: .]-
1687: .ds [K agt86
1688: .ds [K twig
1689: .ds [A A. V. Aho
1690: .as [A ", M. Ganapathi
1691: .as [A ", and S. W. K. Tjiang
1692: .ds [U aho
1693: .ds [T Code generation using tree matching and dynamic programming
1694: .ds [D 1986
1695: .nr [T 0
1696: .nr [A 0
1697: .nr [O 0
1698: .][ 0 other
1699: .ds [F 23
1700: .]-
1701: .ds [A D. A. Turner
1702: .ds [T Miranda: a non-strict functional language with polymorphic types
1703: .ds [I Springer-Verlag
1704: .ds [P 1-16
1705: .nr [P 1
1706: .ds [B Functional Programming Languages and Computer Architecture, LNCS Vol 201
1707: .ds [E J. P. Jouannaud
1708: .ds [D 1985
1709: .nr [T 0
1710: .nr [A 0
1711: .nr [O 0
1712: .][ 3 article-in-book
1713: .ds [F 24
1714: .]-
1715: .ds [K lieberman83
1716: .ds [U lieberman
1717: .ds [A Henry Lieberman
1718: .as [A " and Carl Hewitt
1719: .ds [T A real-time garbage collector based on the lifetimes of objects
1720: .ds [J Communications of the ACM
1721: .ds [I ACM
1722: .ds [V 23
1723: .ds [N 6
1724: .ds [P 419-429
1725: .nr [P 1
1726: .ds [D 1983
1727: .nr [T 0
1728: .nr [A 0
1729: .nr [O 0
1730: .][ 1 journal-article
1731: .ds [F 25
1732: .]-
1733: .ds [U appel
1734: .ds [A A. W. Appel
1735: .ds [T Garbage collection can be faster than stack allocation
1736: .ds [J Information Processing Letters
1737: .ds [V (to appear)
1738: .ds [D 1987
1739: .nr [T 0
1740: .nr [A 0
1741: .nr [O 0
1742: .][ 1 journal-article
1743: .ds [F 26
1744: .]-
1745: .ds [U moon
1746: .ds [K moon84
1747: .ds [A David A. Moon
1748: .ds [T Garbage collection in a large LISP system
1749: .ds [D 1984
1750: .ds [P 235-246
1751: .nr [P 1
1752: .ds [I ACM
1753: .ds [J ACM Symposium on LISP and Functional Programming
1754: .nr [T 0
1755: .nr [A 0
1756: .nr [O 0
1757: .][ 1 journal-article
1758: .ds [F 27
1759: .]-
1760: .ds [A David Ungar
1761: .ds [T Generation scavenging: a non-disruptive high performance storage
1762: .as [T " reclamation algorithm
1763: .ds [I ACM
1764: .ds [J SIGPLAN Notices (Proc. ACM SIGSOFT/SIGPLAN Software Eng. Symp. on Practical Software
1765: .as [J " Development Environments)
1766: .ds [V 19
1767: .ds [N 5
1768: .ds [D 1984
1769: .ds [P 157-167
1770: .nr [P 1
1771: .nr [T 0
1772: .nr [A 0
1773: .nr [O 0
1774: .][ 1 journal-article
1775: .]>
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.