매카시의 1959 LISP

1959 년 초, John McCarthy는 9 개의 기본 기능을 정의한 획기적인 논문을 작성했습니다. 이 논문은 여기에 디지털화되어 있습니다 :

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

즉, 기능 : 당신의 임무는 완전히 정확히으로 1960 년 논문에서 설명 맥카시의 LISP에 대한 파서와 인터프리터 구현하는 것입니다 QUOTE, ATOM, EQ, CAR, CDR, CONS, COND, LAMBDA, 및 LABEL모든 기능을해야합니다. 답의 정확성을 고려할 때이 챌린지 텍스트보다 논문이 우선하지만, 아래 9 가지 기능을 요약하려고했습니다. 언어는 모든 대문자로 표시되며 오류 검사가 필요하지 않으며 모든 입력이 유효한 것으로 간주해야합니다.

종류

• McCarthy의 LISP에는 두 가지 유형 만 있습니다 : 원자 및 링크 된 목록. 목록 또는 원자 일 수있는 헤드로 재귀 적으로 정의되는 링크 된 목록과 헤드가 첨부 된 목록 (꼬리). NIL원자와리스트라는 특별한 특성을 가지고 있습니다.
• 논문에 따라 원자 이름은 대문자, 숫자 및 공백 문자로만 구성되지만 연속 공백 문자열은 하나의 공백으로 간주하고 모든 앞뒤 공백 문자를 제거해야합니다. 동등한 원자 이름 예 (공백 문자로 밑줄을 대체) : ___ATOM__1__ = ATOM_1. 동등한 원자 이름이 아닌 예 :A_TOM_1 != ATOM_1
• 목록은 괄호로 표시되며 NIL모든 목록의 끝에 묵시적 입니다. 목록의 요소는 대부분의 현대 Lisp에서와 같이 공백이 아닌 쉼표로 구분됩니다 . 따라서 목록 (ATOM 1, (ATOM 2))은입니다 {[ATOM 1] -> {[ATOM 2] -> NIL} -> NIL}.

QUOTE:

• 원자 (단일 요소) 또는 연결된 목록 일 수있는 하나의 인수를 취합니다. 인수를 정확하게 돌려줍니다.
• 테스트 사례 :
• (QUOTE, ATOM 1) -> ATOM 1
• (QUOTE, (ATOM 1, ATOM 2)) -> (ATOM 1, ATOM 2)

ATOM:

• 원자 (단일 요소) 또는 연결된 목록 일 수있는 하나의 인수를 취합니다. T인수가 원자 인 경우 (true) 또는 NIL인수가 원자가 아닌 경우 (false)를 리턴 합니다 .
• 테스트 사례 :
• (ATOM, (QUOTE, ATOM 1)) -> T
• (ATOM, (QUOTE, (ATOM 1, ATOM 2))) -> NIL

EQ:

• 원자 여야하는 두 개의 인수를 취합니다 (두 인수 중 하나가 원자가 아닌 경우 동작이 정의되지 않음). 반환 T두 원자는 동등, 또는 경우 (참) NIL그렇지 않은 경우 (거짓).
• 테스트 사례 :
• (EQ, (QUOTE, ATOM 1), (QUOTE, ATOM 1)) -> T
• (EQ, (QUOTE, ATOM 1), (QUOTE, ATOM 2)) -> NIL

CAR:

• 목록이어야하는 하나의 인수를 취합니다 (목록이 아닌 경우 동작은 정의되지 않음). 해당 목록의 첫 번째 아톰 (헤드)을 반환합니다.
• 테스트 사례 :
• (CAR, (QUOTE, (ATOM 1, ATOM 2))) -> ATOM 1

CDR:

• 목록이어야하는 하나의 인수를 취합니다 (목록이 아닌 경우 동작은 정의되지 않음). 목록의 첫 번째 원자, 즉 꼬리를 제외한 모든 원자를 반환합니다. 모든 목록은 묵시적으로 끝나 NIL므로 CDR한 요소 만있는 것으로 보이는 목록에서 실행 하면 반환 NIL됩니다.
• 테스트 사례 :
• (CDR, (QUOTE, (ATOM 1, ATOM 2))) -> (ATOM 2)
• (CDR, (QUOTE, (ATOM 1))) -> NIL

CONS:

