"Dynamic" module generation with compile-time macros

Over on the Erlang Questions mailing list, Jacob Perkins asked:

"I have a few files that are basically lists of words. What I want to do is generate a module whose functions will return each list of words. So if I have two files named "adjectives" and "nouns", then the generated module (let's call it 'grammar') should have two functions, adjectives() and nouns(), that return their respective list of words.

How can I do this?"


If I had some method of running Erlang code at compile-time - and I do - then I could write a program to slurp in those adjective and noun files and generate the appropriate functions.


adjectives.txt:

this
that
these

nouns.txt:

apple
banana
carrot

grammar.erl:

-module(grammar).
-export([nouns/0, adjectives/0]).
-compile({parse_transform, emp2}).

-macro({grammar_macro, generate, [nouns]}).
-macro({grammar_macro, generate, [adjectives]}).

grammar_macro.erl:

-module(grammar_macro).
-export([generate/1]).

generate(NameFun) ->
    {ok,Fd} = file:open(atom_to_list(NameFun) ++ ".txt", [read]),
    generate(Fd, NameFun, []).

generate(Fd, NameFun, Words) ->
    case io:get_line(Fd, "") of
        eof ->
            ok=file:close(Fd),
            io_lib:format("~w() -> ~w.~n", [NameFun, lists:reverse(Words)]);
        Word -> generate(Fd, NameFun, [Word | Words])
        end.

And in the Erlang shell:

1> c(grammar_macro), c(grammar).
{ok,grammar}
2> grammar:nouns().
["apple\n","banana\n","carrot\n"]
3> grammar:adjectives().
["this\n","that\n","these\n"]

Erlang Macro Processor (v2), Part V

The final step for EMP2 is to expand any remote macro function calls and insert the results back into the AST.

Naively we would just follow the same pattern as the macro attribute expansion that we have just added:

node_parse(Node={call,Line,{remote,_,{atom,_,Mod},{atom,_,Fun}},Args}, Mods) ->
    case lists:member(Mod, Mods) of
        true ->
            ast_from_results(lists:flatten([apply(Mod,Fun,Args)|" "]), Line, []);
        false -> setelement(4,Node,node_parse(Args, Mods))
        end;

But if we do, we find that there are three(!) problems with this approach.

Firstly, ast_from_results is currently using erl_parse:parse_form to turn the textual macro results into an AST. This only works for complete Erlang forms (function definitions) and not for, say, a set of three Erlang expressions to be inserted into a function. We can fix this by using erl_parse:parse_exprs instead, but we will also have to append a full-stop and space to the result string (instead of just a space) to get it to work properly.

Secondly, the arguments for the function call are all in AST format with tuples and line numbers everywhere. We cannot just apply the function directly to these arguments; we need to convert them back to something more usable.

Finally, we may receive more than one Erlang expression from the macro. To fit these back into the space of a single node we have to wrap them in a block expression.


To tackle the first issue we need to update ast_from_results a little:

ast_from_results(FunParse, ResultsString, LineStart, ASTResults) ->
    case remove_leading_whitespace(ResultsString) of
        "" -> lists:flatten(lists:reverse(ASTResults));
        String ->
            {done,{ok,Tokens,LineEnd},StringRest} =
                erl_scan:tokens([], String, LineStart),
            {ok, AST} = erl_parse:FunParse(Tokens),
            ast_from_results(FunParse, StringRest, LineEnd, [AST|ASTResults])
        end.

As an aside, you might like to have a closer look at that erl_parse:FunParse call.

Yes, instead of hard-coding a function call or adding an extra if statement, we are calling the erl_parse function via a variable whose value we will not know until run-time[1]. Doesn't thinking about that just make you go all tingly inside? No? Me neither. Of course.

We can now use ast_from_results for erl_parse:parse_form and erl_parse:parse_exprs situations with only a single additional "erl_parse function" argument.


For the second issue I am going to use a cheap and nasty hack. Because we are not (yet) supporting anything fancier than literal terms in the argument list, we can get away with this little bit of trickery to convert the arguments into something usable by our call to apply:

ArgsLiteral = [Value || {_Type,_Line,Value} <- Args]. 

The third issue is also very easily fixed by wrapping the call to ast_from_results in a block expression tuple. We should only do this if there is more than one node in the results list:

