NextremerのCommon Lisp大好きプログラマ、t-sinです。
この記事はNextremer Advent Calendar 2018の19日目の記事ですが本日は12/26（水）です。
大遅刻です。
本記事では、ふしぎなふしぎなプログラミング言語Forthについて、現時点でわかっていることを話します。
ごたくはいいからコードを見せて
ForthでHTTPリクエストを処理するコードです。ご査収ください。
\ https://rosettacode.org/wiki/HTTP#Forth
include unix/socket.fs
s" localhost" 80 open-socket
dup s\" GET / HTTP/1.0\n\n" rot write-socket
dup pad 8092 read-socket type
close-socket
ほかには、Forthのウェブアプリケーションフレームワークである1991のソースコードを見てみてください。「これがウェブフレームワークのソースコード？ ちっさ」と感じることと思います。
Forthとは
Forthは後置（逆ポーランド）記法で記され、引数や返り値を含めた値をすべてスタックに置く、インタプリタ型言語です。その内部では極小のVMが動いており、ユーザ定義の手続き（Forth用語でワード）もVMのバイトコードのレベルまでコンパイルされます。実際マシン語にコンパイルされる処理系もあります。
仕様が規格で定まっている系の言語で、規格で対話的環境が搭載されているのも特徴です。
どうもForthについて調べていて知ったのですが、concatenative languageというプログラミング言語の分類があるらしく、Forthはその開祖的位置付けのようです（英Wikipedia記事で上げられているほかのconcatenative languageにはJoy, Factor, PostScriptなどが挙げられています）。
とりあえずフィボナッチ
こんなコードになります。\から始まる行は読み飛ばされます（コメント）。また(から)までも読み飛ばされます。
\ https://rosettacode.org/wiki/Fibonacci_sequence#Forth より
: fib ( n -- fib )
0 1 rot 0 ?do over + swap loop drop ;
:がいわゆる「関数定義」です。Forthではワード定義といいます。fibという名前のワードを新たに定義し、そのコード本体は;までの間です。
Forthでは値をコードに書くとデータスタックに積まれます。そして、ワード間のデータのやりとりは引数を用いず（つまりゼロ引数！！）、そのままスタックの値を取り出して利用します。
もっとくわしく
Forthの特徴をもっと見ていきましょう。
スタックこそすべて
データはすべてスタックに積まれます。プログラムはスペース区切りで一語ずつ処理されていきますが、その一語が値なら（正しくはワードでないなら）、スタックに積まれます。なので、変数の代入といったものはありません。ワードや条件分岐の引数などもスタック上を見るので、コード上に値が書かれることが少なく、そのためコード密度が非常に高くなります。
対話的環境
Forthはインタプリタ型言語なので、対話的環境があります。これはCommon Lispにも言えることですが、小さなコード片をインタプリタでテストしながら開発を行えるので、素早く開発をすすめることができます。Forthの場合インタプリタの状態をファイルに書き出すこともできるようです。それによって、初期状態からカスタムされたイメージを読み込み高速に独自のソフトウェアを起動できたりします。
規格化された仕様
Forthの言語仕様はANSIやISOで定められています（参考文献参照）。
Common Lispにも言えることですが、仕様が安定しているというのは大事なことです。一度議論された上で固定され普及している仕様は、あるプログラムの動作を長期間保証します。また、ある処理系の開発コミュニティがなくなってしまっても、別の処理系に低いコストで移行することができます。長期間の利用が想定されるプログラムには、安定した仕様は必須なのです。
実装してみた その1
と、ここまで調べてみたところで、こう思うわけです。
「なんだ、Forthって簡単じゃん。つくっちゃお」
そこで、ここまでの理解でつくってみたForthがこちらです。
Common Lisp製なのでCommon Lisp環境が必要ですが、とりあえずフィボナッチ数列を計算できる程度のことは可能なミニミニ処理系です。(2018-12-29追記)ちなみにワードの引数の順序がForth 2012と異なるので、GForthなど本当のForth処理系ではそのまま動きません
;; calculating Fibonacci number of 10
CL-USER> (with-input-from-string
(in "
: <= over over < rot swap = or ;
: fib dup 0 swap <= if drop 0 else dup 1 = if drop 1 else
dup 1 swap - fib swap 2 swap - fib + then then ;
10 fib")
(let ((vm (uf:init-vm (uf:parse in))))
(uf:execute vm)
vm))
#<VM: (55)>
トークンのリスト（線形リスト、配列ではない）を辿ってナイーブにプログラムを解釈するので、とても遅い実装になっています。実装の詳細はShibuya.lispのlisp meetupで発表したときのスライドを眺めてみてください。
おれたちの戦いはこれからだ…
この実装で完全に理解した気になっていました。そして、あとは仕様のワードをひたすら実装していくだけだろうと。
しかし、そのときは知らなかったのです。Forthはただのスタックベースなプログラミング言語ではないことを…。
コンパイラをいじる
冒頭でこのように書きました:
その内部では極小のVMが動いており、ユーザ定義の手続き（Forth用語でワード）もVMのバイトコードのレベルまでコンパイルされます。
はい。たとえば、:を処理系が読むとコンパイルが始まり、;の前までのワードは基本的にコンパイルされ、実行されることはありません。じつは、制御構文であるifなどはコンパイルされてはじめて利用できるワードなのですが（マシン語レベルで判定とジャンプしている）、このifや:たち、じつは言語プリミティブではないのです。あるいはこうも言えます:
お好きなふるまいの制御ワードを、自分で定義できます。
Forth処理系は極小のVMが動いていると言いました。この極小のVMは、とても小さな機能の命令セットしか提供しません。たとえば「命令ポインタを一つすすめる」「名前（文字列）に対応するワード本体を探す」「空のワードをディクショナリの末尾につくる」「ディクショナリ末尾のワードの名前を設定する」などなど。そして、「コンパイル」中には、コード中のワードは実行されず、ワードの呼び出しコードがコンパイルされていきます。
また、コンパイルモードと実行モードを自由に行き来できたり、コンパイル中にも実行できる即値ワードというものを定義したりして、コンパイルの結果つくられるバイトコードをプログラムで操作することが可能です。
それらによって「ifがきたら、スタックトップを評価し、その値に応じて命令ポインタの移動先を変える」というようなVMそのものを操作するような処理を実現できてしまうのです。
パーサをいじる
また、インタプリタのパーサ部分も多少自由が利くようになっています。
たとえばこのような、:を用いてワードを定義するコードがあったとします:
: hello 1 . 2 . 3. ." Hello!" ;
:はhelloという名前をどうやって知るのでしょうか。あるいは変数を定義するVARIABLE nameもそうです。「プログラムは事前にパースされ、ASTとしてインタプリタに渡ってくる」と想定するなら、この問いはナンセンスです。しかしForthにはあるワードがあり、そのワードは「次の文字からスタックに積まれた「文字」までを読み込んで、その文字列を処理する」という処理を定義するワードです。Parsing wordと呼ばれています。
そのようなワードがあることで、パーサが処理する文字列はプログラムによって多少変更することができるため、事前にパースするにはそれ以前に実行してみないとわからないのです。
うむむ。なんだかむずかしげなものがでてきました。ここで言いたいことは、上記によってForthはメタプログラミングを可能にしていることなのです。
ふしぎ…。
実装してみた その2
規格化された仕様、メタプログラミング、プログラマブルなパーサ、C言語並みのスピードで、どうも宇宙にも行ったことがあるようです。あれっ。そんな言語、どこかで聞いたことがあるなあ…？
上述の特徴から滲みでるは変態性 イミフ具合 カッコよさ。超たのしい。
というわけで、上にでてきた処理系を一から書きなおし、コンパイラがあるバージョンを作成しています。WIPです。
現時点で
- コンパイルモード
- 線形リストではないプログラム
- VMの提供するプリミティブでワード定義を実現可能
- 即値ワード、
POSTPONE（ワードの遅延評価）
は実装しました。まだdefining wordというワードがないので、定数を扱うことができないのですが、それはおいおい実装していきたいです。
まとめ
言語処理系のための仮想機械のことを追いかけていたら出会ったプログラミング言語、Forth。この言語は初見のインパクトもさることながら、一歩踏み出してもまだ魅力たっぷりのステキな言語です。
みなさんも、Forthについて、まずはちょこっとWikipediaで調べてみると、たのしいかもしれませんよ。
参考文献
-
Leo Brodie, "Starting FORTH"
- Forth入門者向けに基礎からコンパイラ改変までを網羅的に解説した本
-
Forth 入門とかでググると出てくる同著者の"Thinking FORTH"はソフトウェア開発技法をForthで実践するという本なので、入門には不適
-
Forth Standard
- Forth 2012の仕様書の内容がオンラインで読める。必要ならばPDFファイルの仕様書も公開されているので、リファレンスとして読むのに最適
-
Doug Hoyte, "LET OVER LAMBDA"
- その邦訳
- Common Lispのマクロプログラミング技法の本だが、後半で
Forth万歳Forth実装がはじまるアツい本