PhoenixUndeadView - let's discuss optimization possibilities for something like Phoenix LiveView

I’m interested in going the way of radical AST rewriting. One of the things I’ll have to do for my idea to work is to turn all variable reassignments (pattern = value) into single assignments of variables with unique names.

While I could transform x = f() into x_unique_suffix__1 = f(), that wouldn’t be nice for error reporting. Fortunately, the elixir AST marks each variable with a unique context. In the AST variables are represented as {atom, meta, context}, where context is an atom (often a module name).

My question is then the following: to turn those variables into unique variables, can I just change the context? For example, if the context is MyModule, could I change it to MyModule__unique_suffix_1? This seems like the obvious way to go, but I’m afraid it might mreak something I’m not seeing.

From what I understand, contexts are just meaningless tags to disambiguate variables with the same name that shouldn’t shadow each others. The fact that the context is often a module name is just an implementation detail, right?

Pinging @josevalim because of our discussion in the LiveView thread.

Sorry but the best advice I can give right now is: don’t do it. Emit the correct code in the first place and avoid the AST transformation.

Ok, but theoretically, if there was no other option, I can change the context to whatever I want, right? I’m not very optimistic on the possibility of generating the kind of code I need without AST rewriting.

You could. Although it is possibly easier to do that by setting the counter in the metadata, which is how we do hygiene in macros.

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:

scopes526×276 14.1 KB

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:

1. The scope that results from the expression on the left side is the scope used to compile the right side

2. 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:

1. Build a dependency graph of the variables in scope
2. Rename the variables so that variable names become unique
3. 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)
4. Substitute some of the variables in place so that the list contains only references to variables defined outside of the list
5. 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.

I’m pretty sure ; is a proper operator in Erlang (it is in OCaml), just that it evaluates the left expression, adds it to the environment, and then evaluates and returns the right expression. . I’m unsure is an operator or just a terminator for an erlang function though…

Maybe it is, but it doesn’t appear in this table: http://erlang.org/doc/reference_manual/expressions.html#operator-precedence

EDIT: keep in mind that the little I know about Erlang is from reading the official docs and reading the output of the BEAM disassembler run on Elixir module files…

Nope.

The semicolon is to concatenate alternations, not sequences, you use it as here:

my_not(true) -> false;
my_not(false) -> true.

You were not able to see any binding from the first clause in the second clause, neither would you in elixirs equivalent:

def my_not(true), do: false
def my_not(false), do: true

What you probably mean here is the comma ,, which is used to build “sequences”:

foo(A) ->
  B = A + 1,
  C = A - 1,
  div(B + C, 2).

which is equivalent to this elixir code:

def foo(a) do
  b = a + 1
  c = a - 1
  div(b + c, 2)
end

Yes, it’s the comma. Thanks!

I can’t edit my post anymore, so could a nice mod please add something to the effect that semicolons should be replaced by commas?