Elixir에서 메모이제이션 하기, Part 2

이 포스트는 Elixir에서 메모이제이션 하기, Part 1에서 이어지는 내용을 다루고 있습니다. Part 1을 읽지 않으신 분들은 먼저 읽고 다시 돌아와 주세요!

2.5단계: GenServer 확장하기

일단 저번 포스트에서 작성한 MemoizationServer가 가지고 있는 한계점 중 딱 두 가지가 눈에 띕니다.

• 매개변수가 1개인 (즉, arity가 1인) 함수만 사용할 수 있다.
• 하나의 MemoizationServer는 단 하나의 함수에 대해서만 사용할 수 있다.

먼저 여러개의 매개변수를 갖는 함수에 대응할 수 있도록 구현을 개선해 봅시다. 현재 MemoizationServer 내부에서는 메모이제이션 state가 아래와 같은 형태로 관리되고 있습니다.

%{arg1 => value1, arg2 => value2, arg3 => value3}

하나의 인자에 하나의 함숫값이 대응되어 있는 모습인데요, 이러한 구조는 크게 두 가지 방식으로 개선할 수 있을 것 같습니다.

1. 매개변수의 개수만큼 map을 중첩

    %{
      0 => %{0 => 0,  1 => 1,  2 => 2},
      1 => %{0 => 10, 1 => 11, 2 => 12}
    }

   Map을 다차원 배열처럼 사용하는 방식입니다. 그런데 제가 보기에는 그다지 직관적인 것 같지 않고 함수의 매개변수가 많을 수록 중첩되는 깊이도 커져서 삽입 등의 작업을 하기 위한 코드가 복잡해질 것 같습니다.

2. 매개변수를 리스트로 묶은 것을 key로 사용

    %{
      [0, 0] => 0,  [0, 1] => 1,  [0, 2] => 2,
      [1, 0] => 10, [1, 1] => 11, [1, 2] => 12
    }

   모든 매개변수의 조합을 1차원 공간 내에 다 집어 넣는 방식입니다. Map의 크기가 커질 수록 성능이 어떻게 될 지는 잘 모르겠지만, 일단 이번 시간에는 구현의 편의를 위해 이 방식을 사용하기로 하겠습니다.

이번에는 하나의 MemoizationServer 프로세스가 하나의 함수에 대해서만 사용할 수 있다는 문제에 대해 생각해 봅시다. 사실 Elixir/Erlang 환경에서 프로그램을 작성한다면 이것은 큰 문제가 되지 않습니다. 그냥 메모이제이션이 필요한 함수의 개수만큼 MemoizationServer 프로세스를 띄우면 되거든요. 게다가 Elixir에는 여러 개의 프로세스를 관리하고 각각의 프로세스에서 발생하는 오류를 적절하게 처리할 수 있는 Supervisor라는 프로세스도 제공하고 있습니다. (저는 이것을 OTP의 꽃이라고 생각하고 있어요.)

하지만 이번에는 좀 무식하지만 하나의 MemoizationServer가 여러 함수에 대해 메모이제이션을 지원할 수 있도록 만들고 싶습니다. 메모이제이션 state의 겉쪽에는 각각의 함수를 식별할 수 있는 key를 두고, 각각의 key에 지금까지 만들어 왔던 모양의 매개변수-함숫값 쌍을 대응시키도록 하겠습니다. 피보나치 함수를 예로 들면 메모이제이션 state는 이런 모습을 하고 있겠지요.

%{
  "fib" => %{
    0 => 0, 1 => 1, 2 => 1, 3 => 2,
    4 => 3, 5 => 5, 6 => 8, ...
  }
}

위와 같은 계획을 바탕으로 MemoizationServer와 GenServerFibonacci 모듈을 다시 작성해 보았습니다. 아래 코드에서 주목해야 할 점은 args 매개변수가 반드시 리스트여야 한다는 것, 그리고 fun_id라는 매개변수가 추가되었고 map 안에 map이 한 번 중첩된다는 것입니다.