node_parse(Node={call,Line,{remote,_,{atom,_,Mod},{atom,_,Fun}},Args}, Mods) ->
    case lists:member(Mod, Mods) of
        true ->
            ArgsLiteral = [Value || {_Type,_Line,Value} <- Args],
            Results = lists:flatten([apply(Mod,Fun,ArgsLiteral)|". "]),
            case length(Results) of
                1 -> hd(Results);
                _ -> {block,Line,ast_from_results(parse_exprs, Results, Line, [])}
                end;
        false -> setelement(4,Node,node_parse(Args, Mods))
        end;

Oh, and of course we need to update the other node_parse function clause to include the new argument to ast_from_results:

node_parse({attribute,Line,macro,{Mod,Fun,Args}}, _Mods) ->
    ast_from_results(parse_form, lists:flatten([apply(Mod,Fun,Args)|" "]), Line, []);

And with any luck we are done. Let's try it out on our example code.

1> CL = fun(F) -> c(F), l(F) end.
#Fun
2> CL(emp2), CL(example_macro), CL(example).
{module, example}
3> [example:lookup(N) || N <- lists:seq(0, 3)]. [0,2,4,6] 4>

Yep. EMP2 is done.


The full listing:

-module(emp2).
-author("Philip Robinson").
-vsn('1.0').
-export([parse_transform/2]).

parse_transform(AST, _Options) ->
    Mods = lists:flatten([Mods || {attribute,_Line,macro_modules,Mods} <- AST]),
    lists:flatten([node_parse(Node, Mods) || Node <- AST]).
node_parse({attribute,Line,macro,{Mod,Fun,Args}}, _Mods) ->
    ast_from_results(parse_form, lists:flatten([apply(Mod,Fun,Args)|" "]), Line, []);
node_parse(Node={call,Line,{remote,_,{atom,_,Mod},{atom,_,Fun}},Args}, Mods) ->
    case lists:member(Mod, Mods) of
        true ->
            ArgsLiteral = [Value || {_Type,_Line,Value} <- Args],
            Results = lists:flatten([apply(Mod,Fun,ArgsLiteral)|". "]),
            case length(Results) of
                1 -> hd(Results);
                _ -> {block,Line,ast_from_results(parse_exprs,Results,Line,[])}
                end;
        false -> setelement(4,Node,node_parse(Args, Mods))
        end;
node_parse(Node, Mods) when is_list(Node) ->
    [node_parse(Element, Mods) || Element <- Node];
node_parse(Node, Mods) when is_tuple(Node) ->
    list_to_tuple([node_parse(Element, Mods) || Element <- tuple_to_list(Node)]);
node_parse(Node, _Mods) -> Node.

args_from_ast(AST) -> [Value || {_Type,_Line,Value} <- AST].

ast_from_results(FunParse, ResultsString, LineStart, ASTResults) ->
    case remove_leading_whitespace(ResultsString) of
        "" -> lists:flatten(lists:reverse(ASTResults));
        String ->
            {done,{ok,Tokens,LineEnd},StringRest} =
                erl_scan:tokens([], String, LineStart),
            {ok, AST} = erl_parse:FunParse(Tokens),
            ast_from_results(FunParse, StringRest, LineEnd, [AST|ASTResults])
        end.

remove_leading_whitespace([9 |String]) -> remove_leading_whitespace(String);
remove_leading_whitespace([10|String]) -> remove_leading_whitespace(String);
remove_leading_whitespace([32|String]) -> remove_leading_whitespace(String);
remove_leading_whitespace(    String ) -> String.

EMP2: Entirely painful compile-time macros for functions and expressions, in 45 lines of obscure, uncommented, and unreadable Erlang code.
(If you think that this code is bad, wait until you see EMP3.)


[1] Run-time for EMP2 is, of course, compile-time for the module that we are using EMP2 to transform.

Erlang Macro Processor (v2), Part IV

Okay, now we are getting somewhere. Time to expand some macros!

To begin with we will start with something easy, like duplicating EMP1's functionality. We already have code from EMP1 to expand the -macro attribute entries, but unfortunately we cannot just cut-and-paste the EMP1 code into EMP2; our AST-walking is slightly different and we need to adjust ast_reversed_results:

