Macroator

tags: python

this post was (mostly) written around the same time as the code, then sat unpublished for most of a year.

Macroator (a terrible combination of "macro" and "decorator") is a new library I've written to push the boundaries of there's no way to justify this horror. It provides AST-level macros in Python by abusing decorator syntax and import hooks.

You can find the source code here

Let's look at a simple example:

Here's a simple, somewhat bad implementation of factorial as a tail-recursive function. For fun, it also includes identity, which is simply the identity function. This is not necessary, but does make the later demonstration (slightly) more interesting.

# factorial.py
def identity(x):
  return x

@magic_trampoline
def factorial(n, m=1):
  if n < 2:
    return identity(m)
  else:
    return factorial(n-1, m*n)

We'll just import this and call it:

# combined.py
# this is where the magic happens
import macroator

from factorial import factorial

# let's lower the recursion limit a bit.
import sys
sys.setrecursionlimit(10)

# now, our tail recursive function should go to a stack depth equal to `n`.
# But thanks to our _magic_, this works.
print(factorial(50))

# The answer is right, too.
import math
assert factorial(50) == math.factorial(50)

Now of course, that shouldn't work. Our factorial will recursively call itself 50 times, but our call stack isn't allowed to get any larger than 10 functions deep.

However...

$ python combined.py 
30414093201713378043612608166064768844377641568960512000000000000

What?! How?!

import macroator installs an import hook that catches all later imports and, if the imported module is a python source file, parses it, then looks through the abstract syntax tree for magic decorators, such as @magic_trampoline.

When it finds one, it passes the AST of the function to an AST-rewriter. After the AST has been rewritten, it compiles it and turns it into a module, then returns that as the result of the import process.

The @magic_trampoline decorator gets mapped to TrampolineMacro, which searches the function for all return statements whose return value is a function call expression. It replaces those calls with dictionary literals containing all the information required to call the function. It also adds a new, regular decorator to the decorator list for the function. That decorator, ★trampoline_decorator¹, has a loop which checks the return value of the function for those special dictionaries. When it sees one, it performs the function call described by the dictionary, then repeats the process for its return value. If and when the function stops returning special dictionaries, it returns the final return value.

I'm so sorry.