第九回
「リストの追加」

前回は Felleisen の C オペレータを実装しました。
が、リストがないとあまり面白いプログラムが動かせませんねー
ということで、ちょっと横道にそれますがリストも実装します。

リストを実装って具体的に何するの？というと、
:: と、パターンマッチを実装します。
パターンマッチって大変そう、と思うかもしれませんが、
機能を限定したパターンマッチであればさほど難しくはありません。
今回は結構簡単です！

まずは、構文に Empty と Cons(first, rest) を加えましょう。
例えば 1 :: 2 :: [] は

Cons(Number 1, Cons(Number 2, Empty))

と書き表すようにします。
もちろん[1; 2; 3]のように書きたいわけですが、それは lexer/parser で処理します。
つまり、[1; 2; 3]のような入力が来たら、parser の中でそれを
Cons(Number 1, Cons(Number 2, Cons(Number 3, Empty)))
に変換して返すようにします。

また、リストの構文に対応して、value_t にも VEmpty と VCons(first, rest)を加えます。
で、Empty や Cons(..., ...) が来たら VEmpty, VCons(..., ...)を返すようにします。

あとはパターンマッチです。

match lst with
  [] -> A
| a :: rest -> B

という構文を Match(lst, A, a, rest, B) と表すことにします。
OCaml ではもっと複雑なパターンマッチを書く事が出来ますが、
ここでは簡単のために match 文と言ったら上の形のようなもののみ受け付けることにします。
ここで lst, A, B は任意の式ですが、 a と rest は B の中で使える変数名（文字列）です。

インタプリタでは、この Match を受け取ったら、まず lst を評価し、
その値が VEmpty だったら A を実行、VCont(p, q) だったら B を、
「変数 a の値が p で、変数 rest の値が q である」という情報を付け加えた環境で実行します。

=========================================================
問題（質問、相談可）
リストを実装せよ。いろいろな例で動いていることを確認せよ。
=========================================================

なお、今回は match 文を導入する方法を示しましたが、
リストの先頭部分と残り部分を取ってくる関数 head, tail を実装するという方法もあります。
その場合、パターンマッチをするためには match 文のかわりに以下のように書きます。

if lst = empty
then A
else let a = head lst in
      let rest = tail lst in
      B