TypeScript で Algebraic Effects - Object.create(null)

型をそえて.

TL; DR

(実用には向かないものの) TypeScript で Algebraic Effects (たぶん) を扱うライブラリを作ってみました.

背景と課題

コールバック地獄の解決

たとえば Haskell や Scala にあるような Either モナドを, TypeScript でも使いたいとします.

インターフェースは大雑把にはこういう感じ (必要な部分のみ抜粋):

interface Either<L, R> {
  bind<R2>(k: (x: R) => Either<L, R2>): Either<L, R2>;
}

declare function left<L, R>(x: L): Either<L, R>;
declare function right<L, R>(x: R): Either<L, R>;

これを使うと「失敗するかもしれない」計算が以下のように書けます.

// 文字列を数値としてパース
const parse = (str: string): Either<Error, number> => {
  const num = parseFloat(str);
  if (Number.isNaN(num)) {
    return left(new Error(`failed to parse: ${str}`));
  }
  return right(num);
};

// 除算
const divide = (x: number, y: number): Either<Error, number> => {
  if (y === 0) {
    return left(new Error("division by zero"));
  }
  return right(x / y);
};

// 成功: r1 = Right(21)
const r1 = parse("42").bind(x =>
  parse("2").bind(y =>
    divide(x, y)
  )
);

// 失敗: r2 = Left(Error("division by zero"))
const r2 = parse("42").bind(x =>
  parse("0").bind(y =>
    divide(x, y)
  )
);

TypeScript には Haskell や Scala にあるような do-/for-comprehension がないため, 継続渡しスタイルで明に継続 (コールバック) を書いてやる必要があります. この例ではまだシンプルなのでそこまで気にはならないものの, コードが大きくなってくると往々にしてコールバック地獄 (ネストがどんどん深くなってしまう) という問題を生み出します.

(こちらの方が身近な方も多いでしょうが) async/await を使わずに Promise を使った場合にも同様の問題が起こります.

readFile("file1.txt").then(x =>
  readFile("file2.txt").then(y =>
    writeFile("file3.txt", x + y)
  )
);

こういったコールバック地獄を解決する方法として, ジェネレータを使うものがあります. ここでは詳細は割愛しますが, うまく _do という関数を定義してやると, 上の例と同じロジックを以下のようにフラットな (手続き的な) 形で書くことが出来ます.

const r1 = _do(function* () {
  const x = yield parse("42");
  const y = yield parse("2");
  const z = yield divide(x, y);
  return z;
});

Promise についても async/await が標準化される以前は, 上の _do と同様のことを行う co というライブラリが使われたりもしました.

このあたりについては以前記事を書いたので, 詳しくはそちらをご覧ください.

susisu.hatenablog.com

TypeScript による型付けとの両立

さて時代は下り, async/await は当たり前の存在に, また TypeScript を使って静的に型付けすることも当然となりました.

Promise を使ったコードは, async/await を使ってフラットに, かつ TypeScript によって型がつけられる形で書くことができます.

const x = await readFile("file1.txt");
const y = await readFile("file2.txt");
await writeFile("file3.txt", x + y);

一方で Either に対してジェネレータを使った方法はというと, 型をうまくつける方法がありません. 上の例では x, y, z はすべて (手で型注釈を書かない限り) any 型として扱われてしまいます. これはまあ仕方のない話で, yield 式がどのような値に評価されるかはジェネレータを書いた時点ではわからず, _do がどのような処理をするかまで考慮する必要がありますが, かといってこれらを連携させる方法は TypeScript には今のところありません. async/await は言語組み込みの機能なのでなんとかなっているのですね.

ここでは Either モナドの例を紹介しましたが, 他の様々なモナド (あるいは類似の概念) についても同様のことが言えます.

ということでジェネレータを使った方法は, TypeScript ではいまいち使いづらいものとなっています.

解決

ここまでをまとめると「コールバック地獄の解決と TypeScript による型付けの両立」が課題でした. これからそれをなんとかして解決する方法を考えます.

分析

まずはジェネレータを使った方法がなぜコールバック地獄を解決するのに役に立つのか, また型付けががなぜうまくいかないのかを分析してみましょう.

