本当に最小のリスプ

Question

言語が完全に完全にリスプバリアントになっているように、必要なプリミティブの最小セットはどのくらいですか？

車、CDR、いくつかのフロー制御、そしてREPLのための何かで十分です。そのようなリストがあればいいです。

データ、整数、シンボル、リストの3種類しかないと仮定します（Picolispのように）

Answer 1

これについては良い議論があります LISP FAQ. 。プリミティブの選択に依存します。 McCarthyのオリジナルの「LISP 1.5プログラマーズマニュアル」は、CAR、CDR、CONS、EQ、およびATOMの5つの機能でそれを行いました。

Answer 2

ラムダ計算 チューリングは完全です。それは一つの原始的なものです - ラムダ。それをLISP構文に変換することはかなり些細なことです。

Answer 3

最小セットは、ジョン・マッカーシーが元の論文に掲載したものだと思います。

リスプの根.

コード.

Answer 4

実際にこれを確実に知る最良の方法は、あなたがそれを実装するかどうかです。私は3つの夏を使用して作成しました Zozotez これは、走っているマッカーティっぽいリスプです Brainfuck.

私は自分が必要なものを見つけようとしましたが、フォーラムであなたは言うスレッドを見つける ラムダだけが必要です。 したがって、必要に応じて、Lambda計算でリスプ全体を作成できます。面白いと思いましたが、最終的に副作用があり、現実の世界で機能するものが欲しいなら、それはほとんど道ではありません。

チューリングの完全なリスプのために私が使用しました ポール・グラハムはマッカーシーの論文の説明 そして、あなたが本当に必要とするのは：

• シンボル評価
• 特別なフォームの引用
• 特別なフォームif（またはcond）
• 特別なフォームラムダ（引用に似ています）
• 関数eq
• 関数原子
• 関数Cons
• ファンクションカー
• 関数CDR
• function-dispatch（基本的に適用されますが、実際にはシステムにさらされていないため、最初の要素が関数であるリストを処理します）

それは10に加えて、図面ボードだけでなくテストできる実装を持っていることに加えて：

• 関数読み取り
• 関数書き込み

それは12。私の中で Zozotez 私は実装しました set と flambda （匿名のマクロ、ラムダのような）。ファイルI/Oを除き、動的バウンドLISP（Elisp、Picolisp）を実装するライブラリにフィードできます（基礎となるBFはStdin/Stdout以外にサポートしていないため）。

両方でlisp1-interpreterを実装することをお勧めします LISP と (not LISP), 、言語の実装方法を完全に理解する。 LISPには非常にシンプルな構文があるため、良い出発点です。他のすべてのプログラミング言語では、通訳を実装する方法は非常に似ています。例えば。の中に SICPビデオ 魔法使いは論理的な言語の通訳を作りますが、構造とそれを実装する方法は、この言語がLISPとはまったく異なっていても、LISPインタープリターに非常に似ています。