LISP de McCarthy en 1959

A principios de 1959, John McCarthy escribió un documento innovador que define solo nueve funciones primitivas que, cuando se combinan, todavía forman la base de todos los lenguajes similares a LISP en la actualidad. El documento está disponible digitalizado aquí:

http://www-formal.stanford.edu/jmc/recursive.pdf

Su trabajo consiste en aplicar plenamente un programa de análisis e intérprete de LISP de McCarthy exactamente como se describe en el documento de 1960: Es decir, las funciones QUOTE, ATOM, EQ, CAR, CDR, CONS, COND, LAMBDA, y LABELtodos deben ser funcionales. El documento tendrá prioridad sobre este texto de desafío al considerar la exactitud de las respuestas, pero he tratado de resumir las nueve funciones a continuación. Tenga en cuenta que el idioma estará en TODAS LAS MAYÚSCULAS y no es necesaria la comprobación de errores, se debe suponer que toda la entrada es válida.

Tipos

• Solo hay dos tipos en el LISP de McCarthy: un átomo y una lista vinculada, que se define de forma recursiva como una cabeza, que puede ser una lista o un átomo, y una lista a la que se une la cabeza (cola). NILtiene la propiedad especial de ser tanto un átomo como una lista.
• Según el documento, los nombres de los átomos solo consistirán en letras mayúsculas, números y el carácter de espacio, aunque las cadenas de espacios consecutivos deben considerarse como un solo espacio y todos los caracteres de espacio iniciales y finales deben eliminarse. Ejemplo nombres átomo equivalente (reemplazar subrayado con carácter de espacio): ___ATOM__1__ = ATOM_1. Ejemplo de nombres de átomos no equivalentes:A_TOM_1 != ATOM_1
• Las listas se indican entre paréntesis, y una implícita se NILencuentra al final de cada lista. Los elementos en una lista están separados por comas y no espacios en blanco como en la mayoría de los Lisps modernos. Entonces la lista (ATOM 1, (ATOM 2))sería {[ATOM 1] -> {[ATOM 2] -> NIL} -> NIL}.

QUOTE:

• Toma un argumento que puede ser un átomo (elemento único) o una lista vinculada. Devuelve el argumento exactamente.
• Casos de prueba:
• (QUOTE, ATOM 1) -> ATOM 1
• (QUOTE, (ATOM 1, ATOM 2)) -> (ATOM 1, ATOM 2)

ATOM:

• Toma un argumento que puede ser un átomo (elemento único) o una lista vinculada. Devuelve T(verdadero) si el argumento es un átomo, o NIL(falso) si el argumento no es un átomo.
• Casos de prueba:
• (ATOM, (QUOTE, ATOM 1)) -> T
• (ATOM, (QUOTE, (ATOM 1, ATOM 2))) -> NIL

EQ:

• Toma dos argumentos que deben ser átomos (el comportamiento no está definido si alguno de los argumentos no son átomos). Devuelve T(verdadero) si los dos átomos son equivalentes, o NIL(falso) si no lo son.
• Casos de prueba:
• (EQ, (QUOTE, ATOM 1), (QUOTE, ATOM 1)) -> T
• (EQ, (QUOTE, ATOM 1), (QUOTE, ATOM 2)) -> NIL

CAR:

• Toma un argumento que debe ser una lista (el comportamiento no está definido si no es una lista). Devuelve el primer átomo (cabeza) de esa lista.
• Casos de prueba:
• (CAR, (QUOTE, (ATOM 1, ATOM 2))) -> ATOM 1

CDR:

• Toma un argumento que debe ser una lista (el comportamiento no está definido si no es una lista). Devuelve cada átomo excepto el primer átomo de la lista, es decir, la cola. Tenga en cuenta que cada lista termina de manera implícita NIL, por lo que se ejecutará CDRen una lista que parece tener solo un elemento NIL.
• Casos de prueba:
• (CDR, (QUOTE, (ATOM 1, ATOM 2))) -> (ATOM 2)
• (CDR, (QUOTE, (ATOM 1))) -> NIL

CONS:

