OCaml で書かれた Python のサブセット実装 ocaml-minipy のソースを読む
Tags: ocaml
Published: 2020-05-21 09:54:13

---
title: OCaml で書かれた Python のサブセット実装 ocaml-minipy のソースを読む
published: true
description: ocaml-minipy のコードリーディング
tags: ocaml 
---

OCaml で Python のようなオフサイドルールのある言語実装を探していたところ、まさにちょうどよい実装があったので参考のためソースを読んだ際のメモです。

{% github LaurentMazare/ocaml-minipy %}



## レキサーとパーサー

何はともあれレキサーとパーサーです。

`ocaml-minipy` は `ocamllex` と `Menhir` を利用しているのでまずは `lexer.mll` と `parser.mly` を読みます。

ちなみに作者の[コメント](https://github.com/LaurentMazare/ocaml-minipy/blob/9f3859107ad5ff8a3f470b5ecfef4495826629da/src/parser.mly#L2-L5)によると `Menhir`は `LR(1)` パーサーですが Python は `LL(1)` なので、LL構文をパーシングするために多少トリッキーな実装になっているそうです。

### lexer.mll

インデントによるオフサイドルールを扱うため、[lexer.mll](https://github.com/LaurentMazare/ocaml-minipy/blob/9f3859107ad5ff8a3f470b5ecfef4495826629da/src/lexer.mll) が一番実装が濃い部分のように感じます。


#### `next_line`関数

[next_line関数](https://github.com/LaurentMazare/ocaml-minipy/blob/9f3859107ad5ff8a3f470b5ecfef4495826629da/src/lexer.mll#L9-L11) はレキサーを次の行に移動する関数です。

```ocaml
(* lexbuf をマニュアルで更新する *)
let next_line lexbuf =
  let pos = lexbuf.lex_curr_p in
  lexbuf.lex_curr_p <- { pos with  (* lexer の現在位置を元にして *)
    pos_bol = lexbuf.lex_curr_pos; (* 行頭オフセットはlexerの現在のカーソル位置とする *)
    pos_lnum = pos.pos_lnum + 1    (* 次の行へ移動する *)
  }
```

引数の `lexbuf` は `ocamllex` のレキサーの内部状態を表す型で定義は以下の通りです。

- https://caml.inria.fr/pub/docs/manual-ocaml/libref/Lexing.html

`lexbuf.lex_curr_p` は `Lexing.position` 型で、どの行・箇所をパースしているかを保持しています。

```ocaml
type position = (* ソースファイル内のポイント *)
  Lexing.position = {
  pos_fname : string; (* ファイル名 *)
  pos_lnum : int;     (* 行番号 *)
  pos_bol : int;      (* 行頭のオフセット *)
  pos_cnum : int;     (* 位置のオフセット *)
}
```

#### `Env`モジュール

[Envモジュール](https://github.com/LaurentMazare/ocaml-minipy/blob/9f3859107ad5ff8a3f470b5ecfef4495826629da/src/lexer.mll#L14-L19)はレキサーの意味的な状態を保持するモジュールで、オフサイドルール処理の肝です。

```ocaml
module Env = struct
  type t =
    { indents: int Stack.t (* インデント増加時の累積スペースの数をスタックで保持する *)
    ; mutable nestings : int (* [, {, ( などのネスト数 *)
    ; mutable tokens : Parser.token Queue.t
    ; mutable last_token : Parser.token option
    }
  ...
```

型`Env.t`の `indents` はインデントされたときのスペース数を [Stack](https://ocaml.janestreet.com/ocaml-core/latest/doc/base/Base/Stack/index.html) で保持します。
例えばインデントをスペース4つで行ったときは `4, 8, 12, ...`、[フィボナッチ数](https://github.com/dodie/vim-fibo-indent/blob/master/tty.gif)なら `1, 2, 7, 13 ...` とスタックに整数が積まれていきます。


`Env.t` のインデントスタックの状態を操作する関数は以下のように定義されています。

[Env.push_indent](https://github.com/LaurentMazare/ocaml-minipy/blob/9f3859107ad5ff8a3f470b5ecfef4495826629da/src/lexer.mll#L39-L40) は `t.indents` にインデント時のスペース数をスタックにpushします。

[Env.drop_indent](https://github.com/LaurentMazare/ocaml-minipy/blob/9f3859107ad5ff8a3f470b5ecfef4495826629da/src/lexer.mll#L42-L52)は、スペース数が `~until` になるまでインデントを下げます。

```ocaml
let drop_indent t ~until =
  let rec loop acc =
    match Stack.top t.indents with (* 先頭のインデント数のスペース数を取り出す *)
    | None -> if until = 0 then Some acc else None  (* スタックが空かつインデントレベル0 -> インデントなし *)
    | Some level when level = until -> Some acc     (* 指定したインデントレベル(until)に到達 *)
    | Some level when level < until -> None         (* インデント数が揃っていない *)
    | Some _level (* when level > until *) ->       (* POPしてインデントレベルを下げる *)
        ignore (Stack.pop_exn t.indents : int);
        loop (acc + 1) (* DEDENT数をインクリメント *)
  in
  loop 0
```

例えばスペース数`4`でインデントして現在のインデントレベルが`3`（スペース数が`12`）で `~until` が `4` のとき、`12, 8` とスタック2つポップされるのでインデントが2つ下がったと判別できます。

#### string_loop 関数

`Python` には `"""hoge"""`, `'''fuga'''` や `"a"`, `'b'`, `r"c"`, `r'd'` など色々な文字列リテラルの書き方がありますが、`ocaml-minipy` はではそれぞれのリテラル表記を[個別のレキサー関数](https://github.com/LaurentMazare/ocaml-minipy/blob/9f3859107ad5ff8a3f470b5ecfef4495826629da/src/lexer.mll#L189-L232)で処理しています。

[string_loop関数](https://github.com/LaurentMazare/ocaml-minipy/blob/9f3859107ad5ff8a3f470b5ecfef4495826629da/src/lexer.mll#L60-L69) は `lexbuf` と上述の個別定義された文字列リテラルのレキサー関数を `~f` で受け取り文字列ASTを返します。


#### インデントの検出

`ocaml-minipy` では[レキサーのアクション部](https://github.com/LaurentMazare/ocaml-minipy/blob/9f3859107ad5ff8a3f470b5ecfef4495826629da/src/lexer.mll#L156-L181)でインデントの検出をしています。

対象となる文字列は `('#' [^'\n']*)? '\n' [' ' '\n']*` で以下の通りで

1. 任意のコメント行
2. 改行1つ
3. その後任意のスペースまたは改行

例えば以下のような`Python`コードが対象となります。

```python
# コメント
    func() # func の手前のスペースまでが処理対象
```

アクション部の定義は以下の通りで、レキサーが検出したスペース数と `Env.t` 内に保存されているインデントスタックの状態を比較して処理を行います。

```ocaml
(* 改行の分だけ lex_curr_p の行をすすめる *)
for _i = 1 to String.count str ~f:(Base.Char.(=) '\n') do
  next_line lexbuf
done;
(* 最後の改行から何個スペースがあるか = インデント数 *)
let indent = String.length str - String.rindex_exn str '\n' - 1 in
(* nesting != 0 のときカッコの中にいるのでインデントは無視される *)
if env.nestings <> 0 then read env lexbuf
(* インデントの処理 *)
else
  let last_indent = Env.last_indent env in
  if last_indent = indent then [NEWLINE]
  (* 最後のインデントより少ないスペース数 = インデントが下がっている *)
  else if last_indent > indent then (
    (* インデントが下がった分だけ DEDENT を返す *)
    let dropped =
      match Env.drop_indent env ~until:indent with
      | None -> raise (SyntaxError (Printf.sprintf "Unexpected indentation level %d" indent))
      | Some dropped -> dropped
    in
    NEWLINE :: List.init dropped (fun _ -> DEDENT)
  ) else (
    (* インデントを増やす *)
    Env.push_indent env indent; (* インデント(正確にはインデントしたスペースの数)を積む *)
    [NEWLINE; INDENT]
  )
```

処理の流れは以下の通り

1. 最初の `for` で `lexbuf` をマニュアル更新しておく
2. 行頭のスペース数を計算し `indent` に保存
3. `Env.t` に保存されているインデント数と比較して、それぞれの場合に応じて `push_indent`, `drop_indent` を呼び出す


### parser.mly

レキサーに比べると[parser.mly](https://github.com/LaurentMazare/ocaml-minipy/blob/9f3859107ad5ff8a3f470b5ecfef4495826629da/src/parser.mly)はわかりやすい実装で、定義部にはユーティリティ関数がいくつか定義されている程度です。

- [combine_if関数](https://github.com/LaurentMazare/ocaml-minipy/blob/9f3859107ad5ff8a3f470b5ecfef4495826629da/src/parser.mly#L14-L20)は`if` や `elif` の条件部(`test`)と実行部(`body`)をいい感じに一つのASTにまとめて返す

- [merge_parameters関数](https://github.com/LaurentMazare/ocaml-minipy/blob/9f3859107ad5ff8a3f470b5ecfef4495826629da/src/parser.mly#L24-L57) と [merge_args関数](https://github.com/LaurentMazare/ocaml-minipy/blob/9f3859107ad5ff8a3f470b5ecfef4495826629da/src/parser.mly#L59-L69) は名前の通り関数の引数やキーワード引数をレコードにまとめて返す

なおパーサーが返すASTの定義は [ast.ml](https://github.com/LaurentMazare/ocaml-minipy/blob/9f3859107ad5ff8a3f470b5ecfef4495826629da/src/ast.ml) にあります。

### parse.ml

[parse.ml](https://github.com/LaurentMazare/ocaml-minipy/blob/9f3859107ad5ff8a3f470b5ecfef4495826629da/src/parse.ml)では `lexer.mll` と `parser.mly` で生成されたレキサーとパーサーを利用して実際にパースを実行する関数を定義しています。

`ocaml-minipy` では `Menhir` のインクリメンタルAPIというものを利用しています。これは `Menhir` がパースを実行するときの各状態にアクセスできるようになるもので、より細かいパース処理が書けるようになる機能です。
`ocaml-minipy` ではエラーメッセージの構築のためインクリメンタルAPIの機能を利用しています。

詳しくはドキュメントを参照してください。

- http://gallium.inria.fr/~fpottier/menhir/manual.html#sec57

#### parse関数

実際にパース処理を実行するのが[parse関数](https://github.com/LaurentMazare/ocaml-minipy/blob/9f3859107ad5ff8a3f470b5ecfef4495826629da/src/parse.ml#L125-L179)です。
`parse_fun` には `Menhir` が生成したパーサ関数が与えられます。インクリメンタルAPIを利用するための諸々の定義のあと、[この行](https://github.com/LaurentMazare/ocaml-minipy/blob/9f3859107ad5ff8a3f470b5ecfef4495826629da/src/parse.ml#L171)で実際のパース処理が実行されます。


## EVAL

パース処理によってASTが生成されたら後は実行するのみです。
ASTを実行する関数定義は [interpreter.ml](https://github.com/LaurentMazare/ocaml-minipy/blob/9f3859107ad5ff8a3f470b5ecfef4495826629da/src/interpreter.ml) にあります。

### Envモジュール

[Envモジュール](https://github.com/LaurentMazare/ocaml-minipy/blob/9f3859107ad5ff8a3f470b5ecfef4495826629da/src/interpreter.ml#L11-L69)はインタプリタの実行状態を保持するためのモジュールです。

オフサイドルールによるブロックのネスト状態を `Env.t` に保持しています。

```ocaml
module Env : sig
  type t = Value.env

  val empty : ?builtins:builtins -> unit -> t

  (* [body] is used to extract local variables. *)
  val nest : prev_env:t -> body:Ast.t -> t
  val find_exn : t -> name:string -> Value.t
  val set : t -> name:string -> value:Value.t -> unit
  val remove : t -> name:string -> unit
  val last_scope : t -> (string, Value.t) Hashtbl.t
end = struct
  type t = Value.env =
    { scope : (string, Value.t) Hashtbl.t (* 現在のスコープで定義されている変数や関数とその中身を保持するテーブル *)
    ; prev_env : t option                 (* 一つ前のブロック *)
    ; local_variables : string Hash_set.t (* スコープからアクセス可能なローカル変数名の集合 *)
    ; builtins : builtins                 (* ビルトイン関数の集合 *)
    }

    ...
```

いわゆる再帰的なレコード定義で `t.prev_env` にレコードをつなげていくことでネスト状態を表しています。
ブロックをつなげる関数は [Env.nest関数](https://github.com/LaurentMazare/ocaml-minipy/blob/9f3859107ad5ff8a3f470b5ecfef4495826629da/src/interpreter.ml#L40-L45) です。

### eval

後は文(stmt)と式(expr)のASTを[パターンマッチして](https://github.com/LaurentMazare/ocaml-minipy/blob/9f3859107ad5ff8a3f470b5ecfef4495826629da/src/interpreter.ml#L129-L327)直接OCamlコードに解釈して実行しています。

ASTをバイトコードにコンパイルしてからVMで実行するというのが近代的な実装でしょうが、[コメント](https://github.com/LaurentMazare/ocaml-minipy/blob/9f3859107ad5ff8a3f470b5ecfef4495826629da/src/interpreter.ml#L129)の通りASTを直接実行する素朴な実装です。


## 実行環境

これまで確認したレキサー/パーサー/EVALを使用して完動する処理系を作成する例は`examples`ディレクトリ以下にあります。
例えば [examples/toplevel.ml](https://github.com/LaurentMazare/ocaml-minipy/blob/9f3859107ad5ff8a3f470b5ecfef4495826629da/examples/toplevel.ml) シンプルなトップレベル（REPL）環境の作成例です。


## その他

`bc_` で始まるファイルはバイトコード（Python でいう `.pyc`）変換処理のようですが、まだ作成途中のため使用されていません。