「Forth」の版間の差分

提供: miniwiki
移動先:案内検索
ja>Ef3
(コードの構造: {{仮リンク|覗き穴最適化|en|peephole optimization}},ln)
 
(1版 をインポートしました)
 
(相違点なし)

2018/8/19/ (日) 20:03時点における最新版

Forth
パラダイム スタック指向English版手続き型
登場時期 1970年代
設計者 チャールズ・ムーア
型付け なし
主な処理系 SwiftForth, en:Gforth, VFX Forth
影響を受けた言語 バロースの大型システムLISP, APL
影響を与えた言語 MindFactorJoyCatRPL
テンプレートを表示

Forth(フォース)は、スタック指向のプログラミング言語およびそのプログラミング環境である。Forth はしばしば、かつての習慣に従ってすべて大文字で綴られることもあるが、頭字語ではない。

概要

Forth はスタック指向であり、逆ポーランド記法(RPN)と同様の後置記法による記述が一番の特徴である。その他の特徴としては、手続き型命令型であり、言語としては全ての値は型としての区別なく扱われること(型システムが無いこと)、制御構造などもプログラム可能であること(リフレクション)といったものがある。

典型的な Forth の実装には、LISP におけるRead–eval–print loopEnglish版(REPL)に対応する、入力されたワードを即座に実行する対話型のインタプリタモードと(これは、正規のオペレーティングシステムがないシステム向けのシェルにも適している)、後の実行のために一連のワードをコンパイルするモードのふたつのモードがある。後者にはコロン(:)というワードにより遷移しセミコロン(;)というワードで脱する。

初期の実装や移植性を目的とした実装にはスレッデッドコードを生成するものもあるが、近年の実装では他の言語のコンパイラのように最適化された目的コードを生成するものもある。

他の言語のシステムほどは人気はないが、商用においても Forth はいくつもの言語のベンダを引き止めるだけの十分なサポートを持っている。Forth は現在 Open Firmware のようなブートローダ宇宙開発[1]、組込みシステム、ロボット制御などに使われている。GNUプロジェクトによる実装であるGforthEnglish版は活発にメンテナンスされており、最新のリリースは2008年の12月である。

特徴

Forth の環境はコンパイラと対話形式のシェルが一体化している。実行時環境に似ている仮想マシンにおいて、ユーザは対話的に定義し、「ワード」(words) ともサブルーチンを実行する。ソースコードとしてテスト、再定義、デバッグされることができるワードは、プログラム全体を再コンパイルしたり再起動することなく組み込まれる。変数、基本的な演算子など、すべての構文要素はプロシージャのように見える。たとえ特定のワードが最適化されても、サブルーチンの呼び出しを必要とするといけないので、これもまた依然としてサブルーチンとして有効である。言い換えれば、シェルは対話的に入力されたコマンドをそれが実行される前にマシンコードにコンパイルする(この振る舞いは一般的だが、必須ではない)。どのように結果のプログラムが格納されるかはForth 環境によってさまざまだが、理想的には手動でそのコードが再入力されたときとプログラムの実行は同じ影響を持つ。コンパイルされる関数はプログラムオブジェクトの特殊なクラスで対話的コマンドは厳密にインタープレットされる、C言語Unixシェルの組み合わせとは対照的である。ほとんどのForth のユニークな性質はこの原理の結果である。対話性、スクリプティング、コンパイレーションがあることにより、Forth は BBC MicroApple II シリーズのようなリソースが限られたコンピュータでよく使われ、ファームウェアや小さなマイクロコントローラなどのアプリケーションで生き残っている。Cコンパイラがよりコンパクトで効率的なコードを生成しようとしている今まさにそのときでも、Forth の対話性における優位は保たれているのである。

スタック

再帰的なサブルーチンを持つすべてのプログラミング環境は制御フローのためにスタック (stack) を実装している。この構造は典型的にはローカル変数やサブルーチンの引数も格納する(C言語のようなシステムにおける call-by-value)。Forth にはしばしばローカル変数がないこともあるが、call-by-value でもない。代わりに、中間的な値は第二のスタックにおいて保持される。ワードはスタックの最も上にある値を直接操作する。それゆえ、これは「パラメータ」または「データ」スタックと呼ばれたりもするが、ほとんどの場合は単に「スタック」である。それから、関数呼び出しスタックは「リンケージ」(lincage) もしくは「リターン」(return) スタックと呼ばれ、rstack とも略される。カーネルから提供された特殊な rstack 操作関数はそれがワード内で一時的なストレージとして使われることを可能にするが、その一方でこれは引数や操作データを渡すことに使うことはできない。Forthはスタックの概念をうまく利用しており、演算は逆ポーランド記法により記述される。このため構文解析が極めて単純となり、プログラムおよび処理系が小さくて済む。これは、機器組み込み用プログラムでは有利な特徴である。

また、ルーチンは「ワード」単位で記述され、コンパイルされる。これらの「ワード」を集積して「ディクショナリ」を形成する。一般的なFORTH処理系におけるプログラミングは、インタプリタ上でのワード作成の積み重ねであり、対話的に行える。開発中でも部分的な処理を動かしてのテストがやりやすく、それらを適宜組み合わせてのテストも容易である。

ほとんどのワードはスタック上でのその効果の観点から定義される。典型的には、引数はワードが実行される前にスタックの一番上に置かれる。実行後は引数は消去され、何らかの返り値で置き換えられている。数学的な操作をするためには、これを逆ポーランド記法のルールに従う。スタックの使用法を図解した以下の例を参照すること。

