めらんこーど地階

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

Powershell | 22:17 |

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

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

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

全ては１から

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

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

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

これで、チャーチ数の１を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が参照出来なくなっていたというのだ。

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

>$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によるクロージャは完全な環境を保存しているわけではなさそうだ。

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

ツイートする