めざそう言語処理系の沼 〜shift/resetへの旅 〜 その１０ Consとリスト

今回は言語で簡単なデータ構造を扱えるようにする。具体的にはイミュータブルなconsセル（とnil値）を導入して、linked listを作れるようにする。

ついでにLisperならお馴染みのcar、cdrやリストを便利に作れる・使えるlist、applyなども定義する。

こんな感じで使える：

(let [x (cons 1 2)]
  (+ (car x) (cdr x)))

(apply + (list 1 2 3 4 5))

前回との差分：

Comparing v0.9...v0.10 · zehnpaard/kontlang · GitHub

テスト以外で変更したのはValとBuiltinsだけ。パーサも評価器も変更なし。

まずValモジュールにConsと`Nilを追加：

type t =
| Nil
...
| Cons of t * t

Val.Consは要素２のタプル。Val.Nilは今後副作用ありの計算の結果に使ったりもする予定だが、ここではリストの終端を表すようにしている。

つまり

(cons 1 (cons 2 (cons 3 nil)))

が[1 2 3]というリストとしてみなされる。

ちなみに

(cons 1 (cons 2 (cons 3 4)))

と終端がnilでない場合、dotted listといって[1 2 3 . 4]のように表記される。

ある値が（nilで終わっている）リストか確認する関数is_list：

let rec is_list = function
| Nil -> true
| Cons(_, x) -> is_list x
| _ -> false

や、list、dotted_listをOCamlのリストやリストとVal.tのタプルに変換するヘルパー関数：

let rec cons_to_list = function
| Nil -> []
| Cons(x, xs) -> x::(cons_to_list xs)
| _ -> failwith "Converting non-cons-list into arg list"

let rec cons_to_dotted_list acc = function
| Nil -> failwith "Dotted list cannot end with nil"
| Cons(x, xs) -> cons_to_dotted_list (x::acc) xs
| v -> (List.rev acc, v)

なども追加してある。

Builtinsモジュールに追加された組込関数など：

let builtins =
[
...
; "nil", Val.Nil
; "cons", Val.Op("cons", cons_op)
; "car", Val.Op("car", car_op)
; "cdr", Val.Op("cdr", cdr_op)
; "list", Val.Op("list", list_op)
; "apply", Val.Op("apply", apply_op)
; "nil?", Val.Op("nil?", nilp_op)
; "cons?", Val.Op("cons?", consp_op)
]

nilやconsも予約語ではなく、ただの変数。

cons、car、cdrの定義：

let cons_op = function
  | [x; y] -> Val.Cons(x, y)
  | xs -> failwith @@ Printf.sprintf "Cons applied to %d args" (List.length xs)

let car_op = function
  | [Val.Cons(x, _)] -> x
  | _ -> failwith "Non-cons passed to car"

let cdr_op = function
  | [Val.Cons(_, y)] -> y
  | _ -> failwith "Non-cons passed to cdr"

パターンマッチで、consの場合引数が２つでない場合、carやcdrの場合引数が１つのVal.Consでない場合はエラーとなる。

listとapplyの定義：

let rec list_op = function
  | [] -> Val.Nil
  | x::xs' -> Val.Cons(x, list_op xs')

let apply_op = function
  | [Val.Op(_, op); Val.Cons _ as cons] -> op @@ Val.cons_to_list cons
  | _ -> failwith "Incorrect args passed to apply"

listは引数のリストを再帰的に(cons x (cons y (... nil) ...))の形に変換する。

applyは第一引数の関数を第二引数のリストに適用する、のだがその時「ソース言語のリスト」を「OCamlのリスト」に変換している。なので

(apply + (list 1 2 3 4))

(+ 1 2 3 4)

が同じ結果となる。

あとはnilやconsかどうかを調べる述語：

let nilp_op = function
  | [Val.Nil] -> Val.Bool true
  | [_] -> Val.Bool false
  | _ -> failwith "nil? called with invalid number of args"

let consp_op = function
  | [Val.Cons _] -> Val.Bool true
  | [_] -> Val.Bool false
  | _ -> failwith "cons? called with invalid number of args"

引数が１つ出なければエラー。１つの場合、cons?は引数がVal.Consなら真、それ以外は偽。nil?は引数がVal.Nilなら真、それ以外は偽。

以上で実装完了。

これでmapやfilterが書ける！と思ったのだが、ifだけだと少し書きにくいのでcondを追加して場合分けで分岐できるようにしたい。

というわけで次回はcondの話。