carとcdrとcons

学生のときに受けた講義に「プログラミング」がありました。「プログラミングI」「同II」「同III」と半期の科目が3つあり、それぞれ「基本のC言語」「色々経験するために、関数型言語LISP)・論理型言語(Prolog)・並列並行処理(AEGISという言語だったような?)」「(だいぶ昔のことなので)今後はオブジェクト指向プログラミングが主流になるからJava」というようになっていた気がします。

「プログラミングII」で関数型言語に触れる部分ではLISPを習いました。いま思えばML)とかでも良かったかと思いますが、当時はLISPは実用性のあるメジャーな言語という雰囲気だったのかもしれません。歴史的にも勉強しておいた方がいい言語の一つですしね。

LISPで最初につまづいたのがリスト操作です。いまから思い返すとなぜ理解できないのか分からない、なんて気がしますが、当時はcar、cdr、consでのリスト操作に違和感があり、何が何だか分かりませんでした。おそらくcar+cdrとconsが対称な操作であることが分かっていなかったのではないかと思います。

たとえば

(car '(1 2 3))   -> 1
(cdr '(1 2 3))   -> (2 3)
(cons 1 '(2 3))   -> (1 2 3)

について、carはリストの最初の要素をとってくる、cdrはリストの残りをリストとして得る、consは引数2の先頭に引数1を挿入するという動作をするので、図解すると以下のような印象でした。

f:id:amarui:20191006112409p:plain

この簡単なことが当時の僕にはよく分からず、

(cons '(1 2) '(3 4))   -> (1 2 3 4)

を期待しているのに

(cons '(1 2) '(3 4))   -> ((1 2) 3 4)

となるので「先頭に値を入れてくれるのではないのか?」などと混乱していました。同じ頃にMatlabも使い始めていたので、

>> A = [1 2];
>> B = [3 4];
>> [A B]
ans =
     1     2     3     4

と同じような動作を期待していたのだと思います。

LISPに触れるのは半期の授業の1/3だけなので4回程度。話題はあっという間に他の言語に移ってしまったので「論理型言語おもしろいけど、家系図つくって実用性あるのか?」だの「並列・並行は意味が分からない、円卓の哲学者は馬鹿か?」などと言い始め、期末試験が終わるとそれら全てを忘れてしまい、卒業までずっとC言語を使っていました。

その後、何年も経ってからLISPに再入門すると、car+cdrとconsの見え方が変わっていました。値やリストを抽出・挿入という考え方から、括弧の位置が動くという考え方になりました。図解すると以下のような感じです。

f:id:amarui:20191006114038p:plain

carやcdrは括弧が1つ右に動く感覚です。たとえば(car '(1 2 3))(1 2 3)の先頭の括弧が1 (2 3)と1つぶん右に移動し、そのときに括弧外に出たものがcarで、括弧内に残っているものがcdrです。一方でconsは括弧が1つ左に動く感覚です。リストは1つのまとまりなので、(cons '(1 2) '(3 4))をすると、(3 4)の先頭の括弧が(1 2)のまとまりを超えて左側に動き((1 2) 3 4)となるのでした。

結局、(1 2)(3 4)から僕が期待したとおりの(1 2 3 4)を作るためには、(1 2)の各要素を取り出しつつconsを使い

(cons (car '(1 2)) (cons (car (cdr '(1 2))) '(3 4)))   -> (1 2 3 4)

とすることになります。(これをするために(append '(1 2) '(3 4))が用意されています)