多くの (全部かも?) プログラミング言語はアセンブリ言語で構成されています
Lisp はアセンブリ言語でどのように実装されていますか?
Google に関する適切なリファレンス、マニュアル、チュートリアル、またはキーワードはありますか?
独自の Lisp 実装を構築するための公式の規則/規則はありますか?
末尾再帰などは、いくつかの実施規則または何かに従う必要があります..
ありがとう
10533 次
5 に答える
28
他のコメントや投稿は正しいのですが、この質問は漠然としていて少し混乱しているかもしれません。いくつかの推奨事項を共有せずにはいられません。私は最近、言語の実装に少し興味を持ち始めたので、Lisp の実装に関する多くのリンクと本を集めました。もちろん、これは深いトピックですが、Lisp コンパイラーまたは Lisp インタープリターを実装し、read. これにより、作成者はコンパイルまたは解釈の要点にすばやく到達できます。これらの推奨事項は、私が読んだ、または読み始めた、または読んでいる本であり、主に Common Lisp ではなく、Scheme を扱っていますが、それでもいくらか興味深いかもしれません。
言語実装のバックグラウンドがなく、古典的な Lisp や Scheme の「メタサーキュラー エバリュエーター」について読んだことがない場合は、Structure and Interpretation of Computer Programs をお勧めします。Lisp-in-Lisp (または Scheme-in-Scheme...) を見たことがある場合は、読み飛ばしてください。SICP の最後の 2 つの章で、著者は Lisp/Scheme 用のいくつかの異なるインタープリターといくつかのバリアント、およびバイトコード コンパイラーと仮想マシンを紹介します。それは単に素晴らしい本であり、無料です。
SICP を読む時間がない場合、または解釈とコンパイルの章にたどり着くためだけにじっくり読みたくない場合は、The Little Schemerをお勧めします。この本は非常に短く、Lisp と Scheme の初心者を対象としていますが、Lisp で書かれた Lisp インタープリターを見たことがないのであれば、彼らはそれを紹介しています。 .
An Introduction to Scheme and its Implementation と呼ばれる、SICP に似た別の無料の Scheme の本があります。そこにはインタープリターとコンパイラーに関するセクションがあり、解析などの複雑なことも扱っており、SICP よりも少し深いようです。エディターが必要だったかもしれませんが、それでも印象的な製品です。
Lisp で Lisp を実行する方法について適切なアイデアがあれば、Lisp をより低いレベルで実装する方法に取り組むことができます。
Lisp in Small Piecesは頻繁に推奨されます。私はそのほとんどを読みましたが、それは間違いなく素晴らしい本であり、核心に満ちたものであると言えます. よくわからないときは、すくい取るのが簡単なので、目の細かい櫛でもう一度調べます。また、作成者のサイトからコードを実行するのにも苦労しました。手に入れたら、Gambit Scheme を使用して、このディストリビューションから Meroon で Meroonet に依存するコードを実行することをお勧めします。Lisp in Small Pieces は、Scheme で書かれた多数のインタープリター、バイトコード コンパイラー、コンパイラーから C へのコンパイラーを示しています。
Lisp in Small Pieces は動きが速く、非常に密集しています。それが難しすぎる場合は、おそらくThe Essentials of Programming Languagesから始めてください。私はそれのいくつかを読んだことがありますが、それは非常に優れていますが、より多くの通訳です. どうやら古いエディションの 1 つ (第 1 版かどうかはわかりません...) にはコンパイラが含まれていたようです。3つのエディションでかなりの変更があるようですが、1つ目はAmazonで激安なのでチェックしてみてください。
Cへのコンパイルに関しては、これは毛むくじゃらの部分がたくさんある、一種の総体的な主題です。C へのコンパイルは、末尾呼び出しを最適化し、クロージャを処理する方法、ファーストクラスの継続、ガベージ コレクションなど、これらすべての奇妙なコーナーの問題を引き起こしますが、それは非常に興味深いものであり、Scheme の多くの「実際の」実装はこのルートをたどっています。これに関する Marc Feeley のプレゼンテーションは非常に興味深いもので、タイトルはThe 90 Minute Scheme to C compilerです。
アセンブリに至るまでコンパイルするためのリソースはほとんどありませんが、Scheme の x86 へのコンパイルを紹介する、An Incremental Approach to Compiler Construction と呼ばれる、しばしば推奨される論文があります。読者のことをほとんど想定していませんが、単純に速すぎて、十分な詳細が記入されていないことがわかりました。運が良くなるかもしれません。
上記の推奨事項の多くは、1 年以上前にmahmudから Hacker News に寄せられたこの怪物コメントから来ています。多数の ML リソースと、継続を使用したコンパイルを参照します。勉強はそこまで進んでいないので、何が良いとか悪いとかはなんとも言えません。しかし、それは信じられないほど貴重なコメントです。参考文献には、Andrew Appel の「Compiling with Continuations」と Paul Wilson の「Uniprocessor Garbage Collection Techniques」ペーパーが含まれます。
幸運を！
于 2011-05-03T14:41:38.500 に答える
9
Lispの実装に使用されるアセンブリ言語の例については、Clozure Common Lispを参照してください。Clozure CL はほとんどが Common Lisp 自体で実装されていますが、C で記述されたカーネルとアセンブリの低レベル機能がいくつかあります。
たとえば、次のマクロは、x86 ハードウェアでプリミティブ関数を実装するcompiler/X86/x86-lapmacros.lispCARのマクロで、それぞれ 32 ビットと 64 ビットに 1 つのアセンブリ命令があります。
(defx86lapmacro %car (src dest)
(target-arch-case
(:x8632
`(movl (@ x8632::cons.car (% ,src)) (% ,dest)))
(:x8664
`(movq (@ x8664::cons.car (% ,src)) (% ,dest)))))
示されているように、アセンブリ コード自体は Lisp 形式でエンコードされています。別のプラットフォームへの移植には、(とりわけ) これらの低レベル操作を別のアセンブリ言語に変換し、クロスコンパイルして新しいプラットフォームでランタイムを作成することが含まれます。
ECL (Embeddable Common Lisp)は、C にコンパイルするという別のアプローチを採用しています。これにより、C コンパイラを備えたプラットフォームに実装を簡単に移植できます。
于 2011-05-03T20:01:53.247 に答える
8
私は過去に少し考えました（代わりにCカーネルを使用することに頼りました）。もちろん、単一の「アセンブリ」はありませんが、x86/32 ビットの場合、これは私が計画していたことです。
基本値は 64 ビット ノードに格納され、最下位 3 ビットがタグとして使用され、次の意味があります。
000 -> cell (64 bits are basically two pointers: car/cdr)
001 -> fixnum (64-3-1 bits usable for values)
010 -> vector (32-3 bits for size and 32 bit for pointer to first element)
011 -> symbol (32 bits pointing to values in global env, 32 pointing to name)
100 -> native code (32 bits pointing to executable machine code, 32 bits to args)
101 -> float (using 64-3-1 bit by dropping 4 bits from mantissa)
110 -> string (using 32-3 bits for size and 32 bits pointing to bytes)
111 -> struct (32 bits pointing to definition, 32 bits pointing to content)
すべての割り当てが 8 バイトの倍数であると想定される場合 (8 バイトのセル サイズで妥当)、ポインターを考慮すると 3 ビットが使用可能のままです。単純なガベージ コレクタを実装するには、1 ビット追加する必要があります (「生きている」ビット)。C の実装では、ノードの種類に応じて、このビットをさまざまな部分 (たとえば、ポインターの場合は上位 32 ビットの最下位ビット) に割り当てることになりました。
私のアイデアは、ページに割り当てられてフリーリストで再利用される「ノードメモリ」（上記のレイアウトを使用）と、可変サイズの文字列/コード/配列に使用される「バイナリメモリ」の2つのタイプのメモリを持つことでした。
touch生きているノードによって参照される生きているノードとして再帰的にマークする関数を実装するには、ノードの種類に応じて特定のコードが必要です。
もちろん、これはすべて素朴なアプローチですが、それでも「C」で動作するようになりました。アセンブリでもそれを実行できたと確信しています（私のCコードはvoid *どこでも使用しているため、基本的には移植可能な32ビットアセンブラです）。私の C 実装の怠惰さのために、使用可能なすべてのビットを使用する代わりに、浮動小数点数と整数 (上位 32 ビットを使用) に 32 ビットのみを使用しました。
于 2011-05-03T12:53:49.927 に答える
3
あなたの質問は非常に時代遅れの仮定に基づいています。最近では、アセンブリ言語で書かれた言語実装はほとんどなく、アセンブリ言語で書かれている Lisp 実装も私は知りません。自己ホスト型の実装に加えて、最近では C が一般的な実装言語です。
Lisp 関数のアセンブリ言語表現を見たい場合は、DISASSEMBLE 関数があります。
于 2011-05-03T09:16:23.150 に答える