8

言語がチューリング完全でLispバリアントになるために必要なプリミティブの最小セットは何ですか？

車、cdr、フロー制御など、REPL用のもので十分なようです。そのようなリストがあればいいのですが。

データには、整数、記号、リストの3種類しかないと仮定します（picolispのように）

4

4 に答える 4

12

ラムダ計算は完全にチューリングしています。プリミティブが1つあります-ラムダです。それをlisp構文に変換するのは非常に簡単です。

于 2010-04-28T17:10:32.260 に答える
6

これについてはLispFAQでよく議論されています。プリミティブの選択によって異なります。マッカーシーのオリジナルの「LISP1.5プログラマーズマニュアル」は、CAR、CDR、CONS、EQ、ATOMの5つの機能でそれを実現しました。

于 2010-04-28T17:17:23.063 に答える
5

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

Lispのルーツ。

コード。

于 2010-04-28T17:17:18.073 に答える
2

これを実際に確実に知る最良の方法は、それを実装するかどうかです。私は3つの夏を使用して、 Brainfuckで実行されるMcCarty風のLISPであるZozotezを作成しました。

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

チューリング完全LISPの場合、私はマッカーシーの論文のPaul Grahamsの説明を使用しましたが、本当に必要なのは次のとおりです。

  • シンボル評価
  • 特別な形式の見積もり
  • 特殊形式if（またはcond）
  • 特殊形式ラムダ（引用符と同様）
  • 関数eq
  • 関数アトム
  • 関数の短所
  • ファンクションカー
  • 関数cdr
  • function-dispatch（基本的に適用されますが、実際にはシステムに公開されないため、最初の要素が関数であるリストを処理します）

それは10です。これに加えて、製図板だけでなくテストできる実装を作成するには、次のようにします。

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

それ12.私のZozotezsetでは、flambda（ラムダのような匿名マクロ）も実装しました。ファイルI/Oを除いて、動的にバインドされたlisp（Elisp、picoLisp）を実装するライブラリをフィードできます（基盤となるBFはstdin / stdout以外はサポートしていないため）。

言語の実装方法を完全に理解するために、LISPとの両方でLISP1インタープリターを実装することをお勧めします。(not LISP)LISPの構文は非常に単純なので、出発点として適しています。他のすべてのプログラミング言語の場合、インタプリタの実装方法は非常に似ています。例えば。SICPビデオでは、ウィザードが論理言語のインタープリターを作成しますが、この言語はLispとは完全に異なりますが、構造と実装方法はlispインタープリターと非常によく似ています。

于 2016-02-28T17:52:59.230 に答える