LoginSignup
19
11

More than 1 year has passed since last update.

ScalaAdvent Calendar 2022Day 21
@Kory__3

Scala と Free モナドで入門するモナド

Last updated at Posted at 2022-12-21

この記事は Scala Advent Calendar 2022 の 21 日目の記事です。1

It's a standing joke in the Haskell community that every Haskell programmer,
as part of his or her learning process, will eventually write one or more
monad tutorials. I'm certainly no exception.

拙訳: Haskell コミュニティでは、「Haskell プログラマは、学習プロセスの中でモナドの解説記事の一つや二つをいつしか書くものだ」というのがお決まりのジョークになっている。当然私も例に漏れない。

Yet Another Monad Tutorial (part 1: basics)

概要

モナドとして知られる構造があります。

モナドはよく「計算」や「作用 (Effect)」の抽象化だ、などと（特に純粋関数型プログラミングの文脈で）持てはやされているわけですが、僕はこの主張を落とし込んだモナド自体の説明をあまり読んだことがありませんでした2。この記事では、モナドの「計算そのものの構造を抽象化した構造である」という側面を強調するため、 free operational monad として知られる3 データ型を通してモナドについて見てみます。

記事内のプログラムは Scala 3 で記述することにします。

前提知識

以下の知識・経験を仮定します。

必須

  • 手続き型プログラミングの経験
  • 再帰関数を書いたことがある
  • List の map などの高階関数を扱ったことがある

あると嬉しい (降順)

  • JavaScript の Promise や JVM での Future などでの、コールバックを利用した非同期プログラミングの経験、あるいは継続渡しスタイルに関する知識
  • 末尾再帰最適化、あるいは @tailrec アノテーションに関する知識
  • アセンブリ言語やCPUアーキテクチャでみられる「命令セット」に関する直感
  • 高カインド型に関する知識
  • 契約プログラミングに関する知識

「入門する」とタイトルにあるように、モナドそのものについて知らずとも読めるように書いたつもりですが、どちらかというと「初手でこうやって説明するとうまくいくのかな」、といった実験的な記事なので、もしかしたら初見では理解が難しいかもしれません。

プログラムを値として扱う

手続き型のプログラミングにおいては、プログラムの実行が「関数の最初から最後まで、順番に」行われるという性質に基づいて、複数の副作用（例えば、ユーザーから入力を受け取ったり、ローカルコンピューター上の時刻を読み取ったり、外部 Web サーバー、デバイスないしコンソールなどにデータを送るなど）をうまい具合に組み合わせることでプログラム全体を正しく動作させることを目指します。

純粋関数型プログラミングでは、「副作用を正しく組み合わせるには細心の注意を払う必要がある」、ないし、「副作用を我々が書くプログラムに埋め込むのは早まった最適化 (premature optimization) である」という立場4を取ります。副作用を積極的に起こしていくのではなく、「副作用を起こす手続き型のプログラム (の構文木) を吐き出す純粋なプログラムを書く」といった一種のメタプログラミングを行います。

こういったメタプログラミングを行うにあたって、使える仕組みや機構がいくつか存在します。

例えば、Scala 3 で導入されたビルトインの メタプログラミング機能 (ScalaMatsuri2020 での発表の前半部分で詳しく解説されています) では、

  • コンパイル時に
  • Scala のソースコードを

吐き出すようなメタプログラミングを行うことができます。しかしながら、今回は

  • 実行時に
  • もっと小さな、手軽に操作できる言語の構文木を

吐き出すことを目標としてみます。実行時にソースコードを吐き出してそれを評価する、という二段階の実行を行うことで、最終的には「並列的で結果が決定的に定まらないプログラム」なども扱えるようになることを見ていきます。

「手続き型プログラム」はどんな形をしているか？

この記事において、「プログラムを表現する」というのはデータ型を用いてプログラムの構文木を表現することを言います。どういったデータ型を用意することでそれらしい表現ができるかを検討するために、そもそも手続き型プログラムがどのような形をしているかを考えてみます。

型 A の値を返す手続き型のプログラムは、よく次のような構造を持ちます。

val 変数1: [型1] = [型1 の型が付く式];
val 変数2: [型2] = [型2 の型が付き、変数1 を含んでいたりいなかったりする式];

[変数1 と変数2 を含んでいたりいなかったりする 型3 が付く式];

val 変数4: [型4] = [型4 の型が付き…]

return [A の型が付き、変数1, 変数2, 変数4 を含んでいたりいなかったりする式];

真ん中にある式のみが書かれた文は、返された値が使われていない変数に代入されている式と考えることもできます。よって、先ほどのプログラムは次のような構造で表現できます。

val 変数1: [型1] = [型1 の型が付く式];
val 変数2: [型2] = [型2 の型が付き、変数1 を含んでいたりいなかったりする式];
val 変数3: [型3] = [型3 の型が付き、変数1 と変数2 を含んでいたりいなかったりする式];
val 変数4: [型4] = [型4 の型が付き…]

return [A の型が付き、変数1, 変数2, 変数3, 変数4 を含んでいたりいなかったりする式];

また、一時変数をいくつか用意することで、それぞれの変数宣言の右辺で単一のビルトイン関数呼び出しが行われるものだと考えることができます。最後の return に渡されている式に関しても、一旦一時変数に式の結果が格納されて、その変数が return されていると考えることができます。

すると、先ほどのプログラム内で「式」であったものはすべて「何らかのビルトイン関数の呼び出し」であるとまで考えることもできます。

以後、これら「ビルトイン関数」の事を、アセンブリ言語の単一の命令になぞらえて「ビルトイン命令」と呼ぶことにします。

