Zenn
🎏

Streamをつくる

2021/05/29に公開
1件
TypeScript
#
関数型プログラミング
#
コンピューターサイエンス
tech

本記事で扱う内容は主に以下のような概念です。

  • stream
  • thunk
  • lazy evaluation（遅延評価）

本記事は主に以下のような方を読者として想定しています。

  • 関数型プログラミングに少し触れたことがあり再帰関数や高階関数を知っている程度の人で「そういう言葉・概念があるんだなぁ。あとでちゃんとした文献で調べよう！」という方
  • TypeScriptのコードが読めるという方（説明にはTypeScriptを用います。）

余談はここまでにして、本題に移りましょう。

Streamとは

streamとは「無限に続く一連の値」のことです。
例えば自然数の一連の値（1, 2, 3, ...）などはstreamと言えます。

このような値の集まりをコード上で表現するにはどうすればよいのでしょうか？
もちろん無限に値を書いていくわけにはいきません。
また、再帰を用いて値を生成すればよいとも思われるかもしれませんが、愚直に書いた場合、評価の処理が無限に続くことになることがわかるかと思います。（本記事「streamをつくる」の項に愚直な実装のコードの説明があります。）

本記事では、一見不可能に思える「無限に続く一連の値」（stream）をコードで表現する方法を述べていきます。

式の評価のタイミング

streamをつくるにあたって理解しておかなければならないポイントがあります。
それは「式が評価されるタイミング」です。この「タイミング」は（おそらく）プログラミング言語によって異なるものですが、ほとんどのプログラミング言語では以下のようなタイミングで式が評価されるように実装されているかと思います。

  1. 関数の引数に与えられた式は関数が呼び出される前に評価される。
  2. 関数本体に記述された式は関数が呼び出された後に評価される。

コードで例を示します。まず、次のような関数fを考えます。

const f = (n: number) => n + 1;

例えば関数fをf(1 + 1)のように呼び出すと、

  1. まず1 + 1が評価されます。fには2が渡されます。関数本体の式は2 + 1となります。
  2. 次に関数本体の式2 + 1が評価され、関数fの返り値として3が返却されます。

特に「関数本体にある式は関数が呼び出されてから評価される」というのがstreamの実装に関して重要なポイントとなります。

lazy evaluation（遅延評価）とthunk

前項に関連して次のような関数を考えます。

const myIf = <T extends any>(x: boolean, y: T, z: T): T => x ? y : z;

さて、この関数myIfは三項演算子の代わりとして安易に利用してよいものでしょうか？

答えはNoです。

理由は「式が評価されるタイミングの違い」にあります。

前項で説明したように関数の引数に与えれらた式は関数呼び出し前に評価されます。
つまり、上記のコードにおいては関数myIfの引数yとzに渡される両方の式を評価したあとで関数myIfが呼び出されることになります。

一方、三項演算子の場合はどうでしょうか？
x ? y : zとしたとき、yはxがtrueのとき、zはxがfalseのときのみそれぞれ評価されます。つまり、二つの式のうちどちらか片方は評価されません。

この違いは特に、式の処理コストを考えたとき重要となります。
myIfの引数yとz両方にコストの大きな処理を必要とする式を渡してしまうと、本来評価する必要のない方の式まで評価されることになり、大きな無駄が生じてしまいます。

一方で三項演算子のxとy式は実際にその式の値が必要になるタイミングまで式の評価が行われません。そのためxかyどちらかの式を評価する処理を削減できることになります。

参考までにmyIfと三項演算子の評価の順を追っていくと以下のようになります。

myIf(true, 1 + 1, 2 + 3);
myIf(true, 2, 5); // 関数の引数は評価された結果が渡される
true ? 2 : 5;
2;

true ? 1 + 1 : 2 + 3;
1 + 1; // 1 + 1 だけが評価される
2;

さて、ここで次の問題に移りましょう。

  • 「三項演算子と式の評価のタイミングが同じ挙動になる関数をつくる」にはどうすればよいのでしょうか？

より一般に

  • 「実際に式の値が必要になるまで式の評価を遅らせる」にはどうすればよいのでしょうか？

この問題を解決する中で用いるテクニックを理解することは、streamの実装を理解することに大きな役割を果たします。

まず、myIfを三項演算子の挙動と同じになるよう変更を加えたdelayedMyIfのコードをご覧ください。

type Thunk<T> = () => T; 
const delayedMyIf = <T extends any>(x: boolean, y: Thunk<T>, z: Thunk<T>) => x ? y() : z();

