本記事は
言語実装 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!