結局、プログラムは以下のような構造を持っていると考えられます。

// 変数1 の右辺にあったすべての関数呼び出しの結果を一時変数に入れる
val 変数1_1: [型1_1] = [型1_1の戻り値型を持つビルトイン命令]([定数からなる引数リスト])
val 変数1_2: [型1_2] = [型1_2の戻り値型を持つビルトイン命令]([定数からなる引数リスト])
// ...
val 変数1_n: [型1_2] = [型1_2の戻り値型を持つビルトイン命令]([定数からなる引数リスト])

val 変数1: [型1] = [型1 の戻り値型を持つビルトイン命令]([変数1_1, ..., 変数1_n と定数のみからなる引数リスト])

// 変数2 の右辺にあったすべての関数呼び出しの結果を一時変数に入れる
val 変数2_1: [型2_1] = ...
// ...
val 変数2_m: [型2_m] = ...

val 変数2: [型2] = ...

// ...

return [A の型が付く 変数1, 変数2, ... のいずれか];

ここまでの議論で、手続き型のプログラムは

  • 利用できるビルトイン命令が定まっており
  • 変数にビルトイン命令呼び出しの結果が格納されていき
  • ビルトイン命令に今までに定義された変数を渡すことで副作用が発生しており
  • 最終的に値が返却される

といった構造を持っていることがわかりました。

…というのは少し誤魔化しを含んでいて、実際の手続き型プログラムは if による分岐や while による繰り返し処理などを含んでいます。プログラムを表現するにあたっては、これらがうまく記述出来ないと困ります。

if や while なども最初から正確に表そうとすると複雑になってしまいそうなので、まずは「利用できるビルトイン命令」を固定して、逐次的なビルトイン命令の呼び出しをどう表現すれば良いかを考えてみます。

「記憶領域に読み書きすることが許されたプログラム」を愚直に表現してみる

具体例として、「単一の Int 型の (どんな Int 値で初期化されたかはわからない) メモリ領域が与えられており、それに対する読み書き操作ができる」といったプログラムを表現することを考えてみます。

二つのビルトイン命令

  • def writeValue(x: Int): Unit (与えられたメモリ領域に x を書き込む関数)
  • def readValue(): Int (与えられたメモリ領域から Int 値を読み出す関数)

がある言語を考えます。例えば、この小さな命令型の言語で書かれた次のようなプログラムを考えます。

val initialValue: Int = readValue();
val writeResult: Unit = writeValue(initialValue * 2);

return initialValue;

先ほどの「手続き型のプログラムの構造」で得られた結論をそのままデータ型に落としてみます。どのビルトイン命令を呼び出しているかを表現するためには、 Scala 3 の enum を利用します。

// ビルトイン命令呼び出しに渡される式 (変数の参照か定数)
enum Term:
  case Variable(variableName: String)
  case IntLiteral(constant: Int)

// 右辺に現れるビルトイン命令呼び出し
enum BuiltInFunctionCall_1:
  case WriteValue(Term)
  case ReadValue

// 変数定義の式
case class VariableDefinition(
  // 定義する変数名
  variableName: String,
  // 右辺の式
  rightHandSide: BuiltInFunctionCall
)

// 一つのプログラムの表現
case class NaiveProgram(
  // 変数定義の列
  variableDefinitions: List[VariableDefinition],
  // return に渡される式
  returnTerm: Term
)

この NaiveProgram 型で先ほどの命令型のプログラムを表現しようとしてみます。

NaiveProgram(
  List(
    VariableDefinition(
      "initialValue",
      BuiltInFunctionCall.ReadValue
    ),
    VariableDefinition(
      "writeResult",
      // "initialValue * 2" と書きたいが、
      // これは一体どうやって表現すればよいのか？
      BuiltInFunctionCall.WriteValue(???)
    )
  ),
  Term.Variable("initialValue")
)

initialValue * 2 の部分がうまく表現できていませんね。

NaiveProgram はプログラムの表現としては

  1. 純粋な関数で計算されている引数を表現できない
  2. Int リテラルしか定数として記述できない
  3. プログラム全体がどの型の値を返してくるのかがすぐに分からない（そもそも変数に一切型が付いていない！）
  4. 変数への参照が有効なものなのかがすぐに分からない

といった問題を抱えていることが分かります。(1) と (2) については、それぞれ Term と BuiltInFunctionCall_1 の case を大量に増やすことでなんとか解決できますが、 (3) と (4) については型システムを自分で実装したり、変数の参照を自分で捕捉する仕組みを実装したりする必要があります。

文字列で変数を表す限り、これらの問題の解決は難しそうです。

再訪：「手続き型プログラム」はどんな形をしているか？

記憶領域に読み書きすることが許されたプログラムを愚直に表現してみる のセクションで現れた問題を解決するためには、表現を大きく変える必要がありそうです。

実際、これらの問題の解決策として、元の手続き型のプログラムをすべてコールバック形式で書き直すとうまくいくことが知られています。

元のプログラムは以下のようなものでした。

val initialValue: Int = readValue();
val writeResult: Unit = writeValue(initialValue * 2);

return initialValue;

ここで、writeValue と readValue 関数をそれぞれ

  • def writeValueK[A](x: Int)(callback: () => A): A
  • def readValueK[A]()(callback: Int => A): A

のような、「callback を受け取って、 read/write を実行し、結果を用いて callback を実行する」関数であると再解釈します。writeValueK と readValueK を使うと、元のプログラムは次のように書けます。

