EoPL reading (50) 2.1 Specifying Data via Interfaces

もう 50 か。

Exercise.2-2

ええと、提示されたそれぞれの実装を批判的に分析せよ、それらがデータ型の仕様を満足させるか否かの範囲は何か、という理解で良いのかな。

まず Unary representaion から

これは大きい値の表現が微妙。length で簡単に値が取れますが、例えば 1000 とかもう一桁上の数値とか、値を取得するだけで O(n) なのは微妙。
# いちいち指で数えてる的?
あと、plus をトレイスしてみる。

(plus '(#t #t) '(#t #t #t))

(succ (plus (pred '(#t #t)) '(#t #t #t)))

(succ (plus '(#t) '(#t #t #t)))

(succ (succ (plus (pred '(#t))  '(#t #t #t))))

(succ (succ (plus '() '(#t #t #t))))

(succ (succ '(#t #t #t)))

(succ '(#t #t #t #t))

'(#t #t #t #t #t)

append の実装ってどうなってるんだろ。と言いつつ gauche の実装が以下。

#define SCM_APPEND1(start, last, obj)                           \
    do {                                                        \
        if (SCM_NULLP(start)) {                                 \
            (start) = (last) = Scm_Cons((obj), SCM_NIL);        \
        } else {                                                \
            SCM_SET_CDR((last), Scm_Cons((obj), SCM_NIL));      \
            (last) = SCM_CDR(last);                             \
        }                                                       \
    } while (0)

#define SCM_APPEND(start, last, obj)                    \
    do {                                                \
        ScmObj list_SCM_GLS = (obj);                    \
        if (SCM_NULLP(start)) {                         \
            (start) = (list_SCM_GLS);                   \
            if (!SCM_NULLP(list_SCM_GLS)) {             \
                (last) = Scm_LastPair(list_SCM_GLS);    \
            }                                           \
        } else {                                        \
            SCM_SET_CDR((last), (list_SCM_GLS));        \
            (last) = Scm_LastPair(last);                \
        }                                               \
    } while (0)

この実装だと単純に append した方が早いな。あとこの形は負の値の表現は絶対に不可能ですね。

Scheme number repressntation

これも plus は + で良い。一応負の数値を表現することは可能か。gauche 的には加算の実装って繰り返しにはなってないはず。
もう少し検討必要ってコトで、ここでエントリ投入します。