print

dot記法

一般的にlispでは「（）」やspaceで区切られたアトムやリストでプログラムやデータを表現するのですが，コンスセルの内容を忠実に表現した記法としてdot記法というのがあります。アトムについては変わりませんが，リストについては「(car部 . cdr部)」と表現するんですね。car部とcdr部を「 . 」（space dot spaceの３文字）で連結して全体を「()」でくくる。car部やcdr部もそれ自体アトムかリストなんだから同じように適用して……。まさに再帰ですな。
例えば「(A B C)」というリスト。これは図解すると

＋－－－＋－－－＋　　＋－－－＋－－－＋　　＋－－－＋－－－＋
｜　・　｜　・－＋－→｜　・　｜　・－＋－→｜　・　｜ nil  ｜
＋－＋－＋－－－＋　　＋－＋－＋－－－＋　　＋－＋－＋－－－＋
　　↓　　　　　　　　　　↓　　　　　　　　　　↓
　　Ａ　　　　　　　　　　Ｂ　　　　　　　　　　Ｃ

となるのですが，これを
（Ａ　．　（Ｂ　．　（Ｃ　．　nil）　）　）
と表現するのがdot記法なのです。
コンスセルの状況がまるわかりですね。
ところが，これは実際にはあまり使われません。ただでさえ「（）が多すぎる」と言われるlispで，さらに（）が増えるのを嫌う人の方が多いのです。普通は，
（Ａ　Ｂ　Ｃ）
と書きます。

＋－－－＋－－－＋　　＋－－－＋－－－＋
｜　・　｜　・－＋－→｜　・　｜　・　｜
＋－＋－＋－－－＋　　＋－＋－＋－＋－＋
　　↓　　　　　　　　　　↓　　　↓
　　Ａ　　　　　　　　　　Ｂ　　　Ｃ

のように，cdrにアトムが来るものはdot記法を使わざるを得ないので，
（Ａ　Ｂ　．　Ｃ）
と記述します。

dot記法のprintは簡単だけど……

アトムかどうか判断する関数をatomp(x)（真ならT，偽ならNILを返す），アトムを印字する関数をatomprint(x)，car部を取り出す関数をcar(x)，cdr部を取り出す関数をcdr(x)とすると

int print(x)
{
	if (atomp(x) == T){
		atomprint(x);
	}else{
		printf("(");
		print(car(x));
		printf(" . ");
		print(car(x));
		printf(")");
	}
	return;
}

ですんじゃいます。再帰万歳。

ところが普通の記法だとこうは簡単にはいかない

ところが普通の記法だとこうは簡単にいきません。
まずネックになるのが区切り符号としての空白（space）の存在です。
小数点としても「.」を使うことから，dot記法としての「.」の前後に必ず空白を置くことにすると，区切り符号を意識する必要がありません。
ところが，通常の記法だと(AB)と(A B)とは意味が異なりますから，複数のアトムが並んだ時には必ず空白を置く必要があります。一方((A)B)のような場合には，()が区切り符号となりますので空白を置く必要がありません。したがって複数のアトムが()なしに並ぶ場合か否かを区別して必要な時だけ空白を置くという処理が必要になります。
これについては，空白が必要な場合というのが，「car部がアトム」「cdr部がリスト」「cdr部の先のセルのcar部がアトム」の三条件を全て満たした時であることから，そのチェックをして空白を置くかどうかを決めています。
もう１つは，(と)の数を同じにしなければならないという要請です。dot記法では「(」「car部」「 . 」「cdr部」「)」の順に印字し，car部，cdr部自身も同様に（アトムか）「(」「car部」「 . 」「cdr部」「)」の順に印字すると決まっているため，()の数のバランスに気をつける必要がありません。しかし，通常の記法では，たとえば

＋－－－＋－－－＋　　＋－－－＋－－－＋　　＋－－－＋－－－＋
｜　・　｜　・－＋－→｜　・　｜　・－＋－→｜　・　｜ nil  ｜
＋－＋－＋－－－＋　　＋－＋－＋－－－＋　　＋－＋－＋－－－＋
　　↓　　　　　　　　　　↓　　　　　　　　　　↓
　　Ａ　　　　　　　　　　Ｂ　　　　　　　　　　Ｃ

を例にすると一番右のセルだけ印字する時には「(C)」となるのに対し，真ん中のセルから印字をスタートさせると，「(B C)」となります。空白を置くかどうかの判断をすると同時に(C)の(を印字しないという処理が必要となります。
現在はあまり格好はよくないのですが，
・トップレベルとその下のレベルとを分ける
・それぞれのレベル内でcarの印字とcdrの印字とを分ける
・printを再帰として呼び出すのではなく，carの印字やcdrの印字，さらにはレベルごとの関数を再帰的呼び出す
という方針で書いてなんとか実現しています。
しかし，トップレベルとその下のレベルを分ける必然性はないので，アルゴリズムをきちんと検討することで，もっと単純に書けるのではないかと思っています。
carの印字とcdrの印字とを分けるのは正解っぽい気がしていますが。
System Lufimia 作業状況報告書　へ