The Power of Composition (Scott Wlaschin) 보고 느낀 점 - 합성하려다보니 Currying과 Monad

Scott Wlaschin이 NDC Oslo 2018에 발표한 ’The Power of Composition’은 FP(Functional Programming)의 핵심 개념인 합성(composition)을 설명한다. 합성하면 함수만 떠올릴 수 있다. 타입도 합성의 대상이다.

함수 input 개수와 output 개수가 같다면 아무런 문제가 되지 않는다. input이 더 많거나 output이 더 많을 때, 합성을 위한 다른 도구가 필요하다. 그 도구로 Currying(커링)과 Monad(모나드)를 설명한다.

발표해서 사용한 F# 코드 예제를 Elixir로 바꿔서 정리할 것이다. 좋아하니깐.

요약 by human

• 재사용 방법의 하나인 합성은 타입과 함수
  • 타입은 AND 또는 OR로 합성
• input 개수와 output 개수가 같을 때는 함수 합성이 쉽다
  • 함수의 output을 다음 함수의 input으로 넘기면 끝
  • 개수가 다를 때 이걸 해결할 방법이 필요
• input 개수가 더 많을 때는 Currying(커링)
  • input 개수를 하나로 만들어준다
• output 개수가 더 많을 때는 Monad(모나드)
  • output 개수를 하나로 만들고 처리 혹은 처리되지 않음으로 구분
    • 처리된 건 다음 함수로 그냥 넘김
    • 처리되지 않은 건 함수로 처리 시도
  • 알고 보니 이게 Monad
  • output을 Monad에 담고 bind로 함수 조합

타입 합성(type composition)

합성은 재사용 방법의 하나이다. 합성이라고 하면 함수 합성만 떠올릴 수 있다. 하지만 타입도 합성의 대상이다. 프로그래밍 언어에서 이미 정의한 타입을 쓰는 순간부터 우리는 이미 합성을 사용하고 있다. int 타입 멤버와 string 타입을 멤버로 가지는 타입을 정의한다면 타입을 합성해서 새로운 타입을 만든 것이다

AND 합성을 먼저 살펴보자.

defmodule FruitSalad do
  @type t() :: %__MODULE__{
    apple: AppleVariety.t(),
    banana: BananaVariety.t(),
    cherry: CherryVariety.t()
  }

  defstruct [:apple, :banana, :cherry]
end

FruitSalad 구조체가 멤버로 AppleVariety 타입의 apple과 BananaVariety 타입의 banana와 CherryVariety 타입의 cherry를 가진다. AND 합성으로 새로운 타입인 FruitSalad 타입을 합성했다. OOP(Object-Oriented Programming) 개념으로 설명하면 has-a 관계로 AND 합성으로 새로운 타입을 만든다.

다음은 OR 합성이다. Elixir가 Dynamically-typed(동적타입) 언어라서 구현하면서 범위를 더 좁히는 느낌을 받았다. OR 합성은 타입의 Domain(정의역)을 넓히는 과정이다. 하지만 동적타입 언어는 정의역이 모든 타입이라서 범위를 좁혀서 정의해야 한다.

defmodule Snack do
  @type material :: AppleVariety.t() | BananaVariety.t() | CherryVariety.t()

  @type t :: %__MODULE__{
    material: material()
  }

  defstruct [:material]
end

defmodule SnackProcessor do
  @spec describe(Snack.t()) :: String.t()
  def describe(%{material: %AppleVariety{name: name}}), do: "An apple of variety #{name}"
    def describe(%{material: %BananaVariety{name: name}}), do: "A banana of variety #{name}"
      def describe(%{material: %CherryVariety{name: name}}), do: "A cherry of variety #{name}"
      end

Snack 구조체는 AppleVariety 타입, BananaVariety 타입, CherryVariety 타입 중 하나이다. SnackProcessor.describe/1 함수는 타입에 따른 처리를 한다.

