1 Implementation of the type expander library🔗ℹ

This document describes the implementation of the type-expander library, using literate programming. For the library’s documentation, see the Type expander library document instead.

1.1 Introduction🔗ℹ

Extensible types would be a nice feature for typed/racket. Unlike require and provide, which come with define-require-syntax and define-provide-syntax, and unlike match, which comes with define-match-expander, typed/racket doesn’t provide a way to define type expanders. The type-expander library extends typed/racket with the ability to define type expanders, i.e. type-level macros.

The Some example type expanders section presents a small library of type expanders built upon the mechanism implemented here.

We redefine the forms :, define, lambda and so on to equivalents that support type expanders. Type expanders are defined via the define-type-expander macro. Ideally, this would be handled directly by typed/racket, which would directly expand uses of type expanders.

1.2 Expansion model for type expanders🔗ℹ

Combined, these features allow some form of "curried" application of type expanders: The F type expander could expand to an anonymous Λ type expander which captures the args₁ arguments. In the second expansion step, the Λ anonymous type expander would then consume the args₂ arguments, allowing F to effectively rewrite the two nested forms, instead of being constrained to the innermost form.

1.2.1 Comparison with TeX’s macro expansion model🔗ℹ

For long-time TeX or LaTeX users, this may raise some concerns. TeX programs are parsed as a stream of tokens. A TeX commands is a macro. When a TeX macro occurs in the stream of tokens, it takes its arguments by consuming a certain number of tokens following it. After consuming these arguments, a TeX macro may expand to another TeX macro, which in turn consumes more arguments. This feature is commonly used in TeX to implement macros which consume a variable number arguments: the macro will initially consume a single argument. Depending on the value of that argument, it will then expand to a macro taking n arguments, or another macro taking m arguments. This pattern, omnipresent in any sufficiently large TeX program, opens the door to an undesirable class of bugs: when a TeX macro invocation appears in the source code, it is not clear syntactically how many arguments it will eventually consume. An incorrect parameter value can easily cause it to consume more arguments than expected. This makes it possible for the macro to consume the end markers of surrounding environments, for example in the code:

the someMacro command may actually expect three arguments, in which case it will consume the \end token, but leave the {someEnvironment} token in the stream. This will result in a badly broken TeX program, which will most likely throw an error complaining that the environment \begin{someEnvironment} is not properly closed. The error may however occur in a completely different location, and may easily cause a cascade of errors (the missing \end{someEnvironment} may cause later TeX commands to be interpreted in a different way, causing them to misinterpret their arguments, which in turn may cause further errors. The end result is a series of mysterious error messages somewhat unrelated to the initial problem.

This problem with TeX macros can be summed up as follows: the number of tokens following a TeX macro invocation that will be consumed by the macro is unbounded, and cannot be easily guessed by looking at the raw source code, despite the presence of programmer-friendly looking syntactic hints, like wrapping arguments with {…}.

1.2.2 Interactions between type expanders and scopes🔗ℹ

Our expansion model for type expanders therefore allows a type expander to escape the scope in which it was defined before it is actually expanded. For example, the following type:

(Let ([A Number])

((Let ([F (Λ (self T)

#`(Pairof #,(datum->syntax #'self 'A)

T))])

(Let ([A String])

F))

A))

first expands to:

(F

A)

and then expands to:

(Pairof String A)

and finally expands to:

(Pairof String A)

Effectively, F captures the scope where its name appears (inside all three Let forms), but is expanded in a different context (outside of the two innermost Let forms).

Using Matthew Flatt’s notation to indicate the scopes present on an identifier, we can more explicitly show the expansion steps:

(Let ([A Number])

((Let ([F (Λ (self T)

#`(Pairof #,(datum->syntax #'self 'A)

T))])

(Let ([A String])

F))

A))

The first Let form annotates the identifier it binds with a fresh scope, numbered 1 here, and adds this scope to all identifiers within its body. It stores the binding in the (tl-redirections) binding table, as shown by the comment above the code

;A¹ := Number

((Let¹ ([F¹ (Λ¹ (self¹ T¹)

#`(Pairof¹ #,(datum->syntax¹ #'self¹ 'A¹)

T¹))])

(Let¹ ([A¹ String¹])

F¹))

A¹)

The second Let form then binds the F identifier, adding a fresh scope as before:

;A¹ := Number

;F¹² := (Λ¹ (self¹ T¹)

; #`(Pairof¹ #,(datum->syntax¹ #'self¹ 'A¹)

; T¹))

((Let¹² ([A¹² String¹²])

F¹²)

A¹)

The third Let form then binds A within its body, leaving the outer A unchanged:

;A¹ := Number

;F¹² := (Λ¹ (self¹ T¹)

; #`(Pairof¹ #,(datum->syntax¹ #'self¹ 'A¹)

; T¹))

;A¹²³ := String¹²

(F¹²³

A¹)

The F¹²³ macro is then expanded, passing as an argument the syntax object #'(F¹²³ A¹). A fresh scope is added to the identifiers generated by the macro, in order to enforce macro hygiene. The A¹ identifier is passed as an input to the macro, so it is left unchanged, and A¹²³ is derived from F¹²³, via datum->syntax, and therefore has the same scopes (F¹²³ is also a macro input, so it is not tagged with the fresh scope). The Pairof¹ identifier, generated by the macro, is however flagged with the fresh scope 4. The result of the application of F to this syntax object is:

;A¹ := Number

;F¹² := (Λ¹ (self¹ T¹)

; #`(Pairof¹ #,(datum->syntax¹ #'self¹ 'A¹)

; T¹))

;A¹²³ := String¹²

(Pairof¹⁴ A¹²³ A¹)

The Pairof¹⁴ type is resolved to the primitive type constructor Pairof:

;A¹ := Number

;F¹² := (Λ¹ (self¹ T¹)

; #`(Pairof¹ #,(datum->syntax¹ #'self¹ 'A¹)

; T¹))

;A¹²³ := String¹²

(Pairof A¹²³ A¹)

The type A¹²³ is then resolved to String¹², which in turn is resolved to the String built-in type:

;A¹ := Number

;F¹² := (Λ¹ (self¹ T¹)

; #`(Pairof¹ #,(datum->syntax¹ #'self¹ 'A¹)

; T¹))

;A¹²³ := String¹²

(Pairof String A¹)

And the type A¹ is resolved to Number:

;A¹ := Number

;F¹² := (Λ¹ (self¹ T¹)

; #`(Pairof¹ #,(datum->syntax¹ #'self¹ 'A¹)

; T¹))

;A¹²³ := String¹²

(Pairof String Number)

The syntax-local-value function does not support querying the transformer binding of identifiers outside of the lexical scope in which they are bound. In our case, however, we need to access the transformer binding of F¹²³ outside of the scope of the Let binding it, and similarly for A¹²³.

1.3 The prop:type-expander structure type property🔗ℹ

Type expanders are identified by the prop:type-expander structure type property. Structure type properties allow the same identifier to act as a rename transformer, a match expander and a type expander, for example. Such an identifier would have to implement the prop:rename-transformer, prop:match-expander and prop:type-expander properties, respectively.

The value of the prop:type-expander property should either be a transformer procedure of one or two arguments which will be called when expanding the type, or the index of a field containing such a procedure.

If the value is a field index, it should be within bounds. The make-struct-field-accessor function performs this check, and also returns an accessor. The accessor expects an instance of the struct, and returns the field’s value.

The expander procedure will take one argument: the piece of syntax corresponding to the use of the expander. If the property’s value is a procedure, we therefore check that its arity includes 1.

In the first case, when the property value is a field index, we return an accessor function. The accessor function expects a struct instance, performs some checks and returns the actual type expander procedure.

When the property’s value is directly a type expander procedure, we follow the same convention. We therefore return a function which, given a struct instance, returns the type expander procedure (ignoring the _ argument).

When the value of the prop:type-expander property is neither a positive field index nor a procedure, an error is raised:

1.3.1 The type-expander struct🔗ℹ

We make a simple struct that implements prop:type-expander and nothing else. It has a single field, expander-proc, which contains the type expander transformer procedure.

1.4 Associating type expanders to identifiers🔗ℹ

1.4.1 The type-expander syntax class🔗ℹ