callback のようなコールバックは「プログラムが完了したその後の処理」として考えることができます。「その後の処理」の概念には名前が付いており、継続(Continuation)と呼ばれています。また、継続を受け取る関数によってプログラムを書く書き方のことを継続渡しスタイル(Continuation Passing Style; CPS)と呼びます。

readValue / writeValue を用いた「変数宣言文のリスト」をプログラムとして表そうとする代わりに、次のように継続渡しスタイルで書かれたプログラムをデータ型で表すことを考えてみます。

readValueK[Int]()(initialValue: Int =>
  writeValueK[Int](initialValue * 2)(writeResult: Unit =>
    initialValue
  )
)

まず、readValueK に渡っている callback が、中身にさらにプログラムを含んでいることに注目します。

readValueK[Int]()(initialValue: Int =>
  |writeValueK[Int](initialValue * 2)(writeResult: Unit =>
  |  initialValue
  |)
  ^ この部分すべてが一つのプログラム
)

すると、readValueK に渡っている callback は、「initialValue を受け取って別のプログラムを吐き出している関数」であると考えることができます。

同様に、(readValueK の callback 内の) writeValueK に渡っている callback は、「writeResult を受け取って別のプログラムを吐き出している関数」であると考えることができます。この時吐き出されるプログラムは、 writeResult を無視し、(プログラムの定数として埋め込まれた) initialValue を結果として即座に終了するプログラムです。

readValueK[Int]()(initialValue: Int =>
  writeValueK[Int](initialValue * 2)(writeResult: Unit =>
    |initialValue
    ^ これも一つの「プログラム」であると考える
  )
)

今の議論に基づいて、 Program1[A] 型を定義してみます。(後程 Program2[A] なども定義するので、名前が衝突しないように番号を振っておきます)

// A の値を return するプログラム
enum Program1[A]:
  // 何もせず、即座に与えられた値で終了するプログラム
  case Finish(returnValue: A)

  // readValue を実行し、コールバックに結果を渡して実行するプログラム
  case ReadValueK()(callback: Int => Program1[A])

  // writeValue を実行し、コールバックに結果を渡して実行するプログラム
  case WriteValueK(value: Int)(callback: Unit => Program1[A])

すると、元の命令型のプログラムは Program1[A] を用いて次のような表現をすることができます。

import Program1._

ReadValueK()((initialValue: Int) =>
  WriteValueK(initialValue * 2)((writeResult: Unit) =>
    Finish(initialValue)
  )
)

この表現で前のセクションで現れた (1) から (4) の問題は解決したでしょうか？
一つずつ見てみます。

  • (1): 一つ前の例のように、副作用のない (Scala の) 処理をコールバックのラムダ式内で使ってよいのであれば、Program1 のコンストラクタに計算した値を渡すだけで複雑な引数を表現することができます。
  • (2): Scala の型を Program1 のコンストラクタが受け取ってくれるので、型さえ合っていれば Scala のリテラルを自由に記述することができます。
  • (3): Program1[A] は A 型の値を返します。元のプログラムの各変数はコールバック関数の引数に対応しており、これらに正しい型が付いていることは Scala コンパイラが保証してくれます。
  • (4): 変数の参照はより外側にあるコールバックの引数への参照で置き換えられており、やはり Scala コンパイラが参照が切れていないことを保証してくれます。

良さそうですね！

「関数呼び出し」の概念を言語に組み込む

基本的な手続き型プログラムの表現はうまくいっていそうなので、さらに複雑なプログラムもうまく表せるようにデータ型を拡張していきます。

手続き型のプログラミング言語で大きなプログラムを組む有力な手法として、構造化プログラミング (Wikipedia) として知られるものがあります。

構造化プログラミングでは、大きなプログラムを組み上げるときにすべての処理を一つの関数として記述するのではなく、処理を (ビルトインではない、ユーザーが定義した) 副作用を含む関数達に分割し、それら関数を正しい順序で呼ぶことでプログラムを組むことが推奨されます。

分割された処理一つ一つの事を「サブルーチン」と呼びます。我々の目的は大きな命令型プログラムをも表せるデータ型を作る事であったので、「サブルーチン呼び出し」の処理を Program1 型に組み込むことを考えてみます。

一つの命令は一つの enum case (コンストラクタ) に対応する

とはいっても、この拡張は非常に簡単です。型 B の値を返すプログラム一つは Program1[B] に対応しているので、「Program1[B] を受け取って (それを実行し、実行結果の) B を結果とする命令」を追加してしまえば良いはずです (Program1 に命令を追加すると型が変わるので、以後 Program2 として呼び分けます)。命令型の関数としては、これは次のようなビルトイン命令で表されることでしょう。

def callSubroutine[B](subroutine: Program2[B]): B

継続渡しスタイルで書かれたプログラムでは、この命令は次のような宣言になる事でしょう。

def callSubroutineK[A, B](subroutine: Program2[B])(callback: B => Program2[A]): A

結局、各命令 readValue / writeValue に対してそれに対応する enum case (コンストラクタ) を定義したように、 callSubroutine に対応する (callSubroutineK と同じシグネチャの) enum case を追加することでサブルーチン呼び出しが表現できるようになることが分かります。

// A の値を return するプログラム
enum Program2[A]:
  // 何もせず、即座に与えられた値で終了するプログラム
  case Finish(returnValue: A)
  
  // readValue を実行し、コールバックに結果を渡して実行するプログラム
  case ReadValueK()(callback: Int => Program2[A])

  // writeValue を実行し、コールバックに結果を渡して実行するプログラム
  case WriteValueK(value: Int)(callback: Unit => Program2[A])

  // callSubroutine を実行し、コールバックに結果を渡して実行するプログラム
  //   型引数 A はプログラム全体が返す値の型であり、
  //   型引数 B はサブルーチンが返す値の型。
  //
  // CallSubroutineK[A, B] が Program2[A] であることを明示するために、
  //   extends Program2[A] と書く必要がある。
  case CallSubroutineK[A, B](subroutine: Program2[B])
                            (callback: B => Program2[A])
    extends Program2[A]

