Functional Imperative Programming with Elixir (2018), Hacker News

March 18, 2018

I recently found myself wishing for the simple convenience of awhileloop in Elixir. I had a test where I wanted to loop and test a condition, and either break out of that loop, or time out after some period. Writing this in the form of a recursive function is relatively easy, but is not really fully general:

def while (predicate, timeout)   when is_function (predicate, 0) and is_integer (timeout) do   while (predicate, timeout, System.monotonic_time (: milliseconds)) end defp while (predicate, timeout, started) when timeout>0 do   if predicate. () do     now=System.monotonic_time (: milliseconds)     elapsed=now - started     while (predicate, timeout - elapsed, now)   else     : ok   end end defp while (_predicate, _timeout, _started) do   exit (: timeout) end

You could then use this in a test like so:

test "wait until node is available",% {peer: some_node} do   assert: ok=while (fn ->Node.ping (some_node)!=: ping end, 30 _ 000) end

This would loop untilNode.ping/1returns: ping, or 30 seconds passes, at which point it would exit and fail the test. That’s… acceptable, but it reads a bit weird, and actually has a rather awkward issue in that we can’t slow the loop down to only check once a second, rather than as fast as the runtime will executeping. To do that, we’d need to extend the definition ofwhileto support another function argument, which would be executed if the predicate returns true, and would allow us to insert a call to: timer.sleep / 1or something on each iteration.

As soon as I saw this, I knew I was going to end up writing a macro for it. First,whileis a familiar concept coming from imperative languages, and though technically not needed in Elixir, it does still have a place as a high-level abstraction of a common form of recursive function, where you need to loop until some condition is true, and reimplementing that from scratch each time is a bit annoying. Secondly, with a macro, we could make this look just likewhilein an imperative language, and once I saw it in my head, I knew that at the very least it was going to make for a fun experiment. I also figured that while I was building the macro, I could push the limits a bit and see if we can add mutation to the implementation as well (not real mutability, but at least the semblance of it).

We want this macro to embrace the functional aspects of the language, while providing some of the conveniences of the imperative approach. As a bonus, building in the concept of timeouts to the implementation makes our version ofwhilefar more powerful than your average implementation! Let’s take a look at a few examples of what I had in mind:

# Simple infinite loop while true do   : ok end  # Loop with initializer   accumulator 5=while n=1, nn   1 end  # Loop with timeout condition while true do   : ok after   30 _ 000 ->    exit (: timeout) end  # Loop with timeout and initializer   accumulator while n=1, n    exit (: timeout) end  # Loop with timeout condition but no body while true do after 30 _ 000 ->  exit (: timeout) end

Much more familiar! There are a few syntactic differences from your standardwhilein something C-like, but for the most part there are really no surprises here. I also wanted this to compile down to a form that was actually optimal, i.e., I didn’t want anonymous functions for the predicate, body, and after body, where each iteration would result in at least two function calls. Instead, it should compile down to a recursive function, with the minimal amount of branching based on which parts of the construct where used, eg, no timeout means that we don’t need to branch on the timeout value and calculate new times, etc .

The first problem here is that in order to use this in any arbitrary location, we can’t define a named function at the pointwhileis invoked, asdefisn’t valid within anotherdef; instead, we have to use an anonymous function, and Elixir does not yet support recursively invoking an anonymous function by the name it is bound to (even though Erlang does). Instead, we have to transform our definition of the anonymous function to combinator form, i.e., it has no free variables, and only refers to its parameters. Here is what I mean:

# Doesn't work, refers to the free variable `while` # which is bound _after_ the closure for the fun is created while=fn predicate ->  if predicate. () do     while (predicate)   else     : ok   end end while. (fn ->true end)  # This does, no free variables, we pass in the fun # to itself, so that it can call itself recursively while=fn pred, while ->  if predicate. () do     (predicate, while)   else     : ok   end end while. (fn ->true end, while)

So we know what we’ll have to structure the macro implementation to generate an anonymous function in combinator form. We have a solution for our first problem!

The next problem can be seen in the example above, thepredicateis another anonymous function, but what we really want is for the predicate to be a part of the definition of thewhilefunction itself, so that we avoid the function call overhead. This is pretty straightforward though, we just will just inject it into the definition ofwhile. Let’s stop here and implement the macro up until this point:

