HN 日本語サマリー

← 一覧へ戻る
プログラミング

LispによるForthの実装、そしてForthからLispへ

Lisp moving Forth moving Lisp (letoverlambda.com)

95 pointsby fallat23 コメント

要約

この記事は、Lispのマクロ機能を用いてプログラミング言語Forthを実装する手法を解説しています。Forthの歴史、哲学、そしてLisp環境での実装における「レジスタ」や「辞書」といった概念を、Lispのコード例と共に説明し、両言語のメタプログラミングにおける類似性と違いを探求します。

全文翻訳

Let Over Lambda -- Lispの50年

Doug Hoyte著

LispがForthを動かし、ForthがLispを動かす

設計上の奇妙さ

この章は、これまで本書で見てきた多くのマクロテクニックの集大成です。開発したマクロ抽象化を利用して、私のお気に入りのプログラミング言語の一つであるForthの実装を作成します。この実装はForthの重要なアイデアの多くを体現していますが、非常に異なっており、リスピーです。この章のコードにはいくつかの興味深い用途がありますが、その主な目的は、Forthのメタプログラミングの概念と基礎をLispの読者に教えること、そして本書の中心テーマであるマクロによる構文の二重性の作成と使用のプラットフォームとなることです。

Forthは、Lispを除くほとんどの言語よりも、豊かで魅力的な歴史を持っており、それに出会えたことに感謝しています。その理由と、その他のすべてのために、この章は、私にForthとコンピュータプログラミングを紹介してくれた父、Brian Hoyteに愛を込めて捧げられます。この章は、[THREADING-LISP]とHenry Bakerの研究[LINEAR-LISP][LINEAR-LISP-AND-FORTH]に部分的に触発されています。

Forthは、強力な政府、学術、または企業のスポンサーなしに作成および開発された最初のプログラミング言語でした。あるいは、少なくとも成功した最初のそのような言語でした。大規模組織のニーズによって動機付けられるのではなく、ForthはChuck Mooreによって1968年頃に、天文学、ハードウェア設計などの自身のコンピューティングニーズを解決するために独立して発明されました。それ以来、Forthは情熱的な草の根ユーザーコミュニティによって配布、実装、改善されてきました[EVOLUTION-FORTH-HOPL2]。Forthを、初期LispやCOMMON LISPのMIT(後にDARPA)のパトロン、IBMのFORTRAN、AT&TのUnix言語Cと比較してください。

これらのルーツと、コンピュータソフトウェアおよびハードウェアの役割に関する一般的な哲学の違いにより、Forthは異なります。Lisp以上に、Forthは奇妙に見えます。しかし、Lispと同様に、Forthが奇妙に見えるのには理由があります。それはスタイル以上のものを考慮して設計されたからです。Forthは設計上奇妙であり、この設計はマクロに関連しています。

今日、Forthは一般的に「組み込みプラットフォーム」、つまりリソースが非常に制約されているコンピュータで見られます。Forthの設計が、作成されたほとんどすべてのプログラマブルコンピュータシステムに言語全体を実装できることは、その証です。Forthは、実装と実験を可能な限り容易にするように設計されています。実際、Forthクローンを作成することは非常に些細なことなので、プログラミング言語の設計に関心のあるプログラマーにとって、Forthスタイルのスタックベース言語を1つか2つ発明することは、ほとんど通過儀礼となっています。Forthにルーツを持ち、興味深い貢献をしたスタックベース言語には、PostScriptやJoyがあります。

しばしば、重要なForthの実装上の決定は、Forthが実装されているコンピュータの正確なリソースに基づいています。Forthプログラマーは、実際のレジスタにマッピングされるか、メモリ位置にマッピングされるか、あるいはまったく異なる方法で実装される必要がある抽象レジスタのセットを考案しました。しかし、無限の可能性とほとんど制約のない環境であるLispでForthを実装する場合、どうすればよいでしょうか? Forthの抽象レジスタの任意のマッピングをLispコードに単純に課すのではなく、一歩引いて考えてみましょう。もしChuckがLispマシンを持っていたら、Forthはどのように見えるでしょうか? 任意の機械(実機または仮想)の能力にForthを適合させるのではなく、Lisp上で実装された場合にシンプルさと能力のために最適化された、Forthの抽象レジスタの最小セットを探求します。

しかし実際、最適な抽象概念のセットを探すことは、Chuckが数十もの異なるForth実装を多数のアーキテクチャで作成しながら行ったことです。だからこそForthは素晴らしいのです。Lispと同様に、Forthは言語設計空間における高い局所的極大値を表しており、Lispと同様に、Forthはプログラミング言語や標準セットというよりも、何が機能し何が機能しないかに関する構築材料と知恵のコレクションです。

FORTH-REGISTERS

(defvar forth-registers
        '(pstack rstack pc
          dict compiling dtable))

forth-registers変数は、私たちのForthマシンの抽象レジスタを表すシンボルのリストです。もちろん、Lispはレジスタやフィクスナムの用語では考えず、代わりに変数とシンボルで考えます。単なる変数名のリストからForth環境の開発を始めるのは奇妙に思えるかもしれませんが、これは実際にはForthシステムを実装する際の最初のステップです。Forthを作成することは、Lispにのみ美しさと巧妙さで勝る独創的なブートストラッププロセスです。このプロセスの控えめな説明を以下に示します。

Forthの特徴的な機能の1つは、プログラムがサブルーチンにパラメータを渡したり、これらのサブルーチン全体での実行パスを追跡したりするために使用するスタックデータ構造への直接アクセスです。Forthは、ほとんどのプログラミング言語とは異なり、スタックデータ構造のこれらの2つの用途を、操作できる2つのスタックに分離しています1。典型的なC実装では、関数呼び出しのパラメータとそのいわゆるリターンアドレスは、すべての関数呼び出しに対して単一の可変サイズのスタックフレームに格納されます。Forthでは、これらはパラメータスタックとリターンスタックと呼ばれる2つの異なるスタックであり、抽象レジスタpstackとrstackとして表されます。私たちはCOMMON LISPのpushとpopマクロを使用します。これは、これらのスタックがほとんどのForthで使用される配列データ構造ではなく、コンスセルリンクリストで実装されていることを意味します。

抽象レジスタpcはプログラムカウンタの略で、現在実行中のコードを指すポインタです。Forthコードとは何か、そしてそれをどのように指し示すことができるかは、抽象レジスタcompilingとdtableとともに、すぐに説明します。

FORTH-WORD

(defstruct forth-word
  name prev immediate thread)

Forthのもう一つの構成要素は、その辞書の概念です。Forth辞書は、Lisp関数に似たForth単語の単方向リンクリストです2。単語はLispの構造体で表されます。構造体は、通常ベクトルとして実装される効率的なスロットベースのデータ構造です。nameスロットは、辞書で単語をルックアップするために使用されるシンボル用です。Forth辞書はアルファベット順ではなく、時系列順に格納されていることに注意してください。新しい単語を追加する際に、辞書の末尾に追加するため、辞書をたどると、最新の定義済み単語が最初に検査されます。私たちの辞書の最後の要素は、常に抽象レジスタdictに格納されています。辞書をたどるには、dictから始めて、単語構造体のprevポインタをたどります。これは、以前に定義された単語を指すか、最後の単語の場合はnilを指します3。

FORTH-LOOKUP

(defun forth-lookup (w last)
  (if last
    (if (eql (forth-word-name last) w)
      last
      (forth-lookup
        w (forth-word-prev last)))))

ルックアップする単語wと検索する辞書lastが与えられると、forth-lookupは、単語wが辞書で見つかったかどうかに応じて、Forth単語構造体またはnilを返します。比較関数eqlは、Lispとは異なり、Forthでは単語を数値やその他の非シンボルで名前付けできるため、eqの代わりにeqlが使用されます。

私たちのForth単語のimmediateスロットは、単語が即時であるかどうかのフラグです。即時性は、すぐに詳しく調べるForthメタプログラミングの概念です。今のところ、そのLispの対応物への大まかなアナロジーを以下に示します。即時単語は、Lispマクロのように、実行時ではなくコンパイル時に実行されるForth関数です。何? Lispだけがマクロを持つことになっている。COMMON LISPのマクロシステムは、最高のForth実装を含む他のどのマクロシステムよりもはるかに強力であることは事実ですが、Forthはほとんどすべての言語を凌駕する拡張機能を持っています。Lispと同様に、この機能は設計哲学の結果です。言語実装者にとって十分であれば、アプリケーションプログラマーにとっても十分です。Lispと同様に、Forthはプリミティブという概念を実際には認識しません。代わりに、あなたが望む言語を構築するために組み合わせることができるメタプリミティブのセットを提供します。Lispと同様に、ほとんどのBlub言語とは異なり、マクロを使用した新しい方法での言語拡張は可能であるだけでなく、奨励されています。Lispと同様に、Forthはスタイルではなく、パワーに関するものです。

コンススレッドコード

前のセクションでは、抽象レジスタに焦点を当てました。これらのレジスタは重要な焦点であり、Forthの哲学がそれらを非常に基本的と見なす理由でもありますが、これらのレジスタは実際にはより一般的な概念、つまり抽象マシンのコンポーネントにすぎません。おそらく、異なるForthシステムの最も顕著な特性は、それらのスレッドコードの実装です。Forthがスレッドコードと言うとき、それは先行スケジューリングされた共有メモリプロセス4の従来の意味とは大きく異なります。Forthスレッドは並行性とは無関係です。それらはコードコンパイルとメタプログラミングについて話すためのフレームワークです。

Lispは、プログラムがメモリにアセンブルされる前にコンパイルされるシンボルのツリーデータ構造5へのアクセスを提供しますが、Forthはシンボル操作を提供しません。代わりに、Forthはコードをメモリにアセンブルする、つまりスレッド化するプロセスへのアクセスを提供します。外部からは、Forthの最も明白な機能はそのスタックと後置記法ですが、ForthをForthたらしめているのは実際にはスレッドです。Forthは、Lispがリストについてであるのと同じように、スタックについてです。それらは、メタプログラミングの問題を解決するために使用するのに最も適したデータ構造であるにすぎません。これは、ForthとLispの両方が実際に行っていることです。

