Producing the Fibonacci sequence with m4(1)

m4(1) is a heinously ugly, bronze-age macro language language. It should have died long ago, but it has stuck around because it is very simple and very powerful. If you have ever run ./configure to build a package, it was m4 that generated a custom Makefile for your system.

In addition to acting as the foundation of portable software on UNIX, m4 can also do stupid shit, like calculate the Fibonacci numbers in the least practical way possible. This gnarly bastard will compute any of the first 47 Fibonacci numbers (after that, the signed 32-bit integers used by m4
will overflow):

define(`FIB', `ifelse(`$3',`2',`$2',`FIB($2,expr($1 + $2),decr($3))')')dnl

That's all well and good, but it's incomphrehensible nonsense. m4 has features that will let us clean it up a little, and a fortunately "a little" is all we need.

For starters, those quotes are attrocious. If you have never used m4 before, you may rightly be wondering why it doesn't use ´ or " quotes like most human-designed programming languages. This is because m4 was designed by aliens who are deeply focused on nesting macros.

Nesting macros is important, but so is our ability to read the goddamn code. Let's use the changequote feature to turn these into something a bit easier to read:

changequote([,])
define([FIB], [ifelse([$3],[2],[$2],[FIB($2,expr($1 + $2),decr($3))])])dnl

A bit better, but still borderline unreadable. I mean, for the love of God, there are 7 closing delimeters on the right side, followed by the nonsense phrase “dnl”. We can do better. We must do better! Let's start with something simpler:

decr(3)

Fairly straight-forward example, right? It decrements the literal value “3”, and will therefore print the number “2”. Because m4 repeatedly expands macros, you can do the same thing on any macro that expands to a number:

define([THREE], [3])
decr(THREE)

The expr function allows you to do simple, C-style arithmetic. This is handy for lots of things, but we will use it here just to add two numbers together (since the Fibonacci sequence is made from adding the previous two numbers together):

expr(3 + 5) # returns 8

# define a macro for adding numbers
define([ADD], [expr($1 + $2)])

ADD([3], [5]) # returns 8
ADD([THREE], [5]) # also returns 8

Limited Recursion

The Fibonacci sequence is fundamentally recursive, and the sequence itself is infinitely long. Here is a naive implementation that will keep running until you kill it with Ctrl+C:

define([FIB], [expr($1 + $2) FIB($2, expr($1 + $2))])
FIB(0,1)

On OpenBSD, m4 uses signed, 32-bit integers, so this will overflow pretty quickly and start printing negative numbers, none of which actually appear in the Fibonacci sequence. We can fix this using the built-in ifelse macro to stop recursion after computing the Nth element:

define([FIB], [ifelse([$3],[2],[$2],[FIB($2,expr($1 + $2),decr($3))])])dnl

This allows us to produce the 8th element by calling FIB([0],[1],[8]). The way this works is that each invocation of FIB checks to see if the 3rd argument equals the literal number 2. If it doesn't, the macro will call FIB again, but with the third argument decremented by one. You can see this in action by using m4's traceon feature to show the expanded values for each call to FIB:

traceon([FIB])
FIB([0],[1],[8])

# output:
m4trace: -1- FIB -> [ifelse([8],[2],[1],[FIB(1,expr(0 + 1),decr(8))])]
m4trace: -1- FIB -> [ifelse([7],[2],[1],[FIB(1,expr(1 + 1),decr(7))])]
m4trace: -1- FIB -> [ifelse([6],[2],[2],[FIB(2,expr(1 + 2),decr(6))])]
m4trace: -1- FIB -> [ifelse([5],[2],[3],[FIB(3,expr(2 + 3),decr(5))])]
m4trace: -1- FIB -> [ifelse([4],[2],[5],[FIB(5,expr(3 + 5),decr(4))])]
m4trace: -1- FIB -> [ifelse([3],[2],[8],[FIB(8,expr(5 + 8),decr(3))])]
m4trace: -1- FIB -> [ifelse([2],[2],[13],[FIB(13,expr(8 + 13),decr(2))])]
13

This shows us that $3 (which is passed as the first argument to the ifelse macro) is decremented by 1 each time, returning the final value only when $3 equals 2.

See this gist for more examples of these concepts in action.