We also define a syntax class which matches types. Since types can bear many complex cases, and can call type expanders which may accept arbitrary syntax, we simply define the type syntax class as expr. Invalid syntax will be eventually caught while expanding the type, and doing a thorough check before any processing would only make the type expander slower, with little actual benefits. The type syntax class is however used in syntax patterns as a form of documentation, to clarify the distinction between types and run-time or compile-time expressions.

Finally, we define a convenience syntax class which expands the matched type:

1.4.2 Calling type expanders🔗ℹ

The apply-type-expander function applies the syntax expander transformer function associated to type-expander-id. It passes stx as the single argument to the transformer function. Usually, stx will be the syntax used to call the type expander, like #'(te arg ...) or just #'te if the type expander is not in the first position of a form.

The identifier type-expander-id should be bound to a type expander, in one of the three possible ways described above.

The apply-type-expander function checks that its type-expander-id argument is indeed a type expander before attempting to apply it:

1.4.3 Associating type expanders to already existing identifiers🔗ℹ

As explained above, existing identifiers which are provided by other libraries can be “patched” so that they behave like type expanders, using a global table associating existing identifiers to the corresponding expander code:

1.4.4 Defining new type expanders🔗ℹ

The define-type-expander macro binds name to a type expander which uses (λ (arg) . body) as the transformer procedure. To achieve this, we create a transformer binding (with define-syntax), from name to an instance of the type-expander structure.

1.4.5 Locally binding type expanders🔗ℹ

Some features of the type expander need to locally bind new type expanders:

• The (Let. (([id expr] …) . body)) special form binds the identifiers id … to the type expanders expr … in its body.

• When expanding the body of a (∀ (Tᵢ …) body) form, the Tᵢ bound by the ∀ may shadow some type expanders with the same name. If the ∀ form is directly applied to arguments, each Tᵢ is instead bound to the corresponding argument.

• When expanding the body of a (Rec T body) form, the T bound by the Rec may shadow a type expander with the same name.

We use with-bindings (defined in another file) to achieve this. The code

(with-bindings [bound-ids transformer-values]

rebind-stx

transformer-body)

evaluates transformer-body in the transformer environment. It creates a fresh scope, which it applies to the bound-ids and the rebind-stx. It associates each modified bound-id with the corresponding transformer-value in the (tl-redirections) binding table. The with-bindings form does not mutate the syntax objects, instead it shadows the syntax pattern variables mentioned in bound-ids and rebind-stx with versions pointing to the same syntax objects, but with the fresh scope flipped on them.

The code

(with-rec-bindings [bound-ids generate-transformer-values rhs]

rebind-stx

transformer-body)

works in the same way, but it also flips the fresh scope on each element of rhs. The generate-transformer-values is expected to be a transformer expression which, given an element of rhs with the flipped scope, produces the transformer value to bind to the corresponding bound-id.

It is not practical in our case to use the first solution involving define-syntax, as the type expander may be called while expanding an expression (e.g. ann). The next two solutions assume that syntax-local-value will be called in a well-scoped fashion (in the sense of the official expander): in the second solution, syntax-local-value must be called by expansion-time code located within the scope of the let-syntax form, and in the third solution, syntax-local-value must be called within the dynamic extent of local-expand. The last solution works, but requires that the user explicitly passes the appropriate internal definition context.

The second and third solutions cannot be applied in our case, because type expanders can be expanded outside of the scope in which they were defined and used, as explained the Interactions between type expanders and scopes section.

The current version of the type expander does not support a reliable alternative to syntax-local-value which takes into account local binding forms for types (Let, ∀ and Rec), but one could be implemented, either by using some tricks to make the first solution work, or by providing an equivalent to syntax-local-value which consults the (tl-redirections) binding table.

1.5 Expanding types🔗ℹ

The expand-type function fully expands the type stx. As explained in Locally binding type expanders, shadowing would be better handled using scopes. The expand-type function starts by defining some syntax classes, then parses stx, which can fall in many different cases.

1.5.1 Cases handled by expand-type🔗ℹ

The cases described below which expand a use of a type expander re-expand the result, by calling expand-type once more. This process is repeated until no more expansion can be performed. This allows type expanders to produce calls to other type expanders, exactly like macros can produce calls to other macros.

