(power-c 3)
==> (lambda (n) (if (= 3 0) 1 (* n (power (- 3 1) n))))
==> (lambda (n) (* n (power 2 n)))
==> (lambda (n) (* n (if (= 2 0) 1 (* n (power (- 2 1) n)))))
==> (lambda (n) (* n (* n (power 1 n))))
==> (lambda (n) (* n (* n (* n (power 0 n)))))
==> (lambda (n) (* n (* n (* n (if (= 0 0) 1 (power (- 0 1) n))))))
==> (lambda (n) (* n (* n (* n 1))))

ところで、このように変数部分と定数部分の混ざったものを評価して簡単化を行うことを 部分評価 (pertial evaluation) といいます。

部分評価の話題としてもうひとつ。 テーマは、インタプリタとコンパイラと部分評価。 普通インタプリタというのは、ソースをみながら対応する計算を行っていくことで、 プログラムを実行します。 しかしながらソースが変化しないなら毎度毎度ソースを眺めるのではなくて、 ソースに対応する計算を先につくっておいて、直接計算の方を実行したくなります。 つまりはコンパイルして、実行ファイルを直接実行しようというわけです。 ここで、少し見立てをしてみましょう。 「インタプリタ:interpreter」をプログラムに見立て、 「プログラム:program」と「入力:input」を入力に見立て「インタプリタ」に与えます。 で、(interpreter (program input)) を部分評価します。 そうすると、input は分からないままなので、 program に特化された interpreter が生まれます。 (interpreter (program input)) ==> (compiled-program input) というわけです。 つまり、コンパイラ操作というのは、 プログラムに特化したインタプリタをつくることだと言えます。 このようなプログラム変換の事を futamura projection と呼びます。