Some personal notes which might be useful for AST rewriting (based on a discussion with @OvermindDL1). @josevalim might wish to shield his eyes from the horror; This is like @OvermindDL1’s typed elixir experiments but worse… 
An elixir block:
(
expr1
expr2
expr3
)
which compiles to:
{:__block__, [],
[
expr1,
expr2,
expr3
]}
Such a block has some complex scoping rules, which get even more complex if there are nested blocks, as this image below shows:
The diagram above shows scopes as being enveloped with lines. Visually, the scoping rules are easy to explain: a variable defined in expr1, for example, will be in scope in every expression below, possibly inside nested blocks. More interesting the fact that variables defined in the nested block are in scope in the parent block, but only in the expressions below (as the lines indicate).
The scoping rules are similar to the ones in Erlang. In fact, a block in elixir seems to compile into a sequence of erlang expressions separated by ,. That is, the above block would compile to:
Expr1 , Expr2 , Expr3.
where the separator , is an operator that carries the context (i.e. scope) of the previous expression into the next expression. Of course, the comma (,) is also a sequencing operator in elixir. The block above is equivalent to expr1 , expr2 , expr3. We usually use newlines to separate expressions instead of the ,, but it’s the same idea.
Well, the fact that blocks are compiled into a sequence of binary operations using the , operator (I think it’s not formally an operator in Erlang, but it helps if we think of it as one) gives us an idea: we can compile the blocks ({:__block__, meta, expressions}) into an intermediate binary form, say:
{:__comma__, [],
[
left_side,
right_side
]}
Where comma is the obvious thing (analogous to Erlang ,). By the way, the Erlang comma is also very similar to OCaml’s let ... in ... statement. Which might mean we can apply lambda calculus reduction rules to our modified AST, but I digress…
The advantage of having an AST node with only two children is that the scoping rules become much simpler. Instead of the complex scoping rules of the elixir blocks (in the picture above), the scoping rules here are much simpler:
-
The scope that results from the expression on the left side is the scope used to compile the right side
-
The scope that results from compiling the entire
__comma__block is propagated upwards so that it can be used in the parent__comma__node.
We can represent scopes as maps from variable to unique identifiers, something like: %{var_name, var_meta, var_context} => uuid}. The uuid can be used as the counter to disambiguate between variables with the same name.
In a tree of commas, it looks like the scope always accumulates as you walk the tree in post-order, which means that you can cache it as something like:
{:__comma__, [scope_right: scope_right, scope_up: scope_up],
[
left_side,
right_side
]}
where scope_right is the new variables in scope after compiling the left_side (which will be part of the scope for the right_side) and scope_up, a map with the new variables that propagate up (into the right side of the parent __comma__).
This is a very simple model. We can consider these scopes as deltas, which we apply to the previous scope (using Map.merge/2). Variables in blocks (and as an extension, __commas__) don’t ever go out of scope, which means the scope always increases or stays the same as we traverse the __comma__ tree in post-order. Which means we just need to keep a running scope and can simply merge the maps in order.
This approach is simple and probably doesn’t require any complex graph algorithms (that is, we only operate on trees and never on more general graphs).
I think that to move all variable assignments to the beginning of the tree I just have to traverse the tree in “inverse-post-order” (that’s roughly right to left; I don’t know if this term even exists), and if I could do it it’d be great, because it would avoid the need to use general graphs and some kind of dependency resolution algorithm. I think that if I play my cards right I won’t have to use graph algorithms…
Then, after moving the assignments out of the main compile-time nested iolist of the EEx template (let’s not lose sight of the fact that we want to optimize a template!), I can just expand in place the top-level variables in the list, and flatten the list at compile-time.
With the flattened list, I just have to merge the static binaries and it’s basically done 
This is the kind of thing that a compiler for a functional language (i.e. OCaml, Haskell) does or can do all the time, especially if the reduction semantics of the language are simple. Elixir is not a purely functional language by most criteria, but it does have relatively simple reduction semantics. I’ll not try to explain what reduction semantics are, but it’s basically a set of rules that tells us how we can replace some symbols in the code by other symbols. For example:
a = f(1)
b = a
can’t be replaced by:
a = f(1)
b = f(1)
(because f(1) might return a different result when it’s invoked twice)
So, if theoretically (wink, wink 
) I were to use AST rewriting I’d try do more or less the following:
- Build a dependency graph of the variables in scope
- Rename the variables so that variable names become unique
- Bind the variables according to the order in the dependency graph, so that we can factor them out of the iolist (which represents the final output of the template)
- Substitute some of the variables in place so that the list contains only references to variables defined outside of the list
- Build and flatten the final list so that we can separate the static and dynamic parts.
Note: why do we need to move all the variable assignments outside of the list?
Because in Elixir, variables bound inside an element of a list are not in scope in the remaining elements of the list. For example:
iex(1)> [x = 1, x + 1]
** (CompileError) iex:1: undefined function x/0
(stdlib) lists.erl:1354: :lists.mapfoldl/3
iex(1)> x = 1, [x, x + 1]
[1, 2]
iex(2)>
This is exactly what we’ve done here: we’ve moved the variable assignment out of the list so that we can use the variable inside the list. So, under these limitation, how is it possible that the EEx templates in Phoenix (which compile to iolists) can ssign variables and refer to them later? The answer is that Phoenix templates compile to terms with lots of nested blocks. For example, this:
<% a = 1 %>
<%= a %>
compiles to this (more or less, the template below is simplified):
{:safe,
[
(
tmp1 = [
(
tmp2 = ""
a = 1
tmp2
)
| "\n"
]
[tmp1 | {:dynamic, a}]
)
| "\n"
]}
As you can see, we are building an iolist, but to be able to refer to variables that are defined in other elements of the list, we must use nested blocks so that the scopes propagate. Notice that we create a more or less “useless” block just to define the variable a so that we can use it later.
