問題1.6

Alyssa P. Hacker は if が特殊形式である理由が分からない。「condを利用し、普通の手続きとして定義してはいけないの?」と聞いた。Alyssa の友人の Eva Lu Ator はそうすることはもちろん出来るといって、if の新版を定義した:

(define (new-if predicate then-clause else-clause)
  (cond (predicate then-clause)
 (else else-clause)))

Eva は Alyssa にプログラムを見せた:

> (new-if (= 2 3) 0 5)
5
> (new-if (= 1 1) 0 5)
0
> 

Alyssa は喜び、平方根のプログラムを書き直すのにnew-ifを使った:

(define (sqrt-iter guess x)
  (new-if (good-enough? guess x)
   guess
   (sqrt-iter (improve-guess x)
       x)))

Alyssa が平方根を計算するのにこれを使おうとすると、何が起きるか、説明せよ。

無限ループに陥ります。
問題はnew-ifが手続きであるから、です。ボディ部の評価に入る前に与えられた引数が全部評価されないとなりません。
Eva の例の場合は、再帰定義ではないので問題が生じないのですが、Alyssa が用いようとした手続きは再帰構造を持っています。従って、再帰部分であるnew-ifの第3引数を評価するとまたもや引数の展開が生じて、終了地点が無いまま無限ループに入ってしまうのです。
new-ifも本来はマクロを使って定義するべき、でしょう。これはSchemeの衛生的マクロで簡単に書くことが可能です。

(define-syntax new-if
  (syntax-rules ()
    ((_ predicate then-clause else-clause)
     (cond (predicate then-clause)
    (else else-clause)))))

問題1.5

Ben Bitdiddleは、彼の対面している解釈系が、作用的順序の評価を使っているか、正規順序の評価を使っているか決定するテストを発明した。次の二つの手続きを定義した:

(define (p) (p))

(define (test x y)
  (if (= x 0)
      0
      y))

彼は次に式

(test1 0 (p))

を評価してみた。作用的順序の評価を使う解釈系で、Benはどういう振舞いを見るか。正規順序を使う解釈系で、彼どういう振舞いを見るか。説明せよ。(特殊形式ifの評価規則は、解釈系が正規順序と作用的順序のどちらを使うかに無関係に同じとする: 述語式を最初に評価し、その結果が帰結式と代替式のいずれを評価するかを決める。)

作用的順序の評価を使うインタプリタだと、(test1 0 (p))は無限ループに陥ります。
何故なら、testのボディが評価される前に引数が評価され、(p)が評価されて(p)となり、また(p)が評価され・・・と、引数の展開がどこまでも終わりません。結果、引数yの実引数の無限評価が引き起こり、永久にボディ部に入らないのです。
一方、正規順序を使うインタプリタだと、「必要になるまで」引数が評価されないので、(test1 0 (p))は0を返して終了します。何故なら正規評価では(p)が評価される事自体が無いから、です。
例示のコードの「正規順序」のエミュレートだと、マクロで記述して動作を見てみた方が良いでしょう。マクロはコードの展開前に引数を評価する事がありません。
とは言っても、Schemeの衛生的マクロだと記述出来そうにないんで、仕様範囲外の伝統的マクロ(レガシーマクロやコードタイプのマクロ等としばしば呼ばれる)で記述してみた方が良いでしょう。
PLT Schemeの場合は、次のようにして書いてみれば良いでしょう。

(require mzlib/defmacro)  ;実装依存のdefine-macro使用を宣言

(define-macro (test-macro x y)
  (if (zero? x)
      0
      y))

実行結果は以下の通りです。

> (test-macro 0 (p))
0
> 

ちなみに旧いLispなんかの場合は、マクロを使うまでも無く、処理系のNEXPR型やFEXPR型の関数で簡単に確かめる事が出来たかもしれません。
そう言う意味では、問題の質としては旧いのかもな、とも思います。

問題1.4

われわれの評価モデルは、演算子が合成式である組合せでも使えることを観察せよ。それに従って、次の手続きの振舞いを述べよ。

(define (a-plus-abs-b a b)
  ((if (> b 0) + -) a b))

bが0よりも大きい場合、if式は+を返し、その場合評価対象は

(+ a b)

となる。それ以外の場合、

(- a b)

が評価される。
結果、手続き名通り、aとbの絶対値が加算されるのと同じ結果となる。

問題1.3

三つの数を引数としてとり、大きい二つの数の二乗の和を返す手続きを定義せよ。

(define (Q1.3 x y z)
  (let ((w (min x y z))
 (x2 (* x x))
 (y2 (* y y))
 (z2 (* z z)))
    (cond ((= x w) (+ y2 z2))
   ((= y w) (+ z2 x2))
   (else (+ x2 y2)))))

問題1.2

次の式を前置記法に翻訳せよ。

(/ (+ 5 4 (- 2 (- 3 (+ 6 4/5)))) (* 3 (- 6 2) (- 2 7)))

問題1.1

Welcome to MzScheme v4.2.3 [3m], Copyright (c) 2004-2009 PLT Scheme Inc.
> 9
9
> (+ 5 3 4)
12
> (- 9 1)
8
> (/ 6 2)
3
> (+ (* 2 4) (- 4 6))
6
> (define a 3)
> (define b (+ a 1))
> (+ a b (* a b))
19
> (= a b)
#f
> (if (and (> b a) (< b (* a b)))
      b
      a)
4
> (cond ((= a 4) 6)
 ((= b 4) (+ 6 7 a))
 (else 25))
16
> (+ 2 (if (> b a) b a))
6
> (* (cond ((> a b) a)
    ((< a b) b)
    (else -1))
     (+ a 1))
16
>