Dynamically-typed(동적타입)이라 OR 연산자는 오히려 범위를 좁혀주는 작업을 해야 한다. 타입으로 올 수 있는 모든 타입이 가능하기 때문이다.

언어 차원에서 타입 OR 조합을 지원하지 않는 C++과 같은 정적타입 언어에서는 Tagged union을 사용하면 OR 조합을 할 수 있다. C++은 std::variant<int, float> v 과 같이 variant를 사용하면 된다.

함수 합성(function composition) - input, output 개수가 같을 때

input과 output 타입이 같고 개수도 같으면 조합하려는 함수를 연이어 호출하면 된다.

add1 = fn x -> x + 1 end
double = fn x -> x + x end
add1_double = fn x -> x |> add1.() |> double.() end
add1_double.(3)

이건 문제가 안 된다. 다음은 input이 더 많을 때를 살펴보자.

함수 합성 - input이 더 많을 때 (feat. Currying)

함수를 조합하려는데 input이 더 많은 경우를 살펴보자. ouput은 하나인데, input이 세 개인 경우를 예로 든다. 조합하려면 input도 하나로 맞춰줘야 한다.

십진수를 로마 숫자(Roman Numerals)로 표현하는 코드를 예로 든다. 예) 1을 I로 표현하고 I가 5개면 V로 표현하고 V가 2개이면 X로 표현하는 방식이다.

replace 함수 조각부터 시작하자.

replace = fn input_str, old_value, new_value ->
  String.replace(input_str, old_value, new_value)
end

replace.("IIIIIIII", "IIIII", "V")
#=> "VIII"

replace 함수를 조합해야 하는데, output은 “VIII”로 하나이고 input은 “IIIIIIII”, “IIIII”, “V” 처럼 세 개이다. input을 하나로 만들어주면 조합할 수 있다. 이제 나온다 Currying(커링).

replace 함수는 그대로 놔두고 커링으로 input을 하나로 만든 replace_IIIII_V/1, replace_VV_X/1 함수를 정의한다.

replace = fn input_str, old_value, new_value ->
  String.replace(input_str, old_value, new_value)
end

replace_IIIII_V = fn input_str -> replace.(input_str, "IIIII", "V") end
replace_VV_X = fn input_str -> replace.(input_str, "VV", "X") end

String.duplicate("I", 14)
|> replace_IIIII_V.()
|> replace_VV_X.()
#=> "XIIII"

단일 인자를 받는 Curried function을 만들어서 함수를 조합했다. Elixir에서는 |> 연산자가 이전 함수의 리턴 값을 다음 함수에 첫 번째 인자로 넣어주는 Syntactic sugar(편의 문법)을 지원한다. 특정 인자를 고정하는 Partial application(부분 적용)처럼 사용할 수 있다. 그래서 input 개수가 더 많을 때, Currying(커링)을 안 쓰고 조합할 수 있다.

replace = fn input_str, old_value, new_value ->
  String.replace(input_str, old_value, new_value)
end

String.duplicate("I", 14)
|> replace.("IIIII", "V")
|> replace.("VV", "X")
#=> "XIIII"

String.duplicate("I", 14) 함수의 ouput이 replace.("IIIII", "V") 함수의 첫 번째 인자로 들어가서 replace.(String.duplicate("I", 14), "IIIII", "V") 처럼 호출된다. 그래서 이런 함수를 조합할 때는 Currying(커링)을 안 써도 조합할 수 있다.

전체 구현은 아래와 같다.

defmodule RomanNumeral do
  def from_integer(number) do
    String.duplicate("I", number)
    |> replace("IIIII", "V").()
    |> replace("VV", "X").()
    |> replace("XXXXX", "L").()
    |> replace("LL", "C").()
    |> replace("CCCCC", "D").()
    |> replace("DD", "M").()
  end

  defp replace(old, new) do
    fn input -> String.replace(input, old, new) end
  end