保守

Forth は単純だが拡張性のある言語である。そのモジュール性と拡張性はCADシステムのような高度なプログラミングをも可能にする。しかしながら、拡張性は未熟なプログラマがわかりにくいコードを書くのも促すため、このことは Forth に「記述専用言語」との評判ももたらしている。大規模で複雑なプロジェクトでも成功裏に使われてきていて、有能でよく訓練されたプロフェッショナルによって開発されたアプリケーションが、何十年にもわたって発展していくハードウェアプラットフォーム上でも容易に保守されることを証明している[2]。Forth は天文学分野や宇宙開発分野という得意分野も持っている[3]

その移植性、効率的なメモリ使用、短い開発期間および高速な実行スピードのため、Forth は今日でもいまだ多くの組み込みシステム(小さなコンピュータ化されたデバイス)で使われている。これは近代的なRISCプロセッサ上で効率的に実装されてきており、マシン語としてのForthの利用も生み出されてきている[4]。他の Forth の用途としてはアップルIBMサン・マイクロシステムズOLPC XO-1に使われるOpen Firmware ブートロムが含まれる。また、FreeBSDオペレーティングシステムのFICL-based first stage boot controllerもある。

歴史

Forth はチャールズ・ムーア1958年から絶え間なく開発されていた個人的なプログラミングシステムから考案された[5]。1968年、家具と絨毯を扱う企業に雇われた際、このソフトウェアをミニコン上でFORTRANを使って書き直したものがForthの原型である、という。Forth が他のプログラマに最初に公開されたのは1970年代で、アメリカ国立電波天文台(NRAO)にいたアメリカの Elizabeth RatherEnglish版 によって始められたものである[5]1971年にNRAOの制御用ソフト作成において、ムーアはForthを完成させた。このNRAOにいた彼らの仕事のあと、チャールズ・ムーアとElizabeth Ratherは FORTH, Inc. を1973年に設立し、その後の 10 年でさらに磨きをかけるとともにいくつものプラットフォームに Forth システムを移植した。

1968年の"[t]he file holding the interpreter was labeled FOURTH, for 4th (next) generation software — but the IBM 1130 operating system restricted file names to 5 characters."[6]において Forth は命名された。ムーアは compile-link-go 第三世代プログラミング言語の後継、または「第四世代」ハードウェアのためのソフトウェアとして Forth を見ており、用語として使われるようになっていた第四世代プログラミング言語 (4GL) ではなかった。ムーアは、アセンブラ・FORTRAN・BASICに続く4番目の言語という意味で、このソフトウェアに「fourth」と名付けるつもりだったが、このミニコンで取り扱えるファイル名は最大5文字であったため「FORTH」という名になったという。

チャールズ・ムーアはたびたび仕事を渡り歩いていたため、初期の言語開発の困難は異なるコンピュータアーキテクチャへの移植の容易さであった。Forth システムはしばしば新しいハードウェアを育てるために使われていた。たとえば、Forthは1978年の新しい Intel 8086 チップ上の最初の常駐ソフトウェアで、MacFORTHは1984年の最初のアップルMacintoshの最初の常駐開発システムあった[5]

Forth, Inc の microFORTH は1976年に始まったIntel 8080, Motorola 6800, Zilog Z80 マイクロプロセッサ向けに開発された。MicroFORTH は 後に 1978年6502 のような他のアーキテクチャ向けの Forth システムを生成するのにホビーストたちにも使われた。広い普及は最終的に言語の標準化を誘導することとなった。共通の慣習は事実上の標準である FORTH-79[7] および FORTH-83[8] にそれぞれ1979年1983年に成文化された。これらの標準は1994年ANSIによって統合され、通常これは ANS Forth[9](ANSI INCITS 215-1994 (R2001)、ISO/IEC 15145:1997(E)のベースとなった)と呼ぶ。

Forth は1980年代にはとてもよく使われるようになったが[10]、これは小さくかつ移植性が高いとして当時の小さなマイクロコンピュータにとてもよく適していたからである。すくなくともひとつのホームコンピュータ、英国Jupiter ACEは そのROM常駐オペレーティングシステムに Forth を持っていた。キヤノン・キャットもまた そのシステムプログラミングのために Forth を使っていた。さらに Rockwell も常駐 Forth カーネルを持つ R65F11 と R65F12 のシングルチップマイクロコンピュータを製造していた。

標準規格

  • Forth-77 Standard
  • Forth-78 Standard
  • Forth-79 Standard
  • Forth-83 Standard
  • Forth-94 Standard
  • ISO/IEC 15145:1997(E) - Information technology - Programming languages - Forth (First edition: 1997-04-15)

プログラマの観点

Forthの後置記法は、データスタック(オペランドスタック、以下単にスタックと呼ぶ)を意識的に操作しなければならないというForthの特徴と密接に結びついている。すなわち、オペランドはそのままスタックに積まれ、後から現れる演算子などはスタックからそれを取り出して演算し、結果をスタックに積む、といったように動作する。多くの言語と違い、バッカス・ナウア記法で構文が定義されているわけでもなく、伝統的にはコンパイラは、スレッデッドコードと呼ばれるシンプルな構造の目的コードを直接生成するだけである。また、文法の修正のような、多くの言語では実装の内部に手を入れる変更が必要なことが、Forthではそのようなワードを定義することで可能である(これは、Lispのマクロに少し似ている)。なお、データスタックの他にリターンスタックがあり、そちらはワードの呼出しの後で手続きを再開するアドレス等が積まれるスタックである(CPUのいわゆるスタックに似ている)。