ast_from_results(ResultsString, LineStart, ASTResults) ->
   case remove_leading_whitespace(ResultsString) of
       "" -> lists:reverse(ASTResults);
       String ->
           {done,{ok,Tokens,LineEnd},StringRest} =
               erl_scan:tokens([], String, LineStart),
           {ok, AST} = erl_parse:parse_form(Tokens),
           ast_from_results(StringRest, LineEnd, [AST|ASTResults])
       end.

We change the -macro clause for node_parse to call the new function:

node_parse({attribute,Line,macro,{Mod,Fun,Args}}, _Mods) ->
   ast_from_results(lists:flatten([apply(Mod,Fun,Args)|" "]), Line, []);

And that obscene remove_leading_whitespace function has returned:

remove_leading_whitespace([9 |String]) -> remove_leading_whitespace(String);
remove_leading_whitespace([10|String]) -> remove_leading_whitespace(String);
remove_leading_whitespace([32|String]) -> remove_leading_whitespace(String);
remove_leading_whitespace(    String ) -> String.

The only difference between ast_from_results and ast_reversed_results is that ast_from_results keeps the resulting AST in the same order as the input ResultsString argument (it kindly reverses its already-reversed results for us before passing them back).

Unlike EMP1, EMP2 does NOT want to receive the results of the expanded AST in reversed order. We are not following the "build a list in reverse and then reverse the result" model for our AST (which works just fine for traversing the top level only), but rather using a recursive descent model for AST parsing. In this situation we need to keep the results in the order that they appear.


Now we have the EMP2 module reproducing the functionality of EMP1, and at only a few more lines of code. The only thing left to do is identify macro function calls, apply them, and insert the parsed results into the AST in place of the original call.

Ha!


For remote function calls we have two situations to handle:

• The remote function call is to a macro, and
• The remote function call is not to a macro.

The easier case is when the remote function call is not to a macro function. We pretty much just want the default tuple node function to run on the node, but we cannot (easily) get there because this more-specific function clause will have intercepted the node before the default code gets a chance to run on it.

We could encapsulate the common default code in another function (or a substitution macro), but for simplicity's sake I will just build the required node in place with the setelement function. It is not a large amount of code:

node_parse(Node={call,Line,{remote,_,{atom,_,Mod},{atom,_,Fun}},Args}, Mods) ->
   case lists:member(Mod, Mods) of
       true ->
           io:format("Function-level macro call: ~w~n", [Node]),
           Node;
       false -> setelement(4,Node,node_parse(Args, Mods))
       end;

Next up: The final installment - expanding remote macro function calls.

Erlang Macro Processor (v2), Part III

The top level of the AST is a list of nodes, rather than a node in its own right, so we might write our first attempt at an[other] AST walker like this:

parse_transform(AST, _Options) ->
    Mods = lists:flatten([Mods || {attribute,_Line,macro_modules,Mods} <- AST]),
    lists:flatten([node_parse(Node, Mods) || Node <- AST]).

node_parse(Node, _Mods) -> Node.

The parse_transform function calls node_parse on each top-level node in the AST. It calls lists:flatten on the result because - as we already know - the EMP1-variety of top-level macro expansion may return more than one function definition from a single macro call. These definitions all need to be at the same "height" as the others, so the resulting deep list of nodes needs to be flattened.

These two functions together will traverse the top level of the AST but not examine any sub-nodes. To do that we need to split the atom... er, node tuples, and parse each element in sequence:

node_parse(Node, Mods) when is_tuple(Node) ->
    list_to_tuple([node_parse(Element, Mods) || Element <- tuple_to_list(Node)]).

Now if we were to compile and run this on our example.erl file we would get a big fat error... it turns out that not every element in a node tuple is actually another node tuple (but we already knew that, too). Some of the elements are lists, and some of them are atoms or integers. A few extra clauses should take care of these conditions:

node_parse(Node, Mods) when is_list(Node) ->
    [node_parse(Element, Mods) || Element <- Node];
node_parse(Node, _Mods) -> Node.

Here is the whole module in one piece:

-module(emp2).
-export([parse_transform/2]).

parse_transform(AST, _Options) ->
    Mods = lists:flatten([Mods || {attribute,_Line,macro_modules,Mods} <- AST]),
    lists:flatten([node_parse(Node, Mods) || Node <- AST]).

node_parse(Node, Mods) when is_list(Node) ->
    [node_parse(Element, Mods) || Element <- Node];
