Imagining ‘dynamic macros’ for Scheme

NOTE HXA7241 2011-02-13T09:41Z

It seems possible to merge macros with lambdas, making a smoother single language feature. (At least, as far as a quick casual pondering will take you.)

The Scheme ethos, and macros

R5RS says at the start: “Programming languages should be designed not by piling feature on top of feature, but by removing the weaknesses and restrictions that make additional features appear necessary.”

Does this apply to macros? Macros might seem like a necessarily distinct mechanism, but is that so?

What macros offer, and call-by-name

And’ and ‘or’ cannot be lambdas because they might not want to evaluate some of their arguments. But this looks like something call-by-name could handle. So how much could macros be replaced by specific control of argument passing? – as in Scala a parameter can be set to be call-by-name or call-by-value. This is the seed of the idea. Maybe the solely call-by-value mode of Scheme lambdas could be considered a restriction that might be removed.

From ‘On Lisp’ by Paul Graham, section 8.1, we can understand what macros offer. They do two broad things not possible otherwise: control the evaluation of their arguments, and directly inline their code:

  • control
    • conditional, or multiple, evaluation of arguments
    • transformation of expressions, and binding of lexical variables
  • inlining
    • assuming a variable from the context
    • compile-time-execution, and call-avoidance

The first can be done with call-by-name. The second cannot, but perhaps could be with some extension to it: to allow ‘reaching in’ to the structure of the expression that is evaluated to give the argument.

The third is recognised as dubious, and do Scheme's hygienic macros even allow it? The fourth seems like it should be a separate, orthogonal, feature and mechanism.

Extending call-by-name with ‘constructors’

In one of the ‘On Lisp’ examples, ‘setf’ must be a macro because (setf (car a) 'b) needs to become (progn (rplaca a 'b) 'b). That is not possible with just call-by-name because it cannot see into the structure of the (car a) argument. But if a function could demand that an argument matches a particular ‘constructor’, it could get that access.

With such ‘constructed’ call-by-name, the function parameter is not only specified as by-name, but a ‘constructor’ is specified too, to allow access to the argument's sub-structure.

Basic call-by-name effectively passes arguments wrapped in lambdas, ‘constructed’ call-by-name would pass (in Lisp) a general list – i.e. a tree – of lambda-wrapped terminal things. This tree can then be manipulated, re-arranged, and executed in any way.

(You might ask, how can you pass this as a lambda and have the call site know to provide this special constructed structure? But how does any call site know to provide the right number of the right kind of arguments? These ‘constructed’ parameters are just another part of the lambda's signature – an extension of the same basic thing, not really anything different. With a latent-typed language you write the code to fit, and with a static-typed language those constraints can be specified and checked.)

Is this enough to replace the first two – the main, control – uses of macros? It seems to do the essence of them.

Dynamic macros

What we have, effectively, is dynamic macros – integrated with the rest of execution and with no barrier between them and lambdas (you could pass ‘and’ as a lambda to a ‘map’).

Program execution is tree evaluation. Macros transform the tree, but keep the same (depth-first) traversal of execution. Instead, this extended call-by-name is more like changing the order of traversal, including repeating, skipping, and inserting branches. Really, it is tree transform – but dynamic where macros are static.

Instead of a function taking a single value as each argument, it now takes a sub-tree of program. And function-calling is delegated to the called function: it decides how much of its sub-tree(s) it applies to. That is, for each argument, how much of its sub-tree is evaluated immediately and how much held back for access and re-arrangement inside the function.

It seems to obviate ‘hygienic’ effort, by using the built-in scoping mechanism of lambdas. And should not macros really be like calls anyway? – transforming arbitrary chunks in place is rather unstructured. This kind of dynamic macro slots the transform into the structure of the call.

The harder part is the constructing/destructuring of the argument sub-trees. The rest seems easy.

Implementation needed

Could this actually work? That requires more careful thinking.

Normal execution has to interpret up-coming expression trees, the change is to hold that off a little and delegate it to the called function. That then applies the special mechanism of transform before continuing.

The body of the called function is just like a normal macro definition. And it has its normal closure, but also, inside that, a closure for the parameter trees.

Hmmmm . . . (it has been an interesting thought-exercise so far anyway)

. . . But word has it that there is an implementation of something quite close to this: the Kernel Programming Language – “Kernel is a conservative, Scheme-like dialect of Lisp in which everything is a first-class object.”. The ‘dynamic macros’ there are in fact the primitive functional building-block, and lambdas are made out of them. A thorough and readable description is available at the site.