CallSubroutineK 以外の命令から継続を剥がす

CallSubroutineK によって、任意の Program2[B] を実行して、コールバック B => Program2[A] に結果を流し込むことが表現できるようになりました。

すると、readValue や writeValue に対応するプログラムに継続を持たせる代わりに、「ビルトイン命令を実行するプログラム」をサブルーチンであると考えることで、 CallSubroutineK 以外が継続を持たなくても良くなります。

この考えを元に、 Program2 を改造して Program3 を定義します。

// A の値を return するプログラム
enum Program3[A]:
  // 何もせず、即座に与えられた値で終了するプログラム
  case Finish(returnValue: A)
  
  // readValue を実行するプログラム
  case ReadValue() extends Program3[Int]

  // writeValue を実行するプログラム
  case WriteValue(value: Int) extends Program3[Int]

  // callSubroutine を実行し、コールバックに結果を渡して実行するプログラム
  //   型引数 A はプログラム全体が返す値の型であり、
  //   型引数 B はサブルーチンが返す値の型。
  //
  // CallSubroutineK[A, B] が Program3[A] であることを明示するために、
  //   extends Program3[A] と書く必要がある。
  case CallSubroutineK[A, B](subroutine: Program3[B])
                            (callback: B => Program3[A])
    extends Program3[A]

ReadValueK / WriteValueK が ReadValue / WriteValue に置き換わって、シグネチャがシンプルになりました。

例：メモリに書かれた値を 2 倍する操作を複数回繰り返す

例えば、次のような命令型のプログラムを考えます。

// メモリ領域に書かれた値を 2 倍する
def doubleMemoryValue(): Unit =
  val initialValue: Int = readValue();
  val writeResult: Unit = writeValue(initialValue * 2);

  return ();

// doubleMemoryValue を 3 回呼び出すことによって、
// メモリ領域に書かれた値を 8 倍する。
// 最後に書かれていた値を結果として返す。
def eightFoldMemoryValue(): Int =
  val result1: Unit = doubleMemoryValue();
  val result2: Unit = doubleMemoryValue();
  val result3: Unit = doubleMemoryValue();
  val finalValue: Int = readValue();

  return finalValue;

まず、 doubleMemoryValue は次のような Program3[Unit] の値として書けます。

import Program3._

val doubleMemoryValueProgram: Program3[Unit] =
  CallSubroutineK(ReadValue())((initialValue: Int) =>
    CallSubroutineK(WriteValueK(initialValue * 2))((writeResult: Unit) =>
      Finish(())
    )
  )

そこで、サブルーチン (doubleMemoryValue()) の呼び出しを callSubroutine(doubleMemoryValueProgram) で置き換えれば、 eightFoldMemoryValue は次のように書きなおせます。

def eightFoldMemoryValue(): Int =
  val result1: Unit = callSubroutine(doubleMemoryValueProgram);
  val result2: Unit = callSubroutine(doubleMemoryValueProgram);
  val result3: Unit = callSubroutine(doubleMemoryValueProgram);
  val finalValue: Int = readValue();

  return finalValue;

結局、eightFoldMemoryValue は次のような Program3[Unit] の値として表現できます。

import Program3._

val doubleMemoryValueProgram: Program3[Unit] =
  // 省略

val eightFoldMemoryValueProgram: Program3[Int] =
  CallSubroutineK(doubleMemoryValueProgram)((result1: Unit) =>
    CallSubroutineK(doubleMemoryValueProgram)((result2: Unit) =>
      CallSubroutineK(doubleMemoryValueProgram)((result3: Unit) =>
        CallSubroutineK(ReadValue())((finalValue: Int) =>
          Finish(finalValue)
        )
      )
    )
  )

if と while はどう表現したらいい？

ここまで、 if と while をどのように表現すれば良いかを考えていませんでした。実は、先ほど定義した Program3 は、 if や while が書かれたプログラムを表現できるほどに強力なデータ型です。

それぞれの構文をどのように表せばよいかを例を交えて考えてみます。

if の表現

「メモリに元々書かれていた値が偶数なら 0 を、そうでなければ 1 を書き込む」ようなプログラムを考えてみます。

val initialValue = readValue();

if (initialValue % 2 == 0) 
  writeValue(0);
else
  writeValue(1);

return ();

この分岐は、CallSubroutineK(ReadValue()) に渡すコールバック内で if を書くだけで表現できます。

import Program3._

CallSubroutineK(ReadValueK())((initialValue: Int) =>
  CallSubroutineK(
    if (initialValue % 2 == 0)
      WriteValue(0) // : Program3[Unit]
    else
      WriteValue(1) // : Program3[Unit]
  )((ifBlockResult: Unit) =>
    Finish(())
  )
)

一般に、命令型のプログラムに現れるどのような if であっても、

  • 条件部分が副作用を含まないように別のサブルーチンに切り出した上で
  • そのサブルーチンの結果を使って普通に if で分岐して、継続の中で実行するプログラムを切り替える

といった方法で Program3 で表現することができます。

while の表現

例：メモリに書かれた値を 2 倍する操作を複数回繰り返す のセクションで定義した doubleMemoryValueProgram を利用して、次のような命令型のプログラムを考えます。

