Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 24
Текст из файла (страница 24)
Введение в абстракцию данных101Эта идея ярко иллюстрируется тем, что мы могли бы реализовать cons, car и cdr безиспользования каких-либо структур данных, а только при помощи одних процедур. Вотэти определения:(define (cons x y)(define (dispatch m)(cond ((= m 0) x)((= m 1) y)(else (error "Аргумент не 0 или 1 -- CONS" m))))dispatch)(define (car z) (z 0))(define (cdr z) (z 1))Такое использование процедур совершенно не соответствует нашему интуитивному понятию о том, как должны выглядеть данные. Однако для того, чтобы показать, что этозаконный способ представления пар, требуется только проверить, что эти процедурыудовлетворяют вышеуказанному условию.Тонкость здесь состоит в том, чтобы заметить, что значение, возвращаемое cons,есть процедура, — а именно процедура dispatch, определенная внутри cons, котораяпринимает один аргумент и возвращает либо x, либо y в зависимости от того, равен лиее аргумент 0 или 1.
Соответственно, (car z) определяется как применение z к 0. Следовательно, если z есть процедура, полученная из (cons x y), то z, примененная к 0,вернет x. Таким образом, мы показали, что (car (cons x y)) возвращает x, как нами хотелось. Подобным образом (cdr (cons x y)) применяет процедуру, возвращаемую (cons x y), к 1, что дает нам y. Следовательно, эта процедурная реализация парзаконна, и если мы обращаемся к парам только с помощью cons, car и cdr, то мы несможем отличить эту реализацию от такой, которая использует «настоящие» структурыданных.Демонстрировать процедурную реализацию имеет смысл не для того, чтобы показать, как работает наш язык (Scheme, и вообще Лисп-системы, реализуют пары напрямую из соображений эффективности), а в том, чтобы показать, что он мог бы работатьи так.
Процедурная реализация, хотя она и выглядит трюком, — совершенно адекватный способ представления пар, поскольку она удовлетворяет единственному условию,которому должны соответствовать пары. Кроме того, этот пример показывает, что способность работать с процедурами как с объектами автоматически дает нам возможностьпредставлять составные данные.
Сейчас это может показаться курьезом, но в нашем программистском репертуаре процедурные представления данных будут играть центральнуюроль. Такой стиль программирования часто называют передачей сообщений (messagepassing), и в главе 3, при рассмотрении вопросов моделирования, он будет нашим основным инструментом.Упражнение 2.4.Вот еще одно процедурное представление для пар.
Проверьте для этого представления, что прилюбых двух объектах x и y (car (cons x y)) возвращает x.(define (cons x y)(lambda (m) (m x y)))102Глава 2. Построение абстракций с помощью данных(define (car z)(z (lambda (p q) p)))Каково соответствующее определение cdr? (Подсказка: Чтобы проверить, что это работает, используйте подстановочную модель из раздела 1.1.5.)Упражнение 2.5.Покажите, что можно представлять пары неотрицательных целых чисел, используя только числаи арифметические операции, если представлять пару a и b как произведение 2a 3b . Дайте соответствующие определения процедур cons, car и cdr.Упражнение 2.6.Если представление пар как процедур было для Вас еще недостаточно сумасшедшим, то заметьте,что в языке, который способен манипулировать процедурами, мы можем обойтись и без чисел (покрайней мере, пока речь идет о неотрицательных числах), определив 0 и операцию прибавления 1так:(define zero (lambda (f) (lambda (x) x)))(define (add-1 n)(lambda (f) (lambda (x) (f ((n f) x)))))Такое представление известно как числа Чёрча (Church numerals), по имени его изобретателя,Алонсо Чёрча, того самого логика, который придумал λ-исчисление.Определите one (единицу) и two (двойку) напрямую (не через zero и add-1).
(Подсказка: вычислите (add-1 zero) с помощью подстановки.) Дайте прямое определение процедурысложения + (не в терминах повторяющегося применения add-1).2.1.4. Расширенный пример: интервальная арифметикаЛиза П. Хакер проектирует систему, которая помогала бы в решении техническихзадач. Одна из возможностей, которые она хочет реализовать в своей системе, — способность работать с неточными величинами (например, измеренные параметры физическихустройств), обладающими известной погрешностью, так что когда с такими приблизительными величинами производятся вычисления, результаты также представляют собойчисла с известной погрешностью.Инженеры-электрики будут с помощью Лизиной системы вычислять электрическиевеличины.
Иногда им требуется вычислить сопротивление Rp параллельного соединениядвух резисторов R1 и R2 по формулеRp =11/R1 + 1/R2Обычно сопротивления резисторов известны только с некоторой точностью, которуюгарантирует их производитель. Например, покупая резистор с надписью «6.8 Ом с погрешностью 10%», Вы знаете только то, что сопротивление резистора находится между6.8 − 0.68 = 6.12 и 6.8 + 0.68 = 7.48 Ом. Так что если резистор в 6.8 Ом с погрешностью10% подключен параллельно резистору в 4.7 Ом с погрешностью 5%, то сопротивление этой комбинации может быть примерно от 2.58 Ом (если оба резистора находятся2.1. Введение в абстракцию данных103на нижней границе интервала допустимых значений) до 2.97 Ом (если оба резисторанаходятся на верхней границе).Идея Лизы состоит в том, чтобы реализовать «интервальную арифметику» как наборарифметических операций над «интервалами» (объектами, которые представляют диапазоны возможных значений неточной величины).
Результатом сложения, вычитания,умножения или деления двух интервалов также будет интервал, который представляетдиапазон возможных значений результата.Лиза постулирует существование абстрактного объекта, называемого «интервал», укоторого есть два конца: верхняя и нижняя границы. Кроме того, она предполагает,что имея два конца интервала, мы можем сконструировать его при помощи конструктора make-interval.
Сначала Лиза пишет процедуру сложения двух интервалов. Онарассуждает так: минимальное возможное значение суммы равно сумме нижних границинтервалов, а максимальное возможное значение сумме верхних границ интервалов.(define (add-interval x y)(make-interval (+ (lower-bound x) (lower-bound y))(+ (upper-bound x) (upper-bound y))))Кроме того, она вычисляет произведение двух интервалов путем нахождения минимума и максимума произведений концов интервалов и использования в качестве границинтервала-результата. (min и max — примитивы, которые находят минимум и максимумпри любом количестве аргументов.)(define (mul-interval x y)(let ((p1 (* (lower-bound x) (lower-bound(p2 (* (lower-bound x) (upper-bound(p3 (* (upper-bound x) (lower-bound(p4 (* (upper-bound x) (upper-bound(make-interval (min p1 p2 p3 p4)(max p1 p2 p3 p4))))y)))y)))y)))y))))При делении двух интервалов Лиза умножает первый из них на интервал, обратный второму.
Заметим, что границами обратного интервала являются числа, обратные верхнейи нижней границе исходного интервала, именно в таком порядке.(define (div-interval x y)(mul-interval x(make-interval (/ 1.0 (upper-bound y))(/ 1.0 (lower-bound y)))))Упражнение 2.7.Программа Лизы неполна, поскольку она не определила, как реализуется абстракция интервала.Вот определение конструктора интервала:(define (make-interval a b) (cons a b))Завершите реализацию, определив селекторы upper-bound и lower-bound.Упражнение 2.8.Рассуждая в духе Лизы, опишите, как можно вычислить разность двух интервалов. Напишитесоответствующую процедуру вычитания, называемую sub-interval.104Глава 2.
Построение абстракций с помощью данныхУпражнение 2.9.Радиус (width) интервала определяется как половина расстояния между его верхней и нижней границами. Радиус является мерой неопределенности числа, которое обозначает интервал. Есть такиематематические операции, для которых радиус результата зависит только от радиусов интерваловаргументов, а есть такие, для которых радиус результата не является функцией радиусов аргументов. Покажите, что радиус суммы (или разности) двух интервалов зависит только от радиусовинтервалов, которые складываются (или вычитаются). Приведите примеры, которые показывают,что для умножения или деления это не так.Упражнение 2.10.Бен Битобор, системный программист-эксперт, смотрит через плечо Лизы и замечает: неясно, чтодолжно означать деление на интервал, пересекающий ноль.
Модифицируйте код Лизы так, чтобыпрограмма проверяла это условие и сообщала об ошибке, если оно возникает.Упражнение 2.11.Проходя мимо, Бен делает туманное замечание: «Если проверять знаки концов интервалов, можноразбить mul-interval на девять случаев, из которых только в одном требуется более двухумножений».
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