古典的なスレッドスタイルは間接スレッドコードとして知られていますが、ほとんどの最新のForthは直接スレッドコードで実装されています。違いは間接レベルを含みます。この間接レベルの低レベルの効率への影響は、基盤となるプロセッサに依存するため、ここでは詳細には触れません。Forthスレッドに関する多くの優れたチュートリアルがあります[STARTING-FORTH][MOVING-FORTH]。メモリ内では、これらのスレッドスタイルは両方とも隣接するセルで構成されています。セルは、ポインタを表すフィクスナムマシンワードです。内部インタプリタと呼ばれるタイトなマシンコードの小さな断片は、プロセッサごとに調整されていることがよくあります。なぜなら、その重要なジョブは、これらのForthスレッドのポインタをたどり、それらが進むにつれてそれらの意味を解釈することだからです。セルに遭遇した場合のデフォルトの動作は、現在のプログラムカウンタ位置をリターンスタックにプッシュし、次にセルに含まれているものをプログラムカウンタにポイントすることです。内部インタプリタがスレッドの終わりに達すると、リターンスタックからポップして、中断した場所から実行を再開します6。

想像できるように、この種のプログラムストレージは非常に小さなプログラムを作成します。コンパイルされたForth単語は、フィクスナムの連続した配列にすぎず、そのほとんどは他の単語へのポインタを表します。これは常にForthの利点の1つでした。プログラムがメモリにスレッド化される際の透過性により、Forthは多くのプログラミングのトレードオフを細かく制御できます。これには、最も重要なものの一つである、実行速度とプログラムサイズのトレードオフが含まれます。スレッドコードにより、抽象化を問題にできるだけ近づけて最適化できるため、非常に高速で小さなプログラムが作成されます。しかし、Lispマクロが効率以上のものに関するものであるのと同様に、Forthスレッドもそうです。Lispプログラマーと同様に、Forthプログラマーは自分自身を単なるユーザーではなく実装者と見なす傾向があります。ForthとLispは両方とも制御に関するものです。自分でルールを作るのです。

Forthのスレッド化技術には、少なくとも他に2つの一般的なタイプがあります。トークンスレッドコードとサブルーチンスレッドコードです。これらは、速度対サイズのトレードオフを考慮する際の反対方向を表します。これらのスレッド化技術は、同じForthで間接スレッドコードや直接スレッドコードと共存することがあります。トークンスレッド化は、スレッド内の単語を表すためにポインタよりもさらに小さいフィクスナムを使用することで、もう1つの間接レベルを追加します。スペクトルの反対側はサブルーチンスレッド化です。このタイプのスレッドコードは人気があり、最高の最新Forthコンパイラは部分的にサブルーチンスレッド化を使用しています。内部インタプリタがたどる単語への連続したポインタの代わりに、サブルーチンスレッドコードはこれらのポインタを呼び出すインラインマシン命令を格納します。サブルーチンスレッドコードでは、内部インタプリタは消えます。それは実際にはハードウェア(または仮想マシン)によって実装されます。サブルーチンスレッドコードは通常、不透明なブロックと見なされ、特別な非プログラマブルコンパイラのみが操作できます。特にコードにさまざまな最適化が適用されると、これらの不透明なブロックは均一なセルベースのスレッドとは似ても似つかないものになります。ほとんどすべての非Forthコンパイラはサブルーチンスレッドコードのみをコンパイルし、あなたが他に何かをしたいと思うとは想像もしないため、この奇妙な定義につながります。

Flubとは、サブルーチンスレッドコードのみを考慮する言語、またはサブルーチンスレッドコードのみを提供する言語実装のことです。

たとえば、Cはサブルーチンスレッドコードのみを提供するか、サブルーチンスレッドコードのみを提供するプログラマーに機能を提供するFlubです。確かに、このプログラムで間接スレッドコードを処理する内部インタプリタをCで実装し、このプログラムでスタックベース言語をブートストラップすることはできますが、その場合はもはやCでプログラミングしているわけではありません。ほとんどすべてのBlub言語はFlubです。抽象マシンとしてのForthは、前述のようにFlubではありません。後で見るように、Forthはプログラマー/実装者にプログラムのコンパイル方法を細かく制御できるようにします。

LispはFlubですか? 興味深いことに、Lispはおそらく最初の非Flubプログラミング言語でしたが、ほとんどFlubになりました。標準で厳密に要求されているわけではありませんが、ほとんどのCOMMON LISPコンパイラは、関数を不透明なマシンコードのブロックにのみコンパイルするため、Flubです。しかし、Lispの非常に初期のバージョンでは、関数はリストとして格納されていました。これは、Forthスレッドと完全に似ていない奇妙なコードスレッド化の一種です。これにより、循環コードに意味を与えるなど、非常に巧妙な実行時トリックが可能になりましたが、それは絶望的に非効率的でした。Forthの多くのスレッドタイプ(ほとんどすべてのアーキテクチャで効率的に実装されています)とは異なり、Lisp関数のこの内部表現は許容できず、Lispは(非常に)効率的なコードを可能にするように変更されました。メタプログラマーにとっては、結果としてほとんどのCOMMON LISP実装がFlubになります。

しかし、言語に追加することが不可能である機能と、マクロで追加できる機能の間には違いがあります。マクロを使用すると、言語を好きなように拡張でき、それはLispのままです。COMMON LISPは、継続やファーストクラスマクロを欠いているのと同じ意味でスレッドコードを欠いています。それらは言語から意図的に省略され、必要に応じてマクロライターが実装できるように残されています。この章とそのコードの最も重要な結果の1つは、それらがFlubであっても、Lisp言語はマクロを通じて非Flub言語に変形できることを示すことです。非Blubは非Flubを意味します。つまり、言語を非Flubに変えることができない場合、それはBlubでなければなりません。ただし、逆は真ではありません。Forthのような非Flub言語はBlubのままであり、それらを非Blubに変える最も簡単な方法は、それらでLisp環境を実装することです。そして、それはLispでプログラミングしていることになります。

FORTH-INNER-INTERPRETER

