5 Language Extensions

5.1 When and Why

Extending a language is necessary to eliminate repeated programming patterns—often derisive called boilerplate—that cannot be hidden with the available abstraction mechanisms: functions, class inheritance, and so on. In addition to abstracting over repeated programming patterns, language extensions come with additional advantages, such as enforcing invariants that an implementation may exploit.

_f: addq %r7, %r7     cmpq %r7, $32     jle _f     retq   _g: movq %r7, $8     callq _f     movq %r8, %r7     callq _f     addq %r8, %r7     retq

int f (int x) {  while ( (x += x) <= 32 ) {}  return x; }   int g () {  int t = f(8);  return t + f(t); }

Figure 1: The Procedure Pattern

Language extensions add abstractions to a programming language that it does not already have. For example, in most assembly languages, there is the abstraction of the stack and the program counter, but there is not an abstraction of a procedure. In C, we add the language extension of procedure calls by integrating the many features of pushing arguments on the stack, jumping while pushing a return address, and extending the stack to allocate local variables. Although these features exist in assembly, their use does not constitute an abstraction, because assembly does not allow us to enforce the integrity of the procedure. For example, in C, it is not possible to goto a label in another procedure, while this is permissible inside of procedure-style assembly. Enforcing these abstractions is valuable because it allows us to implement the abstraction in ways that cannot be scalably done at the level of the pattern. For example, in C, we can perform exotic optimizations on our program because we know that the stack will always have the same structure at the start of every label, which is not the case in assembly. A fundamental aspect of language-oriented programming is identifying these intended abstractions and the invariants that enforce their integrity, then exploiting those invariants to produce a better program than you would have done without the abstraction.

button.onclick =  function () {   channel    .send("Where's my money?",     function (ans) {      box.text = ans; }); }

button.onclick =  async function () {   var ans = await channel    .send("Where's my money?");     box.text = ans; }

Figure 2: The Async Callback Pattern

It is typically the case that prior to the creation of a language extension, programmers that wish to use the concept employ a programming pattern, as mentioned above. For example, in JavaScript prior to ES7, it was typical for asynchronous functions to accept an explicit callback argument and extensive libraries and patterns built up to consume and produce these callbacks. In 2016, however, ES7 introduced the async and await keywords that automatically produce these callbacks from callback-less functions. Identifying an appropriate opportunity for language extension typically involves identifying a pattern like this in many programs.

As already mentioned, language extensions are distinct from existing abstractions. They can neither be implemented as functions nor via class inheritance or other abstraction mechanisms. Consider the asyncronous callback pattern, await is not a function that is definable inside of JavaScript. It is not a function that is definable inside of Racket either, because it consumes a syntactic block that contains a function call, rather than a value. It is, however, definable as a syntactix extension in Racket.

5.2 Two Simple Language Extensions

Don’t forget to add (require (for-syntax syntax/parse)) to your program.

A simple re-occurring programming pattern in programs in the timer pattern. In this pattern, you want to know how long an expression took to evaluate, so you capture the time before, and the time after, then display the difference. For example:

(let* ([before (current-inexact-milliseconds)]

[answer (factorial (fibonacci 10))]

[after (current-inexact-milliseconds)])

(printf "It took ~a ms to compute.\n" (- after before))

answer)

This code sequence is awkward, especially when the expression to be timed is embedded inside of a larger context, such as

(printf "The factorial of the tenth fibonacci is: ~a\n"

(factorial (fibonacci 10)))

because the surrounding context is not already suited to define the local variables to capture the time and the answer.

If you attempt to abstract this programming pattern into a function, as

(define (try-to-time-it computation)

(let* ([before (current-inexact-milliseconds)]

[answer computation]

[after (current-inexact-milliseconds)])

(printf "It took ~a ms to compute.\n" (- after before))

answer))

(printf "The factorial of the tenth fibonacci is: ~a\n"

(try-to-time-it (factorial (fibonacci 10))))

then you will find that your computer suddenly got a lot faster. This is because try-to-time-it is not executed until after the computation is finished evaluating. This means that to make an abstraction out of this timer, you must employ the thunk pattern:

(define (thunk-time-it do-computation)

(let* ([before (current-inexact-milliseconds)]

[answer (do-computation)]

[after (current-inexact-milliseconds)])

(printf "It took ~a ms to compute.\n" (- after before))

answer))

(printf "The factorial of the tenth fibonacci is: ~a\n"

(thunk-time-it (λ () (factorial (fibonacci 10)))))

This implementation of thunk-time-it fails to be a satisfying abstraction, because it exposes to the user that it is a function and that the user cannot simply "time the evaluation of expression", but must also explicitly cooperate with thunk-time-it and delay the evaluation of the computation.

Stop! Explain why (map (lambda (x) _) _) has the characteristic of a pattern.

