小さな関数型言語のインタプリタ

2024/04/28

Ocaml で小さな関数型言語のインタプリタを作成しました。

GitHub - seelx3/mini-ml: 小さな関数型言語のインタプリタ
小さな関数型言語のインタプリタ. Contribute to seelx3/mini-ml development by creating an account on GitHub.
favicongithub.com
ogImage

事前準備

  • ocaml
  • dune

インストール

cd mini-ml                     ## プロジェクトディレクトリに移動
dune build                     ## ビルド
chmod +x miniml                ## 実行権限付与
./miniml                       ## REPL 起動
./miniml examples/fun_1.txt    ## プログラム実行

サンプルプログラム

作成したインタプリタでは次のようなプログラムを実行することができます。

plus.txt

  • 以下のような足し算を行うことができます。
1 + 1 + 2 + 3
実行結果 
7

let-in.txt

  • let <var> = <expr1> in <expr2> は <expr2> の中で <var> を <expr1> に束縛します。
  • 次の例では、x に 1 を束縛し、y に 2 を束縛した上で、x + y が評価されるため、実行結果は 3 になります。
let x = 1 in
  let y = 2 in
    x + y
実行結果 
3

fun_1.txt

  • let f = fun x:Int -> x + 1 in f 1 のように、関数を f に束縛し、その関数を呼び出すことができます。
    • 型検査のために、引数の型を指定する必要があります。
  • 次の例では、最初に x に 1 が束縛されているため、変数 f には fun y:Int -> 1 + y が束縛されます。f (x + 3) において x は 3 行目の式で 2 に束縛されているため、最終的に f (2 + 3) が評価され、結果は 6 になります。
let x = 1 in
  let f = fun y:Int -> x + y in
    let x = 2 in
      f (x + 3)
実行結果 
6

product.txt

  • 以下の (1, 2) ような 2 つの式から構成される Product 型を利用することができます。
let x = (1, 2) in
  let l = fst x in
    let r = snd x in
      l + r

デバッグ

REPL には utop を使用することができます。

ocaml 標準の REPL と比べて、utop は補完機能などが充実しているため、開発時に便利です。

dune utop   ## REPL 起動

utop

Miniml.Parse.parse

  • parse により、文字列が構文木に変換されていることが確認できます。
utop # Miniml.Parse.parse "if (1 + 2) < 3 then 4 else 5";;
- : Miniml.Syntax.prog =
Miniml.Syntax.If
 (Miniml.Syntax.Lt
   (Miniml.Syntax.Add (Miniml.Syntax.Int 1, Miniml.Syntax.Int 2),
   Miniml.Syntax.Int 3),
 Miniml.Syntax.Int 4, Miniml.Syntax.Int 5)

Miniml.Infer.infer

  • infer により、構文木が型検査されて TInt 型となっていることが確認できます。
utop # Miniml.Infer.infer (Miniml.Parse.parse "if (1 + 2) < 3 then 4 else 5");;
- : Miniml.Infer.typ = Miniml.Infer.TInt

Miniml.Reduction.normalize

  • normalize により、構文木が評価されて 5 になっていることが確認できます。
utop # Miniml.Reduction.normalize (Miniml.Parse.parse "if (1 + 2) < 3 then 4 else 5");;
- : Miniml.Syntax.prog = Miniml.Syntax.Int 5

ocamllex と ocamlyacc

  • ocamllex
    • 字句解析器を生成するためのツール
    • 字句解析器は、入力された文字列からトークンの列を生成します。
utop # Miniml__Lexer.token (Lexing.from_string "1");;
- : Miniml.Parser.token = Miniml.Parser.INT

utop # Miniml__Lexer.token (Lexing.from_string "+");;
- : Miniml.Parser.token = Miniml.Parser.PLUS
  • ocamlyacc
    • 構文解析器を生成するためのツール
    • 構文解析器は、トークンの列から構文木を生成します。
utop # Miniml__Parser.main Miniml__Lexer.token (Lexing.from_string "1 + 2");;
- : Miniml.Syntax.prog =
Miniml.Syntax.Add (Miniml.Syntax.Int 1, Miniml.Syntax.Int 2)

ミニ言語の構文

syntax.ml で定義されている構文は以下の通りです。

type typ = TBool | TInt | TProduct of typ * typ | TUnit | TArraow of typ * typ

type prog =
  | Bool of bool
  | Int of int
  | Unit
  | Add of prog * prog
  | Lt of prog * prog
  | If of prog * prog * prog
  | Product of prog * prog
  | Fst of prog
  | Snd of prog
  | Var of string
  | Let of string * prog * prog
  | Fun of string * typ * prog
  | FunVal of string * prog * (string * prog) list
  | App of prog * prog

ミニ言語の操作的意味論

reduction.ml で定義されている reduce が、操作的意味論における推論規則に基づいて 1 ステップ簡約を行います。 normalize は、reduce を再帰的に適用して、簡約ができなくなるまで簡約を行います。

type env = (string * prog) list

let rec reduce (e : prog) (env : env) : (prog * env) option =
  match (e, env) with
  | Var x, _ -> (
    match List.assoc_opt x env with Some e' -> Some (e', env) | None -> None)
  | Add (n1, n2), _ -> (
    match (n1, n2) with
    | Int n1, Int n2 -> Some (Int (n1 + n2), env)
    | _, _ -> (
      match reduce n1 env with
      | Some (n1', _) -> Some (Add (n1', n2), env)
      | None -> (
        match reduce n2 env with
        | Some (n2', _) -> Some (Add (n1, n2'), env)
        | None -> None)))
...

let normalize (e : prog) : prog =
  let rec normalize' (e : prog) (env : env) : prog =
    match reduce e env with Some (e', env') -> normalize' e' env' | None -> e
  in
  normalize' e []

型検査

上記でプログラムの評価器を作成しましたが、このままでは型の整合性チェックを行っていません。 そのため、1 + true のような式も評価されてしまい、実行時エラーが発生してしまいます。 プログラム中のエラーを事前に検出するために、型検査を行います。

infer.ml で定義されている infer および typable で型検査が行われます。

exception Type_error

let infer (e : prog) : typ =
  let rec infer' (e : prog) (env : (string * typ) list) : typ =
    match e with
    | Bool _b -> TBool
    | Int _n -> TInt
    | Unit -> TUnit
    | Var x -> ( try List.assoc x env with Not_found -> raise Type_error)
    | Add (p, q) -> (
      let tp = infer' p env in
      let tq = infer' q env in
      match (tp, tq) with TInt, TInt -> TInt | _ -> raise Type_error)
...

let typable (e : prog) : bool =
  try
    let _ = infer e in
    true
  with Type_error -> false

まとめ

字句解析・構文解析に ocamllex と ocamlyacc を使用して、小さな関数型言語のインタプリタを作成しました。 fun の追加あたりから、環境を扱う必要が出てきて、それに伴い、型検査や評価の処理が少し複雑になってきました。 今後時間があれば、再帰関数やパターンマッチングなどの機能を追加していきたいと思います。

© 2024 seelx3