Forthについてのメモ書き


本記事は
<a href="https://qiita.com/advent-calendar/2017/lang_dev">言語実装 Advent Calendar 2017</a>
19日目向けの投稿です。

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

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

# Forthをご存知ですか？
Forth forth, FORTH
※どう書いてもいいらしいです。

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



# Forth はスタック指向であり逆ポーランド記法（RPN）
<b>ex) 1 + 2を計算してprintf(印字)してください</b>

[Forthで書くと]

```forth
1 2 + .
```

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

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

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

<b>ex) HelloWorldしてください</b>

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


[Forthで書くと]

```forth
: HELLO ." HelloWorld"  CR ;
HELLO
```

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

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

." \ 文字列出力

HelloWorld" \ 文字列自身

CR \ printf("\n");

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

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

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


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

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

```forth
1 2 + DUP . .
```

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

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


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

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

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

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

# 終わりに
<a href="http://factorcode.org/">Factor</a>というFORTHの後釜的な処理系があるようです。
遊んだことがないので、今度遊んでみようと思います。
間違いなどあったら指摘ください。

以上です。
<b>Let's enjoy FORTH!</b>