val input: Int = readValue();

// 1 でメモリ領域を初期化する
val writeResult: Unit = writeValue(1);

// メモリ領域が input 以上になるまで
// メモリ領域の中身を二倍し続ける
//   …オーバーフローの事は考えないこととする
var currentMemoryValue: Int = readValue();
while (currentMemoryValue < input) {
  val subroutineResult: Unit = callSubroutine(doubleMemoryValueProgram);
  currentMemoryValue = readValue();
}

// 最終的な値を返す
val finalValue: Int = readValue();
return finalValue;

このコードには var で定義された再代入可能な変数が表れており、このままではうまく Program3[Int] の値に落とせそうにありません。そこで、

var currentMemoryValue: Int = readValue();
while (currentMemoryValue < input) {
  val subroutineResult: Unit = callSubroutine(doubleMemoryValueProgram);
  currentMemoryValue = readValue();
}

の部分を、次のような再帰関数とその呼び出しに置き換えます。

// ループの一回のイテレーション(繰り返し)を実行する
def loopIteration(currentMemoryValue: Int): Unit =
  if (currentMemoryValue < input)
    val subroutineResult: Unit = callSubroutine(doubleMemoryValueProgram);
    val nextIterationMemoryValue: Int = readValue();

    // ループの次のイテレーションに入る
    return loopIteration(nextIterationMemoryValue);
    //     ~~~~~~~~~~~~~
    //     ^ 再帰呼び出し
  else
    // 「ループを抜ける」
    return ();

val initialMemoryValue: Int = readValue();
val loopResult: Unit = loopIteration(initialMemoryValue)

これで再代入がすべて消えました。

寄り道：末尾再帰最適化

今行ったプログラム変換の「逆の」操作は末尾再帰最適化として知られています。 Scala では、loopIteration のように「再帰呼び出しが関数の一番最後の処理として行われている (= 末尾再帰している)」ような再帰関数に @scala.annotation.tailrec アノテーション を付けることで、while 文を利用したプログラムにコンパイルすることができます。

再帰により return をせずに関数を呼び出し続けると StackOverflowError が発生してプログラムがクラッシュしますが、末尾再帰最適化を行うと (実行されるのはただの while 文なので) スタックが消費されず、 StackOverflowError が起こるようなことはありません。

一般に、「関数のパラメータ」を「while 文が再代入していく変数」へと翻訳することで末尾再帰最適化は行われます。逆に、 while 文が再代入する変数をすべて再帰関数のパラメータとしてまとめることで、 while 文は末尾再帰する再帰関数へと変換することができます。先ほど行ったプログラム変換はこれに基づくものです。

この部分をすべて継続渡しスタイルで書くと次のようになります。

def loopIterationK[A](currentMemoryValue: Int)(callback: Unit => A): A =
  return if (currentMemoryValue < input)
    callSubroutineK(doubleMemoryValueProgram)((subroutineResult: Unit) =>
      readValueK()((nextIterationMemoryValue: Int) =>
        // ループの次のイテレーションに入る
        loopIterationK(nextIterationMemoryValue)(callback)
      )
    )
  else callback(()) // 「ループを抜ける」

readValueK()((initialMemoryValue: Int) =>
  loopIterationK(initialMemoryValue)((loopResult: Unit) =>
    // 処理の続き
    // ...
  )
)

この部分を Program3 で表現しようとすると次のようになります。

import Program3._

def loopIterationProgram(currentMemoryValue: Int): Program3[Unit] =
  if (currentMemoryValue < input)
    CallSubroutineK(doubleMemoryValueProgram)((subroutineResult: Unit) =>
      CallSubroutineK(ReadValueK())((nextIterationMemoryValue: Int) =>
        // 「ループの次のイテレーション」を継続のプログラムとして
        //   指定するだけで良い！
        loopIterationProgram(nextIterationMemoryValue)
      )
    )
  else Finish(())

CallSubroutineK(ReadValueK())((initialMemoryValue: Int) =>
  CallSubroutineK(loopIterationProgram(initialMemoryValue))((loopResult: Unit) =>
    // 処理の続き
    // ...
  )
)

結局、元のプログラム全体は次のような Program3[Int] の値として記述できます。

import Program3._

CallSubroutineK(ReadValueK())((input: Int) =>
  // 1 でメモリ領域を初期化する
  CallSubroutineK(WriteValueK(1))((writeResult: Unit) =>

    // ループの一回のイテレーション(繰り返し)を実行するプログラム
    def loopIterationProgram(currentMemoryValue: Int): Program3[Unit] =
      if (currentMemoryValue < input)
        CallSubroutineK(doubleMemoryValueProgram)((subroutineResult: Unit) =>
          CallSubroutineK(ReadValueK())((nextIterationMemoryValue: Int) =>
            // 「ループの次のイテレーション」を継続のプログラムとして
            //   指定するだけで良い！
            loopIterationProgram(nextIterationMemoryValue)
          )
        )
      else Finish(())

    // ループを開始する
    CallSubroutineK(ReadValueK())((initialMemoryValue: Int) =>
      CallSubroutineK(loopIterationProgram(initialMemoryValue))((loopResult: Unit) =>
        // 最終的な値を返す
        CallSubroutineK(ReadValueK())((finalValue: Int) =>
          Finish(finalValue)
        )
      )
    )
  )
)

万能な命令型プログラムのモデル

これまでは、比較的小さな命令セット (readValue + writeValue + callSubroutine) を使った命令型プログラムを考えてきました。

