Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 32
Текст из файла (страница 32)
Рекурсивные операции right-split и corner-split в применении к рисовалкам wave и rogers. Комбинирование четырех картинок corner-split дает симметричные узоры square-limit, как показано на рисунке 2.9.2.2. Иерархические данные и свойство замыкания139Например, и flipped-pairs, и square-limit располагают определенным образом в виде квадрата четыре копии порождаемого рисовалкой изображения; они отличаются только тем, как они ориентируют эти копии.
Один из способов абстрагироватьтакую схему комбинирования рисовалок представлен следующей процедурой, котораяпринимает четыре одноаргументных операции и порождает операцию над рисовалками,которая трансформирует данную ей рисовалку с помощью этих четырех операций ирасставляет результаты по квадрату. Tl, tr, bl и br — это трансформации, которыеследует применить к верхней левой, верхней правой, нижней левой и нижней правойкопиям, соответственно.(define (square-of-four tl tr bl br)(lambda (painter)(let ((top (beside (tl painter) (tr painter)))(bottom (beside (bl painter) (br painter))))(below bottom top))))Тогда в терминах square-of-four можно определить flipped-pairs следующимобразом24 :(define (flipped-pairs painter)(let ((combine4 (square-of-four identity flip-vertidentity flip-vert)))(combine4 painter)))а square-limit можно выразить как25(define (square-limit painter n)(let ((combine4 (square-of-four flip-horiz identityrotate180 flip-vert)))(combine4 (corner-split painter n))))Упражнение 2.45.Right-split и up-split можно выразить как разновидности общей операции разделения.Определите процедуру split с таким свойством, что вычисление(define right-split (split beside below))(define up-split (split below beside))порождает процедуры right-split и up-split с таким же поведением, как и определенныеранее.24 Мытакже могли бы написать(define flipped-pairs(square-of-four identity flip-vert identity flip-vert))25 Rotate180 поворачивает рисовалку на 180 градусов (см.
упражнение 2.50). Вместо rotate180 мы моглибы сказать (compose flip-vert flip-horiz), используя процедуру compose из упражнения 1.42.Глава 2. Построение абстракций с помощью данных140векторedge2рамкивекторoriginрамкивекторedge1рамкиТочка (0,0) на экранеРис. 2.15. Рамка представляется в виде трех векторов — начальной точки и двух краев.РамкиПрежде, чем мы сможем показать, как реализуются рисовалки и средства их комбинирования, нам нужно рассмотреть рамки. Рамку можно описать как три вектора —вектор исходной точки и два вектора краев рамки. Вектор исходной точки Origin указывает смещение исходной точки рамки от некой абсолютной начальной точки, а векторыкраев Edge1 и Edge2 указывают смещение углов рамки от ее исходной точки.
Есликрая перпендикулярны, рамка будет прямоугольной. В противном случае рамка будетпредставлять более общий случай параллелограмма. На рис. 2.15 показаны рамка и соответствующие ей вектора. В соответствии с принципами абстракции данных, нам поканезачем указывать, каким образом представляются рамки; нужно только сказать, чтоесть конструктор make-frame, который принимает три вектора и выдает рамку, и чтоесть еще три селектора, origin-frame, edge1-frame и edge2-frame (см. упражнение 2.47).Для определения изображений мы будем использовать координаты в единичномквадрате (0 ≤ x, y ≤ 1).
Каждой рамке мы сопоставляем отображение координат рамки (frame coordinate map), которое будет использоваться, чтобы сдвигать и масштабировать изображения так, чтобы они умещались в рамку. Это отображение трансформируетединичный квадрат в рамку, переводя вектор v = (x, y) в сумму векторовOrigin(Frame) + x · Edge1 (Frame) + y · Edge2 (Frame)Например, (0, 0) отображается в исходную точку рамки, (1, 1) в вершину, противоположную исходной точке по диагонали, а (0.5, 0.5) в центр рамки. Мы можем создатьотображение координат рамки при помощи следующей процедуры26 :(define (frame-coord-map frame)(lambda (v)26 Frame-coord-map использует векторные операции, определенные ниже в упражнении 2.46, и мы предполагаем, что они реализованы для какого-нибудь представления векторов. Благодаря абстракции данных,неважно, каково это представление; нужно только, чтобы операции над векторами вели себя правильно.2.2. Иерархические данные и свойство замыкания141(add-vect(origin-frame frame)(add-vect (scale-vect (xcor-vect v)(edge1-frame frame))(scale-vect (ycor-vect v)(edge2-frame frame))))))Заметим, что применение frame-coord-map к рамке дает нам процедуру, которая,получая вектор, возвращает тоже вектор.
Если вектор-аргумент находится в единичномквадрате, вектор-результат окажется в рамке. Например,((frame-coord-map a-frame) (make-vect 0 0))возвращает тот же вектор, что и(origin-frame a-frame)Упражнение 2.46.Двумерный вектор v, идущий от начала координат к точке, можно представить в виде пары,состоящей из x-координаты и y-координаты. Реализуйте абстракцию данных для векторов, написавконструктор make-vect и соответствующие селекторы xcor-vect и ycor-vect.
В терминахсвоих селекторов и конструктора реализуйте процедуры add-vect, sub-vect и scale-vect,которые выполняют операции сложения, вычитания векторов и умножения вектора на скаляр:(x1 , y1 ) + (x2 , y2 ) = (x1 + x2 , y1 + y2 )(x1 , y1 ) − (x2 , y2 ) = (x1 − x2 , y1 − y2 )s · (x, y) = (sx, sy)Упражнение 2.47.Вот два варианта конструкторов для рамок:(define (make-frame origin edge1 edge2)(list origin edge1 edge2))(define (make-frame origin edge1 edge2)(cons origin (cons edge1 edge2)))К каждому из этих конструкторов добавьте соответствующие селекторы, так, чтобы получитьреализацию рамок.РисовалкиРисовалка представляется в виде процедуры, которая, получая в качестве аргументарамку, рисует определенное изображение, отмасштабированное и сдвинутое так, чтобыуместиться в эту рамку.
Это означает, что если есть рисовалка p и рамка f, то мыможем получить изображение, порождаемое p, в f, позвав p с f в качестве аргумента.Детали того, как реализуются элементарные рисовалки, зависят от конкретных характеристик графической системы и типа изображения, которое надо получить. Например, пусть у нас будет процедура draw-line, которая рисует на экране отрезок между142Глава 2. Построение абстракций с помощью данныхдвумя указанными точками.
Тогда мы можем создавать из списков отрезков рисовалкидля изображений, состоящих из этих отрезков, вроде рисовалки wave с рисунка 2.10,таким образом27 :(define (segments->painter segment-list)(lambda (frame)(for-each(lambda (segment)(draw-line((frame-coord-map frame) (start-segment segment))((frame-coord-map frame) (end-segment segment))))segment-list)))Отрезки даются в координатах по отношению к единичному квадрату.
Для каждого сегмента в списке рисовалка преобразует концы отрезка с помощью отображения координатрамки и рисует отрезок между точками с преобразованными координатами.Представление рисовалок в виде процедур воздвигает в языке построения изображений мощный барьер абстракции. Мы можем создавать и смешивать множество типовэлементарных рисовалок, в зависимости от имеющихся возможностей графики. Деталиих реализации несущественны.
Любая процедура, если она принимает в качестве аргумента рамку и рисует в ней что-нибудь должным образом отмасштабированное, можетслужить рисовалкой28 .Упражнение 2.48.Направленный отрезок на плоскости можно представить в виде пары векторов: вектор от началакоординат до начала отрезка и вектор от начала координат до конца отрезка. Используйте своепредставление векторов из упражнения 2.46 и определите представление отрезков с конструкторомmake-segment и селекторами start-segment и end-segment.Упражнение 2.49.С помощью segments->painter определите следующие элементарные рисовалки:а. Рисовалку, которая обводит указанную рамку.б.
Рисовалку, которая рисует «Х», соединяя противоположные концы рамки.в. Рисовалку, которая рисует ромб, соединяя между собой середины сторон рамки.г. Рисовалку wave.27 Процедура segments->painter использует представление отрезков прямых, описанное ниже в упражнении 2.48. Кроме того, она использует процедуру for-each, описанную в упражнении 2.23.28 Например, рисовалка rogers с рисунка 2.11 была получена из полутонового черно-белого изображения.Для каждой точки в указанной рамке рисовалка rogers определяет точку исходного изображения, которая внее отображается, и соответствующим образом ее окрашивает. Разрешая себе иметь различные типы рисовалок, мы пользуемся идеей абстрактных данных, описанной в разделе 2.1.3, где мы говорили, что представлениерациональных чисел может быть каким угодно, пока соблюдается соответствующее условие.
Здесь мы используем то, что рисовалку можно реализовать как угодно, лишь бы она что-то изображала в указанной рамке. Вразделе 2.1.3 показывается и то, как реализовать пары в виде процедур. Рисовалки — это наш второй примерпроцедурного представления данных.2.2. Иерархические данные и свойство замыкания143Преобразование и комбинирование рисовалокОперации над рисовалками (flip-vert или beside, например) создают новые рисовалки, которые вызывает исходные рисовалки по отношению к рамкам, производнымот рамок-аргументов. Таким образом, скажем, flip-vert не требуется знать, как работает рисовалка, чтобы перевернуть ее — ей нужно только уметь перевернуть рамкувверх ногами: перевернутая рисовалка просто использует исходную, но в обращеннойрамке.Операции над рисовалками основываются на процедуре transform-painter, которая в качестве аргументов берет рисовалку и информацию о том, как преобразоватьрамку, а возвращает новую рисовалку.
Когда преобразованная рисовалка вызывается поотношению к какой-либо рамке, она преобразует рамку и вызывает исходную рисовалкупо отношению к ней. Аргументами transform-painter служат точки (представленные в виде векторов), указывающие углы новой рамки: будучи отображенной на рамку,первая точка указывает исходную точку новой рамки, а две других — концы краевыхвекторов. Таким образом, аргументы, лежащие в пределах единичного квадрата, определяют рамку, которая содержится внутри исходной рамки.(define (transform-painter painter origin corner1 corner2)(lambda (frame)(let ((m (frame-coord-map frame)))(let ((new-origin (m origin)))(painter(make-frame new-origin(sub-vect (m corner1) new-origin)(sub-vect (m corner2) new-origin)))))))Вот как перевернуть изображение в рамке вертикально:(define (flip-vert painter)(transform-painter painter(make-vect 0.0 1.0); новая исходная точка(make-vect 1.0 1.0); новый конец edge1(make-vect 0.0 0.0))) ; новый конец edge2При помощи transform-painter нам нетрудно будет определять новые трансформации.Например, можно определить рисовалку, которая рисует уменьшенную копию исходногоизображения в верхней правой четверти рамки:(define (shrink-to-upper-right painter)(transform-painter painter(make-vect 0.5 0.5)(make-vect 1.0 0.5)(make-vect 0.5 1.0)))Вот трансформация, которая поворачивает изображение на 90 градусов против часовойстрелки29 :29 Rotate90 представляет собой чистый поворот только для квадратных рамок, поскольку она еще растягивает и сплющивает изображение так, чтобы оно уместилось в повернутой рамке.144Глава 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