end

iex> RomanNumeral.from_integer(1234)
"MCCXXXIIII"

이제 output이 많을 때를 살펴볼 차례다.

함수 합성 - output이 더 많을 때 (feat. Monad 찍먹)

input과 output이 같을 때, 함수 합성을 어떻게 하는지도 살펴봤고 input이 더 많을 때도 살펴봤다. 이제 output이 더 많을 때를 살펴볼 차례다. 코딩 테스트에서 이것도 못 푸는 사람이 있데. 이걸로 인터넷을 뜨겁게 달궜었던 Fizz buzz를 예로 들어서 함수 조합을 해보자.

함수 조합을 생각하지 않고 짜면 아래와 같은 코드를 생각할 수 있다.

fizzbuzz = fn max ->
  for i <- 1..max do
    cond do
      rem(i, 15) == 0 ->
        "FizzBuzz"
      rem(i, 3) == 0 ->
        "Fizz"
      rem(i, 5) == 0 ->
        "Buzz"
      true ->
        to_string(i)
    end
  end
end

iex> fizzbuzz.(15)
["1", "2", "Fizz", "4", "Buzz", "Fizz", "7", "8", "Fizz", "Buzz", "11", "Fizz",
 "13", "14", "FizzBuzz"]

이제 함수 합성으로 어렵게 풀어보자. 간단한 예제 항상 이런 딜레마가 있다. 더 어렵게 풀어야 개념 설명을 할 수 있는 것이다.

함성으로 푼다면 다음과 같은 모양이 나올 것이다

number
|> handle_15_case()
|> handle_3_case()
|> handle_5_case()
|> handle_remaining()
|> make_answer()

입력한 숫자를 15, 3, 5로 나눠지는 경우를 차례로 처리하고 마무리를 하면 된다.

만약 handle_15_case 함수에서 처리가 됐다면 handle_3_case 함수에서는 그냥 흘려보내야 한다. 즉 handle 함수는 처리됐을 때와 처리되지 않았을 때를 구분해야 한다. output이 두 가지인 함수가 된다.

• input
  • number
• output
  • Carbonated
    • fizzbuzz, fizz, buzz,
  • Uncarbonated
    • 2, 7, 13, …

Carbonated, Uncarbonated 라는 단어가 낯설다. Carbonated 는 ’탄산이 있는’이라는 뜻이다. 가공된 값을 나타낸다. 재미있는 표현이다. Elixir로 구현해 보자.

defmodule Carbonate do
  @type carbonated :: String.t()
  @type result :: integer | carbonated
  @type judge :: :carbonated | :uncarbonated

  @spec run(integer, integer, String.t()) :: {judge, result}
  def run(n, divisor, label) do
    if divisible_by?(n, divisor) do
      {:carbonated, label}
    else
      {:uncarbonated, n}
    end
  end

  defp divisible_by?(n, divisor) do
    rem(n, divisor) == 0
  end
end

iex> Carbonate.run(12, 3, "Fizz")
{:carbonated, "Fizz"}
iex> Carbonate.run(10, 3, "Fizz")
{:uncarbonated, 10}
iex> Carbonate.run(10, 5, "Buzz")
{:carbonated, "Buzz"}

어라 input이 3개로 더 많은 거 아냐?

handle_15_case = fn n ->
  Carbonate.run(n, 15, "FizzBuzz")
end

Currying으로 input이 하나인 함수를 만들어서 조합해야 하지만 elixir가 지원하는 기능으로 숫자 n 을 제외한 인자를 고정해서 Currying처럼 사용할 수 있다. 그래서 input이 하나인 함수로 생각하자.

우선 무식하게 구현해서 패턴을 발견해보자.