defmodule MemoizationServer do
  use GenServer

  def start_link(opts) do
    GenServer.start_link(__MODULE__, opts, name: __MODULE__) # --(1)
  end

  @spec get_value(term(), [term()]) :: {:value, term()} | :no_value
  def get_value(fun_id, args) when is_list(args) do
    GenServer.call(__MODULE__, {:get_value, fun_id, args}) # --(2)
  end

  @spec put_value(term(), [term()], term()) :: :ok
  def put_value(fun_id, args, value) when is_list(args) do
    GenServer.call(__MODULE__, {:put_value, fun_id, args, value}) # --(3)
  end

  def init(_opts) do # --(1)
    {:ok, %{}}
  end

  def handle_call({:get_value, fun_id, args}, _from, state) do # --(2)
    case state[fun_id][args] do
      {:value, _} = value -> {:reply, value, state}
      nil -> {:reply, :no_value, state}
    end
  end

  def handle_call({:put_value, fun_id, args, value}, _from, state) do # --(3)
    fun_memo =
      state
      |> Map.get(fun_id, %{}) # state[fun_id]가 없으면 nil 대신 %{} 반환
      |> Map.put(args, {:value, value})
    new_state = Map.put(state, fun_id, fun_memo)

    {:reply, :ok, new_state}
  end
end

defmodule GenServerFibonacci do
  @doc "피보나치 수열의 n번째 수를 반환합니다."
  @spec fib(non_neg_integer()) :: non_neg_integer()
  def fib(0), do: 0
  def fib(1), do: 1

  def fib(n) when is_integer(n) and n > 1 do
    fun_id = "GenServerFibonacci.fib/1"

    case MemoizationServer.get_value(fun_id, [n]) do
      {:value, result} ->
        result

      :no_value ->
        result = fib(n - 2) + fib(n - 1)
        MemoizationServer.put_value(fun_id, [n], result)

        result
    end
  end
end

위의 GenServerFibonacci 모듈의 코드에서 볼 수 있듯이, 매개변수가 한 개일 때에도 원소의 개수가 하나인 리스트를 만들어서 서버 프로세스에 요청을 해야 합니다. fun_id의 값은 여러 함수들 간에 충돌이 일어나지 않는 범위 내에서 어떤 것을 써도 무방하지만, Elixir/Erlang에서 주로 사용되는 "Module.function/arity" 표기법을 따르기로 했습니다. 규칙이 명확하고 이름이 충돌할 가능성을 최소화할 수 있으니까요.

동일한 MemoizationServer를 사용하는 팩토리얼 함수도 한 번 만들어 볼까요?

defmodule GenServerFactorial do
  @doc "n의 팩토리얼을 구합니다."
  @spec fac(non_neg_integer()) :: non_neg_integer()
  def fac(0), do: 1

  def fac(n) when is_integer(n) and n > 0 do
    fun_id = "GenServerFactorial.fac/1"

    case MemoizationServer.get_value(fun_id, [n]) do
      {:value, value} ->
        value

      :no_value ->
        value = fac(n - 1) * n
        MemoizationServer.put_value(fun_id, [n], value)

        value
    end
  end
end

그리고 간단하게 테스트를 해 봅시다. :sys Erlang 모듈을 사용하면 GenServer 내의 state를 확인할 수 있다는 걸 최근에 와서야 알게 되었는데, 이번 기회에 한 번 사용해 보겠습니다.

