Code Aquarium

minazoko's blog -*- 水底のブログ -*-

(PowerShell)ダイナミックスコープなReduce

$1. 関数内再帰関数で Join-Paths

最初にちょっと寄り道。
前回エントリでは、引数を配列にして3つ以上のパス要素連結関数を書きました。
Join-Path 同様に可変長の引数にすることは出来ないでしょうか? できました。

function Join-Paths{
    function rec ([string[]] $paths){
        $parent, $rest = $paths
        if(-not $rest){
            $parent
        }else{
            Join-Path $parent (rec $rest)
        }
    }
    rec $args
}
PS C:\> Join-Paths C: xxx yyy zzz
C:\xxx\yyy\zzz

仮引数を省略するとすべての引数は暗黙変数 $argsに配列で渡されます。可変長の再帰関数は書けませんが $argsで受けてしまえば配列を要求する関数へ渡すことが可能です。
ここでは関数内のローカル関数として再帰関数を定義しています。

$2. パイプラインで実装

PowerShellといえばパイプライン指向ですので、パイプラインによる実装も書いてみましょう。

function Join-Paths {
    $acc, $rest = $args
    $rest | % {}{$acc=Join-Path $acc $_}{$acc}
}

% の後ろの3つのブロックが、begin(初期化), process(繰り返し), end(最終処理)となっています。初期化処理は特に必要なかったので空っぽです。
名前付引数を使えば beginブロック自体を省略できます。

function Join-Paths{
    $acc, $rest = $args
    $rest | % -Process {$acc=Join-Path $acc $_} -End {$acc}
}

この場合、-Processも省略できるようです。

function Join-Paths{
    $acc, $rest = $args
    $rest | % {$acc=Join-Path $acc $_} -End {$acc}
}

PowerShell再帰呼び出しはとても遅いので、通常はこのようにパイプラインやループで書くほうがよさそうです。

$3. ダイナミックスコープなReduce

本題。
% (ForEach-Objectコマンドレット)で畳み込み処理ができましたが、Endブロックを書いたり、Beginブロックに気を遣ったりするのは少し煩わしいですね。そこで関数型言語によくある高階関数的な畳み込み関数 Reduceを書いてみました。

function Get-ReduceObject ([ScriptBlock] $Script, [object] $Init){
    if($null -ne $Init){
        $acc = $Init
    }elseif($input.MoveNext()){
        $acc = $input.Current
    }else{
        return
    }
    $input | % {$acc = & $Script} -End {$acc}
}

Set-Alias reduce Get-ReduceObject

$Init は畳み込みの初期値です。省略可能です。省略した場合、$Inputの初項で代用されます。
$Input は 暗黙の変数で、パイプラインから流れ込むデータを表します。IEnumerator を実装しているので。MoveNextメソッドで参照先を移動し、Currentプロパティで現在の値を取得できます。(ここでは初項を取り出すために MoveNext,Currentを使っています)。また$Inputはforeachで回したりパイプラインへ流すこともできます。

ScriptBlockは無名関数のようなものです。& 演算子で実行します。
ScriptBlockはダイナミックスコープです。クロージャではないので ScriptBlock内の自由変数は実行時の環境で値が決まります。

使ってみます。

PS C:\> 1..10 | reduce {$_ * $acc}
3628800

PS C:\> 1..5 | reduce { "(cons $_ $acc)" } -Init "NIL"
(cons 5 (cons 4 (cons 3 (cons 2 (cons 1 NIL)))))

$_ と $acc は Get-ReduceObject内で $Script が実行される環境で見えている $_ と $acc の値となります。...でも、Get-ReduceObject 内に $_ は見当たりませんね。
ForEach-Objectコマンドレット (%) の Processブロック内ではパイプラインからの値が一つ一つ 暗黙変数 $_ でわたってきます。この暗黙変数がそのまま $Scriptから見えているのです。

この reduce を使ってパス連結関数を書くと。

function Join-Paths {
    $args | reduce  {Join-Path $acc $_}
}

ForEach-Object を生で使った場合と比べるとだいぶスッキリしました。

$4. Emacs Lispでも書いてみる。

Emacs Lispダイナミックスコープな処理系ということで有名です。ならば同じことができるはず。

;; ダイナミックスコープを利用した reduce
(defun reduce-dy (fun ls &optional init)
  (let (($acc (if init init (car ls)))
        (ls (if init ls (cdr ls))))
    (dolist ($_ ls $acc)
      (setq $acc (funcall fun)))))
(reduce-dy
 '(lambda () (* $acc $_))
 '(1 2 3 4 5 6 7 8 9 10))

;;=> 3628800
(reduce-dy
 '(lambda () (format "(cons %s %s)" $_ $acc))
 '(1 2 3 4 5)
 'NIL)

;;=> "(cons 5 (cons 4 (cons 3 (cons 2 (cons 1 NIL)))))"

なるほどね。