SICP 4.2 Variations on a Scheme -- Lazy Evaluation

ノート

4.2.1 Normal Order and Applicative Order

Wikipediaの訳語によると『正規順序と適用順序』。
正規順序は引数を簡約する前に手続きを適用する。適用順序は手続きを適用する前に引数を簡約する。

脚注によるとnormal orderとlazy evaluationと言う言葉の使い分けは曖昧だと。主にlazy evaluationは評価メカニズムにおいて、normal orderは言語の（式の？）意味論において使われる。

引数が評価（簡約）される前に手続きが評価される場合その手続きを非正格（non-strict）と言い、引数が先に評価される場合にはその手続きを正格（strict）と言う。
純粋に適用順序の言語では手続きは全て正格。純粋に正規順序の言語では全ての複合手続きは非正格でプリミティブはどちらもあり得る。

非正格を上手く利用する例としてconsが挙げられる。データの中身が確定する前にそのデータに対する操作を開始出来る。

Exercise 4.25

unlessの引数は最初の引数の結果が何であれ全て評価される。つまり(factorial 1)が呼ばれてもまた(factorial 0)を呼んでしまい、そのまま(factorial -1)、(factorial -2)と永久に呼び続けてしまう。
やってみた

> (define (unless condition usual-value exceptional-value)
  (if condition exceptional-value usual-value))
> unless
#<procedure:unless>
> (define (factorial n)
  (unless (= n 1)
          (* n (factorial (- n 1)))
          1))
> (factorial 5)
. . user break
> 

停止させるまで返って来ない。
正規順序の場合、unlessの引数は評価されないままunlessの中のifに到達し、conditionがfalseの時に限りusual-value即ち(* n (factorial (- n 1)))が評価されるので、(factorial 1)が呼ばれるとusual-valueの部分は評価されずに戻って来る。
Racketでdelayとforceを使って実験。

> (define (unless condition usual-value exceptional-value)
    (if (force condition) (force exceptional-value) (force usual-value)))
> (define (factorial n)
    (unless (delay (= n 1))
      (delay (* n (factorial (- n 1))))
      (delay 1)))
> (factorial 5)
120
> 

Exercise 4.26

Benは遅延評価しなくてもスペシャルフォームつまりマクロを使えばunlessは実現可能と主張。Alyssaはそうしてしまうとunlessを高階関数の引数や戻り値として使えないと主張。

Benの主張の通りシンタックスとして実装する。

(define (analyze exp)
  (cond ((self-evaluating? exp) 
;…中略
        ((if? exp) (analyze-if exp))
        ((unless? exp) (analyze (unless->if exp)))
;…以下省略

(define (unless? exp) (tagged-list? exp 'unless))
(define (unless-condition exp) (cadr exp))
(define (unless-usual-value exp) (caddr exp))
(define (unless-exceptional-value exp) (cadddr exp))
(define (unless->if exp)
  (make-if (unless-condition exp) (unless-exceptional-value exp) (unless-usual-value exp)))

実行する

> (eval '(define (factorial n)
           (unless (= n 1)
             (* n (factorial (- n 1)))
             1))
        the-global-environment)
'ok
> (eval '(factorial 5) the-global-environment)
120
> 

Alyssaの主張。便利と言う訳ではないがこんなのを作ってみた。

(define (in-case condition usual-value exceptional-value)
  (if (force condition) (force usual-value) (force exceptional-value)))

(define (unless condition usual-value exceptional-value)
  (if (force condition) (force exceptional-value) (force usual-value)))

(define (select control pred lst)
  (if (null? lst)
      '()
      (control (delay (pred (car lst)))
               (delay (cons (car lst) (select control pred (cdr lst))))
               (delay (select control pred (cdr lst))))))

in-caseはifと同じ。だけどここでifを定義してしまうとunlessでも使っているので別の名前にした。(condを使う手もあったが）filterと同じ働きのselect。lazy evaluationをシミュレートする為にforceとdelayを使う。

> (select in-case even? '(0 1 2 3 4 5 6 7 8 9))
'(0 2 4 6 8)
> (select unless even? '(0 1 2 3 4 5 6 7 8 9))
'(1 3 5 7 9)
> 

DSL的な使い方をするのに、形式が決まってしまうマクロよりも柔軟に対応出来る様な気がする。