プログラミング言語 Forth

Forth はスタックを基本とするプログラミング言語である。 このため、他に類をほとんどみない特異な部類に属する。

インストール

WSL の Ubuntu 20.04 で動かしている。インストールは次の通りである。

$ sudo apt get install gforth

リンク一覧

主な参照先は次のとおりである。あえて Qiita は外した。↵

日本語

• manabu's forth page(manabu.gomen.org)
• iMops-forth @Wiki(w.atwiki.jp)
• Rpn and forth 超入門(www.slideshare.net)
• Forth(リンク切れ)

英語

• GForth Manual(www.complang.tuwien.ac.at)
• Starting Forth(www.forth.com)
• Forth Tutorial(www.forth.org)

Forth に驚く

以下の記述は WSL2 の Ubuntu 20.04 Gforth 0.7.3 のときのものである。

gforth を起動するとびっくりする。まず、対話環境にプロンプトがない。 それに、リターンキーを打っても次の行に行かない。 そこで、このページではキーボードで打った文字列をアンダーラインで表示することにした。 また文字列を打った後は Enter キーか Return キーを押すが、これを ↵ で表示することにした。 まずすべきことは、対話環境から抜けることである。これには bye を入力する。

$ 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
bye↵
$

gforth はスタックを基本とした演算である。スタックにはいろいろなものを入れられる。 Forth には複数のスタックがあるが、スタックはしては以下特記なき限りパラメータスタックを指すものとする。 当然、数字を入れることができる。数字の演算もできる。また文字列も表示できる。

    $ 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
    1↵  ok
    3↵  ok
    +↵  ok
    .↵ 4  ok
    ." Scarlatti"↵ Scarlatti  ok
    bye↵ 

平方数の和問題の解法

gforth が動作することを確認した。 さて、平方数の和の問題を Forth で解くにはどうすればいいか、 その考えをメモする。

こんなことをしたい

gforth の環境で、平方数の和となる組を順に表示する：

sqsum
2 1 1
5 2 1
8 2 2
10 3 1
13 3 2
17 4 1
18 3 3
（中略）
997 31 6
1000 26 18
1000 30 10

さて、文字列の表示であるが、." で始まり " で終わるものが文字列であること、 この文字列が下記の手順で表示されることを理解した。

." S i j" cr ." -----"↵ S i j
----- ok

平方数の和の問題であるが、まずは 1 から始まって n で終わる階差 1 の等差数列を表示するにはどうするかを知りたい。 当面は末項の n を 7 と決め打ちする。まず、1 から 7 まで順に表示するプログラムである。

: seven  8 1 do  i . cr loop ;↵  ok
seven↵ 1
2 
3 
4 
5 
6 
7 
 ok

2重ループを作ることはできるだろうか。こんな感じだ。

1
2 1
2 2
3 1
3 2
3 3
4 1
4 2
4 3
4 4
（以下省略）

実際にはこんな感じで似たことはできる。

: d-loop   4 1 do i 0 do i . j . cr  loop loop  ;↵  ok
d-loop↵ 0 1
0 2
1 2
0 3
1 3
2 3
 ok

配列の扱い

次の目標は、指標の最小値 low = 6 と指標の最大値 high = 8 のときの、次のスタック

　　　　 high ...  low       
スタック  65   53   52

から、最小値 52 に対応する指標 6 を求めることにある。しばらく時間がかかりそうだ。

配列

配列は、create と allot の組み合わせでできそうだ。また、配列の最小値もなんとかなりそうだ。

create a 5 cells allot↵ ok
3 a 0 cells + !↵ ok
1 a 1 cells + !↵ ok
4 a 2 cells + !↵ ok
1 a 3 cells + !↵ ok
6 a 4 cells + !↵ ok
: 5min a 0 cells + !  5 1 do a i cells + @ min loop ;↵ ok
5min↵ ok
.↵ 1

ではここで、配列の最小値をとる指標（ここでは 0 から 4 まで）を得るにはどうしたらいいだろうか。 argmin という変数を新たに作ってワードを書いてみた。しかし、汚い。

variable argmin↵ ok
: 5argmin 0 argmin ! 5 0 do a argmin @ cells + @  a i cells + @ > if i argmin ! then  loop ;↵ ok
5argmin↵ ok
argmin @ .↵ 1 ok