Racket comes with an awesome abstraction for this programming pattern: for/list, a relatively recent addition to the language. Since it is familiar to you, it serves as a good case study for explaining how developers recognize the need for language extensions and how to create them via the familiar iterative refinement process.

Note Observers of languages such as Racket often describe them as “lacking syntax” because everything is indicated with parentheses. This observation is superficial at best, however, as the rules about parentheses suggest. These rules are the core of Racket’s syntax.

Stop! Rewrite the above macro so that it does not pair the loop identifier and its initialization expression. Show how to use it. Judge the Racket-y-ness of the code.

5.3 Evolving a Language Extension

One option to implement this extension is to write another macro that allows two lists at the same time. Another option is to have a single macro that allows an arbitrary number of lists. Clearly this second option is better than the first, because it both covers the first one and generalizes to potential other uses.

Stop! Equip the syntax pattern with annotations that ensure simple-for/list1 reports syntax errors in terms of itself not lambda or something else.

While map supports iterating through multiple lists, let’s suppose for the rest of this section that it did not.

This implementation is reasonably simple. Its downside is a drastic change to the performance of the language extension. Specifically, while a programmer may imagine a simple parallel traversal of two lists, the macro actually hides an extra linear traversal of the data and the creation of a large intermediate data structure. As every performance-aware functional programmer knows, however, allocating large intermediate data structures is a bad idea. Even if a deforesting compiler might be able to remove the traversals and constructions, it is inappropriate for macro authors to ignore such performance impacts when alternatives exist.

Our iteration macro is needlessly complicated with its re-use of the element name to bind the lists themselves. It only does this because we need to have an equal number of arguments to the iteration function as there are lists and we know that the number of element names is the same as the number of lists.

Just as a reminder, let’s carefully step through the elements of this revision.

First, this macro performs computations during macro expansion with the call to the function generate-temporaries.

Second, we are constructing syntax objects with syntax/#' that do not get returned from the macro. The arguments of generate-temporaries is a syntax object that represents the sequence of names. For each element of this list, the function will generate a new name.

Stop! Could we have used #'(a-list ...) instead?

Third, the use of #:with turns the new names into syntax-pattern variables that syntax/#' may substitute when it is instantiating the output template. As in the preceding chapter, the #:with form uses a list pattern on the left to deconstruct a list of syntax objects—new names—on the right.

Finally, we should ask if it is possible to use these new names, list-name, in the computation? The answer is no, and it is not because they are actually obscured as identifiers like temporary_list-name1924_abcd. Instead, it is because Racket systematically tracks the definition of variables and ensures that variables bound in different scopes do not shadow or capture variables defined in other scopes.

5.4 Another Evolution

Iterating through a data structure is a common programming pattern in all languages. A typical iteration employs a conditional and dispatches on expected values, computing one value for the '() case, another for cons, and maybe a different thing for other atomic values, such as numbers.

(define (sum a-tree)   (cond     [(null? a-tree) 0]     [(cons? a-tree)      (define elem (first a-tree))      (define more (rest a-tree))      (+ (sum elem) (sum more))]     [(number? a-tree) a-tree]     [else      (error "..., given: ~e" a-tree)]))

