forthについてのメモ書き

Forth

本記事は言語実装 Advent Calendar 201719日目向けの投稿です。

gyaboと申します。どうも学術よりのカレンダーだったようで、とても緊張しています。

Forthについて少し勉強したので書きます。
ついでにお試し処理系をC/C++言語で書きます。

Forthをご存知ですか？

Forth forth, FORTH
※どう書いてもいいらしいです。

兎に角、早速簡単にForthを使ってみましょう。

Forth はスタック指向であり逆ポーランド記法（RPN）

ex) 1 + 2を計算してprintf(印字)してください

[Forthで書くと]
1 2 + .

説明します。Forthはスタックを持っています。いろいろなものを積めます。
スタックの状態を以下に図示します。

※\は行末までコメントの意味。

1   \ 1  1をスタックに積む。
1 2 \ 2  2をスタックに積む。
3   \ +  +を計算する
    \ .  3 と出力される。. によってスタックの値は取り出されて空っぽになる

ex) HelloWorldしてください

すいません、わざとサブルーチン使います。

: HELLO ." HelloWorld"  CR ;
HELLO

[Forthで書くと]
: \ サブルーチン宣言開始。次の"ワード"(後述)はサブルーチンの名前

." \ 文字列出力

HelloWorld" \ 文字列自身

CR \ printf("\n");

; \ サブルーチン宣言終了。"ディクショナリ"(後述)に登録される

HELLO \ サブルーチン呼び出し

サブルーチンも定義できるんですね。

こんな感じで、あらゆるメモリ操作、やりたいことのために、一時的に何かしらの保存領域としてスタックを使ったり、
どこかの関数やサブルーチンに値を受け渡しするときにスタックの仕掛けを使います。
もちろん分岐時の評価にもスタックを使います。
Forth自身の組み込み関数がスタックを使わないなら、スタックを通さなくても良くなる認識で、
いろんな処理系があるようです。

ex)1 + 2の結果を2回printfしてください
スタックのコピーを使います。
1 2 + DUP . .

. (印字)はスタックを破棄するので、事前にduplicate（DUP)します。

その他、単に生メモリにアクセスしたりなどもあったりします。足りない処理はとにかく自分で書きます。

Forthの文献で出てくるキーワード

スタック(stack)
計算するためのスタック。あらゆる計算はスタックで行われます。

ワード(word, words)
Forthが解釈する何かしらの最小単位です。

ディクショナリ(dictionary)
組み込み処理だったり登録したサブルーチン処理が登録されているところです。
ワードをディクショナリから検索して、登録されてたらそれを評価し、その繰り返しがForthの処理の基本です。

魅力シンプル

勉強してて面白かったのは、Forthの処理系はとても小さいものが多く、またForthは明確な文法が存在しないようです。

魅力シンプルなのでお試し実装が大量にあって勉強になる

※参考文献参照。pythonでのForth実装とか一杯あります。

魅力 Forthの処理系がやってることがシンプル

Wikipediaを抜粋してかみ砕くと、Forthがやってることは以下の通りです。

1)インタプリタはユーザ入力デバイス(この場合ファイルでも何かしらのメモリ領域でも何でもいい)から入力された行を読み

2) それから区切り文字としての空白を使って単語に構文解析される

3) インタプリタがワードを見つけると、ディクショナリ (dictionary) からそのワードの検索を試みる

4) もしそのワードが見つかれば、インタプリタはワードに関連付けられたコードを実行

5) もしワードを発見することができないなら、ワードを数だと仮定して数値への変換を試み、それをスタックにプッシュ

6) 変換が成功していれば、インタプリタは入力システムからの構文解析を継続する

7) 辞書の参照と数値への変換の両方が失敗した場合、インタプリタはそのワードが認識できないというエラーメッセージを出す

これを書くとForthのサブセットが完成するようです。

サブセットを実装してみた

なんというか手が完璧になまってたので、サブセットを実装しました。

tf.cpp
https://gist.github.com/kumaashi/6d4c83b635fdd996fd67bb8f887bec43

VC2015 64bitで動作確認しています。

以下にあるような見慣れないのはサポートしていません。

http://wiki.laptop.org/go/Forth_stack_operators
entryuserprimであとはひたすら拡張していくだけ、という認識です。
※ほんまかいな

付録スレッデッドコード

Wikipediaによると、スレッデッドコード（英: threaded code）は、
プログラミング言語処理系におけるコード生成手法のひとつで
呼出すべきサブルーチンのアドレスを羅列する、というものです。
いろいろスレッデッドコードの手法があるようですが、Wikipediaのサンプルコードがよくできていたので解説します。
(少し変形)

thread:  ;実行すべき命令列
  &pushA
  &pushB
  &add
  ...

; ↓ここから実行開始

start:
  ip = &thread ;ipってレジスタにthreadのアドレスを格納
top:
  jump *ip++   ;pushAにジャンプしてipを次に進める


pushA:         ;Aをスタックに積んでくれるサブルーチン
  *sp++ = A    ;Aをスタックに積む
  jump top     ;topに強制ジャンプ

pushB:         ;Aをスタックに積んでくれるサブルーチン
  *sp++ = B    ;Bをスタックに積む
  jump top     ;topに強制ジャンプ

add:           ;スタックのトップとトップ-1を足してスタックに積む
  *sp++ = *--sp + *--sp
  jump top