(defmacro forth-inner-interpreter ()
  `(loop
     do (cond
          ((functionp (car pc))
             (funcall (car pc)))
          ((consp (car pc))
             (push (cdr pc) rstack)
             (setf pc (car pc)))
          ((null pc)
             (setf pc (pop rstack)))
          (t
             (push (car pc) pstack)
             (setf pc (cdr pc))))
     until (and (null pc) (null rstack))))

間接/直接スレッドコードのようにスレッドを表すために連続したメモリセルを使用する代わりに、私たちのForthはLispの動的型付けとコンスセルリスト構造を活用します。これをコンススレッドコードと呼びます。マクロforth-inner-interpreterは、これらのコンスセルリンクリストスレッドをたどることができるコードに展開されます。まだ未知の式に展開されるように設計されたマクロで、Forth環境のロジックのプログラミングを開始するのは奇妙に思えるかもしれませんが、これは実際には望ましいLispプログラミングパターンです。マクロはどこからでもプログラミングを開始できるため、なぜ最も興味深く、プログラムを推進するビットから始めないのでしょうか? これらは、プログラムの最終的な設計に最も影響を与えるビットです。

forth-inner-interpreterの定義自体は、コンススレッドコードの意味の簡潔な定義です。各コンスセルのcarは、関数、別のコンスセル、またはその他のLispアトムのいずれかを指します。関数は遭遇すると実行されます。関数自体がpcレジスタを更新するのは、関数に任されていることに注意してください。スレッド内で別のコンスセルが見つかった場合、それはサブルーチン呼び出し、つまり単語の呼び出しを示していると想定されます。私たちの内部インタプリタは、リターンスタックにpc再開位置をプッシュしてから、この新しいスレッドにジャンプします。他のLispアトムが遭遇した場合、それは単にパラメータスタックにプッシュされ、スレッドの次のセルから実行が再開されます。内部インタプリタは、スレッドの終わりに達し、リターンスタックに他のスレッドがない場合、戻ります。

PRIM-FORMS

;; Prim-form: (name immediate . forms)
(defvar forth-prim-forms nil)

(defmacro def-forth-naked-prim (&rest code)
  `(push ',code forth-prim-forms))

(defmacro def-forth-prim (&rest code)
  `(def-forth-naked-prim
     ,@code
     (setf pc (cdr pc))))

def-forth-naked-primで定義されたプリミティブは、pc変数を自動的に更新しません。代わりに、それらは自分で更新する必要があります。def-forth-primは、def-forth-naked-primと同様ですが、コードの最後にpcを更新するコードを追加します。これらのマクロは、最初の引数としてプリミティブを参照するために使用されるシンボル、2番目の引数としてプリミティブが即時であるかどうかを示すブール値、および残りの引数としてプリミティブが実行されるときに評価されるLispフォームを期待します。

BASIC-PRIM-FORMS

(def-forth-prim nop nil)

(def-forth-prim * nil
  (push (* (pop pstack) (pop pstack))
        pstack))

(def-forth-prim drop nil
  (pop pstack))

(def-forth-prim dup nil
  (push (car pstack) pstack))

(def-forth-prim swap nil
  (rotatef (car pstack) (cadr pstack)))

(def-forth-prim print nil
  (print (pop pstack)))

(def-forth-prim >r nil
  (push (pop pstack) rstack))

(def-forth-prim r> nil
  (push (pop rstack) pstack))

8つの単純なプリミティブ(即時またはネイキッドではない)が提示されます。nopは何も行わないダミー命令(「no operation」)です。**


プリミティブは乗算演算子です。スタックから上位2つの値を取り出し、それらを乗算してから、結果をスタックに戻します。dupは「duplicate」の略で、パラメータスタックの最上位の値を再度パラメータスタックにプッシュし、2つの重複した値が残ります。swapは、非常に便利なCOMMON LISPマクロであるrotatefを使用して、上位2つのパラメータスタック要素を交換します。Forthにも(スタックベースの)回転メカニズムがあるのは偶然ではありません。printはパラメータスタックをポップして表示します。


>rは値をパラメータスタックからリターンスタックに転送し、r>はその逆を行います。

**


という名前は、セクション3.5、意図しないキャプチャの、変数が特殊かどうかについて考えを変えた場合にアスタリスクを追加または削除する必要があるという重要な変数キャプチャルールに違反しますか? いいえ、このシンボルを関数にバインドするために実際には使用していないためです。それは単にforth-prim-formsのリストの最初の要素にすぎません。私たちは何も間違ったことはしていません。シンボルは、それらが示される関数やマクロとは独立しています。重要な変数キャプチャルールに違反しない限り、任意のシンボルをどこでも使用できます。これはLispを書くときにのみ関係します。私たちはForthを書いています。

構文の二重性、定義

この本から何も覚えていない場合でも、このセクションのメッセージを覚えておいてください。ここで、私たちはこれまで触れてきた概念、つまり構文の二重性を最終的に定義し、説明します。このセクションでは、少なくとも最初の3つの章、第6章、アナフォリックマクロ、および前のForthセクションを読んでいることを前提としています。

ほとんどのLispプログラマーにとって、LispでのプログラミングがBlubでのプログラミングよりも生産的で、最終的にはより自然であるという事実は経験的に明白ですが、その理由を説明するのははるかに困難です。Lispがその驚異的な表現力をマクロから得ていることは事実ですが(そして私たちはこの本や他の場所で多くの興味深いマクロを見てきました)、これまでのすべての説明は満足のいくものではありません。マクロの本当の利点は何ですか? 部分的な説明には、簡潔さ、つまりプログラムを短くすることが確かに含まれます。その定義は次のとおりです。

プログラミング言語L、そのプログラミング言語の機能F、およびLの任意のプログラムAとする。Fが簡潔さ機能を提供するのは、AがFのないLのバージョンよりも短い場合である。

簡潔さ機能は、簡潔さの理論の基礎と根拠を提供します。

プログラムを構築するために必要な労力は、使用するプログラミング言語で利用可能な簡潔さ機能の量に反比例する。

簡潔さの理論は、プログラミング抽象化によってプログラムの表現が非常に短く簡潔になる場合、書くコードが少なくなるため、それらを書きやすくなるという考えに基づいています。CL-PPCRE読み取りマクロは、簡潔さ機能の例です。それらは、かなり長いCL-PPCRE関数名を簡潔なPerlスタイルの式に短縮し、使用するたびにキーストロークを節約します。簡潔さの理論は、開始時にどこに行きたいかがわかっている小さなプログラムを書くのに非常に適しています9。残念ながら、ほとんどのプログラムはそのようではありません。ほとんどのプログラム、少なくとも興味深いプログラムは、各ステップでのフィードバックを考慮した一連のインタラクティブな書き込み-テストサイクルの反復的に作成されます。抽象化は簡潔かもしれませんが、それらを異なる(おそらく同様に簡潔な)抽象化に常に変更する必要がある場合、ほとんど労力を節約できないでしょう。最終的なプログラムの長さではなく、そこに至るまでのプロセスの長さを考慮すべきかもしれません。

どの言語でも、プログラムは開始時とは異なるものになります。ほとんどのプログラムは、著者が問題についてさらに学ぶにつれて詳細が埋められていく単純なスケッチから始まります。簡潔さと二重性に戻る前に、この章では、議論を動機付ける単純なプログラムの開発を段階的に説明します。それは私たちのForth環境です。

さて、どこまで話しましたか? ああ、抽象レジスタ、抽象マシン、スレッドコードについてたくさん話しましたが、forth-lookupと呼ばれる単語ルックアップユーティリティ、私たちのコンススレッドコードの内部インタプリタ、そして私たちのForthシステム内のプリミティブのリストを表すリストを収集するシステムも定義しました。しかし、Lisp上のForthはどうなるでしょうか? さて、振る舞いと状態を混合するあらゆる抽象化の最も自然な形式は何でしょうか? クローザ、もちろん。私たちの古い友人、letとlambdaです。このアイデアをハッキングすると、次のマクロが得られるかもしれません。

(defmacro new-forth ()
  `(let ,forth-registers
     (forth-install-prims)
     (lambda (v)
       (let ((word (forth-lookup v dict))) 
         (if word
           (forth-handle-found)
           (forth-handle-not-found))))))

Forthの抽象レジスタのリスト、forth-registersは展開に直接スプライスされ、最初にすべての抽象レジスタをnilにバインドします。このマクロには、機能の穴がたくさん残っていることに注意してください。プリミティブフォームをインストールするマクロforth-install-prims、およびマクロforth-handle-foundとforth-handle-not-foundを定義する必要があることがわかりました。しかし、このスケッチから学ぶ最も重要なことは、はい、このクローザ設計は機能する可能性があるということです。デフォルトのLisp設計に従うことで得られたアイデアは、Forthが単語ごとに呼び出されるクローザであることを含みます。私たちのスケッチは、次のユースケースの実装の概要を示しています。ここで、新しいForth環境を作成することを想像します。

(defvar my-forth (new-forth))

ここに、数値3を二乗して結果を表示するForthコードがあります。

3 dup * print

これをForth環境で次のように実行できます。

(progn
  (funcall my-forth 3)
  (funcall my-forth 'dup)
  (funcall my-forth '*)
  (funcall my-forth 'print))

GO-FORTH

(defmacro! go-forth (o!forth &rest words)
  `(dolist (w ',words)
     (funcall ,g!forth w)))

これは使用するには不格好なインターフェースですが、Lispをプログラミングしているので、これらの詳細を隠すマクロを常に作成できることを知っています。そして、それがまさにgo-forthマクロで行われることです。go-forthは、defmacro!の自動的な一度だけ実行される機能を使用していることに注意してください。なぜなら、go-forthに提供される最初の引数はdolistで定義されたループ内にあり、ユーザーが意図するよりも正確に一度評価されない可能性があるからです。go-forthを使用すると、ForthコードをForth環境に供給することがはるかにクリーンになります。

(go-forth my-forth
  3 dup * print)

この時点で、新しいForth環境を作成する際に、最終的にForthのブートストラップコードを実行したいと考えるかもしれません。そのため、作成時にクローザを呼び出すことができる必要があります。これには、プログラムのlet over lambda設計を変更するか、new-forthマクロの周りにラッパー関数を作成して、標準ライブラリをロードし、結果のForthを返す必要があるかもしれません。

FORTH-STDLIB

(defvar forth-stdlib nil)

(defmacro forth-stdlib-add (&rest all)
  `(setf forth-stdlib
         (nconc forth-stdlib
                ',all)))

Forthコードはシンボルやその他のアトムのリストにすぎないため、数個のプリミティブを除いて、必要なすべてのブートストラップを提供する標準ライブラリはリストに格納できます。forth-stdlib変数は、新しいForthが作成されるときに実行されるForthコードのリストを保持し、forth-stdlib-addマクロは、新しいForthコードをforth-stdlibリストに連結するLispコードに展開されます。

新しいForth環境の作成をサポートするためにnew-forthを適応させる最も簡単な方法は? セクション6.3、Aletと有限状態マシンで作成したaletマクロを覚えていますか? このマクロの目的は、COMMON LISPのletとの構文の二重性を作成しながら、アナフォリック変数thisを提供されたコードの周りにバインドすることでした。thisは、aletから返される結果、つまりForthクローザを参照します。

したがって、スケッチを変更するのは予想以上に簡単です。スケッチの最初のletシンボルをaletに変更し、標準環境をthis(Forthクローザ)にロードするコードを追加するだけです。aletの構文は意図的にletの構文に合わせられていたため、何も再配置する必要はありませんでした。次のイテレーションは次のようになります。

(defmacro new-forth ()
  `(alet ,forth-registers
     (forth-install-prims)
     (dolist (v forth-stdlib)
       (funcall this v))
     (lambda (v)
       (let ((word (forth-lookup v dict))) 
         (if word
           (forth-handle-found)
           (forth-handle-not-found))))))

aletはクローザを使用して間接レイヤーを導入するため、Forth環境の効率がわずかに低下することに注意してください。しかし、この効率の負担が大きすぎるかどうかはわかりませんが、この間接が必要になるかどうかさえわかりません。間接を排除するには、aletの直前に定義されたalet%マクロを使用します。

おそらく今、あるいは後でForth環境の構築とデバッグを試みているときに、Forthの抽象レジスタにForth環境の外からアクセスできると便利だと考えるかもしれません。残念ながら、これらの変数はlet over lambdaでクローズされています。それらをアクセス可能にするために、プログラムを再度変更する必要があります。もちろん、これには多くの方法があります。Forth環境に複数のクローザを埋め込んで返すこともできます。そのうちのいくつかは抽象レジスタを保存およびアクセスできます。あるいは、let over lambda戦略全体を再検討することもできます。しかし、それを行う前に、助けになる二重性はありますか? セクション6.7、Pandoricマクロのplambdaを覚えていますか? その目的は、lambdaとの構文の二重性を作成することでしたが、それは実際には外部に開かれたクローザを作成します。このサポートのためにスケッチを変更することは、返されるlambdaにp文字をプレフィックスとして付け、エクスポートしたい変数のリストを追加するだけです。私たちのリストはforth-registersで便利に利用できます11。私たちのスケッチは次のようになります。

(defmacro new-forth ()
  `(alet ,forth-registers
     (forth-install-prims)
     (dolist (v forth-stdlib)
       (funcall this v))
     (plambda (v) ,forth-registers
        (let ((word (forth-lookup v dict))) 
          (if word
            (forth-handle-found)
            (forth-handle-not-found))))))

Forthクローザが開かれた状態で、次のユースケースが利用可能になります。これは、Forthスタックに5つの項目をプッシュします。

* (go-forth my-forth
    1 2.0 "three" 'four '(f i v e))

NIL

そして、パラメータスタックを検査するために、my-forthをpandorically開くことができます。

* (with-pandoric (pstack) my-forth
    pstack)

((F I V E) FOUR "three" 2.0 1)

NEW-FORTH

(defmacro new-forth ()
  `(alet ,forth-registers
     (setq dtable (make-hash-table))
     (forth-install-prims)
     (dolist (v forth-stdlib)
       (funcall this v))
     (plambda (v) ,forth-registers
       (let ((word (forth-lookup v dict))) 
         (if word
           (forth-handle-found)
           (forth-handle-not-found))))))

これが、マクロnew-forthの最終バージョンに到達するために実行されたプロセスです。最終定義は最後のスケッチと同一ですが、dtable抽象レジスタをハッシュテーブル(すぐに説明します)にポイントするように設定している点も異なります。

プログラミング、少なくとも興味深い種類は、プログラムを書くことではなく、それを変更することです。生産性の観点から、簡潔さはそれほど遠くまでしか行きません。lambdaをfnのようにリネームすることもできますが、この簡潔さ機能は、数回のキーストロークを除いてほとんど節約しません12。しかし、労力を節約するのは、コード自体を変更することなくコードの意味を変更するために使用できる、lambdaに似た多くの抽象化があることです。構文の二重性は労力を節約します。

特別な変数名にイヤーマフを付けると、変数が特殊かレキシカルかについて考えを変えた場合にアスタリスクを追加または削除する必要があることで問題が発生する可能性があるのと同様に、不必要に構文を分離し、二重性を避けることは、プログラミング中に多くの無駄な労力を引き起こす可能性があります。別の例:lambdaフォームをシャープ引用符で囲むのは悪い考えです。なぜなら、関数が実際にはalambdaを必要とすると判断した場合や、リストの関数位置でlambdaフォームを使用すると決定した場合に、変更する必要があるものがさらに増えるからです。汎用変数も非常に重要な二重性を提供します。マクロを書くとき、同じフォームが変数へのアクセスと変更の両方の展開にスプライスされる可能性があります。空リストと偽ブール値に対するCOMMON LISPの二重の意味は、さらに別の例です。これらの2つが二重性以外に同じであるべき本当の理由はありません。二重性は、本書が他のCLOS機能14(defclassやdefmethodなど)ではなくクローザを推進してきた理由でもあります。クローザを使用するプログラムを変更する方が、クラスやオブジェクトを使用するプログラムを変更するよりも、通常摩擦が少なくなります。なぜなら、クローザの構文には多くの優れた二重性があり、クローザを構築するマクロのプログラミングはより均一だからです15。これらおよびその他の例を念頭に置いて、構文の二重性とは何かを明確に定義できます。

プログラミング言語L、そのプログラミング言語の機能F、およびLの任意のプログラムAおよびBとする。Fが構文の二重性機能を提供するのは、AをBに変更するために必要な変更が、FのないLのバージョンよりも少ない場合である。

これにより二重性の理論が得られます。

プログラムを構築するために必要な労力は、プログラミング言語で利用可能な二重構文の量に反比例する。

構文の二重性の概念とその利点のインパクトは両方とも非常に明確ですが、優れた二重性を実際に設計する方法ははるかに不明確です。特定の言語で最も役立つ二重性はどれですか? 特定の問題に対して、2つの異なる言語のどちらがより優れた構文の二重性を提供するかわかる方法は?

Lispではプログラミング言語を完全に制御できるため、望むだけまたは少なく二重構文を持つように言語を設計できます。この考え方に従うことは、私の意見では、今日のプログラミング言語研究で最も生産的な分野です。Lispマクロを使用して、さまざまなプログラムを互いにどれだけ似せることができるでしょうか。これにより、それらを新しいプログラムに変更することがより容易になります16。

簡潔さと二重性の両方の定義において、機能Fが効果的であるかどうかは、書かれている、または変更されているプログラムに依存します。場合によっては、簡潔さや二重性を提供する機能が、実際には必要な労力を増加させることがあります。最善のアプローチは、可能な限り多くの有用な簡潔さと二重性機能を提供し、最終的に手間がかかるものを削除することかもしれません。

Going Forth

このセクションでは、前のセクションのnew-forthマクロに残された穴を埋めることで、Forthを実際に進めます。Forthのスレッドメカニズムが機能することを確認した後、Forthプログラミング環境をブートストラップし、その過程でForthの即時性とは何か、そしてそれがLispマクロとどのように関連するかを説明します。

FORTH-INSTALL-PRIMS

;; Prim-form: (name immediate . forms)
(defmacro forth-install-prims ()
  `(progn
     ,@(mapcar
         #`(let ((thread (lambda () 
                           ,@(cddr a1))))
             (setf dict
                   (make-forth-word
                      :name ',(car a1)
                      :prev dict
                      :immediate ,(cadr a1)
                      :thread thread))
             (setf (gethash thread dtable)
                   ',(cddr a1)))
         forth-prim-forms)))

new-forthの定義では、新しいForthインスタンスが作成されるときにプリミティブをコンパイルしてインストールするマクロであるforth-install-primsでマクロの穴を残しました。名前付き抽象化を使用したいが、レキシカル環境を捨てたくないため、マクロである必要があります。このマクロのポイントは、新しいForthインスタンスが作成されるときにプリミティブをコンパイルしてインストールすることです。Forth-install-primsは、プリミティブ単語をdictリンクリストに追加し、提供されたコードをlambdaでラップし、単語のnameとimmediateスロットを設定する各サブフォームを持つprognフォームに展開されます。さらに、各単語のためにlambdaによって作成された関数、threadと呼ばれるものは、dtableハッシュテーブルに追加されます(すぐに説明します)。これらのすべての関数は、元のnew-forthマクロのスコープで作成されるため、抽象レジスタを指定したForth環境に完全にアクセスできます。threadバインディングがユーザー提供コードのthreadをキャプチャしないため、gensymで名前を付ける必要がないことに注意してください。

ForthはLispのメタプログラミングシステムに似ており、このシステムは即時性と呼ばれる概念に基づいています。従来のForthでは、stateという変数があり、ゼロまたは非ゼロです。ゼロの場合、Forthは通常の解釈(実行)状態にあると見なされます。この状態で単語をForthに与えると、その単語はルックアップされて実行されます。しかし、base変数が非ゼロの場合、Forthはコンパイル状態にあると言われます。この状態で単語をForthに提示すると、提示された単語のアドレスが、コンパイル中の現在のスレッド、通常は辞書で最も最近作成された単語に追加されます。ただし、1つの例外があります。これが即時性に関する重要な点です。コンパイル状態にあり、即時単語が与えられた場合、その単語はコンパイルされるのではなく実行されます。したがって、Lispと同様に、Forthはコンパイル時に任意のForthコードを実行できます。

FORTH-PRIMS-COMPILATION-CONTROL

(def-forth-prim [ t ; <- t means immediate
  (setf compiling nil))

(def-forth-prim ] nil ; <- not immediate
  (setf compiling t))

ForthをLisp上の抽象マシンとして構築しているため、フィクスナム値を真偽に任意にマッピングするという任意のマッピングに苦しむ必要はありません。Lispでは、すべての値の真偽への任意の任意のマッピングを楽しむことができる動的型システムがあります。Forth変数stateの代わりに、私たちのForthシステムは、コンパイル状態をLispの汎用ブール値として格納するためにcompiling抽象レジスタを使用します。コンパイル状態を制御するために使用される従来のForth単語は、[と]です。(開き角括弧)はコンパイルモードから抜け出し、したがって即時単語である必要があります。](閉じ角括弧)*はコンパイルモードに戻り、解釈モードのときにのみ実行され、即時である必要はありません。これらのシンボルの選択は、現時点では奇妙に思えるかもしれませんが、高レベルのForthコードではより明確になります。これらの角括弧は、Forthスレッドのコンパイル中に実行されるコードブロックを指定することを可能にします。ある意味で、これらの括弧はLispのバッククォートとアンクォート演算子に似ています。これらの単語は通常Forthコードで次のように使用されます。

... compiled words ...
[ interpret these words ]
... more compiled words ...

Forthのほとんどと同様に、これらの単語は透過的に指定されているため、異常な方法で使用できます。たとえば、これらの単語はLispの括弧のようにバランスが取れていません。選択した場合、逆方向に使用することもできます。

... interpret these words ...
] compile these words [
... more interpreted words ...

ネストの外観さえありますが、これは実際にはネストではありません。なぜなら、単一のブール状態しかないからです。コンパイル中またはコンパイル中でない。

... compiled words ...
[ interpret these words
  ] compile these words [
  interpret these words
]
... more compiled words ...

FORTH-COMPILE-IN

(defmacro forth-compile-in (v)
  `(setf (forth-word-thread dict)
         (nconc (forth-word-thread dict)
                (list ,v))))

私たちのForthは、forth-compile-inマクロを略語マクロとして使用します。このマクロは、Forth単語を現在のスレッド、つまり最後に作成された単語のスレッドにコンパイルします。私たちのスレッドはコンスセルで表されるため、Lisp関数nconcを使用して、宛先単語のスレッドへのポインタを現在のスレッドに単純に追加できます。

FORTH-HANDLE-FOUND

(defmacro forth-handle-found ()
  `(if (and compiling
            (not (forth-word-immediate word)))
     (forth-compile-in (forth-word-thread word))
     (progn
       (setf pc (list (forth-word-thread word)))
       (forth-inner-interpreter))))

new-forthマクロに残したもう一つの穴は、Forthが提供された単語を辞書で見つけることができた場合にどうすべきかということです。この穴はマクロforth-handle-foundによって埋められます。このマクロは、前述のようにForthの即時性を実装します。コンパイル中で、かつ単語が即時でない場合、それを現在のスレッドにコンパイルします。それ以外の場合は、プログラムカウンタpcをルックアップされた単語のスレッドにポイントするように設定し、内部インタプリタを実行して単語を実行します。このマクロは、wordがルックアップされたForth単語にバインドされているレキシカル環境に展開されることを思い出してください。

FORTH-HANDLE-NOT-FOUND

(defmacro forth-handle-not-found ()
  `(cond
     ((and (consp v) (eq (car v) 'quote))
        (if compiling
          (forth-compile-in (cadr v))
          (push (cadr v) pstack)))
     ((and (consp v) (eq (car v) 'postpone))
        (let ((word (forth-lookup (cadr v) dict))) 
          (if (not word)
            (error "Postpone failed: ~a" (cadr v)))
          (forth-compile-in (forth-word-thread word))))
     ((symbolp v)
        (error "Word ~a not found" v))
     (t
        (if compiling
          (forth-compile-in v)
          (push v pstack)))))

new-forthの最後の穴は、Forthが単語を辞書で見つけられなかった場合にどうすべきかということです。Forth-handle-not-foundはこの穴を埋め、いくつかの特別なケースを実装します。forth-handle-not-foundは、vというバインディングを参照するレキシカル環境に展開され、Forthに渡された値に対応することに注意してください。また、このコードが呼び出された場合、vは辞書のどの単語も参照しないことを知っています。vがシンボルである場合、forth-handle-not-foundはエラーをスローします。値がシンボルでない場合、動作はvをパラメータスタックにプッシュするか、コンパイル中の場合は現在のスレッドにコンパイルすることです。ただし、2つの特別なケースがチェックされます。vが最初の要素quoteを持つリストの場合、引用された値をパラメータスタックにプッシュします。これは、シンボルを単語として解釈されることなくパラメータスタックにプッシュできるようにするためです。2番目の特別なケースは、vが最初の要素postponeを持つリストの場合です。postponeはANSI Forthの単語で、いくつかの従来のForth単語を統合し、明確にします。postponeは、即時単語であっても、常に単語をコンパイルするために使用されます。したがって、コンパイルモードの場合、遅延された即時単語は、即時であっても現在のスレッドにコンパイルされます。以下は、(開き角括弧)単語を遅延させる例です。

... compiling ...
(postpone [)
... still compiling ...

new-forthマクロのすべての穴が埋まったので、new-forthマクロを使用して新しいForthインスタンスを作成できます。以前にdefvarでmy-forthという特別な変数を作成しました。そうでなかったとしても、トップレベルのsetqで値を割り当てるのと同時に、それを特殊として暗黙的に宣言できます17。

* (setq my-forth (new-forth))

#<Interpreted Function>

go-forthマクロを使用してForthを使用できるようになりました。

* (go-forth my-forth
    2 3 * print)

6
NIL

しかし、これまでのところ、dup、**


、print**という単語しか定義していません。有用なことをするには、さらに多くのプリミティブが必要です。Lispと同様に、本番品質のForth実装には、プログラマーの利便性のために多数の単語が定義されています。何十年もの使用を通じて、多くの一般的なプログラミングパターンが特定され、単語に抽象化され、一般的なForthの語彙に導入されました。Lispと同様に、言語の一部として定義された言語を拡張できる能力は、多くの貴重な実験につながりました。この哲学とプロセスを調査しているため、経験豊富なForthプログラマーが依存する多くのForth単語を定義しません。代わりに、Lispマクロと比較できるように、Forthのメタプログラミングシステムを説明するために必要な最小限のプリミティブセットを目指します。

FORTH-PRIMS-DEFINING-WORDS

(def-forth-prim create nil
  (setf dict (make-forth-word :prev dict)))

(def-forth-prim name nil
  (setf (forth-word-name dict) (pop pstack)))

(def-forth-prim immediate nil
  (setf (forth-word-immediate dict) t))

3つのプリミティブがさらに定義されています。いずれも即時またはネイキッドではありません。create、name、immediateです。create単語は、名前のない単語を辞書に追加します。nameはパラメータスタックから値を取り出し、辞書の最後の単語の名前をその値に設定します。immediateは、定義された最後の単語を即時単語に設定するだけです。デフォルトでは、単語は即時ではありません。

go-forthマクロを使用してmy-forth Forth環境でコードを実行できることを思い出してください。ここで、数値3を二乗して表示します。

* (go-forth my-forth
    3 dup * print)

9

定義単語はまだ持っていませんが、スレッドコードの透過的な指定のおかげで、Forth単語自体を使ってForthをブートストラップし始めることができます。たとえば、ここでcreateを使用して、新しい空の単語を辞書に追加します。

* (go-forth my-forth
    create)

NIL

次に、(開き角括弧)を使用してコンパイルを開始し、dupと**


**単語をスレッドに追加してから、(開き角括弧)を使用してコンパイルモードを終了します。

* (go-forth my-forth
    ] dup * [)

NIL

これで、辞書に新しい単語ができました。それは完全なForthスレッドを持っており、内部インタプリタによって実行されると、スタックの最上位の数値を二乗します。しかし、この単語は、それにアクセスする方法がない限り、あまり有用ではありません。name単語を使用して名前を付けることができます。割り当てる名前は、新しいスレッドにアクセスするために使用するキーになります。

* (go-forth my-forth
    'square name)

NIL

Forthに渡した最初の値が引用されていることに注意してください。シンボルsquareをパラメータスタックにプッシュするという動作を決定したことを思い出してください。このシンボルは、次にname単語によって消費されます。単語に名前が付いたので、squareシンボルを使用して他の単語と同じように評価できます。

* (go-forth my-forth
    3 square print)

9
NIL

したがって、新しい単語を作成するための一般的な手法は次のパターンです。

create
] ... compiled words ... [ 
'whatever name

FORTH-START-DEFINING

(forth-stdlib-add
  create
    ] create ] [
  '{ name)

しかし、Forthのメタプログラミングを少し利用して、このインターフェースを改善できます。新しいForth単語、{の定義が標準ライブラリに追加されます。そのスレッドは2つのポインタで構成され、最初のポインタは単語createを指し、2番目のポインタは(開き角括弧)を指します。したがって、この単語のスレッドが実行されると、辞書に新しい単語が追加され、コンパイルモードに切り替わります。Forthは通常、この目的のために:単語を使用しますが、これはLispの:の使用と競合するため、単語定義を開始するために{を使用することを選択しました。

FORTH-STOP-DEFINING

(forth-stdlib-add
  { (postpone [) [ 
  '} name immediate)

同様に、補完的な単語}を標準ライブラリに追加します(従来のForth ;を置き換えます)。この単語を定義する理由は実際にはありません。唯一のことは、コンパイル状態から抜け出すことです。すでにそれを行うための単語(開き角括弧)があります。それにもかかわらず、{を定義することは、新しい単語の定義を直感的にするための単語のペア{と}を作成することにより、通常のバランスの取れた括弧18を提供するため、有用です。

これで、これらの新しい標準ライブラリ機能を利用するためにForthを作成できます(以前の単語squareの定義を削除します)。

* (setq my-forth (new-forth))

#<Interpreted Function>

新しい単語{と}を使用したsquareは次のようになります。

* (go-forth my-forth
    { dup * } 'square name)

NIL
* (go-forth my-forth
    5 square print)

25

そして、新しいスレッドは、プリミティブと同じくらい簡単にカスタム作成された単語を参照できます。ここでは、square単語への2つのポインタを持つスレッドとして単語quarticを定義する方法を示します。

* (go-forth my-forth
    { square square } 'quartic name)

NIL

(Expt 1/2 4)は確かに1/16です。

* (go-forth my-forth
    1/2 quartic print)

1/16
NIL

非シンボルはForthスレッドに直接コンパイルされ、内部インタプリタは非関数を遭遇したときにスタックにプッシュするデータアイテムとして扱います。そのため、単語定義に数値を含めることができます。

* (go-forth my-forth
    { 3 } 'three name
    three three * print)

9
NIL

辞書で以前に名前が付けられたかどうかを確認するために、Forthに渡されたすべての要素をルックアップすることを思い出してください。その結果、任意のLispオブジェクトを使用して単語に名前を付けることができます。ここでは、数値19を使用します。

* (go-forth my-forth
    { 4.0 } '4 name
    4 4 * print)

16.0
NIL

MEMORY-PRIMS

(def-forth-prim @ nil
  (push (car (pop pstack))
        pstack))

(def-forth-prim ! nil
  (let ((location (pop pstack)))
    (setf (car location) (pop pstack))))

Forthはポインタスコープの使用方法を学ぶのに優れた言語です。Forthは、メモリから値を読み書きするために使用される2つの単純な演算子、@(フェッチ)と!(ストア)を定義します。私たちのForth単語はメモリワードではなくコンスセルに格納されているため、フェッチでポインタを逆参照することは、ポインタのcarを取得することによって実装されます。セットで設定することは、setfを使用してそのcarを設定することによって実装されます。フェッチはパラメータスタックから値を取り出し、それがコンスセルであると仮定し、そのcarを取得してからスタックにプッシュします。ストアはパラメータスタックから値を取り出し、それがコンスセルであると仮定し、スタックから別の値を取り出し、最初の値のcarに格納します。たとえば、循環リストを作成して表示する方法を次に示します。

* (let ((*print-circle* t))
    (go-forth my-forth
      '(nil) dup dup ! print))

#1=(#1#)
NIL

これで、スレッドコードを使用してForthでプログラミングしています。それとも、そうでしょうか? Lispを離れたことはありますか? 2つの言語の区別は非常に曖昧で、ほとんど識別できません。この章の残りの部分は、Forthのメタプログラミングをさらに説明しながら、この区別をさらに曖昧にすることを目指しています。

Going Forther

FORTH-UNARY-WORD-DEFINER

(defmacro forth-unary-word-definer (&rest words)
  `(progn
     ,@(mapcar
         #`(def-forth-prim ,a1 nil
             (push (,a1 (pop pstack))
                   pstack))
         words)))

COMMON LISPには、Forthスレッドに含めたい多くの関数があります。Forth-unary-word-definerは、マクロ本体に渡された要素の数だけdef-forth-primフォームに展開されます。要素は関数またはマクロを表すシンボルであると想定されますが、ラムダフォームである可能性もあります。ラムダフォームで名前が付けられたプリミティブの唯一の制限は、そのようなプリミティブを呼び出すには、Forth環境に同じ(eq)ラムダフォームを渡す必要があることです。シンボル1つ、notを渡した場合の展開を次に示します。

* (macroexpand
    '(forth-unary-word-definer
       not))

(PROGN
  (DEF-FORTH-PRIM NOT NIL
    (PUSH (NOT (POP PSTACK))
          PSTACK)))
T

1つの引数を受け入れる任意のCOMMON LISP関数を使用でき、forth-unary-word-definerは、Forthパラメータスタックの最上位要素にこの関数を適用するForthプリミティブを定義します。

FORTH-BINARY-WORD-DEFINER

(defmacro! forth-binary-word-definer (&rest words)
  `(progn
     ,@(mapcar
         #`(def-forth-prim ,a1 nil
             (let ((,g!top (pop pstack)))
               (push (,a1 (pop pstack)
                          ,g!top)
                     pstack)))
         words)))

このアイデアの拡張はforth-binary-word-definerです。これは、2つの値を受け入れる演算子についても同様のことを行います。**


や/のような二項関数に最初の引数として2番目に上位の要素を扱うというForthの規則は、パラメータスタックの最上位要素を保持するためのテンポラリletバインディングを作成することによって有効になります。以下は、単語


の展開です。

* (macroexpand
    '(forth-binary-word-definer
       -))

(LET ()
  (PROGN
    (DEF-FORTH-PRIM - NIL
      (LET ((#:TOP1767 (POP PSTACK)))
        (PUSH (- (POP PSTACK)
                   #:TOP1767)
              PSTACK)))))
T

FORTH-AND-LISP-WORDS

(forth-unary-word-definer
  not car cdr cadr caddr cadddr
  oddp evenp)
(forth-binary-word-definer
  eq equal + - / = < > <= >=
  max min and or)

演習:forth-binary-word-definerを使用するとき、マクロのようなandとorをファーストクラスの値として扱うことができるのはなぜですか?

難しい演習:forth-binary-word-definerで意図しない変数キャプチャを回避するためにgensym(g!top)を使用する必要があったのはなぜですか? ヒント:このセクションで既に議論しました。

したがって、これらのマクロは、さまざまなLisp関数をForthプリミティブ環境に追加できるため、Forth内からそれらを使用できます。以下は、単項プリミティブcadrの使用例です。

* (go-forth my-forth
    '(a (b) c) cadr print)

(B)
NIL

および二項演算子<:

* (go-forth my-forth
    2 3 < print)

T
NIL

これまでのところ、私たちのForthスレッドは有向非巡回グラフでした。つまり、それらはどこにも自分自身を指さない(自己参照しない)コンスセル構造で構成されており、最終的にはツリーの葉であるプリミティブで終了します。たとえば、前のセクションでquartic単語を定義したときに作成したスレッドを取得するためにpandoricマクロを使用できます。

* (with-pandoric (dict) my-forth
    (forth-word-thread
      (forth-lookup 'quartic dict)))

((#<Interpreted Function>   ;; square->|->dup
  #<Interpreted Function>)  ;;         |->*
 (#<Interpreted Function>   ;; square->|->dup
  #<Interpreted Function>)) ;;         |->*

上記のコメントは、Lispでフォームを印刷した角度からのみ示しています。コードやコメントからは見えないのは、このスレッド構造が実際に共有されていることです。それを見るには、eqを使用します。

* (eq (car *) (cadr *))

T

または、**


print-circle*が設定されている状態で表示します。

* (let ((*print-circle* t))
    (print **)
    t)

(#1=(#<Interpreted Function>  ;; square->|->dup
     #<Interpreted Function>) ;;         |->*
 #1#)                         ;; ————|
T

スレッドコードは、Forthに驚異的なメモリとサイズの利点をもたらすことができます。完全なForthシステムは、ネットワークドライバから最上位のユーザープログラムまで、このように一緒にスレッド化されたコンパイルコードで構成されています。さらに、quarticからスレッドをきれいに抽出できることに注意してください。余分な他のスレッドを大量に取得することなく。たとえば、言語には+やcadddrのような多くのプリミティブがありますが、それらは上記のどのスレッドにも現れません。これは、特定のForth単語を実行するために必要なスレッド構造のみを抽出するマークスイープガベージコレクションアルゴリズムのようです。Lispでは、このプロセスはツリーシェイキングと呼ばれ、一般的にあまり効果的ではありません。しかし、Forthでは非常に効果的です。

残念ながら、my-forthからpandorically抽出したquarticスレッドは、私たちにとってあまり有用ではありません。それはまだmy-forthクローザに永続的に存在しています。つまり、dupと**


プリミティブを表すラムダ式は、マクロnew-forth**の展開によって参照がキャプチャされています。このコードをLispマクロサーフェスに引き戻して、新しいプログラムに埋め込むことはできますか? これについては後で戻りますが、まずForthメタプログラミングをさらに進めます。

どの言語でも、通常はプログラマーから隠されているレベルで、コードが自分自身を参照できる必要があります。この必要性の最も説得力のある例は、ループ、再帰、およびifステートメントのような条件式を実装するために、コードが何らかの方法で自分自身を参照する必要があるという観察です。Flub言語と非Flub言語の違いは、Flubが自己参照の挿入方法と場所を直接カスタマイズすることを防ぐことです。しかし、今行っているように、Lispの非Blubステータスは、それを非Flubにできることを意味します。

現在の状態の私たちのForthシステム(自己参照を挿入できない状態)は、ほぼ純粋なFlubです。純粋な関数型言語が副作用や非静的マッピングを排除するように言語を意図的に定義するのと同様に、純粋なFlub言語はループや再帰のような自己参照コード構造を排除するように定義されています。この結果として、純粋なFlubスレッドを解釈すると常に終了します。私たちのForth環境は完全に純粋ではありません。なぜなら、私たちはそれを違反することができますし、違反しますが、これまでのところ説明されているようにのみ使用される場合、純粋なFlubスレッドの結果になるという意味で純粋です。純粋なFlubはあまり有用ではないので、私たちのForth環境のFlub純粋性を台無しにしましょう。Flub方向、つまりコードスレッド化が不透明でアクセスできないCOMMON LISPのようなFlub言語に向かうのではなく、Forthの方向に向かい、このコードの属性をマクロでカスタマイズ可能にしましょう。

BRANCH-IF

(def-forth-naked-prim branch-if nil
  (setf pc (if (pop pstack)
             (cadr pc)
             (cddr pc))))

branch-ifプリミティブは、これまで提示された最初のネイキッドプリミティブです。ネイキッドプリミティブは、プログラムカウンタ抽象レジスタ(pc)を自動的に更新しないプリミティブであることを思い出してください。代わりに、それ自体で更新する必要があります。branch-ifはパラメータスタックから値を取り出します。値が非ヌルの場合、pcは解釈中のスレッドの次のセルに含まれるものに設定されます。値がnilの場合、pcは通常どおり再開されますが、解釈中のスレッドの次のセルをスキップします。

たとえば、次のコードは、新しいbranch-ifプリミティブを利用するためにForth環境を作成し、2つの単語を定義します。doubleとif-then-double。

* (go-forth (setq my-forth (new-forth))
    { 2 * } 'double name
    { branch-if double "Not doubling" print } 
        'if-then-double name)

NIL

doubleは単にパラメータスタックの最上位要素を2倍にして二乗します。if-then-doubleは2つの項目をパラメータスタックに必要とします。最上位の要素は消費され、2番目に上位の要素は最上位の要素が非ヌルであった場合にのみ二乗されます。branch-ifの後のスレッドの次の値は別のスレッド(double)へのポインタであるため、リターンスタックに再開場所をプッシュすることなく、実行制御がそのスレッドに転送されることに注意してください。Lispでは、これはテイルコールと呼ばれます。したがって、if-then-doubleにnilを渡すと、分岐が取られ、二乗は行われず、文字列が表示されます。

* (go-forth my-forth
    4 'nil if-then-double print)

"Not doubling"
4
NIL

しかし、値が非ヌルの場合、分岐は取られず、二乗が行われ、文字列は表示されません。

* (go-forth my-forth
    4 't if-then-double print)

8
NIL

EXIT

(forth-stdlib-add
  { r> drop } 'exit name)

しかし、単語から抜ける簡単な方法があり、それはexitという新しい単語で実装されます。Forthの興味深い特性は、呼び出されている単語がテイルコールであったかどうかを決定できることです。exitは通常のForth単語であり、通常どおり呼び出されます。Forthは現在のスレッド位置をリターンスタックにプッシュし、次にプログラムカウンタをexit単語の開始位置にポイントするように設定します。exitが呼び出されると、プリミティブr>と**


rを使用してリターンスタックに直接アクセスできるため、リターンスタックから再開場所を削除して破棄することで、呼び出し元単語が実行制御を取り戻せないようにすることができます。以下はexitの使用例です。

* (go-forth my-forth
    { "hello" print
      exit
      ;; Never gets here
      "world" print } 'exit-test name

    exit-test)

"hello"
NIL

COMPILER-PRIMS

(def-forth-naked-prim compile nil
  (setf (forth-word-thread dict)
        (nconc (forth-word-thread dict)
               (list (cadr pc))))
  (setf pc (cddr pc)))

(def-forth-prim here nil
  (push (last (forth-word-thread dict))
        pstack))

したがって、branch-ifはジャンプ、つまりgoto命令を実装し、おそらく実行中のスレッドの次のセルの値にジャンプします。現在実行中のスレッドから値を取得することは、Forthで一般的なパターンであり、ネイキッドプリミティブが必要です。別のプリミティブ、compileもこのパターンを使用します。compileはネイキッドプリミティブであり、現在実行中のスレッドの次のセルの値を取り込み、その値を辞書に追加された最後の単語のスレッドにコンパイルします。通常、コンパイル中の単語です。hereは、コンパイル中のスレッドの最後のコンスセルをパラメータスタックにプッシュする単純なプリミティブです。私たちのhereは、通常のForth単語hereとはわずかに異なります。Forthでは、hereは通常、次のメモリセルになる次のコンパイル場所をプッシュします。これは、従来のForthでは、次にコンパイルされるメモリ位置がこの時点でわかっているためです。コンススレッドコードでは、まだそのメモリをコンスしていないため、これはわかりません。

compileとhereが利用可能になったので、Forthマクロの作成を開始できます。Forth単語が即時である場合、コンパイル時に最後の単語定義のスレッドにコンパイルされるのではなく実行されることを思い出してください。Lispでマクロを適応および拡張する方法と同様に、即時単語を使用してForthを適応および拡張できます。Lispでは、メタプログラミングに使用される基本的なデータ構造はリストです。Forthでは、基本的なデータ構造はスタックです。

私たちのForth環境には、ifステートメントさえ提供されていないことに気づいたかもしれません。条件分岐プリミティブbranch-ifがありますが、これまでは他のForth単語へのテイルコールを作成するのに役立つだけでした。Forth単語はスレッドで表され、branch-ifがジャンプするセルに任意の単語の値を配置できることを思い出してください。現在コンパイル中の単語の一部にジャンプする値を配置した場合はどうなりますか? ある意味で、それは現在のForth単語の別の部分へのテイルコールになります。さて、ifステートメントはまさにそれです。条件がヌルである場合にのみ取られる、ifステートメントの末尾への条件付きテイルコールです。

IF

(forth-stdlib-add
  { compile not
    compile branch-if
    compile nop
    here } 'if name immediate)

現在Forthで完全にプログラミングしているため、新しいプリミティブを追加する必要はありません。IfステートメントをForthに追加するには、forth-stdlib-addマクロを使用して、Forthコードを標準ライブラリに追加するだけです。ifは即時単語として定義されていることに注意してください。つまり、コンパイル時にのみ使用されるべきです。しかし、即時であるため、実行され、コンパイルされません。即時単語に遭遇した場合、ターゲットスレッドには何も自動的にコンパイルされません。したがって、if自体は、ターゲットスレッドに3つの単語、not、branch-if、およびnopをコンパイルします。次に、here単語を実行します。これは、スタック上にコンパイルされた最後の単語(nop)のアドレスを残します。スタックにそれを残しますか? コンパイル時に単語が行う奇妙なことです。どのスタックにそれを残しますか? 技術的には、コンパイル時に使用されるスタックは制御スタックと呼ばれます。ほとんどのForthでは、制御スタックはパラメータスタックと同じです。実装の多様性のため、区別が必要です。特にクロスコンパイル環境では、制御スタックは最終的なパラメータスタックとは完全に分離されている場合があります。しかし、ここでは、ほとんどのインタラクティブなForth環境と同様に、制御スタックにパラメータスタックを使用します。

したがって、ifは、nopがコンパイルされた場所に対応する値をプッシュします。これは何に役立ちますか? nop自体はそれほど重要ではありませんが、その前に来るものが重要です。nopの直前のセルには、branch-if命令がコンパイルされています。nopの値を何に変更しても、if条件がヌルになった場合に内部インタプリタが分岐する場所になります。

THEN

(forth-stdlib-add
  { compile nop
    here swap ! } 'then name immediate)

しかし、なぜメモリ位置の代わりにnopをそこに置いたのですか? それはまだメモリ位置がわからないからです。プログラマーがthenという別の即時単語を実行するのを待つ必要があります。これは、ifによって制御スタックに残された値を消費します。then自体はnopをコンパイルし、ifによってコンパイルされたnopを上書きして、このnopの場所を書き込みます。したがって、ifとthenの間にコンパイルされたすべての単語は、条件がヌルの場合にスキップされます。

ABS

(forth-stdlib-add
  { 0 swap - } 'negate name
  { dup 0 < if negate then } 'abs name)

Absは、ifとthenを使用してスタックの最上位の絶対値を計算する単語です。値が0未満かどうかをチェックし、そうであれば、別の単語negateを呼び出して負の値をその絶対値に変換します。

このコンパイルプロセスで制御スタックが使用される最も重要な理由は、スタックを使用することで、ifステートメントのような制御構造をネストさせることができることです。つまり、すべてのif単語を対応するthenでバランスを取る限り、ifステートメントを他のifステートメント内に含めることができます。

ELSE

(forth-stdlib-add
  { compile 't
    compile branch-if
    compile nop
    here swap
    compile nop
    here swap ! } 'else name immediate)

Forthは非Flub言語であるため、このようなスレッドがどのように作成され、ifステートメントのような制御構造でスレッド化されるかは、透過的に指定されており、適応および拡張できます。ほとんどの言語にはifステートメントに関連付けられたelse句があります。おそらく私たちも追加すべきでしょう。別の即時単語elseが標準ライブラリに追加されます。elseは、終端thenへの無条件分岐にコンパイルされるため、真(二次または結果)分岐を取った場合、偽(三次または代替)分岐をスキップします。elseは次に、ifによってスタックに残された値を使用して、このnopをelse句の開始位置に置き換えます。次に、thenが利用できるように、自身のnopの位置をスタックに残します。thenが実行することを望む動作は、制御スタック上の位置がifまたはelseによって残されたかどうかにかかわらず同じであるため、else句がない場合でもthenは機能します。

MOD2

(forth-stdlib-add
  { evenp if 0 else 1 then } 'mod2 name)

mod2単語は、if、else、thenを使用して整数をモジュラス2での自然な剰余に還元します。スタックの最上位が偶数の場合は0、奇数の場合は1をプッシュします。

BEGIN-AGAIN

(forth-stdlib-add
  { compile nop
    here } 'begin name immediate
  { compile 't
    compile branch-if
    compile nop
    here ! } 'again name immediate)

条件分岐はコンパイル中のスレッドの他の部分へのテイルコールを実行するため、ループのような反復構造を作成するために同じ技術を使用する理由はありません。最も基本的なForthループは、beginとagainという即時単語によって定義されます。これら2つの単語は単純な無限ループを提供し、ifとthenと非常によく似た方法で実装されますが、これら2つの単語の間で保存されるアドレスは、アドレスをコンパイルする場所ではなく、分岐ステートメントにコンパイルされるべきアドレスに対応します。以下は、スタックに提供された数値から1までカウントダウンしてから終了する単純なループです。

* (go-forth my-forth
    { begin
        dup 1 < if drop exit then
        dup print
        1 - 
      again } 'countdown name

    5 countdown)

5
4
3
2
1
NIL

上記の例では、ifとthen構造がbegin-againループ内にネストされていることに注意してください。Forthの制御スタックのおかげで、スタックを尊重する任意の制御構造をネストすることは完全に許容されます。スタックを尊重するために、制御構造はプッシュしなかった値をポップしたり、終了時に余分な値を残したりしないようにする必要があります。しかし、Lispマクロを構築する際に参照透過性をしばしば違反することを選択するのと同様に、Forthではコンパイル時にスタックを尊重しないことを選択することがよくあります。次の例は前の例と同じですが、ループを脱出するためにexit単語を使用しない点が異なります。代わりに、[と]単語でコンパイルモードに切り替え、ifとbeginによって配置されたポインタを交換して、それらの対応するthenとagain単語を順序外で使用できるようにします。

* (go-forth my-forth
    { begin
      dup 1 >= if
                 dup print
                 1 - 
                 [ swap ] again
               then
      drop
    } 'countdown-for-teh-hax0rz name

    5 countdown-for-teh-hax0rz)

5
4
3
2
1
NIL

上記では、againによってコンパイルされたコード、つまりbeginに戻るコードは、ifステートメント内でのみ実行されます。他の言語でコンパイラにこのようにアクセスできる言語はほとんどありません。正確には非Flub言語だけです。この自由のため、ForthプログラマーはLispプログラマーよりもマクロ組み合わせに慣れていることがあります。本書のLispコードはマクロ組み合わせテクニックを定期的に使用していますが、これらのテクニックとそれらが可能にするレバレッジは、ほとんどの既存のLispコードではその可能な最大範囲まで活用されていません。しかし、本書が示そうとしたように、Lispはマクロの組み合わせに非常に適しています。このような組み合わせテクニックは、今後10年ほどの言語研究でプログラマーの生産性における最大の成果が見つかる場所だと考えています。

Going Lisp

これまでのところ、この章ではミニマリストなForth環境を定義し、Lispの観点から最も重要なForthメタプログラミングの概念のいくつかを実証しました。適切なツール(COMMON LISP)があれば、Forthを設計および実装するのにどれだけの労力が必要かを示したはずです。Forthプログラムを書いてForthプログラムを作成できますが、それはすでに知っていました。それがForthのすべてです。さらに、Lispのマクロシステムのおかげで、Lispプログラムを書いてForthプログラムを作成できます。しかし、Forthプログラムを書いてLispプログラムを作成できますか?

PRINT-FORTH-THREAD

(defun get-forth-thread (forth word)
  (with-pandoric (dict) forth
    (forth-word-thread
      (forth-lookup word dict))))

(defun print-forth-thread (forth word)
  (let ((*print-circle* t))
    (print (get-forth-thread forth word))
    t))

私たちのForthスレッドはコンスセルがリンクされたものであり、これらのツリーの葉は関数(プリミティブを表す)またはアトム(パラメータスタックにプッシュするデータ(を表す)であることを思い出してください。Forth抽象レジスタをpandoricマクロを通じてアクセス可能にすることにしたため、Forthスレッドを取得および印刷するユーティリティを作成するのは簡単です。Get-forth-threadは、渡されたForthクローザforthをpandorically開き、次にwordで指定された単語のスレッドを取得して返します。Print-forth-threadはこの結果のスレッドを、サイクルが含まれている場合に備えて**


print-circle*をtにバインドして印刷します。

デモンストレーションのために、2つのForth単語squareとsquare3を定義したと仮定します。

* (go-forth my-forth
    { dup * } 'square name
    { 3 square print } 'square3 name)

NIL

コンパイルされたForthスレッドでは、すべてのシンボルとその他の単語情報は削除されています。残っているのは、Forth my-forthの辞書から抽出されたリスト構造の一部です。

* (print-forth-thread my-forth 'square3)

(3
 (#<Interpreted Function>
  #<Interpreted Function>)
 #<Interpreted Function>)
T

上記のコードにはサイクルがないため、純粋なFlubプログラムです。前述のように、ほとんどの興味深いプログラムにはサイクルが含まれています。条件分岐とループを作成するために、ネイキッドForthプリミティブbranch-ifを使用できます。これにより、実行中のForthスレッドの次のセルの値によって示される場所にpc抽象レジスタを変更できます。また、**


rとr>に直接アクセスすることで、テイルコールを実装することもできました。ほとんどの他の言語とは異なり、呼び出されている単語の内部からでさえ、どの呼び出しがテイルコールであるかを直接カスタマイズできます。

しかし、Lispの中心的で重要な構造が1つ欠けているようです。再帰です。単語は自分自身を呼び出すことができますか? branch-ifを使用して単語の開始位置に戻る方法(テイル再帰)を見ました。しかし、実際に行いたいのは、通常のThreadメカニズムを通じて単語が自分自身を呼び出すことです。これを行うには、スレッドの開始位置をスレッドのセルとして格納する必要があり、現在の位置がリターンスタックに格納され、次にpcを単語の開始位置に設定する必要があります。これまでのところ、私たちの単語はフル再帰を利用できていません。なぜなら、コンパイルが完了するまで単語に名前を付けないからです。再帰呼び出しをコンパイルしようとするときに辞書を検索する際にはアクセスできません。幸いなことに、これを回避するために使用できる簡単なトリックがあります。コンパイルモードを終了し、再帰呼び出しをコンパイルする前にコンパイル中の単語に名前を付けるだけです。以下は、完全に再帰的な階乗計算機の例です。

* (go-forth (setq my-forth (new-forth))
    { [ 'fact name ]
      dup 1 - 
      dup 1 > if fact then
      * })

NIL

確かに、(fact 5)は120です。

* (go-forth my-forth
    5 fact print)

120
NIL

演習:一部のForthは、現在コンパイル中の単語のスレッドを単純にルックアップして、コンパイル中のスレッドに挿入するrecurseという単語を使用します。これは匿名再帰と呼ばれます。名前付き再帰を実装するための上記トリックの代替として、これを実行する即時単語を記述してください。

Factのスレッドは、上記のsquare3よりも複雑です。自己参照コードが含まれています。

* (print-forth-thread my-forth 'fact)

#1=(#2=#<Interpreted Function>
    1 #<Interpreted Function> #2# 1
    #<Interpreted Function>
    #<Interpreted Function>
    #<Interpreted Function>
    #4=(#<Interpreted Function>
        #<Interpreted Function>)
    #1# . #4#)
T

上記では、#2#はdupプリミティブを参照し、2回コンパイルされました。#1#はfactスレッド自体を参照し、再帰を実装しています。

これらの構造は、Lispプログラムの記述に使用するLispリスト構造と非常によく似ていませんか? これらのスレッドを実行する抽象マシンを理解しているため、いくつかの制限(すぐに説明します)で、これらのForthスレッドをLispリスト構造にコンパイルできます。この構造は、マクロによって式に挿入され、Lispコンパイラでコンパイルできます。このプロセスは、コンパイルされたプログラムを均一でプログラマブルなデータ構造(スレッド)から不透明でアクセス不可能なコードブロック(コンパイル済みCOMMON LISP関数)に変換するため、コードのflubifyingとして知られています。

もちろん、Forthスレッドと評価またはマクロに挿入できるLispリスト構造の間には、大きな違いがあります。第一に、Forthプリミティブは関数の単純なポインタ(ここで#<Interpreted Function>と表示)ですが、これらの関数が作成されたLispリスト構造が必要です。dtable抽象レジスタを説明する時期が来ました。dtableは、これらの関数からそれらを作成したリスト構造へのマッピングを提供するハッシュテーブルであり、Forthが作成されたときに設定されます。

Forthスレッドと私たちのLispプログラムの大きな違いは、Forthスレッドがリターンスタックを利用できると想定していることです。これは、COMMON LISPのようなFlubには実際には存在しない概念です。私たちのinner-interpreterコードの必要性を排除し、代わりにLispコンパイラに通常のLisp制御構造(関数呼び出しやtagbody/goフォームなど)でこれを処理させたいと考えています。

この章の残りのコードは、本書の他のコードのほとんどとは異なる方法で提示されます。その実装は詳細に説明されていませんが、高レベルの観点から説明されています。これは、実装のメカニズムが複雑で乱雑であり、正直なところ、それほど興味深いものではないためです。ほとんどのLispプログラマーは同様に実装するだろうと推測するだけで十分です。

FLUBIFY-AUX

(defmacro flubify-aux ()
  `(alambda (c)
     (if c
       (cond
         ((gethash (car c) prim-ht)
           (assemble-flub
             `(funcall 
                ,(gethash (car c) prim-ht))
             (self (cdr c))))
         ((gethash (car c) thread-ht)
           (assemble-flub
             `(funcall #',(car (gethash (car c)
                                  thread-ht)))
             (self (cdr c))))
         ((eq (car c) branch-if)
           (assemble-flub
             `(if (pop pstack)
                (go ,(gethash (cadr c) go-ht)))
             (self (cddr c))))
         ((consp (car c))
           (flubify forth (car c) prim-ht
                    thread-ht branch-if)
           (self c))
         (t
           (assemble-flub
             `(push ',(car c) pstack)
             (self (cdr c))))))))

Flubify-auxは、Forthスレッドを受け取り、それをFlub化されたLispコードの断片に変換する関数に展開されるマクロです。これは、各非プリミティブ単語がtagbodyで囲まれているという事実を利用しており、gensymをgotoのタグとして使用できます。

ASSEMBLE-FLUB

(defmacro assemble-flub (form rest)
  `(if (gethash c go-ht)
     (list* (gethash c go-ht)
            ,form
            ,rest)
     (list* ,form
            ,rest)))

Assemble-flubは、flubify-auxで頻繁に使用され、go-htハッシュテーブルをチェックして、現在コンパイルしている場所を参照するgoが以前のパスで見つかったかどうかを確認する略語として使用されます。見つかった場合、以前に選択されたgensymタグをtagbodyフォームに追加します。

FLUBIFY

(defun flubify (forth thread prim-ht
                thread-ht branch-if)
  (unless #1=(gethash thread thread-ht)
    (setf #1# (list (gensym)))
    (let ((go-ht (make-hash-table)))
      (funcall
        (alambda (c)
          (when c
            (cond
              ((eq (car c) branch-if)
                (setf (gethash (cadr c) go-ht)
                  (gensym)))
              ((consp (car c))
                (flubify forth thread prim-ht
                         thread-ht branch-if)))
            (self (cdr c))))
        thread)
      (setf #1# (nconc #1# (funcall
                             (flubify-aux)
                             thread))))))

Flubifyは、flubify-auxを使用する関数です。最初のパスを実行し、branch-if命令をチェックしてgo-htハッシュテーブルを構築します。また、現在のスレッドに接続されているすべてスレッドを再帰的にflub化します。実際、flubifyは二重に再帰的になる可能性があります。flubify-auxの使用を展開するまで、それを見ることはできません。見えませんが、Lispは見ることができます。参照透過性が透明なガラスのパネルである場合、ここでは鏡の家を見ています。

COMPILE-FLUBIFIED

(defun compile-flubified (thread thread-ht)
  `(labels (,@(let (collect)
                 (maphash
                   (lambda (k v) 
                     (declare (ignore k))
                     (push 
                       `(,(car v) ()
                          (tagbody ,@(cdr v)))
                       collect))
                   thread-ht)
                 (nreverse collect)))
     (funcall #',(car (gethash thread thread-ht)))))

Compile-flubifiedは、flubifyによって構築されたハッシュテーブルを受け取り、それをgensymによって関数名前空間で名前付けされた関数にバインドするlabelsを使用する形式に変換します。このスコープ内では、その展開は元のスレッド(これもflub化されています)をfuncallします。

FLUBIFY-THREAD-SHAKER

(defun flubify-thread-shaker
       (forth thread ht tmp-ht branch-if compile)
  (if (gethash thread tmp-ht)
    (return-from flubify-thread-shaker)
    (setf (gethash thread tmp-ht) t))
  (cond
    ((and (consp thread) (eq (car thread) branch-if))
       (if (cddr thread)
         (flubify-thread-shaker
           forth (cddr thread) ht
           tmp-ht branch-if compile)))
    ((and (consp thread) (eq (car thread) compile))
       (error "Can't convert compiling word to lisp"))
    ((consp thread)
       (flubify-thread-shaker
         forth (car thread) ht
         tmp-ht branch-if compile)
       (if (cdr thread)
         (flubify-thread-shaker
           forth (cdr thread) ht
           tmp-ht branch-if compile)))
    ((not (gethash thread ht))
       (if (functionp thread)
         (setf (gethash thread ht)
           (with-pandoric (dtable) forth
             (gethash thread dtable)))))))

Flubify-thread-shakerは、私たちのForthスレッドを実際にたどる関数です。関連するすべてのForthスレッドを再帰的にシェイクします。これは、指定されたスレッドを実行するために必要な関連Forthスレッド構造のみを分離し、次に各関数を対応するLispコードに変換し、if-branchesをスキップし、compileを見たときにエラーを発生させることを意味します。

FORTH-TO-LISP

(defun forth-to-lisp (forth word)
  (let ((thread (get-forth-thread forth word))
        (shaker-ht (make-hash-table))
        (prim-ht (make-hash-table))
        (thread-ht (make-hash-table))
        (branch-if (get-forth-thread forth 'branch-if))
        (compile (get-forth-thread forth 'compile)))
    (flubify-thread-shaker
      forth thread shaker-ht
      (make-hash-table) branch-if compile)
    (maphash (lambda (k v)
               (declare (ignore v))
               (setf (gethash k prim-ht) (gensym)))
             shaker-ht)
    (flubify forth thread prim-ht thread-ht branch-if)
    `(let (pstack)
       (let (,@(let (collect)
                 (maphash
                   (lambda (k v)
                     (push `(,(gethash k prim-ht)
                             (lambda () ,@(butlast v)))
                           collect))
                   shaker-ht)
                 (nreverse collect)))
         ,(compile-flubified
             thread thread-ht)))))

Forth-to-lispは、この章の前のマクロと関数によって促進される究極の関数です。これは、new-forthによって作成されたForth環境を受け取り、wordとして渡されたシンボルによって示されるスレッドをルックアップし、このスレッドを実行するための対応するLispコードを返します。まずスレッドをシェイクし(接続されているすべてスレッドを再帰的にシェイク)、次にflubification手順を適用します。最後に、内部インタプリタを通常のLisp制御構造で実装する少量のLispコードをラップします。

デモンストレーションのために、以前に定義したForth単語squareとsquare3を思い出してください。ここでも、my-forth Forth環境でそれらがどのように定義されたかを示します。

* (go-forth my-forth
    { dup * } 'square name
    { 3 square print } 'square3 name)

NIL

ここで、square3スレッドをLispに変換します。

* (forth-to-lisp my-forth 'square3)

(LET (PSTACK)
  (LET ((#:G1814 (LAMBDA () ; dup
                   (PUSH (CAR PSTACK) PSTACK)))
        (#:G1815 (LAMBDA () ; *
                   (PUSH (* (POP PSTACK)
                            (POP PSTACK))
                         PSTACK)))
        (#:G1816 (LAMBDA () ; print
                   (PRINT (POP PSTACK)))))
    (LABELS ((#:G1817 () ; square3
               (TAGBODY
                 (PUSH '3 PSTACK)
                 (FUNCALL #'#:G1818)
                 (FUNCALL #:G1816)))
             (#:G1818 () ; square
               (TAGBODY
                 (FUNCALL #:G1814)
                 (FUNCALL #:G1815))))
      (FUNCALL #'#:G1817))))

確かに、上記は実行可能なLispコードです。必要であれば、マクロを使用してどこかにコンパイルすることもできます。あるいは、単にevalすることもできます。

* (eval *)

9
NIL

分岐と再帰の両方を持つForthスレッドがどのようにflub化されるかを示すために、Forth単語factのコンパイル済みLispコードの一部を次に示します。

* (forth-to-lisp my-forth 'fact)
    ...
    (LABELS ((#:G1803 ()              ; fact
               (TAGBODY
                 (FUNCALL #:G1797)    ; dup
                 (PUSH '1 PSTACK)
                 (FUNCALL #:G1798)    ; -
                 (FUNCALL #:G1797)    ; dup
                 (PUSH '1 PSTACK)
                 (FUNCALL #:G1799)    ; >
                 (FUNCALL #:G1800)    ; not
                 (IF (POP PSTACK) (GO #:G1804))
                 (FUNCALL #'#:G1803)  ; fact
                #:G1804
                 (FUNCALL #:G1801)    ; nop
                 (FUNCALL #:G1802)))) ; *
      (FUNCALL #'#:G1803)) ; fact
    ...

したがって、このプログラムをForthで書きましたが、今やLispになりました。再帰が発生するかどうかを制御する条件付き制御構造をコンパイルするために、Forthの即時単語ifとthenを使用しました。リターンスタックの代わりに、Lispは通常の関数呼び出しインフラストラクチャを使用してこの再帰を実装します。

evalでこれをテストするとき、単語factはスタック上に値があると想定していますが、スタックは新しく始まります。この単語をテストするには、値がスタックに追加されるラッパー単語を作成する必要があります。たとえば、次のようになります。

* (go-forth my-forth
    { 5 fact print } 'fact5 name)

NIL

これを実行できます。

* (eval (forth-to-lisp my-forth 'fact5))

120
NIL

前述のように、LispとForthの不一致のため、forth-to-lispコンパイラにはいくつかの制限があります。たとえば、リターンスタックへのアクセスを提供しなくなるため、r>または**


rを使用するForth単語は禁止されます。これにはexitが含まれるため、以前の単語countdownは機能しません。ただし、exitを使用しないため、countdown-for-teh-hax0rzは機能します。Lispプログラムはリターンスタックにアクセスできないため、Forthのすべての制御構造をCOMMON LISPのようなFlub言語で実装できるわけではありません。演習:exitを、Lispブロックを使用して単語から戻る特別なケース単語として追加してください。

もう1つの制限は、Lispコードは非Flubコードをコンパイルできないため、if、then、begin、againのようなcompileを使用するForth単語を翻訳できないことです。もちろん、これらの単語を使用して作成されたForthスレッドは、上記のfactのように、単語をコンパイルするために引き続き使用できることに注意してください。最後の制限は、Forthでは、branch-ifは任意の単語にジャンプできることです。たとえそれが現在実行中の単語とは異なる単語内で作成されたものであっても。Lispでは、tagbody内の他の場所へのgoしかできません。Forthは非ローカル分岐を許可しますが、一般的な非ローカル分岐はCOMMON LISPのようなFlubでは実行できません。

ちょっと待ってください。Forth環境でプログラミングしていたときに、これらのFlub制限をすべて回避しませんでしたか? はい。マクロは、プログラムをLispとの間で変換することを可能にします。マクロのおかげで、Lispでは何でもプログラミングできます。

すべての資料は(C)Doug Hoyte、特に明記されていない限り、または暗示されていない限り。全著作権所有。