Глава 2

Построение абстракций с помощью

данных

Теперь мы подходим к решающему шагу в математической абстракции: мы забываем, что обозначают наши символы. ...[Математик] не должен стоять на месте: есть много операций, которые он может производить с этими символами, не обращая внимания на те вещи, которые они обозначают.

Герман Вейль. «Математический способ мышления»

В главе 1 мы сконцентрировали внимание на вычислительных процессах и роли процедур в проектировании программ. Мы рассмотрели, как использовать простейшие данные (числа) и простейшие операции (арифметические), как сочетать процедуры и получать составные процедуры с помощью композиции, условных выражений и использования параметров, а также как строить абстрактные процедуры при помощи define. Мы убедились, что процедуру можно рассматривать как схему локального развития процесса; мы классифицировали некоторые общие схемы процессов, воплощенные в процедурах, строили о них умозаключения и производили их простейший алгоритмический анализ. Кроме того, мы увидели, что процедуры высших порядков увеличивают выразительную силу нашего языка, позволяя оперировать общими методами вычисления, а следовательно, и проводить рассуждения в их терминах. Это во многом и составляет сущность программирования.

В этой главе мы будем рассматривать более сложные данные. Все процедуры главы 1 работают с простыми численными данными, а простых численных данных часто бывает недостаточно для тех задач, которые мы хотим решать с помощью вычислений. Программы, как правило, пишут, чтобы моделировать сложные явления, и чаще всего приходится строить вычислительные объекты, состоящие из нескольких частей, чтобы смоделировать многосторонние явления реального мира. Таким образом, в отличие от главы 1, где наше внимание было в основном направлено на создание абстракций с помощью сочетания процедур и построения составных процедур, в этой главе мы обращаемся к другой важной характеристике всякого языка программирования: тем средствам, которые он предоставляет для создания абстракций с помощью сочетания объектов данных и построения составных данных (compound data).

Для чего в языке программирования нужны составные данные? По тем же причинам, по которым нужны составные процедуры: мы хотим повысить понятийный уровень, на котором мы проектируем программы, хотим сделать наши проекты более модульными и увеличить выразительную силу языка. Точно так

же, как способность определять процедуры дает возможность работать с процессами на более высоком содержательном уровне, чем уровень элементарных операций языка, способность конструировать составные объекты данных позволяет работать с данными на более высоком понятийном уровне, чем уровень элементарных данных нашего языка.

Рассмотрим задачу проектирования системы для арифметических вычислений с рациональными числами. Мы можем представить себе операцию add-rat, которая принимает два рациональных числа и вычисляет их сумму. В терминах простейших данных, рациональное число можно рассматривать как два целых числа: числитель и знаменатель. Таким образом, мы могли бы сконструировать программу, в которой всякое рациональное число представлялось бы как пара целых (числитель и знаменатель) и add-rat была бы реализована как две процедуры (одна из которых вычисляла бы числитель суммы, а другая знаменатель). Однако это было бы крайне неудобно, поскольку нам приходилось бы следить, какие числители каким знаменателям соответствуют. Если бы системе требовалось производить большое количество операций над большим количеством рациональных чисел, такие служебные детали сильно затемняли бы наши программы, не говоря уже о наших мозгах. Было бы намного проще, если бы мы могли «склеить» числитель со знаменателем и получить пару - составной объект данных (compound data object), - с которой наши программы могли бы обращаться способом, соответствующим нашему представлению о рациональном числе как о едином понятии.

Кроме того, использование составных данных позволяет увеличить модульность программ. Если бы мы могли обрабатывать рациональные числа непосредственно как объекты, то можно было бы отделить ту часть программы, которая работает собственно с рациональными числами, от деталей представления рационального числа в виде пары целых. Общий метод отделения частей программы, которые имеют дело с представлением объектов данных, от тех частей, где эти объекты данных используются, - это мощная методология проектирования, называемая абстракция данных (data abstraction). Мы увидим, как с помощью абстракции данных программы становится легче проектировать, поддерживать и изменять.

Использование составных данных ведет к настоящему увеличению выразительной силы нашего языка программирования. Рассмотрим идею порождения «линейной комбинации» ax + by. Нам может потребоваться процедура, которая принимала бы как аргументы a, b, x и y и возвращала бы значение ax + by. Если аргументы являются числами, это не представляет никакой трудности, поскольку мы сразу можем определить процедуру

(define (linear-combination a b x y) (+ (* ax) (* b y)))

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

(define (linear-combination a b x y) (add (mul a x) (mul b y)))

где add и mul - не элементарные процедуры + и *, а более сложные устройства, которые проделывают соответствующие операции, какие бы типы данных мы ни передавали как аргументы a, b, x и y. Здесь важнейшая деталь состоит в том, что единственное, что требуется знать процедуре linear-combination об a, b, x и y - это то, что процедуры add и mul проделывают соответствующие действия. С точки зрения процедуры linear-combination несущественно, что такое a, b, x и y, и еще менее существенно, как они могут быть представлены через более простые данные. Этот же пример показывает, почему так важно, чтобы в нашем языке программирования была возможность прямо работать с составными объектами: иначе у процедур, подобных linear-combination, не было бы способа передать аргументы в add и mul, не зная деталей их устройства.1

Мы начинаем эту главу с реализации описанной выше системы арифметики рациональных чисел. Это послужит основанием для обсуждения составных данных и абстракции данных. Как и в случае с составными процедурами, основная мысль состоит в том, что абстракция является методом ограничения сложности, и мы увидим, как абстракция данных позволяет нам возводить полезные барьеры абстракции (abstraction barriers) между разными частями программы.

Мы увидим, что главное в работе с составными данными - то, что язык программирования должен предоставлять нечто вроде «клея», так, чтобы объекты данных могли сочетаться, образуя более сложные объекты данных. Существует множество возможных типов клея. На самом деле мы обнаружим, что составные данные можно порождать вообще без использования каких-либо специальных операций, относящихся к «данным» - только с помощью процедур. Это еще больше размоет границу между «процедурами» и «данными», которая уже к концу главы 1 оказалась весьма тонкой. Мы также исследуем некоторые общепринятые методы представления последовательностей и деревьев. Важная идея в работе с составными данными - понятие замыкания (closure): клей для сочетания объектов данных должен позволять нам склеивать не только элементарные объекты данных, но и составные. Еще одна важная идея состоит в том, что составные объекты данных могут служить стандартными интерфейсами (conventional interfaces), так, чтобы модули программы могли сочетаться методом подстановки. Некоторые из этих идей мы продемонстрируем с помощью простого графического языка, использующего замыкание.

Затем мы увеличим выразительную мощность нашего языка путем введения символьных выражений (symbolic expressions) - данных, элементарные части которых могут быть произвольными символами, а не только числами. Мы рассмотрим различные варианты представления множеств объектов. Мы обнаружим, что, подобно тому, как одна и та же числовая функция может вычисляться различными вычислительными процессами, существует множество способов представить некоторую структуру данных через элементарные объек-

1 Способность прямо оперировать процедурами увеличивает выразительную силу нашего языка программирования подобным же образом. Например, в разделе 1.3.1 мы ввели процедуру sum, которая принимает в качестве аргумента процедуру term и вычисляет сумму значений term на некотором заданном интервале. Чтобы определить sum, нам необходимо иметь возможность говорить о процедуре типа term как о едином целом, независимо от того, как она выражена через более простые операции. Вообще говоря, не имей мы понятия «процедуры», вряд ли мы и думать могли бы о возможности определения такой операции, как sum. Более того, пока мы размышляем о суммировании, детали того, как term может быть составлен из более простых операций, несущественны.