• 두 가지 주장을 취합니다. 첫 번째는 원자 또는 목록 일 수 있지만 두 번째는 목록 또는이어야합니다 NIL. 첫 번째 인수를 두 번째 인수 앞에 추가하고 새로 만든 목록을 반환합니다.
• 테스트 사례 :
• (CONS, (QUOTE, ATOM 1), (QUOTE, NIL)) -> (ATOM 1)
• (CONS, (QUOTE, ATOM 1), (CONS, (QUOTE, ATOM 2), (QUOTE, NIL))) -> (ATOM 1, ATOM 2)

COND:

• 이것은 LISP의 “if-else”종류의 진술입니다. 가변 길이의 인수를 취합니다. 각 인수의 길이는 정확히 2 여야합니다. 각 인수 목록에 대해 첫 번째 항을 평가하고 참인 경우 (T) 연관된 두 번째 항을 리턴하고 함수를 종료하십시오. . 첫 번째 항이 참이 아닌 경우 다음 인수로 이동하여 첫 번째 참 조건에 도달 할 때까지 조건을 테스트합니다. 인수 조건 중 하나 이상이 true 인 것으로 가정 할 수 있습니다. 모두 false 인 경우 정의되지 않은 동작입니다. 이 기능의 동작에 대한 좋은 예는 4 페이지를 참조하십시오.
• 테스트 사례 :
• (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:

• 익명 함수를 정의합니다. 첫 번째는 함수에 대한 인수를 나타내는 원자 목록이고 두 번째는 일반적으로 인수를 사용하는 S- 표현식 (함수 본문) 인 두 개의 인수를 취합니다.
• 테스트 사례 :
• 익명의 “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:

• 익명 LAMBDA함수에 이름을 지정 하면 해당 함수를의 본문에서 재귀 적으로 호출 할 수 있습니다 LAMBDA. 두 번째 인수를 사용합니다. 첫 번째는 레이블이고 두 ​​번째 LAMBDA는 레이블을 바인딩 할 함수입니다. 제공된 이름을 반환합니다. 모든 LABEL이름 의 범위 는 전역 적이며 재정의 LABEL는 정의되지 않은 동작입니다.
• 재미있는 사실 LABEL은 실제로 우리 LAMBDA가 ‘Y-Combinator’ 와 함께 사용 하여이 작업을 수행 할 수 있다는 것을 알기 때문에 재귀 함수를 만드는 데 실제로 필요 하지는 않지만 McCarthy는 원본 논문을 작성할 때이 방법을 알지 못했습니다. 어쨌든 프로그램을 훨씬 쉽게 작성할 수 있습니다.
• 테스트 사례 :
• (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
• (위를 실행 한 후) (SUBST, (QUOTE, A), (QUOTE, B), (QUOTE, (A, B, C))) -> (A, A, C)

SUBST위 의 함수를 시각화하기 위해 다음과 같은 파이썬 유사 의사 코드로 표현할 수 있습니다.

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

최종 테스트 사례 :

올바르게 번역 한 경우 통역사 EVAL가이 코드 로 해석 할 수 있어야 합니다.

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

해당 행을 실행 한 후이 줄은 다음을 반환해야합니다 (A, B, C).

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

그러나 16 페이지의 John McCarthy 자신을 인용하면 컴퓨터에 문자가 부족한 것 같습니다.

컴퓨터에서 더 많은 문자를 사용할 수 있다면 상당히 향상 될 수 있습니다 …

따라서이 도전 과제에는 코드 골프 라는 태그가 붙어 있으며 가장 짧은 문자가 승자가됩니다. 표준 허점이 적용됩니다. 행운을 빕니다!

문자열 평가에 대한 참고 사항 : 일부는 Lisp를 사용하고 호스트 언어에 맞게 구문을 수정 한 다음 문자열을 사용하여이 문제를 해결할 수 있다고 생각합니다 (eval). 나는이 접근법이 특히 식별자 이름 지정 규칙으로 반드시 승리 할 것이라고 확신하지는 못하지만 eval모든 언어에서 문자열 s 금지 는 주관적이고 미끄러운 기울기 라고 생각합니다 . 그러나 나는이 도전을 ‘올바른’방법으로 행한 사람들을 처벌하고 싶지 않기 때문에,이 도전에 대해 두 명의 우승자를 허용 할 수 있습니다. .

답변

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