Fixpoint

Like the last one, the code involved here will be pretty simple, but it'll need a bit more context loaded up. Or possibly a lot more. So do some warmup stretches if needed - safety first, you know - and let's get to it.

The define keyword in Scheme is a deceptively simple thing. Its purpose is clear enough: to bind (associate) a name to a given value within some region of a program. But how exactly it does that can vary quite a bit. And while it's indeed quite useful and frequently used, from a theory and implementation standpoint it tends to look more like a concession to programming practicalities than a central part of the language. With functional programming in general and Scheme in particular planting its roots in Church's lambda calculus model of computation, the essential name-binding construct is, unsurprisingly enough, the λ-expression. Let's recap how that works:

(lambda (x) (+ (* a x) b))

That's an expression which evaluates to a procedure of one argument, for which it introduces the name x; the procedure computes the familiar family of linear functions of one variable. That is, it's like saying f(x) = ax+b, but without having to declare that name f ; the only name being defined here is its parameter x. The procedure itself is treated as a first class value just like the numbers presumably stored in a, x, and b, and thus can always be bound to a name if needed - such as by passing it in to some other lambda.

A distinction we can now observe is between bound and free variable references. With respect to the above lambda expression, the x in (* a x) is considered bound, because it refers to a binding established within that expression. By contrast, the references to a and b are considered free, because they "escape" the confines of that expression and thus must be supplied by the wider environment.⁽ⁱ⁾ Note that bound versus free is not an inherent property of a particular variable use, but a matter of perspective; referring to a variable that has no binding visible at all at its point of use is an error.

We can now take a closer look at Scheme's high-level macro facility.⁽ⁱⁱ⁾ It provides two interesting properties that together support the label of hygienic, providing a general solution to some hazards that arise from the attempt to use macros in practice. The first one might be called hygiene per se:

If a macro transformer inserts a binding for an identifier (variable or keyword), the identifier will in effect be renamed throughout its scope to avoid conflicts with other identifiers. Note that a define at top level may or may not introduce a binding; see section 5.2.

In other words, when defining a macro, you can safely use binding constructs such as lambda to name things for the macro's own internal purposes, without risk that the binding will capture free references to that name by the user code, despite the fact that it will be inserted around that code. A typical example would be defining a temporary variable to hold the result of an expression supplied by the macro user, which might be required because the result is used more than once and multiple evaluation would be unsafe due to side effects (or simply inefficient).

The peculiar note at the end turns out to be a major tease, as we'll be seeing.

The second property is known as referential transparency:

If a macro transformer inserts a free reference to an identifier, the reference refers to the binding that was visible where the transformer was specified, regardless of any local bindings that may surround the use of the macro.

It's a sort of converse of the first: when defining a macro, you can safely refer to any variable (procedure or otherwise) or syntax bound in a surrounding scope, without risk of its capture by a binding in the the user code, despite the fact that such binding would surround the macro-inserted reference. This may sound like pure magic at first, and it's not exactly easy to implement; it can be done using a special kind of renaming, requiring a generalized notion of names whereby the name object itself can be traced back to its original name and definition environment, if it doesn't first resolve to a binding inserted by the same macro use.

Overall, the idea is to cleanly separate macro implementation from use, such that the effect of a macro is predictable just from inspecting its code and surrounding context, in exactly the same way that lexical scoping of variables (also pioneered by Scheme) insulates a procedure's environment of definition from environment of use. On this support, the flexibility in shadowing or redefining names is not really as bad as it may at first sound.

Back to those mildly troublesome yet handy define statements, then. There can be either internal or top-level definitions; for example:

(lambda (x)
  (define the-product (* a x))
  (+ the-product b))

This is equivalent to our standard linear function from earlier, with the addition of an internal variable to hold the product rather than cramming all the operations into one expression. (Terribly exciting, I'm sure.) This style of binding a name to a value has a few advantages, such as keeping the name and the value expression close together in the code, and forming a "block structure" where internal definitions are followed possibly by commands (used for side-effects) and finally a result expression, all at the same indentation level. Its scoping rules also allow for recursive procedure definitions, much like the letrec binding construct, and in fact a procedure body containing internal definitions can be transformed into an equivalent letrec expression.⁽ⁱⁱⁱ⁾ Internal definitions, much like letrec initializers and procedure call arguments, are evaluated in a deliberately unspecified order, which underscores that they're functional programming constructs not intended to be used for side effects.

Top-level definitions look much the same, but they are evaluated sequentially as they occur in the program and they alter the globally-visible variables bound in the interaction environment. Thus they are used for their side effects, and indeed the standard (5.2.1) tells us:

At the top level of a program, a definition

(define <variable> <expression>)

has essentially the same effect as the assignment expression

(set! <variable> <expression>)

if <variable> is bound. If <variable> is not bound, however, then the definition will bind <variable> to a new location before performing the assignment, whereas it would be an error to perform a set! on an unbound variable.

However, it continues:

Some implementations of Scheme use an initial environment in which all possible variables are bound to locations, most of which contain undefined values. Top level definitions in such an implementation are truly equivalent to assignments.

That is, while a program that performs a set! on an unbound variable is not standard-compliant, implementations are not required to report the error, and some will do the obvious thing and simply assign to a global variable of that name.^(iv) Gales Scheme aims to detect all program errors when reasonably possible, and spurious unportabilities too, and so does not take this approach.

Putting the pieces together, we arrive at the promised conundrum:

When a macro transformer inserts a top-level definition for a name of its own, what does that name refer to?

(define-syntax define-my-var
  (syntax-rules ()
    ((define-my-var) (define my-var 1))))

(define-my-var)
(= my-var 1) ; true, false, or error ?

Does the macro's implementation make a free reference to the global variable of the same name, as was visible where the macro was defined, satisfying the referential transparency requirement and matching the behavior of the equivalent assignment expression? Or does it insert a new binding for a variable that must therefore be renamed throughout its (global) scope to avoid conflicts with later uses of the name, satisfying the hygiene requirement?

If you say "the first", it's at least mildly inconsistent with the view that there's a difference between binding a new variable at top level and assigning to an existing one. If you say "the second, if and only if it's in fact binding a new variable", it arguably introduces some serious context sensitivity whereby the interpretation of a macro may differ radically depending on unrelated parts of the program and the order in which they're loaded, as well as throwing a wrench in my current implementation at a potentially deep level.

So for the time being at least I'm sticking with the mild inconsistency, especially as I have yet to see the situation come up in practice to shed any light on what would actually be desirable.

1. What might really cook your goose, if you paid too much attention to your school math teachers, is to notice that there's nothing special about + and * : they're single-character names used free just like a and b, presumably referring to some builtin procedures that perform addition and multiplication when applied like any other function to some list of arguments. [^]
2. Some implementations also provide lower-level facilities, which were not standardized; basically the classic Lisp thing where you write a function that directly manipulates other code, at the level of symbolic expressions represented as nested list objects. [^]
3. And I in fact implemented it this way! You can also further reduce letrec into a lambda and series of assignments, but there are error detection and bootstrapping benefits to including it as a builtin syntactic form in the interpreter and so I do. [^]
4. The explicit distinction between side-effect assignments and functional local binding constructs is a delightfully clean and clarifying thing to work with coming from languages where the single-equals-sign is overloaded to do everything - and gods forbid you confuse it with the double- or even triple-equals! [^]