Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 87
Текст из файла (страница 87)
Потоки как ленивые спискиВ разделе 3.5.1 мы показали, как реализовать потоки в виде задержанных списков.Мы ввели особые формы delay и cons-stream, которые позволили нам строить «обещания» вычислить cdr потока, не выполняя эти обещания до более позднего времени.Можно было бы использовать этот же метод и вводить новые особые формы всякийраз, когда нам требуется детальное управление процессом вычисления, но это было бывесьма неуклюже. Прежде всего, особая форма, в отличие от процедуры, не являетсяполноправным объектом, и ее нельзя использовать в сочетании с процедурами высшихпорядков39 . Кроме того, нам пришлось ввести потоки как новый тип объектов данных,похожий на списки, но отличный от них, и из-за этого потребовалось заново переписатьдля работы с потоками множество обычных операций над списками (map, append итому подобное).Когда у нас есть ленивое вычисление, списки и потоки можно считать одним и темже типом, так что не возникает нужды в особых формах и в отдельных наборах операций для списков и потоков.
Все, что нам требуется, — это так устроить дела, чтобыcons оказалась нестрогой. Можно сделать это, расширив интерпретатор и разрешивнестрогие элементарные процедуры, а затем реализовать cons как одну из таких процедур. Однако проще вспомнить (из раздела 2.1.3), что вообще не существует особойнужды реализовывать cons как примитив.
Вместо этого можно представлять пары ввиде процедур40 .(define (cons x y)(lambda (m) (m x y)))(define (car z)(z (lambda (p q) p)))(define (cdr z)(z (lambda (p q) q)))Выраженные через эти базовые операции, стандартные определения операций надсписками будут работать как с бесконечными списками (потоками), так и с конечными,а потоковые операции можно определить как операции над списками.
Вот несколькопримеров:(define (list-ref items n)(if (= n 0)(car items)(list-ref (cdr items) (- n 1))))(define (map proc items)(if (null? items)39 Этокак раз тот вопрос, который возник по отношению к процедуре unless в упражнении 4.26.процедурное представление, описанное в упражнении 2.4. В сущности, подошла бы и любая другая процедурная реализация (например, на основе передачи сообщений). Обратите внимание, что внести этиопределения в ленивый интерпретатор можно, просто набрав их в управляющем цикле. Если мы изначальновключили cons, car и cdr как примитивы в глобальное окружение, они будут переопределены. (См. такжеупражнения 4.33 и 4.34.)40 ЭтоГлава 4.
Метаязыковая абстракция380’()(cons (proc (car items))(map proc (cdr items)))))(define (scale-list items factor)(map (lambda (x) (* x factor))items))(define (add-lists list1 list2)(cond ((null? list1) list2)((null? list2) list1)(else (cons (+ (car list1) (car list2))(add-lists (cdr list1) (cdr list2))))))(define ones (cons 1 ones))(define integers (cons 1 (add-lists ones integers)));;; Ввод L-Eval:(list-ref integers 17);;; Значение L-Eval:18Заметим, что ленивые списки еще ленивее, чем потоки в главе 3: задерживается нетолько cdr списка, но и car41 . На самом деле, даже доступ к car или cdr ленивойпары не обязательно вынуждает значение элемента списка.
Значение будет вынужденотолько тогда, когда это действительно нужно — например, чтобы использовать его вкачестве аргумента примитива или напечатать в качестве ответа.Ленивые пары также помогают с решением проблемы, которая возникла в разделе 3.5.4, где мы обнаружили, что формулировка потоковых моделей систем с цикламиможет потребовать оснащения программы явными операциями delay, помимо тех, чтовстроены в cons-stream. При ленивом вычислении все аргументы процедур единообразно задерживаются. Например, можно реализовать процедуры для интегрированиясписка и решения дифференциальных уравнений так, как мы изначально намеревалисьв разделе 3.5.4:(define (integral integrand initial-value dt)(define int(cons initial-value(add-lists (scale-list integrand dt)int)))int)(define (solve f y0 dt)(define y (integral dy y0 dt))(define dy (map f y))y)41 Благодаря этому можно реализовать задержанные версии не только последовательностей, но и более общихвидов списковых структур.
В Hughes 1990 обсуждаются некоторые применения «ленивых деревьев».4.3. SCHEME с вариациями —недетерминистское вычисление381;;; Ввод L-Eval:;: (list-ref (solve (lambda (x) x) 1 .001) 1000);;; Значение L-Eval:2.176924Упражнение 4.32.Приведите несколько примеров, которые показывают разницу между потоками из главы 3.5.4и «более ленивыми» списками, описанными в этом разделе. Как можно воспользоваться этойдополнительной ленивостью?Упражнение 4.33.Бен Битобор проверяет вышеописанную реализацию при помощи выражения(car ’(a b c))К его большому удивлению, в ответ выдается ошибка.
После некоторого размышления он понимает, что «списки». которые получаются при чтении кавычек, отличаются от списков, управляемыхновыми определениями cons, car и cdr. Измените работу интерпретатора с закавыченными выражениями так, чтобы при вводе списковых выражений в цикле управления получались настоящиеленивые списки.Упражнение 4.34.Измените управляющий цикл интерпретатора так, чтобы ленивые пары и списки печатались какимлибо разумным образом. (Как Вы собираетесь работать с бесконечными списками)? Вероятно,понадобится также изменить представление ленивых пар, чтобы при печати интерпретатор ихраспознавал и печатал особым образом.4.3.
Scheme с вариациями —недетерминистское вычислениеВ этом разделе мы расширяем интерпретатор Scheme так, чтобы он поддерживал парадигму программирования, называемую недетерминистское вычисление(nondeterministic computing), встраивая в интерпретатор средства поддержки автоматического поиска. Это значительно более глубокое изменение в языке, чем введениеленивых вычислений в разделе 4.2.Подобно обработке потоков, недетерминистское вычисление полезно в задачах типа«порождение и проверка». Рассмотрим такую задачу: даются два списка натуральныхчисел, и требуется найти пару чисел — одно из первого списка, другое из второго, —сумма которых есть простое число.
В разделе 2.2.3 мы уже рассмотрели, как это можносделать при помощи операций над конечными последовательностями, а в разделе 3.5.3 —при помощи бесконечных потоков. Наш подход состоял в том, чтобы породить последовательность всех возможных пар и отфильтровать ее, выбирая пары, в которых суммаесть простое число. Порождаем ли мы на самом деле сначала всю последовательность,как в главе 2, или чередуем порождение и фильтрацию, как в главе 3, несущественнодля общей картины того, как организовано вычисление.382Глава 4. Метаязыковая абстракцияПри недетерминистском подходе используется другой образ. Просто представим себе,что мы (каким-то образом) выбираем число из первого списка и число из второго списка,а затем предъявляем (при помощи какого-то механизма) требование, чтобы их суммабыла простым числом.
Это выражается следующей процедурой:(define (prime-sum-pair list1 list2)(let ((a (an-element-of list1))(b (an-element-of list2)))(require (prime? (+ a b)))(list a b)))Может показаться, что эта процедура просто переформулирует задачу, а не указываетспособ ее решить. Однако это законная недетерминистская программа42 .Основная идея здесь состоит в том, что выражениям в недетерминистском языке разрешается иметь более одного возможного значения. Например, an-element-of можетвернуть любой элемент данного списка.
Наш интерпретатор недетерминистских программ будет автоматически выбирать возможное значение и запоминать, что он выбрал.Если впоследствии какое-либо требование не будет выполнено, интерпретатор попробуетдругой вариант выбора и будет перебирать варианты, пока вычисление не закончитсяуспешно или пока варианты не иссякнут. Подобно тому, как ленивый интерпретаторосвобождал программиста от заботы о деталях задержки и вынуждения значений, недетерминистский интерпретатор позволяет ему не заботиться о том, как происходит выбор.Поучительно будет сравнить различные понятия времени, складывающиеся при недетерминистских вычислениях и обработке потоков. При обработке потоков ленивые вычисления используются для того, чтобы устранить связь между временем, когда строитсяпоток возможных ответов, и временем, когда порождаются собственно ответы.
Интерпретатор создает иллюзию, что все возможные ответы предоставлены нам во вневременной последовательности. При недетерминистских вычислениях выражение представляетсобой исследование множества возможных миров, каждый из которых определяется множеством выбранных вариантов. Некоторые возможные миры приводят в тупик, другиедают полезные ответы.
Вычислитель недетерминистских программ создает иллюзию, чтовремя разветвляется, и что у наших программ есть различные возможные истории исполнения. Если мы оказываемся в тупике, мы можем вернуться к последней точке выбора ипродолжить путь по другой ветке.Описываемый в этом разделе интерпретатор недетерминистских программ называется amb-интерпретатор, потому что он основан на новой особой форме amb.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
