Going lambda/functional with m4

m4 is the GNU version of traditional macro processor. Even though it is a single pass macro processor, unlike cpp, it can also process the substitutions of a macro, we can define a macro to define another macro, and use the newly created macro, and so on. Thus, we can, in some sense, use m4 as a functional programming language.

We can also create non-recursive version in m4. Since lambda terms are essentially anonymous functions, we write m4 macros to create and destroy new pseudo-anonymous macro definitions. Following macro defines the Y combinator equivalent in m4.

This essentially is a version of fixed point combinator given by Haskell Curry and is defined as Y = \lambda f.(\lambda x.f (x x)) (\lambda x.f (x x)). This is similar to recur(recur). \lambda x.f (x x) is implemented as $1(`$1') in y_anon.

Run the above with m4 -dV to get sequence of reductions, it helps a lot with debugging.

Note that data constructors are also actual functions in m4, and there is no built-in support for say tuples or lists. It is more lambda-ish than say Haskell-ish. We have to build all such structures ourselves. The evaluation scheme is not full-lazy.