プログラミング言語の処理系を実装してみたく思い、LispのようなS式を実行する簡易的な処理系を書いてみました。
「第一級の継続(call/cc)を実装する」というのが一番の目標でした。
ひとまずは動くものができたと思うので、実装するにあたって考えたこと、試したことなどを書き残しておこうと思います。
ソースコードはこちらとなります。
言語を軽く説明
Rubyで実装したS式の簡単な処理系です。
VM(バーチャルマシン)実行方式を採用しました。ソースコードを独自のバイトコードに変換して、それを独自のVMで実行します
扱える値は整数と文字列くらいです。組み込みの関数名などは若干Rubyに寄せています。if、while、変数などは実装してあって、こんなコードが動きます。
(= a 5)
(= sum 0)
(while (!= a 0)
(= sum (+ sum a))
(= a (- a 1))
)
(p sum) ; => 15
関数も定義できます。再帰もいけます。
(= sum (-> (x)
(if (== x 0)
0
(+ x (sum (- x 1)))
)
))
(p (sum 5)) ; => 15
関数はクロージャとなっています。
たとえば以下では、「「呼び出すたびにaが加算されてそのaを返す関数」を返す関数」を定義しています。
(= increment (-> (init)
(= a init)
(-> () (= a (+ a 1)))
))
(= inc (increment 10))
(p (inc)) ; => 11
(p (inc)) ; => 12
(p (inc)) ; => 13
第一級の継続があります(多分)。
継続を使うことでループや大域脱出の機能をユーザー側で実装できてすごいです。
(= x 5)
(= cnt "tmp")
(callcc (-> (continuation)
(= cnt continuation)
))
(= x (+ x -1))
(p x)
(if (== x 0)
(puts "finish")
(cnt)
)
; (実行結果)
; 4
; 3
; 2
; 1
; 0
; finish
(= f (-> (raise)
(puts "before raise")
(raise "error in f")
(puts "after raise")
))
(= error_message (callcc (-> (raise)
(puts "before f")
(f raise)
(puts "after f")
)))
(puts error_message)
(puts "finish")
; (実行結果)
; before f
; before raise
; error in f
; finish
S式のパース
パース→コンパイル→実行 の順でソースコードの処理をしていきます。
パースではまず入力のS式を正規表現で区切り、頭から順に読み込んでスタックに入れていきます。
)を読んだときは直近に入れた(を探し、(,)間のトークンを1つにまとめてスタックに入れます。
すべての入力を読み終えればパースは完了しています。
...図示したほうがわかりやすいですね。
たとえば(+ 1 (+ 2 3) (+ 4 5))は次のような流れでパースされます。
stack | input
[] | [:"(", :+, 1, :"(", :+, 2, 3, :")", :"(", :+, 4, 5, :")", :")"]
[:"("] | [:+, 1, :"(", :+, 2, 3, :")", :"(", :+, 4, 5, :")", :")"]
[:"(", :+] | [1, :"(", :+, 2, 3, :")", :"(", :+, 4, 5, :")", :")"]
[:"(", :+, 1] | [:"(", :+, 2, 3, :")", :"(", :+, 4, 5, :")", :")"]
[:"(", :+, 1, :"("] | [:+, 2, 3, :")", :"(", :+, 4, 5, :")", :")"]
[:"(", :+, 1, :"(", :+] | [2, 3, :")", :"(", :+, 4, 5, :")", :")"]
[:"(", :+, 1, :"(", :+, 2] | [3, :")", :"(", :+, 4, 5, :")", :")"]
[:"(", :+, 1, :"(", :+, 2, 3] | [:")", :"(", :+, 4, 5, :")", :")"]
[:"(", :+, 1, [:+, 2, 3]] | [:"(", :+, 4, 5, :")", :")"]
[:"(", :+, 1, [:+, 2, 3], :"("] | [:+, 4, 5, :")", :")"]
[:"(", :+, 1, [:+, 2, 3], :"(", :+] | [4, 5, :")", :")"]
[:"(", :+, 1, [:+, 2, 3], :"(", :+, 4] | [5, :")", :")"]
[:"(", :+, 1, [:+, 2, 3], :"(", :+, 4, 5] | [:")", :")"]
[:"(", :+, 1, [:+, 2, 3], [:+, 4, 5]] | [:")"]
[[:+, 1, [:+, 2, 3], [:+, 4, 5]]] | []
コンパイル方式にした理由
最初は再帰的に実行していたんですよね。
最初の実装ではパースしたS式を再帰的に処理していたのですが、それだと第一級の継続を実装できないことに気づき、バイトコードに変換して処理する方式に切り替えました。
再帰的に処理する方法だと、処理しているS式全体の情報が見えにくいんですよね。
(+ 1 (+ 2 3) (+ 4 5))の1と(+ 2 3)の評価を終えて(+ 1 5 (+ 4 5))になったときを考えてみます。
この時点での継続を取り出す場合、「現在のS式の式全体と、構文木のどこを実行しているのか」という情報をどうにかして取り出す必要があります。
どうにかして取り出せたとしても、継続の呼び出し時には取り出したその情報から再帰のツリーを再構築する必要があります。
そんな芸当はどう頑張っても無理だろうということで、バイトコードを処理するVM実行方式に方針転換しました。
バイトコードであれば実行するコードも評価に使うスタックも線形のリスト構造ですし、計算状態の取り出しと復元がしやすそうです。
コンパイル方法
コンパイル時にはS式を再帰的に辿ります。コードはS式なので、(命令 引数1 引数2 ...)という形式になっています。
再帰的に辿り、命令の種類を見て対応するバイトコードを吐きます。
コードの雰囲気だけ掴んでもらえるとです。
compile_r = -> (exp) do
case exp
in Integer => i
[ "int@#{i}" ]
in Symbol => s
[ "get@#{s}" ]
in Array
case exp.first
# ~~ 省略 ~~
in :if
# ~~~
in :'='
# ~~~
in Symbol | Array
method = exp.first
args = exp[1..]
[*args.map { |a| compile_r.(a) }, compile_r.(method), "send@#{args.size}"]
end
例によって(+ 1 (+ 2 3) (+ 4 5))をコンパイルしてみると、このようなバイトコードが得られます。
int@1
int@2
int@3
get@+
send@2
int@4
int@5
get@+
send@2
get@+
send@3
命令のあとの@は、命令に渡す引数を表しています。
基本的にはこのバイトコードを上から順に実行していきます。
実行方法の概略
計算の結果はスタックを使って管理します。
int@Nは数値Nをスタックにpushする命令です。先程のバイトコードの3行目までを実行すると、1と2と3がpushされます。
命令列: "int@1", "int@2", "int@3"
スタック: [1, 2, 3]
get@Xは変数テーブルからXを取り出してスタックにpushします。+は数少ない組み込みの関数オブジェクトです。
命令列: "get@+"
スタック: [1, 2, 3, +]
send@Nは、引数N個で関数呼び出しをする命令です。呼ぶ関数はスタックのトップにあるものを使います。
この場合、スタックのトップにある+関数を、2と3を引数にして呼び出します。呼び出した結果はスタックにpushします。
引数の数はコンパイル時に分かるので、可変長の引数を扱うことができます。
命令列: "send@2"
スタック: [1, 5]
6行目からの残りはこんな感じです。
"int@4"
[1, 5, 4]
"int@5"
[1, 5, 4, 5]
"get@+"
[1, 5, 4, 5, +]
"send@2"
[1, 5, 9]
"get@+"
[1, 5, 9, +]
"send@3"
[15]
15が計算できました。
VM (バーチャルマシン)について
変数の扱い、ifの扱い、関数呼び出しの扱い、、、の説明に入る前に、まずはこの処理系のVM(バーチャルマシン)について紹介します。
処理系は1つのVMを操作してバイトコードを実行していきます。
1つのVMは複数のスタックフレームを持ち、現在どのスタックフレームを使っているか、を管理しています。
- VMが持っている情報
- スタックフレームの集合
- 現在どのスタックフレームを使っているか
スタックフレームは現在実行しているコードの具体的な情報を持っています。
スタックフレームが管理している情報は以下の5つです。
- スタックフレームが持っている情報
- 実行用のスタック
- 自身を呼び出したスタックフレーム
- 変数の名前と値の対応
- 自身を定義したスタックフレーム
- 実行するコード
- 実行中のコードの行番号
実行用のスタックは、先程見たバイトコードの計算のために使われます。
自身を呼び出したスタックフレームは、関数呼び出し終了後に制御を戻すスタックフレームのことです。
変数の解決時、変数の名前と値の対応に変数の名前があればその値を使います。
無ければ自身を定義したスタックフレームの変数の名前と値の対応を、変数が見つかるまで再帰的に見に行きます。
この機能により関数をクロージャとして実装できています。
実行するコードには、現在実行しているバイトコードが入れられており、実行中のコードの行番号でそのバイトコードの何行目を実行しているかを記録しています。
1つのバイトコードの命令の実行ごとに、実行中のコードの行番号は+1されます。
各情報の詳細はおいおい見ていくとして、ここからは各種機能のコンパイルと実行方法の紹介に移りたいと思います。
変数
変数を定義する構文は次のコードでコンパイルされます。
compile_r = -> (exp) do
case exp
# ~~~
in Array
case exp.first
# ~~~
in :'='
raise "variable `#{exp[1]}` in `#{exp}` is not symbol" unless Symbol === exp[1]
[*compile_r.(exp[2]), "set@#{exp[1]}"]
最初に値の方のS式をコンパイルして、計算結果がスタックのトップにあるように仕込みます。
その後ろにset@変数名のバイトコードを加えます。
set@変数名命令の実行時は、命令列の引数として得た変数名をキーに、スタックのトップに置かれているオブジェクトを値として、変数の名前と値の対応に追加します。
case line
# ~~~
when /^set@(.+)/
name = $1.to_sym
value = vm.current_stack_frame.stack.last
vm.current_stack_frame_update_env(name, value)
.current_stack_frame_line_num_add(1)
例として、(= x 10)は"int@10", "set@x"にコンパイルされます。
コンパイルされたバイトコードを順々に実行し、スタックと変数テーブルを操作していきます。
[] # スタック
[{:+=>Proc12, ...}] # 変数テーブル
"int@10" # 次のバイトコード
------------
[10]
[{:+=>Proc12, ...}]
"set@x"
------------
[10]
[{:+=>Proc12, ..., :x=>10}]
nil
if文
if式では条件ジャンプのjumpif@N命令と、無条件ジャンプのjump@N命令を使います。
これらの命令は、実行中のコードの行番号をN増加させる命令です。
条件式の真偽に応じて、thenの場合とelseの場合のどちらかのみ実行するようにjumpif, jump命令を配置しています。
in :if
if_exp = exp[1]
then_exp = exp[2]
else_exp = exp[3]
if_compiled = compile_r.(if_exp)
then_compiled = compile_r.(then_exp)
else_compiled = compile_r.(else_exp)
[
*if_compiled,
"jumpif@#{else_compiled.size + 1}",
*else_compiled,
"jump@#{then_compiled.size}",
*then_compiled,
]
when /^jumpif@(\d+)/
cond = vm.current_stack_frame.stack.last
line_relative = $1.to_i
vm.then { cond ? _1.current_stack_frame_line_num_add(line_relative) : _1 }
.current_stack_frame_line_num_add(1)
when /^jump@(-?\d+)/
line_relative = $1.to_i
vm.current_stack_frame_line_num_add(line_relative)
.current_stack_frame_line_num_add(1)
while文も似た方法でコンパイルしています。
組み込み関数の呼び出し
(命令 引数1 引数2 ...)の形をした式はすべて関数呼び出しとなります（命令の部分がifや=などの言語のキーワードの場合は除きます）。
引数の個数はコンパイル時に数え、send@Nの引数Nに入れています。
compile_r = -> (exp) do
case exp
# ~~~
in Array
case exp.first
# ~~~
in Symbol | Array
method = exp.first
args = exp[1..]
[*args.map { |a| compile_r.(a) }, compile_r.(method), "send@#{args.size}"]
send@N命令を実行するときは、最初にN個の引数と関数名をスタックからpopします。
変数テーブルから関数を探し、見つけた関数が組み込みの関数(Procオブジェクト)の場合はそれを呼び出し結果をpushして終了です。
def exec_send(vm, code_table, argc)
method_poped_vm, method = vm.current_stack_frame_stack_pop
new_vm, args = argc.times.reduce([method_poped_vm, []]) { |(memo_vm, args), _|
next_vm, poped = memo_vm.current_stack_frame_stack_pop
[next_vm, [poped, *args]]
}
case method
# ~~~
in Proc => pro
new_vm.current_stack_frame_stack_push(pro.(args))
.current_stack_frame_line_num_add(1)
in Closure => closure
# ~~~
end
関数の定義
関数はすべてクロージャとなっており、外側の変数を捕捉できます。
->から始まる式が関数定義の式で、(-> (引数1 引数2 ...) 式本体1 式本体2 ...)という文法です。
関数の定義式はclosure命令1つのみにコンパイルされます。
コンパイル時、式本体1 式本体2 ...の部分をコンパイルするのですが、そのコンパイル結果は別のバイトコードとして保持しておきます。
closure命令の引数部分には「その別のバイトコードを指す番号」と「関数の引数の名前を,でつないだ文字列」が入ります。
compile_r = -> (exp) do
case exp
# ~~~
in Array
case exp.first
# ~~~
in :'->'
args = exp[1]
raise "argument `#{args.find { Symbol != _1 }}` in `#{exp}` must be symbol" unless args.all? { |a| Symbol === a }
codes = exp[2..]
code_table << codes.flat_map { |code| compile_r.(code) }
[ "closure@#{code_table.size - 1}@#{args.join(',')}" ] # 環境とコードをもったオブジェクトを作成する命令
closure命令の実行は関数の実行ではなく、関数定義の実行です。
まずClosureオブジェクトを新しく作成し、それをスタックにpushします。
作るClosureオブジェクトには、以下の3情報を格納しておきます。
-
closure命令の引数から取り出した関数の番号 -
closure命令の引数から取り出した引数の名前 - 現在のVMが実行しているスタックフレーム
case line
# ~~~
when /^closure@(\d+)@([\w,]*)/
function_num = $1.to_i
args = $2.split(',').map(&:to_sym)
closure = Closure[
function_num,
args,
vm.stack_frame_num
]
vm.current_stack_frame_stack_push(closure)
.current_stack_frame_line_num_add(1)
関数の実行
関数の実行時、Closureオブジェクトへ対してsend命令を行う処理はちょっと複雑です。
VMに新しいスタックフレームを作成し、そのスタックフレームにVMの制御を移します。
このとき、新しいスタックフレームの変数の名前と値の対応に「引数とその値の対応」を入れておきます。これにより引数の受け渡しを実現しています。
新しいスタックフレームの自身を呼び出したスタックフレームに、自身のスタックフレームの番号をセットします。こうすることで、新しいスタックフレームの終了後に現在のスタックフレームに戻ってこられるようにします。
自身を定義したスタックフレームには、Closureオブジェクトの作成時に入れておいた「Closureオブジェクト作成時のスタックフレーム番号」をセットします。これを辿ることで、関数の外側で定義された変数にアクセスすることができます。
def exec_send(vm, code_table, argc)
method_poped_vm, method = vm.current_stack_frame_stack_pop
new_vm, args = argc.times.reduce([method_poped_vm, []]) { |(memo_vm, args), _|
next_vm, poped = memo_vm.current_stack_frame_stack_pop
[next_vm, [poped, *args]]
}
case method
# ~~~
in Proc => pro
# ~~~
in Closure => closure
new_stack_frame = StackFrame[
[], # stack
closure.args.zip(args).to_h, # env
0, # line_num
new_vm.stack_frame_num, # call_parent_num
closure.stack_frame_num, # env_parent_num
closure.function_num # code_table_num
].freeze
new_stack_frame_num = new_vm.stack_frames.size
new_vm.current_stack_frame_line_num_add(1)
.insert_stack_frame(new_stack_frame_num, new_stack_frame)
.change_stack_frame_num(new_stack_frame_num)
end
end
継続の実装
第一級の継続を作るにあたって必要なものは、「残りの計算」の情報です。この「残りの計算」の情報は、すべてVM内に含まれています。
ということで、現在のVMを丸々保持した継続オブジェクトを作ることで、call/ccを実装しています。
継続の作成も実行も、コンパイルまでは普通の関数呼び出しと同じです（同じ構文ですし）。
実行について、継続に関する処理には以下の2つがあります。
-
callcc呼び出しの実行 -
callcc呼び出しの引数のクロージャの引数に渡される継続オブジェクトの呼び出し
ひとつめ、「callcc呼び出しの実行時」というのは、send命令でスタックから取り出したメソッド名がcallccであったときです。(callcc (-> (continuation) ~~~))のことです。
現在のVMを保持したContinuationオブジェクトを作り、それを引数にしてクロージャを実行します。
引数として渡されたContinuationオブジェクトは、他の変数に代入するなり呼び出すなり、ユーザー側が自由に扱えます。
def exec_send(vm, code_table, argc)
method_poped_vm, method = vm.current_stack_frame_stack_pop
new_vm, args = argc.times.reduce([method_poped_vm, []]) { |(memo_vm, args), _|
next_vm, poped = memo_vm.current_stack_frame_stack_pop
[next_vm, [poped, *args]]
}
case method
in :callcc
continuation = Continuation[new_vm.current_stack_frame_line_num_add(1)]
closure = args.first
new_stack_frame = StackFrame[
[], # stack
{ closure.args.first => continuation }, # env
0, # line_num
new_vm.stack_frame_num, # call_parent_num
closure.stack_frame_num, # env_parent_num
closure.function_num # code_table_num
].freeze
new_stack_frame_num = new_vm.stack_frames.size
new_vm.current_stack_frame_line_num_add(1)
.insert_stack_frame(new_stack_frame_num, new_stack_frame)
.change_stack_frame_num(new_stack_frame_num)
ふたつめ、「callcc呼び出しの引数のクロージャの引数に渡される継続オブジェクトの呼び出し」というのは、(continuation ~~~)のことです。
Continuationオブジェクトが呼び出されると、Continuationオブジェクトが保持していたVMを現在のVMと差し替えます。このとき、変数の名前と値の対応だけは現在のVMのものを保持しておきます。その後、プログラムの実行を続けます。
こうすることで、callcc呼び出し時の計算の残り、すなわち継続を扱うことができます。
def exec_send(vm, code_table, argc)
method_poped_vm, method = vm.current_stack_frame_stack_pop
new_vm, args = argc.times.reduce([method_poped_vm, []]) { |(memo_vm, args), _|
next_vm, poped = memo_vm.current_stack_frame_stack_pop
[next_vm, [poped, *args]]
}
case method
in :callcc
# ~~~
in Continuation => continuation
VM[ # continuation.vmの環境を現在の環境に差し替えている
continuation.vm.stack_frame_num,
continuation.vm.stack_frames.to_h { |continuation_stack_frame_num, continuation_stack_frame|
[
continuation_stack_frame_num,
StackFrame[
[*continuation_stack_frame.stack, args.first], # stack
new_vm.stack_frames[continuation_stack_frame_num].env, # env
continuation_stack_frame.line_num, # line_num
continuation_stack_frame.call_parent_num, # call_parent_num
continuation_stack_frame.env_parent_num, # env_parent_num
continuation_stack_frame.code_table_num, # code_table_num
].freeze
]
}
].freeze
おわりに
S式の簡単な処理系をRubyで実装してみました。
30行ほどのパーサー、60行ほどのコンパイラ、300行ほどのVMと評価器のコードで、それっぽい言語が作れました。
他に追加してみたい機能として、リスト処理、使われなくなったスタックフレームをGCする機能、マクロ機能などがあります。いずれ実装してみたいと思います。
最後まで読んでいただきありがとうございました。この記事がなにかの参考になれば嬉しいです。
参考
-
shigoto-lisp: はじめてLispを実装するときに 〜 適用編 - Qiita https://qiita.com/t-sin/items/6114208e10d57a9b2ab8
-
Schemeの実装におけるスタックフレーム(Draft) https://practical-scheme.net/docs/stack-j.html
-
n月刊ラムダノート Vol.3, No.1 #2 「継続」のひみつ