defmacro while (predicate, do: body) do   quote location:: keep, generated: true do     whilef=fn whilef ->      if unquote (predicate) do         unquote (body)         (whilef)       else         : ok       end     end     (whilef)   end end  # Usage Example while Node.ping (some_node)!=: ping do   : timer.sleep (1 _ 000) end

Not bad! A few notes:

If you aren’t familiar,location:: keepmakes sure the file / line from the quotation are what end up in traces, rather than the location the macro is invoked from. This means if we make a mistake, we’ll know where in the macro implementation things went south.
If you aren’t familiar with (quote) andunquote, I would stop here and go read thequotedocs, either viah quoteiniexor on HexDocshere

There are some problems here though, not to mention we haven’t yet added support for timeouts or “mutable” state. This is usable, but not ideal.

One of the biggest problems lies with the predicate itself: what if we changed the example to this:

n=1 while n

Can you spot the problem? The issue is that running this will loop forever, asnwill always equal1, the predicate will always see1, andn 1will always calculate2. The state from the body ofwhiledoes not affect the next evaluation of the predicate. We need to ensure that state is accumulated, by making the result of the body be passed along as another parameter to thewhileffunction; which also means we have to make the initializer part ofwhile, so that we can formally introduceninto the scope of both the predicate and the body, otherwise we can't ensure thatnis bound to the updated value, as it is out of scope. Let’s see what our macro looks like now:

defmacro while ({:=, _ [i|_]}=init, predicate, do: [{:->,_,_}]=body) do   quote location:: keep, generated: true do     whilef=fn whilef, acc ->      unquote (i)=acc       if unquote (predicate) do         acc2=          case unquote (i) do             unquote (body)           end         (whilef, acc2)       else         acc       end     end     (whilef, _=unquote (init))   end end  # Usage Example 5=while n=1, n  n   1 end

In the above, we ensure the initializer is just a simple assignment by matching on the AST, and for simplicity right now, I ‘m also matching to ensure that the body accepts the accumulator value using case clause syntax (egn ->...). You’ll notice we also bound the name of the initializer, so that we can cheat a little with theunquote (i )=accline, which, using our example, resetsnto the current state of the accumulator on each iteration . The bit at the bottom,_=unquote (init)will expand to_=n=1, which seems strange, but ensures that we don’t get a warning about an unused binding.

Of course the problem we have now is that our macro requires the use of the initializer and accumulating state in the body, still doesn ‘t supportafter, and isn’t flexible in the way I originally envisioned. This is fine though, since we’re about to fix that!

First, let’s add support forAfter:

