Schemeによる記号処理入門#1

atom

• 英字の集合 {A,..,Z,a,..,z} 特殊文字の集合 {+,-,*,/} 数値の集合 {0,..,9} より 数値以外の文字で始まる文字列と整数からなる集合を atom とする。以下は atom である
  • abc, **, xyz, 2007, AKB48

S式

• atom と () は S式である
• s1 と s2 が S式ならば (s1 . s2) は S式である。(s1 . s2) を ドット対(dotted pair) あるいは 点対と呼ぶ
• () は 空リスト(null list)と呼ばれ nil と書くこともある
• . の 前後には ( や ) あるいは 一個以上の 空白を含めることとする
• s1 を car部(car field) あるいは car(カー) ,s2 を cdr部(cdr field) あるいは cdr(クダー) と呼ぶ
• 以下は S式である
  • A, (A, ()), (a . b), (1 . (2 . 3))
    • (1 . (2 . 3)) は 1 が car部 (2 . 3) が cdr部 である

リストとリスト記法

• si を S式 としたとき (s1 . (s2 . (s3 … . (sn . sn+1) … ))) を (s1 s2 s3 … sn . sn+1) と略記する。つまり .( ) を 一つの空白に置き換える。 最後の要素 sn+1が () あるいは nil である場合　(s1 s2 s3 … sn) と書ける