PHP でイテレータを使って関数型プログラミングっぽい雰囲気を出す: 無限数列編

はじめに

この記事は PHP カンファレンス 2014 における私 @yuya_takeyama の発表 Good Parts of PHP and The UNIX Philosophy のネタ出しも兼ねて書かれています。
当日の発表には、この記事に関する内容が出てくるかもしれませんし、出てこないかもしれません。
興味のある方は是非当日の発表の場にお越しいただければと思います。 (参加登録)

今回実装したコードは以下の GitHub リポジトリに含まれています。
(今後の記事のネタバレ含む)

GitHub: yuya-takeyama/functional_programming_in_php

前回: range 編

前回のおさらい

前回は一般的なイテレータの説明、PHP におけるイテレータについて説明しました。

また、PHP 標準の range() 関数について、以下の問題点を挙げました。

• 呼び出し時に全ての要素を持った array を生成するため、要素数分のメモリを確保してしまう
• 無限数列を扱うことができない

これを解決するため、または Iterator インターフェイスの実装例として RangeIterator を用意し、array ではなくイテレータを返す range() 関数を実装しました。

メモリ使用量の改善については前回の記事で書いたので、今回は無限数列についてです。

無限数列とは

ここでは単に「無限に続く数列」程度のざっくりしたイメージで話を進めます。

例えば Haskell であれば以下のように表現することができます。

[1..]

これは 1 から始まり、無限に続く数列を表します。
何らかの処理において、数列を使うことはわかっているが、いくつまで用意すればいいかわからない・決まっていないときなどに使います。

配列による無限数列

PHP で無限数列を扱う方法について考えてみます。
数列と言えばやはり標準の range() 関数がありますが、結論から言うとこれは不可能です。

PHP には INF という定数があり、無限大を表す float 型の特別な定数です。

例えば、以下のようなループは無限ループとなります。

<?php
for ($i = 0; $i < INF; $i++) {
    echo $i, PHP_EOL;
}

これを使って range() 関数を呼び出してみましょう。

<?php
foreach (range(1, INF) as $n) {
    echo $n, PHP_EOL;
}

これを呼び出すと以下のような結果になります。

$ php inifinite_range_with_array.php
PHP Fatal error:  Allowed memory size of 134217728 bytes exhausted (tried to allocate 32 bytes) in /Users/yuya/src/github.com/yuya-takeyama/functional_programming_in_php/iterator/inifinite.php on line 2

Fatal error: Allowed memory size of 134217728 bytes exhausted (tried to allocate 32 bytes) in /Users/yuya/src/github.com/yuya-takeyama/functional_programming_in_php/iterator/inifinite.php on line 2

値をひとつも出力することなく強制終了してしまいました。

前回も書きましたが、range() はその場で数列全体を array として生成して、その値を返すようになっています。
そのため、無限数列を作ろうとすると配列が無限に拡大し、メモリを使いきったところで Fatal error となってしまいます。

イテレータによる無限数列

これは実は、前回実装した RangeIterator およびそれを用いたオレオレ range() 関数で既に実現できています。

<?php
require_once __DIR__ . '/Functional.php';
use Yuyat\Functional\WithIterator as F;

foreach (F\range(1, INF) as $n) {
    echo $n, PHP_EOL;
}

これを実行すると以下のようになります。
無限ループなので、途中で Ctrl + c などで強制終了する必要があります。

$ php inifinite_range_with_iterator.php
1
2
3
4
5
6
7
(省略)

強制終了するまで、無限に数値が出力され続けます。

array では作ることすらできなかった無限数列ですが、イテレータを使うことで簡単に実装することができました。
これは、RangeIterator が遅延評価 (Lazy evaluation) というテクニックを使うことで実現されています。

遅延評価 (Lazy evaluation) とは何か

ざっくり言うと「必要なときに必要な値を評価する」という感じでしょうか。
標準の range(1, 5) はその場で array として [1, 2, 3, 4, 5] を生成するのに対して、RangeIterator を利用した F¥range(1, 5) は「1 から 5 までの数列」という意味を持ったオブジェクトを生成するのみで、実際の数列は生成しません。
ループ処理の実行時に、初回は 1、その次は 2、そして 3 といった具合に、必要になったものからひとつずつ生成していきます。

