ブートストラッピングでコンパイラを作ろう

1 ：09/12/27 〜 最終レス ：11/11/23

言語Lのコンパイラを言語Lで実装するにはブートストラッピングをしますが、
それをできるだけ原始的なレベルからやってみようと思います。
自分が実装するので、突っ込みお願いします。
コンパイラの勉強が主目的で、面白い言語を作ることは目的ではありません。
具体的には>>2

2 ：

使用ツール: エディタ・アセンブラ・リンカのみ
手順:
1. アセンブラでLのものすごく小さなサブセット言語L1のコンパイラを作る
2. L1でL1のコンパイラを作る
3. L1で少しだけ多機能なL2言語のコンパイラを作る (これを繰り返す)
(オプショナルな目標)
4. どっかの段階でlex/yaccに相当するものをLで作る

3 ：

×: 3. L1で少しだけ多機能なL2言語のコンパイラを作る (これを繰り返す)
○: 3. Lnで少しだけ多機能なLn+1言語のコンパイラを作る (これを繰り返す)

4 ：

誰も見てないかもですが・・・
一番最初のコンパイラの方針を考えました。
アセンブラで作るのでめちゃめちゃ簡単な言語(ほぼアセンブリ言語)にします。
- 標準入力からコード入力 → アセンブリ言語にコンパイル → 標準出力に出力
- リンカは手動で実行することにする
- 制御構造はifとgotoのみ
- 整数型のみ
- ハッシュテーブルがまだ無いので、識別子はx0，x1，…:レジスタ変数，y0，y1，・・・自動変数.の形式のみ。
- 関数は実装する
- 再帰下降型でパース

5 ：

具体的な対象CPUやOSが書いてないよね

6 ：

>>5
CPU:x86系
OS:Linux
でやります。
今自分が使ってるのは
OS : Linux version 2.6.18-6-686 (Debian)
as/ld: 2.17
です。

7 ：

それあとほぼあらゆる問題が「GCCのソース見ろ」で終わりそうですね

8 ：

期待する

9 ：

>>7
読むだけより作った方が勉強になることもあるかと思いますので。
githubに空のリポジトリ作りました。
ttp://github.com/nineties/growl
開発コードはgrowl(growing language)です。
明日からちょびちょび頑張って作っていきますので応援よろしくお願いします。

10 ：

GCC のソースを見るなんて筋が悪すぎる

11 ：

そう言えば、GCCは自由を守るために、わざとおかしな造りにしてるって聞いたことがあった気がする

12 ：

それでもっと自由な LLVM に置き換えられる訳か…

13 ：

作り始めました。
とりあえず、flush/getc/putc/exitだけ実装しました。
まだただのechoプログラムです。
続きは夜やります。
字句解析器作ります。

14 ：

>>1
今時の実装だとNativeコード生成じゃなく
仮想プロセッサのコードへのコンパイラを作って
仮想プロセッサ->JIT->ネイティブ
の方がいいのじゃなかろうか？

15 ：

smalltalk みたいだね

16 ：

>>14
自分もそう思います。
ただ、growlの言語機能が貧弱なうちは出来るだけ単純な構造で作ります。
今ざっくりと考えているロードマップ:
growl0 : アセンブラで実装 (超シンプルに作る)
growl1 : growl0で実装。制御構造・型の種類などを増強。
growl2 : growl1で実装。ヒープの利用・データ構造定義などを可能にする。
growl3以降 : 後で考える。
データ構造が定義できるようになれば、ハッシュテーブル等の利用が可能になり、
構文木も作れるようになるので、実装の幅が広がります。
growl2まではコンパイラと言うよりはほとんどテキストフィルタの様な物になると思います。

17 ：

あけおめ
>>1が成就しますように

18 ：

あけましておめでとうございます。
>>17
ありがとうございます。頑張ります。

19 ：

正月も明けたので再開します。明けましておめでとうございます。
字句解析ですが、いずれ字句解析器生成器を作る事も考えて、状態遷移モデルで書く事にしました。
状態遷移表ベースじゃなく遷移図ベースにします。