defmodule FizzBuzz do
  def run(n) do
    case Carbonate.run(n, 15, "FizzBuzz") do
      {:carbonated, result} -> result
      {:uncarbonated, n} ->
        case Carbonate.run(n, 3, "Fizz") do
          {:carbonated, result} -> result
          {:uncarbonated, n} ->
            case Carbonate.run(n, 5, "Buzz") do
              {:carbonated, result} -> result
              {:uncarbonated, n} -> n
            end
        end
    end
  end
end

iex> FizzBuzz.run(1)
1
iex> FizzBuzz.run(3)
"Fizz"
iex> FizzBuzz.run(5)
"Buzz"
iex> FizzBuzz.run(15)
"FizzBuzz"
iex> FizzBuzz.run(17)
17

잘 동작한다. 패턴을 보면 {:carbonated, result} 튜플을 리턴하면 그냥 결과를 리턴하고 {:uncabonated, n} 튜플을 리턴하면 다음 처리 함수를 호출하는 걸 볼 수 있다.

처리되지 않으면 호출할 함수를 인자로 받는 함수를 생각해 볼 수 있다.

defp if_carbonated_do(result, fun) when is_function(fun, 1) do
  case result do
    {:carbonated, _str} = final -> final
    {:uncarbonated, n} -> fun.(n)
  end
end

함수를 인자로 받고 결과값이 가공된(carbonated) 값이면 값을 리턴하고 아니면 함수 인자로 숫자를 호출하는 함수가 있다면 조합이 가능하다.

n
|> Carbonate.run(15, "FizzBuzz")
|> if_carbonated_do(& Carbonate.run(&1, 3, "Fizz"))
|> if_carbonated_do(& Carbonate.run(&1, 5, "Buzz"))

숫자 n을 입력받아서 15로 나눠진다면 첫 번째 Carbonate.run/3 함수는 {:carbonated, "FizzBuzz"} 를 리턴한다. 이후 함수에서 인자로 받은 함수를 호출하지 않고 "FizzBuzz" 를 리턴한다. 만약 15로 나눌 수 없는 17 같은 수라면 {:uncarbonated, 17} 를 리턴하게 되고 이후 함수에서는 Carbonate.run(17, 3, "Fizz") 를 호출하는 식으로 함수 조합이 이뤄진다.

pipe operator의 왼쪽 값이 오른쪽 함수의 첫 번째 인자로 들어가는 걸 상기하자. 위 코드를 pipe operator를 쓰지 않는다면 다음과 같은 형태로 조합될 것이다.

if_carbonated_do(
  if_carbonated_do(
    Carbonate.run(n, 15, "FizzBuzz"),
    & Carbonate.run(&1, 3, "Fizz")),
  & Carbonate.run(&1, 5, "Buzz"))

아래는 전체 코드다.

defmodule FizzBuzz do
  def run(n) do
    n
    |> Carbonate.run(15, "FizzBuzz")
    |> if_carbonated_do(& Carbonate.run(&1, 3, "Fizz"))
    |> if_carbonated_do(& Carbonate.run(&1, 5, "Buzz"))
    |> last_step()
  end

  defp if_carbonated_do(result, fun) when is_function(fun, 1) do
    case result do
      {:carbonated, _str} = final -> final
      {:uncarbonated, n} -> fun.(n)
    end
  end

  defp last_step(result) do
    case result do
      {:uncarbonated, n} -> n
      {:carbonated, str} -> str
    end
  end
end

iex> FizzBuzz.run(1)
1
iex> FizzBuzz.run(6)
"Fizz"
iex> FizzBuzz.run(5)
"Buzz"
iex> FizzBuzz.run(30)
"FizzBuzz"
iex> FizzBuzz.run(17)
17

감동이다. Unhappy path(예외 흐름)과 Happy path(주요 흐름)와 엮어서 input으로 넣고 함수는 그 값을 꺼내서 처리하고 다시 Unhappy path와 Happy path를 처리할 수 있게 묶어서 다음 함수로 건넨다. 이렇게 input보다 output이 더 많은 함수를 조합할 수 있다.

