SICP по-русски

Я уже упоминал о замечательных видео лекциях по материалам курса “Структура и интерпретация компьютерных программ”. Лекции отлично дополняют текст книги и делают многие вещи более понятными. Смотреть их очень интересно.

Для русскоязычного человека в них есть только один недостаток: они на английском языке, и у многих будут трудности с восприятием информации на слух. В связи с этим я задумал сделать субтитры для этих лекций, так как визуально английский текст воспринимается легче.
Субтитры я планирую выкладывать на специальном ресурсе sicptitles.org. На данный момент там доступны англоязычные субтитры для лекции 1-А. В планах сделать англоязычные, русскоязычные, а также иноязычные субтитры ко всем лекциям.

Естественно, самостоятельно я эту работу не потяну. На подготовку субтитров к первой лекции пришлось потратить много вечеров, а это только одна лекция из 20 и только на одном языке. Поэтому мне необходима ваша помощь. Если вы хотите принять участие в проекте по созданию субтитров к SICP, сообщите, пожалуйста.

Сайт проекта я уже упомянул. Также я создал группу для общения и решения технических вопросов - sicp-subtitles на Google Groups.

Какая помощь нужна:

• создание английских субтитров на слух;
• создание русских субтитров по англоязычному оригиналу (перевод английских субтитров на русский язык) с сохранением тайминга;
• вычитка субтитров;
• любая другая.

В частности, по первой лекции у меня осталось 5 моментов, где я не смог воспринять на слух речь Харольда Абельсона. Эти моменты помечены символами <???> и находятся на в таких местах (указываю время в формате часы:минуты:секунды с начала лекции):

1. 00:05:44,
2. 00:09:33,
3. 00:36:47,
4. 01:02:30,
5. 01:11:45.

Если подскажете мне, что же там все-таки звучит, буду чрезвычайно признателен, потому что я эти фразы слушать без содрогания уже не могу

Эта статья - первый анонс проекта субтитров. Надеюсь, что смогу найти единомышленников среди читателей. Любые замечания и вопросы приветствуются.

Если есть необходимость, я могу отдельно описать, как подключать субтитры так, чтобы они показывались в проигрывателе.

Жду вас на sicptitles, в группе и комментариях. Сделаем доброе дело вместе!

Сказать, какой смысл определять комплексные числа с действительными и мнимыми частями, не являющимися действительными числами, мне трудно. Тем не менее, легко представить, что в системе существует несколько различных представлений действительных чисел (например, различающихся точностью и объемом требуемой памяти). В таком случае задача имеет смысл.

Я не буду приводить весь код модифицированной системы, а просто укажу какие изменения и где потребуется внести.

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

;install-complex-package
(define (add-complex z1 z2)
  (make-from-real-imag (add (real-part z1) (real-part z2))
                       (add (imag-part z1) (imag-part z2))))
(define (sub-complex z1 z2)
  (make-from-real-imag (sub (real-part z1) (real-part z2))
                       (sub (imag-part z1) (imag-part z2))))
(define (mul-complex z1 z2)
  (make-from-mag-ang (mul (magnitude z1) (magnitude z2))
                     (add (angle z1) (angle z2))))
(define (div-complex z1 z2)
  (make-from-mag-ang (div (magnitude z1) (magnitude z2))
                     (sub (angle z1) (angle z2))))

;install-rectangular-package
(define (magnitude z)
  (sqrt (add (square (real-part z))
             (square (imag-part z)))))
(define (make-from-mag-ang r a)
  (cons (mul r (cosine a)) (mul r (sine a))))

;install-polar-package
(define (real-part z)
  (mul (magnitude z) (cosine (angle z))))
(define (imag-part z)
  (mul (magnitude z) (sine (angle z))))
(define (make-from-real-imag x y)
  (cons (sqrt (add (square x) (square y)))
        (arctan y x)))

Обратите внимание, на то, что имена тригонометрических процедур изменились. Это неспроста!

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

Операции, которые требуется сделать обобщенными:

• square
• sqrt
• sin
• cos
• atan

На самом деле square и sqrt можно и не делать обобщенными операциями, а просто заменить в их определениях арифметические операции на обобщенные. Например, так:

(define (square x)
  (mul x x))
(define (average x y)
  (div (add x y) 2.0))
(define (sqrt x)
  (fixed-point (average-damp (lambda (y) (div x y)))
               1.0))

Однако при этом константы 1.0 и 2.0 (или любые другие типизированные константы) вынудят систему приводить типы.