逆に、標準の range() のようにその場で全ての値を生成するものは「正格評価 (Eager evaluation)」などと呼びます。

プログラミング言語によっては、言語の機能として遅延評価を持っているものもあります。
Scala や Scheme 等の関数型言語がそうで、Haskell はデフォルトの評価戦略が遅延評価になっています。

PHP は言語として遅延評価の機能を提供しているわけではありませんが、今回のように遅延評価を用いたイテレータを実装することができます。
一般的なオブジェクト指向言語であれば、処理系が提供する機能に関係なく、今回のように遅延評価を用いた無限数列は実装できるでしょう。

また、イテレータであること即ち遅延評価であるわけではない、という点に注意をしましょう。
今回実装した RangeIterator がたまたま遅延評価を用いていただけで、そうでないイテレータもあります。
PHP 標準の ArrayIterator などがそうです。

無限リストを用いた別の関数を実装する

ここからはもう少し複雑な関数を作ってみましょう。
「1 から任意の値までの数列の合計値」を計算する関数を使います。

手続き型っぽい実装だとこんな感じになるでしょう。

function sumTill($n) {
    $sum = 0;

    for ($i = 1; $i <= $n; $i++) {
        $sum += $i;
    }

    return $sum;
}

これはこれで問題のない実装です。
メモリの消費量も少ないです。

ですが、せっかくなので関数型っぽいアプローチで作ってみましょう。
関数型プログラミングの基本は、小さな関数を組み合わせることです。
そのパーツとなる関数をいくつか実装します。

なお、実装する関数のインターフェイスは、Haskell の標準ライブラリ Prelude を参考にします。

take($n, $iterator)

take() は $iterator から最初の $n 個の要素を返す関数です。
返す要素は、配列ではなくイテレータを返すものとします。

class TakeIterator extends IteratorIterator
{
    private $n;

    private $i;

    public function __construct(Traversable $iterator, $n)
    {
        $this->n = $n;

        parent::__construct($iterator);
    }

    public function rewind()
    {
        $this->i = 0;

        parent::rewind();
    }

    public function next()
    {
        parent::next();

        $this->i += 1;
    }

    public function valid()
    {
        return $this->i < $this->n;
    }
}

function take($n, $iterator) {
    return new TakeIterator($iterator, $n);
}

イテレータをラップして、$n 個の要素を返すイテレータを TakeIterator として実装しました。
そして、それをラップするヘルパーとして take() を実装しています。

ここで TakeIterator の実装は、PHP 標準の IteratorIterator を継承することで実装しています。
イテレータをラップしつつ、元の動きから変えたい部分だけオーバーライドするだけでよくなるので、記述が少し楽になります。

この関数の動作をテストするために、以下のようなユニットテストを用意します。
テスティングフレームワークには PHPUnit を使っています。

まずは、与えられたイテレータの要素が期待通りかをテストするアサーションメソッドを実装します。

    public function assertIterator($expected, Traversable $actualIterator)
    {
        $this->assertSame($expected, \iterator_to_array($actualIterator));
    }

イテレータとしての振る舞いをそのままテストするのは面倒なので、一旦 array に変換し、期待する要素も array として指定するようにしています。
イテレータから array への変換は、標準の iterator_to_array() 関数を使用しています。

次は、実際に take() 関数をテストするコードです。

    public function test_take()
    {
        $this->assertIterator([1, 2, 3, 4, 5], F\take(5, F\range(1, \INF)));
        $this->assertIterator([], F\take(0, F\range(1, \INF)));
    }

1 から始まる無限数列から最初の 5 要素を取り出すと [1, 2, 3, 4, 5] になる、というテストです。
また、0 要素を取り出したときは空のイテレータが返ることもテストしています。

foldl($fn, $initial, $iterator)

foldl() は take() に比べるとやや考え方が難しいかもしれません。
とはいえ、関数型言語にはよく用いる考え方なので、覚えておいたほうが良いでしょう。

これはイテレータを集約するのに使う関数です。
イテレータ中の最大値を返す関数や、全要素を合計した値を返す関数も、これを利用することで実装することができます。

先にテストコードを見ておくと、使い方がわかりやすいかもしれません。

    public function test_foldl()
    {
        $this->assertSame(55, F\foldl(function ($x, $y) { return $x + $y; }, 0, F\range(1, 10)));
    }

