エフェクトとジェネレーターと

TypeScript プログラミング

2 年前に作って放置していたライブラリを最近ちょっと整理したのでその話.

エフェクト

プログラム中に登場する関数のことを考えてみましょう. 関数は引数を与えるとなんらかの計算を行い, 戻り値を返してくれます.

もし関数が純粋な (数学的な意味での) 関数であれば, 関数の入出力は引数と戻り値だけです. つまり, 引数以外の入力 (例えば時刻) によって出力が変わることもなければ, 戻り値以外の出力 (例えば光や音) が得られることもありません.

一方で実用的な価値のあるプログラムというのは時刻に応じて光や音を発生させるようなものであり, これらは純粋な関数だけを組み合わせていては作ることができません. ここで登場する純粋でない関数は, 計算の過程でなんらかのエフェクトを発生させて, 引数と戻り値以外の入出力 (副作用) を行います.

エフェクトの明示と副作用の分離

関数が発生させるエフェクトについては, 言語やエフェクトの種類にも依りますが, 必ずしも明示的には取り扱われません. 例えば TypeScript において Date.now() で現在時刻を取得したり, console.log() でコンソールへの表示を行っても, これらが関数のシグネチャ (型) を変えたりはしませんし, 呼び出し元からエフェクトの発生 (とその結果生じる副作用) に関与することもできません.

エフェクトの発生が暗黙的で外側から関与できないとなると, 関数がどういった副作用を発生させ得るのかわかりづらくなってしまったり, テストなど異なる環境で実行する際に副作用による不都合が生じたりします. こういった問題を回避するためには, 以前の記事でも書いたような, プログラムをできるだけ純粋な関数として記述して, エフェクトは周辺的な部分に追い出すというのが有効な手段です.

逆にこれらの課題は, エフェクトの発生を明示的にして, 関数の外側からでも関与できるようにしてしまうことでも解決できるはずです. いわゆる algebraic effects などです. このためのライブラリはもっと以前にも作っていて, ただあまりにも実行コストが高い実装になっていたのを, (一般性を犠牲にしつつ) ジェネレーターを使って作り直したのがこいつです.

github.com

試しに現在時刻を取得してコンソールへの出力を行うプログラムを書いてみましょう.

まずはエフェクトを定義します (このあたりはボイラープレート).

import type { Effectful } from "@susisu/effectful";
import { perform } from "@susisu/effectful";

// interface を拡張してエフェクトを定義する
declare module "@susisu/effectful" {
  interface EffectDef<A> {
    "time/get": {
      // A = Date の場合に制限する & 型を良い感じに変換する.
      // 詳しくは https://susisu.hatenablog.com/entry/2020/05/03/020854
      ev: (x: Date) => A;
    };
    "console/log": {
      message: string;
      ev: (x: void) => A;
    };
  }
}

function getTime(): Effectful<"time/get", Date> {
  return perform({ id: "time/get", data: { ev: (x) => x } });
}

function consoleLog(message: string): Effectful<"console/log", void> {
  return perform({ id: "console/log", data: { message, ev: (x) => x } });
}

続いてこれらのエフェクトを発生させる適当なプログラムを書きます. ジェネレータ関数として記述していて, エフェクトは yield* で発生させます.

function* main(): Effectful<"time/get" | "console/log", void> {
  const now = yield* getTime();
  yield* consoleLog(`現在時刻は ${now.toISOString()} です`);
}

ここまでで, まずプログラムが発生させるエフェクトを型で明示することができました. また発生させたエフェクトが具体的にどういった作用を起こすのかについてはまだ記述しておらず, プログラム本体と分離することができています.

プログラムを実行するためには, 発生するエフェクトに対するハンドラーを与えて, エフェクトが起こす作用を具体化してやる必要があります.

例えば普通に time/get が発生したら現在時刻を new Date() で取得し, console/log が発生したらメッセージをコンソールに出力するのであれば, 以下のようにハンドラーを記述して実行できます.

import { run } from "@susisu/effectful";

function runApp<T>(comp: Effectful<"time/get" | "console/log", T>): T {
  return run(comp, (x) => x, {
    "time/get": (eff, resume) => {
      return resume(eff.data.ev(new Date()));
    },
    "console/log": (eff, resume) => {
      console.log(eff.data.message);
      return resume(eff.data.ev(undefined));
    },
  });
}

runApp(main());
// => 現在時刻は 2024-06-15T11:16:37.104Z です

あるいはテストでは時刻を固定して, メッセージの出力も検査のために指定した関数を呼び出すようにしたければ, 以下のようにします.

function runTest<T>(
  comp: Effectful<"time/get" | "console/log", T>,
  now: Date,
  log: (message: string) => void,
): T {
  return run(comp, (x) => x, {
    "time/get": (eff, resume) => {
      return resume(eff.data.ev(now));
    },
    "console/log": (eff, resume) => {
      log(eff.data.message);
      return resume(eff.data.ev(undefined));
    },
  });
}

import { vi, describe, it, expect } from "vitest";

describe("main", () => {
  it("現在時刻をコンソールに出力する", () => {
    const log = vi.fn(() => {});
    runTest(main(), new Date("2024-06-06T12:34:56Z"), log);
    expect(log).toHaveBeenCalledWith("現在時刻は 2024-06-06T12:34:56Z です");
  });
});

main 関数は通常であればテストしづらいような副作用を持っていますが, エフェクトの発生と副作用が分離できていることで, main 自体を純粋な関数にするといった実装の変更をすることなくテストすることができました.

使いどころ

TypeScript においては, 現状使いどころはあまり多くないのではないかな〜というのが正直なところ.

