自分が書いているプログラムが正しく動くと信じてプログラムを書く感覚

次のような記事が話題になっていたんだけど、少し感じるところがあったのでメモっとく。ただの自分の感覚なので、結論とかは特にない。

『難しいプログラムでは自分がいままで書いたコードが正しく動くと信じて残りのコードを書く必要がある -- Medium』

多分この元記事の方は複雑なプログラムのことについて言っていて、俺の考えてるような単純な例ではなかろうと思うんだけど、自分の場合は結構単純なプログラムであっても再帰が関わってくるとそう感じる場合がある。単純にループにできそうにないやつ（本質的に再帰的なやつ）とか。

例えば Scheme でリストの長さを返す関数 length は次のように定義できる。

(define (length lst)
 (if (null? lst)
     0
     (+ 1 (length (cdr lst)))))

これも実際には再帰呼出しのlengthを書くところではlengthが正しく動くことを信じて書いてるわけではあるけど、再帰呼出しのlengthが最後に出てくるので（末尾再帰という意味ではなくて記述上の順番として）、これまで書いた部分が正しいという確信を得やすいのもあって、あんまり「 length が正しく動くかどうかわかんないけど正しく動くと信じて書く」って感覚はない。（単純すぎるってのもあるかもしれんが）

次に、「同じくリストの長さを返す関数、ただしリストの最後から連続した偶数要素の部分がある場合その長さはカウントしない」という関数 length2 を考えてみる。

例えば

(length2 '(1 2 3 4 5)) => 5
(length2 '(1 2 3 4 5 6)) => 5
(length2 '(1 2 3 4 5 6 6 6)) => 5
(length2 '(1 2 3 4 5 6 6 6 7)) => 9

のような感じだ。

length2 を再帰で書くとこうなる:

(define (length2 lst)
 (if (null? lst)
     0
     (let ((rest (length2 (cdr lst))))
       (if (and (zero? rest)
                (even? (car lst)))
           0
           (+ 1 rest)))))

# リストの要素が数字じゃない場合とかの処理は本質じゃないので割愛

こういう場合に (let ((rest (length2 (cdr lst)))) の部分を書くときは、「length2はまだ完成してないんだけど、これから書く部分も含めて全部正しく動くはずだぜ」という感覚を強く感じながら書いてる。

まぁlength2も蓄積変数を1個余分に導入するだけで簡単にループにできそうですけどね。