StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<h2>Basic Predicates/F-functions</h2> <p><a href="http://www-formal.stanford.edu/jmc/recursive.pdf" rel="noreferrer">McCarthy</a>'s <em>Elementary S-functions and Predicates</em> were:</p> <ol> <li><p><code>atom</code></p> <p>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 <code>car</code> an atom. </p></li> <li><p><code>eq</code></p> <p>For testing equality between atoms.</p></li> <li><p><code>car</code></p> <p>For returning the first half (address) of the cons cell. (Contents of address register).</p></li> <li><p><code>cdr</code></p> <p>For returning the second half (decrement) of the cons cell. (Contents of decrement register).</p></li> <li><p><code>cons</code></p> <p>For making a new cons cell, with the address half containing the first argument to cons, and the decrement half containing the second argument.</p></li> </ol> <h2>Tying it together: S-Functions</h2> <p>He then went on to add to his basic notation, to enable writing what he called S-functions:</p> <ol> <li><p><code>quote</code></p> <p>To represent an expression without evaluating it.</p></li> <li><p><code>cond</code></p> <p>The basic conditional to be used with the previously described predicates.</p></li> <li><p><code>lambda</code> </p> <p>To denote a function.</p></li> <li><p><code>label</code></p> <p>Though he didn't need this for recursion, he might not have known about the <a href="https://en.wikipedia.org/wiki/Fixed-point_combinator#Fixed_point_combinators_in_lambda_calculus" rel="noreferrer">Y-Combinator</a> (<a href="http://lib.store.yahoo.net/lib/paulgraham/jmc.ps" rel="noreferrer">according to Paul Graham</a>), he added this for convenience and to enable easy recursion.</p></li> </ol> <hr> <p>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 <a href="https://stackoverflow.com/questions/3467317/can-you-implement-any-pure-lisp-function-using-the-ten-primitives-ie-no-type-pr/3468060#3468060">represent and operate on numbers</a> with this system. </p> <p>But the answer to this question really depends on what you want out of your Lisp machine. You could implement one without the <code>label</code> function, as you could simply functionally compose everything, and obtain recursion through applying the Y-Combinator. </p> <p><code>atom</code> could be discarded if you defined the <code>car</code> operation on atoms to return <code>NIL</code>. </p> <p>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.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload