Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 92
Текст из файла (страница 92)
Таким образом, нам нужно уметь отменить присваивание в процессе возврата57 .Этого мы добиваемся, передавая vproc продолжение успеха (отмеченное ниже комментарием «*1*»), которое сохраняет старое значение переменной, прежде чем присвоитьей новое значение и продолжить вычисление. Продолжение неудачи, которое передаетсявместе со значением присваивания (и отмечено ниже комментарием «*2*»), восстанавливает старое значение переменной, прежде чем продолжить откат.
То есть, успешное присваивание дает продолжение неудачи, которое перехватит последующую неудачу; неудача, которая в противном случае вызвала бы fail2, вместо этого зовет эту процедуру, аона отменяет присваивание и уже затем зовет fail2.(define (analyze-assignment exp)(let ((var (assignment-variable exp))(vproc (analyze (assignment-value exp))))(lambda (env succeed fail)(vproc env(lambda (val fail2); *1*(let ((old-value(lookup-variable-value var env)))(set-variable-value! var val env)(succeed ’ok(lambda (); *2*(set-variable-value! varold-valueenv)(fail2)))))fail))))Вызов процедурИсполнительная процедура для вызовов не содержит никаких новшеств, кроме сложных технических деталей работы с продолжениями. Сложность возникает внутри analyze-application и обусловлена необходимостью следить за продолжениями успехаи неудачи при вычислении операндов.
Мы вычисляем операнды с помощью процедурыget-args, а не простого map, как в обыкновенном интерпретаторе.57 Мы не заботились об отмене определений, поскольку можно предположить, что внутренние определенияизымаются (раздел 4.1.6).400Глава 4. Метаязыковая абстракция(define (analyze-application exp)(let ((fproc (analyze (operator exp)))(aprocs (map analyze (operands exp))))(lambda (env succeed fail)(fproc env(lambda (proc fail2)(get-args aprocsenv(lambda (args fail3)(execute-applicationproc args succeed fail3))fail2))fail))))Заметьте, как в get-args для движения через cdr по списку исполнительных процедур aproc и сборки через cons получающегося списка аргументов каждая aproc всписке вызывается с продолжением успеха, которое рекурсивно зовет get-args.
Каждый из этих рекурсивных вызовов get-args имеет продолжение успеха, значение которого — cons свежеполученного аргумента со списком уже собранных аргументов:(define (get-args aprocs env succeed fail)(if (null? aprocs)(succeed ’() fail)((car aprocs) env;; продолжение успеха для этой aproc(lambda (arg fail2)(get-args (cdr aprocs)env;; продолжение успеха для;; рекурсивного вызова get-args(lambda (args fail3)(succeed (cons arg args)fail3))fail2))fail)))Собственно вызов процедуры, который выполняет execute-application, осуществляется так же, как и в обыкновенном интерпретаторе, не считая того, что необходимо управлять продолжениями.(define (execute-application proc args succeed fail)(cond ((primitive-procedure? proc)(succeed (apply-primitive-procedure proc args)fail))((compound-procedure? proc)((procedure-body proc)(extend-environment (procedure-parameters proc)args(procedure-environment proc))succeed4.3.
SCHEME с вариациями —недетерминистское вычисление401fail))(else(error"Неизвестный тип процедуры -- EXECUTE-APPLICATION"proc))))Выполнение выражений ambОсобая форма amb — ключевой элемент недетерминистского языка. Здесь лежит сущность процесса интерпретации и обоснование необходимости отслеживать продолжения.Исполнительная процедура для amb определяет цикл try-next, который перебираетисполнительные процедуры для всех возможных значений выражения amb. Каждая изисполнительных процедур вызывается с продолжением неудачи, которое попробует выполнить следующий вариант.
Когда вариантов больше не остается, все выражение ambтерпит неудачу.(define (analyze-amb exp)(let ((cprocs (map analyze (amb-choices exp))))(lambda (env succeed fail)(define (try-next choices)(if (null? choices)(fail)((car choices) envsucceed(lambda ()(try-next (cdr choices))))))(try-next cprocs))))Управляющий циклУправляющий цикл amb-интерпретатора сложен из-за наличия механизма, позволяющего пользователю заново попытаться выполнить выражение.
Цикл использует процедуру internal-loop, которая в качестве аргумента принимает процедуру try-again.Наш замысел состоит в том, чтобы вызов try-again переходил к следующему нерассмотренному варианту в недетерминистском вычислении. Процедура internal-loopлибо зовет try-again, если пользователь набирает try-again в управляющем цикле,либо запускает новое вычисление, вызывая ambeval.Продолжение неудачи в этом вызове ambeval сообщает пользователю, что значенийбольше нет, и перезапускает управляющий цикл.Продолжение успеха для вызова ambeval устроено тоньше.
Мы печатаем вычисленное значение, а потом заново запускаем внутренний цикл с процедурой try-again,которая сможет попробовать следующий вариант. Этот переход к следующему вариантувыражается процедурой next-alternative, которая передана вторым аргументом впродолжение успеха. Обычно мы считаем этот второй аргумент продолжением неудачи,которое придется использовать, если текущая ветвь исполнения потерпит неудачу. Однако в данном случае мы завершили успешное вычисление, так что «неудачный» вариантможно позвать для того, чтобы найти дополнительные успешные варианты вычисления.(define input-prompt ";;; Ввод Amb-Eval:")402Глава 4.
Метаязыковая абстракция(define output-prompt ";;; Значение Amb-Eval:")(define (driver-loop)(define (internal-loop try-again)(prompt-for-input input-prompt)(let ((input (read)))(if (eq? input ’try-again)(try-again)(begin(newline)(display ";;; Начало новой задачи ")(ambeval inputthe-global-environment;; успех ambeval(lambda (val next-alternative)(announce-output output-prompt)(user-print val)(internal-loop next-alternative));; неудача ambeval(lambda ()(announce-output";;; Нет больше значений")(user-print input)(driver-loop)))))))(internal-loop(lambda ()(newline)(display ";;; Задача не задана")(driver-loop))))Самый первый вызов internal-loop использует процедуру try-again, которая жалуется, что не было дано никакой задачи, и возобновляет управляющий цикл.
Такоеповедение требуется, если пользователь набирает try-again, еще не задав выражениедля вычисления.Упражнение 4.50.Реализуйте новую особую форму ramb, которая подобна amb, однако перебирает варианты неслева направо, а в случайном порядке. Покажите, как такая форма может пригодиться в Лизинойзадаче из упражнения 4.49Упражнение 4.51.Реализуйте новую разновидность присваивания permanent-set! — присваивание, которое неотменяется при неудачах. Например, можно выбрать два различных элемента в списке и посчитать,сколько для этого потребовалось попыток, следующим образом:(define count 0)(let ((x (an-element-of ’(a b c)))(y (an-element-of ’(a b c))))(permanent-set! count (+ count 1))4.3.
SCHEME с вариациями —недетерминистское вычисление403(require (not (eq? x y)))(list x y count));;; Начало новой задачи;;; Значение Amb-Eval:(a b 2);;; Ввод Amb-Eval:try-again;;; Значение Amb-Eval:(a c 3)Какие значения были бы напечатаны, если бы мы вместо permanent-set! использовали здесьобычный set!?Упражнение 4.52.Реализуйте новую конструкцию if-fail, которая позволяет пользователю перехватить неудачу при выполнении выражения. If-fail принимает два выражения. Первое она выполняет какобычно и, если вычисление успешно, возвращает его результат. Однако если вычисление неудачно,то возвращается значение второго выражения, как в следующем примере:;;; Ввод Amb-Eval:(if-fail (let ((x (an-element-of ’(1 3 5))))(require (even? x))x)’all-odd);;; Начало новой задачи;;; Значение Amb-Eval:all-odd;;; Ввод Amb-Eval:(if-fail (let ((x (an-element-of ’(1 3 5 8))))(require (even? x))x)’all-odd);;; Начало новой задачи;;; Значение Amb-Eval:8Упражнение 4.53.Если у нас есть permanent-set!, описанное в упражнении 4.51, и if-fail из упражнения 4.52,то каков будет результат вычисления(let ((pairs ’()))(if-fail (let ((p (prime-sum-pair ’(1 3 5 8) ’(20 35 110))))(permanent-set! pairs (cons p pairs))(amb))pairs))Упражнение 4.54.Если бы мы не догадались, что конструкцию require можно реализовать как обычную процедуру с помощью amb, так что пользователь сам может определить ее в своей недетерминистской404Глава 4.
Метаязыковая абстракцияпрограмме, то нам пришлось бы задать эту конструкцию в виде особой формы. Потребовались бысинтаксические процедуры(define (require? exp) (tagged-list? exp ’require))(define (require-predicate exp) (cadr exp))новая ветвь разбора в analyze:((require? exp) (analyze-require exp))а также процедура analyze-require, которая обрабатывает выражения require. Допишитеследующее определение analyze-require:(define (analyze-require exp)(let ((pproc (analyze (require-predicate exp))))(lambda (env succeed fail)(pproc env(lambda (pred-value fail2)(if h??ih??i(succeed ’ok fail2)))fail))))4.4. Логическое программированиеВ главе 1 мы подчеркивали, что информатика имеет дело с императивным знанием(«как сделать»), в то время как математика имеет дело с декларативным знанием («чтотакое»).
Действительно, языки программирования требуют, чтобы программист, выражаясвои знания, указывал методы пошагового решения определенных задач. С другой стороны, языки высокого уровня обеспечивают в рамках своих реализаций существенныйобъем методологических знаний, которые освобождает пользователя от забот о многихдеталях того, как проходит описываемое вычисление.Большинство языков программирования, включая Лисп, построены вокруг вычисления значений математических функций. Языки, ориентированные на выражения, (такие,как Лисп, Фортран и Алгол) пользуются тем, что выражение, описывающее значениефункции, можно интерпретировать и как способ вычислить это значение. По этой причине большинство языков программирования имеют уклон в однонаправленные вычисления (вычисления со строго определенными входом и выходом).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
