[Question]
  [
# McCarthy's 1959 LISP
In early 1959, John McCarthy wrote a groundbreaking paper defining just nine primitive functions that when put together still form the basis for all LISP-like languages today. The paper is available digitized here: 
**<http://www-formal.stanford.edu/jmc/recursive.pdf>**
Your job is to fully implement a parser and interpreter for McCarthy's LISP exactly as described in the 1960 paper: That is, the functions `QUOTE`, `ATOM`, `EQ`, `CAR`, `CDR`, `CONS`, `COND`, `LAMBDA`, and `LABEL` should all be functional. The paper will take precedence over this challenge text when considering the correctness of answers, but I've tried to summarize the nine functions below. Note that the language will be in ALL CAPS and no error checking is necessary, all input should be presumed to be valid.
**Types**
* There are only two types in McCarthy's LISP: An atom, and a linked list, which is recursively defined as a head, which may be a list or an atom, and a list that the head is attached to (tail). `NIL` has the special property of being both an atom and a list.
* As per the paper, atom names will only consist of capital letters, numbers, and the space character, though strings of consecutive spaces should be considered as just one space and all leading and trailing space characters should be removed. Example equivalent atom names (replace underscore with space character): `___ATOM__1__ = ATOM_1`. Example not equivalent atom names: `A_TOM_1 != ATOM_1`
* Lists are denoted by parentheses, and an implied `NIL` is at the end of every list. Elements in a list are separated by commas and *not* whitespace like in most modern Lisps. So the list `(ATOM 1, (ATOM 2))` would be `{[ATOM 1] -> {[ATOM 2] -> NIL} -> NIL}`.
**`QUOTE`:**
* Takes one argument which may be either an atom (single element) or a linked list. Returns the argument exactly.
* **Test cases:**
* `(QUOTE, ATOM 1) -> ATOM 1`
* `(QUOTE, (ATOM 1, ATOM 2)) -> (ATOM 1, ATOM 2)`
**`ATOM`:**
* Takes one argument which may be either an atom (single element) or a linked list. Returns `T` (true) if the argument is an atom, or `NIL` (false) if the argument is not an atom.
* **Test cases:**
* `(ATOM, (QUOTE, ATOM 1)) -> T`
* `(ATOM, (QUOTE, (ATOM 1, ATOM 2))) -> NIL`
**`EQ`:**
* Takes two arguments which must be atoms (behavior is undefined if either of the arguments are not atoms). Returns `T` (true) if the two atoms are equivalent, or `NIL` (false) if they are not.
* **Test cases:**
* `(EQ, (QUOTE, ATOM 1), (QUOTE, ATOM 1)) -> T`
* `(EQ, (QUOTE, ATOM 1), (QUOTE, ATOM 2)) -> NIL`
**`CAR`:**
* Takes one argument which must be a list (behavior is undefined if it is not a list). Returns the first atom (head) of that list.
* **Test cases:**
* `(CAR, (QUOTE, (ATOM 1, ATOM 2))) -> ATOM 1`
**`CDR`:**
* Takes one argument which must be a list (behavior is undefined if it is not a list). Returns every atom but the first atom of the list, i.e. the tail. Note that every list ends in an implied `NIL`, so running `CDR` on a list that appears to just have one element will return `NIL`.
* **Test cases:**
* `(CDR, (QUOTE, (ATOM 1, ATOM 2))) -> (ATOM 2)`
* `(CDR, (QUOTE, (ATOM 1))) -> NIL`
**`CONS`:**
* Takes two arguments. The first may be an atom or a list but the second must be a list or `NIL`. Prepends the first argument to the second argument and returns the newly-created list.
* **Test cases:**
* `(CONS, (QUOTE, ATOM 1), (QUOTE, NIL)) -> (ATOM 1)`
* `(CONS, (QUOTE, ATOM 1), (CONS, (QUOTE, ATOM 2), (QUOTE, NIL))) -> (ATOM 1, ATOM 2)`
**`COND`:**
* This is LISP's "if-else" statement of sorts. Takes a variable-length amount of arguments, each of which must be a list of length exactly 2. For each argument list in order, evaluate the first term and if it is true (T), return the associated second term and exit the function. If the first term is not true, move on to the next argument and test its condition, and so on until the first true condition is reached. At least one of the argument conditions can be assumed to be true -- if they are all false, this is undefined behavior. See page 4 for a good example of the behavior of this function.
* **Test cases:**
* `(COND, ((ATOM, (QUOTE, ATOM 1)), (QUOTE, 1)), ((ATOM, (QUOTE, (ATOM 1, ATOM 2))), (QUOTE, 2))) -> 1`
* `(COND, ((ATOM, (QUOTE, (ATOM 1, ATOM 2))), (QUOTE, 2)), ((ATOM, (QUOTE, ATOM 1)), (QUOTE, 1))) -> 1`
**`LAMBDA`:**
* Defines an anonymous function. Takes two arguments, the first being a list of atoms which represent the arguments to the function and the second being any S-expression (the function body), which would typically use the arguments.
* **Test cases:**
* Defining and using an anonymous "isNull" function:
* `((LAMBDA, (ATOM 1), (EQ, ATOM 1, (QUOTE, NIL))), (QUOTE, NIL)) -> T`
* `((LAMBDA, (ATOM 1), (EQ, ATOM 1, (QUOTE, NIL))), (QUOTE, ATOM 1)) -> NIL`
**`LABEL`:**
* Gives a name to an anonymous `LAMBDA` function, which also allows that function to be called recursively in the body of the `LAMBDA`. Takes two arguments, the first being a label and the second being the `LAMBDA` function to which the label should be bound. Returns the name supplied. The scope of all `LABEL` names is global, and redefining a `LABEL` is undefined behavior.
* Fun fact, `LABEL` is not actually necessary to create recursive functions as we now know `LAMBDA` can be used with a ['Y-Combinator'](https://en.wikipedia.org/wiki/Fixed-point_combinator#Fixed_point_combinators_in_lambda_calculus) to accomplish this task, but McCarthy wasn't aware of this method when writing the original paper. It makes programs much easier to write anyways.
* **Test cases:**
* `(LABEL, SUBST, (LAMBDA, (X, Y, Z), (COND, ((ATOM, Z), (COND, ((EQ, Y, Z), X), ((QUOTE, T), Z))), ((QUOTE, T), (CONS, (SUBST, X, Y, (CAR, Z)), (SUBST, X, Y, (CDR, Z))))))) -> SUBST`
* *(after running the above)* `(SUBST, (QUOTE, A), (QUOTE, B), (QUOTE, (A, B, C))) -> (A, A, C)`
To help visualize the `SUBST` function above, it could be represented as this Python-like pseudocode:
```
def substitute(x, y, z): # substitute all instances of y (an atom) with x (any sexp) in z
    if isAtom(z):
        if y == z:
            return x
        elif True: 
            return z
    elif True:
        return substitute(x,y,z[0]) + substitute(x,y,z[1:])
```
**FINAL TEST CASE:**
If I have transcribed it correctly, your interpreter should be able to interpret `EVAL` with this code:
```
(LABEL, CAAR, (LAMBDA, (X), (CAR, (CAR, X))))
(LABEL, CDDR, (LAMBDA, (X), (CDR, (CDR, X))))
(LABEL, CADR, (LAMBDA, (X), (CAR, (CDR, X))))
(LABEL, CDAR, (LAMBDA, (X), (CDR, (CAR, X))))
(LABEL, CADAR, (LAMBDA, (X), (CAR, (CDR, (CAR, X)))))
(LABEL, CADDR, (LAMBDA, (X), (CAR, (CDR, (CDR, X)))))
(LABEL, CADDAR, (LAMBDA, (X), (CAR, (CDR, (CDR, (CAR, X))))))
(LABEL, ASSOC, (LAMBDA, (X, Y), (COND, ((EQ, (CAAR, Y), X), (CADAR, Y)), ((QUOTE, T), (ASSOC, X, (CDR, Y))))))
(LABEL, AND, (LAMBDA, (X, Y), (COND, (X, (COND, (Y, (QUOTE, T)), ((QUOTE, T), (QUOTE, NIL)))), ((QUOTE, T), (QUOTE, NIL)))))
(LABEL, NOT, (LAMBDA, (X), (COND, (X, (QUOTE, NIL)), ((QUOTE, T), (QUOTE, T)))))
(LABEL, NULL, (LAMBDA, (X), (AND, (ATOM, X), (EQ, X, (QUOTE, NIL)))))
(LABEL, APPEND, (LAMBDA, (X, Y), (COND, ((NULL, X), Y), ((QUOTE, T), (CONS, (CAR, X), (APPEND, (CDR, X), Y))))))
(LABEL, LIST, (LAMBDA, (X, Y), (CONS, X, (CONS, Y, (QUOTE, NIL))))) 
(LABEL, PAIR, (LAMBDA, (X, Y), (COND, ((AND, (NULL, X), (NULL, Y)), (QUOTE, NIL)), ((AND, (NOT, (ATOM, X)), (NOT, (ATOM, Y))), (CONS, (LIST, (CAR, X), (CAR, Y)), (PAIR, (CDR, X), (CDR, Y)))))))
(LABEL, EVAL, (LAMBDA, (E, A), (COND, ((ATOM, E), (ASSOC, E, A)), ((ATOM, (CAR, E)), (COND, ((EQ, (CAR, E), (QUOTE, QUOTE)), (CADR, E)), ((EQ, (CAR, E), (QUOTE, ATOM)), (ATOM, (EVAL, ((CADR, E), A)))), ((EQ, (CAR, E), (QUOTE, EQ)), (EQ, (EVAL, (CADR, E, A)), (EVAL, (CADDR, E, A)))), ((EQ, (CAR, E), (QUOTE, COND)), (EVCON, (CDR, E), A)), ((EQ, (CAR, E), (QUOTE, CAR)), (CAR, (EVAL, (CADR, E), A))), ((EQ, (CAR, E), (QUOTE, CDR)), (CDR, (EVAL, (CADR, E), A))), ((EQ, (CAR, E), (QUOTE, CONS)), (CONS, (EVAL, (CADR, E), A), (EVAL, (CADDR, E), A))), ((QUOTE, T), (EVAL, (CONS, (ASSOC, (CAR, E), A), (EVLIS, (CDR, E), A)), A)))), ((EQ, (CAAR, E), (QUOTE, LABEL)), (EVAL, (CONS, (CADDAR, E), (CDR, E)), (CONS, (CONS, (CADAR, E), (CONS, (CAR, E), (CONS, A, (QUOTE, NIL))))))), ((EQ, (CAAR, E), (QUOTE, LAMBDA)), (EVAL, (CADDAR, E), (APPEND, (PAIR, (CADAR, E), (EVLIS, (CDR, E), A)), A))))))
(LABEL, EVCON, (LAMBDA, (C, A), (COND, ((EVAL, (CAAR, C), A), (EVAL, (CADAR, C), A)), ((QUOTE, T), (EVCON, (CDR, C), A)))))
(LABEL, EVLIS, (LAMBDA, (M, A), (COND, ((NULL, M), (QUOTE, NIL)), ((QUOTE, T), (CONS, (EVAL, (CAR, M), A), (EVLIS, (CDR, M), A))))))
```
After running that behemoth, this line should return `(A, B, C)`:
```
(EVAL, (QUOTE, (CONS, X, (QUOTE, (B, C)))), (QUOTE, ((X, A), (Y, B))))
```
However, to quote John McCarthy himself on page 16, it seems like he was running out of characters on his computer:
> 
> If more characters were available on the computer, it could be improved considerably ...
> 
> 
> 
Therefore, this challenge is tagged [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'") and the shortest answer in characters will be the winner. Standard loopholes apply. Good luck!
**Note on String Evals**: I understand that some think it may be possible to win this challenge by using a Lisp and modifying the syntax to fit the host language and then using a string `(eval)`. I'm not particularly convinced that this approach will necessarily win especially with the identifier naming rules, and even if it did I think banning string `eval`s in all languages would be a subjective and slippery slope. But I don't want to punish people for doing this challenge the 'right' way, so I may allow two winners for this challenge, one in a Lisp-like language and one in a non-Lispy language, if this becomes a problem.
  
[Answer]
# Python 3, 770 bytes
This is a REPL on stdin/stdout. Expects every line to be a full statement or empty. `eval` is used to shorten the implementation, but is otherwise not necessary for logic.
```
import re,sys;S=re.sub
P=lambda l:eval(S("([A-Z0-9][A-Z0-9 ]*)",r"' '.join('\1'.strip().split())",S("NIL","()",S("\)",",)",l))))
d={"QUOTE":'(v,L[1])[1]',"EQ":'[(),"T"][E(L[1],v)==E(L[2],v)]',
"CDR":'E(L[1],v)[1:]',"CONS":'(E(L[1],v),)+E(L[2],v)',"CAR":'E(L[1],v)[0]',
"LAMBDA":'("#",)+L[1:]',"LABEL":'[v.update({L[1]:E(L[2],v)}),L[1]][1]'}
def E(L,v):
 if L*0=="":return v[L]
 elif L[0]in d:return eval(d[L[0]])
 elif L[0]=="COND":return next(E(l[1],v)for l in L[1:]if E(l[0],v)=="T")
 elif L[0]=="ATOM":o=E(L[1],v);return[(),"T"][o*0in["",o]]
 else:l=E(L[0],v);n=v.copy();n.update({a:E(p,v)for a,p in zip(l[1],L[1:])});return E(l[2],n)
R=lambda o:o==()and"NIL"or 0*o==()and"(%s)"%", ".join(R(e)for e in o)or o
g={}
for l in sys.stdin:
 if l.strip():print(R(E(P(l),g)))
```
[Answer]
# [APL (Dyalog Unicode)](https://www.dyalog.com/), ~~523...451~~ 447 bytes
Saved 12 bytes thanks to [@Bubbler](https://codegolf.stackexchange.com/users/78410/bubbler)!
Saved 1 byte thanks to [@Adám](https://chat.stackexchange.com/users/130368/adam) (and 7 more thanks to [this comment](https://codegolf.stackexchange.com/questions/68637/implement-multiplicative-fuzzy-logic#comment505414_216446) on another answer)
```
s←⎕SE.Dyalog.Utils.repObj
z←'NIL'
p←{')'=⊃⍵:(⊂z)(1↓⍵)⋄v r←{'('=⊃⍵:p⍵⋄⍵(↑,Ö⊂↓)⍨⊃⍸⍵∊',)'}1↓⍵⋄n r←∇r⋄(n,⍨⊂v)r}
e←{1=≡⍵:((⊃⍺)⍳⊂⍵)⊃(1⊃⍺),⊂⍵⋄⍺(⍎⍺e⊃⍵)1↓⍵}
b←⊃∘z'T'
CAR←⊃x←e∘⊃
CDR←1↓x
QUOTE←⊃⊢
CONS←{(⊂⍺x⍵),⊆⍺e 1⊃⍵}
EQ←{b≡/⍺∘e¨¯1↓⍵}
ATOM←b 1=∘≡x
COND←{z≢⍺x⊃⍵:⍺e 1⊃⊃⍵⋄⍺∇1↓⍵}
LAMBDA←{⍕'{((('(s⊃⍵)'),⊃⍺)((⍺∘e¨⍵),1⊃⍺))e'(s 1⊃⍵)'}'}
LABEL←{u←⍎⍕'#.'(⊃⍵)'←',⍺e 1⊃⍵⋄⊃⍵}
```
To execute a line of LISP:
```
{{1=≢⍵:⍵⋄1=≡⍵:'_'⎕R' '⊢⍵⋄⍕1⌽')(',∇¨¯1↓⍵}⍬⍬e⊃p'(?<=\(|,) *(?=\d)| +' ' *([(),]) *'⎕R'_' '\1'⊢⍵}
```
[Try it online!](https://tio.run/##nVVPaxNBFL/vp1jwMDO6VnsVi0x391BImjZJJcGKNLqVSmhDWiWtzaUtNY1WFKl48WBB8CB4kIIUvNRvsl@kvvdmZnez/yqWdLP79v3@vDdvJiu97s0n2yvdjaeX4duTx9tsc6W7xezw9YEdrK90ukFDVprWn4/h4buXPDw@g48dHp8L@IdPHDkTQ7h@thc2utura92uvbrRh8BXC1jnaoC@fbkJV3hq@FMeCU4tba11N6f6Qa/WeWbtwFs2P1dhVg@1mGAz4XgfiO/wcLy3I/h0ePgBdcDaC7tPOTzK6aGR1wdw5eHhewf8jvcgH2x@o4xf@H40Zo5gQ00E6evEE45e9eGBrzuUvfdC9IdWgALTM@HRF7LAiQXL/onMaGO8D5ZU1FExMoA9eQtfgXImtNrQ6qAUxEafdliTWa6sq8AAvgKIwq3lehhEyMBaXKo1fY0Zn1pubb6hFgG1zgfIDbqHKGUrIyDiL2JOB2zfwhUafQouvl38iDzIZq0KCR0bKgPFoy8D5PUQsxMenRKvamhMS8@qNOhURFWR1VlPIjI8PmEvOeeMb@qaGTqjzkDjjA0ybDomAsg2tmFNGBLO@hXke45FYw9P2LUpxk0OzoeTrBY96bKtYBA8Riwt2akqABOiFWSPGMxendkMmmkKOpkO3/xmggPv6FWyUeHxd/jgEvYYv3d3ZpnvOsK@zu/NLD8Ru/YNoIGnB1w4DyGsmB9BcHla0w8vL8mTzTjV5diulHXH5qptcNMScHEpRteWgD@WBnleDohidM0HSa9QqRjkyUIlWaIkS6US2DywdwXYKwXLf0AnDQBJikU2GjV3gsSx28QDmwK@uL9IFMiBca3hqWd84LRLHbuJD5quZcTbRbJEXiTaim/b8B8JZOT0PZyZqFL@NtPA@Voz273YQBJdwNzML25@qVLJMKuK8fTRTcTGtvJcplu1sOCXdosrPSRtZ5zimRnPADowdHq0iteoMtdoFsg29BLTXfsfiliQc/WyElR34kL0rZqw9EroZFo@01CRirTVPOjydSlxF9x4frW1qB0Tg5utxL8vJxYXjMmJSkjeT2wGyhDxOyXui5xdVtdIXTF9Cb3jIkxBMpLTe62ijUZQclFG4C8KM5cGrLGmgDgah8sYsToNhFvTWm2lBCbrIj7KJq3oMkrAngZ7/wOGcUnOTQ4824YEa3LnmSzFZM7ZSFIzwWRm@pLuatolTaLIaphfBF/ElMkzIMqKkxKnQyIgszv6CkO4GdIjEmVFR47ZagkHJR3I3XxqjqLd56Z2XySPAm52weJwznolZtSNTOR4UI4jD9WUB3V0VcUVvyHpEasrTHYuqnkN0TBNmDiTTWQWixDJ85PjqUv0cGLPEt1f "APL (Dyalog Unicode) – Try It Online")
~~Unfortunately, this doesn't work in TIO~~ dzaima (and Adám) got `⎕SE.Dyalog.Utils.repObj` working! Requires `⎕IO←0` now.
## Formatting the input
First `⎕R` is used to format the input. It accepts a bunch of regex on the left and the strings to replace them with on the right. In this case, we're replacing areas before atom names starting with digits (`(?<=\(|,) *(?=\d)`) or multiple spaces ( `+`) with a single underscore because in APL, identifiers cannot contain spaces or start with digits.
At the same time,  `*([(),]) *` captures parentheses or commas along with spaces around them, but only keeps the parentheses and commas, dropping leading or trailing spaces by doing so. Thus, `( QUOTE, (1, ATOM 2))` would become `(QUOTE,(_1,ATOM_2))`.
## Creating an AST
`p` creates an AST from this formatted string. Every atom is represented by a string, and every s-expression is simply an array of atoms or other s-expressions, with the string `NIL` at the end. Thus, `(QUOTE,(ATOM_1,ATOM_2))` would become `('QUOTE' ('ATOM_1' 'ATOM_2' 'NIL') 'NIL')`.
## Executing the AST
`e` takes such an AST as its right argument and evaluates it. The left argument is a context that gives the variables in scope. It's an array whose first elements is a list of strings denoting the names of atoms, while the second element is a list of the same length with those variables' values. For example, given a lisp expression `((LAMBDA, (X, Y), (CONS, Y, X)), (QUOTE, (ATOM 1)), (QUOTE, ATOM 2))`, the context would look like this (the `NIL`s are an unfortunate side effect of how the ASTs are structured, but they're harmless):
```
       'X'     |    'Y'   | 'NIL'
'ATOM_1' 'NIL' | 'ATOM_2' | 'NIL'
```
If the right argument to `e` is a single string (an atom), it looks up the atom in the context and gets back the corresponding value. If the atom is not found in the context, it just gives back the same string. So in the example above, if `⍵` (the right argument) were `X`, we would get back `ATOM_1`, but if it were `CAR`, we would get back `CAR` again.
Otherwise, it's a function call, so it calls `e` on the first element of that tree with the same context on the left. The first element of the AST is either a label name or one of the nine "builtin" functions, or a lambda expression. If it's the former, we'll just get back the name of the function again. In that case, we can execute the string with `⍎` (APL's equivalent of `eval`) to get another dyadic function. We give it the same context on the left and apply it to the rest of `⍵`, the right argument.
Otherwise, if it's a lambda expression, applying the function `LAMBDA` (the one I've defined) returns a string containing a function, so again, we can execute it and apply it to the rest of `⍵`.
The initial left argument is `⍬⍬` (`⍬` is an empty array), because we don't have any variables defined yet.
## Printing the result
`{1=≢⍵:⍵⋄1=≡⍵:'_'⎕R' '⊢⍵⋄⍕'('(∇¨¯1↓⍵)')'}` is a recursive function that turns arrays into strings. `1=≢⍵` checks if the argument is a string (with depth 1). If so, it turns underscores back into spaces with `'_'⎕R' '`. Otherwise, it drops the last element (always `NIL`) using `¯1↓⍵`, then calls itself on each element using `∇¨`. That is put into an array with parentheses, and `⍕` is used to turn that array into a string (with extra spaces).
### `LAMBDA`
This function returns a string representing another function. For example, `(LAMBDA, (X, Y), (CONS, X, Y))` becomes
```
{((('X' 'Y' 'NIL'),⊃⍺)((⍺∘e¨⍵),1⊃⍺))e'CONS' 'X' 'Y' 'NIL'}
```
While the definition of `LAMBDA` itself may look messy, there is nothing complicated about it. On the right is simply the body given to the lambda; only the context has changed. Like the Python answer, I used dynamic scoping, so the new context adds to the context given at the call site, not where the lambda is defined. The first element is just the names lambda's parameters prepended to the the old context's names. The second is the result of evaluating all the arguments (with the same context), prepended to the old context's values. `repObj` (assigned to `s` because it is used multiple times) finds the string representation of the parameters and lambda body.
### `LABEL`
This is why we had to add underscores before. `LABEL` constructs a string that looks like `#.name ← lambda`, given the arguments `name lambda 'NIL'`, executes it, adding a function called `name` to the root namespace `#`, so it is global. Like `LAMBDA`, it ignores the context given to it, because of dynamic scoping.
]