Danny Yoo <firstname.lastname@example.org>
( (f x) )
... well, except this isn’t always true! In particular, we might override or shadow a binding by setting up a new one:
( (f x) ( (g) ( x objection!) ;; Overruled! x) ;; This is g's x, not f's. (g))
Within the body of f, the internal definition of g in f sets up a binding for x that blankets the one from f’s.
( (f x) ( (g x) ( (h x) ( x ;; within here, x refers to h's x. )) x ;; within here, x refers to g's x. ) x ;; within here, x refers to f's x. )
( (f x) ( (g x) (outer x) ;; can we make this refer to f's x? ) )
The following tutorial shows how we might poke lexical scoping portals into our programs. The techniques we’ll show here are those that cooperate with Racket’s compiler, so that we won’t impose any run-time penalty. The tutorial is meant to be self-contained, and expects moderate Racket knowledge (functions, modules, structures).
Please let me know if you have any suggestions or comments!
A common perception about Racket is that it’s an interpreter-based implementation, since it has a REPL and can dynamically evaluate programs. However, this perception is not quite correct.
Racket does use a compiler to translate programs into an internal bytecode format for optimization and ease of execution. However, Racket hides this compiler from most users because, under normal usage, Racket first quietly runs its compiler across a program, and then immediately executes the compiled in-memory bytecode. In fact, tools like raco make allow us to launch the compilation phase up front and save the bytecode to disk. If we use raco make, then program execution can pick up immediately from the on-disk bytecode.
One thing that makes Racket an interesting language is that it allows its users to hook expressions and functions into the compiler, so that these compile-time expressions get evaluated and called during the compilation phase. And unlike a purely textual pre-processor, these compile-time expressions can use the full power of Racket.
#lang racket ( ( racket/date ( dyoo/stardate))) ( ( "This program is being compiled at Stardate ~a\n" (date->stardate (current-date))))
If we run this from DrRacket, we may see somewhat more unusual output, because DrRacket can apply several program transformations that may cause "date-at-compile-time.rkt" to be compiled multiple times.
$ racket date-at-compile-time.rkt
This program is being compiled at Stardate 65741.5
This output supports the idea that, under normal circumstances, Racket interposes a compilation phase since it doesn’t see any stored bytecode on disk.
$ raco make date-at-compile-time.rkt
This program is being compiled at Stardate 65741.6
What is different is that bytecode has been written to disk, under a "compiled" subdirectory. Now let’s try running the program with the bytecode having just been saved to disk:
$ racket date-at-compile-time.rkt
It looks like it’s not doing anything. That’s because it’s not doing anything.
The point is that our Racket programs can express both run-time and compile-time computations, and they run in distinct phases.
One of the main applications of compile-time computation is to rewrite programs from one form to another. Racket’s compiler has a built-in expander that uses compile-time functions to rewrite a program. Racket’s expander is open to extension by letting us associate a compile-time function to a name; we call such compile-time functions “macros”. When the expander sees a name that’s associated to a macro, it applies that macro on a selected portion of the program and replaces that portion with the value returned from the macro. The expander continues expanding until the program only uses primitive “core” forms.
#lang racket ( ;; We can define a compile-time function: ;; ;; repeat-three: syntax -> syntax ( (repeat-three stx) ( stx () [( thing) ( ( thing thing thing))]))) ;; and we can hook this compile-time function up to the macro expander: ( blahblahblah repeat-three) ;; Example: (blahblahblah ( "blah"))
Racket uses an abstract syntax tree structure called a syntax object to represent programs and tools to manipulate these structured values. We can pattern-match and pull apart a syntax object with , and create a new syntax object with . The two forms cooperate with each other: when we pattern match a syntax-object with , it exposes the components of the pattern so that they be referenced by .
( (blahblahblah stx) ( stx () [( thing) ( thing thing thing)]))
; Turn on line/column counting for all ports: > ( #t)
; Read a syntax object:
> ( a-stx ( #f ( "(Racket is my favorite language on the Citadel)")))
; And inspect the individual syntax objects in the structure:
> ( ([piece ( a-stx)]) ( "~a at line ~a, column ~a, position ~a, span ~a\n" piece ( piece) ( piece) ( piece) ( piece)))
#<syntax:1:1 Racket> at line 1, column 1, position 2, span 6
#<syntax:1:8 is> at line 1, column 8, position 9, span 2
#<syntax:1:11 my> at line 1, column 11, position 12, span 2
#<syntax:1:14 favorite> at line 1, column 14, position 15, span 8
#<syntax:1:23 language> at line 1, column 23, position 24, span 8
#<syntax:1:32 on> at line 1, column 32, position 33, span 2
#<syntax:1:35 the> at line 1, column 35, position 36, span 3
#<syntax:1:39 Citadel> at line 1, column 39, position 40, span 7
More importantly, syntax objects hold lexical information, a key element that allows programs to bind and refer to variables. At the beginning of compilation, the program’s syntax object has little lexical information. As the expander walks through the syntax object, though, it can encounter forms that introduce new bindings. When the expander encounters , it enriches the lexical information of the syntax objects in scope.
( (cow x) ( "moooo?" x))
(probe-1 ( (cow x) (probe-2 ( "moooo?" x))))
First, let’s define the initial probe-1 macro:
> ( (probe-1 stx) ( stx () [( (d (f i) (p2 (op rand-1 rand-2)))) ( ( "at probe-1: ~a's binding is ~a\n" #'rand-2 ( #'rand-2)) #'(d (f i) (p2 (op rand-1 rand-2))))]))
It will tell us what the binding of x looks like in the body of the function; the expander does a top-down walk over the structure of the syntax object, so x shouldn’t report any lexical information at this point.
> ( (probe-2 stx) ( stx () [( (op rand-1 rand-2)) ( ( "at probe-2: ~a's binding is ~a\n" #'rand-2 ( #'rand-2)) #'(op rand-1 rand-2))]))
> (probe-1 ( (cow x) (probe-2 ( "moooo?" x))))
at probe-1: #<syntax:7:0 x>'s binding is #f
at probe-2: #<syntax:7:0 x>'s binding is lexical
As we can see, the expansion process enriches the syntax objects in the definition of cow; probe-2 shows us that, at the point where the expander reaches probe-2, x knows it is lexically bound.
Lexical information isn’t just stored in a symbolic syntax object like x, but rather it’s present in every syntax object. To demonstrate this, we can make a probe-3 that’s bit more disruptive to cow: it will take the "moooo?" out of the cow and put something else in its place.
We’ll use a combination of two tools to perform this surgery: and . lets us create syntax objects with arbitrary lexical information, and acts like a that allows us to inject syntax objects with . Just like , cooperates with to make it easy to construct new syntaxes.
> ( (probe-3 stx) ( stx () [( (op rand-1 rand-2)) ( ([new-rand-1 ( #'rand-1 '(string-append x x))]) #'(op new-rand-1 rand-2))]))
> ( (cow x) (probe-3 ( "moooo?" x)))
> (cow "blah")
The use of here takes the lexical information from "moooo?", and pushes it into a fresh syntax object that we construct from '(string-append x x).
And now our cow has been transmogrified into something... familiar, yet unnatural. How unfortunate.
It’s instructive to see what happens if we neglect to preserve the lexical information when we create syntax objects with . What happens if we just put #f in there?
> ( (probe-4 stx) ( stx () [( (op rand-1 rand-2)) ( ([new-rand-1 ( #f '(string-append x x))]) #'(op new-rand-1 rand-2))]))
> ( (cow x) (probe-4 ( "moooo?" x)))
compile: unbound identifier (and no #%app syntax
transformer is bound) at: string-append in: (string-append
Poor cow. What’s important to see is that '(string-append x x) has no inherent meaning: it depends on what we mean by and x, and that is precisely what lexical information is: it associates meaning to meaningless symbols.
Now that we’re finished probing cow, let’s go back and see how to define outer in the remaining space we have.
We now have a better idea of how macros and lexical scope works. Syntax objects accumulate lexical information through the actions of the expander. Now let’s break lexical scope.
To qualify: we’d like to define an outer form that lets us break lexical scoping in a controlled fashion: we’ll allow outer to poke holes along scope boundaries. Let’s say that the boundaries will be at the outskirts of a function definition. In fact, let’s make these boundaries explicit, by introducing our own def form. It’ll works similarly to .
#lang racket ( (def stx) ( stx () [( (name args ) body ) ( (name args ) body )]))
def gives us a function definition syntax that, at the moment, works like .
> (def (f x) ( x x))
> (f 3)
We want to amend def so that it stores the syntax object representing the function as a whole. We want this information to be accessible to other macros that expand when the body of the function is compiled. That way, when we’re in an outer, we might take that stored syntax object and use it as the source of lexical information in constructing a new syntax, as we did with probe-3.
We might use , except that if we do so, we interfere with how needs to be used in a definition context.
#lang racket ( racket/stxparam ;; syntax parameters are defined in racket/splicing) ;; racket/stxparam and ;; racket/splicing ;; Let's make a compile-time parameter called current-def that ;; remembers the innermost def that's currently being compiled. ( current-def #f) ( (def stx) ( stx () [( (name args ) body ) ( ([fun-stx stx]) ( ([current-def fun-stx]) ( (name args ) body )))]))
In production code, we’d probably use the replace-context function from the syntax/strip-context library instead.
( (outer stx) ( stx () [( id) ( ( current-def) ( id) stx)]))
> (def (f x) (def (g x) ( (outer x) x)) (g 4))
> (f 2)
( (bad-def stx) ( stx () [( (name args ) body ) ( ([fun-stx stx]) ( (name args ) ( ([current-def fun-stx]) body )))]))
then we end up placing the splicing-parameterize accidently in the scope of the . This wouldn’t be so bad, except for the case that, when Racket processes the , the expander enriches the syntax objects within the function body with lexical scoping information for its arguments.
In particular, it enriches the syntax object that we’re intending to assign to the current-def parameter later on. Ooops. So we need to take care to keep the outside of the function’s body, or else our pristine source of outside scope will get muddied.
This tutorial arose from my confusion on how macro expansion works. Special thanks to Robby Findler, Matthew Flatt, and Ryan Culpepper for helping resolve my mental confusion about lexical enrichment.