argmin という変数はもう p でよい。また、上限と下限は変数 low と high で渡すことにした。配列は s にした。

    variable p↵ ok
    : argmin high @ 1+ low @ dup p ! do s p @ cells + @  s i cells + @ > if i p ! then  loop ;↵ ok
    argmin↵ ok
    p ?↵ 1 ok    

以下、試行錯誤の結果（何日かかったかは言うまい）、次のプログラムができた。

    1 value p 1 value low 2 value high
    create s 256 cells allot create q 256 cells allot
    2 s 1 cells + ! 5 s 2 cells + ! 1 q 1 cells + ! 1 q 2 cells + !
    : sq dup * ;
    : sq+ sq swap sq + ;
    : argmin high 1+ low dup to p do s p cells + @ s i cells + @ > if i to p then loop ;
    : shrink low 1+ to low ;
    : widen high 1+ to high high sq 1+ s high cells + ! 1 q high cells + ! ;
    : heighten  1 q p cells + +! p q p cells + @ sq+ s p cells + ! ;
    : enlarge  q p cells + @ 1 = if widen then heighten ;
    : fit q p cells + @ p = if shrink else enlarge then ;
    : prt s p cells + @ . p . q p cells + @ . ;
    : sqsum cr ." S i j" cr ." -----" begin cr prt fit argmin s p cells + @  1000 > until ;

ここまで打って、sqsum↵ と入力すると、ずらずらと 1000 までの合計を出す。(2020-10-28)

記号の索引

ここでいう「記号」はワードのほか、慣習として使う文字列を含む。その場合は「非ワード」とする

スタックは鉛直に伸びるイメージがあり、重力に逆らってスタックの上に「置く」、「積む」などとよく言われる。 しかし、ここではスタックは左に伸びるものとする。スタックトップに置く(push する)とは、 目の前から左に伸びる今までのスタックを１つずつずらして左に押しやり、空いた場所に所望の値を入れることをいう。 使う（pop）するときは一番右を取り除くものとする。 ワードは大文字と小文字を区別しない。ここではすべて小文字にした。 意味の欄にあるトップとはスタックトップのことである。 また、トップをトップのアドレス（位置）とトップの値の両方の意味で使っている。 スタックのアイテムとは、スタックにあるものを指す。スタック効果の文字は、n, n1, n2, n3 は整数を、 d, d1, d2 は整数のペアを、b は真偽値を表している。

(

paren

コメントの開始。前後は空白

)

paren

コメントの終了

+

plus

( n1 n2 -- sum )

加算

-

minus

( n1 n2 -- diff )

減算 ( n1 - n2 )

*

star

( n1 n2 -- prod )

乗算

/

slash

( n1 n2 -- quot )

除算の商 (n1 / n2)。n2 がゼロのときはクラッシュするかもしれない

mod

( n1 n2 -- rem )

除算の剰余。n2 がゼロのときはクラッシュするかもしれない

/mod

( n1 n2 -- rem quot )

除算の剰余と商。n2 がゼロのときはクラッシュするかもしれない

*/

star slash

( n1 n2 n3 -- n4 )

n1*n2/n3。n3 がゼロのときはクラッシュするかもしれない

*/mod

star slash mod

( n1 n2 n3 -- n4 n5)

n1*n2/n3の剰余を n4 に、商を n5に置く。n3 がゼロのときはクラッシュするかもしれない

1+

トップを 1 増やす

1-

トップを 1 減らす

2*

トップを 2 倍する

2/

トップを 1/2 倍する。余りは切り捨てる

negate

( n1 -- n2 )

トップの符号を変える

abs

( n1 -- n2 )

トップの絶対値をとる

min

( n1 n2 -- min )

a と b の大きくないほうをトップに置く

max

( n1 n2 -- max )

a と b の小さくないほうをトップに置く

swap

( n1 n2 -- n2 n1 )

トップとその左隣を入れ替える

dup

( n -- n n )

トップを複製してアイテムを１つ増やす。

over

( n1 n2 -- n1 n2 n1 )

トップの左隣をコピーしてスタックを左に押しやりコピーをトップに置く

drop

( n -- )

トップを捨てる

2swap

( d1 d2 -- d2 d1 )

トップペアとその左隣ペアを入れ替える

2dup

( d -- d d )

トップペアを複製してペアアイテムを１つ増やす。

2over

( d1 d2 -- d1 d2 d1 )

トップペアの左隣をコピーしてスタックを左に押しやりペアコピーをトップに置く

2drop

( d -- )

