好きな言語ではじめる
低レイヤゆるっと入門

@igjit

@igjit

R言語 - Wikipedia

低レイヤゆるっと入門

今日紹介するもの

  • コンパイラ
  • Java VM
  • nand2tetris

私はRで実装したけど、他の言語でもできるはず。

みんな好きな言語でチャレンジしてほしい。

コンパイラ

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

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

Cのソースコードを

int main() {
  return 42;
}


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

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

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

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

じゃあどの言語でもできるんじゃね？

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

私は

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

nrc

https://github.com/igjit/nrc

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

四則演算が動くようになったけど

ここから先はCとRで乖離がある

関数

Rの関数はファーストクラスオブジェクト

add2 <- function(x) x + 2

add2(40)

単なる値

add2 <- function(x) x + 2

add2(40)

無名関数もあり得る

(function(x) x + 2)(40)

どうやってコンパイルすれば良いんだ？

https://github.com/andycraig/functional-compiler-presentation

おかげで関数オブジェクトの生成、関数呼び出しを実装できた。

> compile("add2 <- function(x) x + 2; add2(40)") %>% assemble %>% execute
[1] 42


Thanks @andrew_cb2!

テキストと違う言語を実装しようとしてつまづいたが、それも含めて楽しかった。

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

みんなも好きな言語で実装しよう。

Java VM

きっかけ

「他の言語でも JVM は実装可能」

公式ドキュメントにも書いてある

To implement the Java Virtual Machine correctly, you need only be able to read the class file format and correctly perform the operations specified therein.

https://docs.oracle.com/javase/specs/jvms/se23/html/jvms-2.html

「クラスファイルを読めて、そこに書いてある命令を実行できればJVMを実装できるよ」

私はRで実装した。

jvmrr

https://github.com/igjit/jvmrr

Javaのコードを

public class Hello {
  public static void main (String[] args) {
    System.out.println("Hello, world.");
  }
}

コンパイルしたら

$ javac Hello.java

Rで読み込んで

> library(jvmrr)
> java_class <- read_class("Hello.class")

実行できる

> java_class %>% execute
Hello, world.

Fizz Buzzも

class FizzBuzz {
  public static void main(String[] args) {
    for (int i = 1; i <= 20; i++) {
      if (i % 15 == 0) {
        System.out.println("FizzBuzz");
      } else if (i % 3 == 0) {
        System.out.println("Fizz");
      } else if (i % 5 == 0) {
        System.out.println("Buzz");
      } else {
        System.out.println(i);
      }
    }
  }
}

コンパイルしたら

$ javac FizzBuzz.java

R上で動く

> read_class("FizzBuzz.class") %>% execute
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
16
17
Fizz
19
Buzz

詳細は

Java VM 自作 方法

みんなも好きな言語で実装しよう。

nand2tetris

https://www.oreilly.co.jp/books/9784873117126/

「コンピュータを理解するための最善の方法はゼロからコンピュータを作ることです。」

コンピュータシステムの理論と実装

通称 nand2tetris (Nand to Tetris)

コンピュータの構成要素

  • ハードウェア
  • ソフトウェア
  • コンパイラ
  • OS

をひとつずつ実装していく

NANDゲートから始まって

最終的にゲームが動くようになるよ

(Nand to Tetrisと言いつつテトリスではない)

この本で実装する階層

アプリケーション
OS
コンパイラ
バーチャルマシン
アセンブラ
機械語
ハードウェア

ハードウェアはHDLで記述

アプリケーション
OS
コンパイラ
バーチャルマシン
アセンブラ
機械語
ハードウェア

これらは好きな言語で実装できる

アプリケーション
OS
コンパイラ
バーチャルマシン
アセンブラ
機械語
ハードウェア

私はRで実装した。

順に紹介します。

1. アセンブラ

アプリケーション
OS
コンパイラ
バーチャルマシン
アセンブラ
機械語
ハードウェア

アセンブラ

アセンブリ言語をバイナリに変換する

アセンブリ言語を

@2
D=A
@3
D=D+A
@0
M=D

バイナリに変換

0000000000000010
1110110000010000
0000000000000011
1110000010010000
0000000000000000
1110001100001000

ハードウェアに対する命令なので低水準

@2
D=A
@3
D=D+A
@0
M=D

ちなみにこれは 2 + 3 を計算するコード

Rによるアセンブラの実装

assembler

2. バーチャルマシン

Virtual Machine (VM)

抽象化されたコンピュータ

この本で作るのはVM変換器 (VM translator)

VMコードをアセンブリコードに変換する

アプリケーション
OS
コンパイラ
バーチャルマシン
アセンブラ
機械語
ハードウェア

2 + 3 を計算するVMコード

push constant 2
push constant 3
add

アセンブリより読みやすい

スタックマシン (stack machine)

という計算モデル

RによるVM変換器の実装

vmtranslator

3. コンパイラ

高級言語をVMコードに変換する

アプリケーション
OS
コンパイラ
バーチャルマシン
アセンブラ
機械語
ハードウェア

Jack言語のコード

class Main {
   function void main() {
      do Output.printString("Hello world!");
      do Output.println();
      return;
   }
}

普通に読める

RによるJackコンパイラの実装

jackanalyzer

実装にかかった行数

行数
アセンブラ 206
VM変換器 323
コンパイラ 788

強力な抽象は実装が大変

行数
アセンブラ 206
VM変換器 323
コンパイラ 788

でも楽しい。

みんなも好きな言語で実装しよう。

まとめ

低レイヤの入り口を紹介

  • コンパイラ
  • Java VM
  • nand2tetris

動くものを作るのは楽しい。

ものが動く仕組みを知ることは楽しい。

Happy hacking!