числа мы обращаемся по многу раз, вычислять НОД лучше тогда, когда рациональное число конструируется. Если нет, нам может быть выгодно подождать с его вычислением до времени обращения. В любом случае, когда мы переходим от одной реализации к другой, нам ничего не нужно менять в процедурах add-rat, sub-rat и прочих.

То, что мы ограничиваем зависимость от представления несколькими интерфейсными процедурами, помогает нам и проектировать программы, и изменять их, поскольку таким образом мы сохраняем гибкость и получаем возможность рассматривать другие реализации. Продолжая наш простой пример, представим себе, что мы строим пакет работы с рациональными числами и не можем сразу решить, вычислять ли НОД при построении числа или при обращении к нему. Методология абстракции данных позволяет нам отложить это решение, не теряя возможности продолжать разработку остальных частей системы.

Упражнение 2.2.

Рассмотрим задачу представления отрезков прямой на плоскости. Каждый отрезок представляется как пара точек: начало и конец. Определите конструктор make-segment и селекторы start-segment и end-segment, которые определяют представление отрезков в терминах точек. Далее, точку можно представить как пару чисел: координата x и координата у. Соответственно, напишите конструктор make-point и селекторы x-point и y-point, которые определяют такое представление. Наконец, используя свои селекторы и конструктор, напишите процедуру midpoint-segment, которая принимает отрезок в качестве аргумента и возвращает его середину (точку, координаты которой являются средним координат концов отрезка). Чтобы опробовать эти процедуры, Вам потребуется способ печатать координаты точек:

(define (print-point p) (newline)

(display "(")

(display (x-point p)) (display ",") (display (y-point p)) (display ")"))

Упражнение 2.3.

Реализуйте представление прямоугольников на плоскости. (Подсказка: Вам могут потребоваться результаты упражнения 2.2.) Определите в терминах своих конструкторов и селекторов процедуры, которые вычисляют периметр и площадь прямоугольника. Теперь реализуйте другое представление для прямоугольников. Можете ли Вы спроектировать свою систему с подходящими барьерами абстракции так, чтобы одни и те же процедуры вычисления периметра и площади работали с любым из Ваших представлений?

2.1.3 Что значит слово «данные»?

Свою реализацию рациональных чисел в разделе 2.1.1 мы начали с определения операций над рациональными числами add-rat, sub-rat и так далее в терминах трех неопределенных процедур: make-rat, numer и denom. В этот момент мы могли думать об операциях как определяемых через объекты данных - числители, знаменатели и рациональные числа, - поведение которых определялось тремя последними процедурами.

Но что в точности означает слово данные (data)? Здесь недостаточно просто сказать «то, что реализуется некоторым набором селекторов и конструкторов».

Ясно, что не любой набор из трех процедур может служить основой для реализации рациональных чисел. Нам нужно быть уверенными в том, что если мы конструируем рациональное число x из пары целых n и d, то получение numer и denom от x и деление их друг на друга должно давать тот же результат, что и деление n на d. Другими словами, make-rat, numer и denom должны удовлетворять следующему условию: для каждого целого числа n и не равного нулю целого d, если x есть (make-rat n d) , то

(numer x) n (denom х) d

Это на самом деле единственное условие, которому должны удовлетворять make-rat, numer и denom, чтобы служить основой для представления рациональных чисел. В общем случае можно считать, что данные - это то, что определяется некоторым набором селекторов и конструкторов, а также некоторыми условиями, которым эти процедуры должны удовлетворять, чтобы быть правильным представлением.5

Эта точка зрения может послужить для определения не только «высокоуровневых» объектов данных, таких как рациональные числа, но и объектов низкого уровня. Рассмотрим понятие пары, с помощью которого мы определили наши рациональные числа. Мы ведь ни разу не сказали, что такое пара, и указывали только, что для работы с парами язык дает нам процедуры cons, car и cdr. Но единственное, что нам надо знать об этих процедурах - это что если мы склеиваем два объекта при помощи cons, то с помощью car и cdr мы можем получить их обратно. То есть эти операции удовлетворяют условию, что для любых объектов x и у, если z есть (cons x y), то (car z) есть x, а (cdr z) есть у. Действительно, мы упомянули, что три эти процедуры включены в наш язык как примитивы. Однако любая тройка процедур, которая удовлетворяет вышеуказанному условию, может использоваться как основа реализации пар. Эта идея ярко иллюстрируется тем, что мы могли бы реализовать cons, car и cdr без использования каких-либо структур данных, а только при помощи одних процедур. Вот эти определения:

(define (cons x y) (define (dispatch m) (cond ((= m 0) x) ((= m 1) y)

(else (error "Аргумент не 0 или 1 -- CONS" m)))) dispatch)

5Как ни странно, эту мысль очень трудно строго сформулировать. Существует два подхода к такой формулировке. Один, начало которому положил Ч. А. Р. Хоар (Hoare 1972), известен как метод абстрактных моделей (abstract models). Он формализует спецификацию вида «процедуры плюс условия» вроде описанной выше в примере с рациональными числами. Заметим, что условие на представление рациональных чисел было сформулировано в терминах утверждений о целых числах (равенство и деление). В общем случае абстрактные модели определяют новые типы объектов данных в терминах типов данных, определенных ранее. Следовательно, утверждения об объектах данных могут быть проверены путем сведения их к утверждениям об объектах данных, которые были определены ранее. Другой подход, который был введен Зиллесом из MIT, Гогеном, Тэтчером, Вагнером и Райтом из IBM (см. Thatcher, Wagner, and Wright 1978) и Гаттэгом из университета Торонто (см. Guttag 1977), называется алгебраическая спецификация (algebraic specification). Этот подход рассматривает «процедуры» как элементы абстрактной алгебраической системы, чье поведение определяется аксиомами, соответствующими нашим «условиям», и использует методы абстрактной алгебры для проверки утверждений об объектах данных. Оба этих метода описаны в статье Лисков и Зиллеса (Liskov and Zilles 1975).

(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, и вообще Лисп-системы, реализуют пары напрямую из соображений эффективности), а в том, чтобы показать, что он мог бы работать и так. Процедурная реализация, хотя она и выглядит трюком, - совершенно адекватный способ представления пар, поскольку она удовлетворяет единственному условию, которому должны соответствовать пары. Кроме того, этот пример показывает, что способность работать с процедурами как с объектами автоматически дает нам возможность представлять составные данные. Сейчас это может показаться курьезом, но в нашем программистском репертуаре процедурные представления данных будут играть центральную роль. Такой стиль программирования часто называют передачей сообщений (message passing), и в главе 3, при рассмотрении вопросов моделирования, он будет нашим основным инструментом.

Упражнение 2.4.

Вот еще одно процедурное представление для пар. Проверьте для этого представления, что при любых двух объектах x и y (car (cons x y)) возвращает x.

(define (cons x y)

(lambda (m) (m x y)))

(define (car z)

(z (lambda (p q) p)))

Каково соответствующее определение cdr? (Подсказка: Чтобы проверить, что это работает, используйте подстановочную модель из раздела 1.1.5.)

Упражнение 2.5.

Покажите, что можно представлять пары неотрицательных целых чисел, используя только числа и арифметические операции, если представлять пару а и b как произведение 2°3Ь. Дайте соответствующие определения процедур cons, car и cdr.