概要
Lisp を C へ変換するコンパイラの Go 実装
github.com/kawakami-o3/PLC
フィボナッチ数を計算させてみるまで
Qiitaで記事書きました。
自己紹介 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も作れる。
今回はフィボナッチ数の計算
(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
(print 1 2)
これを
( ＾ω＾)
⊃) (⊂
( ＾ω＾)
≡⊃⊂≡
こうじゃ…
# include<stdio.h>
int main(void) {
printf("%d %d %d\n", 1, 2);
}
ちなみに LLVM IRだと
(print 1 2)
@.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*, ...)
+関数
(print (+ 1 2) (+ 3 4 5))
int plus_0 = 1 + 2;
int plus_1 = 3 + 4 + 5;
printf("%d %d\n", plus_0, plus_1);
+ で連結するだけ
define
(progn
(define a 1)
(print a))
int a = 1;
printf("%d\n", a);
prognは順々にコードを評価して出力しているだけなので割愛
lambda
(print (
(lambda (x) (+ x 1))
2
))
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
(define add1
(lambda (x)
(+ x 1)))
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
(eq 1 2 3)
int eq_0 = 1==2 && 1==3;
if
(if (eq 1 2)
10
20)
int if_0;
int eq_0 = 1==2;
if (eq_0) {
if_0 = 10;
} else {
if_0 = 20;
}
フィボナッチ数を求めてみる
(progn
(define fib (lambda (n)
(if (eq n 0)
0
(if (eq n 1)
1
(+ (fib (- n 1)) (fib (- n 2)))))))
(print (fib 10)))
フィボナッチ数を求めてみる
# 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