McCarthy's 1959 LISP
No início de 1959, John McCarthy escreveu um artigo inovador definindo apenas nove funções primitivas que, quando reunidas, formam a base de todas as linguagens semelhantes ao LISP atualmente. O documento está disponível digitalizado aqui:
http://www-formal.stanford.edu/jmc/recursive.pdf
Seu trabalho é implementar plenamente um analisador e intérprete para LISP de McCarthy exatamente como descrito no documento 1960: Ou seja, as funções QUOTE
, ATOM
, EQ
, CAR
, CDR
, CONS
, COND
, LAMBDA
, e LABEL
todos devem ser funcional. O artigo terá precedência sobre este texto de desafio ao considerar a exatidão das respostas, mas tentei resumir as nove funções abaixo. Observe que o idioma estará em ALL CAPS e nenhuma verificação de erro é necessária; todas as entradas devem ser consideradas válidas.
Tipos
- Existem apenas dois tipos no LISP de McCarthy: um átomo e uma lista vinculada, definida recursivamente como uma cabeça, que pode ser uma lista ou um átomo, e uma lista à qual a cabeça está anexada (cauda).
NIL
tem a propriedade especial de ser um átomo e uma lista. - De acordo com o artigo, os nomes dos átomos consistirão apenas de letras maiúsculas, números e caracteres de espaço, embora as sequências de espaços consecutivos devam ser consideradas apenas um espaço e todos os caracteres de espaço à esquerda e à direita sejam removidos. Exemplo nomes átomo equivalente (sublinhado substituir com carácter de espaço):
___ATOM__1__ = ATOM_1
. Exemplo de nomes de átomos não equivalentes:A_TOM_1 != ATOM_1
- As listas são indicadas por parênteses, e um implícito
NIL
está no final de cada lista. Os elementos de uma lista são separados por vírgulas e não em espaço em branco, como na maioria dos Lisps modernos. Então a lista(ATOM 1, (ATOM 2))
seria{[ATOM 1] -> {[ATOM 2] -> NIL} -> NIL}
.
QUOTE
:
- Adota um argumento que pode ser um átomo (elemento único) ou uma lista vinculada. Retorna o argumento exatamente.
- Casos de teste:
(QUOTE, ATOM 1) -> ATOM 1
(QUOTE, (ATOM 1, ATOM 2)) -> (ATOM 1, ATOM 2)
ATOM
:
- Adota um argumento que pode ser um átomo (elemento único) ou uma lista vinculada. Retorna
T
(true) se o argumento for um átomo ouNIL
(false) se o argumento não for um átomo. - Casos de teste:
(ATOM, (QUOTE, ATOM 1)) -> T
(ATOM, (QUOTE, (ATOM 1, ATOM 2))) -> NIL
EQ
:
- Aceita dois argumentos que devem ser átomos (o comportamento é indefinido se um dos argumentos não for átomos). Retorna
T
(true) se os dois átomos são equivalentes ouNIL
(false) se não forem. - Casos de teste:
(EQ, (QUOTE, ATOM 1), (QUOTE, ATOM 1)) -> T
(EQ, (QUOTE, ATOM 1), (QUOTE, ATOM 2)) -> NIL
CAR
:
- Aceita um argumento que deve ser uma lista (o comportamento é indefinido se não for uma lista). Retorna o primeiro átomo (cabeça) dessa lista.
- Casos de teste:
(CAR, (QUOTE, (ATOM 1, ATOM 2))) -> ATOM 1
CDR
:
- Aceita um argumento que deve ser uma lista (o comportamento é indefinido se não for uma lista). Retorna todos os átomos, exceto o primeiro átomo da lista, ou seja, a cauda. Observe que toda lista termina de forma implícita
NIL
; portanto, a execuçãoCDR
em uma lista que parece ter apenas um elemento retornaráNIL
. - Casos de teste:
(CDR, (QUOTE, (ATOM 1, ATOM 2))) -> (ATOM 2)
(CDR, (QUOTE, (ATOM 1))) -> NIL
CONS
:
- Leva dois argumentos. O primeiro pode ser um átomo ou uma lista, mas o segundo deve ser uma lista ou
NIL
. Anexa o primeiro argumento ao segundo argumento e retorna a lista recém-criada. - Casos de teste:
(CONS, (QUOTE, ATOM 1), (QUOTE, NIL)) -> (ATOM 1)
(CONS, (QUOTE, ATOM 1), (CONS, (QUOTE, ATOM 2), (QUOTE, NIL))) -> (ATOM 1, ATOM 2)
COND
:
- Esta é a declaração "if-else" do LISP. Leva uma quantidade variável de argumentos, cada um dos quais deve ser exatamente uma lista de comprimento 2. Para cada lista de argumentos em ordem, avalie o primeiro termo e, se for verdadeiro (T), retorne o segundo termo associado e saia da função . Se o primeiro termo não for verdadeiro, passe para o próximo argumento e teste sua condição, e assim sucessivamente até que a primeira condição verdadeira seja atingida. Pelo menos uma das condições do argumento pode ser considerada verdadeira - se todas forem falsas, esse é um comportamento indefinido. Veja a página 4 para um bom exemplo do comportamento desta função.
- Casos de teste:
(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 uma função anônima. Leva dois argumentos, o primeiro sendo uma lista de átomos que representam os argumentos para a função e o segundo sendo qualquer expressão S (o corpo da função), que normalmente usaria os argumentos.
- Casos de teste:
- Definindo e usando uma função 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
:
- Atribui um nome a uma
LAMBDA
função anônima , que também permite que essa função seja chamada recursivamente no corpo doLAMBDA
. Leva dois argumentos, o primeiro sendo um rótulo e o segundo aLAMBDA
função à qual o rótulo deve estar vinculado. Retorna o nome fornecido. O escopo de todos osLABEL
nomes é global e a redefinição de umLABEL
é um comportamento indefinido. - De fato,
LABEL
não é realmente necessário criar funções recursivas, como sabemos agora queLAMBDA
podem ser usadas com um 'Y-Combinator' para realizar essa tarefa, mas McCarthy não estava ciente desse método ao escrever o artigo original. Torna os programas muito mais fáceis de escrever de qualquer maneira. - Casos de teste:
(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
- (depois de executar o acima)
(SUBST, (QUOTE, A), (QUOTE, B), (QUOTE, (A, B, C))) -> (A, A, C)
Para ajudar a visualizar a SUBST
função acima, ela pode ser representada como este pseudocódigo do tipo 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 TESTE FINAL:
Se eu a transcrevi corretamente, seu intérprete deve ser capaz de interpretar EVAL
com 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))))))
Depois de executar esse gigante, essa linha deve retornar (A, B, C)
:
(EVAL, (QUOTE, (CONS, X, (QUOTE, (B, C)))), (QUOTE, ((X, A), (Y, B))))
No entanto, para citar o próprio John McCarthy na página 16, parece que ele estava ficando sem caracteres no computador:
Se houver mais caracteres disponíveis no computador, ele poderá ser melhorado consideravelmente ...
Portanto, esse desafio é marcado como code-golf e a resposta mais curta em caracteres será o vencedor. Aplicam-se brechas padrão. Boa sorte!
Nota sobre as avaliações de strings : Entendo que alguns acham que pode ser possível vencer esse desafio usando um Lisp e modificando a sintaxe para ajustar-se ao idioma do host e, em seguida, usando uma string (eval)
. Não estou particularmente convencido de que essa abordagem necessariamente vença, especialmente com as regras de nomeação de identificadores, e mesmo que eu ache que proibir cadeias de caracteres eval
em todas as línguas seria uma inclinação subjetiva e escorregadia. Mas eu não quero punir as pessoas por fazerem esse desafio da maneira 'certa', por isso posso permitir dois vencedores para esse desafio, um em uma linguagem semelhante ao Lisp e outro em uma linguagem não Lispy, se isso se tornar um problema .
fonte
((LAMBDA, (ATOM 1), (EQ, ATOM 1, (QUOTE, NIL))), (QUOTE, NIL)) -> NIL
Onde(QUOTE NIL)
no final está a entrada, então isso deve retornarT
?-> NIL
CONS
você diz "Anexa o primeiro argumento ao segundo argumento e retorna a lista recém-criada", mas os casos de teste mostram o segundo argumento sendo anexado ao primeiro. Qual é correto?Respostas:
Python 3, 770 bytes
Este é um REPL no stdin / stdout. Espera que cada linha seja uma declaração completa ou vazia.
eval
é usado para reduzir a implementação, mas, caso contrário, não é necessário para a lógica.fonte
SUBST
exemplo ainda está quebrado (que eu saiba) como uma caixa de teste. Um dosCOND
s chega ao fim antes de encontrar aT
.EVAL
(tão agradavelmente surpreso que eu tenha acertado aquele na primeira tentativa!). Vou premiar você com a recompensa e a resposta aceita agora!R(E(P(l)
configuração ;-)repr
, E =eval
, P =parse
, l =line
.