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`])changequote`dnl
(changequote([,])`$[]1'changequote)dnl
`popdef(`y_anon')')'dnl
`y_anon')dnl
pushdef(`y_anon',`dnl
recur(`recur')'changequote([,])(`$[]1')changequote`dnl
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.
