3
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

R言語で簡単な自作言語のコンパイラを書いた

Last updated at Posted at 2023-12-24

これは R言語 Advent Calendar 2023 の25日目の記事です。一つ前の記事は Rでサンタクロース です。

image.png

簡単な自作言語のコンパイラをいろんな言語で書いてみるシリーズ 27番目の言語は R言語です。

できたもの

サイズ

  $ wc -l mrcl_*.R lib/utils.R
  355 mrcl_codegen.R
   89 mrcl_lexer.R
  321 mrcl_parser.R
  120 lib/utils.R
  885 合計

動作例

  $ echo '
  func add(a, b) {
    return a + b;
  }

  func main() {
    call add(1, 2);
  }
' | Rscript mrcl_lexer.R | Rscript mrcl_parser.R | Rscript mrcl_codegen.R

  # ↓ アセンブリが出力される

  call main
  exit
label add
  push bp
  mov bp sp
  mov reg_a [bp:2]
  push reg_a
  mov reg_a [bp:3]
  push reg_a
  pop reg_b
  pop reg_a
  add reg_a reg_b
  mov sp bp
  pop bp
  ret
  mov sp bp
  pop bp
  ret
label main
  push bp
  mov bp sp
  mov reg_a 2
  push reg_a
  mov reg_a 1
  push reg_a
  _cmt call~~add
  call add
  add sp 2
  mov sp bp
  pop bp
  ret

... snip ...

移植元

こちらのコンパイラ部分が移植元です。

<自作言語処理系(Ruby版)の説明用テンプレ>

自分がコンパイラ実装に入門するために作った素朴なトイ言語 Mini Ruccola とその処理系です。概要は以下のような感じ。

  • 小規模: コンパイラ部分は 1,000 行程度
    • 無理して短く書くようなことはせず、読みやすさ優先で素直に書いてこのくらい
  • pure Ruby
    • 標準ライブラリ以外のライブラリ不要。ブラックボックスなしですべてを掌握できるように。
  • x86風の自作VM向けにコンパイルする
  • ライフゲームのために必要な機能だけ
    • 変数宣言、代入、反復、条件分岐、関数
    • 演算子
      • +, *, ==, != のみ
      • 左結合(優先順位は ( ) で明示)
    • 型なし(値は符号付き整数のみ) ... B言語や BCPL に似てる?
  • 作ったときに書いた備忘記事
  • 本体には含めていない後付けの機能など
    • 真偽値リテラル / break / if/else / 単項マイナス / パーサの別実装 / 静的型検査 / etc.
  • セルフホスト版
    • 育てていってセルフホストまでできました
  • 他言語への移植
    • コンパイラ部分のみ
    • Python, Java, PHP, TypeScript, Julia, Dart, OCaml, Haskell, Rust, Zig, V, Forth など、2023-12-25 の時点では 27言語
  • 作り方は製作過程のメモに全部書いています。
    • この通りにやれば誰でも同じものが作れる、と言いたいところだけどいろいろ改善点が見えてきたので全体的に改訂したい……
    • 凝ったことはしていないので Ruby を知らない人でも雰囲気くらいは分かるんじゃないかと。

<説明用テンプレおわり>

メモ

R言語に入門したての人が付け焼き刃でむりやり書いたという感じでこなれてないと思いますが、とにかく動いてはいます。

20年近く前にちょっとだけ書いたことありましたが、忘れてしまっているので今回はほぼゼロからの再入門でした。R 自体もたまーにちょっと触るという程度。


何点かメモ。大きく詰まったところはありませんでした。

  • 関数などの命名が(自分視点では)若干独特で「よく知らない文化圏」感がある
    • 単に名前の問題なので分かってしまえば問題なし
  • リストの扱い
    • リストの要素に添字でアクセスする場合は xs[[n]]
    • 今回は定型的なことしかしてないので書き方が分かってしまえば問題なし
    • ベクトル、リスト、データフレームが一級市民的な扱いで、それを前提とした言語になっているという印象
  • 関数の遅延評価
    • と聞いて少し身構えたけど、気を使って書かないとハマるといった場面はなかった(今回書いた範囲では)
    • 軽く使うだけならあまり意識する必要はなくて、単に「こういう構文なんだな」くらいの意識で使える(今回書いた範囲では)
    • switch なんかも普通の関数呼び出し(関数適用?)として記述できておもしろい

今回書いた範囲ではいずれも一定のパターンに納まるので、慣れてしまえばなんとかなって、割と普通のスクリプト言語っぽい書き味だなと感じました。

遅延評価といえば……

たらい回ししたくなりますよね。

tarai <- function(x, y, z) {
  # print(x)
  if (x <= y) {
    y
  } else {
    tarai(
      tarai(x - 1, y, z),
      tarai(y - 1, z, x),
      tarai(z - 1, x, y)
    )
  }
}

args <- commandArgs(trailingOnly = TRUE)
x = as.numeric(args[[1]])
y = as.numeric(args[[2]])
z = as.numeric(args[[3]])

print(tarai(x, y, z))
  $ time Rscript tarai.R 12 6 0
[1] 12

real    0m0.173s
user    0m0.127s
sys     0m0.052s

  $ time Rscript tarai.R 100 50 0
[1] 100

real    0m0.147s
user    0m0.114s
sys     0m0.035s

R はたらい回しが速い言語!

参考:

(詳しいところは私も理解できてなくて、遅延評価だと速いということだけ知っています)

この記事を読んだ人は(ひょっとしたら)こちらも読んでいます

3
3
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
3
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?