"Algebraic Expression Evaluation in FORTH" の解説
Lisp、そしてForthのような「中置記法による式の構文」の無い言語に対して最も良く聞く不満が、なぜ直感的にわかりやすい中置記法が使えないのだ、ということでしょう。当然ながらそれに対する長年の反論もありますが、中置は小学校の算数以来ずっと親しんでいる記法であることも確かです。
Forth系の言語では、たとえばMindのように言語組込みで中置記法の式が書けるものもありますが（処理系に添付の「プログラミング言語Mind 基本文法」（ kihonbunpou.docm ）の第6章の最後を参照のこと）、ここではMichael Stolowitz氏がForth Dimensions誌に1982年に寄稿した、中置記法的な働きをする演算子を追加定義する技法を紹介します。Forthに十分慣れている読者を対象とします。現行の処理系（筆者の手元のFreeBSD/AMD64上のGforthとPortable Forth Environment）に対応するよう修正し、動作を確認したコードをまず示します。
元のコードと記事を参照したい方は http://www.forth.org/fd/contents.html#A にあるPDFを見てください。
これを gforth algebraic.fs あるいは pfe algebraic.fs のように読込ませてForthを起動し、
A[ ( 2 + 3 ) * ( 4 + 5 ) ]A .<Enter>
のように入力すると、
A[ ( 2 + 3 ) * ( 4 + 5 ) ]A . 45 ok
のように結果を確認できるはずです（トークンを区切る規則は通常のForthのままですので、スペースは絶対に省略しないように）。以下、詳細を述べます。
記事の最初にエディターズノートが付いており、以前の記事のチャールズ・ムーア氏のBASICコンパイラで使われている手法との違いについての筆者からのコメントについて書かれています。BASICコンパイラはコンパイラとしてのみ機能するもので通常のデータスタックだけを使用する、それに対し提案手法はインタプリタでも機能するが別に演算子スタックを必要とする、といった点が述べられています（編集者が良い仕事をしています）。
中置記法をパースしてRPN順に変換することは、スタックを使った簡単なアルゴリズム（ダイクストラの操車場アルゴリズム）で可能なことはよく知られています。
そのアルゴリズムで、たとえば、
A + B - C * (D / E)
のような式を変換すると、
A B + C D E / * -
のようになりますが、この時 A B C D E というオペランドの出現順は変わりませんから、Forth処理系ではインタプリタモードでもコンパイラモードでも、オペランドについてはそのままにして、演算子のワードを出現後適当に遅延させてやるだけで、中置記法からRPNへの変換はできることになります。
演算子の優先順位のことをlevelと元の文献では呼んでいるので、ここでもレベルと呼びます。レベル0は「式の端」を示す特別な値、レベル1はカッコのための特別なレベルとします。
まず最初のこのコード、
CREATE OP 96 ALLOT
は、演算子スタックとして96バイトを確保しています。元のコードでは44バイトで、セルのサイズが2バイトから8バイトに大きくなっていますから（Forthでは言語で使う「ワード」と区別するため、マシン側のいわゆる「ワード」は「セル」と呼ぶ慣習になっています）もっと大きくしたほうが良いかもしれませんが、そんなに複雑な式を書くことも無いでしょう。
以下で、
( a b -- c d )
というようなコメントの記法は、-- の左側がワードの実行前のスタック（ここでは b がトップ）、右側がワードの実行後のスタック（ここでは d がトップ）を示しています。
: ?INTERP ( xt -- ) STATE @ IF COMPILE, ELSE EXECUTE THEN ;
これは後回しにします。
: OPP@ ( -- addr ) OP DUP @ + ;
（op pointer fetch）演算子スタック領域の最初には、そこから演算子スタックのトップまでのオフセットをバイト数で書いておきます。DUPで複製しているのは、@（fetch）がスタックを消費してしまうためです。フェッチしてきたオフセットを足して、演算子スタックのトップのアドレスを得ます。
: >OP ( xt lev -- ) 16 OP +! OPP@ 2! ;
（to op）演算子スタックへのプッシュです。プリインクリメントで、元のコードでは2セルぶんとして4を足していますが、現代の（1セルが64ビットの）マシンでは16を足します（ +! は、メモリの値に足し込むワード）。ずらした後のトップのアドレスを OPP@ で得て 2! で書き込みます。2! は、スタックに b a addr の順にデータとアドレスを用意しておいて、a と b の2個の値を addr から連続して書込むワードで、addr に a を、(addr+8) に b を書込みます。
: OP> ( -- ) OPP@ 2@ -16 OP +! DROP ?INTERP ;
（from op）演算子スタックからのポップで、ポストデクリメントです。2@ は 2! の逆で2個の値を読出すワードで、スタックトップに指定されたアドレスから読出した値が、次のアドレスからの値がその次に入ります。ポップするのはその演算子による演算を実行することが決定した後なので、レベルの値は不要ですから DROP します。
最後に ?INTERP を呼んでいるので、ここで ?INTERP の説明をします。
: ?INTERP ( xt -- ) STATE @ IF COMPILE, ELSE EXECUTE THEN ;
STATE @ で、Forth処理系の現在の状態（コンパイラモードなら真、インタプリタモードなら偽）を得ます。続いて IF ～ ELSE ～ THEN でそれぞれの場合の動作をするわけですが、ここでコメントにある xt とはexecution tokenというもので、ワードをコンパイルしたり実行したりするための整数値です（昔のForthではPFAやCFAという具体的なアドレスの値だったが、実装の自由度を上げるために標準ではそのように抽象化された）。ここでは、演算子のワードのexecution tokenです。コンパイラモードでは COMPILE, （コンパイル コロン）により xt のワードを実行するコードをコンパイルし現在コンパイル中のワードのコードに追加します。インタプリタモードでは EXECUTE というワードにより、その演算を実行します。
: LEV? ( -- lev ) OPP@ @ ;
演算子スタックのトップの値をpeekします。演算子スタックの先頭にある演算子のレベル（優先度）が得られます。
: ]A BEGIN LEV? WHILE OP> REPEAT
FORTH ; IMMEDIATE中置モードから抜けるワードです。単に、名前空間を FORTH に戻すだけではダメで、演算子スタックが空になるまで演算子を取出して OP> を実行する必要があります。演算子スタックが空になると、OP に 0 が書込まれてそれを読出すことになり、0 は真偽値としては偽なので BEGIN ～ REPEAT のループから抜けて、名前空間を FORTH に戻し（演算子のワードの意味を元に戻し）ます。]A は、コンパイル中でもコンパイルされるのではなく実行されるイミディエイトワードです。
: INFIX ( lev -- ) ( old rpn op new infix op )
' CREATE SWAP , , IMMEDIATE
DOES> 2@ BEGIN DUP LEV? > INVERT WHILE
>R >R OP> R> R> REPEAT >OP ;このシステムの中核となるワードです。CREATE と DOES> というワードの組合せは、Forthにおいて「ワードを定義するワード」を書く際の基本的なイディオムです。このワードを、この後にある「6 INFIX + +」というようなコードで使っています。「6 INFIX + +」の例で説明します。
まず、ワード INFIX が実行される時点で、スタックには 6 が積まれています。これは演算子の優先度（レベル）です。最初の ' というワード（tick と読みます）で、INFIX に続く1個目の + のexecution tokenがスタックに積まれます。続いて CREATE というワードで、2個目の + を読込み、その名前で新しいワードを作ります（なので、2個目の + を別の名前にすれば、その名前で定義される）。
SWAP でスタックトップと2番目を入替え、トップから「レベル」「execution token」という順にします。続くカンマ2個 , , で、この順序で新しく作ったワードの定義に書込みます。最後に IMMEDIATE で、新しく作ったワードをイミディエイトワードにします。
DOES> 以降は、INFIX により作られたワードの実行時の動作になります。
最初の 2@ で、ワードの定義時に書込んだレベルとexecution tokenをスタックに取出します（これらを取出せるようなアドレスが最初に積まれています）。BEGIN ～ REPEAT がループで、まずレベルを複製して演算子スタックの先頭のレベルと比較します。演算子スタックに在るほうのレベルが等しいか大きい間は OP> で演算子スタックから演算子を取出し処理します。OP> の前後の >R >R と R> R> は現在のスタックをリターンスタックに退避したり戻しているだけです（インタプリタモードの場合に、演算子が演算する対象がスタックトップにあるようにしている）。最後の >OP で、自分自身を演算子スタックに積みます。
VOCABULARY ALGEBRAIC ALGEBRAIC DEFINITIONS
ALGEBRAIC というボキャブラリを作り、CONTEXT（名前を探しにゆくボキャプラリ）をそれに切替え、DEFINITIONS で CURRENT（新たに定義するワードが追加されるボキャプラリ）も ALGEBRAIC に切替えます。
7 INFIX * * 7 INFIX / / 6 INFIX + + 6 INFIX - - 5 INFIX > > 5 INFIX < < 5 INFIX = = 4 INFIX INVERT INVERT 3 INFIX AND AND 2 INFIX OR OR
中置演算子の定義。詳細は前述しました。
: ( ['] CR 1 >OP ; IMMEDIATE
: ) [ FORTH ] BEGIN 1 LEV? < WHILE OP> REPEAT
1 LEV? = IF -16 OP +!
ELSE 1 ABORT" Missing (" THEN ; IMMEDIATEかっこ（通常のForthではコメント）の再定義です。詳細は略します。元の文献にある L は 1 の誤植なので注意してください（そもそも 1 と小文字の l の区別が不可能なフォントを使っているのは現代の感覚では信じられないだろう）。
FORTH DEFINITIONS : A[ 0 OP ! ALGEBRAIC ; IMMEDIATE
FORTH ボキャブラリに戻して、開始ワードの定義。演算子スタックを初期化してボキャブラリを切替えるだけです。イミディエイトワード。
以上です。なお、元の文献との差異いくつかは解説していません（ボキャブラリのワードがイミディエイトか否か、など）。