We distinguish the expansion of types which will appear as the first element of their parent form from types which will appear in other places. When the applicable? argument to expand-type is #true, it indicates that the current type, once expanded, will occur as the first element of its enclosing form. If the expanded type is the name of a type expander, or a ∀ or Λ form, it will be directly applied to the given arguments by the type expander. When applicable? is #false, it indicates that the current type, once expanded, will not appear as the first element of its enclosing form (it will appear in another position, or it is at the top of the syntax tree representing the type).

When applicable? is #true, if the type is the name of a type expander, or a ∀ or Λ form, it is not expanded immediately. Instead, the outer form will expand it with the arguments. Otherwise, these forms are expanded without arguments, like identifier macros would be.

1.5.2 Applying type expanders🔗ℹ

When a type expander is found in a non-applicable position, it is called, passing the identifier itself to the expander. An identifier macro would be called in the same way.

When a type expander is found in an applicable position, it is returned without modification, so that the containing application form may expand it with arguments. When the expander e appears as (e . args), it is applicable. It is also applicable when it appears as ((Let (bindings…) e) . args), for example, because Let propagates its applicable? status.

When a form contains a type expander in its first element, the type expander is called. The result is re-expanded, so that a type expander can expand to a use of another type expander.

When a form of the shape (f . args) is encountered, and the f element is not a type expander, the f form is expanded, and the whole form (with f replaced by its expansion) is expanded a second time. The applicable? parameter is set to #true while expanding f, so that if f produces a type expander (e.g. f has the shape (Let (…) some-type-expander)), the type expander can be applied to the args arguments.

1.5.2.1 Polymorphic types with ∀🔗ℹ

When the ∀ or All special forms from typed/racket are used, the bound type variables may shadow some type expanders. The type expanders used in the body T which have the same identifier as a bound variable will be affected by this (they will not act as a type-expander anymore). The body of the ∀ or All form is expanded with the modified environment. The result is wrapped again with (∀ (TVar …) expanded-T), in order to conserve the behaviour from typed/racket’s ∀.

Where «shadowed» is used to bind the type variables tvarᵢ to (No-Expand tvarᵢ), so that their occurrences are left intact by the type expander:

When a ∀ polymorphic type is found in an applicable position, it is returned without modification, so that the containing application form may expand it, binding the type parameters to their effective arguments.

When a ∀ polymorphic type is immediately applied to arguments, the type expander attempts to bind the type parameters to the effective arguments. It currently lacks any support for types under ellipses, and therefore that case is currently handled by the «expand-type-case-app-fallback» case described later.

If the given number of arguments does not match the expected number of arguments, an error is raised immediately:

1.5.2.2 Recursive types with Rec🔗ℹ

Similarly, the Rec special form will cause the bound variable R to shadow type expanders with the same name, within the extent of the body T. The result is wrapped again with (Rec R expanded-T), in order to conserve the behaviour from typed/racket’s Rec.

1.5.2.3 Local bindings with Let and Letrec🔗ℹ

The Let special form binds the given identifiers to the corresponding type expanders. We use with-bindings, as explained above in (part ("(lib type-expander/type-expander.hl.rkt)" "shadow")), to bind the Vᵢ … identifiers to their corresponding Eᵢ while expanding T.

The Letrec special form behaves in a similar way, but uses with-rec-bindings, so that the right-hand-side expressions Eᵢ appear to be within the scope of all the Vᵢ bindings.

1.5.2.4 Anonymous types with Λ🔗ℹ

When an anonymous type expander appears as the first element of its enclosing form, it is applied to the given arguments. We use the trampoline-eval function defined in another file, which evaluates the given quoted transformer expression, while limiting the issues related to scopes. The “official” eval function from racket/base removes one of the module scopes which are normally present on the expression to evaluate. In our case, we are evaluating an anonymous type expander, i.e. a transformer function. When using eval, identifiers generated by the transformer function may not have the expected bindings. The alternative trampoline-eval seems to solve this problem.