여기서 낯선 if_carbonated_do/2 함수의 일반화된 이름이 있는지 궁금해진다. 감동적인 접근이지만 이런 건 벌써 형님 누님들이 다 해보고 이름도 그럴듯하게 붙여놨을 것이다.

위에서 본 if_carbonated_do/2 함수를 bind라고 부른다.

bind = fn result, next_function ->
  case result do
    {:uncarbonated, n} ->
      next_function.(n)
    {:carbonated, _str} = other ->
      other
  end

bind로 이름만 바꿨지 위 예제에서 사용한 if_carbonated_do/2 함수와 동작이 같다. bind는 Monad(모나드)와 관련된 개념이다. 값을 꺼내서 적용하고 다시 감싸서 다음 연산과 연결해 주는 역할을 한다. 나왔다 모나드! 순간 가까워졌다는 생각이 들지만 엄밀하게 정의해서 좀 더 거리를 벌려보자.

bind :: (M a) -> (a -> M b) -> (M b) (일반적으로 >>= 로 표현됨)는 M a 타입의 모나드 값(monadic value)과 기본 타입 a 의 값을 받아들이는 함수 f 를 받습니다. Bind는 a 의 포장을 풀고(unwrap) f 를 적용한 후 f 의 결과를 모나드 값 M b 로 처리할 수 있습니다.

Monad (functional programming) - en.wikipedia.org

하나씩 풀어서 멀어졌던 거리를 다시 좁혀보자.

• M a 타입의 모나드 값(manadic value)
  • {:carbonated, result} 또는 {:uncarbonated, n} 를 가리킨다
  • Either 모나드로 볼 수 있음
• 기본 타입 a 의 값을 받아들이는 함수 f
  • Carbonate.run/3 함수이다
  • 입력으로 숫자를 받는다
    • 예) 1, 2, 3
  • 출력은 M b 값이다
    • 예) {:carbonated, "Fizz"}, {:uncarbonated, 10}

모나드의 형체가 어렴풋이 보인다. 결국 함수 합성을 하기 위해 일반화시킨 개념인 것이다. 뭔가 신난다.

마치며

FP(Functional Programming)에 대한 이해가 더 높아진 느낌이다. 합성이라고 하면 함수 함성만 떠올리기 쉬운데, 타입 또한 합성의 대상이다.

Currying(커링)과 Monad(모나드)를 이렇게 설명해야 하는 거구나. 함수 조합으로 설명해서 “왜?”에 대한 답을 주니깐 확실히 이해된다. 모나드를 상자에 넣고 bind는 상자에서 값을 꺼내고 다시 상자에 넣고 이런 식으로 설명한 걸 봤을 때는 당최 이해되지 않았다. 지금 생각하니 “왜?”가 빠진 설명이었다.

함수형 프로그래밍의 핵심인 함수 합성을 정말 쉽고 재미있게 설명한다. 대박. 철로로 합성을 설명하니 이해가 정말 잘 된다. 모나드 등장할 때는 소름. 너무 좋은 발표라서 블로그에 정리할 계획 - The Power of Composition - Scott Wlaschin #functionalprogramming https://t.co/TaUZYdNpgA

— 오종빈(Jongbin Oh) (@ohyecloudy) April 28, 2019

벌써 6년이 지났네. 드디어 정리했다.

links

• Syntactic sugar - en.wikipedia.org(archive)
• 커링 - ko.wikipedia.org(archive)
• 함수형 프로그래밍 - ko.wikipedia.org(archive)
• Tagged union - en.wikipedia.org(archive)
• Monad (functional programming) - en.wikipedia.org(archive)
• 객체 지향 프로그래밍 - ko.wikipedia.org(archive)
• 로마 숫자 - ko.wikipedia.org(archive)
• Partial application - en.wikipedia.org(archive)
• Fizz buzz - en.wikipedia.org(archive)
• The Power of Composition - Scott Wlaschin - youtube.com