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.22.を解いてみる。

その他参考書籍

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

問題 1.22.

コード(BBEdit, Emacs)

sample22.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? (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 (+ test-divisor 1))))))
(define divides? (lambda (a b) (= (remainder b a) 0)))

(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 search-for-primes
  (lambda (a b)
    (if (= (remainder a 2) 0)
        (search-for-primes-iter (+ a 1) b)
        (search-for-primes-iter a b))))

(define search-for-primes-iter
  (lambda (a b)
    (if (< a b)
        (begin  (timed-prime-test a)
                (search-for-primes-iter (+ a 2) b)))))

(search-for-primes 1000 1020)
(newline)
(search-for-primes 10000 10038)
(newline)
(search-for-primes 100000 100044)
(newline)
(search-for-primes 1000000 1000038)
(newline)

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

$ ./sample22.scm

1001
1003
1005
1007
1009 *** 33
1011
1013 *** 32
1015
1017
1019 *** 31

10001
10003
10005
10007 *** 97
10009 *** 98
10011
10013
10015
10017
10019
10021
10023
10025
10027
10029
10031
10033
10035
10037 *** 98

100001
100003 *** 302
100005
100007
100009
100011
100013
100015
100017
100019 *** 303
100021
100023
100025
100027
100029
100031
100033
100035
100037
100039
100041
100043 *** 307

1000001
1000003 *** 954
1000005
1000007
1000009
1000011
1000013
1000015
1000017
1000019
1000021
1000023
1000025
1000027
1000029
1000031
1000033 *** 1088
1000035
1000037 *** 1018
$

時間のデータは大体、増加の程度を支持している。