20 ：

字句解析器を
- 整数定数・キャラクタ定数・文字列定数・識別子・その他記号
まで実装してコミットしました。
次は予約語を実装して、その後コンパイラ本体の実装に入ります。

21 ：

現状の動作例：
% cd glc0
% cat test.c
#include <stdio.h>
int main(void) {
puts("Hello World");
}
% make
% ./glc0 < test.c
SYMBOL #
IDENT include
SYMBOL <
IDENT stdio
SYMBOL .
IDENT h
SYMBOL >
IDENT int
IDENT main
SYMBOL (
IDENT void
SYMBOL )
SYMBOL {
IDENT puts
SYMBOL (
STRING "Hello World"
SYMBOL )
SYMBOL ;
SYMBOL }

22 ：

lexerに予約語実装しました。(if goto returnのみ)
次はコンパイラ本体を書きます。
アセンブリでヒープ使うコード書きたく無いので、growl0では構文木を作らずに
パースしつつ逐次コード生成します。
growlの言語仕様は漠然と考えてますが、具体的には作りながら決めてきます。
特に以下の物についてみなさんのアイデアを頂けると嬉しいです。
1. Cのプリプロセッサ(include含め)のような事は止めたいです。

23 ：

(途中で切れちゃいました)
1. Cのプリプロセッサ(include含め)の代わり
テンプレートベースのメタプログラミングを出来るようにするつもり。
C++的なのではなく、template haskellみたいに、growl自身でメタプログラミングできるようにしたい。
2. データ構造定義
- オブジェクト指向にはしない予定
- variant・パターンマッチを使えるようにする
3. メモリ管理関係
- GCを搭載するかどうかは悩み中
- shared_ptr的なのは用意したい

24 ：

growl0で書いた以下のコードがコンパイルできるようになりました。
export main;
main: () {
syscall(1, 0); # exit(0)
};
まだ変数など一切使えませんが、結構早くアセンブラを抜け出せそうです。

25 ：

乙
とか思ったが夜くらい寝ろｗ

26 ：