まずジェネレータの大きな特徴として, yield 式を使って処理を中断できる / .next() を呼び出すことで中断した箇所から再開できる, ということがあります. コールバック地獄を解決するのに役に立つのはこの点で, 要するに任意の地点での "継続" を取り出すことができるため, 継続渡しスタイルで手でコールバックを書く必要がなくなります.

続いて型付けについて考えてみましょう. たとえば t: Either<L, R> という変数があったとき, ここまでのようなコールバック地獄を解決している文脈では, ジェネレータ内の yield t という式の型は R となってほしいところです. 一方で TypeScript の機能としては, yield 式に対しては Generator<T, TRetrun, TNext> の TNext を指定することで特定の型とすることはできるものの, Either<L, R> に対しては R といったように, yield された値と yield 式の型の関係を指定する方法はありません.

function* myGenerator(): Generator<Either<Error, unknown>, void, number> {
  // たとえば
  //   t: Either<Error, number>
  //   u: Either<Error, string>
  // として
  const x = yield t; // x: number / .next() には number 型の値のみ渡すことができる
  const y = yield u; // y: number (?) / .next() には number 型の値しか渡すことが出来ない
  doSomething(x, y);
}

ではどのような方法であれば型の関係を指定することができるかというと, おそらく唯一の方法は以下のように関数を使うことでしょう.

// yield_: <L, R>(m: Either<L, R>) => R
const x = yield_(t); // x: number
const y = yield_(u); // y: string

しかしながらこの yield_ のような関数の内部では, ジェネレータの yield 式を使って処理を中断することは出来ません. 関数の内部からその外側の処理を中断する方法として, 我々に残されているのは throw のみです.

ということで throw で処理を中断するほかありませんが, 今度は中断した地点から処理を再開する方法がありません. 詰みました.

Algebraic Effects

ここで思い当たるのが Algebraic Effects です. これは直感的には「中断した地点から再開できる例外」とも説明される概念・言語機能で, 計算を行う上で発生する様々な効果 (副作用, 失敗, 非同期処理待ち, etc.) を扱うための一貫した方法を提供します. ここでは詳しくは説明しませんので, 以下の記事や論文などを参照してください.

もしこれが TypeScript に組み込まれていれば問題は解決 (というかこのような議論をするまでもない) というところなのですが, 現実にはそのようなものは (まだ) ありません.

解決方針

さて未来の (?) 言語機能の話は一旦置いておいて, どうしたら throw で中断した地点から処理を再開できるかを考えましょう. とはいえもちろん真の意味での再開は不可能なので, なんらかの妥協をすることになります.

ここで思いつくおそらく最善の (かつ最悪っぽい) アイデアは, 処理を再開するのではなく, 最初からやりなおすというものです. もし関数が純粋で副作用がなければ, 何度呼び出しても結果は変わらないはずなので, パフォーマンス上の懸念を除けば問題はありません.

具体的には以下のような記述を可能にします.

function myProc(yield_: <T>(e: Either<Error, T>) => T): void {
  const x = yield_(either(t));
  const y = yield_(either(u));
  doSomething(x, y); // TODO: 副作用どうする?
}

runProc(myProc);

runProc は受け取った関数を yield_ とともに呼び出しつつ, try/catch を使って throw されたものをハンドリングします. yield_ は最初に呼び出されたときは throw して処理を中断し, runProc はそれを見て, Left ならば処理を終了, Right ならば内部に持っている値のリストを更新します. その後再度関数を呼び出し, 二回目に呼び出された yield_ は値のリストに格納された値をそのまま返す, ..., ということを繰り返すことで, 最終的な結果が得られる, という仕組みです.

問題は関数が純粋でなく, 副作用があるような場合です. この場合は処理を中断した地点から再開することと最初からやり直すことが同じとは言えなくなるため, 例えば yield_ に関数を渡せるようにして, 繰り返し実行する中でその関数は一度だけ呼び出すようにする, といった対処が必要です.