(define (in a-tree)   (cond     [(null? a-tree) '()]     [(cons? a-tree)      (define elem (first a-tree))      (define more (rest a-tree))      (append (in elem) (in more))]     [(number? a-tree) (list a-tree)]     [else      (error "..., given: ~e" a-tree)]))

Figure 3: Traversing a Data Structure

Figure 3 displays two such iteration function with similar function bodies. This conditional is tedious to get right. Programmers tend to forget the error case, fail to name pieces of the data structure and thus re-extract them, or make other small mistakes.

While a programmer could just use match for traversing this data structure, let’s suppose for the rest of this section that Racket did not come with such a fancy library.

We have been faced with such a situation

5.5 Language Extensions Must Behave Properly

The macros of this chapter aren’t proper language extensions yet. A proper extension is indistinguishable from a linguistic construct that comes with the core language. In particular, like such constructs, a proper extension does not reveal—especially not through error messages—that it is just programmer-defined syntax.

Suppose for a moment that you have learned enough to place this wonderful new macro into a library and to provide it from there to the numerous Racket programmers who can’t wait to use it to improve their code. When one of these coders doesn’t provide an initialization expression that evaluates to a list, the error message from the macro might not be as informative as one from contracted library function. That is, it may not blame the module that contains the actual bug.

Stop! Can you think of any other syntactic mistake that a programmer could make in conjunction with robust-for/list2? Do the compile-time error message make sense? Do they reveal that the construct is programmer-defined when compared to error messages from Racket’s core constructs?

5.6 Language Extensions Must Generate Properly Sized Code

Figure 4 displays two implementations of the time-it language extension side by side. At first glance the two look equivalent. Both The original one on the left and the new one on the right essentially perform the same computation steps: they grab the current time, run the computation, grab the current time again, compute how many milliseconds have passed, print this number, and finally return the result of the computation. The new definition is more compact than the old one, and thus you may wonder whether the new one is an acceptable implementation of the time-it extension.

original macro definition		alternative definition
(define-syntax (time-it stx)   (syntax-parse stx    [(_ computation)     #'(thunk-time-it         (λ () computation))]))   (define (thunk-time-it do-c)   (define before (cim))   (define answer (do-c))   (define after  (cim))   (define delta  (- after before))   (printf "time: ~a ms\n" delta)   answer)		(define-syntax (alt-time-it stx)   (syntax-parse stx     [(_ computation)      (let()        (define before (cim))        (define answer computation)        (define after  (cim))        (define delta (- after before))        (printf "time: ~a ms\n" delta)        answer)]))

To keep things short:

(define cim current-inexact-milliseconds)

Figure 4: Code Size Matters

Let’s compare the two implementations in detail. The original definition generates a function application whose function position refers to a run-time function definition and whose argument us a generated, null-ary procedure. The alternative definition in-lines the body of the function and thus does not need to create the procedure; it merely places the computation code at the right place.

Based on this detailed description, we can now describe the effects in simple terms. While time-it generates a small amount of code and shares most of the needed code via a run-time library, alt-time-it duplicates the generated code for measuring the time at every single use site of the macro. If this language extension is used a lot, the resulting Racket code may become large, and large source code may affect the compiler’s back-end, e.g., put pressure on a register allocator. The downside of time-it is that it allocates a closure for every call site, which may create pressure on the memory manager at run-time.

Although time-it is a small language extensions, we can still generalize from these observations. We observe two points. On one hand, the generation of code is the point of language extensions via macros. On the other hand, keeping this code small is a good idea, and like compiler writers, language extenders create auxiliary run-time functions to achieve this goal.

Stop! Doesn’t the multi-list variant of our simple-for/list extension generate large code blocks with recursive functions? Can this be simplified?

5.7 Macros in Libraries

Say you have developed your macros, protected them against potential compile-time and run-time mistakes, and reduced the size of generated syntax as much as possible in the given time. You are ready to create your first extension library. Figure 5 demonstrates how to accomplish this last step. You place the code into a module, both the macro definitions and the run-time definitions that your generated code needs; and if you need compile-time only definitions, place them into this module, too. Then you specify those identifiers that you wish to export in a provide specification. This may include macros, as the figure illustrates. Be a good citizen and document the functionality of the exported identifiers.

Stop! The figure uses a new syntax-class annotation. What do you think it means?

"extensions.rkt"

#lang racket

(provide

; (my-for/list ((~var elem-name id) (~var a-list expr))

;   (~var computation))

; evaluates computation with elem-name successively

; bound to the elements of a-list, which must evaluate to a list

my-for/list

; (time-it (~var computation expr))

; evaluates computation and returns the result

; —it measure the time it takes and prints the number of ms consumed

time-it)

; - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

(require (for-syntax syntax/parse))

; - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

(define-syntax (my-for/list stx)

(syntax-parse stx

[(_ ((~var elem-name id) a-list) computation)

#:declare a-list (expr/c #'list?)

#'(map (λ (elem-name) computation) a-list.c)]))

(define-syntax (time-it stx)

(syntax-parse stx

[(_ computation)

#'(thunk-time-it

(λ () computation))]))

(define (thunk-time-it do-c)

(define before (cim))

(define answer (do-c))

(define after  (cim))

(define delta  (- after before))

(printf "time: ~a ms\n" delta)

answer)

; - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

; local tests

Figure 5: An Extension Library

Figure 6 shows how to program with these extensions. It simply suffices to require the extension library. The use of a relative path name in the example relies on the assumption that the two files—"extensions.rkt" and "extensions-client.rkt"—exist in the same directory. With the macros imported, the rest of the module may use them as if they had always existed. The require specification is the only evidence that the forms used in the module are language extensions.

"extensions-client.rkt"

#lang racket

(require "extensions.rkt")

(require math)

; - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

(time-it

(my-for/list (p (build-list 10000 (λ (i) (+ 50000000000 i))))

`(,p ,(prime? p))))

Figure 6: An Extension Client

If you know how to create a collection with raco, you may create one for the extension library and use a collection-based path for importing the language extensions.

5.8 Lessons Learned

This chapter is about extending the Racket language with macros. Like an ordinary library function, a language extension doesn’t come about easily and deserves careful design. And also like a library function, once the extension exists, people will make use of it and the uses may even surprise the creator.

An Insight

Stop! Can you use define-syntax and syntax-parse to create a language extension that hides this pattern? It might be good to call it define-simple-macro.