OCamlで48 Hour Schemeをやってみる その1 (第一章〜第三章前半まで)
こういうことを言ってしまった:
これは宗教勧誘とかじゃなくて真面目に言うんですが、Lisp(処理系)ってある程度書けるようになるまでの学習コストがとても(?)低い。 https://t.co/OQPte4lm4I
— zehnpaard (@zehnpaard) June 14, 2019
発言に責任を持つためにもOCamlでLisp処理系を実装してみようと思う。
幸いHaskellで簡単なLisp処理系を実装するためのチュートリアルが存在する:
昔Haskellを触っていた時に試して大変面白かった。これをOCamlに移植してみる。
第一章
まずは第一章でとりあえずテキストを表示できるプロジェクトを作ってコンパイルするところまで:
あまりコメントするべきことはない。ビルドツールに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式を返すようにする。
この段階ではパースした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")
第三章前半
パースした式を文字列として出力し直せるようにする。
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))
続く
今週末中に全部実装して記事にできたらいいな・・・ (続き)