Need help trying to map procedural to functional

Questions & Help Questions
1

:ok:
ello!

I’m trying to learn some Elixir by doing some exercises. Currently, I’m trying to understand how to write the equivalent of a fibonacci with a cache. At the moment, I came up with the following implementation:

defmodule M do
  @moduledoc false
  def main do
    cache = spawn(M, :fib_cache, [%{}])
    IO.puts(fib(10, cache))
  end

  def fib(n, cache_pid) do
    case n do
      1 -> 0
      2 -> 1
      3 -> 1
      _ ->
      send(cache_pid, {self(), :fetch, n})
      receive do
        {:reply, value} ->
          if value != nil do
            value
          end
      end
      num = fib(n-1, cache_pid) + fib(n - 2, cache_pid)
      send(cache_pid, {self(), :store, n, num})
      receive do
        {:ok} ->
          num
      end
    end
  end

  def fib_cache(state) do
    receive do
      {from, :store, n, m} ->
        IO.inspect(state)
        send(from, {:ok})
        fib_cache(Map.put(state, n, m))
      {from, :fetch, n} ->
        send(from, {:reply, Map.get(state, n, nil)})
        fib_cache(state)
    end
  end
end

What is worrying me is the log that it prints when I run it:


iex(3)> M.main
%{}
%{4 => 2}
%{4 => 2, 5 => 3}
%{4 => 2, 5 => 3}
%{4 => 2, 5 => 3, 6 => 5}
%{4 => 2, 5 => 3, 6 => 5}
%{4 => 2, 5 => 3, 6 => 5}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8, 8 => 13}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8, 8 => 13}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8, 8 => 13}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8, 8 => 13}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8, 8 => 13}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8, 8 => 13}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8, 8 => 13}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8, 8 => 13}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8, 8 => 13, 9 => 21}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8, 8 => 13, 9 => 21}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8, 8 => 13, 9 => 21}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8, 8 => 13, 9 => 21}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8, 8 => 13, 9 => 21}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8, 8 => 13, 9 => 21}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8, 8 => 13, 9 => 21}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8, 8 => 13, 9 => 21}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8, 8 => 13, 9 => 21}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8, 8 => 13, 9 => 21}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8, 8 => 13, 9 => 21}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8, 8 => 13, 9 => 21}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8, 8 => 13, 9 => 21}
34
:ok

In short, the state gets printed multiple times when in a equivalent implementation in a procedural language it would print once. My question is: what am I missing here? Are the functions executed in parallel when I create the num variable? Shouldn’t it fill the state with all the values from 1 to 10 and fib(n-2) be a O(1) operation?

Looking forward to hearing from you

2

The problem is that the value returned from fetch doesn’t get used for anything, so the calculation continues despite getting a value from the cache.

You’d want to pull the calculation into an else:

      send(cache_pid, {self(), :fetch, n})
      receive do
        {:reply, value} ->
          if value != nil do
            value
          else      # <= CHANGE STARTS HERE
            num = fib(n-1, cache_pid) + fib(n - 2, cache_pid)
            send(cache_pid, {self(), :store, n, num})
            receive do
              {:ok} ->
                num
            end
          end
      end
3

Thanks a lot for your response! I’m just wondering, why is it that value is not used? Is it because elixir does not accept early returns?

How can I systematically find and solve these issues, coming from a procedural background? The pattern I’m seeing is an if without an else. Is this accurate?

Also, how do I avoid the Hadouken code that is forming? The depth of the context is getting somewhat overwhelming with the receive > else > receive. For such a pet example, it is not an issue, but for production code this will be an issue. I ask this because most of the time I leverage early returns to avoid having deep context in my code - therefore I need to understand what would be the Elixir way of doing this.

Any guidance would be invaluable. Thanks in advance

4

Even in a language (for instance, Ruby) where early returns were supported, you’d need to say return(value) or similar.

It’s technically possible to do early-return-ish things in Elixir with catch and throw but the preferred alternative is to write code that doesn’t need them.

Not specifically the problem - the root cause is that there’s no early-return.

Here’s another version with slightly less nesting:

      send(cache_pid, {self(), :fetch, n})

      value =
        receive do
          {:reply, value} -> value
        end

      if is_nil(value) do
        num = fib(n-1, cache_pid) + fib(n - 2, cache_pid)
        send(cache_pid, {self(), :store, n, num})
        receive do
          {:ok} ->
            num
        end
      else
        value
      end

Functions are cheap. Use lots.

For instance, this version mostly just moves code around:

  def fib(n, cache_pid) do
    case n do
      1 -> 0
      2 -> 1
      3 -> 1
      _ ->
        case get_cached(cache_pid, n) do
          nil -> compute(cache_pid, n)
          cached -> cached
        end
    end
  end

  defp get_cached(cache_pid, n) do
    send(cache_pid, {self(), :fetch, n})
    receive do
      {:reply, value} -> value
    end
  end

  defp compute(cache_pid, n) do
    num = fib(n-1, cache_pid) + fib(n - 2, cache_pid)
    send(cache_pid, {self(), :store, n, num})
    receive do
      {:ok} ->
        num
    end
  end

Or you can get fancier with an anonymous function:

  def fib(n, cache_pid) do
    case n do
      1 -> 0
      2 -> 1
      3 -> 1
      _ -> compute_cached(cache_pid, n, fn i -> fib(i-1, cache_pid) + fib(i-2, cache_pid) end)
    end
  end

  defp compute_cached(cache_pid, n, fun) do
    case get_cached(cache_pid, n) do
      nil ->
        num = fun.(n)
        store_cache(cache_pid, n, num)
        num
      cached -> cached
    end
  end

  defp get_cached(cache_pid, n) do
    send(cache_pid, {self(), :fetch, n})
    receive do
      {:reply, value} -> value
    end
  end

  defp store_cache(cache_pid, n, num) do
    send(cache_pid, {self(), :store, n, num})
    receive do
      {:ok} ->
        num
    end
  end

One nice property of this arrangement is that the caching machinery is now uninvolved in the specifics of Fibonacci-ness.

Most of the time that pattern is wrapped up into higher-level functions. For instance, here’s the code from the previous version but with the fib_cache cache replaced with an Agent from stdlib:

defmodule M do
  @moduledoc false
  def main do
    {:ok, cache} = Agent.start_link(fn -> %{} end)
    IO.puts(fib(10, cache))
  end

  def fib(n, cache_pid) do
    case n do
      1 -> 0
      2 -> 1
      3 -> 1
      _ ->
        compute_cached(cache_pid, n, fn i ->
          fib(i-1, cache_pid) + fib(i-2, cache_pid)
        end)
    end
  end

  defp compute_cached(cache_pid, n, fun) do
    case get_cached(cache_pid, n) do
      value when is_integer(value) -> value
      nil ->
        num = fun.(n)
        store_cache(cache_pid, n, num)
        num
    end
  end

  defp get_cached(cache_pid, n) do
    Agent.get(cache_pid, fn s ->
      Map.get(s, n)
    end)
  end

  defp store_cache(cache_pid, n, num) do
    Agent.update(cache_pid, fn s ->
      IO.inspect(s)
      Map.put(s, n, num)
    end)
  end
end

The custom message formats ({:fetch, ...}, {:reply, ...} etc) are now handled by wrapper functions like Agent.get and Agent.update.

5

I appreciate the help. I just thought at the example that simply writing value in the body of the if would return the value. Thanks a lot for the patience and the snippets.