エレファント・コンピューティング調査報告

極限に関する順序を論理プログラミングの手法を使って指定することを目指すブロクです。

ラムダ計算と無限ラムダ多項式

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

たらい回し関数の調査 たらい回し関数は変数を使わない例には使えそうにないですが、調査を継続します。「wikipedia:竹内関数」に書かれている高速化をやってみます。C# で書いた以下のプログラムについて考えます。 public static string Test() { int coun…

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

たらい回し関数の例 フィボナッチ数列の例ではクロージャーを変数を使わずに書く例としては単純すぎてわかりにくかったので、たらい回し関数が使えるかどうか調べてみます。まずたらい回し関数自体について調べてみます。たらい回し関数は以下のように定義さ…

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

フィボナッチ数列の例(4) クラスを使ったものを考えます。 private class FibClass { private int x = 0; private int y = 1; public int Next() { int z = x + y; x = y; y = z; return z; } } このクラスを使ったものは以下のようになります。 IEnumerable<int></int>…

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

フィボナッチ数列の例 繰り返しの回数が有限のときに、(有限個の)変更しない変数で書けることや関数の再帰的定義を取り除くことができること(また変数や関数定義を取り除くことができること)を示すための例を考えます。平方根の例は長いので、ここではフィボ…

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

有限ラムダ多項式 Lisp 「平方根の例」を移植するために Common Lisp のサブセットを目指した Lisp を作成します。これを「有限ラムダ多項式 Lisp」と呼ぶことにします。仕様は以下のようになります。 定数・変数 定数には数値、t (真を表す)、nil (偽を表す…

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

有限ラムダ多項式によるクロージャーの定義 有限ラムダ多項式 有限ラムダ多項式は以下のものから構成されます。 定数 変数 は演算子、 は有限ラムダ多項式 演算子 に対して演算子の項数 が決まっているとします。定数は項数 の演算子とします。 クロージャー…

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

有限の場合から無限の場合へ 有限の場合(任意の再帰的定義の関数の呼び出しの深さが有限の回数 以内の場合)、関数定義、無名関数、クロージャーを取り除くことができて、式の値は以前定義した「一般マグマの多項式」のような形にすることができます。これの…

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

有限の場合のポインター除去 再帰的定義の関数が有限の回数で終わるとき、再帰的定義がない形に書き直すことができます。C# で階乗を求める関数で考えてみます。 private int fac(int n) { if (n == 1) { return 1; } else { return n * fac(n - 1); } } 関…

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

クロージャーの定義 wikipedia:クロージャ などを見ると(できることは同じようですが)クロージャーの定義にはいろいろあるようです。ここでも定義しておいた方が良いと思われるので、ここで使うものを定義しておきます。式は以下のものから構成されます。 定…

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

Calc クラスの IterateServer です。 public static Func<string> IterateServer = () => new ExpBlock { Exp.Define("take", new NameList{"count", "gen"}, Exp.If( Exp.Func("==", Exp.Name("count"), Exp.Number(0)), Exp.Nil(), new ExpBlock { Exp.Let(new Nam</string>…

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

Calc クラスの IterateGenerator と RepeatServer です。 public static Func<string> IterateGenerator = () => new ExpBlock { Exp.Define("take", new NameList{"count", "gen"}, Exp.If( Exp.Func("==", Exp.Name("count"), Exp.Number(0)), Exp.Nil(), new ExpB</string>…

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

Calc クラスの RepeatGenerator と、それに必要な関数の文字列版です。 private static Func<Exp, Exp> GetNextDecimalDigitAndNumbers = (Exp numbers) => Exp.From("{" + "let (number, square_difference, scale) = numbers;" + "def maxdd (dd) =" + "if dd >= 0 t</exp,>…

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

Calc クラスの RepeatGenerator と、それに必要な関数を書き直しました。 private static Func<Exp, Exp> GetNextDecimalDigitAndNumbers = (Exp numbers) => { Exp n0 = Exp.Number(0); Exp n1 = Exp.Number(1); Exp n2 = Exp.Number(2); Exp n9 = Exp.Number(9); Exp</exp,>…

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

Calc クラスの RepeatGenerator をラムダ式のようなもので書き直したものの動作するバージョンです。 public static Func<string> RepeatGenerator = () => new ExpBlock { Exp.Let("generator", Exp.From("GenerateDecimal()")), Exp.Define("GetNextDecimalDigit",</string>…

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

C# で以下のような式を書くことができるようにします。 Exp.Number ( 数値 ) 数値を表します。「数値」は整数、文字列、または BigNum です。 Exp.Bool ( 真理値 ) 真理値を表します。 Exp.String ( 文字列 ) 文字列を表します。 Exp.Name ( 文字列 ) 変数名…

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

以下は Calc クラスの RepeatGenerator をラムダ式のようなもので書き直したもののイメージです。まだ動作するものではありません。C# で書いてもエラーにはならない形式になっています。単純な式のときは文字列で書けるようになっています。 public static …

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

LISP と LOGO の本がいくつか見つかりましたが、LISP の本は古いのでクロージャーが使えるのかどうかよくわかりません。クロージャーの変数を変更できないようにしたらどうなるかを調べることが目的なので、この意味では LOGO を使って調べた方が良いかもし…

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

「関数プログラミングと無限論理多項式」でLisp の簡単な処理系を作ってクロージャーの調査をしようとしたのですが、Lisp で動作確認をするのはたいへんそうなので、まずは C# の例から徐々に Lisp 風に移行していきたいと思います。ラムダ式で書くと Lisp …