composition calculus

あなごるに出てた composition calculus が面白そうで，真面目にインタプリタを書いてみたくなったので OCaml で実装してみた。所要時間は Stream のインタフェースを思い出すところから始めて全部で一時間くらい。

type token = char
type expr = Atom of token | App of expr * expr
let dot = Atom '.'

let rec read_token stream =
  let c = Stream.next stream in
    if c = ' ' then read_token stream else c

let tokenize_string string =
  let rec loop s a =
    if Stream.peek s = None
    then List.rev_map (fun t -> Atom t) a
    else loop s (read_token s :: a)
  in loop (Stream.of_string string) []

let parse string =
  match tokenize_string string with
    | t::tks -> List.fold_left (fun x y -> App (x, y)) t tks
    | [] -> failwith "invalid input"

let rec eval = function
  | Atom _ as e -> e
  | App(e, e') ->
      let f = eval e in
      let a = eval e' in
        match f with
          | App(App(f, e0), e1) when f = dot -> eval (App(e0, App(e1, a)))
          | _ -> App(f, a)

let rec string_of_expr = function
  | Atom c -> String.make 1 c
  | App(e, e') -> "(" ^ string_of_expr e ^ " " ^ string_of_expr e' ^ ")"

let rec doit () =
  try
    let string = read_line () in
      print_endline (string_of_expr (eval (parse string)));
      doit ()
  with End_of_file -> ()

let _ = doit ()

値の型を式とは区別するようにしたり，dot が fully applied じゃないまま残る場合も考慮したり，CPS 変換したり，あるいは機能を追加してみたり，などなどをやればまだいろいろ楽しめるんじゃないかと。今度やるかも。