計算機科学のブログ

Building Abstractions with Functions - The Elements of Programming - Example: Square Roots by Newton's Method - conditional expressions, evaluation, order

Structure and Interpretation of Computer Programs: JavaScript Edition(Harold Abelson(著)、Gerald Jay Sussman(著)、Julie Sussman(著)、The MIT Press)のChapter 1(Building Abstractions with Functions)、1.1(The Elements of Programming)、1.1.7(Example: Square Roots by Newton’s Method)、Exercise 1.6の解答を求めてみる。

predicate ? then_clause : else_clauseの場合の評価はpredicateが真の場合にはthen_clauseが評価されて、偽の場合にはelse_clauseが評価されるけど、conditional(predicate, then_clause, else_clause)の場合には引数のpredicate、then_clause、else_clauseが全てが評価される。

なので、sqrt_iterの呼び出しの評価について、例えばguessが1、xが2の場合、

  1. sqrt_iter(1, 2)
  2. conditional(is_good_enough(1, 2), 1, sqrt_iter(improve(1, 2), 2))
  3. conditional(abs(square(1) - 2) < 0.001, 1, sqrt_iter(improve(1, 2), 2))
  4. conditional(abs(1 * 1 - 2) < 0.001, 1, sqrt_iter(improve(1, 2), 2))
  5. conditional(1 < 0.001, 1, sqrt_iter(improve(1, 2), 2))
  6. conditional(false, 1, sqrt_iter(average(1, 1/2), 2))
  7. conditional(false, 1, sqrt_iter(1.5, 2))
  8. conditional(false, 1, conditional(is_good_enough(1.5, 2), 1.5, sqrt_iter(improve(1.5, 2), 2)))
  9. …

となって終了しない。

実際に確認。

コード

let abs = Math.abs;

function square(x) {
    return x * x;
}
function improve(guess, x) {
    return average(guess, x / guess);
}
function average(x, y) {
    return (x + y) / 2;
}
function is_good_enough(guess, x) {
    return abs(square(guess) - x) < 0.001;
}
function conditional(predicate, then_clause, else_clause) {
    return predicate ? then_clause : else_clause;
}
function sqrt_iter(guess, x) {
    return conditional(
        is_good_enough(guess, x),
        guess,
        sqrt_iter(
            improve(guess, x),
            x
        )
    );
}

console.log(sqrt_iter(1, 2));

入出力結果(Terminal, Zsh)

% node answer1.6.js
/Users/…/answer1.6.js:13
    return abs(square(guess) - x) < 0.001;
    ^

RangeError: Maximum call stack size exceeded
    at is_good_enough (/Users/…/answer1.6.js:13:5)
    at sqrt_iter (/Users/…/answer1.6.js:20:9)
    at sqrt_iter (/Users/…/answer1.6.js:22:9)
    at sqrt_iter (/Users/…/answer1.6.js:22:9)
    at sqrt_iter (/Users/…/answer1.6.js:22:9)
    at sqrt_iter (/Users/…/answer1.6.js:22:9)
    at sqrt_iter (/Users/…/answer1.6.js:22:9)
    at sqrt_iter (/Users/…/answer1.6.js:22:9)
    at sqrt_iter (/Users/…/answer1.6.js:22:9)
    at sqrt_iter (/Users/…/answer1.6.js:22:9)
%

遅延評価のHaskellなら上手くいく。

コード

import Distribution.Simple.Utils (xargs)
square :: Num a => a -> a
square x = x * x

improve :: Fractional a => a -> a -> a
improve guess x = average guess $ x / guess

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

isGoodEnough :: (Ord a, Fractional a) => a -> a -> Bool
isGoodEnough guess x = abs (square guess - x) < 0.001

conditional :: Bool -> p -> p -> p
conditional predicate then_clause else_clause = 
    if predicate
        then then_clause
        else else_clause

sqrtIter :: (Ord t, Fractional t) => t -> t -> t
sqrtIter guess x = 
    conditional
        (isGoodEnough guess x)
        guess $ 
        sqrtIter (improve guess x) x

main :: IO ()
main = do
    print $ sqrtIter 1 2

入出力結果(Terminal, Zsh)

% runghc answer1.6.hs
1.4142156862745097
%