LISP 머신을 구축하려면 얼마나 많은 프리미티브가 필요합니까?

LISP 머신을 구축하려면 얼마나 많은 프리미티브가 필요합니까? 10, 7, 5?

---

이 사이트에는 10 개의 LISP 프리미티브가 있다고합니다. 기본 요소는 다음과 같습니다 atom, quote, eq, car, cdr, cons, cond, lambda, label, apply..

http://hyperpolyglot.wikidot.com/lisp#ten-primitives

Stevey는 7 개 (또는 5 개)가 있다고 생각합니다.

LISP 아이디어의 순수함의 일부입니다. 전체 머신을 구축하려면 7 개 (또는 5 개입니까?) 기본 요소 만 필요합니다. http://steve-yegge.blogspot.com/2006/04/lisp-is-not-acceptable-lisp.html

LISP 머신을 구축하기위한 최소 프리미티브 수는 얼마입니까 (즉, LISP 코드에서 평가 / 값 함수를 실행할 수있는 것)? (그리고 그들은 어떤 것입니까?)

(당신이없이 살 수 있다는 것을 이해할 수 있습니다 atom, label and apply)

---

Paul Graham의 7 가지 기본 요소 집합에서 매크로를 구성하려면 이 다른 질문 을 참조하세요 .

---

기본 술어 / F 함수

McCarthy 의 기본 S- 함수 및 술어 는 다음 과 같습니다.

1. atom

   car와 cdr은 목록에 대해서만 정의 되었기 때문에 필요했습니다. 즉 car, 원자 를 주면 무슨 일이 일어 났는지 나타 내기 위해 어떤 종류의 대답에도 의지 할 수 없습니다 .

2. eq

   원자 간의 동등성을 테스트합니다.

3. car

   단점 셀의 전반부 (주소)를 반환합니다. (주소 레지스터의 내용).

4. cdr

   단점 셀의 후반부 (감소)를 반환합니다. (감소 레지스터의 내용).

5. cons

   새로운 cons 셀을 만들기 위해 주소 half는 cons에 대한 첫 번째 인수를 포함하고 감소 절반은 두 번째 인수를 포함합니다.

함께 묶기 : S-Functions

그런 다음 기본 표기법을 추가하여 S- 함수라고 부르는 것을 작성할 수있게했습니다.

1. quote

   평가하지 않고 표현을 표현하는 것.

2. cond

   이전에 설명한 술어와 함께 사용할 기본 조건입니다.

3. lambda

   기능을 나타냅니다.

4. label

   그는 재귀를 위해 이것을 필요로하지 않았지만, Y-Combinator 에 대해 알지 못했을 수도 있습니다 ( 폴 그레이엄에 따르면 ), 그는 편의와 쉬운 재귀를 가능하게하기 위해 이것을 추가했습니다.

---

그래서 그가 실제로 Lisp 머신에 대해 9 개의 기본 "연산자"를 정의한 것을 볼 수 있습니다. 다른 질문에 대한 이전 답변 에서이 시스템 으로 숫자 를 표현하고 조작 하는 방법을 설명했습니다 .

그러나이 질문에 대한 답은 Lisp 머신에서 원하는 것이 무엇인지에 달려 있습니다. label모든 것을 기능적으로 구성하고 Y-Combinator를 적용하여 재귀를 얻을 수 있으므로 함수 없이 하나를 구현할 수 있습니다.

atomcar반환 할 원자에 대한 작업을 정의한 경우 버릴 수 있습니다 NIL.

기본적으로 이러한 9 개의 정의 된 기본 요소 중 7 개가있는 McCarthy의 LISP 시스템을 가질 수 있지만, 자신에게 얼마나 많은 불편을 끼치고 싶은지에 따라 표면적으로 더 간결한 버전을 정의 할 수 있습니다. 나는 그의 기계가 아주 훌륭하거나 Clojure와 같은 새로운 언어의 많은 원시를 좋아합니다.

---

이것을 확실히 아는 가장 좋은 방법은 그것을 구현하는 것입니다. Brainfuck에서 실행되는 McCarty-ish LISP 인 Zozotez 를 만들기 위해 3 개의 여름을 사용 했습니다 .

