Rで書く
Rコンパイラ

@igjit

きっかけ

https://www.sigbus.info/compilerbook/

低レイヤを知りたい人のためのCコンパイラ作成入門
低レイヤを知りたい人のためのCコンパイラ作成入門

コンパイラ作るのってすごく難しそうなイメージだったけど

Cのソースコードを

int main() {
  return 42;
}

x86-64アセンブリに変換する

.intel_syntax noprefix
.global main
main:
        mov rax, 42
        ret

(アセンブリから実行ファイルの変換はGCCでやる)

文字列を読んで文字列を書ければコンパイラは作れる

じゃあRでもできるんじゃね?

どの言語でどの言語のコンパイラを書いても良いはず

ならば

RでRのコンパイラを書いてみよう。

やってみた。

nrc

https://github.com/igjit/nrc

インストール

devtools::install_github("igjit/nrc")

(現在Linuxにしか対応してないので他のOSの場合はDockerとか使ってください。)

あそびかた

packageを読み込むと

> library(nrc)

Rのコードをコンパイルできる

> compile("1+2")
.intel_syntax noprefix
.global main
main:
  push rbp
  mov rbp, rsp
  sub rsp, 208
  push 1
  push 2
  pop rdi
  pop rax
  add rax, rdi
  push rax
  pop rax
  mov rsp, rbp
  pop rbp
  ret

コンパイルしてアセンブル

> compile("1+2") %>% assemble
[1] "/tmp/RtmpW7m1KT/file760c7d79428b"

実行ファイルが出力される

コンパイルしてアセンブルして実行

> compile("1+2") %>% assemble %>% execute
[1] 3

変数も使える

> "a <- 2; a + 40" %>% compile %>% assemble %>% execute
[1] 42

代入演算子は <- (今のところ唯一のRっぽさ)

テキストの ステップ6: ==と!=を追加する までは大体実装

ここから先はCとRで乖離がありそう

  • ファーストクラスの関数
  • スコープ規則

しくみ

コンパイルの流れ

compile <- function(s) {
    s %>%
        tokenize %>%
        parse %>%
        generate
}

tokenize

単語に分割する

正規表現を使って雑に実装

#' @import stringr

tokenize <- function(s) {
    s %>%
        str_replace_all("(<-|==|!=|[()+\\-*/=;])",
                        " \\1 ") %>%
        str_trim %>%
        str_split("\\s+")
}
> tokenize("a=2;a+40")
[[1]]
[1] "a"  "="  "2"  ";"  "a"  "+"  "40"

parse

文法にそって解釈する

(1 + 2) * 3

a = 40 + 2

詳細は 再帰下降構文解析 参照

generate

アセンブリを生成

詳細は スタックマシンへのコンパイル 参照

使ったパッケージ

実装が捗るやつ

パッケージ作成が捗るやつ

楽をするためにテストを書く

感想

楽しい!

コンパイラ作成は大変楽しい作業です。

低レイヤを知りたい人のためのCコンパイラ作成入門

3(0)日でできる! Cコンパイラ自作入門

まとめ

Rでもコンパイラを作れるし低レイヤを学べる。

コンパイラを作るのは楽しい。

なのでみなさんもコンパイラを作りましょう。

Enjoy!