defmacro while ({:=, _ [i|_]}=init, predicate, [do: [{:->,_,_}]=body, after: [{:->,_,[[timeout], after_body]}]) do   quote location:: keep, generated: true do     whilef=fn       whilef, acc, timeout, started when timeout>0 ->        unquote (i)=acc         if unquote (predicate) do           acc2=            case unquote (i) do               unquote (body)             end           now=System.monotonic_time (: milliseconds)           elapsed=now - started           (whilef, acc2, timeout - elapsed, now)         else           acc         end       _, _, _, _ ->        unquote (after_body)     end     now=System.monotonic_time (: milliseconds)     whilef. (whilef, _=unquote (init), unquote (timeout), now)   end end  # Usage Example 5=while n=1, n  n   1 after   5 _ 000 ->    exit (: timeout) end

Similar to the previous iteration of the macro, we’re matching against the AST to ensure theafterclause uses thetimeout ->bodysyntax, and that only one timeout clause is allowed. We’re not validating the timeout, or dealing with invalid constructs very well though, for that we need to do the pattern matching in the macro body so that we can catch common mistakes and raise more helpful errors. You’ll notice that we calculate the elapsed time on each iteration before continuing, that way we can just jump straight to theafterclause if the timeout reaches zero.

We’re almost done! We have a few items to address to make this a “complete” implementation:

Put this all in a module and document it
Support optionalafter, optionaldo, optional initializer / accumulator so that we can arrive at the various forms I originally sketched out
Support multiple accumulator clauses withindoso that pattern matching is supported.
Compile to an optimal form, where no unnecessary function calls, branching, or work is performed
Validate the constructs used so that invalid forms are not permitted and raise a useful compilation error , egaftercan only accept a positive integer for a timeout, and only one timeout clause is allowed. We could theoretically support multiple, but I don’t think that is useful for this exercise.

Let’s take a look at the final form with all of those points addressed:

defmodule LanguageExtensions.While do   @moduledoc "" "   Adds support for `while` to Elixir.    See the docs for `# {__ MODULE __}. While / 2` for more information.    ## Example        use # {__ MODULE__}        ...        while n=1, n        if n==4 do           break         end         : timer.sleep (1 _ 000)         n   1       after         5 _ 000 ->          : timeout       end   "" "    defmacro __using __ (_) do     quote do       import unquote (__ MODULE__)     end   end    @doc "" "   Intended for use within `while`, this will break out of iteration,   returning the last accumulator value as the result of the `while` expression.        iex>while true do break end       : ok   end   "" "   defmacro break do     quote do       throw {unquote (__ MODULE__),: break}     end   end    @doc "" "   A looping construct, looks like so:        # Simple infinite loop (never terminates)       while true do         : ok       end        # Loop with accumulator       iex>while n=1, nn   1 end       5        # Loop with timeout condition       iex>while true do       ...>: ok       ...>after       ...>1 _ 000 ->      ...>: timeout       ...>end       : timeout        # Loop with timeout and accumulator       iex>while n=1, nif n==4 do       ...>break       ...>end       ...>: timer.sleep (1 _ 000)       ...>n   1       ...>after       ...>5 _ 000 ->      ...>: timeout       ...>end       4        # Loop with timeout condition but no body (exits with: timeout)       iex>while true do after 1 _ 000 ->: timeout end       : timeout   "" "   # A simple while loop   defmacro while (predicate, do: block) do     quote location:: keep do       while (_=: ok, unquote (predicate), [do: unquote(block), after: nil])     end   end    # A loop   timeout block   defmacro while (predicate, [do: block, after: after_block]) do     quote location:: keep do       while (_=: ok, unquote (predicate), [do: unquote(block), after: unquote(after_block)])     end   end    # An accumulator loop   defmacro while (init, predicate, do: block) do     quote location:: keep do       while (unquote (init), unquote (predicate), [do: unquote(block), after: nil])     end   end    # An accumulator loop   timeout block   defmacro while (init, predicate, [do: block, after: after_block]) do     # Validate initializer     {init_name, init_expr}=      case init do         {:=, env, [init_name | init_expr]} ->          {init_name, {: __ block__, env, init_expr}}         {_, env, _} ->          raise CompileError,             description: "expected an initializer of the form` n=`, got: # {Macro.to_string (init)}",             file: Keyword.get (env,: file, __ENV __. file),             line: Keyword.get (env,: line, __ENV __. line)       end      # Validate and extract timeout / after body     # Timeout must be a positive integer     # After body only allows one timeout clause     {timeout, after_block}=      case after_block do         [{:->, _, [[timeout], after_body]}] when is_integer (timeout) and timeout>=0->          {timeout, after_body}          [{:->, env, [[_], _after_body]}] ->          raise CompileError,             description: "expected a positive integer timeout in` after` ",             file: Keyword.get (env,: file, __ENV __. file),             line: Keyword.get (env,: line, __ENV __. line)          [{:->, env, _}, _ | _] ->          raise CompileError,             description: "multiple timeouts are not supported in` after` ",             file: Keyword.get (env,: file, __ENV __. file),             line: Keyword.get (env,: line, __ENV __. line)          [{_, env, _} | _] ->          raise CompileError,             description: "multiple timeouts are not supported in` after` ",             file: Keyword.get (env,: file, __ENV __. file),             line: Keyword.get (env,: line, __ENV __. line)          nil ->          {nil,: ok}       end      # Determine the type of while block we're building     {block_type, block}=      case block do         # Empty block, i.e. `while true do after ... end`         {: __ block__, _, []} ->          {: empty,: ok}          # Has one or more accumulator patterns         [{:->, _, [[_binding], _body]} | _]=blk ->          {: acc, blk}          # No accumulator         _other ->          {: noacc, block}       end      timeout_calc=      if is_nil (timeout) do         quote location:: keep, generated: true do           now=start_time         end       else         quote location:: keep, generated: true do           now=System.monotonic_time (: milliseconds)           elapsed=now - start_time           after_time=after_time - elapsed         end       end       # Construct the body of the function     body=      case block_type do         # If there is no `do` body, then skip it entirely         : empty ->          quote location:: keep, generated: true do             if unquote (predicate) do               import unquote (__ MODULE__), only: [break: 0]               unquote (timeout_calc)               f. (after_time, now,: ok, f)             else               : ok             end           end          # If we're not accumulating, skip the unnecessary pattern match         # we need when managing the accumulator         : noacc ->          quote location:: keep, generated: true do             if unquote (predicate) do               import unquote (__ MODULE__), only: [break: 0]               acc2=unquote (block)               unquote (timeout_calc)               f. (after_time, now, acc2, f)             else               acc             end           end          # If we're managing an accumulator, we need to use the case         # statement to         : acc ->          quote location:: keep, generated: true do             unquote (init_name)=acc             if unquote (predicate) do               import unquote (__ MODULE__), only: [break: 0]               acc2=                case unquote (init_name) do                   unquote (block)                 end               unquote (timeout_calc)               f. (after_time, now, acc2, f)             else               acc             end           end       end      # Construct the actual function, tag the quoted AST with     # generated: true to make sure unused bindings and such are     # not warned     quote location:: keep, generated: true do       fun=fn         # Since nil is always>0 due to Erlang sort order         # We can use this to represent both infinite timeouts, and         # finite timeouts which haven't expired         after_time, start_time, acc, f when after_time>0 ->          try do             unquote (body)           catch             : throw, {unquote (__ MODULE__),: break} ->              acc           end          _after_time, _start_time, acc, _f ->          try do             unquote (after_block)           catch             : throw, {unquote (__ MODULE__),: break} ->              acc           end       end       now=System.monotonic_time (: milliseconds)       fun. (unquote (timeout), now, unquote (init_expr), fun)     end   end end

That’s it! I’ve documented the code a bit with comments describing the various changes, but I hope for the most part you will be able to see the evolution from our last version. We did the following:

while / 3

while

We extracted the function head matches into the body so that we can match on valid uses of different constructs and raise compilation errors with useful descriptions and file / line numbers for debugging.
We break apart the two major types ofwhileusage, with timeouts, and without timeouts, and construct the body differently based on the type so that no extra work is done while iterating
We break apart the type ofwhilebody, whether it is empty, accumulates state , or does not accumulate state, and construct the body optimally for each case. This is especially necessary if we want to support optional accumulation – thepat ->exprsyntax will not be valid outside of thecaseblock we wrap it in when building up the accumulator form, but we want to avoid the branch match if we don’t care about the accumulator and just want to return the value of the body on each iteration. So we base the type of body we generate based on the syntax of thedo (block.)
Definedbreak / 0which just throws a special error for us to catch and break out of the loop early. We do this transparently to the user ofwhile, and do so in such a way that the accumulated value is returned.

The final version of the macro is a bit long due to the optimizations we are performing. If one wanted a simpler implementation, you could support fewer optional parts, or be willing to calculate elapsed time on each iteration and always branch on the accumulator so that the accumlator / no accumulator forms are the same. In any case, I wanted to pull out all of the stops and see where we got.

I’m not sure I would recommend using this macro generally, but it was a fun experiment, and I love the opportunity to stretch the macro muscle a bit, especially with one like this which really shows how you extend the syntax of the language via macros, just like howwithandforare built.

I hope you enjoyed reading this! It isn’t often I write something up, but this seemed like too much fun to resist:)

