Does elixir use tail recursion automatically or the programmer must do it manually to optimize the algorithm ?
And therefore previous calculated calls should be stored in a map ?
Elixir has tail call optimisation, but for it to happen, it must obviously be a tail call. So I’d say it’s part automatic and part manual. I don’t think there are any heuristics to change code to tail recursive if it isn’t already.
Ok, because in python I used to save previous calculations in a dictionary (key-value elements). And before every recursive call (key) I first check if the calculation (value) was already done.
There is something similar in FP, it is called memoization.
http://rocket-science.ru/hacking/2017/11/23/idiomatic-function-memoization-in-elixir
That would actually be a dreadfully slow way to do that. Instead you’d want to use ETS.
TCO is built in to the VM itself, it is entirely and fully tail call optimized.
You’d probably want to use ETS for that (that has nothing to do with TCO at all).
Contrasting the three approaches:
defmodule Demo do
# 1. body recursion, i.e. not tail call optimized
def fib(0),
do: 0
def fib(1),
do: 1
def fib(n) when n > 1 and is_integer(n),
do: fib(n-2) + fib(n-1)
# 2. utilizing "last call optimization"
# http://erlang.org/pipermail/erlang-questions/2016-October/090663.html
defp fib_lco(_, acc, i, n) when i == n,
do: acc
defp fib_lco(fi_2, fi_1, i, n) when i < n,
do: fib_lco(fi_1, fi_2 + fi_1, i + 1, n)
def fib_lco(0),
do: 0
def fib_lco(1),
do: 1
def fib_lco(n) when n > 1 and is_integer(n),
do: fib_lco(fib_lco(0), fib_lco(1), 1, n)
# 3. using a result cache
defp fib_mem_fill(_, fi_1, i, mem, n) when i > n do
{fi_1, mem}
end
defp fib_mem_fill(fi_2, fi_1, i, mem, n) do
fi = fi_2 + fi_1
fib_mem_fill(fi_1, fi, i+1, Map.put(mem, i, fi), n)
end
defp fib_mem_fill(n, mem) do
with i <- Map.size(mem),
{:ok, fi_2} <- Map.fetch(mem, i - 2),
{:ok, fi_1} <- Map.fetch(mem, i - 1) do
fib_mem_fill(fi_2, fi_1, i, mem, n)
else
_ -> # unexpected lookup failure - start fresh
fib_mem_fill(0, 1, 2, %{0 => 0, 1 => 1}, n)
end
end
def fib_mem(n, mem \\ %{0 => 0, 1 => 1}) when n >= 0 and is_integer(n) do
with {:ok, result} <- Map.fetch(mem, n) do
{result, mem}
else
_ -> # not found
fib_mem_fill(n, mem)
end
end
# "show"" functionality
def show(name,n,f,extract) do
result = f.(n)
IO.puts("#{name}(#{n}): #{extract.(result)}")
result # needed for fib_mem
end
defp extract({result,_}), do: result
defp extract(x), do: x
defp inject(nil), do: &(fib_mem(&1)) # i.e. use default argument
defp inject(mem), do: &(fib_mem(&1, mem))
def show2(n, mem \\ nil) do
show("fib_lco", n, &fib_lco/1, &extract/1)
show("fib_mem", n, inject(mem), &extract/1) # returns {result, mem}
end
def show3(n, mem \\ nil) do
show("fib", n, &fib/1, &extract/1)
show2(n, mem) # returns {result, mem}
end
def show_list(mem, list, show) do
show_entry =
fn (n, mem_map) ->
{_, next_map} = show.(n, mem_map)
next_map
end
List.foldl(list, mem, show_entry) # returns newest mem
end
end
nil
|> Demo.show_list([0, 10, 30], &Demo.show3/2)
|> Demo.show_list([100, 1_000, 10_000], &Demo.show2/2)
$ elixir demo.exs
fib(0): 0
fib_lco(0): 0
fib_mem(0): 0
fib(10): 55
fib_lco(10): 55
fib_mem(10): 55
fib(30): 832040
fib_lco(30): 832040
fib_mem(30): 832040
fib_lco(100): 354224848179261915075
fib_mem(100): 354224848179261915075
fib_lco(1000): 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
fib_mem(1000): 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
But keep in mind:
2.1 Myth: Tail-Recursive Functions are Much Faster Than Recursive Functions
Erlang’s Tail Recursion is Not a Silver Bullet
Tail vs. Body Recursion in Erlang Part 1
- Tail recursion isn’t always better than body recursion.
- But given that formulating tail recursive versions takes practice it’s probably a good idea to take every opportunity to design a tail recursive version of a body recursive function - and then choose the implementation with the most merits.
@peerreynders Thank you for the answer. Maybe to compare those 3 methods, a counter can be added to count the number of operations required to perform the calculations.
$ mix profile.fprof -e Demo.load_1
Warmup...
Reading trace data...
..................................................
.................................
End of trace!
Processing data...
Creating output...
Done!
CNT ACC (ms) OWN (ms)
Total 2966862 7384.348 7370.573
:fprof.apply_start_stop/4 0 7384.348 0.013
anonymous fn/0 in :elixir_compiler_1.__FILE__/1 1 7384.319 0.002
Demo.load_1/0 1 7384.317 0.002
Demo.run_load/2 1 7384.315 0.007
List.foldl/3 1 7384.274 0.001
List."-foldl/3-lists^foldl/2-0-"/3 9 7384.273 0.024
anonymous fn/2 in Demo.load_1/0 8 7384.249 0.010
Demo.run_1/2 8 7384.239 0.019
Fib.body/1 2959380 7383.630 7330.228
:garbage_collect 5424 39.637 39.637
:suspend 1708 13.775 0.000
Demo.run_2/2 8 0.590 0.040
Fib.mem/2 9 0.215 0.031
Fib.lco/1 20 0.191 0.038
Fib.mem_fill/2 6 0.175 0.036
Fib.lco/4 105 0.153 0.153
Fib.ets/2 8 0.150 0.020
Fib.mem_fill/5 35 0.120 0.087
Fib.ets_fill/2 6 0.118 0.017
Fib.ets_fill/6 35 0.092 0.070
:maps.put/3 29 0.033 0.033
:maps.find/2 21 0.021 0.021
:ets.lookup/2 14 0.021 0.021
:ets.insert/2 7 0.019 0.019
:fprof."-apply_start_stop/4-after$^1/0-0-"/3 1 0.016 0.006
:ets.delete/1 1 0.015 0.015
Fib.ets_init/1 1 0.012 0.005
:maps.size/1 6 0.007 0.007
Fib.mem/1 1 0.007 0.001
Fib.ets_top/3 7 0.007 0.007
:ets.new/2 1 0.003 0.003
:undefined 0 0.000 0.000
$ mix profile.fprof -e Demo.load_2
Warmup...
Reading trace data...
..................................................
......
End of trace!
Processing data...
Creating output...
Done!
CNT ACC (ms) OWN (ms)
Total 46769 104.538 102.942
:fprof.apply_start_stop/4 0 104.538 0.014
anonymous fn/0 in :elixir_compiler_1.__FILE__/1 1 104.520 0.002
Demo.load_2/0 1 104.518 0.002
Demo.run_load/2 1 104.516 0.006
List.foldl/3 1 102.996 0.001
List."-foldl/3-lists^foldl/2-0-"/3 6 102.995 0.030
anonymous fn/2 in Demo.load_2/0 5 102.965 0.010
Demo.run_2/2 5 102.955 0.028
Fib.mem/2 6 47.658 0.023
Fib.mem_fill/2 5 47.628 0.028
Fib.mem_fill/5 10004 47.584 28.096
Fib.ets/2 5 29.961 0.017
Fib.ets_fill/2 5 29.936 0.015
Fib.ets_fill/6 10004 29.912 16.173
Fib.lco/1 15 25.317 0.033
Fib.lco/4 16600 25.284 24.615
:maps.put/3 9999 13.114 13.114
:garbage_collect 25 12.586 12.586
:ets.insert/2 6 6.606 6.606
:suspend 33 1.596 0.000
:ets.delete/1 1 1.491 1.483
:maps.find/2 16 0.017 0.017
:ets.lookup/2 10 0.017 0.017
Fib.ets_init/1 1 0.013 0.006
Fib.mem/1 1 0.010 0.001
:maps.size/1 5 0.006 0.006
Fib.ets_top/3 6 0.006 0.006
:fprof."-apply_start_stop/4-after$^1/0-0-"/3 1 0.004 0.004
:ets.new/2 1 0.003 0.003
:undefined 0 0.000 0.000
defmodule Demo do
# lib/demo.ex
def load_1() do
run_load([0,1,5,10,15,20,25,30], &run_1/2)
end
def load_2() do
run_load([100,500,1000,5000,10000], &run_2/2)
end
def run_load(load, run_f) do
{_, mem} = Fib.mem(0)
tid = Fib.ets_init(:my_cache)
_state = List.foldl(load, {mem,tid}, run_f)
:ets.delete(tid)
end
def run_1(n, state) do
Fib.body(n)
run_2(n, state) # returns new state
end
def run_2(n, {mem, tid}) do
Fib.lco(n)
{_, next_mem} = Fib.mem(n, mem)
Fib.ets(n, tid)
{next_mem, tid}
end
end
defmodule Fib do
# lib/fib.ex
# 1. body recursion
def body(0),
do: 0
def body(1),
do: 1
def body(n) when n > 1 and is_integer(n),
do: body(n-2) + body(n-1)
# 2. utilizing "last call optimization"
# http://erlang.org/pipermail/erlang-questions/2016-October/090663.html
defp lco(_, acc, i, n) when i == n,
do: acc
defp lco(fi_2, fi_1, i, n) when i < n,
do: lco(fi_1, fi_2 + fi_1, i + 1, n)
def lco(0),
do: 0
def lco(1),
do: 1
def lco(n) when n > 1 and is_integer(n),
do: lco(lco(0), lco(1), 1, n)
# 3. using a result cache
defp mem_fill(_, fi_1, i, mem, n) when i > n do
{fi_1, mem}
end
defp mem_fill(fi_2, fi_1, i, mem, n) do
fi = fi_2 + fi_1
mem_fill(fi_1, fi, i+1, Map.put(mem, i, fi), n)
end
defp mem_fill(n, mem) do
with i <- Map.size(mem),
{:ok, fi_2} <- Map.fetch(mem, i - 2),
{:ok, fi_1} <- Map.fetch(mem, i - 1) do
mem_fill(fi_2, fi_1, i, mem, n)
else
_ -> # unexpected lookup failure - start fresh
mem_fill(0, 1, 2, %{0 => 0, 1 => 1}, n)
end
end
def mem(n, mem \\ %{0 => 0, 1 => 1}) when n >= 0 and is_integer(n) do
with {:ok, result} <- Map.fetch(mem, n) do
{result, mem}
else
_ -> # not found
mem_fill(n, mem)
end
end
# 4. ETS cache
defp ets_top(fib_i1, fib_i, i),
do: {:top, {fib_i1, fib_i, i}}
defp ets_fill(fib_i1, fib_i, i, kvs, tid, n) when i == n do
:ets.insert(tid, [ets_top(fib_i1, fib_i, i) | kvs])
fib_i
end
defp ets_fill(fib_i1, fib_i, i, kvs, tid, n) when i < n do
fib_next = fib_i1 + fib_i
next = i + 1
ets_fill(fib_i, fib_next, next, [{next, fib_next}|kvs], tid, n)
end
defp ets_fill(n, tid) do
with [{_, {fib_i1, fib_i, i}}] <- :ets.lookup(tid, :top) do
ets_fill(fib_i1, fib_i, i, [], tid, n)
else
_ -> # unexpected lookup failure
raise ArgumentError, message: "Provided inconsistent ETS cache"
end
end
def ets_init(name) when is_atom(name) do
tid = :ets.new(name,[:set, :private, {:keypos, 1}])
:ets.insert(tid, [{0, 0}, {1, 1}, ets_top(0,1,1)])
tid
end
def ets(n, tid) do
with [{_ ,fib_n}] <- :ets.lookup(tid, n) do
fib_n
else
_ ->
ets_fill(n, tid)
end
end
end
Edit: Added an ETS version.
Using maps:merge/2
instead of Map.put/3
for Fib.mem/2
:
# 3. using a result cache
defp mem_fill(n, kvs, _fib_i1, _fib_i, i) when n == i do
kvs
end
defp mem_fill(n, kvs, fib_i1, fib_i, i) when i < n do
fib_next = fib_i1 + fib_i
next = i + 1
mem_fill(n, [{next,fib_next}|kvs], fib_i, fib_next, next)
end
defp mem_fill(n,mem) do
[{_, fib_n}|_] = kvs =
with top <- Map.size(mem), # top - 1 = i
{:ok, fib_i1} <- Map.fetch(mem, top - 2), # i - 1
{:ok, fib_i} <- Map.fetch(mem, top - 1) do # i
mem_fill(n, [], fib_i1, fib_i, top-1)
else
_ -> # unexpected lookup failure - start fresh
mem_fill(n, [], 0, 1, 1)
end
more_mem = :maps.from_list(kvs)
new_mem = :maps.merge(mem, more_mem)
{fib_n, new_mem}
end
def mem(n, mem \\ %{0 => 0, 1 => 1}) when n >= 0 and is_integer(n) do
with {:ok, result} <- Map.fetch(mem, n) do
{result, mem}
else
_ -> # not found
mem_fill(n, mem)
end
end
$ mix profile.fprof -e Demo.load_1
Warmup...
Reading trace data...
...................................
End of trace!
Processing data...
Creating output...
Done!
CNT ACC (ms) OWN (ms)
Total 2967928 7451.080 7434.032
:fprof.apply_start_stop/4 0 7451.080 0.007
anonymous fn/0 in :elixir_compiler_1.__FILE__/1 1 7451.070 0.002
Demo.load_1/0 1 7451.068 0.001
Demo.run_load/2 1 7451.067 0.011
List.foldl/3 1 7451.023 0.001
List."-foldl/3-lists^foldl/2-0-"/3 9 7451.022 0.029
anonymous fn/2 in Demo.load_1/0 8 7450.993 0.010
Demo.run_1/2 8 7450.983 0.017
Fib.body/1 2959380 7450.397 7388.353
:garbage_collect 6511 44.996 44.996
:suspend 1704 17.048 0.000
Demo.run_2/2 8 0.569 0.040
Fib.mem/2 9 0.202 0.029
Fib.lco/1 20 0.178 0.033
Fib.mem_fill/2 6 0.163 0.072
Fib.ets/2 8 0.155 0.021
Fib.lco/4 105 0.145 0.145
Fib.ets_fill/2 6 0.125 0.020
Fib.ets_fill/6 35 0.096 0.072
Fib.mem_fill/5 35 0.051 0.051
:maps.find/2 21 0.023 0.023
:ets.insert/2 7 0.021 0.021
:ets.lookup/2 14 0.018 0.018
:ets.delete/1 1 0.014 0.014
Fib.ets_init/1 1 0.012 0.005
:maps.size/1 6 0.010 0.010
:maps.from_list/1 6 0.010 0.010
:maps.merge/2 6 0.007 0.007
Fib.mem/1 1 0.007 0.001
Fib.ets_top/3 7 0.007 0.007
:fprof."-apply_start_stop/4-after$^1/0-0-"/3 1 0.003 0.003
:ets.new/2 1 0.003 0.003
:undefined 0 0.000 0.000
$ mix profile.fprof -e Demo.load_2
Warmup...
Reading trace data...
....................................
End of trace!
Processing data...
Creating output...
Done!
CNT ACC (ms) OWN (ms)
Total 36778 74.796 72.899
:fprof.apply_start_stop/4 0 74.796 0.008
anonymous fn/0 in :elixir_compiler_1.__FILE__/1 1 74.785 0.002
Demo.load_2/0 1 74.783 0.001
Demo.run_load/2 1 74.782 0.009
List.foldl/3 1 73.435 0.001
List."-foldl/3-lists^foldl/2-0-"/3 6 73.434 0.026
anonymous fn/2 in Demo.load_2/0 5 73.408 0.006
Demo.run_2/2 5 73.402 0.028
Fib.lco/1 15 26.574 0.042
Fib.lco/4 16600 26.532 24.625
Fib.mem/2 6 23.493 0.023
Fib.mem_fill/2 5 23.463 0.062
Fib.ets/2 5 23.314 0.015
Fib.ets_fill/2 5 23.290 0.014
Fib.ets_fill/6 10004 23.264 15.164
Fib.mem_fill/5 10004 21.344 15.504
:garbage_collect 27 8.112 8.112
:ets.insert/2 6 5.860 5.860
:suspend 29 1.897 0.000
:maps.from_list/1 5 1.690 1.690
:ets.delete/1 1 1.320 1.294
:maps.merge/2 5 0.350 0.350
:ets.lookup/2 10 0.021 0.021
:maps.find/2 16 0.019 0.019
Fib.ets_init/1 1 0.010 0.004
Fib.mem/1 1 0.008 0.001
Fib.ets_top/3 6 0.007 0.007
:maps.size/1 5 0.005 0.005
:fprof."-apply_start_stop/4-after$^1/0-0-"/3 1 0.003 0.003
:ets.new/2 1 0.003 0.003
:undefined 0 0.000 0.000