내가 필요한 것을 찾으려고했고 포럼에서 You only need lambda 라는 스레드를 찾을 수 있습니다. 따라서 내가 원하는 람다 미적분으로 전체 LISP를 만들 수 있습니다. 나는 그것이 흥미 롭다는 것을 알았지 만 결국 부작용이 있고 현실 세계에서 작동하는 것을 원한다면 갈 길은 거의 없습니다.

Turing 완전한 LISP를 위해 저는 McCarthy의 논문에 대한 Paul Grahams의 설명을 사용 했으며 실제로 필요한 것은 다음과 같습니다.

• 기호 평가
• 특별 양식 견적
• 특수 형식 if (또는 cond)
• 특수 형식 람다 (인용문과 유사)
• 함수 eq
• 기능 원자
• 기능 단점
• 기능 차
• 기능 cdr
• 함수 디스패치 (list-lambda)

10.이 외에도 드로잉 보드뿐만 아니라 테스트 할 수있는 구현을 가지려면 :

• 기능 읽기
• 기능 쓰기

Thats 12. In my Zozotez I implemeted set and flambda (anonymous macroes, like lambda) as well. I could feed it a library implementing any dynamic bound lisp (Elisp, picoLisp) with the exception of file I/O (because the underlying BF does not support it other than stdin/stdout).

I recommend anyone to implement a LISP1-interpreter in both LISP and (not LISP) to fully understand how a language is implemented. LISP has a very simple syntax so it's a good starting point for a parser. I'm currently working on a scheme compiler written in scheme with different targets (like Stalin is for target C), hopefully BF as one of them.

---

McCarthy used seven operators to define the original Lisp: quote, atom, eq, car, cdr, cons and cond. This article retraces his steps.

---

This faq states:

There is no single "best" minimal set of primitives; it all depends on the implementation. For example, even something as basic as numbers need not be primitive, and can be represented as lists. One possible set of primitives might include CAR, CDR, and CONS for manipulation of S-expressions, READ and PRINT for the input/output of S-expressions and APPLY and EVAL for the guts of an interpreter. But then you might want to add LAMBDA for functions, EQ for equality, COND for conditionals, SET for assignment, and DEFUN for definitions. QUOTE might come in handy as well.

That comes from the School of Computer Science, Carnegie Melon website.

---

Paul Graham implements eval using seven.

In McCarthy's Micro Manual for LISP he implements eval using ten.

---

You just need an x86 MOV instruction.

"The M/o/Vfuscator (short 'o', sounds like "mobfuscator") compiles programs into "mov" instructions, and only "mov" instructions. Arithmetic, comparisons, jumps, function calls, and everything else a program needs are all performed through mov operations; there is no self-modifying code, no transport-triggered calculation, and no other form of non-mov cheating."

Seriously though, these primitives will not implement a Lisp Machine. A machine needs facilities like I/O, and garbage collection. Not to mention a function calling mechanism! Okay, you have seven primitives which are functions. How does the machine call a function?

The proper understanding of what these primitives make possible is that they expose the instruction set of a Universal Turing Machine. Because those instructions are "Lispy", by a slip of the tongue (speaking with a Lisp) we sneakily call this a "Lisp Machine". "Universal" means that the machine is programmable: with some combination instructions applied to the Universal Turing Machine, we can instantiate any Turing Machine. But so far, all of that is purely a mathematical construct.

To actually simulate this UTM—realize it physically in order to explore it on a computer, we need a machine which provides for a way to us to actually input those forms which create Turing Machines from combinations of those seven Lisp instructions. And we also need some form of output; the machine as to at least be able to tell us "yes", "no", or "Wait, I'm still running".

In other words, the only way those seven instructions can practically work is if they are hosted in a larger machine which provides the environment.

Also note that Graham's seven primitives have no explicit support for numbers, so you would have to build them out of functions ("Church numerals" technique). No production Lisp implementation does such a crazy thing.

참고URL : https://stackoverflow.com/questions/3482389/how-many-primitives-does-it-take-to-build-a-lisp-machine-ten-seven-or-five