Forth に入門した | Hato Tech Blog

この記事は旧ブログからの転載です。旧ブログは閉鎖しています。

Forth - スタック指向言語

https://twitter.com/sin_clav/status/1466987337800630281

やばい。かっこいい。惚れた。腫れた。うああ。つよい。おもしろい。アツい。カッコいい。すごい。うおぉぉぉぉん。機械語手書きから言語処理系をブートストラップする - Qiita

機械語手書きから言語処理系をブートストラップする - Qiita
https://qiita.com/9_ties/items/349b2ed65b7cd8a7d580

この記事をきっかけに Forth というスタック指向言語を知った。スタック指向というと、他には Bitcoin などで使われていた（今も使われている？）「スクリプト言語」というのを、少し触ったことがあるくらいで他には知らないし経験がない。今ぐぐってみると、

スクリプト言語はForthという言語に似たスタックベースの言語です。

（ https://recruit.gmo.jp/engineer/jisedai/blog/bitcoin-script/ より）

とある。

ポーランド記法の表現力とシンプルさは Lisp や S式で喧伝されているから触れることが多いけど、逆ポーランド記法の特徴や利点は何なのだろう。スタックと相性の良さというのが答えの大きな１つだろうことは既に分かってきているが、メタプログラミングに強かったり REPL 文化（ Forth だとインタプリタモードという？）とかもそこらへんと関係が深いのかもしれない。

Gforth

Forth は仕様が規格化されていることやシンプルな Syntax から処理系が非常に多いようだ。 GNU プロジェクトのフリーソフトウェアとして Gforth という実装が広くプラットフォームもサポートしており、 ANS Forth Standard に準拠しているようで良さそう。というか Homebrew で見つけた処理系がそれくらいだったので、手軽に試すにはほぼ一択か。

$ brew info gforth
gforth: stable 0.7.3 (bottled)
Implementation of the ANS Forth language
https://www.gnu.org/software/gforth/
/opt/homebrew/Cellar/gforth/0.7.3_3 (248 files, 4.6MB) *
  Poured from bottle on 2021-12-04 at 20:05:32
From: https://github.com/Homebrew/homebrew-core/blob/HEAD/Formula/gforth.rb
==> Dependencies
Build: emacs ✘
Required: libffi ✔, libtool ✔, pcre ✔
==> Caveats
Emacs Lisp files have been installed to:
  /opt/homebrew/share/emacs/site-lisp/gforth
==> Analytics
install: 251 (30 days), 803 (90 days), 1,648 (365 days)
install-on-request: 251 (30 days), 802 (90 days), 1,647 (365 days)
build-error: 0 (30 days)

install: 251 (30 days), 803 (90 days), 1,648 (365 days) とのことなので、けっこうインストールされている。

$ brew install gforth

$ gforth -v
gforth 0.7.3

