Recursive anonymous functions

I do not know the exact state at this time, but I did have a discussion with @sasajuric and @michalmuskala about this while at the Code BEAM Lite Amsterdam.

Some notes:

1. There is no current syntax in Elixir to define the ‘named anonymous functions’ that were added to Erlang in OTP 17 directly.
2. However, one can argue that it is not really required. In Erlang, a problem was that you were unable to define a module inside the shell, only being able to define one-off anonymous functions. That really makes it difficult when you want to test out a piece of code that should call itself recursively. (In Elixir’s IEx this is not a problem, as it allows defining new modules in the shell.)
3. Of course, the ‘classical’ way to do this, the Y-Combinator, is a possibility both in Erlang and Elixir. However, using this is (a) rather slow and (b) beginner-unfriendly, because it is difficult to read. But then again, it’s manually-entered shell-code we are talking about, in which these arguments might not be as strong. When writing modules, why not, instead of a self-recursing anonymous function, define it as a private, named function instead?
4. It is possible to define an macro that wraps a function in a similar way that the Y-Combinator construction does, in a way that might be more understandable for users (say fn_rec. No alterations to Elixir’s core are necessary to do this. (But this also does not use Erlang’s ‘named anonymous functions’).

An example of how (4) could look when used would be:

fn_rec
  _, 0, acc -> acc
  myfun, num, acc -> myfun.(num - 1, acc + 1)
end

(although when using this syntax, I’d prefer writing it as:

fn_rec myfun, num, acc ->
  case num  do
   0 -> acc
   _ -> myfun.(num - 1, acc + 1)
end

)

or possibly:

fn_rec myfun do
   0, acc -> acc
   num, acc -> myfun.(num - 1, acc + 1)
end

One of the things I do not know, is how performance compares between:

• using a y-combinator-style approach (where no new names are defined).
• using an indirectly-threaded approach where the macro defines a new name
• using the Erlang’s ‘named anonymous functions’ directly.

(I expect the y-combinator to be slow, and directly using the Erlang feature to be the fastest, but I do not know how by how much, or if it is enough to justify adding it as a built-in construct to the Elixir language itself.)

That’s really interesting. I’m too new to math behind functional programming, so Y combinator isn’t for me now, but I initially thought about slightly different approach: new keyword $, which would always refer to the current function. This would not only allow named anonymous function, but shorten a bit plain functions.

For example:

def len(x) when is_list(x), do: _len(x, 0)

defp _len([], acc), do: acc
defp _len([_ | t], acc) , do: $(t, acc+1)

I’m typically not fond of introducing new keywords for every small feature, but this could be really helpful in writing clean and concise code.

iex(1)> f = fn                      
...(1)>   (_, 0, acc) -> acc             
...(1)>   (g, num, acc) -> g.(g, num-1, acc+1)
...(1)> end
#Function<18.128620087/3 in :erl_eval.expr/5>
iex(2)> 
nil
iex(3)> f.(f,10,10)
20
iex(4)> 

Functions are values …

I know you can pass function as
argument, even to itself, but in that way you’re leaking implementation details and introducing possibly needless parameter. It’s a problem? In most cases not really, but this solution is a bit hacky.

The disadvantage of introducing $ is twofold:

1. It is a new ‘keyword’ to learn; you will not be able to see what happens simply by reading the code. You have to have learned about what it does beforehand.
2. Actually, $ itself it is not a keyword but an operator (a symbol), which means that it is even more difficult to find out what it means:

• It does not convey a meaning itself. (which a keyword like this_function would do)
• It is difficult to search for, because $ is overloaded to mean many different things in different contexts, and because many search-tools do not work with non-alphanumeric input.

So:

Introducing $ is bad because it is unreadable.
Introducing this_function or similar still is bad, because it still is a name that appears out of thin air, as well as having to be introduced as a new language feature. (Adding a language feature is remarkable easy, but changing or removing a feature is extremely difficult).

So either we try very hard to get it ‘right’, or we decide that this is not worth it and keep this functionality to be implemented in library-land.

As to get some intuition for the Y-combinator: In a language where we can refer to things by name, it could be defined as

y1 = fn fun -> fn a -> fun.(fun, a) end end
y2 = fn fun -> fn a, b -> fun.(fun, a, b) end end
y3 = fn fun -> fn a, b, c -> fun.(fun, a, b, c) end end

(Obviously, a different variant would be needed for each arity. In the example you see definitions it for arity-1 up to arity-3. This is the main reason why we could use a macro, because it would take care of the non-matching arities for us).

1> G = fun                  
1>   F (0, Acc) -> Acc;        
1>   F (Num, Acc) -> F(Num - 1, Acc + 1)
1> end.
#Fun<erl_eval.36.128620087>
2> G(10,10).
20
3>

Even though this feature now exists in Erlang the points are:

1. There already is a solution in Elixir (and Erlang pre-17.0) that works even if it isn’t elegant.
2. How often does a real need for recursive anonymous functions actually come up, given that recursion is well supported with named functions within actual code (rather than the shell)?

Erlang and by extension Elixir are pragmatic languages.

I contend that anonymous functions are an overused feature which are even more prevalent in Elixir because of the existence of the shorthand notation.

I see the primary value of an anonymous function in it’s closure (i.e. its connection to the scope that created it) - that should be the reason for using it. More often than not they are used simply for notational convenience even though quite often code becomes less readable.

The Erlang named anonymous function example can be quite easily emulated with a mixture of an anonymous function for its closure and a named function to do the real work:

# file: Demo.ex
# Original: https://learnyousomeerlang.com/higher-order-functions#highlighter_833032
#
defmodule Demo do
  def prepare_alarm(room) do
    IO.puts("Alarm set in #{room}")
    fn -> loop(room) end
  end

  defp loop(room) do
    IO.puts("Alarm tripped in #{room}! Call Batman!")
    Process.sleep(500)
    loop(room)
  end
end

iex(1)> c("Demo.ex")
[Demo]
iex(2)>  alarm_ready = Demo.prepare_alarm("bathroom")
Alarm set in bathroom
#Function<0.61175415/0 in Demo.prepare_alarm/1>
iex(3)>  alarm_ready.()
Alarm tripped in bathroom! Call Batman!
Alarm tripped in bathroom! Call Batman!
Alarm tripped in bathroom! Call Batman!

BREAK: (a)bort (c)ontinue (p)roc info (i)nfo (l)oaded
       (v)ersion (k)ill (D)b-tables (d)istribution
a

We can use macro to generate code like f.(f, …)

sum =
  make_rec(fn
    [], result -> result
    [num | next], result -> __REC__(next, num + result)
  end)

IO.puts(sum.([1, 2, 3], 0))

Here is the implementation

defmodule Rfn do
  defmacro make_rec({:fn, ctx, patterns}) do
    arity = get_arity(patterns)
    new_patterns = patterns |> Enum.map(&insert_rec_fn/1)
    ast = {:fn, ctx, new_patterns}

    quote do
      f = unquote(ast)
      make_fn_arity(f, unquote(arity))
    end
  end

  defmacro make_fn_arity(f, arity) do
    {:&, [], [{{:., [], [f]}, [], [f | 1..arity |> Enum.map(&{:&, [], [&1]})]}]}
  end

  defp insert_rec_fn({:->, _, [_arg_list, _]} = pattern) do
    {pattern, mod?} =
      Macro.postwalk(pattern, false, fn
        {:__REC__, _, arg_list}, _ when is_list(arg_list) ->
          re = {{:., [], [{:rec__, [], nil}]}, [], [{:rec__, [], nil} | arg_list]}
          {re, true}

        other, mod? ->
          {other, mod?}
      end)

    arg_name =
      if mod? do
        :rec__
      else
        :__REC__
      end

    update_in(pattern, [Access.elem(2), Access.at(0)], &[{arg_name, [], nil} | &1])
  end

  defp get_arity([{:->, _, [arg_list, _]} | _]) do
    length(arg_list)
  end
end

When generating a set of Stream.resource/3 functions through a single function call, you might want to parameterize an anonymous recursive function with the closure and it will seem natural – at least until disappointed Google searches lead to this thread. Always plenty of ways to do it, but I thought the solution was elegant.

I used your recommendation to make an exercise from the “Programming Elixir” book,
and I can really see myself applying the technique in real code.

defmodule Example do 

def max([]), do: nil

def max([head | tail]) do 
  build = fn 
    ( b, [h | t], accum ) when h > accum -> b.(b, t, h)
    ( b, [_h | t], accum ) -> b.(b, t, accum)
    ( _b, [] , accum ) -> accum
  end 

  build.(build, tail, head)
end 


end 

Agreed!

I think it’s pretty elegant as-is.