Are recursive closures tail call optimized?

Questions / Help
,
1

Would this code be tail call optimized?

  def loop do
    inner = fn func, idx, propulsor ->
              if idx === 1000 do
                propulsor + 1
              else
                :timer.sleep(1000)
                func.(func, idx + 1, propulsor)
              end
            end

    outer = fn func, idx ->
              # This should approximately turn out to be 24 hours
              if idx === 96 do
                IO.puts("Updating Cache")
                InstagramApi.main()
                func.(func, 0)
              else
                # Generates new index after a timeout of 1000 seconds
                new_idx = inner.(inner, 0, idx)

                func.(func, new_idx)
              end
            end

    outer.(outer, 0)
  end
2

It does not seem to get optimized, based on the following steps.

Start with a file bleh.ex:

defmodule InstagramApi do
  def main do
    IO.puts("Instagram API")
  end
end

defmodule Bleh do
  @compile :S

  def loop do
    inner = fn func, idx, propulsor ->
              if idx === 1000 do
                propulsor + 1
              else
                :timer.sleep(1000)
                func.(func, idx + 1, propulsor)
              end
            end

    outer = fn func, idx ->
              # This should approximately turn out to be 24 hours
              if idx === 96 do
                IO.puts("Updating Cache")
                InstagramApi.main()
                func.(func, 0)
              else
                # Generates new index after a timeout of 1000 seconds
                new_idx = inner.(inner, 0, idx)

                func.(func, new_idx)
              end
            end

    outer.(outer, 0)
  end

  def named_loop(idx \\ 0) do
    if idx === 96 do
      IO.puts("Updating Cache")
      InstagramApi.main()
      named_loop(0)
    else
      new_idx = named_inner(0, idx)

      named_loop(new_idx)
    end
  end

  def named_inner(idx, propulsor) do
    if idx === 1000 do
      propulsor + 1
    else
      :timer.sleep(1000)
      named_inner(idx + 1, propulsor)
    end
  end
end

Compile it with elixir bleh.ex. It will print an error message:

** (CompileError) bleh.ex: could not compile module Bleh. We expected the compiler to return a .beam binary but got something else. This usually happens because ERL_COMPILER_OPTIONS or @compile was set to change the compilation outcome in a way that is incompatible with Elixir

That’s expected, because the @compile :S flag causes the compiler to dump a BEAM-assembly file at bleh.ex.S and stop.

There’s a lot of detail that’s not directly relevant in the assembly; see the BEAM Book for more info. The important thing to look for is the definitions of the functions.

The closures for outer and inner are compiled to functions named -loop/0-fun-1- and -loop/0-fun-0- respectively; you can check by looking at the func_info line that shows where they came from in the source.

inner is the shorter of the two:

{function, '-loop/0-fun-0-', 3, 28}.
  {label,27}.
    {line,[{location,"bleh.ex",11}]}.
    {func_info,{atom,'Elixir.Bleh'},{atom,'-loop/0-fun-0-'},3}.
  {label,28}.
    {test,is_eq_exact,{f,29},[{x,1},{integer,1000}]}.
    {line,[{location,"bleh.ex",13}]}.
    {gc_bif,'+',{f,0},3,[{x,2},{integer,1}],{x,0}}.
    return.
  {label,29}.
    {allocate,3,3}.
    {move,{x,0},{y,0}}.
    {move,{x,1},{y,1}}.
    {move,{x,2},{y,2}}.
    {move,{integer,1000},{x,0}}.
    {line,[{location,"bleh.ex",15}]}.
    {call_ext,1,{extfunc,timer,sleep,1}}.
    {line,[{location,"bleh.ex",16}]}.
    {gc_bif,'+',{f,0},0,[{y,1},{integer,1}],{x,1}}.
    {move,{y,0},{x,3}}.
    {move,{y,2},{x,2}}.
    {move,{y,0},{x,0}}.
    {call_fun,3}.
    {deallocate,3}.
    return.

The signal that it’s not tail-call optimized is the call_fun / deallocate / return sequence.

For comparison, named_inner does the same thing but gets different optimization:

{function, named_inner, 2, 13}.
  {label,12}.
    {line,[{location,"bleh.ex",49}]}.
    {func_info,{atom,'Elixir.Bleh'},{atom,named_inner},2}.
  {label,13}.
    {test,is_eq_exact,{f,14},[{x,0},{integer,1000}]}.
    {line,[{location,"bleh.ex",51}]}.
    {gc_bif,'+',{f,0},2,[{x,1},{integer,1}],{x,0}}.
    return.
  {label,14}.
    {allocate,2,2}.
    {move,{x,1},{y,0}}.
    {move,{x,0},{y,1}}.
    {move,{integer,1000},{x,0}}.
    {line,[{location,"bleh.ex",53}]}.
    {call_ext,1,{extfunc,timer,sleep,1}}.
    {line,[{location,"bleh.ex",54}]}.
    {gc_bif,'+',{f,0},0,[{y,1},{integer,1}],{x,0}}.
    {move,{y,0},{x,1}}.
    {call_last,2,{f,13},2}. % named_inner/2

The assembly instead ends with a call_last (which also does a deallocate) and no return at all.

3 Likes