$ gforth -h
Usage: gforth [engine options] ['--'] [image arguments]
Engine Options:
  --appl-image FILE		    Equivalent to '--image-file=FILE --'
  --clear-dictionary		    Initialize the dictionary with 0 bytes
  -d SIZE, --data-stack-size=SIZE   Specify data stack size
  --debug			    Print debugging information during startup
  --diag			    Print diagnostic information during startup
  --die-on-signal		    Exit instead of THROWing some signals
  --dynamic			    Use dynamic native code
  -f SIZE, --fp-stack-size=SIZE	    Specify floating point stack size
  -h, --help			    Print this message and exit
  --ignore-async-signals	    Ignore instead of THROWing async. signals
  -i FILE, --image-file=FILE	    Use image FILE instead of `gforth.fi'
  -l SIZE, --locals-stack-size=SIZE Specify locals stack size
  -m SIZE, --dictionary-size=SIZE   Specify Forth dictionary size
  --no-dynamic			    Use only statically compiled primitives
  --no-offset-im		    Load image at normal position
  --no-super			    No dynamically formed superinstructions
  --offset-image		    Load image at a different position
  -p PATH, --path=PATH		    Search path for finding image and sources
  --print-metrics		    Print some code generation metrics on exit
  --print-sequences		    Print primitive sequences for optimization
  -r SIZE, --return-stack-size=SIZE Specify return stack size
  --ss-greedy			    Greedy, not optimal superinst selection
  --ss-min-codesize		    Select superinsts for smallest native code
  --ss-min-ls			    Minimize loads and stores
  --ss-min-lsu			    Minimize loads, stores, and pointer updates
  --ss-min-nexts		    Minimize the number of static superinsts
  --ss-number=N			    Use N static superinsts (default max)
  --ss-states=N			    N states for stack caching (default max)
  --tpa-noequiv			    Automaton without state equivalence
  --tpa-noautomaton		    Dynamic programming only
  --tpa-trace			    Report new states etc.
  -v, --version			    Print engine version and exit
  --vm-commit			    Use OS default for memory overcommit
SIZE arguments consist of an integer followed by a unit. The unit can be
  `b' (byte), `e' (element; default), `k' (KB), `M' (MB), `G' (GB) or `T' (TB).
Image Options:
  FILE				    load FILE (with `require')
  -e STRING, --evaluate STRING      interpret STRING (with `EVALUATE')
Report bugs on <https://savannah.gnu.org/bugs/?func=addbug&group=gforth>

引数もオプションもなしで実行すると対話型のインタプリタモードというのが起動する

$ gforth
Gforth 0.7.3, Copyright (C) 1995-2008 Free Software Foundation, Inc.
Gforth comes with ABSOLUTELY NO WARRANTY; for details type `license'
Type `bye' to exit
  ok
.( こんにちは!) CR こんにちは!
 ok
bye
$

なにも入力せずに Enter すると ok と出力される。

.( こんにちは!) CR あたりが Hello World 。

bye と入力するとインタプリタモードから抜けた。

VSCode Extensions

こんどはファイルから実行してみたい。

VSCode で拡張を検索すると２つ出てきた。

Forth - Visual Studio Marketplace https://marketplace.visualstudio.com/items?itemName=fttx.language-forth

forth - Visual Studio Marketplace https://marketplace.visualstudio.com/items?itemName=rickcarlino.forth

どちらも Gforth はターゲットにしているようだ。また、前者は2019年のリリースで、意外に新しい。よくわからないので前者を入れた。

Hello World

この gforth のチュートリアルを参考に。

Using files for Forth code Tutorial - Gforth Manual

$ cat << EOT > helloworld.fth
\ hello world forth program.
.( Hello World!) CR
EOT
$ gforth helloworld.fth -e bye
Hello World!

-e は eval で bye コマンド（Forth ではワード:word といい、もっと強力で中心的な概念）を実行して終了させている。なくてもインタプリタモードが起動したままになるだけの違い。

コンパイルして実行バイナリを生成するにはどうするんだろう？

とりあえずもう少し文法をみていく。 https://www.complang.tuwien.ac.at/forth/gforth/Docs-html/Tutorial.html#Tutorial のチュートリアルに従って進めてみます。以降しばらくはインタプリタモード。

Forth は Word をスペースで区切る。スペースを入れ忘れるエラーは多い。

\ これは正しいが、
." hello, world"

\ これは "Undefined word" error を引き起こす。スペースが足りない。
."hello, world"

Gforth を含む多くの Forth 処理系は大文字小文字を区別しない case-insensitive 。

\ これは正しいが、
." hello, world"

\ これは "Undefined word" error を引き起こす。スペースが足りない。
."hello, world"

.s はスタックのトップを表示するワード。 head に似てる。実行してもスタックの中身を消費しないのが他の一般的なワードとは異なるらしい。

1 2 .s <2> 1 2  ok
3 .s <3> 1 2 3  ok
4 5 6 7 8 9 10 .s <10> 2 3 4 5 6 7 8 9 10  ok \ スタックの一番下にある 1 が表示から欠けているのが分かる。
.s <10> 2 3 4 5 6 7 8 9 10  ok

算術（加算）

1 2  ok           \ 1 と 2 をスタックに積む
.s <2> 1 2  ok    \ スタックの状態を確認
+  ok             \ 加算し、結果をスタックに積む
.s <1> 3  ok      \ 積まれた結果を見る

これを一気に書くと

1 2 + .s <1> 3  ok
. 3  ok

ポーラント記法（後置記法）だから、後ろにワードを繋いでいくだけでいい。スタックを表示する .s ワードと似て . ワードはスタックから先頭要素をポップする（つまり消費してなくなる）。

その他の四則演算

10 3 - . 7  ok      \ 10 - 3 = 7
10 3 * . 30  ok     \ 10 * 3 = 30
10 3 / . 3  ok      \ 10 / 3 = 3
10 3 mod . 1  ok    \ 10 / 3 の余りは 1

後置記法なのでかっこは不要。というか無いらしい。

3 4 + 5 * . 35  ok    \ (3 + 4) * 5 = 35
3 4 5 * + . 23  ok    \ 4 * 5 + 3 = 23

負の数はそのままも書けるし negate というワードもある。

-10 . -10  ok
10 negate . -10  ok

-3 negate 4 * 5 - . 7  ok   \ -(-3) * 4 - 5 = 7

除算と Mod の結果の値２つをスタックに積んでくれる /mod ワード

7 3 /mod . . 2 1    \ 7 / 3 = 2 あまり 1

Stack 操作

1 .s drop .s <1> 1 <0>  ok                                \ スタックの先頭要素1つを捨てる drop
1 .s dup .s drop drop .s <1> 1 <2> 1 1 <0>  ok            \ スタックの先頭要素を複製してスタックの先頭に積む dup
1 2 .s over .s drop drop drop                             \ スタックの先頭から2つ目の要素を複製してスタックの先頭に積む over
1 2 .s swap .s drop drop <2> 1 2 <2> 2 1  ok              \ スタックの先頭要素と2つ目の要素を入れ替える swap
1 2 3 .s rot .s drop drop drop <3> 1 2 3 <3> 2 3 1  ok    \ スタック内の順序を逆にする rot

操作対象を倍にした 2swap や 2drop というのもある

1 2 3 4 5  ok
.s <5> 1 2 3 4 5  ok
2swap  ok
.s <5> 1 4 5 2 3  ok
2drop  ok
.s <3> 1 4 5  ok

さらに

1 2 3 4 .s nip .s nip .s <4> 1 2 3 4 <3> 1 2 4 <2> 1 4  ok    \ 先頭から2番目の要素を捨てる nip
1 2 3 4 .s tuck .s <4> 1 2 3 4 <5> 1 2 4 3 4  ok              \ 先頭要素を複製して先頭から3番目に追加する？ tuck

べき乗はこんな感じ？

5 dup * . 25  ok          \ 5の2乗
5 dup dup * * . 125  ok   \ 5の3乗

コロン定義

: squared             \ 関数宣言（ワード宣言？）
  dup * ;             \ 関数の実装。インデントはみやすさのためで必須ではない。

5 squared . 25  ok    \ 使ってみる。

3 squared  ok         \ 3 を2乗して、結果がスタックに積まれたのをそのまま、
squared   ok          \ もう一度2乗。
.s <1> 81  ok         \ スタックの状態は 81 。

スタックの状態に対してただ squared ワードが発動しているだけで引数という概念がないんだ。すごい。おもしろい。

さらに続けて、これらのワードを decompilation してみる。実装が見れる。

see squared
: squared
  dup * ; ok

see forth-power
: forth-power
  squared squared ; ok

組み込みのワードも decompilation できる。今の僕には見てもよくわからないが。

see .
: .
  s>d d. ; ok

see .s
: .s
  .\" <" depth 0 .r .\" > " depth 0 max maxdepth-.s @ min dup 0
  ?DO    dup i - pick .
  LOOP
  drop ; ok

see +
Code +
sh: line 0: type: gdb: not found

102BB2744: F7 03 05 AA  E9 03 10 AA - E8 03 11 AA  EA 03 0E AA  ................
102BB2754: EB 03 0F AA  4F 00 00 F9 - F4 03 0E AA  8C 8E 40 F8  ....O.........@.
102BB2764: CA 01 40 F9  4A 01 0C 8B - FC 21 00 91  8A 02 00 F9  [email protected]....!......
102BB2774: EA D7 00 F9  EF 03 1C AA - EE 03 14 AA  E7 03 1C AA  ................
102BB2784: F6 03 14 AA  F3 03 11 AA - F9 03 11 AA  FE 03 11 AA  ................
102BB2794: 88 83 5F F8  E0 03 10 AA - FA 03 10 AA  E4 03 10 AA  .._.............
102BB27A4: F8 03 05 AA  FB 03 05 AA - E6 03 1C AA  F5 03 14 AA  ................
102BB27B4: 00 01 1F D6  F7 03 05 AA - E9 03 10 AA  EA 03 11 AA  ................
102BB27C4: F6 03 0E AA  E8 03 0F AA - EB D7 00 F9  E6 03 0F AA  ................
102BB27D4: FC 03 0F AA  EB 81 5F F8 - E7 03 0F AA  E8 03 0B AA  ......_.........
102BB27E4: F5 03 0E AA  F4 03 0E AA - F3 03 11 AA  F9 03 11 AA  ................
102BB27F4: FE 03 11 AA  E0 03 10 AA - FA 03 10 AA  E4 03 10 AA  ................
102BB2804: F8 03 05 AA  FB 03 05 AA - 60 01 1F D6  F7 03 05 AA  ........`.......
102BB2814: E9 03 08 AA  EA 03 10 AA - EB 03 11 AA  F6 03 0E AA  ................
102BB2824: EC 03 0F AA  E6 03 0F AA - FC 03 0F AA  E7 03 0F AA  ................
102BB2834: F5 03 0E AA  F4 03 0E AA - F3 03 11 AA  F9 03 11 AA  ................
102BB2844: FE 03 11 AA  E0 03 10 AA - FA 03 10 AA  E4 03 10 AA  ................
102BB2854: F8 03 05 AA  FB 03 05 AA - 00 01 1F D6               ............
end-code
 ok

終わり

今日はここまで

Tutorial 的にはここまで進んだ。 Decompilation Tutorial - Gforth Manual https://www.complang.tuwien.ac.at/forth/gforth/Docs-html/Decompilation-Tutorial.html#Decompilation-Tutorial

ちなみに Forth 言語の使い手のことを Forthers というみたいだ。かっこいい。

メモ

Forth で特徴的な概念

word : コマンド？のようなやつ。
stack effect : word がスタックに及ぼす影響や効果を指すようだが、主体は word だけではなく広く使っているように見える。
factoring : 因数分解？。ワードの定義を短く小さく分解し、それらを組み合わせて大きなものを構成するようにすること。 re- を接頭したらまさに「リファクタリング」なのが面白い。