強くなくても作ってみるコンパイラ

# 概要

Lisp を C へ変換するコンパイラの Go 実装

github.com/kawakami-o3/PLC

フィボナッチ数を計算させてみるまで

Qiitaで記事書きました。

[技術も腕力もないけどコンパイラを自作してみた](https://qiita.com/kawakami_o3/items/a788989caeaec94dddf8)

---
# 自己紹介 kawakami

* Twitter: kawakami_o3
* GitHub: kawakami-o3
* 新宿のゲーム会社でサーバー書いてます
* サーバーをPHP, Java, C++
* ツールなどをRuby, Python, Go


---
# 発端

Turing Complete FM

東大CPU実験で自作CPUにUnixを移植した話

```
簡単なコンパイラを作るのは難しくない
```

ホントか？

自分みたいなヘタレでもできるのか？

---
# 目標はなるべく低く

頓挫したら元も子もないので、できるところまでレベルを下げる

* Cコンパイラ、無理
* Lispならインタプリタ作ったことある
  * github.com/kawakami-o3/yaLispy
  * 6つの言語で実装。Go実装もあるよ。
* 出力形式
  * アセンブリ、無理
  * LLVM IR、できそうだけどコード量ががが
  * C、イケそうな気がする

---
# 純Lisp

```
LISP のうち、ごく基本的な要素だけからなる方言の一種(wikipedia)
```

データは、アトムとペア

atom, eq, car, cdr, cons, if, quote, lambda, define

これだけでいろいろできる。evalも作れる。

今回はフィボナッチ数の計算

```scheme
(progn
    (define fib (lambda (n)
        (if (eq n 0)
            0
            (if (eq n 1)
                1
                (+ (fib (- n 1)) (fib (- n 2)))))))
    (print (fib 10)))
```


---
# 実装してみる `print`

```scheme
(print 1 2)
```

これを
( ＾ω＾)
⊃)　 (⊂

( ＾ω＾)
≡⊃⊂≡
こうじゃ…

```c
#include<stdio.h>

int main(void) {
	printf("%d %d %d\n", 1, 2);
}
```

---
# ちなみに LLVM IRだと


```scheme
(print 1 2)
```

```llvm
@.str.1 = private unnamed_addr constant [7 x i8] c"%d %d\0A\00", align 1

define i32 @main() {
  %1 = alloca i32, align 4
  store i32 1, i32* %1, align 4
  %2 = load i32, i32* %1, align 4

  %3 = alloca i32, align 4
  store i32 2, i32* %3, align 4
  %4 = load i32, i32* %3, align 4

  %5 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds([7 x i8], [7 x i8]* @.str.1, i32 0, i32 0), i32 %2, i32 %4)

  ret i32 0
}
declare i32 @printf(i8*, ...)
```


---
# `+`関数

```scheme
(print (+ 1 2) (+ 3 4 5))
```

```c
int plus_0 = 1 + 2;
int plus_1 = 3 + 4 + 5;
printf("%d %d\n", plus_0, plus_1);
```
`+` で連結するだけ

---

# `define`

```scheme
(progn
  (define a 1)
  (print a))
```

```c
int a = 1;
printf("%d\n", a);
```

`progn`は順々にコードを評価して出力しているだけなので割愛

---
# `lambda`

```scheme
(print (
  (lambda (x) (+ x 1))
  2
))
```

```c
int lambda_0(int *args) {
	int x = args[0];
	int add_0 = x + 1;
	return add_0;
}

int main(void) {
	int lambda_0_args[] = {2};
	printf("%d\n", lambda_0(lambda_0_args));
}
```

* `lambda`を使ったら順次関数として定義
* 引数は配列にくるんで渡すだけ


---
# `define` と `lambda`

```scheme
(define add1
  (lambda (x)
    (+ x 1)))
```

```c
int (*add1)(int*);
int lambda_0(int *args) {
	int x = args[0];
	int add_0 = x + 1;
	return add_0;
}

int main(void) {
	add1 = lambda_0;
}
```

どこで呼び出されるかわからないので、とりあえずグローバルに

---
# `eq`

```scheme
(eq 1 2 3)
```

```c
int eq_0 = 1==2 && 1==3;
```

---
# if

```scheme
(if (eq 1 2)
  10
  20)
```

```c
int if_0;
int eq_0 = 1==2;
if (eq_0) {
	if_0 = 10;
} else {
	if_0 = 20;
}
```

---
# フィボナッチ数を求めてみる

```scheme
(progn
	(define fib (lambda (n)
		(if (eq n 0)
			0
			(if (eq n 1)
				1
				(+ (fib (- n 1)) (fib (- n 2)))))))
	(print (fib 10)))
```

---
# フィボナッチ数を求めてみる

```c
#include<stdio.h>

int (*fib)(int*);
int lambda_1(int *args){
  int n = args[0];
  int if_1;
  int eq_2 = n == 0;
  if (eq_2) {
    if_1 = 0;
  } else {
    int if_3;
    int eq_4 = n == 1;
    if (eq_4) {
      if_3 = 1;
    } else {
      int minus_5 = n;
      minus_5 -= 1;
      int fib_args_6[] = {
        minus_5
      };
      int minus_7 = n;
      minus_7 -= 2;
      int fib_args_8[] = {
        minus_7
      };
      int plus_9 = 0;
      plus_9 += fib(fib_args_6);
      plus_9 += fib(fib_args_8);
      if_3 = plus_9;
    }
    if_1 = if_3;
  }

  return if_1;
}

int main(void) {
  fib = lambda_1;
  int fib_args_2[] = {
    10
  };
  printf("%d\n" , fib(fib_args_2));
}
```

---
# まとめ

lisp2c コンパイラを作ってみた。

テキトーに作ってみるだけなら確かに簡単

今回のコンパイラではlispなのにリスト処理できない
_最新版は設計見直しして、evalもコンパイルできる_

---
# 宣伝

lispに興味を持ち始めた方

来週月曜 19:30

五反田

Shibuya.lisp lispmeetup #66

https://lisp.connpass.com/event/93911/