ペアトップを捨てる

rot

( n1 n2 n3 -- n2 n3 n1 )

トップの左隣のそのまた左隣を取り出してスタックを左に押しやりトップに置く

nip

( n1 n2 -- n2 )

トップの左隣を捨てる。swap drop に同じ。

tuck

( n1 n2 -- n2 n1 n2 )

トップをコピーし。トップの左隣の左隣に挿入する。swap over に同じ。

pick

トップ n を取り、その左のアイテムを0から数え始めて n 番目にあたるアイテムをコピーしトップに置く

roll

トップ n を取り、その左の n+1 個のアイテムを、最左アイテムがトップになるよう循環置換する

create

create a n cells allot でaに n バイトの領域を割り当てる

allot

確保すべきバイト長に当たる数値をスタックから入力として取る

cells

create a n cells allot でaに n セルの領域を割り当てる

--

（非ワード）

スタック(|効果)コメントで、スタックの入力と出力を分離する慣用的な印

.

dot

スタックトップの値を取り除き、取り除いたスタックトップの値を印字する

.S

dot S

スタックの状態を維持したまま、スタックの状態をスクリーン上に印字する

: xxx yyy ;

colon semicolon

( -- )

: 直後の文字列 xxx がワードとなり、その後の処理 yyy を定義する。; で終了する

cr

( -- )

改行と復帰

spaces

( n -- )

与えられた数だけスペースを印字する

space

( -- )

スペース１つを印字する

if

( b -- )

b が真であれば xxx を、さもなければ else があれば yyy を行なう。 if の終わりは then であり続けて zzz を行なう。

=

( n1 n2 -- b )

n1 と n2 が等しいときは true を残し、等しくないときは 非 true を残す。

<>

( n1 n2 -- b)

n1 と n2 が等しくないときは true を残し、等しいときは 非 true を残す

<

( n1 n2 -- b )

n1 が n2 より小さいときは true を残し、そうでないときは 非 true を残す

>

( n1 n2 -- b )

n1 が n2 より大きいときは true を残し、そうでないときは 非 true を残す

<=

( n1 n2 -- b )

n1 が n2 以下のときは true を残し、そうでないときは 非 true を残す

>=

( n1 n2 -- b )

n1 が n2 以上のときは true を残し、そうでないときは 非 true を残す

0=

( n -- b )

n が 0 に等しいときは true を残し、そうでないときは 非 true を残す

0<>=

( n -- b )

n が 0 に等しくないときは true を残し、そうでないときは 非 true を残す

0<

( n -- b )

n が 負の数のときは true を残し、そうでないときは 非 true を残す

0>

( n -- b )

n が 正の数のときは true を残し、そうでないときは 非 true を残す

0<=

( n -- b )

n が 0 以下のときは true を残し、そうでないときは 非 true を残す

0>=

( n -- b )

n が 0 以上のときは true を残し、そうでないときは 非 true を残す

?dup

( n - n n ) または
( 0 -- 0 )

n が 非ゼロならコピーする

begin

( -- )

不定ループ（indefinite loop）を構成する。構文は次のいずれか
begin ... b until
begin ... b while ... repeat
begin ... again

until

( b -- )

begin と組み合わせてループを構成する。 b が 0 なら begin に戻る。b が 0 以外であればループを抜ける。

while

( b -- )

b が 0 でなけなければ次の REPAT まで続けてループする。b が 0 であれば実行は REPEAT の直後まで飛び、ループを抜ける。

again

( -- )

begin に戻る（無限ループ）。ループを抜けるには exit を用いる。

do

( n1 n2 -- )

loop と組み合わせて確定ループを構成する。 n1 は上限値、n2 は指標（インデックス）。

loop

( -- )

ループ指標 を 1 増やす。do と組み合わせて確定ループを構成する。

+loop

( n -- )

ループ指標 を n 増やす。do と組み合わせて確定ループを構成する。

i

do ... loop におけるカウンター。 スタックトップに置かれる。

leave

if 文などと組み合わせてループを途中で抜ける。

bye

forth 開発環境を終了する

dup

スタックトップの値を複製する

swap

スタックの最も右２つの順序を入れ替える

variable

( -- ) v: ( -- addr )

v という名前の変数を宣言する。 ワード v は実行されるとアドレスを返す

!

store

( n addr -- )

値 n を格納する

!

store

n a idx cells + !

指標 idx にあるセル配列 a に値 n を格納する。a は create ... allot で確保しておく。