>>25 すいません(^^;
- グローバル変数の定義
- 関数コール f(a,b,c)
- 間接代入 *x = ..
などを実装しました。
値の管理はpush/popしまくるという大変非効率的な実装になっています。
構文木も識別子表もないので仕方ないです。
グローバル変数はアセンブリ言語レベルで名前が付けられるので簡単ですが、
ローカル変数などは>>4のような方針で作ります。

27 ：

こんな感じのコードがコンパイルできるようになりました。↓
プログラミング言語っぽくなってきました。
#
# growl - generation 1
# Copyright (C) 2009 nineties
#
# $Id: stdlib.gl 2010-01-10 21:00:57 nineties $
export STDIN_FD;
export STDOUT_FD;
export STDERR_FD;
STDIN_FD : 0;
STDOUT_FD : 1;
STDERR_FD : 2;
# system calls
SYS_EXIT : 1;
SYS_READ : 3;
SYS_WRITE : 4;
export exit;
exit: (p0) {
# p0 : status
syscall(SYS_EXIT, p0);
};

28 ：

しばらくgrowlの構文の設計とそれに伴うコードの書き直しをしていました。
現状：配列とか書けるようになりました。↓
まだ代入構文とかありません。
あと、growl0では型の概念がないんですが、char配列とlong配列をどうやって区別するか悩み中です。
スカラ型についてはlong統一という方針です。
ary : [1,2,3];
f: (p0) {
return ary[p0];
};
export main;
main: () {
exit(f(2));
};

29 ：

growl0でHello World書いてみました。今のところはこれが精一杯です。
export main;
STDOUT_FD : 1;
SYS_EXIT : 1;
SYS_WRITE : 4;
main: () {
syscall(SYS_WRITE, STDOUT_FD, "Hello World\n", 12);
syscall(SYS_EXIT, 0);
};
現状だと文字列リテラルはtextエリアのど真ん中に確保して、
jmpで飛び越すというコードにコンパイルされます(笑)
後で直します。
movl STDOUT_FD,%eax
pushl %eax
jmp _lbl0
.section .rodata
_lbl1: .string "Hello World\n"
.text
_lbl0:
movl $_lbl1,%eax
pushl %eax

30 ：

>>29
実行形式に落としてからobjdump -dにかけてみれ。
まあ.sが読みにくいので直したほうがいいとは思うが。

31 ：

>>30
なるほど、コンパイル時に並び替えしてくれるんですね。知りませんでした。
てことはjmpもいらないのか〜。

32 ：

ず〜っと規制で書き込めませんでしたorz
現状、rowl1の実装を進めています。
アセンブリからdlopen()をコールする為のコードを書いている所です。

33 ：

そろそろ完成したかな？

34 ：

リポジトリの更新も止まってるし
てこずってるよう棚

35 ：

レポジトリ見るとallocとかが実装され始めてるようだね。
1/22から更新がないようだがガンガレ

36 ：

久しく間があいてしまってすいません。
しばらく趣味に裂く時間がありませんで停滞しておりました。
そろそろペースを戻していきたいと思います。
dlopen()の実装は流石に挫折しましたのでglibcを直接呼ぶ方向にしたいと思います。
がんばります。

37 ：

これは良いものが出来そうですね。
Linuxが普及する原動力になると思います。
期待しています。

38 ：

↑なにいってんだこいつ

39 ：

↓なにいってんだこいつ

40 ：

これは良いものが出来そうですね。
Linuxが普及する原動力になると思います。
期待しています。

41 ：

↑なにいってんだこいつ

42 ：

とりあえず>>1すげぇな・・・・
とてもじゃないが俺には出来ん・・・
でも勉強に見させてもらうよ

43 ：

>>42
どうもありがとうございます。頑張りますので応援してください。
現在rowl2コンパイラを実装していますが、
Hindley-Milnerの型システム
GC
メタプログラミング機能
などを一気に実装しようとして大分苦しくなってきました。
なので方針を変更して、rowl2では型システムのみ追加することにして高級な機能は先送りに
しようと思います。

44 ：

>>43
了解。
応援させていただきます。

45 ：

経過報告です。型システムを黙々と実装中です。
で、単純なHindley-Milnerだと使いにくい言語になると思うんで、何らかの拡張を考えてます。
一つは名前付きのタプルフィールドです。
p : (x : 0.0, y : 0.0);
などと書けて、p.x、p.yとアクセスできるようにしたいと思います。
これは多分kindを使って、健全性・完全性を保ってできると思います。
それから型による多重定義です。
例えば 1 + 1、 1.0 + 1.0、などと書けるようにしたいと思います。
これは安直にやると完全性を壊してしまいそうな気がするので、勉強中です。
もし、よい論文など知っている方がいましたら教えていただけると嬉しいです。

46 ：

きちんと構文解析してexpressionの型を決めていけばできると思うけど、
もっと簡単にやる方法あるのかな。
応援してる。

47 ：

型推論の方針は定まりました。健全性と完全性はある程度犠牲にして、
多重定義・多相的な定数リテラルをサポートできるようにしたいと思います。
それから↓に触発されてrowlでのOS作りに挑戦することにしました。
【超高速】C/C++に代わる低級言語を開発したい
ttp://pc12.2ch.net/test/read.cgi/tech/1268843875/
理想とかあまり考えないで、まったり作ります。
まだ何も出来ていないですけど、
rowl/os/rowlos.img
がそれです。QEMUで実行できます。

48 ：

間違ってもその痛いスレを参考にしちゃだめだよ
どっちかっつーとひげぽんさん目指した方がいい(割とマジで言うけどあの人の技術面でなく取り組み方の方ね）

49 ：

新しいネタを頂いただけで、言語設計は自分の好きなようにやってこうと思います。
こっちはアセンブリのみで実装という縛りがあるんで、逆にあまり言語仕様で悩まなくていいですね。
ひげぽんさんはホント尊敬してます。特にやる気をあれだけ維持出来るのがすごいです。

50 ：

ひげぽんなんていろいろ手を出してどれも中途半端
他の人のコードを何年も放置した後とりいれて顰蹙かったり
真似したら駄目

51 ：

人がどういうやり方してるかあまり気にしても仕方ないので、ひとりでやってる限りは適当にやります。
忠告ありがとうございます。
経過報告です。
型推論の実装は目処が立ったので、バックエンドの実装に入りました。
rowl1では
型付きCore言語→三番地コード→アセンブリ
というパスでやることにします。三番地コードを突っ込んだのは、値管理をスタックに頼らないで、レジスタ割り当てをちゃんとしようと思った為です。

52 ：

生存解析を三番地コードに実装しました。(liveness.rl)

53 ：

レジスタ割り当てを実装しました。グラフカラーリングで作りました。
これで、型付きCore→アセンブリが繋がったので、あとは命令や機能をいろいろ追加していきます。
予定：
- 数値演算
- 条件分岐
- レキシカルクロージャ
- ループ
その後は、多重定義あたりやってみます。

54 ：

経過報告です。
スタックローカルのタプルとかパターンマッチとか実装しました。
ここ数日、快調なペースです。

55 ：

rowl1の実装と並行してですが、rowl2の実装を開始しました。
ブートストラップ3週目です。

56 ：

あれ、いつのまにか growl から rowl になったんですね。

57 ：

すいません、growlという名のアプリが既に存在しましたので。
gitのURL変更はアナウンス忘れですorz

58 ：

a

59 ：

ご無沙汰しております。
ブログ立ててそっちで書いているうちにここの存在をすっかり忘れてしまっておりました。
自分でスレを立てておいて半年も放置してしまって大変申し訳ありません・・・。
いろいろと方針変更がありましたが、開発は続けておりましてGC搭載のVMが動くところまで来ました。
http://github.com/nineties
作ると言ったOSやってなかったり、関数型言語じゃなくなってたりなんかいろいろグダグダですいません。

60 ：

>>59
がんばれー
かげながら応援してるよー

61 ：

>>60
ありがとうございます。頑張ります。

62 ：

がんばれ!!!
僕も応援してるよ!!!

63 ：

>>61
github経由でblogも見た、
感動した

64 ：

ありがとうございます！
実装を開始して今日で1年経ちました。
これからもがんばりますのでよろしくお願いします。
来年はドキュメントを書いて人に使ってもらえるようにすることが目標です。

65 ：

頑張れ!!
Twitterもたまに見てますぞ!!

66 ：

これ>>1は勉強とかのつもりかもしれないけど、やってることって70年代〜80年代のbitやcomputer todayの連載記事（とか別冊本)みたいで
ものすごく読んでいて楽しい、最後まで行ったら全部まとめて一冊にして欲しいとか思う

67 ：

周りも勉強になるから本当に良スレ
2ちゃんはこうあれば良いと思う

68 ：

一人で誉めし乙
そこまでいくとわざとらしい

69 ：

>>68
目が曇っちゃうとどうしようもないね

70 ：

いまきた産業だけど
Javaのシンタックスシュガーを増やすとかそのくらいにしとけばいいのに

71 ：

おそくなりましたが、あけましておめでとうございます。
現状報告ですが、REPLの実装をしています。
バッファリングしないIOが必要だったりと面倒でちょっと時間がかかりそうな感じです。
>>70
言語作りではなくコンパイラの勉強が目的なので、出来るだけ既存物に頼らないで作ってく予定です。

72 ：

Pythonとかがスマートポインタやウィークポインタから
ガベージコレクションに乗り換えたけど処理効率より
スコープを隠ぺいすることでコーディングの負担を減らしたいのかな

73 ：

1すごい

74 ：

rowlでOS作ってみるお

75 ：

これ ； デリミタっていうんだけどさ、よく打ち忘れるよね
Rubyだとつけなくてよくなるんだけど
ゴミじゃねーか

76 ：

天使ちゃんマジ天使

77 ：

ほ

78 ：

>>75
;はデリミタじゃないぞ、行コメントだ

79 ：

行コメントだね

80 ：11/11/23

一般的には、;はセミコロンっていうんだけどね。