型推論を実装する その１ （型なしの言語を作る）
Oleg先生のサイトのhttps://t.co/7F4vsWGgr7
— zehnpaard (@zehnpaard) June 23, 2019
とhttps://t.co/ABdXWoAxcW
をちゃんと読みたいと思っている・・・ 現在外堀を埋めている段階・・・
とあるように、最近型推論や型クラスに興味があり、界隈では非常に著名なOleg先生の書いたものをなんとか読もうと考えている。（実はそれもModular Implicitsの論文をちゃんと理解するためなのだが、道は遠い・・・）
Essentials of Programming Languagesでは第七章で型推論のある言語をracketで実装するので、それをOCamlで試しつつ、具体的に何が起きているかをある程度メモっておこうと考えている。
EoPLの流れとしては * 第三章で再帰関数をサポートする純粋関数型言語LETRECを実装 * 第四章〜第六章では状態やCPSによる例外やスレッド実装など（型には直接関係なし） * 第七章ではまたLETREC言語に戻ってそこに型注釈・型検査ありのCHECKED言語、そしてCHECKEDから型注釈を省ける型推論付きのINFERRED言語を実装 となっている
なのでLETREC、CHECKED、INFERREDを見ていけば型無しから型推論への道が少しわかってくるはず。
今回はLETRECの実装をやっていく。
言語仕様
LETRECはその名の通り、再帰関数を使える言語である。かなり機能としては最低限に絞ってある。
- 正数値リテラル
- 数値間の引き算
-(x, y) - 数値のゼロチェック
zero?(x) - 分岐
if ... then ... else - 変数束縛
let x = ... in ... - 非再帰の無名関数
proc (x) ... - 再帰関数
letrec f (x) = ... in ... - 関数呼び出し
(f x)
whitespaceは無意味（Lexerが取り除く）。
サンプルプログラム：
letrec double(x) = if zero?(x) then 0 else -((double -(x, 1)), -(0, 2)) in (double 6)
これは12として評価される。
実装
パーサはocamllex/menhirで作成。この部分はとくに真新しいところはなし。（letlangについて書いた記事の内容を微調整しただけ）
以下の記事でも書いた：
純粋関数型言語でクロージャを持つ関数を実装する場合、クロージャを直接「変数環境」の型として表現してしまい、その型を含む直和型のバリアントを「関数」として値の型に追加するのが自然だと思う。しかし、変数環境自体が変数を表す文字列と、その変数の値とのマップとして表現している。というわけで変数環境の型と値の型が相互再帰になってしまうのをどう解決するか（というか相互再帰になっている型を二つのモジュールにどうわけるか）がポイント。
上記の記事の通り、Valenvモジュールを作って型を定義し、その型を使ってValとEnvモジュールを定義している。
再帰関数を実装するために変数環境に少し工夫してある：
module Env = struct type t = envt let empty = Empty let rec find env s = match env with | Empty -> None | Extend (s', v', env') -> if s = s' then Some v' else find env' s | ExtendRec (fname, arg, body, env') -> if s = fname then Some (Val.Proc (arg, body, env)) else find env' s let extend env s v = Extend (s, v, env) let extend_rec env f a b = ExtendRec (f, a, b, env) end
再帰関数を実現するために変数環境にExtendRec of string * string * Exp.t * Env.t（関数名、仮引数、関数の内容、元々の変数環境）のようなバリアントを入れ、その関数が参照されるたびに新たな関数値を作成して返している。
あまり効率のいいやり方とは言えない（EoPLでも破壊的代入を使ったより効率的な実装を演習問題として紹介している）が、まあ挙動は正しいのでよしとする。
実装の心臓部分はEvalモジュール。再帰関数eval'をパターンマッチで定義している。
まずは数値リテラルの式：
let rec eval' env = function | Exp.Const n -> Val.Num n
リテラルそのままの数値を表すValに評価される。
zero?や-(x, y)：
| Exp.ZeroP e -> (match eval' env e with | Val.Num n -> Val.Bool (n = 0) | _ -> failwith "Zero-checking non-numeric value") | Exp.Diff (e1, e2) -> (match eval' env e1, eval' env e2 with | Val.Num n1, Val.Num n2 -> Val.Num (n1 - n2) | _ -> failwith "Diffing non-numeric value(s)")
まず引数を評価し、数値Valになることを確かめてから計算して結果を返している。
条件分岐：
| Exp.If (e1, e2, e3) -> (match eval' env e1 with | Val.Bool b -> eval' env (if b then e2 else e3) | _ -> failwith "Using non-boolean if-condition")
まず条件を評価し、それを元に分岐の一方だけを評価している。
let式と束縛変数：
| Exp.Let (s1, e1, e2) -> let v1 = eval' env e1 in let env' = Env.extend env s1 v1 in eval' env' e2 | Exp.Var s -> (match Env.find env s with | Some v -> v | None -> failwith "Variable not found in environment")
letではまず束縛する値を評価し、それを変数とともに環境に加え、その拡張された環境を使ってbody部分を評価している。
変数の評価は環境から結果を探し出すだけ。
関数定義と呼び出し：
| Exp.Proc (s, e) -> Val.Proc (s, e, env) | Exp.Call (e1, e2) -> (match eval' env e1 with | Val.Proc (s, e, env') -> let v = eval' env e2 in let env'' = Env.extend env' s v in eval' env'' e | _ -> failwith "Calling non-procedure")
関数定義は評価は全くせず、ただ仮引数とbody式と現在の環境をクロージャとしてVal.Procコンストラクタに渡すだけ。
関数呼び出しでは、まず関数部分を評価し関数Valだと確かめてから、引数を評価し、クロージャに仮引数とともに追加し、それを環境としてbody式を評価する。
再帰関数：
| Exp.LetRec (fname, arg, body, e) -> eval' (Env.extend_rec env fname arg body) e
再帰関数は定義されるときは特殊なロジックがある（前述のExtendRecで変数環境を拡張する）が、関数呼び出しの際は非再帰関数と同じ扱い。
これでeval'は定義完了。あとは：
let f = eval' Env.empty
eval'に空の変数環境を与え、式だけを引数としてとる関数fを定義して終わり。
使ってみる
この言語を使ってみるために、bin/ex.mlにメイン関数的なものを用意する：
open Letreclang let f s = Lexing.from_string s |> Parser.f Lexer.f |> Eval.f |> Val.to_str |> print_endline let rec rep acc = let s = read_line () in if s = "" then f acc else rep (acc ^ "\n" ^ s) let _ = (print_string ">>> "; rep "")
これでbashなどでdune exec bin/ex.bcというコマンドを叩くと >>>というプロンプトが表示され、複数行にまたがる文字列を入力として受け取り（空行を入力の終わりとして解釈する）、パース・評価して結果を表示する。
例えば：
$ dune exec bin/ex.bc >>> letrec double(x) = if zero?(x) then 0 else -((double -(x, 1)), -(0, 2)) in (double 6) 12
これから
前述の通り、次はこの言語に型注釈と型検査を加える。
OCamlで48 Hour Schemeをやってみる その５ （第九、十章）
Write Yourself a Scheme in 48 Hoursの最後の二章をやっていく。入出力と標準ライブラリ作成。
第九章：入出力
stdin, stdoutやファイルに対する入出力を実装する。
例によって「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で読み込んで使う、という流れになる。
std.scmの定義自体は（変数名をいくつかいじった以外では）Haskell版とまったく同じ。foldl、foldr、map、filterなどおなじみの関数を定義していく。
これらを定義するにあたって関数、クロージャ、そして変数環境全体の実装が間違っていることが発覚した。
とりあえず48 Hour Lisp、最終章まで終わった。が標準ライブラリに(Lispで）定義したmember関数がなんだかバグっている・・・
— zehnpaard (@zehnpaard) June 18, 2019
おっとかなり本質的なところでバグってるな・・・
— zehnpaard (@zehnpaard) June 19, 2019
変数環境を「文字列とLisp式のMap」のrefとして定義していたのだが、正しくは「文字列とLisp式refのMap」のrefであるべきだった。
実は本物のSchemeでも：
(define (f x) (set! y (+ x y))) (define y 10) (f 5) y
が言語仕様上エラーにならない、というのはちゃんと理解していなかった。これだとたしかに相互再帰とかも簡単に実現できるな・・・
何はともあれfixできた。
falseaをfalseでパースしてしまうの、どうすればいいんだろう。
— くよくま (@hennin_ltn) June 18, 2019
これと同じ問題が起きていることが確認できたのでそれも修正・・・
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やっていくかな・・・）
これは宗教勧誘とかじゃなくて真面目に言うんですが、Lisp(処理系)ってある程度書けるようになるまでの学習コストがとても(？)低い。 https://t.co/OQPte4lm4I
— zehnpaard (@zehnpaard) June 14, 2019
というのが法螺ではないことを示せたんじゃないかと思うので、よかったよかった。
OCamlで48 Hour Schemeをやってみる その４ （第六〜八章）
前回から続いて、REPL機能を追加し、変数と関数を定義できるようにする。
第四章： REPL
REPLとはRead Eval Print Loopの略で、対話的にプログラムを入力・実行できる環境である。
この場合は
Lisp>>>
などといったプロンプトを表示してS式を受け取り、評価して結果を返した上で再度プロンプトを表示するようにする。終了のためにはquitと入力すればいい。
変更はbin/ex.mlファイルだけ。こんな感じになった：
open Lisp let f s = try Lexing.from_string s |> Parser.f Lexer.f |> Eval.f |> Exp.to_string |> print_endline with | Exception.NumArgs (n, s) -> Printf.printf "NumArgs %d %s\n" n s | Exception.TypeMismatch (s1, s2) -> Printf.printf "TypeMismatch %s %s\n" s1 s2 | Exception.LexingFail s -> Printf.printf "LexingFail %s\n" s | Exception.BadSpecialForm (s1, s2) -> Printf.printf "BadSpecialForm %s %s\n" s1 s2 | Exception.NotFunction (s1, s2) -> Printf.printf "NotFunction %s %s\n" s1 s2 | Exception.UnboundVar (s1, s2) -> Printf.printf "UnboundVar %s %s\n" s1 s2 | Exception.Default s -> Printf.printf "DefaultError %s\n" s let rec repl () = let s = (print_string "Lisp>>> "; read_line ()) in if s = "quit" then () else (f s; repl ()) let _ = repl ()
例外を投げっぱなしにしていたのをcatchして文字列として出力するようにした。こうしないとループが止まってしまう。もうすこしよさげな書き方がありそうなものだが・・・
REPL自体は再帰関数となっていて、それでループしている。
第七章： 変数
第七章では変数を定義できるようにする。
そのためには変数環境を作る必要がある。このチュートリアルでの変数はlet式によるイミュータブルなものではなく、defineやset!で破壊的代入を起こすものなので、それに合わせて変数環境もミュータブルな状態を持つデータ構造にする。とりあえずHashtblで実装してみる。
変数環境を定義するEnvモジュールはこの通り：
type t = (string, Exp.t) Hashtbl.t let create () = (Hashtbl.create 100 : t) let is_bound = Hashtbl.mem let get_var env v = match Hashtbl.find_opt env v with | Some e -> e | None -> raise @@ Exception.UnboundVar ("Getting unbound var", v) let set_var env v e = if is_bound env v then (Hashtbl.replace env v e; e) else raise @@ Exception.UnboundVar ("Setting unbound var", v) let define_var env v e = (Hashtbl.replace env v e; e)
基本的にはHashtblの関数をラップする形でEnvの関数を定義している。
次に、式評価のためのEval.fを変数環境を使うよう変更：
let rec f env e = match e with (* 省略 *) | Atom x -> Env.get_var env x (* 省略 *) | List [Atom "set!"; Atom v; e'] -> f env e' |> Env.set_var env v | List [Atom "define"; Atom v; e'] -> f env e' |> Env.define_var env v (* 省略 *)
単なるAtom xは変数xが束縛された値として評価される。set!やdefineは変数環境を変更して、束縛された値を評価結果として返す。
あとは変数環境をREPLで使えるようbin/ex.mlを変更：
let f env s = try Lexing.from_string s |> Parser.f Lexer.f |> Eval.f env |> Exp.to_string |> print_endline with (* 省略 *) let rec repl env = let s = (print_string "Lisp>>> "; read_line ()) in if s = "quit" then () else (f env s; repl env) let _ = repl (Env.create ())
fやreplがenvをとるようにし、プログラムスタート時に新しく変数環境を作ってreplに渡す。
これで
Lisp>>> (define x 5) 5 Lisp>>> (define y (+ x 1)) 6 Lisp>>> (set! x 3) 3 Lisp>>> (+ x y) 9
のように変数を定義・代入して使える。
第八章： 関数定義
第八章はユーザが関数を自作できるようにする。defineで直接名前に束縛する・lambdaで無名関数として定義する、といった選択肢を用意し、またmultiarityにも対応する。さらには以前定義したprimitivesもある程度統一的なアーキテクチャで呼び出されるようにしたい。
まずは変数環境を見直すところから。
というのもこのLispの関数はclosureを持つので、関数が定義された時点での変数環境を凍結させた形で関数のデータとして保持させたい。そのためには完全にミュータブルなHashtblだと少し都合が悪い。Map refに変更する。
そして関数定義を実装するためには、ExpとEnvの型を相互再帰にする必要が出てくる。（ここでも同じ話をした）
なのでまずはExpとEnvの相互再帰的な部分をくくりだしたExpenvモジュールを定義する：
module Envm = Map.Make(String) type expt = Atom of string | List of expt list | DottedList of expt list * expt | Number of int | String of string | Bool of bool | PrimitiveFunc of (expt list -> expt) | Func of fn and envt = expt Envm.t ref and fn = {params : string list; varargs : string option; body : expt list; closure : envt}
環境はtype envt = (string, expt) map refになっており、式の型はFuncが追加され、その内部ではclosureにenvt型が使われている。
EnvとExpはこのEnvexp内の型定義を使って書かれている。
Evalに長々と書かれていたprimitive関数の定義はすべてPrimitivesモジュールに移し、変数環境に全部定義するための関数loadを用意しておく。これでbin/ex.mlから：
let _ = repl (Env.create () |> Primitives.load)
などとしてプログラムスタート時にPrimitivesを変数環境に加えている。
あとはEvalモジュールで関数呼び出しと関数定義に関するコードを追加する。
関数呼び出し：
let rec f env e = match e with (* 省略 *) | List (head :: tail) -> let func = f env head in let args = List.map (f env) tail in apply func args (* 省略 *) and apply func args = match func with | PrimitiveFunc fn -> fn args | Func fn -> List.map (f (bind_args fn args)) fn.body |> List.rev |> List.hd | _ -> raise @@ Exception.NotFunction ("Non-function found at front position", to_string func)
先頭の要素がquoteやifなどの特殊なワードではない場合、まず先頭要素を評価し、それ以外の要素を評価し、先頭要素を関数、それ以外を引数としてapplyする。先頭要素がPrimitive関数な場合はそのまま引数を渡して結果を計算する。primitiveではない関数な場合、関数のclosureに仮引数と引数を対応させる形で追加し、そのclosureをenvとして関数のbodyとなるリストを順次評価（ここでapplyとEval.fが相互再帰する）、最後の結果を式全体の評価結果として返す。
「関数のclosureに仮引数と引数を対応させる形で追加」というのが少しめんどくさく、以下のヘルパー関数を定義してある：
let rec bind_args' params args env = match params, args with | [], [] -> env | p::params', a::args' -> (Env.define_var env p a |> ignore; bind_args' params' args' env) | _ -> raise @@ Exception.Default "Interpreter error - failed to detect NumArg mismatch" let rec bind_vargs' params args varg env = match params, args with | [], [] -> env | p::params', a::args' -> (Env.define_var env p a |> ignore; bind_vargs' params' args' varg env) | [], _ -> (Env.define_var env varg (List args) |> ignore; env) | _ -> raise @@ Exception.Default "Interpreter error - failed to detect NumArg mismatch" let bind_args (fn : Exp.fn) args = let pcount = List.length fn.params in let acount = List.length args in if pcount != acount && fn.varargs = None then raise @@ Exception.NumArgs (pcount, "" ^ string_of_int acount) else match fn.varargs with | None -> bind_args' fn.params args fn.closure | Some varg -> bind_vargs' fn.params args varg fn.closure
とくにmultiarity用のvarargsの存在が実装を少しややこしくしている印象。
関数定義はmake_funcというヘルパー関数を使って実装している：
let make_func paratoms vargs body env = let stringify_atom = function | Atom s -> s | e -> raise @@ Exception.TypeMismatch ("Function parameters must be atoms", to_string e) in Func {params=List.map stringify_atom paratoms; varargs=vargs; body=body; closure=(Env.copy env)} let rec f env e = match e with (* 省略 *) | List (Atom "define" :: List (Atom v::paratoms) :: body) -> make_func paratoms None body env |> Env.define_var env v | List (Atom "define" :: DottedList (Atom v::paratoms, Atom varg) :: body) -> make_func paratoms (Some varg) body env |> Env.define_var env v | List (Atom "lambda" :: List paratoms :: body) -> make_func paratoms None body env | List (Atom "lambda" :: DottedList (paratoms, Atom varg) :: body) -> make_func paratoms (Some varg) body env | List (Atom "lambda" :: Atom varg :: body) -> make_func [] (Some varg) body env (* 省略 *)
varargs有無でdefine/lambdaによる関数定義ができる。
closureがちゃんと作動していることを示す例として：
Lisp>>> (define (count inc) (lambda (x) (set! inc (+ inc x)) inc)) (lambda (inc) ...) Lisp>>> (define my-counter (count 1)) (lambda (x) ...) Lisp>>> (my-counter 3) 4 Lisp>>> (my-counter 5) 9 Lisp>>> inc UnboundVar Getting unbound var inc
inc変数はmy-counterの中には存在していて、関数呼び出しごとに破壊的代入されている。関数の外からはアクセスできない（外側の変数環境には存在しない、とエラーが出る）。
と、ここまででようやくちゃんとしたプログラミング言語らしくなってきた。再帰ができないのが非常に気がかりだが、とりあえず48時間以内に最低限のLispが実装できた、と言ってもいい気がする。
しかしもうちょっとだけ続くんじゃ。
OCamlで48 Hour Schemeをやってみる その3 （第四章、五章）
第四章：エラーハンドリング
第四章の主眼はエラーハンドリング。
Haskellだとモナドでやるのが正しい作法なようで、型チェックの恩恵に与れる。その反面、一章を割いていろんな関数の実装と型注釈を変更していく必要がある。
OCamlだと例外を投げればいいので楽。
Exceptionsモジュールで使ういろんなエラーを定義して：
exception NumArgs of int * string exception TypeMismatch of string * string exception LexingFail of string exception BadSpecialForm of string * string exception NotFunction of string * string exception UnboundVar of string * string exception Default of string
他のモジュールで投げるだけ。今のところは「捉えて解釈してより有用なエラーメッセージを出力する」みたいなことはしていない。
第五章：機能追加
第五章では新たにいろいろと機能を追加していく。
=, <, >, &&, ||などの二項演算子、ifによる条件分岐、car, cdr, consなどのリスト処理関数、そして比較演算子eq?, eqv? equal?などを実装した。
ついでに細々とした実装の間違いが発覚したので、それも修正：
'(a b c)を(quote a b c)とパースしていたのを(quote (a b c))になるように変更"abc"といった文字列をString "\"abc\""とパースしていたのをString "abc"になるように変更
細かい修正はコミットログを見てもらえばわかるが、比較的簡単に機能が追加できるのは嬉しい。
次章はREPLを追加する話。
OCamlで48 Hour Schemeをやってみる その２ （第三章後半）
前回から続いてWrite Yourself a Scheme in 48 Hours第三章。
primitive関数適用の評価まで実装する。
src/eval.mlというモジュールを新たに作った。
open Exp (* 省略 *) let rec f e = match e with | String _ -> e | Number _ -> e | Bool _ -> e | List [Atom "quote"; e2] -> e2 (* 省略 *) | _ -> failwith "Evaluation not implemented"
まずはこんな感じに文字列、数字、真偽値は評価されてもそのままであると定義。(quote x)のようなリストはxに評価される。
これをbin/ex.mlから使うようにする：
open Lisp let _ = Lexing.from_channel stdin |> Parser.f Lexer.f |> Eval.f |> Exp.to_string |> print_endline
ここまでは簡単。次はeval.mlを拡張してprimitive関数適用を評価できるようにする。
まずはLisp式を整数値に変換する関数：
let rec to_int = function | Number n -> n | String s -> (try int_of_string s with Failure _ -> 0) | List [e] -> to_int e | _ -> 0
Number型は単純なのだが
- 文字列は変換できれば変換する
- 単一の要素を持つリストはその要素を整数値に変換する
- それ以外の式はすべて0として扱う
というなんとも「弱い型」な評価方法。
二項演算子とLisp式のリストをとり、Lisp式を整数に変換してfoldするnumeric_binop関数：
let numeric_binop op params = let n = match List.map to_int params with | [] -> 0 | x :: xs -> List.fold_left op x xs in Number n
primitive関数をnumeric_binopで定義してstring Mapに入れておく：
module P = Map.Make(String) let primitives = P.empty |> P.add "+" (numeric_binop (+)) |> P.add "-" (numeric_binop (-)) |> P.add "*" (numeric_binop ( * )) |> P.add "/" (numeric_binop (/)) |> P.add "mod" (numeric_binop (mod))
これで関数適用のためのapplyが書ける：
- Lisp式リストのCARがprimitiveに合致するかどうかをチェック
- もし合致していたらその関数をリストのCDRに適用する
let apply func args = match P.find_opt func primitives with | None -> Bool false | Some f -> f args
Eval.f関数内では、まずCDRの個々の要素を評価してからapplyを使う：
let rec f e = match e with (* 省略 *) | List (Atom func :: args) -> List.map f args |> apply func (* 省略 *)
これで
> echo "(- 54 10 2)" | dune exec bin/ex.bc 42
となる。
次回はエラーハンドリング。
OCamlで48 Hour Schemeをやってみる その１ （第一章〜第三章前半まで）
こういうことを言ってしまった：
これは宗教勧誘とかじゃなくて真面目に言うんですが、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))
続く
今週末中に全部実装して記事にできたらいいな・・・ （続き）
let多相と型制約と型推論
こういう（けっこう前の）記事があって面白かった：
大変面白かったのと、何故こうなるのかが微妙に理解し切れなかったのと、で少し自分でも調べてみた。
ちょっと例を簡略化すると
let f x = x in f 1, f true
は型検査を通るけど
let f x : 'a = x in f 1, f true let g (x : 'a) = x in g 1, g true
などは通らない、という話だ。
（ちなみにOCaml 4.06.1だと"Error: This expression has type bool but an expression was expected of type int"と怒られる）
'aという型「注釈」をつけた途端に型検査が通らなくなる、ように見える。
さらにいうとutopなどで
let f x = x;;
としてみるとval f : 'a -> 'a = <fun>だと言ってくる。その型と合致する注釈をつけているのに何故？
ポイントは上記の記事で@camloebaさんが言っている通り、let f x : 'a ...は型注釈ではなく型制約だという点のようだ。
つまりlet f x : 'a = ... in ...というような記述は
この
f xは'a型（パラメトリック多相）として扱ってね
という型注釈ではなく
型推論のunificationの時にとりあえず
f xには'aという型変数を振っておいてね
という型制約だということ。.mliファイルやモジュールのsignatureでval f : 'a -> 'aと指定するのとは本質的に異なる記述のようだ。
そう考えると、この制約があると
let f x : 'a = x in f 1, f true
でf 1の時点で'a = intだとunifyされて、f trueで型検査が失敗する、というのは直観的だと思う。
ではなぜこの型制約がないと型検査を通るか？
let多相と型推論についてTaPLの22.6章にこう書いてあった：
A better alternative (to allow programmers to completely omit type annotations on lambda-abstractions) is to add un-annotated abstractions to the syntax of terms and a corresponding rule to the constraint typing relation. ...
This account of un-annotated abstractions is ... more expressive, in a small but useful way: if we make copies on an un-annotated abstraction, the CT-ABS_INF (type constraint) rule will allow us to choose a different variable as the argument type of each copy. By contrast, if we regard a bare abstraction as being annotated with an invisible type variable, then making copies will yield several expressions sharing the same argument type. This difference is important for the discussion of let-polymorphism... - Benjamin Pierce, Types and Programming Languages, Chapter 22.6
そもそもlet多相を実現するためにlet x = t1 in t2という記述に対して型推論時にxに型変数を振らないでおくということらしい。ちなみに22.7章はその考えで具体的にどうlet多相を実現するかというトピック。
せっかく型推論が空気を読んで（？）letで定義される変数に型変数を振らずに解決しようとしているのに、let f x : 'a ...などとしたせいで振らざるを得なくなってしまって、その結果unificationで「int = boolになるので型検査失敗です」とエラーが出てしまう、というのが真相のようだ。
