SICP по-русски

Для того, чтобы получить уменьшение вдвое числа шагов, необходимого для добавления элемента во множество, представленное в виде неупорядоченного списка, нам недостаточно просто определить, есть ли элемент во множестве с помощью element-of-set?, а затем добавить его подобно тому, как мы делали для множеств, представленных неупорядоченными списками. В этом случае поиск и вставка потребуют в среднем по n/2 шагов, где n - число элементов множества. В старом варианте поиск потребовал бы n шагов, зато вставка была бы одношаговой. Таким образом выходит обмен шила на мыло.

Мы пойдем другим путем: объединим проверку нахождения элемента во множестве с добавлением элемента. Воспользуемся упорядоченностью списка. Если элемент x содержится во множестве, то он должен находиться в списке раньше, чем любой элемент, больший его. Таким образом мы просто будем идти по элементам списка, пока не встретим среди них либо x, либо какой-нибудь y больший x. Если мы встретили x, то просто вернем исходное множество без изменений. Если же нам встретился y, а x не встретился до него, то значит x в списке (и множестве, им представленном) отсутствует и должен быть добавлен непосредственно перед y.

Процедура, реализующая этот подход, представлена ниже:

(define (adjoin-set x set)
  (cond ((null? set) (list x))
        ((= x (car set)) set)
        ((< x (car set)) (cons x set))
        (else (cons (car set) (adjoin-set x (cdr set))))))

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

Мы делаем число шагов, пропорциональное позиции наименьшего элемента, не меньшего x, в списке. В среднем оно будет равно половине длины списка.

Очень показательное упражнение, которое одновременно является достаточно простым. SICP продолжает радовать.

Итак, как будут выглядеть операции проверки принадлежности множеству, добавления элемента, пересечения и объединения множеств в случае, если элементы в списке, представляющем множество, могут повторяться?

Во-первых, я хочу заметить, что мы можем вообще ничего не менять: старые операции работают корректно и на новом представлении множеств. Но это не единственный способ задать операции для такого внутреннего представления. Мы можем более вольно обращаться с операциями, создающими большие множества из меньших. Я имею в виду операции adjoin-set и union-set. Если операции element-of-set? и intersection-set мы оставим без изменений, то  adjoin-set и union-set можно сильно упростить, аж до неприличия:

(define (adjoin-set x set)
  (cons x set))

(define (union-set set1 set2)
  (append set1 set2))

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

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

Число шагов, требующихся для операций element-of-set?, пропорционально числу элементов, то же можно сказать и о union-set (выигрыш по сравнению с квадратичным числом шагов ранее). Процедура intersection-set, по-прежнему, требует числа шагов, пропорционального квадрату длины списка (только вот длина его теперь будет больше). Наконец, adjoin-set выполняется за константное число шагов (большой выигрыш).

Итак, мы выигрываем в скорости операций adjoin-set и union-set, но проигрываем на операциях element-of-set? и intersection-set.

Таким образом представление множеств в виде списков с повторяющимися элементами имеет смысл тогда, когда операции добавления элемента и объединения множеств производятся часто, а проверка принадлежности элемента множеству и пересечение множеств производятся редко.

Для реализации операции объединения множеств мы можем применить рекурсивную стратегию, близкую по задумке к той, которая приводится при описании операции пересечения множеств в тексте книги. А именно, воспользуемся следующими тремя правилами при объединении множеств set1 и set2:

1. Если set1 пусто, то объединение set1 и set2 есть set2.
2. Если элемент x из set1 содержится в set2, то объединение set1 и set2 - это то же, что и объединение set1 без элемента x и set2.
3. Если элемент x из set1 не содержится в set2, то объединение set1 и set2 - это то же, что и объединение set1 без элемента x и set2, к которому добавлен элемент x.

Воспользовавшись этими тремя правилами и выбирая в качестве элемента x первый элемент списка, представляющего множество set1, получим следующее определение union-set:

(define (union-set set1 set2)
  (cond ((null? set1) set2)
        ((element-of-set? (car set1) set2)
         (union-set (cdr set1) set2))
        (else
         (cons (car set1)
               (union-set (cdr set1) set2)))))

