Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 34
Текст из файла (страница 34)
В Scheme это сходит нам с рук,поскольку для разделения объектов мы полагаемся на пробелы и скобки. Таким образом,значением одинарной кавычки является требование закавычить следующий объект33 .Теперь мы можем отличать символы от их значений:(define a 1)(define b 2)(list a b)(1 2)(list ’a ’b)(a b)(list ’a b)(a 2)Кроме того, кавычки позволяют нам вводить составные объекты, используя обычноепредставление для печати списков:34 .32 Когда мы разрешаем в языке кавычки, это разрушает нашу способность говорить о языке в простых терминах, поскольку становится неверным, что равнозначные выражения можно подставлять друг вместо друга.Например, три есть два плюс один, но слово «три» не есть слова «два плюс один». Кавычки являются мощныминструментом, поскольку они дают нам способ строить выражения, которые работают с другими выражениями (как мы убедимся в главе 4, когда станем писать интерпретатор).
Однако как только мы разрешаем вязыке выражения, которые говорят о других выражениях того же языка, становится очень сложно соблюдатьв каком-либо виде принцип «равное можно заменить равным». Например, если мы знаем, что утренняя и вечерняя звезда — одно и то же, то из утверждения «вечерняя звезда — это Венера» мы можем заключить, что«утренняя звезда — это Венера». Однако если нам дано, что «Джон знает, что вечерняя звезда — это Венера»,мы не можем заключить, что «Джон знает, что утренняя звезда — это Венера».33 Одинарная кавычка отличается от двойной, которую мы использовали для обозначения строк, выводимыхна печать.
В то время как одинарную кавычку можно использовать для обозначения списков символов, двойнаякавычка используется только со строками, состоящими из печатных знаков. Единственное, для чего такиестроки используются в нашей книге — это печать.34 Строго говоря, то, как мы используем кавычку, нарушает общее правило, что все сложные выражениянашего языка должны отмечаться скобками и выглядеть как списки. Мы можем восстановить эту закономерность, введя особую форму quote, которая служит тем же целям, что и кавычка.
Таким образом, мы можемпечатать (quote a) вместо ’a и (quote (a b c)) вместо ’(a b c). Именно так и работает интерпретатор. Знак кавычки — это просто сокращение, означающее, что следующее выражение нужно завернуть в формуquote и получить (quote hвыражениеi). Это важно потому, что таким образом соблюдается принцип, чтос любым выражением, которое видит интерпретатор, можно обращаться как с объектом данных. Например,можно получить выражение (car ’(a b c)), и это будет то же самое, что и (car (quote (a b c))),вычислив (list ’car (list ’quote ’(a b c))).148Глава 2. Построение абстракций с помощью данных(car ’(a b c))a(cdr ’(a b c))(b c)Действуя в том же духе, пустой список мы можем получить, вычисляя ’(), и такимобразом избавиться от переменной nil.Еще один примитив, который используется при работе с символами — это eq?,который берет в качестве аргументов два символа и проверяет, совпадают ли они35 .С помощью eq? можно реализовать полезную процедуру, называемую memq.
Онапринимает два аргумента, символ и список. Если символ не содержится в списке (тоесть, не равен в смысле eq? ни одному из элементов списка), то memq возвращает ложь.В противном случае она возвращает подсписок списка, начиная с первого вхождениясимвола:(define (memq item x)(cond ((null? x) false)((eq? item (car x)) x)(else (memq item (cdr x)))))Например, значение(memq ’apple ’(pear banana prune))есть ложь, в то время как значение(memq ’apple ’(x (apple sauce) y apple pear))есть (apple pear).Упражнение 2.53.Что напечатает интерпретатор в ответ на каждое из следующих выражений?(list ’a ’b ’c)(list (list ’george))(cdr ’((x1 x2) (y1 y2)))(cadr ’((x1 x2) (y1 y2)))(pair? (car ’(a short list)))(memq ’red ’((red shoes) (blue socks)))(memq ’red ’(red shoes blue socks))35 Можно считать, что два символа «совпадают», если они состоят из одних и тех же печатных знаковв одинаковом порядке.
Такое определение обходит важный вопрос, который мы пока не готовы обсуждать:значение «одинаковости» в языке программирования. К нему мы вернемся в главе 3 (раздел 3.1.3).2.3. Символьные данные149Упражнение 2.54.Предикат equal? для двух списков возвращает истину, если они содержат одни и те же элементыв одинаковом порядке. Например,(equal? ’(this is a list) ’(this is a list))истинно, но(equal? ’(this is a list) ’(this (is a) list))ложно. Более точно, можно определить equal? рекурсивно в терминах базового равенства символов eq?, сказав, что a равно b, если оба они символы и для них выполняется eq? либо оба онисписки и при этом верно, что (car a) равняется в смысле equal? (car b), а (cdr a) равняется в смысле equal? (cdr b).
Пользуясь этой идеей, напишите equal? в виде процедуры36.Упражнение 2.55.Ева Лу Атор вводит при работе с интерпретатором выражение(car ’’abracadabra)К ее удивлению, интерпретатор печатает quote. Объясните.2.3.2. Пример: символьное дифференцированиеКак иллюстрацию к понятию символьной обработки, а также как дополнительныйпример абстракции данных, рассмотрим построение процедуры, которая производит символьное дифференцирование алгебраических выражений.
Нам хотелось бы, чтобы этапроцедура принимала в качестве аргументов алгебраическое выражение и переменную,и чтобы она возвращала производную выражения по отношению к этой переменной. Например, если аргументами к процедуре служат ax2 + bx + c и x, процедура должна возвращать 2ax + b.
Символьное дифференцирование имеет для Лиспа особое историческоезначение. Оно было одним из побудительных примеров при разработке компьютерногоязыка для обработки символов. Более того, оно послужило началом линии исследований,приведшей к разработке мощных систем для символической математической работы, которые сейчас все больше используют прикладные математики и физики.При разработке программы для символьного дифференцирования мы будем следоватьтой же самой стратегии абстракции данных, согласно которой мы действовали при разработке системы рациональных чисел в разделе 2.1.1. А именно, сначала мы разработаемалгоритм дифференцирования, который работает с абстрактными объектами, такими как«суммы», «произведения» и «переменные», не обращая внимания на то, как они должныбыть представлены.
Только после этого мы обратимся к задаче представления.36 На практике программисты используют equal? для сравнения не только символов, но и чисел. Числане считаются символами. Вопрос о том, выполняется ли eq? для двух чисел, которые равны между собой (всмысле =), очень сильно зависит от конкретной реализации. Более правильное определение equal? (например,то, которое входит в Scheme как элементарная процедура) должно содержать условие, что если и a, и bявляются числами, то equal? для них выполняется тогда, когда они численно равны.150Глава 2. Построение абстракций с помощью данныхПрограмма дифференцирования с абстрактными даннымиЧтобы упростить задачу, мы рассмотрим простую программу символьного дифференцирования, которая работает с выражениями, построенными только при помощи операций сложения и умножения с двумя аргументами.
Дифференцировать любое такоевыражение можно, применяя следующие правила редукции:dc= 0 для константы либо переменной, отличной от xdxdx=1dxd(u + v)dudv=+dxdx dxdvdud(uv)= u( ) + v( )dxdxdxЗаметим, что два последних правила по сути своей рекурсивны. То есть, чтобы получить производную суммы, нам сначала нужно получить производные слагаемых и ихсложить. Каждое из них в свою очередь может быть выражением, которое требуетсяразложить на составляющие. Разбивая их на все более мелкие части, мы в конце концовдойдем до стадии, когда все части являются либо константами, либо переменными, и ихпроизводные будут равны либо 0, либо 1.Чтобы воплотить эти правила в виде процедуры, мы позволим себе немного помечтать, подобно тому, как мы делали при реализации рациональных чисел. Если бы у насбыл способ представления алгебраических выражений, мы могли бы проверить, является ли выражение суммой, произведением, константой или переменной.
Можно было быизвлекать части выражений. Например, для суммы мы хотели бы уметь получать первоеи второе слагаемое. Еще нам нужно уметь составлять выражения из частей. Давайтепредположим, что у нас уже есть процедуры, которые реализуют следующие селекторы,конструкторы и предикаты:• (variable? e) Является ли e переменной?• (same-variable? v1 v2) Являются ли v1 и v2 одной и той же переменной?• (sum? e) Является ли e суммой?• (addend e) Первое слагаемое суммы e.• (augend e) Второе слагаемое суммы e.• (make-sum a1 a2) Строит сумму a1 и a2.• (product? e) Является ли e произведением?• (multiplier e) Первый множитель произведения e.• (multiplicand e) Второй множитель произведения e.• (make-product m1 m2) Строит произведение m1 и m2.При помощи этих процедур и элементарного предиката number?, который распознает числа, мы можем выразить правила дифференцирования в виде следующей процедуры:2.3.
Символьные данные151(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))))(else(error "неизвестный тип выражения -- DERIV" exp))))Процедура deriv заключает в себе весь алгоритм дифференцирования.
Поскольку онавыражена в терминах абстрактных данных, она будет работать, как бы мы ни представили алгебраические выражения, если только у нас будут соответствующие селекторы иконструкторы. Именно этим вопросом нам и нужно теперь заняться.Представление алгебраических выраженийМожно представить себе множество способов представления алгебраических выражений с помощью списковых структур. Например, можно использовать списки символов,которые отражали бы обычную алгебраическую нотацию, так что ax + b представлялосьбы как список (a * x + b).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
