m4 is a general purpose macro processor. It was written in 1977 by Brian Kernighan and Dennis Ritchie, and was an essential part of early Unix systems; it was largely originally intended as a Fortran preprocessing tool. (particularly for the Ratfor language, an early attempt to impose structured programming on Fortran).

The GNU m4 manual does warn:

I'm not sure if what these essays attempt to do falls into that category …

Before we look at using m4 for HOP, we need to explore a few techniques for building suitable macros. HOP needs functions that take other functions as arguments (operators), and functions that return other functions (Currying).

Constructing operators is relatively trivial - using functions as arguments comes as an essential part of recursive macro expansion, and is easy enough, subject to getting quoting right (for which, see the next section).

Currying is rather more difficult, so we will build up to it slowly.

Defining a macro in m4 is easy; but defining macros which build macros is tricky to get right, largely because of m4's quoting rules. Consider the very simple macro, which takes one argument and expands to the literal value of that argument:

This is mostly self-explanatory, but we need to be careful about quoting here. When m4 processes this definition, it evaluates the two arguments to define; since they are both quoted strings, this means stripping off one layer of quoting around each argument. Thus, it registers a macro called repeater, which will expand to the string `$1'. Since one layer of quoting still remains, then the when this argument is evaluated, one layer of quoting is stripped off again, and $1 is not further evaluated.

To make this clearer, let's use this macro:

If we did not have the correct quoting, then m4 would have tried to further evaluate the result of repeater.

Consider how we might write a macro which, when invoked, defines a macro with the behaviour above. Let the first argument to this creator macro be the desired name of the new repeater macro.

Naively, we might write this:

This fails because of how m4 handles argument expansion; on macro invocation it replaces all instances of $1 with the argument, regardless of quoting levels. Normally, in order to prevent "$1" from being expanded too early, we replace it with $`'1 - the quotes will be removed after one evaluation, and $1 revealed. Thus:

Unfortunately, this still won't give the desired effect, since the version immediately above will result in a macro definition without enough quoting around its argument. And we can't get around this with additional quoting, or the quotes between $ and 1 will not be removed at the right point. Instead, we must resort to temporarily changing the quote characters:

Here, we change the quote characters to []. This means that the normal quotes in the definition are initially treated as non-special characters - in the definition of the mkrepeater macro - while in its invocation they recover their normal meaning, and the correct level of quoting is achieved. Thus:

and we can see that the newrepeater macro has the desired property of returning its argument unexpanded.

The same principle applies when stepping back again, and writing a macro to produce a mkrepeater-like macro - that is, a macro which produces a macro which produces a macro which returns its first argument:

Working out why this is correct is left as an exercise for the reader.

Anonymous functions, or "lambda" functions, are functions without a name bound to them. They are first-class citizens in many languages, but not m4.

However, depending on one's need for them, it is possible to fake the necessary parts of a lambda function as a macro, at least in Gnu m4 (POSIX m4 is insufficient, I think).

An important aspect of a lambda function is that it provides evaluation of a function, without polluting the function namespace. This is particularly important in m4, which has only one, purely global, namespace. Every macro which is defined is registered in this global namespace, regardless of where and how it is defined. So, for doing higher-order computation, we need anonymous functions - even more so than in a language which has locally-scoped name binding.

We can't create macros which are anonymous (the expansion of a macro can't exist without a macro name to be expanded). But, we can create macros which unbind their own names as their last action.

That is, while their name is bound (and thus pollutes the global namespace) from their definition to their invocation, thereafter it is unbound, so if invocation immediately follows definition, they are essentially anonymous.

Additionally, we must ensure that the name used does not overwrite any macros currently defined with that name. To this end, we need to use Gnu m4's extension of pushdef and popdef macros, which permit temporary re-binding of a macro name.

Putting this all together, we can use "anonymous" macros like so:

This macro (called global), internally defines a macro lambdalite, and then immediately invokes it. The lambdalite macro expands to some text, followed by unbinding of its own name. To show that this works:

We define a macro lambdalite in the global namespace, then call our global macro - which uses its internal anonymous function, also called lambdalite - and then we invoke lambdalite again. As you can see from the result, the original version of "lambdalite" is invoked, and we have truly used an "anonymous" macro.

Clearly the internal macro above is not truly anonymous, because it has a name associated with it, albeit briefly. This means certain things are not possible - for example, we cannot use the word lambdalite inside its own definition (or we end up with an infinitely recursive definition. A call to this macro will never terminate:

GNU m4 allows for yet further degrees of anonymity through the use of the indir builtin. define can give a macro any name, including names that are not directly callable, because they are not "word"s as m4 understands them. These can then be invoked by using the indir builtin, like so:

Since $lambda is not an m4 word, it won't ever be expanded accidentally, and we don't need to worry about the contents of the anonymous function:

(Of course, if we used indir inside the anonymous function, we'd have to ensure it didn't invoke $lambda, but that is much less likely to happen accidentally).

Using indir for anonymous functions works fine in this case, for macros without arguments. However, it turns out not to be possible to use it in the way required for the next section, so we won't pursue this line of enquiry further. (At least, I've been unable to do so. I'd welcome corrections.)

Bringing the last two techniques together - macros that define macros, and anonymous macros - we can build the final structure we need for higher-order programming, macros which "return" macros. Or to put it another way, macros whose expanded value are invokable as macros. In functional language, functions whose return values are functions, which may be called themselves.

In the first section above we showed how to define a macro from within another, but that was a side-effect of macro expansion - the expanded value of that macro was a macro definition, not an invokable macro itself. That is, we want to be able to write the following:

where repeater(5) acts itself as a macro, which then takes an argument, (6). Let's define repeater to take a numerical argument n, and return a function, also taking one argument, which adds its argument to n and returns the result. This is otherwise known as Currying over the first argument, in this case, 5.

(The advantage of dealing with macros manipulating numbers is that quoting is decidedly easier; numbers cannot be macro names, so don't need quoted.)

To explain this macro: it creates an anonymous macro, called LL, which multiplies together the argument to adder ($1) and LL's own argument; it then calls LL immediately.

That is, the expanded value of adder(5) is an (anonymous) macro invocation expecting an argument. You can see this by trying to do:

However, used as intended:

adder(5) is the curried function f(x)=5+x which, when itself called with the argument 6, expands to the correct value.

Having created this anonymous function, we could, if we wished, assign it a name:

and we can now use add5 as you would expect:

In particular, note that although the anonymous function used inside adder can only be used once, it is created and destroyed on each invocation of add5, so this acts as a true Curried function.

Ideally, we'd like to be able to use indir to further anonymize the internal macros. As it stands, we need to be careful not to accidentally use the literal word LL inside its definition.

So, roughly, we'd like something that looked like:

but in this case, $lambda needs arguments, and those arguments are never available within the definition of adder - precluding the use of indir.

Direct invocation is fine, since we are simply relying on the fact that after expansion, the macro can expect to find a set of arguments waiting for it.

This is very simple, but for completeness, we'll look now at how to write macros which take other macros as arguments; operator macros.

This macro expects two arguments; the first of which is expected to be a macro. It then applies that macro to its second argument and returns the result.

Assuming we have defined add5 and add10 in the obvious way from the previous section, we can see this in action:

With the ability to build operators and Curry functions, we are now equipped to do generalized HOP. As a test of this, in part II of this essay we'll construct a Y Combinator - or more precisely, the fixed-point operator for the m4 macro calculus.