Маккарти 1959 LISP
В начале 1959 года Джон Маккарти написал новаторский документ, в котором определены всего девять примитивных функций, которые, будучи объединенными, все еще составляют основу для всех LISP-подобных языков сегодня. Документ доступен в цифровом виде здесь:
http://www-formal.stanford.edu/jmc/recursive.pdf
Ваша задача заключается в полной мере реализовать синтаксический анализатор и интерпретатор LISP Маккарти точно , как описано в работе 1960: То есть, функции QUOTE
, ATOM
, EQ
, CAR
, CDR
, CONS
, COND
, LAMBDA
, и LABEL
все должны быть функциональными. Этот документ будет иметь приоритет над этим контрольным текстом при рассмотрении правильности ответов, но я попытался суммировать девять функций ниже. Обратите внимание, что язык будет в ALL CAPS и проверка ошибок не требуется, все входные данные должны считаться действительными.
Типы
- В LISP Маккарти есть только два типа: атом и связанный список, который рекурсивно определяется как заголовок, который может быть списком или атомом, и список, к которому присоединена голова (хвост).
NIL
обладает особым свойством быть как атомом, так и списком. - Согласно статье, имена атомов будут состоять только из заглавных букв, цифр и символа пробела, хотя строки последовательных пробелов должны рассматриваться как один пробел, и все начальные и конечные пробелы должны быть удалены. Пример названия атомов (эквивалентно заменить подчеркивание с пробелом):
___ATOM__1__ = ATOM_1
. Пример не эквивалентных имен атомов:A_TOM_1 != ATOM_1
- Списки обозначаются круглыми скобками, и подразумевается,
NIL
что в конце каждого списка. Элементы в списке разделяются запятыми, а не пробелами, как в большинстве современных Лиспов. Так что список(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
(true), если два атома эквивалентны, илиNIL
(false), если они не являются. - Тестовые случаи:
(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 "если-еще". Принимает количество аргументов переменной длины, каждый из которых должен быть точно равным списку длины 2. Для каждого списка аргументов по порядку оцените первый член и, если он истинный (T), верните связанный второй член и выйдите из функции , Если первый член неверен, переходите к следующему аргументу, проверяйте его условие и т. Д., Пока не будет достигнуто первое истинное условие. Можно предположить, что хотя бы одно из условий аргумента является истинным - если они все ложные, это неопределенное поведение. См. Стр. 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 для выполнения этой задачи, но Маккарти не знал об этом методе при написании оригинальной статьи. Это делает программы намного легче писать в любом случае. - Тестовые случаи:
(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
функцию выше, она может быть представлена в виде этого 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:])
ЗАКЛЮЧИТЕЛЬНОЕ ИСПЫТАНИЕ:
Если я расшифровал его правильно, ваш переводчик должен иметь возможность интерпретировать 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, кажется, что на его компьютере не хватает персонажей:
Если бы на компьютере было больше символов, это можно было бы значительно улучшить ...
Таким образом, эта задача помечена как code-golf, и самый короткий ответ в символах будет победителем. Применяются стандартные лазейки. Удачи!
Примечание к String Evals : я понимаю, что некоторые думают, что можно выиграть эту задачу, используя Lisp и изменив синтаксис, чтобы он соответствовал языку хоста, а затем используя строку (eval)
. Я не особенно убежден, что этот подход обязательно победит, особенно с правилами именования идентификаторов, и даже если бы я это сделал, я думаю, что запрет строки eval
s на всех языках был бы субъективным и скользким шагом. Но я не хочу наказывать людей за то, что они выполнили этот вызов «правильным» способом, поэтому я могу разрешить двум победителям этого конкурса, один на языке, похожем на Лисп, и один на языке, отличном от Лиспи, если это станет проблемой. ,
источник
((LAMBDA, (ATOM 1), (EQ, ATOM 1, (QUOTE, NIL))), (QUOTE, NIL)) -> NIL
Где(QUOTE NIL)
в конце ввод, так что это должно вернутьсяT
?-> NIL
CONS
вы говорите: «Добавляет первый аргумент ко второму аргументу и возвращает вновь созданный список», но в тестовых примерах второй аргумент добавляется к первому. Что правильно?Ответы:
Python 3, 770 байт
Это ответ на стандартный ввод / вывод. Ожидается, что каждая строка будет полным или пустым.
eval
используется для сокращения реализации, но в противном случае не требуется для логики.источник
SUBST
пример все еще не работает (насколько мне известно) в качестве теста. Один изCOND
s достигает конца, прежде чем найтиT
.EVAL
(так приятно удивленный, что я получил это право с первой попытки!) Я собираюсь наградить вас за вознаграждение и принятый ответ сейчас!R(E(P(l)
установку ;-)repr
, E =eval
, P =parse
, l =line
.