SICP3.5 Stream on PHP

demo.php

<?php
require 'stream.php';

/** SICP3.5.2 無限ストリーム */
function integers_start_from($n)
{
    return cons_stream($n, function() use ($n) {return integers_start_from($n + 1);});
}
$integers = integers_start_from(1);
echo "integers\n";
display_line($integers, 20);

$squares = stream_map(function($n) {return $n*$n;}, $integers);
echo "integers^2:\n";
display_line($squares, 20);



function divisible($x, $y)
{
    return 0 == $x % $y;
}

$no_sevens = stream_filter(function($n) {return !divisible($n,7);}, $integers);
echo "no_sevens\n";
display_line($no_sevens, 20);


/** SICP3.5.2 エラトステネスの篩 */
function sieve($s)
{
    return cons_stream(
        stream_car($s),
        function() use($s) {
            return sieve(
                stream_filter(
                    function($x) use($s) {
                        return !divisible($x, stream_car($s));
                    },
                    stream_cdr($s)
                )
            );
        }
    );
}

// 素数列の無限ストリーム
$primes = sieve(integers_start_from(2));
echo "primes:\n";
display_line($primes, 20);



$s = stream_iterate(-10, function($v) {return $v + 1;});
echo "iterate\n";
display_line($s, 40);


echo "take\n";
display_line(stream_take($s, 10), 20);

echo "sqrt 2\n";
$root2 = stream_iterate(2.0, function($v) {return $v - (($v*$v - 2)/(2*$v));});
display_line($root2, 20);


// 自己参照
//$ones = cons_stream(1, function() {global $ones; return $ones;});
//display_line($ones);


function ones()
{
    return cons_stream(
        1,
        function() {
            return ones();
        }
    );
}
$ones = ones();
echo "ones\n";
display_line($ones,20);

echo "stream_merge\n";
$oneUp = stream_merge(function($v1, $v2) {return $v1 + $v2;}, $integers, $ones);
display_line($oneUp,20);

// 整数列の作り方その２
function generate_integers($ones)
{
    return stream_merge(
        function($v1, $v2) {return $v1 + $v2;},
        $ones,
        cons_stream(
            0,
            function() use($ones) {
                return generate_integers($ones);
            }
        )
    );
}

$integers2 = generate_integers($ones);
echo "integers2\n";
display_line($integers2, 20);


// 順列
function perm($a, $b, $c)
{
    $rotate = function($v) use($a, $b, $c) {
        return $v == $a ? $b :
              ($v == $b ? $c : $a);
    };
    $s1 = stream_iterate($a, $rotate);
    $s2 = stream_iterate($b, $rotate);
    $s3 = stream_iterate($c, $rotate);
    return perm_rec($s1, $s2, $s3);
}

function perm_rec($s1, $s2, $s3)
{
    $v1 = stream_car($s1);
    $v2 = stream_car($s2);
    $v3 = stream_car($s3);
    return cons_stream(
        "[$v1, $v2, $v3]",
        function() use($s1, $s2, $s3) {
            return perm_rec(
                stream_cdr($s1),
                stream_cdr($s3),
                stream_cdr($s2)
            );
        }
    );
}

echo "permutation\n";
display_line(perm('a', 'b', 'c'), 20);

stream.php

<?php
/**
 * SICP3.5 Stream on PHP
 * http://sicp.iijlab.net/fulltext/x350.html
 */

function delay($fn)
{
    $already_run = false;
    $result = null;
    return function() use($fn, $already_run, $result) {
        // メモ化しないと遅い
        if (!$already_run) {
            $result = force($fn);
            $already_run = true;
        }
        return $result;
    };
}

function force($fn)
{
    if ($fn instanceOf Closure)
        return call_user_func($fn);
    else
        return $fn;
}


function cons_stream($a, $b=null)
{
    if ($b == null)
        return array($a, null);
    else
        return array($a, delay($b));
}

function stream_car($s)
{
    return $s[0];
}

function stream_cdr($s)
{
    if ($s[1] == null)
        return null;
    else
        return force($s[1]);
}

function stream_ref($s, $n)
{
    if ($n==0)
        return stream_car($s);
    else
        return stream_ref(stream_cdr($s), $n-1);
}

function is_stream_null($s)
{
    return $s == null;
}

function stream_map($fn, $s)
{
    if (is_stream_null($s))
        return null;
    else
        return cons_stream(call_user_func($fn, stream_car($s)),
                           function() use($fn,$s) {
                               return stream_map($fn, stream_cdr($s));
                           });
}

function stream_filter($pred, $s)
{
    if (is_stream_null($s))
        return null;
    else if (call_user_func($pred, stream_car($s)))
        return cons_stream(stream_car($s),
                           function() use($pred, $s) {
                               return stream_filter($pred, stream_cdr($s));
                           }
        );
    else
        return stream_filter($pred, stream_cdr($s));
}

function stream_foreach($fn, $s, $limit=100)
{
    $s = force($s);
    if (is_stream_null($s) || $limit == 0)
        return;
    else {
        call_user_func($fn, stream_car($s));
        stream_foreach($fn, stream_cdr($s), $limit - 1);
    }
}

function stream_take($s, $n)
{
    if (is_stream_null($s) || $n<=0)
        return null;
    return cons_stream(stream_car($s),
                       function() use($s,$n) {
                           return stream_take(stream_cdr($s), $n - 1);
                       });
}


// clojureのiterate
function stream_iterate($init, $fn)
{
    $val = call_user_func($fn, $init);
    return cons_stream($init,
                       function() use($val,$fn) {
                           return stream_iterate($val, $fn);
                       });
}

function stream_merge($fn, $s1, $s2)
{
    return cons_stream(
        call_user_func($fn, stream_car($s1), stream_car($s2)),
        function() use($fn, $s1, $s2) {
            return stream_merge($fn, stream_cdr($s1), stream_cdr($s2));
        }
    );
}



function display_line($s, $limit = 20)
{
    stream_foreach(function($n) {echo $n." ";}, $s, $limit);
    echo "\n\n";
}