node_parse(Node, Mods) when is_tuple(Node) ->
    [Type,Line|ListElements] = tuple_to_list(Node),
    Results = [node_parse(Element, Mods) || Element <- ListElements],
    list_to_tuple([Type,Line|Results]);
node_parse(Node, _Mods) -> Node.

And that is all we need to generically walk the entire AST.

Trapping the specific nodes we want to macro-expand is also rather trivial. We need to catch macro module attributes and remote function calls, and to do that we just add two new clauses to the node_parse function:

node_parse(Node={attribute,Line,macro,{Mod,Fun,Args}}, _Mods) ->
    io:format("Line ~B: EMP1-style macro attribute found.~n", [Line]),
    % Do macro-expansion of attribute's Mod, Fun, and Args values.
    Node;
node_parse(Node={call,Line,{remote,L,{atom,_,Mod},{atom,_,Fun}},Args}, Mods) ->
    io:format("Line ~B: EMP2-style remote function call found.~n", [Line]),
    % Test whether the remote call is to a macro module.
    % If so, expand it.  Otherwise traverse node as usual.
    setelement(4, Node, node_parse(Args, Mods));

Next up: Expanding the macros.

Erlang Macro Processor (v2), Part II

You know we need to do it eventually, so let's get the boring "find -macro_modules attributes and store their values" bit out of the way so we can move on to some more interesting stuff. Here we go:

-module(emp2).
-export([parse_transform/2]).

parse_transform(AST, _Options) ->
    Mods = lists:flatten([Mods || {attribute,_Line,macro_modules,Mods} <- AST]),
    io:format("Macro Modules: ~p~n", [Mods]),
    AST.

Ah, whoops. One of those list comprehension thingies seems to have slipped into the parse_transform function. To get rid of it we just have to change that line into something like this:

    Mods = lists:flatten(lists:map(
        fun ({attribute,_Line,macro_modules,Mods}) -> Mods;
            (_Node) -> []
            end,
        AST)),

Hmmm. On second thoughts, maybe we should keep the list comprehension.

I believe that list comprehensions are a relatively new feature in Erlang so you may not see too many of them in existing code, but they really are worth learning. (Erlang is in good company: Python and Haskell have list comprehensions too.)


Back from that tangent and to the program at hand, we see that the macro module names are being stored in an ordinary list. I expect that only a few macro modules (probably only one at most) will be specified in any given module, and looking for an element in a one-element list is pretty quick, so we should not be needing the indexing overhead of a dictionary. I also don't particularly mind if someone specifies a macro module more than once, or if a specified macro module is never used. (If we were really concerned about duplicate macro module names then we could use one of the list module functions to easily remove them.)

We could also roll the gathering of the macro_modules attributes up into the AST-walking code, but conceptually it is nicer to keep it up here and out of the way. Also, as this code only traverses the very top level of the AST it should be quite quick. Pattern-matching one entry per module attribute and function definition is not a computationally expensive task.

Right, the boring stuff is done; let's get into parsing that AST.


As I briefly mused at the bottom of a previous Atomiser post:

Rather than consisting of a bunch of pattern matching clauses, the walk_ast function could be made "smarter" by transforming the given node tuple into a list, and applying some rules-based logic to the elements of that list (from the third element onwards).