iex> {:ok, pid} = MemoizationServer.start_link([])
{:ok, #PID<x.y.z>}

iex> GenServerFibonacci.fib(5)
5

iex> GenServerFactorial.fac(5)
120

iex> :sys.get_state(MemoizationServer)
%{
  "GenServerFactorial.fac/1" => %{
    [1] => {:value, 1},
    [2] => {:value, 2},
    [3] => {:value, 6},
    [4] => {:value, 24},
    [5] => {:value, 120},
  },
  "GenServerFibonacci.fib/1" => %{
    [2] => {:value, 1},
    [3] => {:value, 2},
    [4] => {:value, 3},
    [5] => {:value, 5},
  }
}

저희가 구상했던 대로 아주 잘 동작하는군요! 지금까지 함수형 프로그래밍과 Elixir/Erlang에서만 사용할 수 있는 기법을 이용하여 메모이제이션을 구현해 보았습니다. 이 아래부터는 저번 포스트의 끝에서 잠깐 밝힌 대로, 메모이제이션을 소재로 하고 있을 뿐 메모이제이션과는 살짝 멀지만 아주 재미있는 내용을 다뤄보려고 합니다.

3단계: 언어의 기능을 확장하기

지금부터 다루게 될 내용은 순수하게 제 욕심에 의한 것입니다. 왜냐면 우리는 이미 어떤 함수든지 사용할 수 있는 전천후 메모이제이션 스토리지를 만들어 놓았거든요. 여기서 저는 좀 더 나아가고 싶습니다. 다음과 같은 상황을 가정해 봅시다.

• 라이브러리에 메모이제이션이 필요한 함수가 많이 있다.
• 그럼 메모이제이션이 필요한 함수 하나하나에 MemoizationServer를 사용하는 코드를 써 넣어야 한다. 그리고 나는 그게 너무 귀찮다!
• 그래서 메모이제이션을 하지 않는 평범한 함수를 정의해 놓으면 그 함수가 컴파일 시간에 메모이제이션을 하는 함수로 바뀌었으면 좋겠다.

Elixir의 매크로 기능이 필요한 순간이군요. 매크로는 Elixir 소스 코드가 컴파일되는 시점에 호출되어 코드의 모양을 변형시키는 함수입니다. 대부분이 C언어로 컴퓨터 프로그래밍에 입문한 사람으로서, 보통 “매크로”라 하면 소스 코드를 컴파일 하기 전에 무식하게 소스 코드의 문자열을 치환해주는 것이라는 인식이 짙은데, Elixir의 매크로는 일단 소스 코드를 한 번 분석해서 추상 구문 트리(AST)를 생성하고, 이 AST의 일부분을 치환하는 방식으로 동작합니다. 이러한 특징 덕분에 Elixir의 매크로는 훨씬 더 자유도가 높고, 그만큼 상당히 어렵습니다.

매크로에 관한 기본적인 내용이 궁금하면 이 포스트를 먼저 읽고 오시는 것이 좋습니다.

다시 본론으로 돌아가 봅시다. 이번 단계의 목표를 간단히 요약하자면,

defmodule Foo do
  defmemoized foo(a, b) do
    a_crazy_calculations(a)
    another_crazy_calculations(b)

    a + b
  end
end

이런 코드를

defmodule Foo do
  def foo(a, b) do
    fun_id = "Foo.foo/2"

    case MemoizationServer.get_value(fun_id, [a, b]) do
      {:value, value} ->
        value

      :no_value ->
        value = ( # ()는 블록을 만드는 syntax입니다.
          a_crazy_calculations(a)
          another_crazy_calculations(b)
          a + b
        )
        MemoizationServer.put_value(fun_id, [a, b], value)

        value
    end
  end
end

이러한 모양으로 컴파일 시간에 바꾸어 주는 defmemoized라는 매크로를 작성하는 것입니다. 그런데 defmemoized라는 함수는 몇 개의 매개변수를 받고 있을까요? 이것을 알기 위해서는 Elixir의 syntactic sugar에 대해 알고 있어야 합니다. 지금 이 경우에 대해서는 아래의 세 가지만 알고 있으면 됩니다.

• do ... end는 키워드 리스트 [do: (... block ...)]에 대한 syntactic sugar이다
• 키워드 리스트 [a: foo, b: bar]는 첫번째 원소가 atom인 2-tuple의 리스트 [{:a, foo}, {:b, bar}]에 대한 syntactic sugar이다.
• 익명 함수가 아닌 함수를 호출할 때는 매개 변수를 감싸는 괄호를 생략할 수 있다.

위 세 가지를 이용해서 defmemoized를 호출하는 코드를 아래와 같이 못생긴 모양으로 고쳐 쓸 수 있습니다.

defmemoized(
  # 매개변수 1: 함수의 이름과 매개변수 목록
  foo(a, b),
  # 매개변수 2: 함수의 본문 (body)
  [{:do,
    (
      a_crazy_calculations(a)
      another_crazy_calculations(b)
      a + b
    )}]
)

코드에서 단물을 쫙 빼내고 나니 매크로에 전달되는 매개변수가 명확해졌습니다. defmemoized라는 매크로는 두 개의 매개변수가 필요하다는 것을 알았으니 이제 매크로 정의를 시작할 수 있습니다.

defmodule MemoizationMacros do
  defmacro defmemoized(call, body) do
    # TODO: 여기에 def를 호출하는 AST를 만드는 코드를 작성하기
  end
end

이제 Elixir 컴파일러가 다른 모듈을 컴파일할 때 defmemoized를 호출하는 부분의 AST를 만나게 되면 defmacro/2의 do 블록에서 반환하는 AST로 치환합니다. 지금부터 차근차근 매크로의 안쪽을 채워볼까요? 우선 def의 껍데기부터 만들어 봅시다. 아직 준비가 되지 않은 부분은 “[TODO n]” 문자열로 채워 놓았습니다.

defmodule MemoizationMacros do
  defmacro defmemoized(call, body) do
    fun_name = "[TODO 1: fun_name]"

    # 이 매크로를 호출할 때마다 이하의 식으로 확장(expand)됩니다.
    quote do
      def unquote(call) do
        fun_id = "#{__MODULE__}." <> unquote(fun_name)

        case MemoizationServer.get_value(fun_id, "[TODO 2: args]") do
          {:value, value} ->
            value

          :no_value ->
            value = "[TODO 3: value]"
            MemoizationServer.put_value(fun_id, "[TODO 2: args]", value)

            value
        end
      end
    end
  end
end

fun_name

가장 먼저 만들어 볼 식은 fun_id를 만드는 데 쓰이는 fun_name입니다. fun_id는 "Module.function/arity"의 형태로 이루어져 있으므로 fun_name에 "function/arity" 형식의 문자열을 집어넣는 것이 목표입니다. 그럼 정의할 함수의 이름과 그 함수가 받아야 할 매개변수의 개수는 어떻게 알 수 있을까요? 그 답은 매크로를 호출할 때 주어지는 call 매개변수에 들어 있습니다. call 매개변수에는 foo(a, b)와 같은 함수 호출 식의 AST가 들어 있으므로 이 AST를 뜯어보면 필요한 정보를 얻을 수 있을 것입니다.

iex> quote do
...>   foo(a, b)
...> end
{:foo, [], [{:a, [], Elixir}, {:b, [], Elixir}]}
# {함수이름, 메타데이터, [매개변수1, 매개변수2, ...]}

이를 이용하여 AST의 구조를 패턴 매칭하여 함수의 이름과 매개변수를 추출해 내도 문제는 없습니다만, Elixir에서는 Macro.decompose_call/1이라는 유용한 함수를 제공하고 있습니다.

iex> {fun, args} = Macro.decompose_call(quote(do: foo(a, b)))
{:foo, [{:a, [], Elixir}, {:b, [], Elixir}]}

iex> fun
:foo

iex> args
[{:a, [], Elixir}, {:b, [], Elixir}]

이렇게 fun_name을 완성할 수 있습니다.

defmacro defmemoized(call, body) do
  {fun, args} = Macro.decompose_call(call)
  fun_name = "#{fun}/#{length(args)}"

  quote do
    # 이하 생략...

args

다음은 메모이제이션 서버에서 함숫값을 조회하거나 서버에 함숫값을 저장할 때 키로 사용되는 매개변수 목록을 준비하는 것입니다. 그런데 이 매개변수 목록은 이미 fun_name을 만들기 위해 준비해 놓았군요. PROFIT!

case MemoizationServer.get_value(fun_id, unquote(args)) do
  {:value, value} ->
    value

  :no_value ->
    value = "[TODO 3: value]"
    MemoizationServer.put_value(fun_id, unquote(args), value)

    value
end

value

마지막으로 남은 건 실제로 함숫값을 계산한 뒤에 그 값을 value라는 변수에 대입하는 부분입니다. 계산을 수행하는 코드의 AST는 어떻게 삽입할 수 있을까요? 바로 defmemoized/2의 두번째 매개변수를 이용하는 것입니다. 앞에서 보여드린 defmemoized/2를 호출하는 코드를 다시 보여드리겠습니다.

defmemoized(
  # call
  foo(a, b),
  # body
  [{:do,
    (
      a_crazy_calculations(a)
      another_crazy_calculations(b)
      a + b
    )}]
)

Elixir 컴파일러가 소스 코드로부터 AST를 생성할 때, 키워드 리스트는 형태가 그대로 유지됩니다. 그래서 defmemoized/2가 호출될 때 body 매개변수에는 다음과 같이 생긴 AST가 주어집니다.

[{:do,
  {:__block__, []
    [{:a_crazy_calculations, [], [{:a, [], Elixir}]},
     {:another_crazy_calculations, [], [{:b, [], Elixir}]},
     {:+, [import: Kernel], [{:a, [], Elixir}, {:b, [], Elixir}]}]}}]

즉, body[:do] 식으로 안쪽의 블록 AST를 추출해 낼 수 있습니다.

이제 defmemoized/2 매크로를 작성하기 위해 필요한 세 가지가 모두 모였으므로, 매크로의 구현을 마무리할 수 있습니다.

defmodule MemoizationMacros do
  defmacro defmemoized(call, body) do
    {fun, args} = Macro.decompose_call(call)
    fun_name = "#{fun}/#{length(args)}"

    # 이 매크로를 호출할 때마다 이하의 식으로 확장(expand)됩니다.
    quote do
      def unquote(call) do
        fun_id = "#{__MODULE__}." <> unquote(fun_name)

        case MemoizationServer.get_value(fun_id, unquote(args)) do
          {:value, value} ->
            value

          :no_value ->
            value = unquote(body[:do])
            MemoizationServer.put_value(fun_id, unquote(args), value)

            value
        end
      end
    end
  end
end

이제 이 매크로를 한번 사용해 볼까요! 어떤 모듈에서든 MemoizationMacros 모듈을 import하고 require하면 defmacro/2 매크로를 사용하여 메모이제이션을 하는 함수를 쉽게 만들 수 있습니다.

defmodule MacroTest do
  import MemoizationMacros
  require MemoizationMacros

  @doc "피보나치 수열의 n번째 수를 반환합니다."
  @spec fib(non_neg_integer()) :: non_neg_integer()
  def fib(0), do: 0
  def fib(1), do: 1
  defmemoized fib(n), do: fib(n - 2) + fib(n - 1)

  @doc "n의 팩토리얼을 구합니다."
  @spec fac(non_neg_integer()) :: non_neg_integer()
  def fac(0), do: 1
  defmemoized fac(n), do: fac(n - 1) * n
end

아래는 매크로를 이용하여 만든 함수를 실제로 사용해 본 결과입니다.

iex> {:ok, pid} = MemoizationServer.start_link([])
{:ok, #PID<x.y.z>}

iex> MacroTest.fib(10)
55

iex> MacroTest.fac(10)
3628800

iex> :sys.get_state(MemoizationServer)
%{
  "Elixir.MacroTest.fac/1" => %{
    [1] => {:value, 1},
    [2] => {:value, 2},
    [3] => {:value, 6},
    [4] => {:value, 24},
    [5] => {:value, 120},
    # ...
  },
  "Elixir.MacroTest.fib/1" => %{
    [2] => {:value, 1},
    [3] => {:value, 2},
    [4] => {:value, 3},
    [5] => {:value, 5},
    # ...
  }
}

한계

정말 아름답지 않나요? 마치 defmemoized가 Elixir 언어의 일부분이 된 것 처럼 코드에 아주 자연스럽게 녹아들어 있습니다. 하지만 이 매크로는 많이 단순화된 버전으로, 다음과 같은 몇 가지 제약 사항이 있습니다.

• when을 이용한 가드를 사용할 수 없습니다. 즉, 아래와 같은 코드를 작성하면 프로그램이 제대로 동작하지 않습니다.

    defmemoized fib(n) when is_integer(n) and n > 1 do
      fib(n - 2) + fib(n - 1)
    end

• do ~ rescue ~ end를 사용하면 rescue 블록은 처리되지 않습니다.

• def로 정의된 함수만 생성할 수 있습니다. 즉 defmemoized로는 메모이제이션을 하는 private 함수를 만들 수 없습니다. 보통은 defmemoizedp라는 매크로를 만들어 둠으로써 이를 해결하는 것이 일반적입니다.

물론 Elixir의 매크로는 매우 강력하기 때문에 코드를 조금만 더 덧붙이면 위의 문제를 모두 해결할 수 있지만, 이와 관련된 내용은 이 포스트에서는 다루지 않겠습니다.

마무리

지금까지 피보나치 함수를 가지고 Elixir에서 메모이제이션을 하는 데 사용할 수 있는 여러가지 기법에 대해 알아보았고, 메모이제이션을 하는 함수를 쉽게 만들 수 있도록 언어를 마개조하는 것까지 해 보았습니다. 이렇게 길다란 포스트는 처음 써 보네요 ㅎㅎ… 재미있게 읽으셨길 바라며, 나중에 다른 재미있는 내용으로 또 뵙겠습니다 ><