主にプログラミングに関して。Python, .NET Framework(C#), JavaScript, その他いくらか。
記事にあるサンプルやコードは要検証。使用に際しては責任を負いかねます

スポンサーサイト

                
tags:
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

JavaScript: λ Calculus

                
tags: JavaScript
http://blog.livedoor.jp/dankogai/archives/50996734.html

計算機科学でやる基礎的な内容の一つに「λ Calculus」というのがあるようだ。ちょいと学んでおく。JavaScriptでやる。


まず。JavaScriptの特徴の一つは先行評価ということ。どういうことか。スクリプトは基本的に上から下に向かって順次実行されていく。スクリプト中に式が現れれば、そこで式は実行される。
var a = 5;
var b = a - 5;
a = 0;
alert("a: " + a);
alert("b: " + b);

このスクリプトを実行すると、二行目でa-5が実行され、その結果がbに入れられる。これによってbが0と表示されるのは明らかだ。じゃあ次のようにしてみたらどうだろう。
var a = 5;
var b = function(){return a - 5};
a = 0;
alert("a: " + a);
alert("b: " + b());

無名関数を使って、bにa-5の計算結果ではなく、a-5という式を入れるようにした。こうすることでbが関数として実行されるまで、式a-5の実行はおあずけとなった。bが関数として呼ばれる前にaに0が代入されているので、最後のアラートで"b: -5"と表示される。
JavaScriptでは式がなんにもくるまれることなく置いてあると、処理がそこにさしかかった時点で問答なく実行される。無名関数を使うと問答無用の実行を回避し、あとで関数として呼び出して式を評価できる。


このページの上部にあるリンク先の小飼氏の記事にある例はなぜ動かない? 関数myifが定義後、7行目で呼ばれている。この引数に再帰となっている式があり、この式が実行され続けるので関数factの定義が再帰ループで終わらないのが原因だ。
var myif = function(_cond, _then, _else){
return _cond ? _then : _else;
};

function fact(n){
//alert(n);
return myif(n <= 1, 1, n * fact(n-1));
};
fact(10);


そこで小飼氏は下記のように書き換えている。
var myif = function(_cond, _then, _else){
return _cond() ? _then() : _else();
};
var fact = function(n){
return myif(function(){ return n <= 1 },
function(){ return 1 },
function(){ return n * fact(n-1) });
}
fact(10);

問題となっていた関数factのなかの再帰ループは、無名関数で式をつつむことで実行を後回しにされた。これでこのスクリプトは実行から正常に終了まですることができるものになった。ちなみにこの関数factは、整数を与えられた場合は階乗を計算して返す関数になっている。

式を記述しておいて、その式の評価は後回しにできる。これが「λ Calculus」。これによって再帰をする式を関数に渡せるようになる。
Pythonなどでは「ラムダ式」なるものが実装されている。無名関数と似ているわりに、ラムダ式中に複数行にわたる複雑な処理を書けないのでなんなのかと思っていたけど腑に落ちた。たぶん、本来は遅延評価したい式をつっこんでおくもので、複雑な処理をする関数のためのものではないんだろう。

おまけ
Pythonでは以下のように書ける。
def myif(_cond, _then, _else):
return _then() if _cond() else _else()

def fact(n):
return myif(lambda: n <= 1, lambda: 1, lambda: n * fact(n-1))

print fact(10)

これって階乗計算してるのよね……ということを考慮すると以下のように書ける。
fact = lambda x: x * (fact(x-1) if x > 1 else 1)
print fact(10)


ぼくは条件演算式を使ったが、怠惰なPythonistaは論理演算子を使って以下のように書くらしい。
参考:https://gist.github.com/fmeyer/289467
f = lambda x: x and x * f(x - 1) or 1
print f(10)


注意:実際に使うなら引数チェックが必要
            

コメントの投稿

非公開コメント

プロフィール

hMatoba

Author:hMatoba
Github

最新記事
リンク
作ったものなど
月別アーカイブ
カテゴリ
タグリスト

検索フォーム
Amazon
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。