@

fetch

( addr -- n )

addr に格納されていた値を取り出す

@

fetch

a idx cells + @

指標 idx にあるセル配列 a の値をスタックに取り出す。

?

question
( または query ）

( addr -- )

アドレスの値を表示する

+!

( n addr -- )

アドレスの中身に 数値 n を加える

value

3014 value l で初期値 3014 の l という名前の変数を定義する。3014 はスタックトップの値。 値を取り出すには、l とすれば、スタックトップに値が得られる

配列をどうする

この二乗和問題では配列が大きな役割を担っているのだが、Forth については配列という用語を聞いたことがないのだ。 どうしてだろう？　GForth のマニュアルの 3.32 に Arrays and Records(www.complang.tuwien.ac.at) （配列とレコード）という項があるので和訳してみた。

Forth には配列やレコード（C 言語でいう構造体）といったデータ構造を定義する標準的なワードはない。 しかし、アドレス算術（address arithmetic）に基づいてワードを作ることができる。 また、配列やレコードを定義するためのワードも定義できる（ワードの定義を見よ）。

ワードの定義の方法を覚えた Forth 初心者の最初の仕事は、 配列の定義（できれば n 次元の配列）である。 先に進めば、できる。私も、できた。そこから、学べる。 しかし、定義したワードがほとんど使い道がなくてもがっかりするには及ばない （不適切な利用はもっとひどくなるから）。（後略）

やはり英語であるが、Forth の総本山でこのような主張があるのも見た。
Arrays in Forth(forth.org)というページである。

初心者から受ける質問：どうして Forth には、他の言語にあるような標準、たとえば配列などがないのか？ その答：Forth は必要に適した新しいデータ型を作るのが非常に容易なので、 プログラムをお仕着せの型に合わせるよりは都度新しい型を作るからだ。

悩んでいたが、二乗和問題であればスタックそのものを配列とみなすのが最善だろうという結論に達した。 しかし、そのあとで配列をスタックで実装してはいけないという主張を目にした。J.L. Bezemer 氏の著作
http://ficl.sourceforge.net/pdf/Forth_Primer.pdf
の 2.3 節に書かれている。

2.3 Deep stack manipulators There are two manipulators that can dig deeper into the stack, called ’PICK’ and ’ROLL’ but I cannot recommend them. A stack is NOT an array! So if there are some Forth-83 users out there, I can only tell you: learn Forth the proper way. Programs that have so many items on the stack are just badly written. Leo Brodie agrees with me.

If you are in ’deep’ trouble you can always use the returnstack manipulators. Check out that section.

スタックを配列代わりに使った顛末

以降、深いスタックを取り出す pick を使っている。どうやら、この pick は仲間の roll とともに、 推薦されないワードなのだ。なんということだろう。一応、pick の使い方として残しておく。

スタックの処理を考える

スタックに 3 1 4 1 6 という 5 つのアイテムがあるとする。このアイテムの総和を求めよう。まず、 スタックを消費する、破壊的な方法である。

: 5sum 4 0 do + loop ;↵ ok
3 1 4 1 6↵ ok
5sum↵ ok
.S↵ <1> 15 ok
.↵ 15 ok

5 つのアイテムを加えるが、加算は４回である。植木算を思い出す。

続いて 5 つのアイテムの最小値を求めよう。

: 5min 4 0 do min loop ;↵ ok
3 1 4 1 6↵ ok
5min↵ ok
.S↵ <1> 1 ok

それでは仕切り直して、非破壊的な総和を求めよう。

: 5sum dup 6 2 do i pick + loop ;↵ ok
3 1 4 1 6↵ ok
5sum↵ ok
.S↵ <6> 3 1 4 1 6 15 ok

pick を使って非破壊的にスタックにアクセスして総和を求めた。 アキュムレータの初期値は dup を使って 6 を指定しているが、開始インデックスが 2 で 境界値が 6 である。 この境界値というのが曲者で、インデックスは加算されるが、最終的には 5 で止まり、6 にはいかない。 ここもどこかすっきりしないが、値が得られたということでいいことにしよう。非破壊的な min も同様である。

: 5min dup 6 2 do i pick min loop ;↵ ok
3 1 4 1 6↵ ok
5min↵ ok
.S↵ <6> 3 1 4 1 6 15 ok

まりんきょ学問所 ＞ コンピュータの部屋 ＞ Forth