リストとツリー

今、無謀にも、なんちゃってSchemeをC#で実装しようと試みているところ。
まだ字句解析器しかできてないけど。ヽ(´Д`；)ノ ｱｩｱ

切り出したトークンの並びをチェックしつつ、リストを構成するのは今から。
構文解析器って言うのかな？
マクロはまだ自分が理解できていないのでガン無視でやっていきます。
それだけに、構文解析は簡単そうだな。

で、リストを表現するデータ構造作ってて、あぁ、こりゃ木構造じゃねーかよ、と。
（むしろ今更気づくなよ、っていう突っ込みは全力でスルーしますよ。うるせーうるせー！）
以前、id:yagiey:20090121:1232504281でチラッと言ったけど、リストをドット対の形で書いてみると、木構造が際立って見える。
たとえば、

(foo bar baz qux)

は

(foo . (bar . (baz . (qux . ()))))

のことで、car部とcdr部が子ノードになってるし。
アトムが葉になるわけですな。

初めてcdrを触ったとき、

(cdr '(foo bar))

の結果が

bar

じゃなくて

(bar)

になることが直感的でないように感じた。
はじめからリストをドット対の再帰的構造として意識していれば、そんなことはなかったのかも。

ということで、リストさえできてしまえば、あとはThe Little Schemerの10章、手続きvalue（id:yagiey:20081105以降）を参考にやっていけるのかな。