Scheme - 手続きによる抽象の構築(手続きとその生成するプロセス(例: 素数性のテスト(アルゴリズム, 偶数の削除による高速化)))

計算機プログラムの構造と解釈[第2版]
(翔泳社)
ハロルド エイブルソン (著) ジュリー サスマン (著)
ジェラルド・ジェイ サスマン (著)
Harold Abelson (原著) Julie Sussman (原著)
Gerald Jay Sussman (原著) 和田 英一 (翻訳)

開発環境

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

計算機プログラムの構造と解釈[第2版](ハロルド エイブルソン (著)、ジュリー サスマン (著)、ジェラルド・ジェイ サスマン (著)、Harold Abelson (原著)、Julie Sussman (原著)、Gerald Jay Sussman (原著)、和田 英一 (翻訳)、翔泳社、原書: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の1(手続きによる抽象の構築)、1.2(手続きとその生成するプロセス)、1.2.6(例: 素数性のテスト)、問題 1.23.を解いてみる。

その他参考書籍

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

問題 1.23.

コード(BBEdit, Emacs)

sample23.scm

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

(define square (lambda (x) (* x x)))
(define (runtime)
  (use srfi-11)
  (let-values (((a b) (sys-gettimeofday)))
    (+ (* a 1000000) b)))

(define prime-slow? (lambda (n) (= n (smallest-divisor-slow n))))
(define smallest-divisor-slow
  (lambda (n) (find-divisor-slow n 2)))
(define find-divisor-slow
  (lambda (n test-divisor)
    (cond ((> (square test-divisor) n) n)
          ((divides? test-divisor n) test-divisor)
          (else (find-divisor-slow n (+ test-divisor 1))))))

(define next (lambda (n)
               (if (= n 2)
                   3
                   (+ n 2))))
(define prime? (lambda (n) (= n (smallest-divisor n))))
(define smallest-divisor
  (lambda (n) (find-divisor n 2)))
(define find-divisor
  (lambda (n test-divisor)
    (cond ((> (square test-divisor) n) n)
          ((divides? test-divisor n) test-divisor)
          (else (find-divisor n (next test-divisor))))))
(define divides? (lambda (a b) (= (remainder b a) 0)))

(define (timed-prime-test-slow n)
  (newline)
  (display n)
  (start-prime-test-slow n (runtime)))

(define (start-prime-test-slow n start-time)
  (if (prime-slow? n)
      (report-prime (- (runtime) start-time))))

(define (timed-prime-test n)
  (newline)
  (display n)
  (start-prime-test n (runtime)))

(define (start-prime-test n start-time)
  (if (prime? n)
      (report-prime (- (runtime) start-time))))

(define (report-prime elapsed-time)
  (display " *** ")
  (display elapsed-time))
        
(define primes (list 1009 1013 1019
                     10007 10009 10037
                     100003 100019 100043
                     1000003 1000033 1000037))

(for-each
 (lambda (n)
   (timed-prime-test-slow n)
   (timed-prime-test n)
   (newline))
 primes)
(newline)

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

$ ./sample23.scm

1009 *** 51
1009 *** 36

1013 *** 32
1013 *** 22

1019 *** 32
1019 *** 22

10007 *** 97
10007 *** 63

10009 *** 99
10009 *** 61

10037 *** 99
10037 *** 62

100003 *** 308
100003 *** 189

100019 *** 307
100019 *** 191

100043 *** 306
100043 *** 192

1000003 *** 969
1000003 *** 604

1000033 *** 970
1000033 *** 679

1000037 *** 961
1000037 *** 588

$ 

ステップ数を半分にしても、二倍速にならないのは、基本手続き+の呼び出しではなくnext手続きの呼び出しになること、さらに、特殊形式ifによる述語の評価が必要になるからという理由が考えられる。