Parenist養成ゼミ: リスト
この記事は、Parenist養成ゼミシリーズの記事である。
今回は、Parenにおけるlistは、式とデータの2面性があることを理解することを目標とした。
課題をこなすことにより、macroによる可能性を垣間見ることができる。
list
listはParenが評価する式である一方、Parenが扱うことのできるデータでもある。
データであるということはプログラムによって操作ができることを意味する。この2面性により「プログラムを書くプログラムを書く」ことが容易となる。
式としてのlistは、括弧で括られた零個以上の式であった。
データとしてのlistは、nil終端しているcons cell全体のことをいう。
cons
cons cellは関数consによって作成できる。
) (cons 1 nil)
(1)
) (cons 2 (cons 1 nil))
(2 1)
) (cons (cons 3 nil) (cons 2 (cons 1 nil)))
((3) 2 1)
あらゆるlistは高々有限回のconsの呼び出しによって作成することができるが、式としてのlistと(少なくとも、新米lisperには)直感的に異なっているかもしれない。
関数listはより直感的に使用できる。
) (list 1)
(1)
) (list 2 1)
(2 1)
) (list (list 3) 2 1)
((3) 2 1)
special operator quoteは、引数を評価せずに返す。これにより、さらに直感的にlistの作成ができる。
) (quote (1))
(1)
) (quote (2 1))
(2 1)
) (quote (3) 2 1))
((3) 2 1)
quoteは、その使用頻度から、構文等が用意されている。'の直後の式はquote呼び出しと同じになる。
(quote expr) <=> 'expr
したがって、先の例は以下のようになる。
) '(1)
(1)
) '(2 1)
(2 1)
) '((3) 2 1)
((3) 2 1)
car, cdr
listの要素を取得するために関数car, cdrがある。carはlistの最初の要素を返し、cdrはlistの最初の要素を除いたものを返す。
) (.. 3)
(0 1 2)
) (car (.. 3))
0
) (cdr (.. 3))
(1 2)
これらは利便性のために、引数がnilだった場合はnilを返すように定義されている。
) (car nil)
nil
) (cdr nil)
nil
定義により、あらゆる空ではないlist xに対して以下の等式が成り立つことを意味する。
x <=> (cons (car x) (cdr x))
) (cons (car (.. 3)) (cdr (.. 3)))
(0 1 2)
課題
- 付録のファイル
list.pを作成せよ。 - 評価されると
(1 (2) 3)を返す式を3種類考案し、i番目の式をグローバル変数$expriに代入せよ。 i番目の要素が$expriであるような長さ3のlistをグローバル変数$exprsに代入せよ。- 引数を1つ受け取り、listの2番目の要素を返すような関数
secondを実装せよ。ただし、listの長さが2未満の場合はnilを返すこと。 - 引数を1つ受け取り、1番目と2番目の要素を除いたlistを返す関数
after-secondを実装せよ。ただし、listの長さが3未満の場合はnilを返すこと。 - 長さが3のlistを1つ受け取り、要素の順番を2, 1, 3番目の順序に入れ替える関数
->polish-notationを実装せよ。 - 関数
->polish-notationの返り値が評価可能な式となり、その評価結果が6となるような引数を1つ考案し、グローバル変数$infix-notationに代入せよ。
実行例
$ paren list
) $expr1
(1 (2) 3)
) $expr2
(1 (2) 3)
) $expr3
(1 (2) 3)
) $exprs
((1 (2) 3) (1 (2) 3) (1 (2) 3))
) (second $expr1)
(2)
) (after-second $expr2)
(3)
) (->polish-notation $expr3)
((2) 1 3)
) (eval (->polish-notation $infix-notation))
6
付録
list.p
(<- $expr1 '???
$expr2 '???
$expr3 '???
$exprs '???)
(function second (x) '???)
(function after-second (x) '???)
(<- $infix-notation '???)
(function ->polish-notation (x) '???)
(function! main (args)
(repl))