EoPL reading (49) 2.1 Specifying Data via Interfaces

scheme

なんだか括弧内の数値だけが増えていっている今日この頃。とりあえず定義されている手続きを全部 disasm してみます。
まず succ から

gosh> (disasm (lambda (n)
    (cond ((null? n) '(1))
          ((= (car n) (- N 1))
           (cons 0 (succ (cdr n))))
          (else
           (cons (+ 1 (car n)) (cdr n)))))
)
main_code (name=#f, code=0x815ce80, size=29, const=3, stack=11):
args: #f
     0 LREF0                    ; n
     1 BNNULL 5                 ; (null? n)
     3 CONST-RET (1)
     5 LREF0                    ; n
     6 CAR-PUSH                 ; (car n)
     7 GREF #<identifier user#N>; N
     9 NUMADDI(-1)              ; (- N 1)
    10 BNUMNE 21                ; (= (car n) (- N 1))
    12 CONSTI-PUSH(0)
    13 PRE-CALL(1) 19
    15 LREF0                    ; n
    16 CDR-PUSH                 ; (cdr n)
    17 GREF-CALL(1) #<identifier user#succ>; (succ (cdr n))
    19 CONS                     ; (cons 0 (succ (cdr n)))
    20 RET
    21 LREF0                    ; n
    22 CAR                      ; (car n)
    23 NUMADDI(1)               ; (+ 1 (car n))
    24 PUSH
    25 LREF0                    ; n
    26 CDR                      ; (cdr n)
    27 CONS                     ; (cons (+ 1 (car n)) (cdr n))
    28 RET
#<undef>
gosh>

よく考えたら計算量って N (基数の値) と数値自体の大きさに依存してますね。N が小さくて数値が大きいほど繰り返しが増えるのは disasm しなくても分かりますね。とほほ。
えと、具体的に考えてみると、数値が 255 として

  • 基数が 2 だと 11111111 に 1 を加えるので繰り返しは 9 回?
  • 基数が 4 だと 3333 に 1 を加える形? なら繰り返しは 5 回?
  • 基数が 8 だと 773 に 1 を加える形? なら繰り返しは 3 回?
  • 基数が 16 だと FF に 1 を加える形? なら繰り返しは 3 回?

桁が上がる可能性も基数が増えれば減るな。これって計算量は n log n ? ってか、加減算に限って言えば基数が小さくなればなるほど、値の大きさに計算量が左右されるのか。
あるいは、mul という手続きで言えば 0 でない桁の数にも依存するし、この場合は基数の値が大きければ繰り返しの回数が増える可能性も増える?
ええと、外側のループは桁数依存で、内側のループは基数と car 要素の大きさ依存か。

次の問題

_それぞれの実装を批判的に分析せい_との事。その後に続く_To what extent do they succeed or fail in satisfying the specification of the data type?_なナニが微妙。