サブルーチンへの呼び出しがあることで if や while は表現できますが、このままでは外部サーバーへの通信はおろか、例外の throw / catch を通したエラーハンドリングや、なんとコンソールへ文字列を出力することすらできません。

ここで一つの疑問が現れます。とてもとても強力な命令セットを用意して、常識的に考えられるすべての命令型プログラムを表現できるようなデータ型を作ることは可能でしょうか？

ようこそ、 cats.effect.IO の世界へ。

cats.effect.IO

cats.effect.IO は cats-effect によって提供されているデータ型です。 cats.effect.IO は非常に広範囲の命令型のプログラムを表現することを目標としています。例えば、 cats.effect.IO は次のような「ビルトイン命令」を含んでいます。

  • 何もせずにすぐに終了する命令 (Pure)
  • サブルーチンを呼び出す命令 (FlatMap)
  • 任意の 同期的な処理 (() => A の形をした Scala の関数) を実行する命令 (Delay)
  • 任意の 非同期的な処理を実行する命令 (IOCont)
  • Throwable を throw する命令 (Error) と、投げられた Throwable をハンドル (catch) する命令 (HandleErrorWith)
  • サブルーチンをバックグラウンドで並列に実行して、新たに開始した軽量スレッド (Fiber) への参照を得る命令 (Start)
  • 特定の ExecutionContext (≈ スレッドプールの指定) 上でサブルーチンを実行する命令 (EvalOn)

Java のエコシステム内に元々あった任意の (命令型で書かれた) 処理を Delay と IOCont によって cats.effect.IO の 1 命令として埋め込むことができるため、おおよそどういった命令型の処理も cats.effect.IO に埋め込めることが分かります。

また、上で挙げたように、いくつかの命令は IOCont や Start での並列実行を制御するものになっており、並列プログラミングもシームレスに行えるようになっています。

具体的な使い方や、 cats.effect.IO でどのようにプログラムを書けば良いか、というのは、Scala Advent Calendar 2022 13日目の記事 で説明されています。また、 cats.effect.IO が具体的にどのような命令を用意しているかが気になる方は、実際の実装を眺めると面白いと思います (内部実装なのでコメントはあまりついていませんが…)。

ここまでのプログラム型をすべて統一するデータ型

命令型プログラムを表すデータ型は、データ型を enum として定義し、

  • すぐに a を return するようなプログラムを表す Finish(a)
  • サブルーチン subroutine を呼び出してコールバック callback に結果を渡すプログラムを表す CallSubroutine(subroutine, callback)

を基本的なコンストラクタとしたうえで、「命令セット」の各命令に対応するコンストラクタを用意することで表現できることを見てきました。この構成では、表現したい命令型のプログラムが「どのような命令セットを持つか」によって、別々のデータ型 (Program2, Program3, cats.effect.IO, ...) を用意する必要がありました。

これは何やら抽象化ができそうです。これらの別々に定義された「命令型プログラム」のデータ型をたった一つのジェネリックなデータ型ですべて表すことはできるでしょうか？

追加する命令の部分を抽象化したいので、まずは「命令」のみの部分をデータ型にまとめます。 Program3 は 「与えられたメモリ領域から Int 値を読み出す」と「与えられたメモリ領域に Int 値を書き込む」の命令セットを持っていましたから、この命令セットを表すデータ型 SingleMemoryInstruction を定義します。

enum SingleMemoryInstruction:
  case ReadValue()
  case WriteValue(value: Int)

このままでは「ReadValue は Int 型の結果が返ってくる命令で、 WriteValue は Unit 型の結果が返ってくる命令である」という情報が表現できていないので、 SingleMemoryInstruction に型引数 ResultType を追加し、次のような定義をします。

enum SingleMemoryInstruction[ResultType]:
  case ReadValue() extends SingleMemoryInstruction[Int]
  case WriteValue(value: Int) extends SingleMemoryInstruction[Unit]

良さそうです。 Program3 は次のような SingleMemoryInstructionProgram と等価になります。

// A 型の値が結果になるような、
// `SingleMemoryInstruction` が命令として現れるプログラム
enum SingleMemoryInstructionProgram[A]:
  // すぐに終了するプログラム
  case Finish(value: A)

  // 命令を実行して命令の結果を得るプログラム
  case RunInstruction(instruction: SingleMemoryInstruction[A])

  // サブルーチンを呼び出して結果でコールバックを実行するプログラム
  case CallSubroutine[Instruction[_], A, B](
    subroutine: Program[Instruction, A],
    callback: A => Program[Instruction, B]
  ) extends Program[Instruction, B]

これで、

  • Finish と CallSubroutine という基本的な部分
  • 命令セットに関係する RunInstruction という部分

の二つに Program3 を分離することができました。

あとは、命令セットを表していた SingleMemoryInstruction の部分を型引数に移すことで、任意の命令セット Instruction から「Instruction を使うプログラム」 を構成できるようになりそうです。

ただし、 SingleMemoryInstruction は型引数をとって型引数を返す高カインド型なので、型変数として宣言するときは Instruction[_] のように宣言する必要があります (高カインド型がどのようなものであるかは Scalaの「高カインド型」について調べてみました。 を参考にするとよいと思います)。

これに気を付けると、今までのプログラムを表現しているデータ型を (命令セットに関して抽象化した) 次のようなデータ型 Program が定義できます。

// Instruction を命令セットとして利用して A の値を return するプログラム
enum Program[Instruction[_], A]:
  // すぐに終了するプログラム
  case Finish(value: A)

  // 命令を実行して命令の結果を得るプログラム
  case RunInstruction(instruction: Instruction[A])

  // サブルーチンを呼び出して結果でコールバックを実行するプログラム
  //   型変数の数が Program と異なるので、
  //   Instruction[_], A, B を case 内で定義して、
  //   明示的に extends Program[Instruction, B] と書く必要がある。
  case CallSubroutine[Instruction[_], A, B](
    subroutine: Program[Instruction, A],
    callback: A => Program[Instruction, B]
  ) extends Program[Instruction, B]