例えば上記の例ではテストで挙動を差し替えるために副作用を分離していますが, テストで現在時刻の取得やコンソールの出力を差し替える方法は他にもあります. 一般的なシチュエーションであれば大抵はすでに何らかの解決策が用意されているもので, あえてこの方法を使いたいというケースはあまり多くなさそうです. 実際そんなに困ったことがない.

エフェクトの明示についても, どちらかといえばエフェクトを発生させない関数の方が取り回しやすく好ましいはずで, エフェクトを発生させるようなレイヤーはある程度制限されますし, そういったレイヤーにある関数がエフェクトを発生させることは明示的でなくても十分に推測できそうなものです.

良く言えば衛生的, 悪く言えばリスクに対してコストが過剰で潔癖症にもなりかねないといった感じ. この仕組みの上にさらにフレームワークを構築することで利用するコストを下げたり, もっと本質的に (テスト以外にも) 実行方法の差し替えが必要とされたりするのであれば便利に使えるかもしれません.

なんか良いユースケースあったら教えて!

おまけ: yield*

なぜエフェクトを発生させるのに yield ではなく, わざわざ yield* を使うのか.

実は yield を使うと型がまともにつけられません. ジェネレーターの型は Generator<T, TReturn, TNext> という形なのですが, yield の型はその yield が書かれている外側のジェネレーターの TNext です. つまり yield を複数回使っても常に同じ TNext ということになるのですが, エフェクトを発生させた結果の型は本来それぞれ異なることを考えると, これでは不便です.

function f(): Generator<..., void, number | string> {
  const x = yield getNumber();
  // x: number | string
  const y = yield getString();
  // y: number | string
  // Komaru!
}

対して yield* の型は, yield* が書かれている外側のジェネレーターではなく, yield* に与えているジェネレーターの TReturn によって決まります. これによってエフェクトの発生ごとに異なる型がつけられるので安心です.

function f(): Generator<..., void, ...> {
  const x = yield* getNumber();
  // getNumber(): Generator<..., number, ...>
  // x: number
  const y = yield* getString();
  // getString(): Generator<..., string, ...>
  // y: string
  // Tasukaru!
}

型がちゃんとつく代わりに, yield* に与える値はジェネレーターである必要があります. これについては以下のように yield する値をジェネレーターに包むだけの単純なユーティリティ関数を作って解決しています.

export function* perform<Row extends EffectId, A>(eff: Effect<Row, A>): Effectful<Row, A> {
  return yield eff;
}

おまけ: 末尾呼び出し最適化

ライブラリの中でプログラムを実行する部分は末尾呼び出しの再帰関数になっているのですが, JavaScript において末尾呼び出しの除去は仕様には記載があるものの, JavaScriptCore くらいでしか実装されていません. そのため長期間実行されるようなプログラムではスタックオーバーフローしてしまう可能性があります.

と思ったんですが, そういえば最近は JavaScriptCore を使った JS ランタイムが気軽に手に入る世の中になっていました. Bun のことです. これで安心ですね (?)

ちなみに非同期処理が含まれて Promise が挟まる場合は良い感じに trampoline されるので V8 とかでもなんとかなると思います.

おまけ: operational monad, extensible effects との関係

TypeScript の記法で書くとめちゃくちゃになるので Haskell っぽい記法で書きます.

まず Effectful r a は単にジェネレーター Generator (Effect r Any) a Any のエイリアスです. Any が混ざってるのは一旦気にしない.

Effectful r a
= Generator (Effect r Any) a Any

ジェネレーター Generator (Effect r Any) a Any の実行を進める (next を呼び出す) と,

  • 実行が完了したら a を返す
  • 実行が完了しないなら Effect r Any を返して, 自身を Any -> Generator (Effect r Any) a Any に変化させる

のいずれかが起こります. ここで,

  • 「自身を変化させる」という副作用をあくまで戻り値の一部だと思うことにする
  • Effect r Any の Any と, Any -> Generator (Effect r Any) a Any の引数の Any が一致するような規約を持たせている
  • ジェネレーターの実行を進めた結果はジェネレーターから無条件で取り出せるので, これらを同一視する

とすると,

Effectful r a
= Generator (Effect r Any) a Any
~= Either a (exists b. (Effect r b, b -> Generator (Effect r Any) a Any))
= Either a (exists b. (Effect r b, b -> Effectful r a))

のように, Effectful r a は Either a (exists b. (Effect r b, b -> Effectful r a)) と同じようなものと見なせます (ここでの ~= は必ずしも厳密ではなく「大体同じ」くらいの意味で使っています).

ここで Coyoneda と Free をベランダから取ってきます.

data Coyoneda f a where
  Coyoneda :: (b -> a) -> f b -> Coyoneda f a

data Free f a where
  Pure :: a -> Free f a
  Free :: f (Free f a) -> Free f a

これらを使うと,

Effectful r a
~= Either a (exists b. (Effect r b, b -> Effectful r a))
~= Either a (Coyoneda (Effect r) (Effectful r a))
~= Free (Coyoneda (Effect r)) a

のようにして, Effectful r a は結局 Free (Coyoneda (Effect r)) a と同じようなものであると言えます.

この最終的な Free (Coyoneda f) a という形は freer あるいは operational monad などと呼ばれるもので, f で与えられる命令を適当に解釈することで実行可能なプログラムを表すのに使われます. そしてこの f について複数のものをユニオンなどで後から合成 (拡張) 可能にしたものが extensible effects と呼ばれているようです.

つまるところ Effectful r a はこの operational monad の f が Effect r になったのと似たようなもので, r で与えられる計算エフェクトを適当にハンドリングすると実行可能なプログラムであり, r はユニオン型になっていて拡張が可能です. この対応関係を知っていれば他の言語や実装での議論を翻訳して持ち込みやすくなりそうですね.