delayedMyIfが引数yと引数zにThunk型の関数をとるように変更したところがポイントです。

コードを順に説明していきます。

  • Thunk型は0引数の関数でT型を返す関数の型です。
  • delayedMyIfは引数yとzにおいて式の代わりにthunkを受け取ります。
  • delayedMyIfの本体ではy()、z()のように記述し、渡されたthunkを呼び出すようにします。

以上の変更により、delayedMyIfを呼び出したときの評価は次のように進行します。

delayedMyIf(true, () => 1 + 2, () => 3 + 9);
true ? (() =>  1 + 2)() : (() => 3 + 9)(); 
(() => 1 + 2)(); // 評価を遅らせたことにより3+9は評価されない。
1 + 2; // 1+2を関数の引数として渡した場合とは異なり、1+2はこのタイミングになるまで評価されない。
3;

以上のようにthunkを用いることにより式の評価を遅らせること（lazy evaluation：遅延評価）が可能になることがわかりました。

いよいよ次の項では本項で説明してきたテクニックを用い、streamを実装していきます。

Streamをつくる

本項では、自然数のstream（naturals）を2要素からなるタプルを用いて実装します。
まず初めに愚直に実装したstream(badNaturals)を示し、その後thunkを用いたstream(naturals)の実装を説明していきます。

早速、以下のBadNaturalsのコードを見ていきましょう。

type BadStream<T> = [T, BadStream<T>];
const badNaturals = (n: number): BadStream<number> => {
  return [n, badNaturals(n+1)];
}; 
badNaturals(1);

streamを生成する関数badNaturalsは単純な再帰関数として実装されています。
ではbadNaturals(1)のように呼び出すとどのようなことが起こるのでしょうか？

評価を順に追って行くと以下のようになります。

badNaturals(1)
[1, badNaturals(2)]
[1, [2, badNaturals(3)]]
[1, [2, [3, badNaturals(4)]]]
[1, [2, [3, [4, [badNaturals(5)]]]]]
// 以下無限に続くため省略

確かにbadNaturals(1)は自然数を無限に生成し、自然数のsteamをつくりだしています。
しかし、評価が一つ終わるごとに関数呼び出し（再帰呼び出し）が返ってくるため、badNaturals(1)の評価は終わりません。実際にbadNaturals(1)を実行すれば再帰スタックの上限に達しエラーとなるでしょう。

それでは、どのようにすれば評価が無限に続くことなく停止する自然数のstreamを実装することができるのでしょうか？

この実装を実現するために利用するテクニックがthunkの導入です。

まず、badNaturalsの問題点は関数の返り値として「関数呼び出し（badNaturals(n+1)）」を含んでいるがゆえに処理が無限に続くプログラムになっているという点にあります。

したがって、「次の自然数を生成する関数呼び出し(badNaturals(n+1))の評価」を遅延させるようにコードを変更すれば、処理は無限に続くことなく終了すると考えられます。

つまり、badNaturals(n+1)の評価をthunkによって遅延させれば良いということになります。

この考えのもと実装した自然数のstreamが以下のコードになります。
（以下のコードにおいてbadNaturals(n+1)はf(n+1)に当たります。）

type Thunk<T> = () => T; 
type Stream<T> = Thunk<[T, Stream<T>]>;
const naturals: Stream<number> = () => {
  const f = (n: number): [number, Stream<number>] => [n, () => f(n + 1)];
  return f(1);
};

最後にnaturals(1)がどのように評価されていくのかを追っていきましょう。

naturals(1)
() => [1, () => naturals(2)] // thunkが返ってくる

上に示した通り、thunkによって評価は() => [1, () => naturals(2)]で停止します。

以上により、一見不可能に思えた「自然数のstream」を実装することができました。

さいごに

本記事では自然数のstreamであるnaturalsを実装したところで説明を終えていますが、さらに次のようなことをおこなうとより理解が深まるかもしれません。

  • naturalsから1番目の値を取り出してみる。2番目の値を取り出してみる。
  • naturalsからn番目の値を取り出す関数を実装してみる。
  • naturals以外のstreamを実装してみる。
  • streamをつくる高階関数を実装してみる。その関数を用いてnaturalsを実装してみる。

以上で本記事は終わりです。
ここまでお読みくださりありがとうございました。
本記事が関数型プログラミングをより深く学ぶための足掛かりとなれば幸いです。

Discussion

akiaki

「Streamをつくる」の項を「単に実装を示す構成」から「愚直な実装を示しその実装を改善する構成」へと変更しました。より理解しやすくなっていると幸いです。