|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[78] (define (cons x y) (let ((new (get-new-pair))) (set-car! new x) (set-cdr! new y) new)) Упражнение 3.12. В разделе 2.2.1 была введена следующая процедура для добавления одного списка к другому: (define (append x y) (if (null? x) y (cons (car x) (append (cdr x) y)))) Append порождает новый список, по очереди наращивая элементы x в начало у. Процедура append! подобна append, но только она является не конструктором, а мутатором. Она склеивает списки вместе, изменяя последнюю пару x так, что ее cdr становится равным у. (Вызов append! с пустым x является ошибкой.) (define (append! x y) (set-cdr! (last-pair x) y) x) Здесь last-pair - процедура, которая возвращает последнюю пару своего аргумента: (define (last-pair x) (if (null? (cdr x)) x (last-pair (cdr x)))) Рассмотрим последовательность действий (define x (list a b)) (define y (list c d)) (define z (append x у)) z (a b c d) (cdr x) (ответ) (define w (append! x y)) w (a b c d) (cdr x) ( ответ) Каковы будут пропущенные (ответы)? Объясните, нарисовав стрелочные диаграммы. ления памятью в рамках реализации Лиспа. Мы рассмотрим эти вопросы в разделе 5.3.1. zi- 471 Рис. 3.16: Список zi, порождаемый выражением (cons x x). x b a Упражнение 3.13. Рассмотрим следующую процедуру make-cycle, которая пользуется last-pair из упражнения 3.12: (define (make-cycle x) (set-cdr! (last-pair x) x) x) Нарисуйте стрелочную диаграмму, которая изображает структуру z, созданную таким кодом: (define z (make-cycle (list a b c))) Что случится, если мы попробуем вычислить (last-pair z)? Упражнение 3.14. Следующая процедура, хотя и сложна для понимания, вполне может оказаться полезной: (define (mystery x) (define (loop x y) (if (null? x) y (let ((temp (cdr x))) (set-cdr! x y) (loop temp x)))) (loop x ())) Loop пользуется «временной» переменной temp, чтобы сохранить старое значение cdr пары x, поскольку set-cdr! на следующей строке его разрушает. Объясните, что за задачу выполняет mystery. Предположим, что переменная v определена выражением (define v (list a b c d). Нарисуйте диаграмму, которая изображает список, являющийся значением v. Допустим, что теперь мы выполняем (define w (mystery v)) . Нарисуйте стрелочные диаграммы, которые показывают структуры v и w после вычисления этого выражения. Что будет напечатано в качестве значений v и w? Разделение данных и их идентичность В разделе 3.1.3 мы упоминали теоретические вопросы «идентичности» и «изменения», которые возникают с появлением присваивания. Эти вопросы начинают иметь практическое значение тогда, когда отдельные пары разделяются (are shared) между различными объектами данных. Рассмотрим, например, структуру, которая создается таким кодом: 43 b Рис. 3.17: Список z2, порождаемый выражением (cons (list a b) (list a b)). x a (define x (list a b)) (define zl (cons x x)) Как показано на рис. 3.16, zl представляет собой пару, в которой car и cdr указывают на одну и ту же пару x. Разделение x между car и cdr пары z1 возникает оттого, что cons реализован простейшим способом. В общем случае построение списков с помощью cons приводит к возникновению сложносвязан-ной сети пар, в которой многие пары разделяются между многими различными структурами. В противоположность рис. 3.16, рис. 3.17 показывает структуру, которая порождается кодом (define z2 (cons (list a b) (list a b))) В этой структуре пары двух списков (a b) различны, притом, что сами символы разделяются.14 Если мы рассматриваем zl и z2 как списки, они представляют «один и тот же» список ((a b) a b). Вообще говоря, разделение данных невозможно заметить, если мы работаем со списками только при помощи операций cons, car и cdr. Однако если мы вводим мутаторы, работающие со списковой структурой, разделение данных начинает иметь значение. Как пример случая, когда разделение влияет на результат, рассмотрим следующую процедуру, которая изменяет car структуры, к которой она применяется: (define (set-to-wow! x) (set-car! (car x) wow) x) Несмотря на то, что zl и z2 имеют «одинаковую» структуру, применение к ним процедуры set-to-wow! дает различные результаты. В случае с zl изменение car влияет и на cdr, поскольку здесь car и cdr - это одна и та же пара. В случае с z2, car и cdr различны, так что set-to-wow! изменяет только car: 19Пары различаются потому, что каждый вызов cons порождает новую пару. Символы разделяются; в Scheme существует только один символ для каждого данного имени. Поскольку Scheme не дает возможности изменять символ, это разделение невозможно заметить. Заметим, кроме того, что именно разделение позволяет нам сравнивать символы при помощи eq?, который просто проверяет равенство указателей. |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||