The Compiler-Parser library

The Compiler-Parser library handles lexical analysis, parsing and macro expansion. It relies only on the Compiler-Base library.

The Tokenize Module

This module provides an abstract class <tokenizer> supporting get-token, unget-token and a few other functions.

For implementations of this interface, see the Section called The Lexer Module and the Section called The Fragments Module.

The Source-Utilities Module

This module implements a number of subclasses of <source-location> (see the Section called The Source Module for details) that are used to represent the source of tokens during macro expansion.

There may be slightly more to this module than is apparent at first glance.

The Lexer Module

This module provides <lexer>, a subclass of <tokenizer> used to get tokens from a source record.

The Fragments Module

Fragments are the input to and output from macro expansion. According to the top-of-file comment:

The DRM says that:

The input to, and output from, a macro expansion is a fragment, which is a sequence of elementary fragments. An elementary fragment is one of the following:

  • A token: the output of the lexical grammar. ...

  • A bracketed fragment: balanced brackets ( (), [], or {} ) enclosing a fragment.

  • A macro-call fragment: a macro call.

  • A parsed fragment: a single unit that is not decomposable into its component tokens. It has been fully parsed by the phrase grammar. A parsed fragment is either an expression, a definition, or a local declaration.

So the parser needs to be able to produce fragments, the macro expander needs to be able to destructure and reconstruct fragments, and then the parser needs to be able to grovel the final results. This file implements all that.

This module also provides <fragment-tokenizer>, a subclass of <tokenizer> used to get tokens from a macro fragment.

The Parse-Tree Module

This module defines the tree representation used by the parser and the macro-expander. (It also includes the classes needed to represent the contents of a define macro form.)

The Parser Module

This modules takes input from a <tokenizer> and generates a parse tree. It looks like the main entry point is parse-source-record. There are other entry points which are called recursively by the macro expander; these parse a single production of Dylan's grammar.

This module defines the generic function process-top-level-form. It does not, however, define any methods. When the parser has found a top-level form, it calls process-top-level-form and allows other modules to take care of the details. This design may have implications for multi-threading and code reuse—it looks like the parser can only be used in one way by any given program.

The Macros Module

This module implements macro expansion as defined in the Dylan Reference Manual . It also provides <macro-definition> (see the Section called The Definitions Module).

Note that this module only handles those macros which expand according to the standard rules. More complicated macros are handled elsewhere by procedural expanders. To define a new procedural expander, register it using define-procedural-expander (a method defined in this module). We'll discuss procedural macros as implemented by d2c in some detail below.

Gwydion Dylan ™ Procedural Macros

In this section, I shall use "procedural macro" to mean "procedural macro as implemented by Gwydion Dylan Maintenance Project on d2c". This special definition contains an implicit caveat: procedural macros are not defined in the Dylan Reference Manual and are not standardized across Dylan ™ implementations -- use at your own risk. Also, discussion on the Gwydion Dylan Maintenance Project mailing list has noted that macros defined by the Dylan Reference Manual (hereinafter referred to as "plain macros") are "Turing-complete" (yes, just as machine language and C are Turing-complete), which means that Dylan Reference Manual macros can do whatever procedural macros can do; it just may require more effort and creativity on the user of the plain macro definition to do it. Procedural macros provide the macro writer alternatives to an aim, their lack does not disallow any desired aim. Those wishing to write Dylan Reference Manual -compliant Dylan ™ may safely skip this section.

An Introduction

First off, a procedural macro is a macro ... a special kind of macro that (explained simply) uses Dylan expressions evaluated before expansion time to build a macro-expansion. Then, like any plain macro, the expansion substitutes fragments matched by the template with the procedural result. Procedural macros can be more expressive than the macros defined in the Dylan Reference Manual , but this expressiveness comes at the cost of necessarily more work both in preparing to write the macro (the bits of support code) and in actually writing the macro itself. I will use the make-if procedural macro as defined in the Section called The Expanders Module to show how procedural macros work.

Second off, plain macros are straightforward (!) in their approach to source-code manipulation as compared to procedural macros. Plain macros match a pattern in the source code and then substitute that pattern with the (fixed) expansion:

source code (with a macro pattern) in
 => expanded source code out

Procedural macros give the user programmatic control over the expansion:

source code (with a macro pattern) in
 => generate appropriate expansion (programmatically, of course)
  => expanded source code out

A procedural macro writer must not only manage issues of writing plain macros, but must also manage the process of writing the expansion. This additional requirement means that writing code that creates a macro expansion is writing code that manipulates the Front-End Representation (see the Section called The Compiler-Front library), and, as such, is quite different than writing general-purpose code. Particularly, the code (method) that writes the expander must interact with the code generator engine and feed it things it understands: fragments (see the Section called The Fragments Module).

An Example

Section using make-if as an illustration TBD.

Roll Your Own, With Analysis

TBD: here we'll create avg from Paul Graham's On Lisp book as a regular macro (from Chris Double) and as a procedural macro, comparing and contrasting the two styles.