2022-04-16

ラムダ計算と無限ラムダ多項式(15)

フィボナッチ数列の例

繰り返しの回数が有限のときに、(有限個の)変更しない変数で書けることや関数の再帰的定義を取り除くことができること(また変数や関数定義を取り除くことができること)を示すための例を考えます。

平方根の例は長いので、ここではフィボナッチ数列の例を考えます。フィボナッチ数列は以下のように定義されます(wikipedia:フィボナッチ数を参照)。

$F_0 = 0$
$F_1 = 1$
$F_{n+2} = F_n + F_{n+1} \ (n \ge 0)$

フィボナッチ数列の例(1)

C# のイテレーターを使って擬似的な無限の列を考えます。

            IEnumerable<int> fib()
            {
                int x = 0;
                int y = 1;
                yield return x;
                yield return y;
                for (; ; )
                {
                    int z = x + y;
                    yield return z;
                    x = y;
                    y = z;
                }
            }

最初の30項は以下のようになります。

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229

繰り返しの回数が8回以内として「for」を「展開」して取り除き、変数を変更しないようにすると以下のようになります。

            IEnumerable<int> fib()
            {
                int x_0 = 0;
                int y_0 = 1;
                yield return x_0;
                yield return y_0;
                int z_0 = x_0 + y_0;
                yield return z_0;
                int x_1 = y_0;
                int y_1 = z_0;
                int z_1 = x_1 + y_1;
                yield return z_1;
                int x_2 = y_1;
                int y_2 = z_1;
                int z_2 = x_2 + y_2;
                yield return z_2;
                int x_3 = y_2;
                int y_3 = z_2;
                int z_3 = x_3 + y_3;
                yield return z_3;
                int x_4 = y_3;
                int y_4 = z_3;
                int z_4 = x_4 + y_4;
                yield return z_4;
                int x_5 = y_4;
                int y_5 = z_4;
                int z_5 = x_5 + y_5;
                yield return z_5;
                int x_6 = y_5;
                int y_6 = z_5;
                int z_6 = x_6 + y_6;
                yield return z_6;
                int x_7 = y_6;
                int y_7 = z_6;
                int z_7 = x_7 + y_7;
                yield return z_7;
            }

結果は以下のようになります。

0, 1, 1, 2, 3, 5, 8, 13, 21, 34

フィボナッチ数列の例(2)

fib() の中で fib() を参照するようにします。2つの数の和を取らなければいけないのですが、「foreach (…)」の中では1つしか書くことができないので以下のようになります。

            IEnumerable<int> fib()
            {
                yield return 0;
                yield return 1;
                IEnumerator<int> fib_itr = fib().GetEnumerator();
                fib_itr.MoveNext();
                foreach (int n in fib())
                {
                    fib_itr.MoveNext();
                    yield return n + fib_itr.Current;
                }
            }

foreach をやめて for で書き直すと以下のようになります。

            IEnumerable<int> fib()
            {
                yield return 0;
                yield return 1;
                IEnumerator<int> fib_itr1 = fib().GetEnumerator();
                IEnumerator<int> fib_itr2 = fib().GetEnumerator();
                fib_itr2.MoveNext();
                for (; ; )
                {
                    fib_itr1.MoveNext();
                    fib_itr2.MoveNext();
                    yield return fib_itr1.Current + fib_itr2.Current;
                }
            }

for を展開することはできるのですが、fib_itr1.MoveNext()、fib_itr2.MoveNext() で fib_itr1、fib_itr2 が更新されるので、C# のイテレーターを直接使うと変数が変更されないようにはできません。

            IEnumerable<int> fib()
            {
                yield return 0;
                yield return 1;
                IEnumerator<int> fib_itr1 = fib().GetEnumerator();
                IEnumerator<int> fib_itr2 = fib().GetEnumerator();
                fib_itr2.MoveNext();
                fib_itr1.MoveNext();
                fib_itr2.MoveNext();
                yield return fib_itr1.Current + fib_itr2.Current;
                fib_itr1.MoveNext();
                fib_itr2.MoveNext();
                yield return fib_itr1.Current + fib_itr2.Current;
                fib_itr1.MoveNext();
                fib_itr2.MoveNext();
                yield return fib_itr1.Current + fib_itr2.Current;
                fib_itr1.MoveNext();
                fib_itr2.MoveNext();
                yield return fib_itr1.Current + fib_itr2.Current;
                fib_itr1.MoveNext();
                fib_itr2.MoveNext();
                yield return fib_itr1.Current + fib_itr2.Current;
                fib_itr1.MoveNext();
                fib_itr2.MoveNext();
                yield return fib_itr1.Current + fib_itr2.Current;
                fib_itr1.MoveNext();
                fib_itr2.MoveNext();
                yield return fib_itr1.Current + fib_itr2.Current;
                fib_itr1.MoveNext();
                fib_itr2.MoveNext();
                yield return fib_itr1.Current + fib_itr2.Current;
            }

