補足 (リスト構造)

S-expression

S 式というのは、symbolic expressions の略です。

quote 関連情報

R5RS 情報はこちら

各種の equal

Scheme には、 eqv?, eq?, equal? と各種の同一性判定の命令が提供されています。 詳しくは、 こちら(R5RS)を 見て下さい。

基本的には、eqv? も eq? も equal? も、両者が同じ型でないと #f を返します。 また、数や boolean や symbolに対しては、 同じ値の時 #t を返します。 eq?,eqv? が、equal? と大きく異なる点は、前者がリスト構造 などについて、同じ object を指している場合のみ #t を返すのに対して、 後者は、構造が同じであれば #t を返す点です。

backquote (quasiquote)

quote は、次にくる式の中身を一切評価してくれませんが、評価して欲しいところを 指定できるものもあります。` です。 , (comma) をつけることで`を付けられた式のなかで、 評価して欲しい式の部分をそれぞれ指定します。

> `((+ 1 2) ,(+ 1 2) (+ 1 2))
((+ 1 2) 3 (+ 1 2))

実は、 list と ' をつかえば同じことが出来ます。 どちらを指定するかの違いだけです。

> (list '(+ 1 2) (+ 1 2) '(+ 1 2))
((+ 1 2) 3 (+ 1 2))

R5RS 情報はこちら

cons, car, cdr

参考文献[3]pp76などによると、 cons は constructor の、car は contents of address (portion of) register、 cdr は contents of decrement (portion of) register の略だそうです。

ちなみに、cdr は "could-er" と発音するそうです。 cadr や caddr や cdar をどう発音するのか知っている人は僕に教えて下さい。

リスト構造にまつわる関数の定義

詳しくは R4RSの記述 を見て下さい。

代入のない場合の効用

例えば、以下のプログラムを見てみましょう(let は次回以降に説明)。

(let ((x '(#t (1 2))))
  (let ((p (do-something x)))
    (if (car x)
        3
        p)))

まず、x にリストを作り、さらに良く知らない関数 do-something を呼んでいます。 もし、仮に変数、リスト構造への代入が一切ない世界であれば、 このプログラムを以下のように変更しても式の値は変わらないことになります *。

(let ((x '(#t (1 2))))         ; x が 変わらないことを利用
  (let ((p (do-something x)))
    (if #t 
        3
        p)))
==>                          ; (if 文を簡略) 
(let ((x '(#t (1 2))))
  (let ((p (do-something x)))
     3))
==>                          ; (do-something x) が外界に影響を与えることはない*。
(let ((x '(#t (1 2)))) 3)
==>                          ; x 使う人がいなくなった。
 3

実は、Scheme においては代入はありますのでこのような事はできませんが、 関数型の性質としては、このような効果が期待できることになります。

*: 但し、値があればの話ですが。 つまり、 do-something が無限ループなどで停止しない場合は、 式変換によって動かないプログラムが動くようになってしまいます。

データ抽象

この課題では、データ型について、その内部表現や内部表現にまつわる関数群と、 そのデータ型の意味に関する演算群を切り離して考えています。 このような、考え方はデザインの仕方を データ抽象(Data Abstraction)をおこっているといいます。

また、内部表現や内部表現にまつわる関数群を一体として定義されたデータ型を 抽象データ型(Abstract Data Type) といいます。データ抽象を行っていると言うのは、抽象データ型を定義しているとも言えます。