Структура и интерпретация компьютерных программ: заметки и решения
В примечании 34 описывается особая форма quote и идентичность ее действия кавычке. Кроме того, указывается, что знак кавычки является просто сокращением для формы quote. Таким образом запись
(car ''abracadabra)
является лишь сокращенной формой записи для выражения
(car (quote (quote abracadabra)))
Первая quote заставляет интерпретатор понимать остаток записи буквально как список. Вполне очевидно, что для этого списка операция car возвращает символ quote.
В соответствии с примечанием реализуем процедуру equal? таким образом, чтобы она корректно работала и с числами тоже. Отметим также, что мы считаем два пустых списка эквивалентными.
Процедуру equal? можно определить таким образом:
(define (equal? a b) (or (and (null? a) (null? b)) (and (number? a) (number? b) (= a b)) (and (symbol? a) (symbol? b) (eq? a b)) (and (pair? a) (pair? b) (equal? (car a) (car b)) (equal? (cdr a) (cdr b)))))
Здесь я обошелся без конструкции cond, хотя можно было бы использовать при реализации и ее.
Это простое упражнение, проверяющее степень усвоения базового материала об использовании кавычки для представления символьных данных. Ответы приведены ниже:
> (list 'a 'b 'c) (a b c)
> (list (list 'george)) ((george))
> (cdr '((x1 x2) (y1 y2))) ((y1 y2))
> (cadr '((x1 x2) (y1 y2))) (y1 y2)
> (pair? (car '(a short list))) #f
> (memq 'red '((red shoes) (blue socks))) #f
> (memq 'red '(red shoes blue socks)) (red shoes blue socks)
Думаю, комментарии излишни.
Описанные в каждом из пунктов упражнения изменения можно внести в результат, переопределив соответствующие процедуры указанным ниже образом:
(define wave-painter (segments->painter (append (polyline (make-vect 0 0.15) (make-vect 0.15 0.4) (make-vect 0.3 0.35) (make-vect 0.4 0.35) (make-vect 0.35 0.15) (make-vect 0.4 0)) (polyline (make-vect 0.6 0) (make-vect 0.65 0.15) (make-vect 0.6 0.35) (make-vect 0.75 0.35) (make-vect 1 0.65)) (polyline (make-vect 1 0.85) (make-vect 0.6 0.55) (make-vect 0.75 1)) (polyline (make-vect 0.6 1) (make-vect 0.5 0.7) (make-vect 0.4 1)) (polyline (make-vect 0.25 1) (make-vect 0.35 0.5) (make-vect 0.3 0.4) (make-vect 0.15 0.6) (make-vect 0 0.35)) (polyline (make-vect 0.45 0.25) (make-vect 0.5 0.3) (make-vect 0.55 0.25)))))
(define (corner-split painter n) (if (= n 0) painter (let ((up (up-split painter (- n 1))) (right (right-split painter (- n 1)))) (let ((corner (corner-split painter (- n 1)))) (beside (below painter up) (below right corner))))))
(define (square-limit painter n) (let ((combine4 (square-of-four flip-vert rotate180 identity flip-vert))) (combine4 (corner-split painter n))))
В wave-painter я просто добавил еще одну ломаную (последнюю) для улыбки. Два других пункта выполнены точно в соответствии с рекомендациями из условия упражнения.
Обратите внимание, что в первом случае мы вносим изменение на уровне рисовалки. Во втором случае мы меняем операцию над рисовалками. В третьем случае мы перекомбинируем операции над рисовалками, то есть работаем на еще более высоком уровне.
Определение below напрямую абсолютно аналогично определению beside. Отличия только в том, как происходит разбиение исходной рамки на две. В beside исходная рамка (0.0, 0.0) - (1.0, 1.0) разбивается на две по вертикали : (0.0, 0.0) - (0.5, 1.0) и (0.5, 0.0) - (1.0, 1.0). В below та же исходная рамка разбивается несколько иначе (по горизонтали): (0.0, 0.0) - (1.0, 0.5) и (0.0, 0.5) - (1.0, 1.0). Соответсвенно меняется split-point и координаты векторов. Результат выглядит так:
(define (below painter1 painter2) (let ((split-point (make-vect 0.0 0.5))) (let ((paint-bottom (transform-painter painter1 (make-vect 0.0 0.0) (make-vect 1.0 0.0) split-point)) (paint-top (transform-painter painter2 split-point (make-vect 1.0 0.5) (make-vect 0.0 1.0)))) (lambda (frame) (paint-bottom frame) (paint-top frame)))))
Теперь более интересная часть - определение below через beside и операции вращения. Несложно заметить, что результат below это почти повернутый на 90 градусов результат beside. Проблема, однако, в этом почти. Изображения в каждой из половин также поворачиваются на 90 градусов, что нам совершенно не нужно. Но эту проблему можно легко решить. Достаточно просто предварительно повернуть каждое из них на 90 градусов в противоположную сторону. На схеме ниже представлено два варианта действий, отличающихся порядком поворотов (по часовой или против часовой стрелки). Кликните на картинке для просмотра в увеличенном виде.
Вспоминая теперь, что поворот на 90 градусов по часовой стрелке - это то же, что поворот на 270 градусов против часовой стрелки, можем записать такие два определения для below:
(define (below painter1 painter2) (rotate-90 (beside (rotate-270 painter1) (rotate-270 painter2))))
(define (below painter1 painter2) (rotate-270 (beside (rotate-90 painter2) (rotate-90 painter1))))
Все просто и красиво.
Для горизонтального отражения и поворотов на 180 и 270 градусов против часовой стрелки будем также применять transform-painter. Схематически каждое из этих преобразований обозначено на рисунке ниже:
Думаю, чертеж объясняет в даном случае лучше слов. Таким образом мы легко получаем следующие определения процедур:
(define (flip-horiz painter) (transform-painter painter (make-vector 1.0 0.0) (make-vector 0.0 0.0) (make-vector 1.0 1.0)))
(define (rotate-180 painter) (transform-painter painter (make-vector 1.0 1.0) (make-vector 0.0 1.0) (make-vector 1.0 0.0)))
(define (rotate-270 painter) (transform-painter painter (make-vector 0.0 1.0) (make-vector 0.0 0.0) (make-vector 1.0 1.0)))
Все делается аналогично повороту на 90 градусов.
Сначала простое. Рисовалка, обводящая рамку просто строит 4 отрезка, которые являются сторонами рамки, то есть соединяют точки (0, 0), (1, 0), (1, 1) и (0, 1):
(define outline-painter (segments->painter (list (make-segment (make-vect 0 0) (make-vect 1 0)) (make-segment (make-vect 1 0) (make-vect 1 1)) (make-segment (make-vect 1 1) (make-vect 0 1)) (make-segment (make-vect 0 1) (make-vect 0 0)))))
Рисовалка, соединяющая противоположные концы рамки еще проще:
(define X-painter (segments->painter (list (make-segment (make-vect 0 0) (make-vect 1 1)) (make-segment (make-vect 1 0) (make-vect 0 1)))))
Ромб - это контур с вершинами в точках (0.5, 0), (1, 0.5), (0.5, 1) и (0, 0.5):
(define diamond-painter (segments->painter (list (make-segment (make-vect 0.5 0) (make-vect 1 0.5)) (make-segment (make-vect 1 0.5) (make-vect 0.5 1)) (make-segment (make-vect 0.5 1) (make-vect 0 0.5)) (make-segment (make-vect 0 0.5) (make-vect 0.5 0)))))
Для того, чтобы построить рисовалку wave, нам нужно будет пострить 17 отрезков. Для сокращения записи введем две вспомогательные процедуры:
Определения этих процедур выглядят так:
(define (polyline vectors) (if (null? (cdr vectors)) null (cons (make-segment (car vectors) (cadr vectors)) (polyline (cdr vectors)))))
(define (contour vectors) (polyline (append vectors (list (car vectors)))))
Идея процедуры contour в том, что контур - это ломаная линия, к которой начальная точка добавлена еще раз в конец.
Теперь мы можем укоротить с помощью этих новых процедур рисовалки outline-painter и diamond-painter:
(define outline-painter (segments->painter (contour (list (make-vect 0 0) (make-vect 1 0) (make-vect 1 1) (make-vect 0 1))))) (define diamond-painter (segments->painter (contour (list (make-vect 0.5 0) (make-vect 1 0.5) (make-vect 0.5 1) (make-vect 0 0.5)))))
Рисовалка wave может быть записана таким образом (обратите внимание, как я объединяю 5 ломаных линий, составляющих изображение в набор отрезков):
(define wave-painter (segments->painter (append (polyline (make-vect 0 0.15) (make-vect 0.15 0.4) (make-vect 0.3 0.35) (make-vect 0.4 0.35) (make-vect 0.35 0.15) (make-vect 0.4 0)) (polyline (make-vect 0.6 0) (make-vect 0.65 0.15) (make-vect 0.6 0.35) (make-vect 0.75 0.35) (make-vect 1 0.65)) (polyline (make-vect 1 0.85) (make-vect 0.6 0.55) (make-vect 0.75 1)) (polyline (make-vect 0.6 1) (make-vect 0.5 0.7) (make-vect 0.4 1)) (polyline (make-vect 0.25 1) (make-vect 0.35 0.5) (make-vect 0.3 0.4) (make-vect 0.15 0.6) (make-vect 0 0.35)))))
Координаты векторов взяты приближенно (но достаточно правдоподобно) по исходному рисунку.
Снова будем для представления направленного отрезка пару. На этот раз элементами пары будут вектора к началу и концу отрезка из начала координат.
Конструктор и селекторы будут такими:
(define (make-segment start end) (cons start end)) (define (start-segment segment) (car segment)) (define (end-segment segment) (cdr segment))
Итак, селекторы для первого варианта представления рамки записываются следующим образом:
(define (origin-frame frame) (car frame)) (define (edge1-frame frame) (cadr frame)) (define (edge2-frame frame) (caddr frame))
Селекторы для второго варианта выглядят так:
(define (origin-frame frame) (car frame)) (define (edge1-frame frame) (cadr frame)) (define (edge2-frame frame) (cddr frame))
Как видим, отличие лишь в последнем селекторе, что легко пояснить тем, что конструкция
(cons a1 (cons a2 … (cons ak-1 ak) …))
лишь чуть-чуть отличается от
(list a1 a2 … ak-1 ak),
которая всего лишь является краткой формой записи для
(cons a1 (cons a2 … (cons ak-1 (cons ak nil)) …)).
Это упражнение не вызовет труда у тех, кто разобрался с концепциями барьеров абстракции, конструкторов и селекторов.
Для представления векторов я выбрал пары. Можно было бы избрать и альтернативную форму, например списки, что было бы более удобно при работе с многомерными векторами. Но в случае двумерного пространства пара видится простейшим способом представления.
Конструктор и селекторы для векторов выглядят следующим образом:
(define (make-vect x y) (cons x y)) (define (xcor-vect v) (car v)) (define (ycor-vect v) (cdr v))
Операции над векторами определяются так:
(define (add-vect u v)
(make-vect (+ (xcor-vect u) (xcor-vect v))
(+ (ycor-vect u) (ycor-vect v))))
(define (sub-vect u v)
(make-vect (- (xcor-vect u) (xcor-vect v))
(- (ycor-vect u) (ycor-vect v))))
(define (scale-vect s v)
(make-vect (* s (xcor-vect v))
(* s (ycor-vect v))))
Операции также можно было бы обобщить на случай многомерных векторов.