Finish と CallSubroutine だけを抜き出したインターフェース、モナド

Program は、どんなに小さかったり大きかったりする命令セット Instr[_] が与えられていても、「すぐに終了するプログラム」と「サブルーチンを呼び出すプログラム」を表現することができます。

この、「何もしないプログラムを構築する」と、「サブルーチンを呼び出すプログラムを構築する」演算のみを抽象化したインターフェースとして、モナド (Monad) として知られるインターフェースがあります。

プログラムは一般に [A] =>> Program[Instr, A] の様な高カインド型になっているので、高カインド型で宣言された型変数 F[_] に対して、 Monad[F] は次のように定義された操作を提供します。

// F 上で Finish と CallSubroutine のようなことを行うためのインターフェース
trait Monad[F[_]]: 
  def finish[A](value: A): F[A]
  def callSubroutine[A, B](subroutine: F[A], callback: A => F[B]): F[B]

などに特有の実装規約が存在するように、Monad にも、「プログラムの合成っぽさ」を要求するための実装規約がいくつか知られています。これらはモナド則として知られています。モナド則は、 monad: Monad[F] が正しく実装されているならば、次の等式が成り立っていることを要求します。

  • monad.callSubroutine(monad.finish(x), f) == f(x)
    • 「x ですぐに終わるサブルーチンを呼び出すのは、そもそもコールバックに x を入れて得られるプログラムと同じ」
  • monad.callSubroutine(subroutine, (result) => monad.finish(result)) == subroutine
    • 「すぐに終了するコールバックを渡すのは、サブルーチンをそのまま実行するのと同じ」
  • monad.callSubroutine(monad.callSubroutine(subroutine, callback1), callback2)
    と
    monad.callSubroutine(subroutine, (result) => monad.callSubroutine(callback1(result), callback2))
    が等価
    • 「コールバックを二度渡して得られるプログラムは、一つのまとまったコールバックを渡したプログラムと同じ」

上で提示した Monad trait は非標準的なメソッド名で記述されています。

cats のエコシステムでは、 finish は pure、 callSubroutine は flatMap と呼ばれています。Haskell のエコシステムにおいては finish は return、 callSubroutine は >>= (bind) と呼ばれています。

また、ほとんどの流儀では Monad は Functor の subtrait として定義されていますが、今回は Functor の説明は不要だったため省略しています。

Monad[F] の (実装規約に従って実装された) 値を、F のモナド構造 と呼びます。前述のとおり、F のモナド構造は、F をプログラム(のようなもの)であると考えたうえで、F の上で「何もしないプログラムを構築する」と「サブルーチンを呼び出すプログラムを構築する」を行う手段を提供しています。

用語の濫用により、「最もよく利用されている」モナド構造が存在する F について、そのモナド構造の事を「F モナド」と呼ぶことがあります。例えば、「List モナド」といった時は、最もよく利用されている List のモナド構造 standardListMonad: Monad[List] の事を指します。

Program のモナド構造、Free (Operational) モナド

ここまでのデータ型をすべて統一するデータ型 で紹介したデータ型 Program[F, A] は、任意の型コンストラクタ F[_] について (コンストラクタが呼ばれるだけの) 自然なモナド構造 freeOperationalMonad: Monad[[A] =>> Program[F, A]] を持ちます。これは、 Monad が Program の Finish 部分と CallSubroutine 部分のみを抜き出したインターフェースであることを鑑みると当たり前のようにも思えます。

次の実装は cats の Free.scala を参考にしたものです5。

// Instruction を命令セットとして利用して A の値を return するプログラム
enum Program[Instruction[_], A]:
  case Finish(value: A)
  case RunInstruction(instruction: Instruction[A])
  case CallSubroutine[Instruction[_], A, B](
    subroutine: Program[Instruction, A],
    callback: A => Program[Instruction, B]
  ) extends Program[Instruction, B]

def freeOperationalMonad[Instr[_]]: Monad[[A] =>> Program[Instr, A]] =
  import Program._
  new Monad[[A] =>> Program[Instr, A]]:
    def finish[A](value: A): Program[Instr, A] = Finish(value)

    def callSubroutine[A, B](
      subroutine: Program[Instr, A],
      callback: A => Program[Instr, B]
    ): Program[Instr, B] =
      CallSubroutine[Instr, A, B](subroutine, callback)

この Program[F, A] の自然なモナド構造 freeOperationalMonad は Free (Operational) Monad として知られています。用語の濫用により、 Program[F, A] そのものの事を Free (Operational) Monad と呼ぶことがあります。

紛らわしいことに、単に「Free Monad」といった時は、Free Operational Monad の事を指す場合もあれば、サブルーチン読み出しが組み込まれていない別のデータ型を指すこともあります (例えば、 この記事 は PureScript を通してこのバージョンの Free Monad を解説しています)。サブルーチン呼び出しを一般に行うことができないため、これは我々の Program とは異なる表現力を持つプログラムの表現です。

どちらのモナド構造も (代数学的な理由から) Free Monad と呼ばれるのに相応しい構造なので、どちらが正しいといったことは無いのですが、これら二つの構造を明示的に区別するため、 Program のモナド構造を Free Monad ではなく「Free Operational Monad」や「Freer Monad」と呼ぶことがあります。

