### 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.

Recursive version of factorial program is straightforward in m4:

define(rec_fact', ifelse($1,0,1,eval'($1 * rec_fact'(eval'($1 - 1))))') rec_fact(15) 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. dnl Thanks to Toby White (http://uszla.me.uk/space/essays/m4Y) define(define(Y_COMB', dnl pushdef(recur',dnl pushdef(y_anon',dnl $1''changequote([,])(['changequote([,])changequote]$[]1'($[]1'')dnl
['changequote([,])'changequote])changequotednl
(changequote([,])$[]1'changequote)dnl popdef(y_anon')')'dnl y_anon')dnl pushdef(y_anon',dnl recur(recur')'changequote([,])($[]1')changequotednl
popdef(recur')'popdef(y_anon')')'dnl
'y_anon')'dnl

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.

The non-recursive version of factorial can be written as :
define(ARG1', changequote([,])$[]1'changequote')dnl define(F_fact',dnl pushdef(anon',dnl ifelse'(ARG1,1,1, dnl eval''(ARG1 * $1''(eval'(ARG1 - 1))))dnl
popdef(anon')')'dnl
anon')dnl

And now all we need to do to call this non-recursive factorial functions is:
Y_COMB(F_fact')(5)

We can also define a sugar function named fact that expands to Y_COMB(F_fact').

Not just tail recursion but we can also run any kind of general recursive program in non-recursive fashion:

define(F_fib',dnl
pushdef(anon',dnl
ifelse'(ARG1,1,1, ARG1,2,1, dnl
eval''($1''(eval'(ARG1 - 2)) + $1''(eval'(ARG1 - 1))))dnl
popdef(anon')')'dnl
anon')dnl
Y_COMB(`F_fib')(11)

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.