I reckon we could give this a go and see where we end up. (Either it will work and we have learned something new, or it won't work and we will have learned something new, so it is a win-win situation either way.)

You might recall that the Atomiser walk_ast function had a clause for each node type. This was a great way for me to implement the Atomiser because I got to see the AST nodes that made up my programs, but in the end it has turned out to be a pretty ugly function.

Here are a few lines of the walk_ast function as a quick refresher (the substitution macro actually makes the code nicer than it could be):

?WALK_AST({call,_Line,_Fun,Args}, Args); % Handles local and module calls.
?WALK_AST({'case',_Line,Test,Clauses}, [Test|Clauses]);
?WALK_AST({'catch',_Line,Expr}, Expr);
?WALK_AST({char,_Line,_Char}, []);

And those clauses go on (and on!) for about forty different node types...

I would much rather only have specific clause for handling each node that we are interested in, and use some generic code to handle the rest. But if we want to create some rules to manage these nodes generically then we had better find some patterns in all of that mess.

...

The first (and blindingly obvious) thing to notice about the nodes is that - without exception - they are all tuples. (I know, I know: I am a genius. Applause is not strictly necessary. Really. Oh, all right then, a little bit of applause is okay, if you insist.)

Two of these tuple nodes are not quite the same as the others: {error, Details} and {warning, Details}. In all of the other nodes the first element is the node type and the second element is the line number of the source file that the node appears in. After that there are a variable number of elements (possibly none) with node-specific meanings.

We are interested in catching -macro attributes (so EMP2 can do the work of EMP1) as well as remote function call nodes that are calling a macro function. Everything else is irrelevant, except that we want to recursively descend into sub-nodes to keep searching for other remote macro function calls.

If we take a closer look at the elements of nodes we will note that the element is always either a list, a tuple, or atomic (i.e.: an atom or an integer). These elements might have a special meaning to the compiler (depending on their location in the current node tuple) but to us they are just potential sub-nodes. If the node does not match an attribute or remote function call pattern then the elements have no meaning to EMP2 and we can treat them as homogenous lumps of node matter.

Of the additional elements in a node (if any), they are either

• a list, which we can parse as its own sub-AST,
• a tuple, which we can parse as another node, or
• atomic (or integer), which we can pass back as-is.

I think that all of these notes are probably enough to get us started coding.

Erlang Macro Processor (v2), Part I

EMP1 is all well and good, but it does have more than its fair share of idiosyncratic behaviour[1]:

• EMP1 can only be used to create full functions at the top level of a module. This makes it a bit more difficult to use than strictly necessary, especially if we only want to generate a term to use within a function.
• Arguments passed to the macro must be literal values - no function calls allowed!
• Macros must be defined in a separate module, which must be compiled before the macro-using module is compiled.

Quite frankly that first point bugs the hell out of me. I really should not have to write a macro that returns an entire function definition if I only need to generate a small portion of a function.

Today we will begin to tackle this issue with EMP2, but before we dive straight into the parse_transform code I would like to spend a few moments updating our example code. The rewrite will make the example_macro.erl and example.erl modules use the as-yet-unwritten EMP2 module functionality. I probably won't explicitly show it in these posts, but the compile errors I get from running EMP2 over example.erl will have a big influence over the direction that its development takes.


We will still need a separate macro module, but the macro function will only generate the lookup table itself rather than return a whole function definition:

-module(example_macro).
-export([lookup_binary/1]).

lookup_binary(Size) ->
    [[$,,FirstVal]|NumberString] = lists:map(
        fun(Offset) -> io_lib:format(",~B", [Offset * 2]) end,
        lists:seq(0, Size - 1)),
    "<<" ++ [FirstVal] ++ NumberString ++ ">>".

We have lost the code that produces the whole function and only kept our lookup binary creation function, which also seems to have picked up a jaunty little Size argument from somewhere. As before, each element's value is twice its offset (modulo 256: we are only storing bytes after all).

To check that the new macro code works correctly:

1> CL = fun(F) -> c(F), l(F) end.
#Fun
2> CL(example_macro).
{module,example_macro}
3> M = fun(R) -> io:format("~s~n", [lists:flatten(R)]) end.
#Fun
4> M(example_macro:lookup_binary(4)).
<<0,2,4,6>>
ok
5>

And we also have to rewrite the module that calls this lookup macro:

-module(example).
-export([lookup/1]).

-compile({parse_transform, emp2}).
-macro_modules([example_macro]).

lookup(Offset) ->
    <<_:offset/binary,value:8/integer,_/binary>> =
        example_macro:lookup_binary(4),
    Value.


This does look a lot nicer than the EMP1 version. Only the snippet of code that needs to be dynamically generated is in the macro module; the rest of the code is in the standard module where it belongs, and the macro call is in a much more appropriate place - inside the function that uses it - than lurking within a module attribute.

With EMP1 we had to peek inside another module to see that a lookup/1 function was being generated, but here we can see that fact already in front of us. We can even guess that a binary term will be created just from the context around the macro call.

Note that 'emp1' has changed to 'emp2' in the parse_transform compiler directive, and that we need a new 'macro_modules' module attribute to tell EMP2 which remote function calls are to be expanded at compile-time.

Once we have written EMP2 and compiled all the modules,we should be able to run the lookup function and receive the same results as we did before:

1> lists:map(fun(N) -> example:lookup(N) end, lists:seq(0, 3)).
[0,2,4,6]
2>


We shall see.


[1] And I cannot have all that competition floating around out there, you know.