これは 1 から 10 までの数列をすべて足し合わせています。
初期値として 0 を指定しているので、0 + 1 + ... + 9 + 10 = 55 というような計算が行われています。

それではこの関数の実装を見てみましょう。

function foldl($fn, $initial, $iterator) {
    $a = $initial;

    foreach ($iterator as $value) {
        $b = $value;
        $a = $fn($a, $b);
    }

    return $a;
}

再帰を用いたより関数型っぽいアプローチで実装することもできますが、そのためには必要な関数が足りないので、ここでは妥協して手続き型っぽいアプローチを使ってみました。

関数を組み合わせて作る

それでは本題に戻って「1 から任意の値までの数列の合計値」を計算する関数を実装してみましょう。

function sumTill($n) {
    return F\foldl(function ($x, $y) { return $x + $y; }, 0, F\take($n, F\range(1, INF)));
}

元の手続き型の例と比べて、こちらの方が簡潔になったかどうか、は意見の別れるところでしょう。
少なくとも、関数型の考えに慣れない方には、直感的に動きを捉えることができないでしょう。

この関数は以下の流れで実行されます。

1. 1 から始まる無限数列を生成する
2. そこから始めの $n 個の要素を持つイテレータを生成する
3. それらの要素を全て足し合わせる

なお、この例は「無限数列を使用する」ということと「小さな関数を組み合わせる」ということを説明するために、やや冗長な実装になっています。
以下のように書き換えたほうが簡潔だと言えるでしょう。

function sumTill($n) {
    return F\foldl(function ($x, $y) { return $x + $y; }, 0, F\range(1, $n));
}

何故関数型のアプローチを用いるのか

今回は単純な例を用いたために、関数型のアプローチを用いるメリットがわかりづらかったかもしれません。
ですが、より複雑な現実のプログラムを実装する上では、以下のようなメリットがあります。

複雑な処理を副作用の無い式として表現できる

最初の手続き型の例では、関数内で foreach 文を用いていました。
sumTill() 関数の中では合計値 $sum とループカウンタの $i がなんども書き換えられます。

現在の実装であれば問題ないですが、これが用件に合わせて複雑化し、書き換えられる変数が増えたらどうなるでしょう。
プログラマはその状態をいちいち把握していないと、意図しない形で実装を壊してしまうかもしれません。

このような変数の書き換えは「副作用」であると言えます。
「副作用」はこれ以外にも、ファイルやネットワークへの書き出し・端末への出力等も含みます。

これに対して、関数型の実装には副作用がありません。
ひとつの式として値を返すだけになっています。

この例においては、手続き型の例でも、sumTill() 関数の実行には副作用がありません。
関数内で発生している副作用は、関数内のローカルスコープに閉じ込められており、これはこれで十分安全だと言えます。

関数型のプログラミングにおいては副作用をできる限り排し、関数の組み合わせとして表現することが重要です。
言語によっては、副作用のある実装と副作用のない実装が静的に区別され、副作用のある範囲だけそれに気をつければ良い、ということを言語処理系がサポートしてくれます。

PHP においてはそういった処理系レベルのサポートは無いものの、副作用を減らすことはプログラムの堅牢性に寄与するでしょう。

数列の生成も関数として置き換え可能にする

今回の例では単純な数列を用いたので、for 文での数列の生成でもあまり問題は無いように見えました。
ですが、これがより複雑な数列 (例えばフィボナッチ数列など) だったらどうでしょう。

for 文で行っている処理をモジュールとして切り出すのは難しいでしょう。
フィボナッチ数列を無限に生成する for 文があったとして、そこから最初の 5 要素を取り出す場合、for 文の終了条件自体を直接書き換える必要があるでしょう。

ですが、数列としてイテレータを使っていれば、それはモジュールとして他の関数と組み合わせることができます。
フィボナッチ数を無限に生成するイテレータがあれば、それに take() 関数を組み合わせるだけで最初の 5 要素を取り出すことができます。

無限数列のまとめ

• 配列としては作れない無限数列も、イテレータとしてなら簡単に作れる
• 無限数列の生成には遅延評価を用いる
• 関数型のアプローチでは副作用の無い小さな関数の組み合わせとして処理を表現する
• イテレータを使えば数列の生成もモジュールとして他の関数と組み合わせが容易にできる