Aval Kay's Eval/ Применить момент Эйнштейна
Алан Кей сказал, что внимательное изучение кода и поиск единственной ошибки в коде на странице 13 руководства по Lisp 1.5 помогли ему понять компьютерные науки в 100 раз лучше.
Данный код является первым выпуском eval & apply что-то отдаленно похожее на современный шутник (о котором я знаю).
Так как правильный ответ, вероятно, известен, но потерян (мой Google-фу приличный, и я искал не менее 20 минут), я присуждаю 1-й правильный ответ (я буду смотреть на время редактирования, поэтому не пытайтесь обманывать) вознаграждение в 250 баллов как можно скорее.
Я бы посоветовал другим также внести свой вклад в вознаграждение, помните из видео выше, Алан Кей сказал, что этот материал напоминает об окружающей среде, в которой находился Эйнштейн, когда он открыл Теорию Относительности.
Код в тексте написан в M-Expressions. Я работаю над переводчиком для перевода из M-выражений в S-выражения (код lisp) @ https://github.com/Viruliant/MccarthyMCEval-1.5.
В любом случае вот переведенная цитата со страницы 13:
;______________________________________Lisp Meta-Circular Evaluator S-Expression
;this code is written in the order it appears on pages 10-13 in the Lisp 1.5 Manual
;and is translated from the m-expressions into s-expressions
(label mc.equal (lambda (x y)
(mc.cond
((atom x) ((mc.cond ((atom y) (eq x y)) ((quote t) (quote f)))))
((equal (car x)(car y)) (equal (cdr x) (cdr y)))
((quote t) (quote f)))))
(label mc.subst (lambda (x y z)
(mc.cond
((equal y z) (x))
((atom z) (z))
((quote t) (cons (subst x y (car z))(subst x y (cdr z)))))))
(label mc.append (lambda (x y)
(mc.cond
((null x) (y))
((quote t) (cons (car x)) (append (cdr x) y)))))
(label mc.member (lambda (x y)
(mc.cond ((null y) (quote f))
((equal x (car y)) (quote t))
((quote t) (member x (cdr y))))))
(label mc.pairlis (lambda (x y a)
(mc.cond ((null x) (a)) ((quote t) (cons (cons (car x)(car y))
(pairlis (cdr x)(cdr y) a)))))
(label mc.assoc (lambda (x a)
(mc.cond ((equal (caar a) x) (car a)) ((quote t) (assoc x (cdr a))))))
(label mc.sub2 (lambda (a z)
(mc.cond ((null a) (z)) (((eq (caar a) z)) (cdar a)) ((quote t) (
sub2 (cdr a) z)))))
(label mc.sublis (lambda (a y)
(mc.cond ((atom y) (sub2 a y)) ((quote t) (cons (sublis a (car y))))
(sublis a (cdr y)))))
(label mc.evalquote (lambda (fn x)
(apply fn x nil)))
(label mc.apply (lambda (fn x a)
(mc.cond ((atom fn) (
(mc.cond
((eq fn car) (caar x))
((eq fn cdr) (cdar x))
((eq fn cons) (cons (car x)(cadr x)))
((eq fn atom) (atom (car x)))
((eq fn eq) (eq (car x)(cadr x)))
((quote t) (apply (eval (fn a)x a))))))
((eq (car fn) lambda) (eval (caddr fn) (parlis (cadr fn) x a)))
((eq (car fn) label) (apply (caddr (fn)x cons (cons (cadr (fn)))
(caddr fn))a)))))
(label mc.eval (lambda (e a)
(mc.cond
((atom e) (cdr (assoc e a)))
((atom (car e)) (mc.cond
((eq (car e) quote) (cadr e))
((eq (car e) cond) (evcon (cdr e) a))
((quote t) (apply (car e) (evlis (cdr e) a) a))))
((quote t) (apply (car e) (evlis (cdr e) a) a))))))
(label mc.evcon (lambda (c a)
(mc.cond
((eval (caar c) a) (eval (cadar c) a))
((quote t) (evcon (cdr c) a)))))
(label mc.evlis (lambda (m a)
(mc.cond
((null m) (nil))
((quote t) (cons (eval (car m) a) (evlis (cdr m) a)))))))
4 ответа
Есть две разные проблемы:
Первое: динамическое связывание как ошибка
Не уверен, что он имеет в виду, но, как правило, в Маккарти EVAL использование dynamic binding можно рассматривать как ошибку. Он не реализует лексическую область видимости для переменных. Ошибка обнаруживается, например, здесь:
http://www-formal.stanford.edu/jmc/recursive/node3.html
Смотрите функции maplist а также diff, Оба используют x, Это не будет работать, как показано, так как ранний Лисп обеспечивает динамическое связывание.
Более простой пример, который показывает, что оценщик использует динамическое связывание
Обратите внимание на использование eval., какой eval от Маккарти.
CL-USER 36 > (eval. '((lambda (f)
((lambda (x) (f))
'foo))
'(lambda () x))
nil)
Это возвращает FOO, поскольку значение X отрывается от динамического связывания.
Если мы посмотрим на код, он требует, чтобы мы передали функцию в виде списка: '(lambda () x)), Это оценивает список. Позже список будет вызываться через (f) - без аргументов. Список тогда интерпретируется как лямбда-выражение и x будет решена путем просмотра текущей динамической привязки для x, Существует обязательное x в FOO представлен ((lambda (x) (f)) 'foo), Это будет использовано тогда.
В реализации Lisp 1.5 из 60-х можно написать что-то похожее на:
((lambda (f)
((lambda (x) (f))
'foo))
(function (lambda () x)))
Обратите внимание, что (function (lambda () x)) оценивает список маркера, динамического окружения и функции. К сожалению, реализация Lisp 1.5 все еще использует динамическое связывание. Так что это было уже правильное направление, но ошибка не была исправлена. Улучшена ситуация, когда кто-то передавал функции другим функциям в качестве аргументов.
Проблема FUNARG
В течение 60-х - начала 70-х годов потребовалось некоторое время, чтобы понять эту проблему. Это было известно как проблема FUNARG. См., Например, статью Джоэля Мозеса: "Функция FUNCTION в LISP" или "Почему проблему FUNARG следует называть проблемой окружающей среды". Существовали различные решения для создания замыканий и использования лексического связывания. Часто интерпретатор использует динамическое связывание, а компилятор использует лексическое связывание. В мире Lisp это было в основном решено в Scheme, который по умолчанию ввел лексическое связывание. Это лексическое связывание позволяет, например, использовать замыкания для эмуляции объектных систем (что Кей, вероятно, сочтет полезным). См. Статью " Схема: интерпретатор расширенного лямбда-исчисления" с 1975 года.
В Common Lisp, который по умолчанию использует лексическую область видимости, как в диалектной схеме Lisp, приведенный выше пример будет ошибкой (здесь мы используем eval из Common Lisp, с немного измененным кодом, чтобы сделать его легальным кодом Common Lisp):
CL-USER 43 > (eval '((lambda (f)
((lambda (x) (funcall f))
'foo))
(function (lambda () x))))
Error: The variable X is unbound.
Как вы можете видеть в Common Lisp (и Схеме), (lambda () x) является настоящим лямбда-выражением, а не списком в кавычках и (function (lambda () x)) оценивает функциональный объект - если есть привязки, то это замыкание - функциональный объект и его привязки. Эта функция объекта / clojure передается, а затем вызывается через (funcall f), Так как x не ссылается ни на что (это свободная переменная) и не просматривается с помощью привязок; при выполнении кода возникает ошибка. Это то, что мы хотим: мы хотим лексическое связывание, и эта ошибка в нашем коде является следствием. То, что эта ошибка не происходит в оригинальном Лиспе Маккарти, является одним из результатов ошибки. Исправление этой ошибки (на полное удовлетворение которой ушло более десяти лет) позволяет нам использовать замыкания в Лиспе - как в Common Lisp, который извлек это из Схемы.
Вероятно, Кей также рассматривал динамическое связывание как ошибку. Это очень фундаментальная проблема, и понимание / решение ее помогло спроектировать и разработать лучшие языки программирования.
Обратите внимание, что типичные ранние реализации Smalltalk (пример Xerox Smalltalk 80) также использовали динамическое связывание.
Маккарти об этой ошибке
В " От LISP 1 до LISP 1.5" (1979) Маккарти пишет (выделено мной жирным шрифтом):
д. Свободные переменные. При всей своей невиновности Джеймс Р. Слэйгл запрограммировал следующее определение функции LISP и пожаловался, что он работает неправильно:
Цель функции - найти подвыражение x, удовлетворяющее p[x], и вернуть f[x]. Если поиск неудачен, то должна быть рассчитана функция продолжения u[] без аргументов и возвращено ее значение. Сложность заключалась в том, что когда происходила внутренняя рекурсия, значение car[x] хотел было внешним значением, но фактически использовалось внутреннее значение. В современной терминологии лексическое определение объема было востребовано, и динамическое определение объема было получено.
Я должен признаться, что я расценил эту трудность как просто ошибку и выразил уверенность, что Стив Рассел скоро исправит это. Он все исправил, но изобрел так называемое устройство FUNARG, которое приняло лексическую среду вместе с функциональным аргументом. Подобные трудности позже проявились в Алголе 60, и Рассел оказался одним из наиболее комплексных решений проблемы. Хотя в интерпретаторе это работало хорошо, в скомпилированном коде, похоже, противоречат полноте и скорости, и это приводит к череде компромиссов. К сожалению, время не позволило написать приложение, содержащее историю проблемы, и заинтересованного читателя называют (Moses 1970) как место для начала. (Дэвид Парк говорит мне, что Патрик Фишер также приложил руку к разработке устройства FUNARG).
Это не связано со второй проблемой:
Второе: ошибки в другой версии EVAL в той же книге
См. " The Roots of Lisp" Пола Грэма для обсуждения ошибки в определении EVAL позже в книге. На странице 12 вы найдете описание ошибки в коде Маккарти, которая вызывает двойную оценку аргументов для именованной функции.
Это выглядит как
equal[x;y] =
[atom[x] -> [atom[y] -> eq[x;y]; T -> F];
equal[car[x];car[y]] -> equal[cdr[x];cdr[y]];
T -> F]
не обрабатывает случай, когда x это минусы и y это атом
редактировать: также assoc не вернет ноль, если ключ не найден.
Скорее всего, это ссылка на ошибку динамического объема (ошибка, поскольку результат не выполняет то, что должен делать, если ожидается, что он будет похож на лямбда-исчисление):
eq[car[fn];LAMBDA] -> eval[caddr[fn];pairlis[cadr[fn];x;a]];
%^^^^^^^^^^^^^^^^^^^^^
И в отредактированном полу-подобном тексте:
((eq (car fn) lambda) (eval (caddr fn) (parlis (cadr fn) x a)))
;^^^^^^^^^^^^^^^^^^^^^^
Но это совсем не полезно. Исправление должно прийти не только туда, в это одно место; и вам нужно понять, как все это работает, и действительно следовать этому, чтобы увидеть, как происходит ошибка.
В качестве быстрой подсказки в правильном направлении проблема заключается в том, что тело лямбда-функции вычисляется в среде (второй аргумент eval), который является расширением текущей среды, что приводит к динамическому охвату. Решение этой проблемы - реализация лексической области видимости - включает в себя больше, чем просто редактирование, поскольку информация о лексической области действия функции уже потеряна.
(Любая случайная приличная книга на PL должна содержать гораздо больше деталей. В контексте Lisp, копание глубже действительно поможет вам разобраться в FUNARG.)
update2: Вот код из статьи, переписанный в каком-то псевдокоде со списком шаблонов и пониманий (включая параллельное понимание), во всех 13 строках кода (15 с добавлением FUNARG Устройство, рассмотренное ниже), все здесь в одном определении:
apply f args = eval [f, ...[[QUOTE, a] | a <- args]] [] % McCarthy-LISP-paper
eval e a | atom e = head [v | [n, v] <- a, n == e]
| otherwise = case e of
[QUOTE, x] -> x
[FUNCTION, x] -> [FUNARG, x, a] % enclose the definitional environment!
[CONS, x, y] -> [eval x a, ...eval y a]
[CAR, x] -> head ( eval x a )
[CDR, x] -> tail ( eval x a )
[ATOM, x] -> atom ( eval x a )
[EQ, x, y] -> eval x a == eval y a
[COND, ...xs] -> head [eval c a | [t, c] <- xs, eval t a]
[[LAMBDA,p,b], ...xs] -> eval b [...[[n, eval x a] | n <- p | x <- xs], ...a]
[[LABEL, n,x], ...xs] -> eval [x, ...xs] [[n, [LABEL, n, x]], ...a]
[[FUNARG,f,d], ...xs] -> eval [f, ...[[QUOTE, eval x a] | x <- xs]] d
[x, ...xs] -> eval [eval x a, ...xs] a % fixing the bug,
%% eval [eval x a, ...[eval x a | x <- xs]] a % args eval'd twice
обновление: вот видео Филипа Уодлера, где он говорит (в 22:30) об этой "ошибке" и о том, как использовать "неправильную переменную" (для среды, которая будет использоваться при оценке лямбда-тела, a вместо env в псевдокоде, который следует) приводит к "динамическому связыванию", а не "статическому связыванию".
Я переписал исходные M-выражения из кода в книге (руководство для программистов на Lisp 1.5) в каком-то специальном псевдокоде, который проще для меня использовать, используя : за cons или же .с сопоставлением с образцом и т. д., что следует в ближайшее время.
На самом деле, я не вижу никакой проблемы с двойной оценкой. apply ожидает, что его аргументы уже оценены, и eval оценивает их за это.
Я думаю, что ошибка была в оригинальной статье "Рекурсивные функции символических выражений" (обновление: да! Райнер Джосвиг упоминает в конце своего ответа статью Пола Грэма, в которой говорится, что это было в ссылке на код в статье).
Так что, на самом деле, похоже, что замечание Алана Кея касалось динамической оценки. Он упоминает, что смотрел "внизу страницы 13" (так в книге), и вот где evlis определение, которое оценивает элементы списка в той же текущей среде. Посмотрите на страницы 70, 71 книги для решения этой проблемы, требуя от программиста явного тегирования своих лямбда-определений новым ключевым словом function, создавать funargсписки с тегами, упаковывающие лямбды вместе (или закрывающиеся, как в "замыкании") со средой во время function форма оценивается - т.е. определяющая среда этого lambda форма.
Моисей 1970 называет это связующей средой, обсуждая только неявное создание замыканий при использовании в качестве функциональных аргументов при вызове функции более высокого порядка (отсюда и название "funarg"). Это также контекст в более современных дискуссиях о "глубоком и поверхностном связывании" (на мой взгляд, неправильное использование терминологии) в слове Perl и т. Д.
Но, глядя на эту расширенную версию в книге, кажется, что это позволило бы программисту явно создавать такие сущности, сохранять их в переменной, передавать как обычную сущность первого класса. Затем, когда закрытие funarg-метки), лямбда-определение оценивается в его среде, а не в текущей (то, что Моисей 1970 называет средой активации). Это очень близко к убедительной имитации лексической области видимости с динамическим связыванием.
Вот этот псевдокод, следующий за кодом из книги:
evalquote fn x = apply fn x [] % `x` a list of arguments
apply CAR ((x:_):_) a = x % `a` an association-list, the environment
| CDR ((_:x):_) _ = x
| CONS (x:y:_) _ = x:y
| ATOM (x:_) _ = atom x
| EQ (x:y:_) _ = eq x y
| fn xs a , atom fn = apply (eval fn a) xs a
| (LAMBDA args body) xs a = eval body (pairlis args xs a)
| (LABEL fn lambda) xs a = apply lambda xs ((fn:lambda):a)
%% and the FUNARG device, pg 70:
| (FUNARG lambda env) xs a = apply lambda xs env % not a, NB!
eval e a , atom e = assv e a
| (QUOTE e) _ = e
| (COND (t c) : cs) a = { eval t a -> eval c a ; eval (COND:cs) a }
%% the FUNARG device, pg 71:
| (FUNCTION lambda) a = (FUNARG lambda a) % enclose the definitional environment!
| (e1:es) a , atom e1 = apply e1 (evlis es a) a % or shortcut this directly to:
% apply (eval e1 a) (evlis es a) a
| (e1:es) a = apply e1 (evlis es a) a
evlis (m : ms) a = eval m a : evlis ms | [] _ = []
equal (x:xs) (y:ys) = equal x y && equal xs ys
| x y , atom x, atom y = eq x y | _ _ = F
subst x y z , equal y z = x
| _ _ z , atom z = z
| x y (h:t) = subst x y h : subst x y t
append (x:xs) ys = x : append xs ys | [] ys = ys
member x (y:_) , equal x y = T
| x (_:ys) = member x ys | _ [] = F
pairlis (x:xs) (y:ys) a = (x:y) : pairlis xs ys a | _ _ a = a
assv x ((h:y):ys) = { x==h -> y ; assv x ys }
sub2 ((x:v):xs) z = { eq x z -> v ; sub2 xs z } | [] z = z
sublis a y , atom y = sub2 a y | a (y:ys) = sublis a y : sublis a ys