SICP 読書ノート#52 - 4.1.5 プログラムとしてのデータ (pp.228-230)

前回悩んでいたquoteのバグはparserが原因でした。

% git diff
diff --git a/ch4-ruby-evaluator/parser.rb b/ch4-ruby-evaluator/parser.rb
index f3a74f6..130c78d 100644
--- a/ch4-ruby-evaluator/parser.rb
+++ b/ch4-ruby-evaluator/parser.rb
@@ -14,7 +14,7 @@ class Parser
    def self.tokenize(input)
        tokens = input.strip
              .gsub(/\n/, ' ')
-             .gsub('\'(', '(quote (')
+             .gsub(/\'\(([0-9A-Za-z_\+\-\*\/\<\>\s]*)\)/, '(quote (\1))')
              .gsub('(', '( ')
              .gsub(')', ' )')
              .split(' ')

これでquoteを使った式も動くようになった。楽しい。

> (map + '(1 2 3) '(4 5 6) '(7 8 9))
=> (12 15 18)
> (apply + 1 2 '(3 4 5))
=> 15

処理系の基本的な部分は動くようになったので先へ進みます。

プログラムとしてのデータ

ここで作った処理系は万能機械(universal machine)と見なしてよい云々といったお話。「思考する機械」ですな。

文庫 思考する機械コンピュータ (草思社文庫)

問題 4.15

万能機械の流れからTuringの停止問題が出てきた。この手の問題がさらっと出てくるところがSICPのスゴイところだよなぁ。

(define (run-forever) (run-forever))

(define (try p)
  (if (halts? p p)
      (run-forever)
      'halted))

ここで(try try)を実行すると(halts? try try)が評価される。

もし(halts? try try)が(try try)を停止すると判定すると、(run-forever)が実行されるため再び(try try)が実行されて無限ループへ陥る。

反対に(halts? try try)が(try try)を停止しないと判定すると、'haltedとなるため停止してしまう。

よってhalts?の意図した振る舞いと矛盾するため、halts?を実装することは不可能である。

次回は「§4.1.6 内部定義」から。

---

※「SICP読書ノート」の目次はこちら