フィボナッチ数列の例(3)

C# のイテレーターでは変数を変更しないようにはできなかったので、自作のイテレーターを作ります。

            IEnumerable<int> fib()
            {
                int x = 0;
                int y = 1;
                int next()
                {
                    int z = x + y;
                    x = y;
                    y = z;
                    return z;
                }
                yield return 0;
                yield return 1;
                for (; ; )
                {
                    yield return next();
                }
            }

この next を変数を変更しないように書き直します。

            IEnumerable<int> fib()
            {
                (int,int) next(int x, int y)
                {
                    int z = x + y;
                    return (y, z);
                }
                int x = 0;
                int y = 1;
                yield return 0;
                yield return 1;
                for (; ; )
                {
                    (x, y) = next(x, y);
                    yield return y;
                }
            }

そして for を展開すると変数を変更しないようにすることができます。

            IEnumerable<int> fib()
            {
                (int, int) next(int x, int y)
                {
                    int z = x + y;
                    return (y, z);
                }
                int x_0 = 0;
                int y_0 = 1;
                yield return 0;
                yield return 1;
                (int x_1, int y_1) = next(x_0, y_0);
                yield return y_1;
                (int x_2, int y_2) = next(x_1, y_1);
                yield return y_2;
                (int x_3, int y_3) = next(x_2, y_2);
                yield return y_3;
                (int x_4, int y_4) = next(x_3, y_3);
                yield return y_4;
                (int x_5, int y_5) = next(x_4, y_4);
                yield return y_5;
                (int x_6, int y_6) = next(x_5, y_5);
                yield return y_6;
                (int x_7, int y_7) = next(x_6, y_6);
                yield return y_7;
                (int x_8, int y_8) = next(x_7, y_7);
                yield return y_8;
            }

計算論計算可能性とラムダ計算 (コンピュータサイエンス大学講座)

フィボナッチ数列の例

フィボナッチ数列の例(1)

フィボナッチ数列の例(2)

フィボナッチ数列の例(3)

有限ラムダ多項式 Lisp

定数・変数

( 関数名 式 式 … 式 )

' 式

(lambda (変数名 変数名 … 変数名) 式 式 … 式)

setf 変数名 式

(defun 関数名 (変数名 変数名 … 変数名) 式 式 … 式)

(if 条件式 式1 式2)

平方根の例

サーバー側で計算し、一桁ずつ取得する例

サーバー側で計算し、イテレーターを使う例

ブラウザー側で計算し、(サーバー側の)データを更新する例

ブラウザー側で計算し、(サーバー側の)データを(ジェネレーターで)更新する例

有限ラムダ多項式によるクロージャーの定義

有限ラムダ多項式

クロージャーの定義

定数 の値

変数 の値

の値

let = in の値

subst = in の値

def ( ) = in の値

fun ( ) = の値

if then else の値

if then else の値

有限の場合から無限の場合へ

有限の場合のポインター除去

let = のとき

subst = のとき

クロージャーの定義

定数 の値

変数 の値

算術演算子、比較演算子を使った 、 という式の値

let = in の値

subst = in の値

def ( ) = in

fun ( ) =

if then else

ブロックの記法

変数の変更が不可能なクロージャーとポインターの調査

( 関数名式式 … 式 )

(lambda (変数名変数名 … 変数名) 式式 … 式)

setf 変数名式

(defun 関数名 (変数名変数名 … 変数名) 式式 … 式)

(if 条件式式1 式2)

定数 $a$ の値

変数 $v$ の値

$f(x_1, x_2, \cdots , x_n)$ の値

let $v$ = $x$ in $y$ の値

subst $v$ = $x$ in $y$ の値

def $f$ ( $v_1, v_2, \cdots , v_n$ ) = $x$ in $y$ の値

fun ( $v_1, v_2, \cdots , v_n$ ) = $x$ の値

if $x$ then $y$ else $z$ の値

if $f (v_1, v_2, \cdots , v_n) = x$ then $y$ else $z$ の値

let $v$ = $x$ のとき

subst $v$ = $x$ のとき

定数 $a$ の値

変数 $v$ の値

算術演算子、比較演算子を使った $x \triangle y$ 、 $\triangle x$ という式の値

let $v$ = $x$ in $y$ の値

subst $v$ = $x$ in $y$ の値

def $f$ ( $v_1, v_2, \cdots , v_n$ ) = $x$ in $y$

fun ( $v_1, v_2, \cdots , v_n$ ) = $x$

if $x$ then $y$ else $z$