🐰
깡부지 Blog/
Elixir tail-call optimization
Search

Elixir tail-call optimization

Tags
Published
Author
Elixir 에서 특정 프로세스의 mailbox 에 특정 메세지가 있는지 확인할 때 receive 를 사용한다.
def listen(_) do
	receive do
		msg ->
			# do something
	end
end
위 handle 함수는 하나의 메세지에 대해서 receive 를 처리하고 바로 종료된다. 프로세스가 계속 receive 를 수행하기를 원한다면 아래와 같이 재귀호출을 하도록 하면 된다.
def listen(state) do
	receive do
		msg ->
			# do something
	end
	
	listen(state)
end
위 코드에 어떤 문제점이 있는가? 만약에 위 코드를 실행하는 Process 의 수명이 길다면 어떤일이 발생할까?
하나의 메세지를 호출할 때마다 매번 재귀호출이 발생하므로 메세지당 스택이 하나씩 추가될 것이다. 즉 일반적인 언어에서 위 코드는 StackOverflow 가 발생할 수 있는 위험이 있는 코드이다.
하지만 Elixir 에서는 위와같은 코드에 대해서 tail-call optimization(꼬리재귀 최적화) 를 적용한다.
 
재귀함수와 붙어다니는 클리셰인 factorial 함수를 예시로 더 자세히 확인해보자.
defmodule Factorial do
  def calculate(0), do: 1
  def calculate(n), do: n * calculate(n - 1)
end
아주 단순하게 Factorial 을 구현했다. 위 함수는 꼬리재귀 최적화가 적용될까?
확인을 위해 stack size 를 출력하는 코드를 추가해보자.
defmodule Factorial do
  def calculate(0), do: 1

  def calculate(n) do
    process_info = :erlang.process_info(self())
    IO.inspect(process_info[:stack_size])
    n * calculate(n - 1)
  end
end

result = Factorial.calculate(3)
IO.puts("Result: #{result}")
iex 로 실행해 보면 아래와 같은 결과가 나온다.
notion image
stack size 가 늘어난다. 원인은 함수의 마지막 줄이 마지막 연산이 아니기 때문이다. calculate 연산을 한 뒤에 곱셈을 해야한다.
꼬리재귀를 적용하려면 아래와 같이 곱셈을 재귀호출 내부로 이동시킨다.
 
defmodule Factorial do
  def calculate(n), do: _cal(n, 1)

  defp _cal(0, acc) do
    process_info = :erlang.process_info(self())
    IO.inspect(process_info[:stack_size])

    acc
  end

  defp _cal(n, acc) do
    process_info = :erlang.process_info(self())
    IO.inspect(process_info[:stack_size])

    _cal(n - 1, n * acc)
  end
end

result = Factorial.calculate(3)
IO.puts("Result: #{result}")
실행 시 아래와 같이 스택이 늘어나지 않는것을 확인할 수 있다.
notion image