たとえば、25 * 10 + 50 は、次のように入力して計算する(「」は、改行の入力。「ok」はForth処理系が結果の出力の後に付けるプロンプト)。

25 10 * 50 + . ⏎
300 ok

まず最初に数値 25 と 10 がこの順でスタックに積まれる。テンプレート:Clr

ワード * がスタックの一番上にあるふたつの数を乗算し、その積に置き換える。テンプレート:Clr

それから数値 50 をスタックに積む。テンプレート:Clr

ワード + がこれに先ほどの積を加算する。最後に、. コマンドがスタックのトップを取り出して、それを、ユーザの端末に結果として出力する[11]テンプレート:Clr

 4 5 + .

これは、スタックに4を積み、さらに5を積み、スタック上の2つの値を取り出して加算、その結果をスタックに戻し、スタックの値を表示する操作を示している。

上記のように入力してエンター(⏎:リターン)を打鍵すると、画面上には下記のように結果が表示される。

4 5 + .  ⏎
9 ok

Forth の構造化機能でさえもスタックベースである。たとえば、

: FLOOR5 (n -- n')   DUP 6 < IF DROP 5 ELSE 1 - THEN ;

このコードは 次のコマンドを使うことによって FLOOR5 が呼ばれる新しいワード(繰り返すが、「ワード」という単語はサブルーチンとして使われている)を定義する。DUPはスタックの数値を複製する。6がスタックの一番上に 6 を配置する。ワード < はスタックの一番上の二つの数(6 と DUP で複製された入力の値)を比較し、真偽値で置き換える。IFは真偽値をとり、その直後のコマンドを実行するか、ELSEまでスキップするかを選択する。DROPはスタックの上の値を放棄する。そして、THENは条件分岐の終端である。括弧に囲まれたテキストは、このワードが期待するスタックの数と値を返すかどうかを説明するコメントである。ワード FLOOR5C言語で書かれた次の関数に相当する。

 int floor5(int v) { return v < 6 ? 5 : v - 1; }

この関数はより簡潔につぎのように書かれる。

: FLOOR5 (n -- n') 1- 5 MAX ;

このワードは次のように実行できる。

1 FLOOR5 . ⏎
5 ok
8 FLOOR5 . ⏎
7 ok

最初にインタプリタは数値 1(もしくは 8)をスタックにプッシュし、それからこの数値を再びポップし結果をプッシュする FLOOR5 を呼び出す。最後に、「.」の呼び出しは値をポップし、ユーザの端末にそれを表示する。

機能

Forth の構文解析は明確な文法がないので単純である。インタプリタはユーザ入力デバイスから入力された行を読み、それから区切り文字としての空白を使って単語に構文解析される。他の空白文字を認識するシステムもある。インタプリタがワードを見つけると、ディクショナリ (dictionary) からそのワードの検索を試みる。もしそのワードが見つかれば、インタプリタはワードに関連付けられたコードを実行し、それから入力システムの残りを構文解析するために復帰する。もしワードを発見することができないなら、ワードをだと仮定して数値への変換を試み、それをスタックにプッシュする。これが成功すれば、インタプリタは入力システムからの構文解析を継続する。辞書の参照と数値への変換の両方が失敗した場合、インタプリタはそのワードが認識できないというエラーメッセージに続けてそのワードを表示し、入力ストリームをフラッシュし、ユーザからの新しい入力を待機する[12]

新規ワードの定義は、ワード:(コロン)から始まり、;(セミコロン)で終了する。たとえば、

: X DUP 1+ . . ;

のコードはワード X をコンパイルし、辞書にこの名前が発見できるようにする。コンパイルと言っても、文頭にコロン、その後にワードの名称を置き、そこから一連の式を並べておいて、文末にセミコロンを付加するだけでよい。10 Xコンソールに入力して実行すると、11 10 が表示されるようになるだろう[13]

例えば、前述の式をfooという語(ワード)としてコンパイルするには、以下の通り記述する。記述法はコロン記号で始まりセミコロン記号で終わるので、「コロン定義」と呼ばれる。

 : foo 4 5 + . ;

コンパイルすることにより、FORTHの辞書(ディクショナリ)に、この語(ワード)が登録されることになる(この場合はfooが登録される)。

実のところ、FORTHでは「+」や「.」などの演算子や出力機能などの全てがワードである。こういった組み込み済みのワードと、ユーザが後からコロン定義(コンパイラ)で追加したワードと、2つの間に本質的な差異はない。コンパイルしたワードはただちに環境に組み込まれ、インタプリタより単独で実行できるようになる。つまり、そのFORTH処理系を拡張するのである。このような点より、FORTHは自己拡張性が高いと云われる。

プログラムの開発においては、処理毎に区切ってワードとして順次構築していくので、注意深く進めていけば自然ときれいに構造化されることになる。ワードは単独で実行できるため、部分に分けてのデバッグも容易である。また、それらのワードを使ってテスト用の処理(ワード)を気軽に作成して実行・テストできる。

多くの Forth システムは実行可能なワードを生成する特殊化されたアセンブリ言語を含む。このアセンブラはコンパイラの特殊な方言である。Forth アセンブラはしばしば命令の前に引数がくる逆ポーランド記法を使う。Forth アセンブラの普通の設計では命令をスタック上に構築し、それからこれを最後の段階でメモリにコピーする。Forth システムでは、番号(0..n, 実際のオペレーションコードとして使われる)付けされるかその目的に応じて名づけられた、製作者によって使われる名前でレジスタは参照されることもある。たとえば、スタックポインタとして使われるレジスタは「S」など。[14]

オペレーティングシステムとファイル、マルチタスク

古典的な Forth システムでは伝統的にオペレーティングシステムファイルシステムも使われない。コードはファイルに格納される代わりに、ソースコードは物理的なディスクアドレスに書かれたディスクブロックに格納される。ワード BLOCK はディスクスペースの1キロバイトサイズのブロックの数値からデータを格納しているバッファのアドレスへの変換に割り当てられ、Forth システムによって自動的に管理される。固定されたディスクブロック範囲にファイルが配置されるときには、システムのディスクアクセスが使われる実装もある。たいていはこれらはディスクブロックごとのレコードの整数をつかって、固定長バイナリレコードして実装される。高速な検索はキーデータ上のハッシュアクセスによって実現される。

ふつうは cooperative なラウンドロビンスケジューリングであるマルチタスクは、通常利用可能である(ただし、マルチタスキング・ワードとサポートは ANSI Forth 規格ではカバーされていない)。ワード PAUSE は、次のタスクの配置や実行コンテキストのリストアための 現在のタスクの実行コンテキストの保存に使われる。どちらのタスクも自分自身のスタックやいくつかのコントロール変数のコピー、スクラッチエリアを持っている。タスクのスワップは単純で、効率的である。その結果、Forth マルチタスクは Intel 8051, Atmel AVR, and TI MSP430のような非常に単純なマイクロコントローラでさえ有効である[15]

その一方で、Microsoft WindowsLinuxUnixのようなホストオペレーティングシステムのもとで実行され、ソースやデータのファイルのためにホストオペレーティングシステムのファイルシステムを利用する Forth システムもある。ANSI Forth 規格では I/O のために使われたワードについて書かれている。他の標準的でない機能はホスト OS やウィンドウシステムへのシステムコールを発行するためのメカニズムも含み、多くはオペレーティングシステムから提供されるスケジューリングを採用する拡張を提供する。典型的には、タスク作成、一時停止、解体、および優先順位の変更のために、スタンドアロンのForthの PAUSEワードとは大きくて異なったワードのセットを持っている。

セルフコンパイルとクロスコンパイル

すべてのソースコードとともに十分な機能を有する Forth システムは自身をコンパイルすることができ、Forth プログラマはこのようなテクニックを普通メタ・コンピレーション (meta-compilation) と呼ぶ(ただし、この用語は普通の定義であるメタコンピレーションとは厳密には一致しない)。通常の方法はコンパイルされたビットをメモリに配置する一握りのワードの再定義である。コンパイラのワードはメモリ内のバッファエリアにリダイレクトされることができるフェッチとストアの、特別に命名されたバージョンを使う。このバッファエリアはコードバッファというより異なるアドレスから始まるメモリ領域へのシミュレートやアクセスをする。このコンパイラは対象のコンピュータのメモリとホストの(コンパイルする)コンピュータのメモリの両方にアクセスするワードを定義する[16]

フェッチやストア操作がコード空間に再定義されたあと、コンパイラやアセンブラなどはフェッチやストアの新たな定義を使って再コンパイルされる。これはコンパイラとインタプリタのすべてのコードの効果的な再利用である。それから、Forth システムのコードはコンパイルされるが、このバージョンはバッファに格納される。このメモリ内のバッファはディスクに書きこまれ、これをテストのために一時的にメモリにロードする方法が提供される。新たなバージョンがきちんと機能するようなら、これは以前のバージョンに上書きされる。

異なる環境のためのバリエーションが多数存在する。組み込みシステム向けには、代わりに他のコンピュータのためにコードが書かれることになるが、このテクニックはクロスコンピレーションとして知られ、シリアルポートや単独の TTL ビット越しでさえ、その上オリジナルのコンパイルするコンピュータのワード名やディクショナリの他の実行されない部分も維持する。このようなForthコンパイラのための最小の定義は バイト単位のフェッチやストアをするワードと、実行される Forth ワード を命令するワードである。しばしばもっとも多くの時間のかかるリモートのポートへの書き込みの部分は、フェッチやストア、実行を実装するための初期化プログラムの構築であるが、多くの現代的なマイクロプロセッサ(Motorola CPU32など)は、このタスクを排除する統合されたデバッグ機能を持っている[17]

言語の構造

Forthの基本的なデータ構造は、「ワード」を実行可能なコードや名前のつけられたデータ構造を対応させる「ディクショナリ」である。このディクショナリは、門番(通常は NULL ポインタ)が発見されるまで最も新しく定義されたワードから最も古いワードまで進むリンクを用いた連結リストのツリーとして、メモリに展開される。コンテキストスイッチは異なる葉で開始するためにリスト検索を引き起こす。首位のメインの幹への枝のマージは最終的にルートの門番へ戻ってくるので、連結リスト検索は継続する。そこはさまざまなディクショナリになることができる。メタコンピレーションのような稀なケースでは、ディクショナリは隔離されスタンドアロンである。この効果は名前空間のネストのそれに似ていて、コンテキストに依存するキーワードのオーバーロードが可能である。

定義されたワードは一般的にヘッドボディからなり、ヘッドは名前フィールド (NF) とリンクフィールド (LF) からなり、ボディはコードフィールド (CF) とパラメータフィールド (PF) からなる。

ディクショナリのエントリのヘッドとボディは、隣接していないかもしれないので別々に扱われる。たとえば、Forth プログラムが新しいプラットフォームのために再コンパイルされたとき、ヘッドはコンパイルするコンピュータに残るかもしれないが、ボディは新しいプラットフォームに行ってしまっている。組み込みシステムのようないくつかの環境によっては、ヘッドは不必要にメモリを占有する。しかしながら、もしターゲット自身が対話的なForthをサポートすることを期待されるなら、クロスコンパイラによってはヘッドをターゲット内に配置するかもしれない[18]

ディクショナリのエントリ

ディクショナリの厳密なフォーマットは規定されず、実装に依存する。しかしながら、いくつかのコンポーネントはほとんどいつも提示しており、しかし、厳密なサイズと順序は変わるかもしれない。記述された構造、ディクショナリエントリはこのように見えるかもしれない[19]

structure
  byte:       flag           \ 3bit flags + length of word's name
  char-array: name           \ name's runtime length isn't known at compile time
  address:    previous       \ link field, backward ptr to previous word
  address:    codeword       \ ptr to the code to execute this word
  any-array:  parameterfield \ unknown length of data, words, or opcodes
end-structure forthword

この名前フィールドはワードの名前の長さ(典型的には32バイト)を与えるプリフィックスで開始し、何ビットかはフラグ用である。それからワードの名前の文字表現がプリフィックスのあとに続く。特定のForth実装に依存するが、アラインメントのためひとつ以上の NUL ('\0') バイトがあるかもしれない。

リンクフィールドは以前に定義されたワードへのポインタを含む。このポインタは次に古い隣接するワードへの、相対的な変位かもしれないし、絶対的なアドレスかもしれない。

このコードフィールドポインタは コードを実行するワードのアドレスか、パラメータフィールド内のデータか、プロセッサ直接実行するであろうマシンコードの開始のいずれかになるだろう。ワードを定義するコロンでは、コードフィールドポインタはリターンスタック上の現在の Forth 命令ポインタ (instruction pointer, IP) を保存し、ワードを実行継続するための新たなアドレスを用いてIP をロードするワードを指し示す。これはプロセッサの call/return 命令が行っているのと同様である。

コンパイラの構造

コンパイラ自身はモノリシックなプログラムではない。これは システムから可視な Forth ワードとプログラマから利用可能なものとからなっている。このことはプログラマが特殊な目的のためにコンパイラのワードを変更することを可能にする。

名前フィールド内の「コンパイル時」フラグは、「コンパイル時」の振る舞いのワードのセットである。ほとんどの単純なワードは、それがコマンドライン上で入力されたかコードに埋め込まれたかにかかわらず、同じコードが実行される。そのようにコンパイルされるとき、コンパイラはコードかワードへのスレッデッドポインタを単に配置する[13]

コンパイル時ワードの古典的な例は IF and WHILE といった制御構造である。Forth のすべての制御構造とほとんどすべてのコンパイラはコンパイル時ワードとして実装される。すべての Forth 制御フローワードは、プリミティブなワードBRANCH?BRANCH(もしfalseなら分岐する)の各種の組み合わせをコンパイルするために、コンパイルの間に実行される。コンパイルの間、データスタックは制御構造のバランシング、ネスティング、ブランチアドレスのバックパッチングをサポートするのに使われる。コード断片

... DUP 6 < IF DROP 5 ELSE 1 - THEN ...

は定義の内側では典型的には次のような一連にコンパイルされる。

... DUP LIT 6 < ?BRANCH 5  DROP LIT 5  BRANCH 3  LIT 1 - ...

BRANCHのあとの数のは相対的なジャンプアドレスを表している。LITは「リテラル」数値をデータスタックにプッシュするためのプリミティブなワードである。

コンパイル時と実行時

ワード :(コロン)は名前を引数として構文解析し、辞書にヘッダを作り(記述法はコロン記号で始まりセミコロン記号で終わるので、コロン定義, colon definition)、コンパイル状態に突入する。コンパイラは後続のワードをコンパイルしていく。このときワードが後述する即時ワードである場合は実行し、そうでない場合は実行時に呼び出されるようにコンパイルする。

ワード;(セミコロン)は現在の定義を終了し、実行状態へと復帰する。

システムの状態はワード [(左大括弧)及び ](右大括弧)を用いて手動で変更させることができ、それぞれ実行状態とコンパイル状態に突入する。ANS Forthでは、現在のインタプリタの状態はフラグ STATEから読み取ることができ、コンピレーションステート状態 true、そうでなければ false の値がこいる。をこのインタプリタの現在の状態による振る舞いコンパイル時ステートスマートワード (state-smart words) の実装を可能にする。

イミディエイトワード

ワードIMMEDIATEは、直近のコロン定義を、即時ワードにする。即時ワードは通常はコンパイル後ではなくコンピレーションの間に実行されるが、どちらのステートにおいてもプログラマにオーバーライドされることができる。; は即時ワードの一例である。ANS Forth では、ワードがイミディエイトとしてマークされていても、ワード POSTPONE は名前を引つけられたワードのコンピを強制的にコンパイルする。

無名ワードと実行トークン

ANS Forth では、ワード :NONAME を用いて、次の;(セミコロン)までの後続のワードをコンパイルし、実行トークン (execution token) をデータスタック上に残す、無名のワードが定義できる。

ワード EXECUTE はデータスタックから実行トークンを取り出し、関連づけられたセマンティクスを実行することができる。またワード COMPILE,(COMPILE コンマ)は、データスタックから実行トークンを取り出し、コンパイルする。

ワード ' (tick) は、ワード名を引数としてとりデータスタック上のワードに関連づけられた実行トークンを返す。

ワードの構文解析とコメント

ワード : (colon)、POSTPONE' (tick)と :NONAME は、データスタックの代わりにユーザからの入力からそれらの引数をとる構文解析ワード (parsing words) の例である。別の例では、コロン定義において、次の右括弧を含む後続のワードを読み込んで無視し、コメントを配置するのに使われる ((左括弧)がある。同様に、ワード \(バックスラッシュ)は現在の行の終端まで続くコメントのために使われる。

コードの構造

ほとんどの Forth システムにおいて、コード定義のボディはマシン語といくつかの形式のスレッデッドコード[20]からなる。非公式の FIG 規格 (Forth Interest Group) のあとに続くオリジナルの Forth は、TIL (Threaded Interpretive Language) である。これは 間接スレッディング(indirect-threading)とも呼ばれ、直接スレッディング(direct-threading) と サブルーチン・スレッディング(subroutine-threading) も現在はよく使われるようになってきた。最初期のモダンな Forth はサブルーチン・スレッディングを使っており、マクロとしてシンプルなワードを挿入し、より小さく速いコードを生成するために のぞき穴的最適化English版 や他の最適化戦略を実行した[21]

データオブジェクト

ワードが変数や他のデータオブジェクトであるとき、CPはそれを作成した定義ワードに関連付けられたランタイムコードを指している。定義ワードは特徴的な"defining behavior"(ディクショナリエントリの作成に加え、もしかしたらアロケートとデータ領域の初期化をする)を持っており、この定義しているワードによって構築されたワードのクラスのインスタンスの振る舞いの定義もする。たとえは、

VARIABLE
初期化されていないものを命名する、one-cell memory location。VARIABLE のインスタンスの振る舞いはそのスタック上のアドレスを返す。
CONSTANT
値を命名する(CONSTANTの引数として指定する)。インスタンスの振る舞いは値を返す。
CREATE
位置を命名する。空間がこの場所に確保されるか、さもなくばこれは文字列か他の初期化された値を格納するためにそれがセットされることができる。インスタンスの振る舞いは、この空間の開始のアドレスを返す。

Forth は、カスタム定義の振る舞いとインスタンスの振る舞いを指定する、新しいアプリケーション特有の定義ワードをプログラマが定義できる機能もまた提供する。円形バッファ、I/Oポート上で命名されたビット、自動的にインデックス化された配列などの例がある。

これらに定義されたデータオブジェクトと同様のワードはスコープにおいてグローバルである。他の言語でローカル変数から提供された関数は、Forth ではデータスタックから提供される(しかし、Forth も真のローカル変数は持っている)。Forth のプログラミングスタイルは他の言語に比べ、ごく少数の名付けられたデータオブジェクトを使う。典型的にはこのようなデータオブジェクトは、たくさんのワードやタスク(マルチタスクの実装においては)によって使われるデータを格納するのに使われる[22]

Forth は型システムを持たない。したがって値の操作は全てプログラマの責任で行われる。

プログラミング

Forth で書かれたワードは実行可能な形式にコンパイルされる。古典的実装は、順に実行されるワードのアドレスのリストをコンパイルする。多くの現代的なシステムは実際のマシンコードを生成する(いくつかの外部ワードの呼び出しと、適当な場所に展開された他者のためのコードを含む)。最適化コンパイラをもつシステムもある。一般的な場合、Forth プログラムは実行可能形式としてロードされたとき実行されるコマンド (e.g., RUN) を含めた、Forthプログラムのコンパイル済みコードのメモリイメージとして保存されている。

開発中、プログラマは小さなコード片を開発したときに実行およびテストするためにインタプリタを使う。そのため、ほとんどの Forth プログラマは緩やかなトップダウン設計と、単体テストと統合の繰り返しによるボトムアップ開発を支持している[23]

トップダウン設計では、普通まずプログラムを「語彙」へのプログラムを分割し、それらを最終的に必要なプログラムを書くための、高レベルなツールセットとして利用する。よく設計された Forth プログラムは自然言語のように読むことができ、単一の目的を達成するために用いられるだけでなく、関連する問題を解くプログラムを書くのに利用することができる[24]

コード例

Hello world

For an explanation of the tradition of programming "Hello World", see Hello world.

実装の一つとしては、

: HELLO  ( -- )  CR ." Hello, world!" ; HELLO <cr>
HELLO

ワード CR (Carriage Return) は後続の出力を新しい行の上に表示するようにする。構文解析ワード ." (dot-quote) はダブルクオートで区切られた文字列を読み、構文解析された文字列が実行時に表示されるように現在の定義にコードを追加する。文字列 Hello, world! からこの空白文字で区切っているワード ." は、文字列には含まれていない。これは構文解析器が ." を Forth ワードとして認識するために必要である。

標準的な Forth システムはインタプリタでもあり、同じ出力は次のコード片を Forth コンソールに入力することで得ることができる。

CR .(Hello, world!)

.( (dot-paren) は括弧で囲まれた文字列を構文解析し、これを表示するイミディエイトワードである。."と同様に、Hello, world! から空白文字で区切られた.( は文字列の一部ではない。

ワード CR は表示する文字列の前にくる。慣例的に、Forth インタプリタは新規行に出力を開始しない。また、慣例により、インタプリタは直前の行の終端、okプロンプトの後で入力を待つ。他のプログラミング言語で時々そうであるような、Forth の CR にはバッファをフラッシュする暗黙の動作はない。

コンピレーションステートとインタープリテーションステートの混用

ここに 実行されると単一の文字 Q を発行するワード EMIT-Q の定義がある。

: EMIT-Q   81 (the ASCII value for the character 'Q') EMIT ;

この定義は Q のASCII値 (81) を直接を使うことで書かれている。括弧の間の文字列はコメントで、コンパイラに無視される。ワード EMIT はデータスタックから値をとり、対応する文字を表示する。

次の EMIT-Q の再定義は、ワード[(左大括弧)、](右大括弧), CHARLITERAL をインタプリタステートを一時的に切り替えるために使っており、文字 Q のAscii値を計算し、コンピレーションステートを返し、計算した値を現在のコロン定義に追加する。

: EMIT-Q   [ CHAR Q ]  LITERAL  EMIT ;

構文解析ワード CHAR は空白で区切られたワードをパラメータとしてとり、データスタック上のその最初の文字の値を置く。ワード [CHAR]CHAR のイミディエイトバージョンである。[CHAR]を使って、EMIT-Q の定義例は次のように書くことができる。

: EMIT-Q   [CHAR] Q  EMIT ; \ Emit the single character 'Q'

この定義はコメントを書くために \(バックスラッシュ)を使っている。

CHAR[CHAR]の両方は ANS Forth では事前に定義される。IMMEDIATEPOSTPONE と使って、[CHAR] はこのように定義することができる。

: [CHAR]   CHAR  POSTPONE LITERAL ; IMMEDIATE

完全な RC4 暗号プログラム

1987年、Ron Rivest は RC4 暗号システムを RSA Data Security, Inc. のために開発した。このコードは非常に単純で、説明を読めば大抵のプログラマは書くことができる。

それぞれすべて値の異なった 256 バイトの配列がある(訳注:これが暗号ストリームの状態であり、鍵で適当に初期化する)。

この配列が使われるときはいつも、2つのバイトが交換されることによって変更される。

この交換はカウンタ i および j によって制御され、どちらも最初は 0 である。

新しい i を取得するには 1 を加算する。

新しい j を取得するには、新しい i の位置にある配列のバイトを加算する。

ij の位置にある配列の値を交換する。

このコード(訳注:後のXORに使う値)は ij の位置にある配列のバイトの和の位置にある配列のバイトである。

平文を暗号化したり暗号文を復号するためには、このバイトを XOR される。

配列は最初の設定によって 0 から 255 にかけて初期化される(訳注:手順の途中に書いてあるが、これは最初に行う)。

それから ij を使う、i の位置にある配列のバイトを j に加算による新しい j とキーのバイトの取得、ij のバイトの交換と手順は進んでいく。

最後に、ij は 0 にセットされる。

すべての加算は 256 を法とするモジュラ演算である。

さらなる情報は、http://ciphersaber.gurus.com を参照すること。

以下の標準の Forth バージョンはコアのワードのみを使っている。

0 VALUE ii
0 VALUE jj
CREATE S[] 256 CHARS ALLOT
: ARCFOUR  (c -- x)
	ii 1+ DUP TO ii 255 AND		( -- i)
	S[] +  DUP C@			( -- 'S[i] S[i]) 
	DUP jj +  255 AND DUP TO jj	( -- 'S[i] S[i] j)
	S[] +  DUP C@ >R			( -- 'S[i] S[i] 'S[j])
	OVER SWAP C!      		( -- 'S[i] S[i])
	R@ ROT C!			( -- S[i])
	R> +				( -- S[i]+S[j])
	255 AND S[] + C@			( -- c x)
	XOR ;
: ARCFOUR-INIT	(key len -- )
	256 MIN LOCALS| len key |
	256 0 DO  I  S[] I + C!  LOOP
	0 TO jj 
	256 0  DO			(key len -- )
		  key I len MOD + C@  
		  S[] I  + C@  + jj + 255 AND TO jj
		  S[] I  + DUP C@  SWAP (c1 addr1)
		  S[] jj + DUP C@  (c1 addr1 addr2 c2) ROT C! C!
	     LOOP
	0 TO ii  0 TO jj ;

これはこのコードを検証する多くのテストのひとつである。

CREATE KEY: 64 CHARS ALLOT
: !KEY (c1 c2 ... cn n—store the specified key of length n)
	DUP 63 U> ABORT" key too long (<64)"
	DUP KEY: C! KEY: + KEY: 1+ SWAP ?DO  I C!  -1 +LOOP ;
 
	HEX  61 8A 63 D2 FB  5 !KEY
	KEY: COUNT ARCFOUR-INIT
	CR 
	   DC ARCFOUR 2 .R SPACE
	   EE ARCFOUR 2 .R SPACE
	   4C ARCFOUR 2 .R SPACE
	   F9 ARCFOUR 2 .R SPACE
	   2C ARCFOUR 2 .R
	CR .(Should be: F1 38 29 C9 DE)

実装

Forth 仮想マシンは実装が単純で規格のリファレンス実装を持たないため、大量の言語実装が存在する。標準的な各種デスクトップコンピュータシステム (POSIX, Microsoft Windows, macOS) をサポートしていることに加え、これらの多くの Forth システムは各種の組み込みシステムもまた対象としている。1994年の ANS Forth 規格に準拠するさらに有名ないくつかのシステムが列挙する。

Forthベースの言語等

  • Forthをベースにしてワードを日本語で記述可能にした言語としてMindがある
  • Forthをベースに、オブジェクト指向に改良したMac OS向けの開発システムMopsオブジェクト指向マルチスレッド対応のPalo Alto Shipping Co.製のMach1(まっはわん)がある。
  • Open Firmwareのシェル言語はForthベースである。SunのOpenBoot PROM(OBP)やCHRPベースのPower Macintoshの起動用ファームウェアはOpen Firmwareの実装である。
  • Forthを元にしたコマンド言語であるFiclFreeBSDのブートローダの実装に使われている。
  • 1985年ごろ、服飾メーカーとして知られるJUN(株式会社ジュン)が開発したコンピュータグラフィックシステム4D-Boxのオペレーション言語0DLはForthであった。

似た言語等

  • PostScriptは、Forthと同じく後置記法でスタック指向であり、類似性が指摘されることがある(が、作者によれば影響されたものではない)。
  • TeleScript General Magic社が開発・提供していた次世代エージェント指向の通信用プログラム言語。Forthアーキテクチャで実装されていた。

脚注

  1. NASA applications of Forth
  2. Forth Success Stories”. . 2006閲覧.
  3. Space Related Applications of Forth”. . 2007閲覧.
  4. Forth Chips Page”. pp. 54. . 2006閲覧.
  5. 5.0 5.1 5.2 The Evolution of Forth”. ACM SIGPLAN Notices, Volume 28, No. 3. March, 1993. ACM SIGPLAN History of Programming Languages Conference (1993年4月). . 2010閲覧.
  6. Moore, Charles H (1991年). “Forth - The Early Years”. . 2006閲覧.
  7. The Forth-79 Standard (PDF)”. . 2010閲覧.
  8. The Forth-83 Standard”. . 2010閲覧.
  9. Programming Languages: Forth”. ANSI technical committee X3J14 (1994年3月24日). . 2006閲覧.
  10. “The Forth Language”, BYTE Magazine 5 (8), (1980) 
  11. Brodie 1987, p. 20.
  12. Brodie 1987, p. 14.
  13. 13.0 13.1 Brodie 1987, p. 16.
  14. Rodriguez, Brad. “B.Y.O.ASSEMBLER”. . 2006閲覧.
  15. Rodriguez, Brad. “MULTITASKING 8051 CAMELFORTH (PDF)”. . 2006閲覧.
  16. Rodriguez, Brad (1995年7月). “MOVING FORTH”. . 2006閲覧.
  17. Shoebridge, Peter (1998年12月21日). “Motorola Background Debugging Mode Driver for Windows NT”. . 2006閲覧.
  18. Martin, Harold M. (1991年3月). “Developing a tethered Forth model”. ACM Press. . 2006閲覧.
  19. Brodie 1987, pp. 200–202.
  20. マルチスレッド・プログラミングとは異なる
  21. Ertl, M. Anton; Gregg, David. “Implementation Issues for Superinstructions in Gforth (PDF)”. . 2006閲覧.
  22. Brodie, Leo (1987). “Under The Hood”, Starting Forth (paperback), 2nd, Prentice-Hall, 241. ISBN 0-13-843079-9. “To summarize, there are three kinds of variables: System variables contain values used by the entire Forth system. User variables contain values that are unique for each task, even though the definitions can be used by all tasks in the system. Regular variables can be accessible either system-wide or within a single task only, depending upon whether they are defined within OPERATOR or within a private task.” 
  23. Brodie, Leo (1984). Thinking Forth (paperback), Prentice-Hall. ISBN 0-13-917568-7. 
  24. The classic washing machine example describes the process of creating a vocabulary to naturally represent the problem domain in a readable way.

参考文献

  • Brodie, Leo (1987). Starting Forth (paperback), Second, Prentice-Hall. ISBN 0-13-843079-9. 
  • Brodie, Leo (2007). in Marcel Hendrix: Starting Forth (Online book), Marlin Ouverson, Web edition, FORTH, Inc.. Retrieved on 2007-09-29. 
  • Brodie, Leo (2004). in Bernd Paysan: Thinking Forth (PDF Online book). ISBN 0-9764587-0-5. Retrieved on 2008-09-15. 
  • Conklin, Edward K.; Elizabeth D. Rather et al. (2007-09-08). Forth Programmer's Handbook (paperback), 3rd, BookSurge Publishing, 274. ISBN 1-4196-7549-4. 
  • Rather, Elizabeth D.. Forth Application Techniques (spiral bound), Forth Inc., 158. ISBN 0-9662156-1-3. 
  • Pelc, Stephen F. [2005]. Programming Forth (spiral bound), MicroProcessor Engineering Ltd, 188. 
  • Kelly, Mahlon G.; Nicholas Spies. FORTH: A Text and Reference. Prentice-Hall. ISBN 0-13-326331-2. 
  • Koopman, Jr, Philip J. (1989). Stack Computers: The New Wave (hardcover), Ellis Horwood Limited. ISBN 0-7458-0418-7. 
  • Pountain, Dick (1987). Object-oriented Forth: Implementation of Data Structures (paperback), Harcourt Brace Jovanovich. ISBN 0-12-563570-2. 
  • Payne, William (19 December 1990). Embedded Controller Forth for the 8051 Family. Elsevier, 528. ISBN 978-0125475709. 

関連項目

外部リンク