先ほど紹介した Monad として知られるインターフェースは Free Operational Monad よりも真に抽象的なインターフェースになっています。つまり、Monad[F] を実装できるような型コンストラクタ F[_] であって、[A] =>> Free[Instr, A] と F が等価になる命令セット Instr[_] が存在しないようなものが存在します。

むしろ、ほとんどの Monad 構造は [A] =>> Free[Instr, A] の形で得られず、例えば

  • Maybe Monad として知られる、型コンストラクタ Option のモナド構造
  • Exception Monad / Either Monad として知られる、固定された型 Err についての型コンストラクタ [A] =>> Either[Err, A] のモナド構造
  • Reader Monad として知られる、固定された型 Env についての型コンストラクタ [A] =>> Env => A のモナド構造
  • State Monad として知られる、固定された型 State についての型コンストラクタ [A] =>> State => (State, A) のモナド構造

などはすべて、 Free Operational Monad と同じにはなりません6。

まとめ

純粋関数型プログラミングでは、プログラムそのものを値として扱い、プログラム達を合成することで副作用を持つプログラムを記述します。

手続き型のプログラムに現れる各命令を「命令のパラメータと継続を受け取ることで、より大きなプログラムを生成するもの」であると捉え直すことで、手続き型のプログラムのモデルを機械的に作ることができます。元の手続き型のプログラムを継続渡しスタイルで書き直せば、後は機械的にプログラムのモデルに翻訳できます。さらに、サブルーチン呼び出しをビルトインの命令として組み込んでおけば、if や while に相当するプログラムをもモデルに翻訳することが可能になります。

この考えを推し進めて様々な命令型の処理を包括できるように表現力を高めたデータ型として、 cats.effect.IO があります。

これら手続き型言語のモデルに似たデータ型をうまく合成するために、 Monad として知られるインターフェースが規定されています。また、ここまで見てきたすべてのプログラムのモデルは、Instruction[_] を「命令セット」を与えるデータ型とすると、 Program[Instruction, A] と呼ばれる構造で表現することができます。 Program[Instruction, A] の「サブルーチンを呼び出すプログラム (CallSubroutine)」と「即座に終了するプログラム (Finish)」のコンストラクタ呼び出しはモナドの構造を成し、 free operational monad と呼ばれています。

参考

  1. 冬休みに入り堕落した生活を送っていたら急に記事を書く気持ちになってきたので、気分をぶち上げるために二日前 (12/19) に参加登録をしました。これが パニックモンスター 駆動生活です。ちなみに、当然参考文献をちゃんと読み漁る時間がありませんでした。こういうことはやめたほうがいいです。っていうか二日で書く文量ではない……… ↩

  2. これは記事を書いている途中に @Alwe_Logic さんから教えてもらったのですが、 @mr_konn さんの 絶対に理解出来ないモナドチュートリアル の「おまけ」セクションで、まさに当記事の説明方針の様なチュートリアルが「あってもよいのではないだろうか」、ということが記述されています。 ↩

  3. このデータ型のモナド構造は Free Monad と呼ばれていたり、 Free Operational Monad と呼ばれていたり、 Freer Monad と呼ばれることもあります。 cats では単に Free という名前のデータ型になっているため、記事タイトルは「Free モナド」としています。 ↩

  4. この考え方は この動画 の開始 15 分で詳しく語られています。 ↩

  5. この実装は厳密には Monad の実装規約を満たせていなさそうです。例えば、 CallSubroutine(Finish(1), n => Finish(n)) は実装規約によれば (n => Finish(n))(1) == Finish(1) と等しいはずですが、そうはなっていません。実は僕自身この点についてはよくわかっていないのですが、「等しい」の概念を「ある一定の正規化に掛けたら等しい」に置き換えるとうまくいくはずです。cats の Free (我々の Program に相当します) にはそのような「正規化」を行うための.stepが定義されており、callSubroutine(r, f) を CallSubroutine(r, f).step のように再定義することでモナド則を満たすと思います (未確認)。実用上、 Free / Program は「インタプリタで実行して結果を見る」ことでしか消費 (≈ 中にあった情報を外に取り出すこと) されないため、「等しい」の概念を「実行結果が常に等しくなるならば二つの Program は等しい」のように置き換えておけば、この記事の実装でも問題ないような気はします(気がするだけ)。間違っていたらコメントで教えてください… ↩

  6. しかしながら、 Free Operational Monad は普遍性として知られる性質から、すべてのモナドと非常に密接な関わりを持っています。命令セットの型 Instruction[_] からモナド構造を持つ型 M[_] へのどのような多相変換 [A] =>> Instruction[A] => M[A] が与えられても、この変換を多相インタプリタ [A] =>> Program[Instruction, A] => M[A] へと「拡張」することができます (この性質を Free　Operational Monad の普遍性と呼びます)。ここでは、線形代数などで現れる、「基底の送り先を決めると、その送り方を空間全体からの線形写像へと一意に拡張できる」という現象と同じことが起こっています。実際、M そのものを命令セットだと考えて、恒等変換 [A] =>> M[A] => M[A] をインタプリタ canonicalInterpreter: [A] =>> Program[M, A] => M[A] に拡張すると、canonicalInterpreter は Program[M, A] が「実際にどのように振舞うのか」という情報を与えてくれます。 canonicalInterpreter で同じ M[A] の値へと評価される Program[M, A] 達をすべて同じものであると考えれば、Program[M, A] (に同一視を入れたもの) は M と同じ構造を持つはずです (ちゃんと言語化できていないので、詳しい人教えてください…)。 ↩

19
11
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
19
11