OCamlで48 Hour Schemeをやってみる その１ （第一章〜第三章前半まで）

こういうことを言ってしまった：

これは宗教勧誘とかじゃなくて真面目に言うんですが、Lisp(処理系)ってある程度書けるようになるまでの学習コストがとても(？)低い。 https://t.co/OQPte4lm4I

— zehnpaard (@zehnpaard) June 14, 2019

発言に責任を持つためにもOCamlでLisp処理系を実装してみようと思う。

幸いHaskellで簡単なLisp処理系を実装するためのチュートリアルが存在する：

en.wikibooks.org

昔Haskellを触っていた時に試して大変面白かった。これをOCamlに移植してみる。

第一章

まずは第一章でとりあえずテキストを表示できるプロジェクトを作ってコンパイルするところまで：

github.com

あまりコメントするべきことはない。ビルドツールにduneを使っているのでdune exec bin/ex.bcなどとするとbin/ex.mlのコードが実行される。

第二章

第二章ではParserを作る。ようやくLisp的なものが出てくる。

type t = Atom of string
       | List of t list
       | DottedList of t list * t
       | Number of int
       | String of string
       | Bool of bool

こんな感じのLisp式のASTを表す型を定義して、ocamllex製のlexer、menhir製のparserでそのLisp式を返すようにする。

github.com

この段階ではパースしたLisp式はignoreするだけ。ちゃんとパースされるかどうかは確認できる。

> echo "(+ 1 2 '(3 4))" | dune exec bin/ex.bc

> echo "(+ 1 2a)" | dune exec bin/ex.bc
Fatal error: exception Failure("Atoms cannot start with a digit")

第三章前半

パースした式を文字列として出力し直せるようにする。

github.com

ExpモジュールにLisp式型を文字列に変換するto_string関数を追加する：

let rec to_string = function
  | Atom a -> a
  | List es ->
      let s = List.map to_string es |> String.concat " " in
      Printf.sprintf "(%s)" s
  | DottedList (es, e) ->
      let s = List.map to_string es |> String.concat " " in
      Printf.sprintf "(%s . %s)" s (to_string e)
  | Number n -> string_of_int n
  | String s -> "\"" ^ s ^ "\""
  | Bool b -> string_of_bool b

その関数をbin/ex.mlで使ってパースした式を文字列に変換して出力する：

let _ =
  Lexing.from_channel stdin
  |> Parser.f Lexer.f
  |> Exp.to_string
  |> print_endline

使い方はこんな感じ：

> echo "1" | dune exec bin/ex.bc
1
> echo "abc" | dune exec bin/ex.bc
abc
> echo "(+ abc 1)" | dune exec bin/ex.bc 
(+ abc 1)
> echo "(+ abc 1 '(x y z))" | dune exec bin/ex.bc
(+ abc 1 (quote x y z))

続く

今週末中に全部実装して記事にできたらいいな・・・ （続き）