• Toma dos argumentos. El primero puede ser un átomo o una lista, pero el segundo debe ser una lista o NIL. Antepone el primer argumento al segundo argumento y devuelve la lista recién creada.
• Casos de prueba:
• (CONS, (QUOTE, ATOM 1), (QUOTE, NIL)) -> (ATOM 1)
• (CONS, (QUOTE, ATOM 1), (CONS, (QUOTE, ATOM 2), (QUOTE, NIL))) -> (ATOM 1, ATOM 2)

COND:

• Esta es la declaración de tipo "si no" de LISP. Toma una cantidad de argumentos de longitud variable, cada uno de los cuales debe ser una lista de longitud exactamente 2. Para cada lista de argumentos en orden, evalúe el primer término y, si es verdadero (T), devuelva el segundo término asociado y salga de la función . Si el primer término no es verdadero, pase al siguiente argumento y pruebe su condición, y así sucesivamente hasta que se alcance la primera condición verdadera. Se puede suponer que al menos una de las condiciones del argumento es verdadera: si todas son falsas, este es un comportamiento indefinido. Consulte la página 4 para ver un buen ejemplo del comportamiento de esta función.
• Casos de prueba:
• (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:

• Define una función anónima. Toma dos argumentos, el primero es una lista de átomos que representan los argumentos de la función y el segundo es cualquier expresión S (el cuerpo de la función), que normalmente usaría los argumentos.
• Casos de prueba:
• Definición y uso de una función anónima "isNull":
• ((LAMBDA, (ATOM 1), (EQ, ATOM 1, (QUOTE, NIL))), (QUOTE, NIL)) -> T
• ((LAMBDA, (ATOM 1), (EQ, ATOM 1, (QUOTE, NIL))), (QUOTE, ATOM 1)) -> NIL

LABEL:

• Da un nombre a una LAMBDAfunción anónima , que también permite que esa función se llame de forma recursiva en el cuerpo de LAMBDA. Toma dos argumentos, el primero es una etiqueta y el segundo es la LAMBDAfunción a la que debe vincularse la etiqueta. Devuelve el nombre proporcionado. El alcance de todos los LABELnombres es global, y redefinir a LABELes un comportamiento indefinido.
• Dato curioso, en LABELrealidad no es necesario crear funciones recursivas, ya que ahora sabemos que LAMBDAse puede usar con un 'Combinador en Y' para realizar esta tarea, pero McCarthy no conocía este método al escribir el documento original. De todos modos, hace que los programas sean mucho más fáciles de escribir.
• Casos de prueba:
• (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
• (después de ejecutar lo anterior) (SUBST, (QUOTE, A), (QUOTE, B), (QUOTE, (A, B, C))) -> (A, A, C)

Para ayudar a visualizar la SUBSTfunción anterior, podría representarse como este pseudocódigo similar a Python:

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:])

CASO DE PRUEBA FINAL:

Si lo he transcrito correctamente, su intérprete debería poder interpretar EVALcon este código:

(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))))))

Después de ejecutar ese gigante, esta línea debería volver (A, B, C):

(EVAL, (QUOTE, (CONS, X, (QUOTE, (B, C)))), (QUOTE, ((X, A), (Y, B))))

Sin embargo, para citar al propio John McCarthy en la página 16, parece que se estaba quedando sin personajes en su computadora:

Si hubiera más caracteres disponibles en la computadora, podría mejorarse considerablemente ...

Por lo tanto, este desafío está etiquetado como code-golf y la respuesta más corta en caracteres será la ganadora. Se aplican lagunas estándar. ¡Buena suerte!

Nota sobre Evaluaciones de cadena : Entiendo que algunos piensan que puede ser posible ganar este desafío usando un Lisp y modificando la sintaxis para que se ajuste al idioma del host y luego usando una cadena (eval). No estoy particularmente convencido de que este enfoque necesariamente gane, especialmente con las reglas de denominación de identificadores, e incluso si lo hiciera, creo que prohibir las cadenas evalen todos los idiomas sería una pendiente subjetiva y resbaladiza. Pero no quiero castigar a las personas por hacer este desafío de la manera "correcta", por lo que puedo permitir a dos ganadores para este desafío, uno en un lenguaje similar a Lisp y otro en un idioma que no sea Lispy, si esto se convierte en un problema .

Python 3, 770 bytes

Este es un REPL en stdin / stdout. Espera que cada línea sea una declaración completa o vacía. evalse usa para acortar la implementación, pero por lo demás no es necesario para la lógica.

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)))