ここで再度 Algebraic Effects を思い出しましょう. もし Either のような失敗するかも知れない処理を Algebraic Effects で扱うのであれば, 「失敗」という効果で表現することになるでしょう. そして IO 操作のような副作用もまた効果の一つとして扱うことが可能です.

つまり何が言いたいかというと, Either に特化した処理という形で記述するのではなく, Algebraic Effects のように一般の効果を扱う仕組みを作ることで, 副作用に対して上記のような場当たり的な対処をするのではなく, 全てに対して一貫した扱いが可能になるはず, ということです. さらにおまけとして他の様々な効果についても同様に扱うことができるようになります.

ライブラリ作ったよ

というわけで上記の方法で Algebraic Effects (たぶん) を実現するライブラリを作りました. とはいえ効果を発生させるたびに throw していたり, 処理が完了するまでに関数を何度も呼び出すなど, パフォーマンス的にはあまり期待できないため, 実用することはおすすめしません.

github.com

これを使うと, 失敗するかも知れない関数は以下のように書けます.

import { Action, raise } from "@susisu/effects";
 
const parse = (str: string): Action<"exn/raise", number> => perform => {
  const num = parseFloat(str);
  if (Number.isNaN(num)) {
    return perform(raise(new Error(`failed to parse: ${str}`)));
  }
  return num;
};

const divide = (x: number, y: number): Action<"exn/raise", number> => perform => {
  if (y === 0) {
    return perform(raise(new Error("division by zero")));
  }
  return x / y;
};

Action<K, T> は K という効果を発生させて T 型を返す値 (アクション) で, 実体は perform を受け取る関数です. perform は効果を引数にとり, 初回は throw して処理を中断し, 二回目以降は結果の値をそのまま返します (この例では二回呼び出されることはありませんが).

これらを組み合わせた処理に対しては, 以下のように runExn を使って実行することで最終的な結果を得ることができます. ここでアクションに対して perform(action) は action(perform) のエイリアスです. また副作用は compute という効果で表現します.

import { runExn, compute } from "@susisu/effects";

// r1 = { isErr: false, val: 21 }
const r1 = runExn(perform => {
  const x = perform(parse("42"));
  const y = perform(parse("2"));
  const z = perform(divide(x, y));
  perform(compute(() => {
    console.log(`${x} / ${y} = ${z}`); // -> 42 / 2 = 21
  }));
  return z;
});

// r2 = { isErr: true, err: Error("division by zero") }
const r2 = runExn(perform => {
  const x = perform(parse("42"));
  const y = perform(parse("0"));
  const z = perform(divide(x, y));
  return z;
});

その他の効果を使った例もリポジトリ内の examples/ ディレクトリにあります. 一部を抜粋すると, 例えば async/await を使わずに Promise を待つこともできます.

import { runAsync, waitFor } from "@susisu/effects";

const r = runAsync(perform => {
  const x = perform(waitFor(Promise.resolve(6)));
  const y = perform(waitFor(Promise.resolve(7)));
  return `The answer is ${x * y}.`;
});

r.then(res => {
  console.log(res); // "The answer is 42."
});

他にも処理を分岐させたりとかもできます. このようなことはジェネレータでは継続が一度しか呼び出せないため不可能でした.

import { runCtrl, split } from "@susisu/effects";

const r = runCtrl(perform => {
  const x = perform(split([1, 2]));
  const y = perform(split([1, 3]));
  return x * y;
});
console.log(r); // [1, 3, 2, 6]

ユーザーが独自に効果を定義することもできます. これは interface Effect<A> を拡張することで行います.

type S = number;

declare module "@susisu/effects" {
  interface Effect<A> {
    "my:state/get": Readonly<{ t: (x: S) => A }>;
    "my:state/put": Readonly<{ val: S; t: (x: undefined) => A }>;
  }
}

なぜ単なる型定義ではなく interface の拡張になっているかというと, ユーザー定義の効果を扱うためには, 効果を発生させる値の型を高カインド型 (効果だけに) で表現する必要があり, そのために fp-ts でも使われているような, interface の定義が "開かれている" ことを使った擬似的な高カインド型の再現をしているためです. 余談ですが上の定義の t は前回の記事で紹介した GADT っぽいのです (このために考えていました).