Edited at

Forthについてのメモ書き

More than 1 year has passed since last update.

本記事は

言語実装 Advent Calendar 2017

19日目向けの投稿です。

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してください

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

[Forthで書くと]

: HELLO ." HelloWorld"  CR ;

HELLO

意味を同様にコメントで書いていきます。

: \ サブルーチン宣言開始。次の"ワード"(後述)はサブルーチンの名前

." \ 文字列出力

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


参考文献

◆Wikipedia Forth

https://ja.wikipedia.org/wiki/Forth

◆FORTH の情報まとめてみた 2016 年版

https://qiita.com/ryos36/items/d2d50f9803cddd091905

◆6 行の Lua プログラムで、Forth の内部インタプリタを作る

https://qiita.com/iigura/items/855954ad000fe1da6c59

◆西尾泰和のはてなダイアリー : 最小限Forth + ワード定義機能付きForth

http://d.hatena.ne.jp/nishiohirokazu/20110401/1301667130

◆Forthを作るのじゃ | TECHSCORE BLOG

http://www.techscore.com/blog/2014/01/28/forth%E3%82%92%E4%BD%9C%E3%82%8B%E3%81%AE%E3%81%98%E3%82%83/

◆Wikipedia : スレッデッドコード

https://ja.wikipedia.org/wiki/%E3%82%B9%E3%83%AC%E3%83%83%E3%83%87%E3%83%83%E3%83%89%E3%82%B3%E3%83%BC%E3%83%89

◆[Factor] LOL -> FORTH -> Factor に出会う

http://basicwerk.com/blog/archives/1619


終わりに

FactorというFORTHの後釜的な処理系があるようです。

遊んだことがないので、今度遊んでみようと思います。

間違いなどあったら指摘ください。

以上です。

Let's enjoy FORTH!