Оно очень похоже на определение intersection-set.

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

Таким образом мы сразу же достаточно прямолинейным способом получаем определения предикатов, селекторов и конструкторов (в конструкторах не реализовано упрощение выражений для большей наглядности):

(define (sum? e)
  (and (pair? e) (eq? (cadr e) '+)))

(define (addend e)
  (car e))

(define (augend e)
  (caddr e))

(define (make-sum a1 a2)
  (list a1 '+ a2))

(define (product? e)
  (and (pair? e) (eq? (cadr e) '*)))

(define (multiplier e)
  (car e))

(define (multiplicand e)
  (caddr e))

(define (make-product m1 m2)
  (list m1 '* m2))

Теперь перейдем к части Б упражнения. Здесь ситуация осложняется тем, что каждая операция уже не задается жестко списком из трех элементов в фиксированном порядке. Для того, чтобы определить, какая операция перед нами, нужно найти то действие, которое будет выполняться первым и, соответственно, по нему определить, что это за операция и к каким операндам она применяется. Для этого введем вспомогательную процедуру split, которая, получив на вход элемент и последовательность, разбивает последовательность на список элементов до заданного элемента и список элементов после заданного элемента и возвращает список из этих двух списков. Если же элемент отсутствует в последовательности, split возвращает null:

(define (split el seq)
  (define (split-iter before after)
    (cond ((null? after) null)
          ((eq? (car after) el) (list before (cdr after)))
          (else (split-iter (append before (list (car after)))
                            (cdr after)))))
  (split-iter '() seq))

С помощью процедуры split мы теперь сможем разделять выражение для суммы или произведения по операции + или * и тем самым определить предикаты и селекторы:

(define (sum? e)
  (and (pair? e)
       (not (null? (split '+ e)))))

(define (omit-parenthesis e)
  (if (null? (cdr e))
      (car e)
      e))

(define (addend e)
  (omit-parenthesis (car (split '+ e))))

(define (augend e)
  (omit-parenthesis (cadr (split '+ e))))

(define (product? e)
  (and (pair? e)
       (not (sum? e))
       (not (null? (split '* e)))))

(define (multiplier e)
  (omit-parenthesis (car (split '* e))))

(define (multiplicand e)
  (omit-parenthesis (cadr (split '* e))))

Обратите внимание на две вещи:

1. При проверке на то, является ли выражение произведением, мы сначала убеждаемся в том, что оно не является суммой. Это необходимо делать, так как сложение имеет более низкий приоритет, а значит выражение вида A*B+C является суммой, а не произведением.
2. Мы вводим процедуру omit-parenthesis, которая убирает ненужные скобки вокруг переменных и чисел при получении аргументов сложения и умножения.

Теперь определим конструкторы для сложения и умножения. Здесь нам снова понадобятся вспомогательные процедуры:

(define (add-parenthesis predicate? e)
  (if (predicate? e)
      e
      (list e)))

(define (sum-or-product? e)
  (pair? e))

(define (make-operation op predicate? arg1 arg2)
  (append (add-parenthesis predicate? arg1)
          (list op)
          (add-parenthesis predicate? arg2)))

Процедура add-parenthesis в некотором смысле обратна omit-parenthesis. Она окружает скобками выражения, не удовлетворяющую предикату. Процедура sum-or-product? является предикатом, возвращающим истину на сумме и произведении и ложь на всем остальном. В нашем случае он может быть записан очень просто. Наконец, make-operation выполняет основную работу, соединяя выражения-операнды, окружая их скобками при необходимости.

Записать конструкторы для сложения и умножения очень просто:

(define (make-sum a1 a2)
  (make-operation '+ sum-or-product? a1 a2))

(define (make-product m1 m2)
  (make-operation '* product? m1 m2))

На этом адаптация программы дифференцирования для записей в инфиксной форме завершена. Проверим, как она работает на каком-нибудь примере:

> (deriv '(x + 3 * (x + y + 2)) 'x)
(1 + 3 * (1 + 0 + 0) + 0 * (x + y + 2))

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

(define (make-sum a1 a2)
  (cond ((=number? a1 0) a2)
        ((=number? a2 0) a1)
        ((and (number? a1) (number? a2)) (+ a1 a2))
        (else (make-operation '+ sum-or-product? a1 a2))))

(define (make-product m1 m2)
  (cond ((or (=number? m1 0) (=number? m2 0)) 0)
        ((=number? m1 1) m2)
        ((=number? m2 1) m1)
        ((and (number? m1) (number? m2)) (* m1 m2))
        (else (make-operation '* product? m1 m2))))

Теперь результат вычисления производной упрощается:

> (deriv '(x + 3 * (x + y + 2)) 'x)
4

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

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

Итак, что сразу бросается в глаза:

1. Оба лектора очень хороши. Они разные, но манера преподнесения материала весьма приятна. Их интересно слушать.
2. На протяжении всего курса есть определенный налет волшебства, который подчеркивает Абельсон уже с первых минут. Создается впечатление, что смотришь сказку для инженеров.
3. Аудитория очень возрастная. Молодежи довольно мало. Это сразу бросается в глаза. Сейчас более типично было бы ожидать увидеть среди слушателей около 80% 20-25 летних. Но прошло 20 лет, индустрия программного обеспечения здорово изменилась.
4. Структура лекций близка к книге, но не полностью повторяет ее. Некоторые разделы пропущены, некоторые вещи идут в другом порядке, что-то вообще в книге отсутствует. Естественно, на чем-то делается больший акцент, на чем-то меньший. Это не странно, особенно учитывая, что книга с тех пор пережила второе издание, в котором были сделаны изменения.
5. Английский обоих лекторов мне показался очень понятным и достаточно простым.

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

Окончание истории. Начало читайте здесь, а продолжение здесь.

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

После непродолжительного разбирательства выяснилось, что бандероль действительно уже пришла и ждет своего адресата. Заплатив 42 гривны 10 копеек (чуть больше $8), я забрал диски. Упакованы они были достаточно аккуратно, в специальный защитный пакет с воздушной прослойкой, оберегающей диски от повреждений.

Сейчас успел только бегло просмотреть видео, которые, конечно же, нужно будет внимательно изучать. Первые впечатления опишу в следующей заметке. Диски отлично читаются. Лекции записаны в DivX, их 10 штук, каждая состоит их двух частей. Одна часть представлена одним avi-файлом, размером около 500М.

Хочу поблагодарить Lafox.net за отличную работу.

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

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

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

Селектор addend вообще не меняется:

(define (addend s) (cadr s))

Селектор augend будет возвращать либо одно последнее слагаемое, если слагаемых было всего два, либо сумму всех слагаемых, начиная со второго:

(define (make-sum-list seq)
  (if (null? (cdr seq))
      (car seq)
      (cons '+ seq)))

(define (augend s)
  (make-sum-list (cddr s)))

Процедура make-sum-list вынесена специально, так как она нам еще понадобится.

При построении суммы с помощью make-sum мы будем делить все слагаемые на две группы: числа (константы), которые будen сразу суммироваться в число const, и выражения (с переменные значениями), которые будут накапливаться в списке vars. Затем в зависимости от результирующих значений мы будем их комбинировать для получения окончательного результата. Определение выглядит так:

(define (make-sum . seq)
  (let ((vars (filter non-number? seq))
        (const (accumulate + 0 (filter number? seq))))
    (cond ((null? vars) const)
          ((= 0 const) (make-sum-list vars))
          (else (make-sum-list (cons const vars))))))

Абсолютно аналогичные построения можно проделать и для произведения:

(define (multiplier p) (cadr p))

(define (make-product-list seq)
  (if (null? (cdr seq))
      (car seq)
      (cons '* seq)))

(define (multiplicand p)
  (make-product-list (cddr s)))

(define (make-product . seq)
  (let ((vars (filter non-number? seq))
        (const (accumulate * 1 (filter number? seq))))
    (cond ((null? vars) const)
          ((= 0 const) 0)
          ((= 1 const) (make-product-list vars))
          (else (make-product-list (cons const vars))))))

Попробуем вычислить производную из условия упражнения:

> (deriv '(* x y (+ x 3)) 'x)
(+ (* x y) (* y (+ x 3)))

Результат ожидаемый.

Сначала модифицируем процедуру deriv с тем, чтобы она распознавала и операцию возведения в степень:

(define (deriv exp var)
  (cond ((number? exp) 0)
        ((variable? exp)
         (if (same-variable? exp var) 1 0))
        ((sum? exp)
         (make-sum (deriv (addend exp) var)
                   (deriv (augend exp) var)))
        ((product? exp)
         (make-sum
           (make-product (multiplier exp)
                         (deriv (multiplicand exp) var))
           (make-product (deriv (multiplier exp) var)
                         (multiplicand exp))))
        ((exponentiation? exp)
         (make-product
           (make-product
             (exponent exp)
             (make-exponentiation (base exp)
                                  (- (exponent exp) 1)))
           (deriv (base exp) var)))
        (else
         (error "неизвестный тип выражения -- DERIV" exp))))

Теперь доопределим новые операции, связанные с возведением в степень. Проверка exponentiation?, а также селекторы base и exponent записываются абсолютно аналогично соответствующим процедурам для сложения и умножения:

(define (exponentiation? x)
  (and (pair? x) (eq? (car x) '**)))

(define (base e) (cadr e))

(define (exponent e) (caddr e))

Теперь перейдем к конструктору, в котором сразу же учтем правила сокращения. Хочу подчеркнуть, что в данный момент мы будем работать только лишь с выражениями, показатель степени которых числовой. То есть для показателя не допускается содержание выражений либо переменных. Это ограничение мы приняли еще на этапе записи процедуры deriv. В противном случае задача усложняется, так как нам нужно вводить производную для сложной функции, вводить операцию вычитания, рассматривать существенно больше случаев сокращения, оповещать об ошибках несоответствия аргументов области определения функций и т.д. - коротко говоря, последствия столь опрометчивого поступка весьма существенны. Итак, примем, что показатель является числом. Будем учитывать такие 2 правила сокращения выражений:

1. x⁰ = 1,
2. x¹ = x.

Тогда получим следующее определение процедуры make-exponentiation:

(define (power a b)
  (exp (* b (log a))))

(define (make-exponentiation base expt)
  (cond ((=number? expt 0) 1)
        ((=number? expt 1) base)
        ((and (number? base) (number? expt)) (power base expt))
        (else (list '** base expt))))

Проверим работу на примере:

> (deriv '(+ (** x 3) (** x 2)) 'x)
(+ (* 3 (** x 2)) (* 2 x))

Ответ правильный и даже сокращен.

Продолжение истории. Начало читайте здесь.

При столкновении красивой теории с жестокой реальностью рождается горькая практика. В моем случае оптимистичные ожидания получить диски с видео лекций курса “Структура и интерпретация компьютерных программ” еще к концу прошлой недели не оправдались.

Сегодня прошло 9 дней с момента отправки бандероли, и я посетил свое почтовое отделение, ожидая обнаружить диски там (у нас иногда почтальон “забывает” принести оповещение о приходе посылки). Однако, на почте меня огорчили, сказав, что никаких писем и посылок для меня у них нет.

Уточнив ситуацию у Lafox.net, выяснил, что днепропетровские почтальоны у них на плохом счету. Буду в субботу делать второй заход на почту. Все же нужно было выбирать доставку “Автолюксом”.

Тем не менее не теряю надежду получить диски в ближайшее время. Следите за новостями

В примечании 34 описывается особая форма quote и идентичность ее действия кавычке. Кроме того, указывается, что знак кавычки является просто сокращением для формы quote. Таким образом запись

(car ''abracadabra)

является лишь сокращенной формой записи для выражения

(car (quote (quote abracadabra)))

Первая quote заставляет интерпретатор понимать остаток записи буквально как список. Вполне очевидно, что для этого списка операция car возвращает символ quote.