In “On Lisp”, Paul Graham introduced the concept of “anaphoric macros”, a term he borrowed from linguistics. We can have them in Elixir as well, and while they’re dangerous because code written in them might confuse people, they are fun to play with.

So what is an anaphoric macro exactly? Let’s start by example: Common Lisp has the loop macro which is pretty much `for` with everything but the kitchen sink. I think books have been written about it. From the Wikipedia article on anaphoric macros:

``````(loop for element in '(nil 1 nil 2 nil nil 3 4 6)
when element sum it)
;; ⇒ 16
``````

Like an anaphora in linguistics, `it` refers to something that came before, in this case the result of the conditional clause. It just magically appears, without warning, poking up its head like a jack-in-the-box and you need to know about the loop macro to know that you can use `it` here. But, for its expensive and posh sounding name, it’s a simple concept: a macro that on expansion introduces variables the user didn’t specify.

A more interesting example is when you make an anaphoric lambda macro:

``````(defmacro alambda (parms &body body)
`(labels ((self ,parms ,@body))
#'self))
``````

This macro packs a punch: it introduces the lambda expression as an anaphoric variable in the macro, which means that you can refer to it from the lambda expression. The result is that you can write:

``````(alambda (n)
(if (= n 0)
1
(* n (self (1- n)))))
``````

Look - an anymous function that can call itself recursively supported by just three lines! Much nicer than the Y combinator version which is too long to list here. On the same page, the Elixir Y combinator solution is much shorter:

``````fib = fn f -> (
fn x -> if x == 0, do: 0, else: (if x == 1, do: 1, else: f.(x - 1) + f.(x - 2))	end
)
end

y = fn x -> (
fn f -> f.(f)
end).(
fn g -> x.(fn z ->(g.(g)).(z) end)
end)
end

IO.inspect y.(&(fib.(&1))).(40)
``````

It works, but it is hardly elegant. Can we have an anaphoric lambda in Elixir?

Well, yes, but it is somewhat harder. While Elixir has a pretty powerful macro system it has a very clear and compile time distinction between “data” and “code” and the sort of on-the-fly function definition thing that the Lisp version leans on using `labels` won’t cut it. The simplest I got to work is this:

``````defmodule AnaphoricLambda do
defmacro alambda(fun) do
r = Macro.var(:self, nil)

quote do
unquote(r) = unquote(fun)
fn (x) -> unquote(fun).(x, unquote(r)) end
end
end
end

defmodule Test do
import AnaphoricLambda
def test do
fib = alambda fn
x, _ when x < 0 -> raise "Stay positive!"
0, _ -> 0
1, _ -> 1
n, self -> self.(n - 1, self) + self.(n - 2, self)
end
end
end

IO.inspect Test.test()
``````

This is short but not very elegant. We inject the function into itself to enable the recursion, but that means that we need to write the single-argument function as a two-argument one where the second argument is the anaphoric variable.

Now, I’m not sure that this is an optimal solution but I puzzled over it for a couple of hours and this is the best I could come up with (I’m writing this post partially in the hope that someone will correct me and come up with something nice - I’m hardly a macro specialist). Note the

``````r = Macro.var(:self, nil)
``````

which creates a variable `self` in an empty context. If you start digging through the ASTs during macro hacking then you’ll see that you need this nil context for such local variables. It expands to just `{:self, [], nil}` but writing it this way shows intent better.

What we want is a simple one-argument `fn` and the macro then has to tweak things. Without further ado:

``````defmodule I do
defmacro alambda(block) do
r = Macro.var(:self, nil)
block = Macro.prewalk(block, fn
{:when, meta, elems} ->
{:when, meta, [r | elems]}
b = {:->, meta, [lhs, rhs]} ->
case lhs do
[{:when, _, _} | _] ->
b
_ ->
{:->, meta, [[r | lhs], rhs]}
end
{ {:., meta, [{:self, _, _}]}, _, args} ->
{ {:., meta, [r]}, [], [{:self, [], nil} | args]}
other ->
other
end)
block = quote do
r = unquote(block)
fn x -> r.(r, x) end
end
IO.puts Macro.to_string(block)
block
end
end

defmodule Test do
import I
def test() do
fib = alambda fn
x when x == 1 or x == 0 ->
x
x ->
self.(x - 2) + self.(x - 1)
end
IO.inspect fib.(20)
end
end

Test.test()
``````

We made the invocation quite nice: the `alambda` expression now has just a single argument and the `self` is magically injected. But that macro is enough to give you a headache (and it is hardcoded to single argument functions, although that shouldn’t be too hard to fix). We use `Macro.prewalk/2` to walk through the function body and we match for three clauses in the AST:

• `{:when, meta, elems}` matches a `when` clause. `elems` are the arguments to `when` and this is a flat list of parameters and then the when expression as the last element. We simply prepend `self` to the parameters so that `x when x == 1` now reads `self, x when x == 1`.

• `{:->, meta, args}` matches a regular function head. We need to exclude a `when` clause in therei because it gets processed in the first clause but otherwise we do the same trick: `x ->` is changed to read `self, x`.

• Finally, `{ {:., meta, ....` matches a function call. When we recurse from the function body, we need to rewrite `self.(x - 2)` into `self.(self, x - 2)` and that completes the expansion.

There is debugging code in the macro code to print the expansion, and this is what we create:

`````` r = fn
(self, x) when x == 1 or x == 0 ->
x
self, x ->
self.(self, x - 2) + self.(self, x - 1)
end
fn x -> r.(r, x) end
``````

Pretty much what we wrote manually before, and this compiles and runs. The first clause causes an “unused” warning because the `self` there really should be a `_self` but as the author here I can leave that as an exercise to the reader.

Anaphoric lambda, yay! Now, are we loosing a lot of performance? The reason I switched from factorial to fibonacci is that the trivial recursive implementation is bad. It is even O(2n) bad, people on StackOverflow tell me (and it is true because that answer got upvotes). Using `:timer.tc/1` and a trivial regular function definition, we can compare:

``````def fib(x) when x == 0 or x == 1, do: x
def fib(x), do: fib(x - 1) + fib(x - 2)
...
IO.inspect :timer.tc(fn ->
fib.(20)
end)
IO.inspect :timer.tc(fn ->
fib(20)
end)
``````

This very scientific benchmark shows 1.4ms for the anaphoric lambda version and 1.2ms for the regular function. Not bad, the overhead for the anaphoric lambda doesn’t seem to be very high, but O(2n) starts showing. Let’s push it a bit and calculate the 40th number instead of the 29th (the `tc/1` function returns a tuple with the time in microseconds and the function return value):

``````{21719438, 102334155}
{18201677, 102334155}
``````

Ouch. 2n hits hard. And I wanted to know the 400th Fibonacci number! Can we do better? Yes we can, with an all-time favorite macro writers tool, “memoization”. We sneak in some time-for-memory tradeoff by expanding the macro so that we only calculate any given fibonacci number once. The whole variable injection stays the same, but we now introduce a unique key for this particular macro and then return code that stores results in ETS so they only need to be created once:

``````    ...
memo_key = :erlang.unique_integer()
retval = quote do
r = unquote(block)
m_r = fn self, x ->
case :ets.lookup(Memoize, {unquote(memo_key), x}) do
[] ->
v = r.(self, x)
:ets.insert(Memoize, { {unquote(memo_key), x}, v})
`	    v
[{_key, val}] ->
val
end
end
fn x -> m_r.(m_r, x) end # TODO more than one arg
end
...
``````

This now results in the following expansion:

``````r = fn
(self, x) when x == 1 or x == 0 ->
x
self, x ->
self.(self, x - 2) + self.(self, x - 1)
end
m_r = fn self, x -> case(:ets.lookup(Memoize, {-576460752303423327, x})) do
[] ->
v = r.(self, x)
:ets.insert(Memoize, { {-576460752303423327, x}, v})
v
[{_key, val}] ->
val
end end
fn x -> m_r.(m_r, x) end
``````

We first lookup in ETS, and if there’s a value we return that. We smash O(2n) to O(n) and that shows:

``````{14, 102334155}
``````

Note that the really nice thing here is that we did not have to touch our code. The `alambda fn ...` is untouched but we sped it up by, well, a lot of orders of magnitude. Memoization truly can be a miracle!

If you want to use memoization for more serious purposes than this code diversion, there are multiple packages on Hex that will help you out. The version here is lacking because there is no way to clean out unused values (you probably want something with a TTL, for example).

Also, if you want to generate fibonacci numbers quickly, here’s an O(1) version:

``````def Fibonacci do
@φ (1 + :math.sqrt(5)) / 2
@sqrt_5 :math.sqrt(5)
def fib(x) do
round(:math.pow(@φ, x) / @sqrt_5)
end
end
``````

It probably shows that math trumps recursion and certainly shows that tricks like anaphoric macros and memoization are best left in the toolbox until you’re sure you need them. But I had fun with them, and that counts for something :)