Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 35
Текст из файла (страница 35)
Однако естественней всего использовать ту же скобочнуюпрефиксную запись, с помощью которой в Лиспе представляются комбинации; то естьпредставлять ax + b в виде (+ (* a x) b). Тогда наше представление данных длязадачи дифференцирования будет следующим:• Переменные — это символы. Они распознаются элементарным предикатом symbol?:(define (variable? x) (symbol? x))• Две переменные одинаковы, если для представляющих их символов выполняетсяeq?:(define (same-variable? v1 v2)(and (variable? v1) (variable? v2) (eq? v1 v2)))• Суммы и произведения конструируются как списки:(define (make-sum a1 a2) (list ’+ a1 a2))(define (make-product m1 m2) (list ’* m1 m2))• Сумма — это список, первый элемент которого символ +:152Глава 2.
Построение абстракций с помощью данных(define (sum? x)(and (pair? x) (eq? (car x) ’+)))• Первое слагаемое — это второй элемент списка, представляющего сумму:(define (addend s) (cadr s))• Второе слагаемое — это третий элемент списка, представляющего сумму:(define (augend s) (caddr s))• Произведение — это список, первый элемент которого символ *:(define (product? x)(and (pair? x) (eq? (car x) ’*)))• Первый множитель — это второй элемент списка, представляющего произведение:(define (multiplier p) (cadr p))• Второй множитель — это третий элемент списка, представляющего произведение:(define (multiplicand p) (caddr p))Таким образом, нам осталось только соединить это представление с алгоритмом,заключенным в процедуре deriv, и мы получаем работающую программу символьногодифференцирования. Посмотрим на некоторые примеры ее поведения:(deriv ’(+ x 3) ’x)(+ 1 0)(deriv ’(* x y) ’x)(+ (* x 0) (* 1 y))(deriv ’(* (* x y) (+ x 3)) ’x)(+ (* (* x y) (+ 1 0))(* (+ (* x 0) (* 1 y))(+ x 3)))Ответы, которые выдает программа, правильны; однако их нужно упрощать.
Верно, чтоd(xy)= x·0+1·ydxно нам хотелось бы, чтобы программа знала, что x·0 = 0, 1·y = y, а 0+y = y. Ответом навторой пример должно быть просто y. Как видно из третьего примера, при усложнениивыражений упрощение превращается в серьезную проблему.Наши теперешние затруднения очень похожи на те, с которыми мы столкнулись приреализации рациональных чисел: мы не привели ответы к простейшей форме.
Чтобыпроизвести приведение рациональных чисел, нам потребовалось изменить только конструкторы и селекторы в нашей реализации. Здесь мы можем применить подобную же2.3. Символьные данные153стратегию. Процедуру deriv мы не будем изменять вовсе. Вместо этого мы изменимmake-sum так, что если оба слагаемых являются числами, она их сложит и вернет ихсумму. Кроме того, если одно из слагаемых равно 0, то make-sum вернет другое.(define (make-sum a1 a2)(cond ((=number? a1 0) a2)((=number? a2 0) a1)((and (number? a1) (number? a2)) (+ a1 a2))(else (list ’+ a1 a2))))Здесь используется процедура =number?, которая проверяет, не равно ли выражениеопределенному числу:(define (=number? exp num)(and (number? exp) (= exp num)))Подобным же образом мы изменим и make-product, так.
чтобы встроить в него правила, что нечто, умноженное на 0, есть 0, а умноженное на 1 равно самому себе:(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 (list ’* m1 m2))))Вот как эта версия работает на наших трех примерах:(deriv ’(+ x 3) ’x)1(deriv ’(* x y) ’x)y(deriv ’(* (* x y) (+ x 3)) ’x)(+ (* x y) (* y (+ x 3)))Хотя это заметное улучшение, третий пример показывает, что нужно многое еще сделать, прежде чем мы получим программу, приводящую выражения к форме, которуюмы согласимся считать «простейшей».
Задача алгебраического упрощения сложна, средипрочего, еще и потому, что форма, которая является простейшей для одних целей, можеттаковой не являться для других.Упражнение 2.56.Покажите, как расширить простейшую программу дифференцирования так, чтобы она воспринимала больше разных типов выражений. Например, реализуйте правило взятия производнойd(un )du= nun−1 ( )dxdxдобавив еще одну проверку к программе deriv и определив соответствующие процедуры exponentiation?,base, exponent и make-exponentiation (обозначать возведение в степень можно символом154Глава 2.
Построение абстракций с помощью данных**). Встройте правила, что любое выражение, возведенное в степень 0, дает 1, а возведенное встепень 1 равно самому себе.Упражнение 2.57.Расширьте программу дифференцирования так, чтобы она работала с суммами и произведениямилюбого (больше двух) количества термов. Тогда последний из приведенных выше примеров мог быбыть записан как(deriv ’(* x y (+ x 3)) ’x)Попытайтесь сделать это, изменяя только представление сумм и произведений, не трогая процедуру deriv.
Тогда, например, процедура addend будет возвращать первое слагаемое суммы, аaugend сумму остальных.Упражнение 2.58.Предположим, что нам захотелось изменить программу дифференцирования так, чтобы она работала с обычной математической нотацией, где + и * не префиксные, а инфиксные операции.Поскольку программа взятия производных определена в терминах абстрактных данных, мы можемизменять представление выражений, с которыми она работает, меняя только предикаты, селекторы и конструкторы, определяющие представление алгебраических выражений, с которыми долженработать дифференциатор.а.
Покажите, как это сделать так, чтобы брать производные от выражений, представленных винфиксной форме, например (x + (3 * (x + (y + 2)))). Для упрощения задачи предположите, что + и * всегда принимают по два аргумента, и что в выражении расставлены все скобки.б. Задача становится существенно сложней, если мы разрешаем стандартную алгебраическуюнотацию, например (x + 3 * (x + y + 2)), которая опускает ненужные скобки и предполагает, что умножение выполняется раньше, чем сложение. Можете ли Вы разработать соответствующие предикаты, селекторы и конструкторы для этой нотации так, чтобы наша программа взятияпроизводных продолжала работать?2.3.3.
Пример: представление множествВ предыдущих примерах мы построили представления для двух типов составныхобъектов: для рациональных чисел и для алгебраических выражений. В одном из этихпримеров перед нами стоял выбор, упрощать ли выражение при его конструированииили при обращении; в остальном же выбор представления наших структур через спискибыл простым делом. Когда мы обращаемся к представлению множеств, выбор представления не так очевиден. Здесь существует несколько возможных представлений, и онизначительно отличаются друг от друга в нескольких аспектах.Говоря неформально, множество есть просто набор различных объектов.
Чтобы датьему более точное определение, можно использовать метод абстракции данных. А именно, мы определяем «множество», указывая операции, которые можно производить надмножествами. Это операции union-set (объединение), intersection-set (пересечение), element-of-set? (проверка на принадлежность) и adjoin-set (добавлениеэлемента). Element-of-set? — это предикат, который определяет, является ли данный объект элементом множества.
Adjoin-set принимает как аргументы объект имножество, и возвращает множество, которое содержит все элементы исходного множества плюс добавленный элемент. Union-set вычисляет объединение двух множеств,2.3. Символьные данные155то есть множество, содержащее те элементы, которые присутствуют хотя бы в одном изаргументов. Intersection-set вычисляет пересечение двух множеств, то есть множество, которое содержит только те элементы, которые присутствуют в обоих аргументах.С точки зрения абстракции данных, мы имеем право взять любое представление, позволяющее нам использовать эти операции способом, который согласуется с вышеуказаннойинтерпретацией37.Множества как неупорядоченные спискиМожно представить множество как список, в котором ни один элемент не содержитсяболее одного раза. Пустое множество представляется пустым списком.
При таком представлении element-of-set? подобен процедуре memq из раздела 2.3.1. Она используетне eq?, а equal?, так что элементы множества не обязаны быть символами:(define (element-of-set? x set)(cond ((null? set) false)((equal? x (car set)) true)(else (element-of-set? x (cdr set)))))Используя эту процедуру, мы можем написать adjoin-set. Если объект, который требуется добавить, уже принадлежит множеству, мы просто возвращаем исходное множество. В противном случае мы используем cons, чтобы добавить объект к списку.представляющему множество:(define (adjoin-set x set)(if (element-of-set? x set)set(cons x set)))Для intersection-set можно использовать рекурсивную стратегию. Если мы знаем,как получить пересечение set2 и cdr от set1, нам нужно только понять, надо лидобавить к нему car от set1.
Это зависит от того, принадлежит ли (car set1) ещеи set2. Получается такая процедура:(define (intersection-set set1 set2)(cond ((or (null? set1) (null? set2)) ’())((element-of-set? (car set1) set2)(cons (car set1)(intersection-set (cdr set1) set2)))(else (intersection-set (cdr set1) set2))))37 Если нам хочется быть более формальными, мы можем определить «соответствие вышеуказанной интерпретации» как условие, что операции удовлетворяют некоторому набору правил вроде следующих:• Для любого множества S и любого объекта x, (element-of-set? x (adjoin-set x S)) истинно(неформально: «добавление объекта к множеству дает множество, содержащее этот объект»).• Для любых двух множеств S и T и любого объекта x, (element-of-set? x (union-set S T))равно (or (element-of-set? x S) (element-of-set? x T)) (неформально: «элементы (union-setS T) — это те элементы, которые принадлежат либо S, либо T»).• Для любого объекта x, (element-of-set? x ’()) ложно (неформально: «ни один объект не принадлежит пустому множеству»).156Глава 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
