継続を扱えるLispの簡易的な処理系をRubyで実装

プログラミング言語の処理系を実装してみたく思い、LispのようなS式を実行する簡易的な処理系を書いてみました。

「第一級の継続(call/cc)を実装する」というのが一番の目標でした。

ひとまずは動くものができたと思うので、実装するにあたって考えたこと、試したことなどを書き残しておこうと思います。

ソースコードはこちらとなります。

https://github.com/tetetratra/mini_lisp

## 言語を軽く説明

Rubyで実装したS式の簡単な処理系です。

VM(バーチャルマシン)実行方式を採用しました。ソースコードを独自のバイトコードに変換して、それを独自のVMで実行します

扱える値は整数と文字列くらいです。組み込みの関数名などは若干Rubyに寄せています。if、while、変数などは実装してあって、こんなコードが動きます。

```lisp
(= a 5)
(= sum 0)
(while (!= a 0)
  (= sum (+ sum a))
  (= a (- a 1))
)
(p sum) ; => 15
```

関数も定義できます。再帰もいけます。

```lisp
(= sum (-> (x)
  (if (== x 0)
    0
    (+ x (sum (- x 1)))
  )
))
(p (sum 5)) ; => 15
```

関数はクロージャとなっています。
たとえば以下では、「「呼び出すたびに`a`が加算されてその`a`を返す関数」を返す関数」を定義しています。

```lisp
(= increment (-> (init)
  (= a init)
  (-> () (= a (+ a 1)))
))
(= inc (increment 10))
(p (inc)) ; => 11
(p (inc)) ; => 12
(p (inc)) ; => 13
```

第一級の継続があります(多分)。

継続を使うことでループや大域脱出の機能をユーザー側で実装できてすごいです。

```lisp
(= 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
```

```lisp
(= 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))`は次のような流れでパースされます。

```ruby
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 ...)`という形式になっています。
再帰的に辿り、`命令`の種類を見て対応するバイトコードを吐きます。

コードの雰囲気だけ掴んでもらえるとです。

```ruby:compiler.rb
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行目からの残りはこんな感じです。

```ruby
"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されます。

各情報の詳細はおいおい見ていくとして、ここからは各種機能のコンパイルと実行方法の紹介に移りたいと思います。

## 変数

変数を定義する構文は次のコードでコンパイルされます。

```ruby:compiler.rb
      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@変数名`命令の実行時は、命令列の引数として得た`変数名`をキーに、スタックのトップに置かれているオブジェクトを値として、`変数の名前と値の対応`に追加します。

```ruby:evaluator.rb
          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`命令を配置しています。

```ruby:compiler.rb
          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,
            ]
```

```ruby:evaluator.rb
          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`に入れています。

```ruby:compiler.rb
      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して終了です。

```ruby:evaluator.rb
      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`命令の引数部分には「その別のバイトコードを指す番号」と「関数の引数の名前を`,`でつないだ文字列」が入ります。

```ruby:compiler.rb
      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が実行しているスタックフレーム



```ruby:evaluator.rb
          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オブジェクト作成時のスタックフレーム番号」をセットします。これを辿ることで、関数の外側で定義された変数にアクセスすることができます。

```ruby:evaluator.rb
      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オブジェクトは、他の変数に代入するなり呼び出すなり、ユーザー側が自由に扱えます。

```ruby:evaluator.rb
      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`呼び出し時の計算の残り、すなわち継続を扱うことができます。

```ruby:evaluator.rb
      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

- なんでも継続 http://practical-scheme.net/docs/cont-j.html

- n月刊ラムダノート Vol.3, No.1 #2 「継続」のひみつ