Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationEventAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
8
Help us understand the problem. What are the problem?

More than 3 years have passed since last update.

posted at

updated at

Forthについてのメモ書き

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

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
8
Help us understand the problem. What are the problem?