A few useful tips for writing macros:

Have twoiexwindows open, one for testing, one for docs. I’m constantly experimenting with quoting expressions and reviewing the AST, compiling and importing the macro I’m working on so that I can test it, and usingHto pull up docs to double check what I’m doing
To see what kind of AST is produced for some syntax, just use one of theiexwindows and type inquote do (end) and it will spit out the quoted form of the expression.
You can get the pretty printed form of a quoted expression for easier reading withquoted |>Macro.to_string |>IO.puts. As of 1.6 you can also doquoted |>Macro.to_string |>Code.format_string! |>IO.putsto format the code using the new formatter.
If there is a compile error coming from your macro, get a quoted usage of it withquote doend, and useMacro.expand_once (quoted, __ENV __)to see a single expansion of the macro, which will help you see how the macro is actually being converted into Elixir syntax. You can chain this call as well, or just useMacro.expand (quoted, __ENV __)to see the fully expanded AST.
Read up on quoting, unquoting, splicing, and: bind_quotedbefore you get started. Understanding those are critical to not only know what you are doing, but also saving yourself a lot of pain when trying to figure out why something isn’t working the way you thought it would. Things can get quite complex when you are working with nested macros, which is almost always the case anyway, as much of Elixir syntax itself is written using macros. Anytime you find yourself confused by the behavior of your macro, it pays to go back and re-read the docs, because it is almost certainly a case of something you overlooked.