Arantium Maestum

プログラミング、囲碁、読書の話題

OCamlで48 Hour Schemeをやってみる　その５　（第九、十章）

OCaml 言語処理系

Write Yourself a Scheme in 48 Hoursの最後の二章をやっていく。入出力と標準ライブラリ作成。

第九章：入出力

stdin, stdoutやファイルに対する入出力を実装する。

github.com

例によって「Haskellだとモナドが出現していろいろ型を頑張らないといけないけどOCamlだから・・・」という案件。

HaskellではIOモナド型のために新しいIOFunc式を用意したりしているが、OCamlだと普通に今まで通りPrimitiveFuncに放り込んでいける。

type expt = (* 省略 *)
          | PortIn of in_channel
          | PortOut of out_channel

と入出力用のchannelをラップしたPortIn/PortOut式は用意する。あとはIoモジュールでそれを使う関数を定義し、primitives.mlで環境に追加するよう変更するだけ：

let load env =
  let add v e env = (Env.define_var env v (PrimitiveFunc e) |> ignore; env) in
  env
  (* 省略 *)
  |> add "open-input-file" Io.make_port_in
  |> add "open-output-file" Io.make_port_out
  |> add "close-input-file" Io.close_port_in
  |> add "close-output-file" Io.close_port_out
  |> add "read" Io.read_proc
  |> add "write" Io.write_proc
  |> add "read-contents" Io.read_contents
  |> add "read-all" Io.read_all

とくに面白いのはloadで、ファイルからS式を複数読み込んで順次評価する。

let read_exp s = Lexing.from_string s |> Parser.f Lexer.f
let read_exps s = Printf.sprintf "(%s)" s |> read_exp

(* 省略 *)

let read fn =
  let inf = open_in fn in
  let rec read' acc = match input_line inf with
    | s -> read' (s :: acc)
    | exception End_of_file -> List.rev acc |> String.concat "\n"
  in
  read' []

(* 省略 *)

let read_all = function
  | [String filename] -> read filename |> read_exps
  | _ -> raise @@ Exception.TypeMismatch ("string", "")

let load s = match read_all [String s] with
  | List xs -> xs
  | _ -> raise @@ Exception.Default "read-all returned non-list"

これはEval.fを使う必要があるのでprimitiveな関数ではなくspecial formとしてEvalモジュール内で実装している：

let rec f env e = match e with
  (* 省略 *)
  | List [Atom "load"; String filename] ->
      Io.load filename |> List.map (f env) |> List.rev |> List.hd
  (* 省略 *)

これを使って別ファイルに定義した標準ライブラリを読み込めるようになる。

第十章：標準ライブラリ

というわけで実装する機能がでる最後の章に到達（実際にはもう一つ、まとめ的な章がある）。

標準ライブラリをstd.scmというファイルに書き込み、前回定義したload special formで読み込んで使う、という流れになる。

github.com

std.scmの定義自体は（変数名をいくつかいじった以外では）Haskell版とまったく同じ。foldl、foldr、map、filterなどおなじみの関数を定義していく。

これらを定義するにあたって関数、クロージャ、そして変数環境全体の実装が間違っていることが発覚した。

変数環境を「文字列とLisp式のMap」のrefとして定義していたのだが、正しくは「文字列とLisp式refのMap」のrefであるべきだった。

実は本物のSchemeでも：

(define (f x) (set! y (+ x y)))
(define y 10)
(f 5)
y

が言語仕様上エラーにならない、というのはちゃんと理解していなかった。これだとたしかに相互再帰とかも簡単に実現できるな・・・

何はともあれfixできた。

これと同じ問題が起きていることが確認できたのでそれも修正・・・

github.com

Lexerで#tや#fを見つけてTRUE/FALSEトークンにするのではなく、普通のAtomとしてトークン化しておいて、Parserで中身をチェックしてExp.AtomにするかExp.Boolにするかを決定している。そうすれば#fはExp.Bool false、#footballはExp.Atom "#football"にパースできる。

これでようやく完了。標準ライブラリを使ってみる：

Lisp>>> (load "std.scm")
(lambda (pred xs) ...)
Lisp>>> (define xs '(1 2 3 4 5))
(1 2 3 4 5)
Lisp>>> (define ys (map (curry * 2) xs))
(2 4 6 8 10)
Lisp>>> (apply sum (filter (curry < 5) ys))
24

成功。

まとめ

とりあえず駆け足で簡易なLispを実装してみた。変数や再帰的な関数が定義でき、ファイル入出力が可能で、外部ファイルに書かれたライブラリコードを読み込んで使える、とそれなりの機能は備えている。

所感としては：

  • 言語処理系実装は楽しい
  • 言語仕様はちゃんと理解しよう
  • Haskellと比べて、これくらいの規模のプロジェクトではOCamlは型の強度がちょうどいいのでは？（Haskell実装ではかなりの部分をエラーやIO関連モナドへと型を書き換える話が占めていた）
  • かかった時間は実装とバグ修正合わせて１０時間ほどだろうか？（昔一回Haskellでやったことがあったのと、最近小規模な言語処理系実装をいくつかやっていたのが大きい）
  • マクロと継続が実装したい（Lisp in Small Piecesやっていくかな・・・）

というのが法螺ではないことを示せたんじゃないかと思うので、よかったよかった。