DEV Community

zenwerk
zenwerk

Posted on

OCaml で書かれた Python のサブセット実装 ocaml-minipy のソースを読む

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

GitHub logo LaurentMazare / ocaml-minipy

Naive interpreter for a Python like language

minipy

Minimalist Python-like language interpreter in OCaml.

Try the interpreter online or use the editor (these rely on js_of_ocaml).

This is a work in progress, most of the supported features are only partially implemented.

Supported Features

  • Python values
    • Boolean.
    • Integer (represented with arbitrary precision).
    • Float.
    • String.
    • List/Tuple.
  • Function definitions (with keyword arguments, ...), nested function definition.
  • Variable assignments with tuple/list destructuring and assignements to a list element.
  • Augmented assignments +=, -=, etc.
  • Control flow
    • Loops: while and for loops, with support for break and continue.
    • If conditionals with elif and else.
  • Expressions
    • Unary and binary operators, comparisons.
    • Ternary if operator.
    • Attributes, e.g. x.foo.
    • Subscripts, e.g. x[foo].
    • Lambdas, lambda.
    • List comprehensions (only for lists, no support for dict/set).
  • Built-ins print, range.
  • Dictionaries.
  • Delete operator, del.
  • REPL example, javascript version with js-of-ocaml.
  • Starred expressions.
  • Basic object system.
  • Exceptions, try/with blocks, raise

レキサーとパーサー

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

ocaml-minipyocamllexMenhir を利用しているのでまずは lexer.mllparser.mly を読みます。

ちなみに作者のコメントによると MenhirLR(1) パーサーですが Python は LL(1) なので、LL構文をパーシングするために多少トリッキーな実装になっているそうです。

lexer.mll

インデントによるオフサイドルールを扱うため、lexer.mll が一番実装が濃い部分のように感じます。

next_line関数

next_line関数 はレキサーを次の行に移動する関数です。

(* 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    (* 次の行へ移動する *)
  }

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

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

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

Envモジュール

Envモジュールはレキサーの意味的な状態を保持するモジュールで、オフサイドルール処理の肝です。

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.tindents はインデントされたときのスペース数を Stack で保持します。
例えばインデントをスペース4つで行ったときは 4, 8, 12, ...フィボナッチ数なら 1, 2, 7, 13 ... とスタックに整数が積まれていきます。

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

Env.push_indentt.indents にインデント時のスペース数をスタックにpushします。

Env.drop_indentは、スペース数が ~until になるまでインデントを下げます。

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)で ~until4 のとき、12, 8 とスタック2つポップされるのでインデントが2つ下がったと判別できます。

string_loop 関数

Python には """hoge""", '''fuga'''"a", 'b', r"c", r'd' など色々な文字列リテラルの書き方がありますが、ocaml-minipy はではそれぞれのリテラル表記を個別のレキサー関数で処理しています。

string_loop関数lexbuf と上述の個別定義された文字列リテラルのレキサー関数を ~f で受け取り文字列ASTを返します。

インデントの検出

ocaml-minipy ではレキサーのアクション部でインデントの検出をしています。

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

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

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

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

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

(* 改行の分だけ 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. 最初の forlexbuf をマニュアル更新しておく
  2. 行頭のスペース数を計算し indent に保存
  3. Env.t に保存されているインデント数と比較して、それぞれの場合に応じて push_indent, drop_indent を呼び出す

parser.mly

レキサーに比べるとparser.mlyはわかりやすい実装で、定義部にはユーティリティ関数がいくつか定義されている程度です。

なおパーサーが返すASTの定義は ast.ml にあります。

parse.ml

parse.mlでは lexer.mllparser.mly で生成されたレキサーとパーサーを利用して実際にパースを実行する関数を定義しています。

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

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

parse関数

実際にパース処理を実行するのがparse関数です。
parse_fun には Menhir が生成したパーサ関数が与えられます。インクリメンタルAPIを利用するための諸々の定義のあと、この行で実際のパース処理が実行されます。

EVAL

パース処理によってASTが生成されたら後は実行するのみです。
ASTを実行する関数定義は interpreter.ml にあります。

Envモジュール

Envモジュールはインタプリタの実行状態を保持するためのモジュールです。

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

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関数 です。

eval

後は文(stmt)と式(expr)のASTをパターンマッチして直接OCamlコードに解釈して実行しています。

ASTをバイトコードにコンパイルしてからVMで実行するというのが近代的な実装でしょうが、コメントの通りASTを直接実行する素朴な実装です。

実行環境

これまで確認したレキサー/パーサー/EVALを使用して完動する処理系を作成する例はexamplesディレクトリ以下にあります。
例えば examples/toplevel.ml シンプルなトップレベル(REPL)環境の作成例です。

その他

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

Top comments (0)