The auto-syntax-case form is used, so that an anonymous type expander (Λ (_ a b) …) can either use a and b as pattern variables in quoted syntax objects, or as regular values (i.e syntax->datum is automatically applied on the syntax pattern variables when they are used outside of syntax templates, instead of throwing an error).

This case works by locally binding a fresh identifier tmp to a type expander, and then applying that type expander. It would also be possible to immediately invoke the type expander function.

When a Λ anonymous type expander appears on its own, in a non-applicable position, it is expanded like an identifier macro would be.

This case is implemented like the «expand-type-case-app-Λ» case, i.e. by locally binding a fresh identifier tmp to a type expander, and then applying that type expander. The difference is that in the identifier macro case, the syntax object given as an argument to the type expander contains only the generated tmp identifier. This allows the type expander to easily recognise the identifier macro case, where the whole syntax form is an identifier, from regular applications, where the whole syntax form is a syntax pair. The whole original syntax is attached consed onto a syntax property named 'original-Λ-syntax, in (unlikely) case the type expander needs to access the original Λ syntax used to call it (this is an experimental feature, and may change without notice in later versions).

When a Λ anonymous type expander appears on its own, in an applicable position, it is returned without modification, so that the containing application form may expand it with arguments (instead of expanding it like an identifier macro would be).

1.5.2.5 Preventing the expansion of types with No-Expand🔗ℹ

The No-Expand special form prevents the type expander from re-expanding the result. This is useful for example for the implementation of the fancy quote expander, which relies on the built-in quote expander. It is also used to implement shadowing: type variables bound by ∀ in non-applicable positions and type variables bound by Rec are re-bound to type expanders returning (No-Expand original-tvar).

1.5.2.6 The overloaded : identifier🔗ℹ

This case handles the colon identifiers : (overloaded by this library) and : (provided by typed/racket). Wherever the new overloaded : identifier appears in a type, we want to convert it back to the original : from typed/racket. The goal is that a type of the form (→ Any Boolean : Integer), using the new :, will get translated to (→ Any Boolean : Integer), using the old : so that it gets properly interpreted by typed/racket’s parser.

1.5.2.7 Last resort cases: leaving the type unchanged🔗ℹ

If the type expression to expand was not matched by any of the above cases, then it can still be an application of a polymorphic type T. The arguments TArg … can contain uses of type expanders. We therefore expand each separately, and combine the results.

As a last resort, we consider that the type T (which would most likely be an identifier) is either a built-in type provided by typed/racket, or a user-declared type introduced by define-type. In both cases, we just leave the type as-is.

1.5.3 Debugging type expanders🔗ℹ

In order to facilitate writing type expanders, it is possible to print the inputs, steps and outputs of the expander using (debug-type-expander #t), which sets the value of debug-type-expander?. This can then be undone using (debug-type-expander #f).

For better readability, each level of recursion indents the debugging information:

Before expanding a term, it is printed:

Once the term has been expanded, the original term and the expanded term are printed:

Finally, each rule for the type expander is wrapped with the rule macro, which prints the name of the rule, and returns a pair containing the result and the rule’s name, so that the debugging information indicates the rule applied at each step.

1.6 Overloading typed/racket forms🔗ℹ

Throughout this section, we provide alternative definitions of the typed/racket forms :, lambda, define, struct, ann, inst… . We write these definitions with syntax-parse, using the syntax classes defined in section syntax classes.

Most of the time, we will use the experimental template macro from syntax/parse/experimental/template which allows more concise code than the usual #'() and #`().

1.6.1 syntax classes🔗ℹ

The syntax classes from typed-racket/base-env/annotate-classes match against the : literal. Since we provide a new definition for it, these syntax classes do not match code using our definition of :. We therefore cannot use the original implementations of curried-formals and lambda-formals, and instead have to roll out our own versions.

We take that as an opportunity to expand the types directly from the syntax classes using #:with, instead of doing that inside the macros that use them.

The colon syntax class records the identifier it matches as a "disappeared use", which means that DrRacket will draw an arrow from the library importing it (either typed/racket or type-expander) to the identifier. Unfortunately, this effect is not (yet) undone by syntax/parse’s backtracking. See https://groups.google.com/forum/#!topic/racket-users/Nc1klmsj9ag for more details about this.