めらんこーど地階 RSSフィード

2011-07-21

Powershell 2.0でチャーチ数の夢を見た

| 22:17 | Powershell 2.0でチャーチ数の夢を見たを含むブックマーク Powershell 2.0でチャーチ数の夢を見たのブックマークコメント

(***) $one=&{params($f)&{params($X)f x}};とか受け付けてくれない残念なps1

と言われて、最初は何のことか分からなかったけど、なるほどチャーチ数であることに気付いた。

折角なので受けて立とう、その挑戦を。

全ては1から

チャーチ数の1は以下のように表される。

ONE := λf.λx. f x

愚直にλ項をスクリプトブロック相当と考えて組むと

$one={param($f){param($x)&$f($x)}}

となる。

しかし、これを使って評価しようとすると、思わぬエラーと遭遇することになる。

> &$(&$one({param($x)$x+1}))(0)
パイプライン要素内で '&' の後にある式が無効なオブジェクトを作成しました。コマンド名、スクリプト ブロック、または CommandInfoオブジェクトになる必要があります。
発生場所 行:1 文字:27
+ $one={param($f){param($x)& <<<< $f($x)}};
    + CategoryInfo          : InvalidOperation: (:) []、RuntimeException
    + FullyQualifiedErrorId : BadExpression

$fが無効なオブジェクト?どういうことだろうか。

実はスクリプトブロックは環境を保持しない、つまり、クロージャではない。どなたかの研究によると、変数スタックに確保されるらしく、変数の定義されたスクリプトブロックから出ると消されてしまう。そのため、入れ子になっているスクリプトブロックで$fを参照しようとすると$Nullとなり、このエラーを見るハメになったわけだ。

そこで活躍するのが、Powershell 2.0から登場したスクリプトブロックをクロージャに変換するメソッド、ScriptBlock::GetNewClosureだ。クロージャにしてしまえばその時点での環境が保存されるので、環境中にある変数を参照出来るようになる。

> $ONE={param($f){param($x)&$f($x)}.GetNewClosure()}
> &$(&$one({param($x)$x+1}))(0)
1

すごくまどろっこしい書き方になっているけど、これは致し方ない。

これで、チャーチ数の1をPowershellで記述することが叶った。

気づくわけがない落とし穴

勢いに乗って次のチャーチ数の元を得る関数SUCCを実現してみよう。

SUCCの定義は次の通りだ。

SUCC := λn.λf.λx. f (n f x)

単位元の反省を元にきっちりクロージャで書こう。

$succ={param($n){param($f){param($x)&$f(&$(&$n($f))($x))}.GetNewClosure()}.GetNewClosure()}

これでTWOを求めてみると、

> $succ={param($n){param($f){param($x)&$f(&$(&$n($f))($x))}.GetNewClosure()}.GetNewClosure()}
> &$(&$(&$succ($one))({param($x)$x+1}))(0)
パイプライン要素内で '&' の後にある式が無効なオブジェクトを作成しました。コマンド名、スクリプト ブロック、または CommandInfo オブジェクトになる必要があります。

発生場所 行:1 文字:45
+ $succ={param($n){param($f){param($x)&$f(&$(& <<<< $n($f))($x))}.GetNewClosure()}.GetNewClosure()}
    + CategoryInfo          : InvalidOperation: (:) []、RuntimeException
    + FullyQualifiedErrorId : BadExpression

パイプライン要素内で '&' の後にある式が無効なオブジェクトを作成しました。コマンド名、スクリプト ブロック、または CommandInfo オブジェクトになる必要があります。
発生場所 行:1 文字:42
+ $succ={param($n){param($f){param($x)&$f(& <<<< $(&$n($f))($x))}.GetNewClosure()}.GetNewClosure()}
    + CategoryInfo          : InvalidOperation: (:) []、RuntimeException
    + FullyQualifiedErrorId : BadExpression

???どうして?どういうことだろう?

エラーメッセージは、$nが関数呼び出し出来ない値を持っていると言っている。考えられる値はただ1つ、$Nullだ。クロージャで$nは保存されているはずだ。$Nullになってしまうはずがない。……ない?

そう、ここにGetNewClosureメソッドの落とし穴があった。

GetNewClosureはブロックで参照されていない変数を落としてしまうらしく、中間のスクリプトブロックで参照されていないがために、一番深いスクリプトブロックで$nが参照出来なくなっていたというのだ。

解決策を考えてみたところ、1つ思い浮かんだ。入れ子のスクリプトブロックが参照している変数を中間のスクリプトブロックが影響の無い程度に参照してやるのだ。

>$succ={param($n){param($f)$n=$n;{param($x)&$f(&$(&$n($f))($x))}.GetNewClosure()}.GetNewClosure()}
>&$(&$(&$succ($one))({param($x)$x+1}))(0)
2

この解決策を以て、無事にTWOを求めることが出来た。内部仕様が分からないので、何とも言えないが、GetNewClosureによるクロージャは完全な環境を保存しているわけではなさそうだ。

まさか、まさかこんな課題でこんな現象に出会うとはね?

トラックバック - http://d.hatena.ne.jp/anon_193/20110721/1311254247