See this other question to construct macros from Paul Graham's set of 7 primitives.
构建一个 LISP 机器需要多少个原语？ 十个，七个还是五个？
On this site they say there are 10 LISP primitives.
The primitives are:
atom, quote, eq, car, cdr, cons, cond, lambda, label, apply.
Stevey reckons there are seven (or five):
Its part of the purity of the idea of LISP: you only need the seven (or is it five?) primitives to build the full machine.
What is the minimum number of primitives to build a LISP machine (ie something that can run an eval/value function on LISP code)? (And which ones are they?)
(I can understand you could live without
atom, label and apply)
7条回答 默认 最新
- 已采纳 MAO-EYE 2010-09-14 06:52点赞 8 评论 复制链接分享
- Memor.の 2013-02-28 22:13
I tried to find out what I needed and on a forum you'll find a thread that says You only need lambda. Thus, you can make a whole LISP in lambda calculus I you'd like. I found it interesting, but it's hardly the way to go if you want something that eventually has side effects and works in the real world.
For a Turing complete LISP I used Paul Grahams explanation of McCarthy's paper and all you really need is:
- special form quote
- special form if (or cond)
- special form lambda (similar to quote)
- function eq
- function atom
- function cons
- function car
- function cdr
- function-dispatch (list-lambda)
Thats 10. In addition to this, to have a implementation that you can test and not just on a drawing board:
- function read
- function write
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.点赞 10 评论 复制链接分享
- 衫裤跑路 2010-08-14 07:48
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.点赞 9 评论 复制链接分享
- lrony* 2010-08-14 10:21
McCarthy used seven operators to define the original Lisp:
cond. This article retraces his steps.点赞 9 评论 复制链接分享
- ?yb? 2010-09-10 08:51
- Didn"t forge 2010-08-14 16:39
McCarthy's Elementary S-functions and Predicates were:
Which was necessary because car and cdr are defined for lists only, which means you cannot count on any sort of answer to indicate what was happening if you gave
For testing equality between atoms.
For returning the first half (address) of the cons cell. (Contents of address register).
For returning the second half (decrement) of the cons cell. (Contents of decrement register).
For making a new cons cell, with the address half containing the first argument to cons, and the decrement half containing the second argument.
Tying it together: S-Functions
He then went on to add to his basic notation, to enable writing what he called S-functions:
To represent an expression without evaluating it.
The basic conditional to be used with the previously described predicates.
To denote a function.
So you can see he actually defined 9 basic "operators" for his Lisp machine. In a previous answer to another one of your questions, I explained how you could represent and operate on numbers with this system.
But the answer to this question really depends on what you want out of your Lisp machine. You could implement one without the
labelfunction, as you could simply functionally compose everything, and obtain recursion through applying the Y-Combinator.
atomcould be discarded if you defined the
caroperation on atoms to return
You could essentially have McCarthy's LISP machine with 7 of these 9 defined primitives, but you could ostensibly define a more concise version depending on how much inconvenience you'd want to inflict on yourself. I like his machine quite fine, or the many primitives in the newer languages like Clojure.点赞 7 评论 复制链接分享
- 乱世＠小熊 2017-08-06 15:05
"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.点赞 评论 复制链接分享