Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 21
Текст из файла (страница 21)
Программы, как правило, пишут, чтобы моделировать сложные явления, и чаще всего приходитсястроить вычислительные объекты, состоящие из нескольких частей, чтобы смоделировать многосторонние явления реального мира. Таким образом, в отличие от главы 1,где наше внимание было в основном направлено на создание абстракций с помощьюсочетания процедур и построения составных процедур, в этой главе мы обращаемся кдругой важной характеристике всякого языка программирования: тем средствам, которые он предоставляет для создания абстракций с помощью сочетания объектов данныхи построения составных данных (compound data).Для чего в языке программирования нужны составные данные? По тем же причинам,по которым нужны составные процедуры: мы хотим повысить понятийный уровень, накотором мы проектируем программы, хотим сделать наши проекты более модульными и91увеличить выразительную силу языка.
Точно так же, как способность определять процедуры дает возможность работать с процессами на более высоком содержательном уровне,чем уровень элементарных операций языка, способность конструировать составные объекты данных позволяет работать с данными на более высоком понятийном уровне, чемуровень элементарных данных нашего языка.Рассмотрим задачу проектирования системы для арифметических вычислений с рациональными числами. Мы можем представить себе операцию add-rat, которая принимает два рациональных числа и вычисляет их сумму. В терминах простейших данных, рациональное число можно рассматривать как два целых числа: числитель и знаменатель.Таким образом, мы могли бы сконструировать программу, в которой всякое рациональноечисло представлялось бы как пара целых (числитель и знаменатель) и add-rat былабы реализована как две процедуры (одна из которых вычисляла бы числитель суммы,а другая знаменатель).
Однако это было бы крайне неудобно, поскольку нам приходилось бы следить, какие числители каким знаменателям соответствуют. Если бы системетребовалось производить большое количество операций над большим количеством рациональных чисел, такие служебные детали сильно затемняли бы наши программы, неговоря уже о наших мозгах. Было бы намного проще, если бы мы могли «склеить» числитель со знаменателем и получить пару — составной объект данных (compound dataobject), — с которой наши программы могли бы обращаться способом, соответствующимнашему представлению о рациональном числе как о едином понятии.Кроме того, использование составных данных позволяет увеличить модульность программ.
Если бы мы могли обрабатывать рациональные числа непосредственно как объекты, то можно было бы отделить ту часть программы, которая работает собственно срациональными числами, от деталей представления рационального числа в виде пары целых. Общий метод отделения частей программы, которые имеют дело с представлениемобъектов данных, от тех частей, где эти объекты данных используются, — это мощнаяметодология проектирования, называемая абстракция данных (data abstraction).
Мыувидим, как с помощью абстракции данных программы становится легче проектировать,поддерживать и изменять.Использование составных данных ведет к настоящему увеличению выразительной силы нашего языка программирования. Рассмотрим идею порождения «линейной комбинации» ax+ by.
Нам может потребоваться процедура, которая принимала бы как аргументыa, b, x и y и возвращала бы значение ax + by. Если аргументы являются числами, это непредставляет никакой трудности, поскольку мы сразу можем определить процедуру(define (linear-combination a b x y)(+ (* a x) (* b y)))Предположим, однако, что нас интересуют не только числа. Предположим, что намхотелось бы выразить в процедурных терминах идею о том, что можно строить линейные комбинации всюду, где определены сложение и умножение — для рациональныхи комплексных чисел, многочленов и многого другого. Мы могли бы выразить это какпроцедуру в следующей форме:(define (linear-combination a b x y)(add (mul a x) (mul b y)))92Глава 2. Построение абстракций с помощью данныхгде 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 может быть составлен из болеепростых операций, несущественны.2.1. Введение в абстракцию данных93идеи в контексте символьного дифференцирования, представления множеств и кодирования информации.После этого мы обратимся к задаче работы с данными, которые по-разному могутбыть представлены в различных частях программы.
Это ведет к необходимости ввестиобобщенные операции (generic operations), которые обрабатывают много различных типов данных. Поддержка модульности в присутствии обобщенных операций требует болеемощных барьеров абстракции, чем тех, что получаются с помощью простой абстракцииданных. А именно, мы вводим программирование, управляемое данными (data-directedprogramming) как метод, который позволяет проектировать представления данных отдельно, а затем сочетать их аддитивно (additively) (т. е., без модификации). Чтобыпроиллюстрировать силу этого подхода к проектированию систем, в завершение главымы применим то, чему в ней научились, к реализации пакета символьной арифметики многочленов, коэффициенты которых могут быть целыми, рациональными числами,комплексными числами и даже другими многочленами.2.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
