🐥

Forth（Gforth）で簡単な自作言語のコンパイラを書いた

2023/06/11に公開5件

かんたんな自作言語のコンパイラをいろんな言語で書いてみるシリーズ 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 ...

移植元

https://github.com/sonota88/vm2gol-v2

＜自作言語処理系（Ruby版）の説明用テンプレ＞

自分がコンパイラ実装に入門するために作った素朴なトイ言語 Mini Ruccola とその処理系です。簡単に概要を書くと下記のような感じ。

小規模: コンパイラ部分は 1,000 行程度
pure Ruby / 標準ライブラリ以外のライブラリ不要
x86風の自作VM向けにコンパイルする
ライフゲームのために必要な機能だけ
- 変数宣言、代入、反復、条件分岐、関数定義
- 演算子: +, *, ==, != のみ（優先順位は ( ) で明示）
- 型なし（値は符号付き整数のみ） ... B言語に似てる？
作ったときに書いた備忘記事
- RubyでオレオレVMとアセンブラとコード生成器を2週間で作ってライフゲームを動かした話
- Rubyでかんたんな自作言語のコンパイラを作った
本体には含めていない後付けの機能など
- 真偽値リテラル / 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。

https://gforth.org/manual/Memory.html

あと、メインのスタック（data stack）とは別にリターンスタックというスタックがあり、それを補助的に使うこともできる。

なるほどと思ったところ

文字列

C のような NUL終端文字列ではなく、先頭アドレスと文字数をセットにして取り回す慣習（？）らしいです（標準的なワードのインターフェイスがそうなっている）。

馴染みがない方式で最初はちょっと戸惑いましたが、文字列とその部分文字列を区別せずに扱えると気付いてなるほどと思いました。

多値が返せる

多値を返すしくみがわざわざ用意されているわけではなく、単にスタックに好きな数の値を残せばよい。「関数から値と処理の成否を分けて返す」みたいなことが普通にできる。

たとえば Gforth の組み込みワード s>number? に文字列を渡すと数値（パース結果）とフラグ（成否を表す）の2つをスタックに残す、といった感じ。

脚注

Collapse OS ネタ。元はゲーム・オブ・スローンズですね。 ↩︎

Discussion

nfunato

Forthに関するサイトとしては、Leo Wongさんのサイトも "らしい” 内容でお勧めかもしれません。
http://murphywong.net/hello/forth.htm
(これがhttpsじゃないんだよなぁ...)

murphywong.net/hello/….htm に色々な記事があり(simple,comus,inching,01234th,stacks,...)、たいてい上のforth.htmから辿れると思います。

sonota88

おすすめありがとうございます。土地勘がないので助かります。
まださらっと眺めた程度ですが、「ちょうどこういうのが欲しかった」というトピックが並んでいて、これを読んでいればもうちょっとスムーズだったかもな〜と思いました。

MIN0

学生時代にforthの本に歯が立たず、還暦を過ぎた今になってforthの勉強をやっています。とは言ってもstarting forthもgforthもチラッと触っただけの雑な状況で、「ちゃんと読んでみるしかないなぁ」と再認識しました。ありがとうございます。

今は学生時代に挫折した日本語のforth本を参考にしています。国立国会図書館サーチで「標準FORTH」で検索すると電子書籍として閲覧できます（登録が必要）。
また、Facebookのプライベートグループで「FORTH2020」と言うグループで情報をもらっています。不定期で土曜日にZOOMミーティングを行なっていて、ちょっと前の記念ミーティングではFORTHの生みの親も参加していて、感動しました。興味がありましたらどうぞ。
https://www.forth2020.org

sonota88

国立国会図書館サーチで探すのは思いつきませんでした。標準FORTH 読んでみたいですね。forth2020 も知りませんでした。ご紹介ありがとうございます。

私も最初のとっかかりがなかなか掴めず苦労しました。小さいものでも具体的な目標があって手を動かした方が学習が進みやすいので、Mini Ruccola コンパイラをよく知らない言語に移植するときは素朴な cat コマンド（標準入力から1バイト読んで標準出力に書く、を繰り返すだけのもの）を書くことを最初の目標にすることが多いです。Forth への移植の場合もそうしていたのですが、そこにたどり着くまでがまず大変でしたね……目標なしだったら私も挫折していたと思います。