Scheme - 手続きによる抽象の構築(作用的順序と特殊形式if(special form)について)

計算機プログラムの構造と解釈
Gerald Jay Sussman, Julie Sussman
Harold Abelson (原著) 和田 英一 (翻訳)

開発環境

• OS X Mavericks - Apple(OS)
• Emacs (CUI)、BBEdit - Bare Bones Software, Inc. (GUI) (Text Editor)
• Scheme (プログラミング言語)
• Gauche (処理系)

計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション、原書: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の1(手続きによる抽象の構築)、1.1(プログラミングの要素)、1.1.7(例: Newton法による平方根)、問題 1.6.を解いてみる。

その他参考書籍

• Instructor's Manual to Accompany Structure & Interpretation of Computer Programs
• プログラミングGauche (Kahuaプロジェクト (著), 川合 史朗 (監修), オライリージャパン)

問題 1.6.

Lispは作用的順序の評価を使っていることに注意する必要がある。

new-ifを使用した場合。

1. (good-enough? guess x)を評価
2. guessを評価
3. (sqrt-iter (improve guess x) x)を評価
4. (improve guess x)を評価(guess1とする)
5. (sqrt-iter guess1 x)を評価
6. (good-enough? guess1 x)を評価
7. guess1を評価
8. (sqrt-iter (improve guess1 x) x)を評価
9. (improve guess1 x)を評価(guess2とする)
10. (sqrt-iter guess2 x)を評価
11. (good-enough? guess2 x)を評価
12. 1-5を循環

特殊形式ifを使った場合はpredicateがtrueの場合、else-clauseが評価されないので循環することはない。このことが、ifは特殊形式であり、condを利用し、普通の手続きとして定義してはいけない理由。

確認。

コード(BBEdit, Emacs)

sample.scm

#!/usr/bin/env gosh
;; -*- coding: utf-8 -*-

(define (square x) (* x x))

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

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

(define (improve guess x)
  (average guess (/ x guess)))

(define (average x y)
  (/ (+ x y) 2))

(define (good-enough? guess x)
  (≪ (abs (- (square guess) x)) 0.001))

(define (sqrt x)
  (sqrt-iter 1.0 x))

入出力結果(Terminal, REPL(Read, Eval, Print, Loop))

$ gosh
gosh> (load "./sample.scm")
#t
gosh> (sqrt 4)
^C*** UNHANDLED-SIGNAL-ERROR: unhandled signal 2 (SIGINT)
Stack Trace:
_______________________________________
  0  x

  1  (abs (- (square guess) x))
        At line 23 of "./sample.scm"
  2  (good-enough? guess x)
        At line 11 of "./sample.scm"
  3  (sqrt-iter (improve guess x) x)
        At line 13 of "./sample.scm"
  4  (sqrt-iter (improve guess x) x)
        At line 13 of "./sample.scm"
  5  (sqrt-iter (improve guess x) x)
        At line 13 of "./sample.scm"
  6  (sqrt-iter (improve guess x) x)
        At line 13 of "./sample.scm"
  7  (sqrt-iter (improve guess x) x)
        At line 13 of "./sample.scm"
  8  (sqrt-iter (improve guess x) x)
        At line 13 of "./sample.scm"
  9  (sqrt-iter (improve guess x) x)
        At line 13 of "./sample.scm"
 10  (sqrt-iter (improve guess x) x)
        At line 13 of "./sample.scm"
 11  (sqrt-iter (improve guess x) x)
        At line 13 of "./sample.scm"
 12  (sqrt-iter (improve guess x) x)
        At line 13 of "./sample.scm"
 13  (sqrt-iter (improve guess x) x)
        At line 13 of "./sample.scm"
 14  (sqrt-iter (improve guess x) x)
        At line 13 of "./sample.scm"
 15  (sqrt-iter (improve guess x) x)
        At line 13 of "./sample.scm"
 16  (sqrt-iter (improve guess x) x)
        At line 13 of "./sample.scm"
 17  (sqrt-iter (improve guess x) x)
        At line 13 of "./sample.scm"
 18  (sqrt-iter (improve guess x) x)
        At line 13 of "./sample.scm"
 19  (sqrt-iter (improve guess x) x)
        At line 13 of "./sample.scm"
 20  (sqrt-iter (improve guess x) x)
        At line 13 of "./sample.scm"
 21  (sqrt-iter (improve guess x) x)
        At line 13 of "./sample.scm"
 22  (sqrt-iter (improve guess x) x)
        At line 13 of "./sample.scm"
 23  (sqrt-iter (improve guess x) x)
        At line 13 of "./sample.scm"
 24  (sqrt-iter (improve guess x) x)
        At line 13 of "./sample.scm"
 25  (sqrt-iter (improve guess x) x)
        At line 13 of "./sample.scm"
 26  (sqrt-iter (improve guess x) x)
        At line 13 of "./sample.scm"
 27  (sqrt-iter (improve guess x) x)
        At line 13 of "./sample.scm"
 28  (sqrt-iter (improve guess x) x)
        At line 13 of "./sample.scm"
 29  (sqrt-iter (improve guess x) x)
        At line 13 of "./sample.scm"
... (more stack dump truncated)
gosh> (exit)
$

おまけ。

正規順序の評価を使っているHaskellの場合はifは特殊形式ではなく普通の手続きとして定義出来る。

コード(BBEdit, Emacs)

sample.hs

{-# OPTIONS -Wall -Werror *-}
module Main where

main :: IO ()
main = print $ mySqrt 4

square :: Double -> Double
square x = x * x

newIf :: Bool -> a -> a -> a
newIf predicate x y | predicate = x
                    | otherwise = y

sqrtIter :: Double -> Double -> Double
sqrtIter guess x = newIf (goodEnough guess x) guess
                         (sqrtIter (improve guess x) x)

improve :: Double -> Double -> Double
improve guess x = average guess (x / guess)

average :: Double -> Double -> Double
average x y = (x + y) / 2

goodEnough :: Double -> Double -> Bool
goodEnough guess x = (abs $ (square guess) - x) ≪ 0.001

mySqrt :: Double -> Double
mySqrt = sqrtIter 1.0

入出力結果(Terminal, runghc)

$ runghc Sample.hs
2.0000000929222947
$