OCaml で Python のようなオフサイドルールのある言語実装を探していたところ、まさにちょうどよい実装があったので参考のためソースを読んだ際のメモです。
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
andfor
loops, with support forbreak
andcontinue
. - If conditionals with
elif
andelse
.
- Loops:
- 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-minipy
は ocamllex
と Menhir
を利用しているのでまずは lexer.mll
と parser.mly
を読みます。
ちなみに作者のコメントによると Menhir
は LR(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 (* 次の行へ移動する *)
}
引数の lexbuf
は ocamllex
のレキサーの内部状態を表す型で定義は以下の通りです。
lexbuf.lex_curr_p
は Lexing.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.t
の indents
はインデントされたときのスペース数を Stack で保持します。
例えばインデントをスペース4つで行ったときは 4, 8, 12, ...
、フィボナッチ数なら 1, 2, 7, 13 ...
とスタックに整数が積まれていきます。
Env.t
のインデントスタックの状態を操作する関数は以下のように定義されています。
Env.push_indent は t.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
)で ~until
が 4
のとき、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つ
- その後任意のスペースまたは改行
例えば以下のような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]
)
処理の流れは以下の通り
- 最初の
for
でlexbuf
をマニュアル更新しておく - 行頭のスペース数を計算し
indent
に保存 -
Env.t
に保存されているインデント数と比較して、それぞれの場合に応じてpush_indent
,drop_indent
を呼び出す
parser.mly
レキサーに比べるとparser.mlyはわかりやすい実装で、定義部にはユーティリティ関数がいくつか定義されている程度です。
combine_if関数は
if
やelif
の条件部(test
)と実行部(body
)をいい感じに一つのASTにまとめて返すmerge_parameters関数 と merge_args関数 は名前の通り関数の引数やキーワード引数をレコードにまとめて返す
なおパーサーが返すASTの定義は ast.ml にあります。
parse.ml
parse.mlでは lexer.mll
と parser.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)