Forth(Gforth)で簡単な自作言語のコンパイラを書いた
かんたんな自作言語のコンパイラをいろんな言語で書いてみるシリーズ 23番目の言語は Forth です。これで 冬来たる-ready [1] になりました。世界が崩壊して Forth しか使えなくなっても自作言語で書いたプログラムをコンパイルして遊ぶことができますね!
(他所に書いていたものを引っ越してきました。元の公開日は 2023-03-12 です。)
できたもの
動かし方の例
$ echo '
func add(a, b) {
return a + b;
}
func main() {
call add(1, 2);
}
' | gforth mrcl_lexer.fs | gforth mrcl_parser.fs | gforth mrcl_codegen.fs
# ↓アセンブリが出力される
call main
exit
label add
push bp
cp sp bp
cp [bp:2] reg_a
push reg_a
cp [bp:3] reg_a
push reg_a
pop reg_b
pop reg_a
add_ab
cp bp sp
pop bp
ret
label main
push bp
cp sp bp
cp 2 reg_a
push reg_a
cp 1 reg_a
push reg_a
_cmt call~~add
call add
add_sp 2
cp bp sp
pop bp
ret
# ... snip ...
移植元
<自作言語処理系(Ruby版)の説明用テンプレ>
自分がコンパイラ実装に入門するために作った素朴なトイ言語 Mini Ruccola とその処理系です。簡単に概要を書くと下記のような感じ。
- 小規模: コンパイラ部分は 1,000 行程度
- pure Ruby / 標準ライブラリ以外のライブラリ不要
- x86風の自作VM向けにコンパイルする
- ライフゲームのために必要な機能だけ
- 変数宣言、代入、反復、条件分岐、関数定義
- 演算子:
+
,*
,==
,!=
のみ(優先順位は(
)
で明示) - 型なし(値は符号付き整数のみ) ... B言語に似てる?
- 作ったときに書いた備忘記事
-
本体には含めていない後付けの機能など
- 真偽値リテラル / break / if/else / 単項マイナス / Racc などを使って書いたパーサの別実装
-
他言語への移植
- コンパイラ部分のみ
- Python, Java, PHP, TypeScript, Julia, Dart, Haskell, Rust, Zig など、2023-03-12 の時点では 23言語
-
セルフホスト版
- さらに育てていくとセルフホストまでできます
- 作り方は製作メモに全部書いています。凝ったことはしていないので Ruby を知らない人でも雰囲気くらいは分かるんじゃないかと。
<説明用テンプレおわり>
メモ
Forth というかスタック指向の言語でまともにプログラミングするのはほぼ今回初めて(逆ポーランド記法自体は知識としては知っていて、BibTeX とか PostScript で昔ちょっと触れたことがある、という程度)。だいぶ手探り感が強かったです。
基本的には以下の2つを見ながら書きました。
一番最初は Starting FORTH を読んで基本を知るのがおすすめ。私は Gforth Manual のチュートリアルセクションに一通り目を通したあと Starting FORTH を読み「こっちを先に読んどけばよかった……」となりました。
こちらの解説動画も参考になりました。英語だと Gforth の解説もいろいろありますね。
Thinking Forth も参考になりました。文化を知れて興味深いです。翻訳ありがとうございます。
困ったところ
日本語情報が少ない
誰でも知っているメジャーな言語ではないとはいえそこそこ歴史のある言語なので日本語でも蓄積があるのでは……という予想に反して、少なくとも Gforth に関してはちょっとググればOKという感じではないですね。
スタックの状態が分からない
読み書きに多少慣れてきたかなと思えてきた段階でも分からない。仕方なく以下の例のように逐一コメントで書くようにしてみました。今回はこのコメントなしでもスラスラ読めるという境地には至れず、そのまま残しています。自分が分かればいいやという程度の適当なもの。
: read-stdin-all ( -- src_ size )
here
\ src_
100000 chars allot
dup
\ src_ src_
\ src_ src_current_
begin
read-char
\ src_ src_cur_ | char num-read
0 = if
\ src_ src_cur_ char
drop
\ src_ src_cur_
dup
\ src_ src_cur_ | src_cur_
2 pick
\ src_ src_cur_ | src_cur_ src_
-
\ src_ src_cur_ | size
drop-1
\ src_ size
exit
endif
\ src_ src_cur_ | char
1 pick
\ src_ src_cur_ | char src_cur_
c!
\ src_ src_cur_
1 +
\ src_ src_next_
again
;
○○とか△△とかやりたいんだけどスタック操作だけだと無理じゃない? 一体どうやって書くの??
連続したメモリ領域の読み書きができるので、それを使えばOK。
あと、メインのスタック(data stack)とは別にリターンスタックというスタックがあり、それを補助的に使うこともできる。
なるほどと思ったところ
文字列
C のような NUL終端文字列ではなく、先頭アドレスと文字数をセットにして取り回す慣習(?)らしいです(標準的なワードのインターフェイスがそうなっている)。
馴染みがない方式で最初はちょっと戸惑いましたが、文字列とその部分文字列を区別せずに扱えると気付いてなるほどと思いました。
多値が返せる
多値を返すしくみがわざわざ用意されているわけではなく、単にスタックに好きな数の値を残せばよい。「関数から値と処理の成否を分けて返す」みたいなことが普通にできる。
たとえば Gforth の組み込みワード s>number?
に文字列を渡すと数値(パース結果)とフラグ(成否を表す)の2つをスタックに残す、といった感じ。
-
Collapse OS ネタ。元はゲーム・オブ・スローンズですね。 ↩︎
Discussion
Forthに関するサイトとしては、Leo Wongさんのサイトも "らしい” 内容で お勧めかもしれません。
(これがhttpsじゃないんだよなぁ...)murphywong.net/hello/….htm に色々な記事があり(simple,comus,inching,01234th,stacks,...)、たいてい上のforth.htmから辿れると思います。
おすすめありがとうございます。土地勘がないので助かります。
まださらっと眺めた程度ですが、「ちょうどこういうのが欲しかった」というトピックが並んでいて、これを読んでいればもうちょっとスムーズだったかもな〜と思いました。