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.

## No comments:

## Post a Comment