Описывать реализацию sin, cos и atan как обобщенных операций полностью я не буду. Она абсолютно аналогична ранее введенным обобщенным операциям. Так же добавляются определения обобщенных процедур (они будут называться несколько иначе: sine, cosine и arctan) через apply-generic и конкретные процедуры для каждого типа добавляются с помощью put в таблицу типов в каждом пакете. Для обычных чисел это будет выглядеть так:

;generic functions
(define (sine x) (apply-generic 'sine x))
(define (cosine x) (apply-generic 'cosine x))
(define (arctan x) (apply-generic 'arctan x))

;install-scheme-number-package
(put 'sine '(scheme-number) (lambda (x) (tag (sin x))))
(put 'cosine '(scheme-number) (lambda (x) (tag (cos x))))
(put 'arctan '(scheme-number scheme-number) (lambda (x y) (tag (atan x y))))

Для других типов все аналогично и выписать реализацию несложно.

Определение операции проецирования project похоже на определение операции raise.

Мы также вводим обобщенную операцию:

(define (project x) (apply-generic 'project x))

и добавляем в пакеты соответствующие строки, реализующие для каждого типа в башне проецирование на предыдущий:

;integer package

;rational package
(define (rational->integer r)
  (make-integer (round (/ (numer r) (denom r)))))
(put 'project '(rational) rational->integer)

;real package
(define (real->rational x)
  (make-rational (numerator x) (denominator x)))
(put 'project '(real) real->rational)

; complex package
(define (complex->real z)
  (make-real (real-part z)))
(put 'project '(complex) complex->real)

Преобразование комплексного числа к действительному и рационального к целому особых трудностей не вызывает, а вот получить из действительного числа рациональное уже сложнее. Первоначально я хотел выбросить рациональные числа из башни и сделать упражение без них, но потом подглядел у Эли Бендерски, что в Scheme есть встроенные процедуры numerator и denominator, которые получают числитель и знаменатель по действительному числу. Это как раз то, что мне было нужно для получения рационального числа из действительного.

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

(define (drop x)
  (let ((op (get 'project (type-tag x))))
    (if op
        (let ((p (project x)))
          (if (equ? x (raise p))
              (drop p)
              x))
        x)))

Для того, чтобы внедрить упрощение результатов операций с помощью drop в apply-generic достаточно просто обернуть в drop результат вызова apply. Соответствующая строчка будет иметь вид:

(drop (apply proc (map contents args)))

Больше никаких изменений apply-generic не требует.

Для простоты я буду рассматривать вариант приведения типов только для бинарных операций, который соответствует рассмотренному в основном тексте книги варианту apply-generic.

Я модифицирую процедуру apply-generic следующим образом: если операции для двух аргументов заданных типов не нашлось, я сравню их типы. Если типы одинаковы, я попытаюсь поднять оба аргумента по башне типов и, если это возможно, выполнить операцию на поднятых таким образом аргументах. Если же один из типов находится выше другого в иерархии, я подниму более низкий на один уровень вверх по иерархии и выполню операцию. Наконец, если типы аргументов несопоставимы, то есть не принадлежат одной башне типов, я немедленно выдам сообщение об ошибке.

Процедура apply-generic, реализующая описанную идею, приведена ниже:

(define (apply-generic op . args)
  (let ((type-tags (map type-tag args)))
    (let ((proc (get op type-tags)))
      (if proc
          (apply proc (map contents args))
          (if (= (length args) 2)
              (let ((a1 (car args))
                    (a2 (cadr args)))
                (let ((ra1 (raise a1))
                      (ra2 (raise a2)))
                  (cond ((eq? (type-tag a1) (type-tag a2))
                         (if (and ra1 ra2)
                             (apply-generic op ra1 ra2)
                             (error "Нет метода для этих типов"
                                    (list op type-tags))))
                        ((higher? a1 a2)
                         (apply-generic op a1 ra2))
                        ((higher? a2 a1)
                         (apply-generic op ra1 a2))
                        (else (error "Нет метода для этих типов"
                                     (list op type-tags))))))
              (error "Нет метода для этих типов"
                     (list op type-tags)))))))

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

(define (higher? a1 a2)
  (let ((ra2 (raise a2)))
    (and ra2
         (or (eq? (type-tag a1) (type-tag ra2))
             (higher? a1 ra2)))))

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

Евгений Кирпичев с февраля этого года читает в ИТМО СПбГУ спецкурс, основанный на книге и видео-лекциях “Структура и интерпретация компьютерных программ”. Планы своих лекций Евгений выложил в открытый доступ на вики питерской Haskell User Group. Пока что доступны две первые лекции:

Лекция 1. Основы лямбда-исчисления и лиспа. Итерация и рекурсия.
Лекция 2. Функции высшего порядка и данные.

К сожалению, в данный момент на сайте есть проблема с кодировкой. Если вы видите слишком много вопросительных знаков вместо осмысленных сочетаний символов, установите явно кодировку Windows-1251.

Начнем с обобщенной процедуры raise, которая будет поднимать объект на один уровень в башне типов. Она записывается абсолютно аналогично остальным обобщенным операциям:

(define (raise x) (apply-generic 'raise x))

Просто. Но для того, чтобы она заработала, необходимо определить конкретные реализации подъема типа в башне для всех типов, кроме последнего, самого верхнего в иерархии. Мне кажется, что помещать соответствующие процедуры подъема объекта типа А к находящемуся непосредственно над ним в башне типу В лучше в пакете, описывающем тип В, так как именно более общий тип должен заботиться о приведении к себе частных. Впрочем, возможно, есть и лучшее решение.

Итак, в пакет для работы с целыми числами (integer) мы не включаем ничего.

В пакет для работы с рациональными числами (rational) включаем строки:

(define (integer->rational n)
  (make-rational n 1))
(put 'raise '(integer) integer->rational)

В пакет для работы с действительными числами (real) включаем:

(define (rational->real r)
  (make-real (/ (numer r) (denom r))))
(put 'raise '(rational) rational->real)

Пакет комплексных чисел (complex) дополняем так:

(define (real->complex x)
  (make-complex-from-real-imag x 0))
(put 'raise '(real) real->complex)

Все. Теперь подъем по иерархии типов с помощью raise будет работать.

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

Реализация этой идеи в виде процедур приводится ниже:
(define (coerce arg type)
  (if (eq? (type-tag arg) type)
      arg
      (let ((arg->type (get-coercion (type-tag arg) type)))
        (if arg->type
            (arg->type arg)
            false))))

(define (coerce-all args type)
  (if (null? args)
      '()
      (let ((first (coerce (car args) type))
            (rest (coerce-all (cdr args) type)))
        (if (and first rest)
            (cons first rest)
            false))))

(define (apply-with-coercion op args types)
  (if (null? types)
      (error "Нет метода для этих типов"
             (list op types))
      (let ((type (car types)))
        (let ((coerced-args (coerce-all args type)))
          (if coerced-args
              (apply apply-generic (cons op coerced-args))
              (apply-with-coercion op args (cdr types)))))))

(define (apply-generic op . args)
  (let ((type-tags (map type-tag args)))
    (let ((proc (get op type-tags)))
      (if proc
          (apply proc (map contents args))
          (apply-with-coercion op args type-tags)))))

Процедура apply-generic использует процедуру apply-with-coercion, которая  пытается найти подходящую операцию для аргументов, приведенных к одному типу из набора. Та в свою очередь использует coerce-all, которая приводит все аргументы к заданному типу (либо возвращает ложь, если это невозможно). coerce-all использует процедуру coerce для приведения одного аргумента к заданному типу.

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

Почему так происходит? Потому что apply-generic сначала попытается найти процедуру возведения в степень, заданную для комплексного и целого аргументов. Такой операции в таблице типов нет, поэтому будут предприняты попытки приведения типов. Сначала попытаемся привести тип второго аргумента к типу первого. Предположим, это удается, так как целое в принципе можно привести к комплексному. Однако операции возведения в степень для двух комплексных чисел у нас в системе нет. Теперь попытаемся привести первый аргумент к типу второго. Это не получается, так как комплексное число в общем случае не приводится к целому.

В то же время, мы могли бы привести второй целочисленный аргумент к рациональному типу и найти имеющуюся операцию.

Идея Хьюго о добавлении процедур приведения типов к самим себе, скажем так, не слишком светлая.

а. Посмотрим, что происходит при вызове обобщенной процедуры exp, определенной только для обычных чисел, с двумя комплексными параметрами в случае, когда заданы процедуры приведения типов к себе, предложенные Хьюго. Сначала exp вызовет apply-generic для операции exp и двух комплексных чисел. apply-generic не найдет подходящую обобщенную процедуру по этой операции и типам и попытается привести типы аргументов. У нее получится осуществить приведение типа первого аргумента к типу второго (complex к complex), а следоавтельно она рекурсивно запустит себя же для тех же типов. Мы пришли к тому же, с чего начинали. Таким образом произойдет зацикливание. Это явно не то, что нам нужно.

б. Получается, предложенным Хьюго способом проблему не решить. Что же делать? Прежде всего, определим, существует ли вообще проблема. В каком случае может потребоваться приведение типа к себе же? Только в случае вызова apply-generic с однотипными аргументами, причем в ситуации, когда процедура для этого типа не задана. Если процедуры приведения типа к себе нет, то особой беды не произойдет, разве что может пострадать эффективность. А вот если кто-то добавит такую процедуру приведения, то наша система может встретиться с серьезными трудностями, например зацикливанием, как показано выше. Было бы более безопасно, если бы apply-generic не пыталась привести тип к самому себе в принципе.

в. Измененный вариант процедуры apply-generic, не выполняющий приведение типов в случае, когда типы операндов совпадают, представлен ниже:

(define (apply-generic op . args)
  (let ((type-tags (map type-tag args)))
    (let ((proc (get op type-tags)))
      (if proc
          (apply proc (map contents args))
          (if (= (length args) 2)
              (let ((type1 (car type-tags))
                    (type2 (cadr type-tags))
                    (a1 (car args))
                    (a2 (cadr args)))
                (if (eq? type1 type2)
                    (error "Нет метода для этих типов"
                           (list op type-tags))
                    (let ((t1->t2 (get-coercion type1 type2))
                          (t2->t1 (get-coercion type2 type1)))
                      (cond (t1->t2
                             (apply-generic op (t1->t2 a1) a2))
                            (t2->t1
                             (apply-generic op a1 (t2->t1 a2)))
                            (else
                             (error "Нет метода для этих типов"
                                    (list op type-tags)))))))
              (error "Нет метода для этих типов"
                     (list op type-tags)))))))

Реально я добавил лишь одну строчку проверки условия равенства типов (eq? type1 type2) и сообщение об ошибке.

Это упражнение аналогично предыдущему, поэтому буду краток, но остановлюсь на интересных деталях.

Обобщенная процедура =zero? определяется следующим типичным образом:
(define (=zero? x) (apply-generic '=zero? x))

В пакет для работы с обычными числами добавляем строки:

(define (=zero? x) (= x 0))
(put '=zero? '(scheme-number) =zero?)

В пакет рациональных чисел добавляем:

(define (=zero? x) (= (numer x) 0))
(put '=zero? '(rational) =zero?)

В пакет комплексных чисел включаем строки:

(define (=zero? x)
  (and (= (real-part x) 0)
       (= (imag-part x) 0)))
(put '=zero? '(complex) =zero?)

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

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

Еще один способ определения внутренних процедур - помещать их как безымянные lambda-опредления прямо внутрь put.

Я продемонстрирую кратко совмещение последних двух подходов:

;install-scheme-number-package:
(put '=zero?
     '(scheme-number)
     (lambda (x) (= x 0)))

;install-rational-package:
(put '=zero?
     '(rational)
     (lambda (x) (=zero? (numer x))))

;install-complex-package:
(put '=zero?
     '(complex)
     (lambda (x) (and (=zero? (real-part x))
                      (=zero? (imag-part x)))))

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

Первым делом, определим саму обобщенную операцию проверки эквивалентности equ?. Мы еще не определяли обобщенных операций, являющихся предикатами. Но никаких сложностей с этим не возникает, ведь предикат - это всего лишь частный случай обыкновенной процедуры, который возвращает булево значение (истина или ложь). Таким образом определяется обобщенный предикат так же, как любая обобщенная операция:
(define (equ? x y) (apply-generic 'equ? x y))

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

Для того, чтобы реализовать equ? для каждого типа чисел, добавим в install-scheme-number-package следующий код:
(put 'equ? '(scheme-number scheme-number) =)

В install-rational-package аналогично добавим (процедура equal-rat? взята один в один из раздела 2.1.1 без модификаций):

(define (equal-rat? x y)
  (= (* (numer x) (denom y))
     (* (numer y) (denom x))))
(put 'equ? '(rational rational) equal-rat?)

В install-complex-package добавим такие строки:

(define (equal-complex? x y)
  (and (= (real-part x) (real-part y))
       (= (imag-part x) (imag-part y))))
(put 'equ? '(complex complex) equal-complex?)


Все. Теперь наша обобщенная операция equ? будет работать при сравнении пар обыкновенных, рациональных либо действительных чисел. Правда, сравнить обыкновенный 0 с рациональным 0/1 или комплексным 0+0i не получится. Пока что. Следующий раздел книги 2.5.2 как раз об этом…