|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[46] Еще один примитив, который используется при работе с символами - это 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)) Упражнение 2.54. Предикат equal? для двух списков возвращает истину, если они содержат одни и те же элементы в одинаковом порядке. Например, (equal? (this is a list) (this is a list)) истинно, но (equal? (this is a list) (this (is a) list)) 35Можно считать, что два символа «совпадают», если они состоят из одних и тех же печатных знаков в одинаковом порядке. Такое определение обходит важный вопрос, который мы пока не готовы обсуждать: значение «одинаковости» в языке программирования. К нему мы вернемся в главе 3 (раздел 3.1.3). ложно. Более точно, можно определить 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. А именно, сначала мы разработаем алгоритм дифференцирования, который работает с абстрактными объектами, такими как «суммы», «произведения» и «переменные», не обращая внимания на то, как они должны быть представлены. Только после этого мы обратимся к задаче представления. Программа дифференцирования с абстрактными данными Чтобы упростить задачу, мы рассмотрим простую программу символьного дифференцирования, которая работает с выражениями, построенными только при помощи операций сложения и умножения с двумя аргументами. Дифференцировать любое такое выражение можно, применяя следующие правила редукции: dc - = 0 для константы либо переменной, отличной от х dx 36На практике программисты используют equal? для сравнения не только символов, но и чисел. Числа не считаются символами. Вопрос о том, выполняется ли eq? для двух чисел, которые равны между собой (в смысле =), очень сильно зависит от конкретной реализации. Более правильное определение equal? (например, то, которое входит в Scheme как элементарная процедура) должно содержать условие, что если и a, и b являются числами, то equal? для них выполняется тогда, когда они численно равны. dx dx d(u + v) du dv dxdxdx d(uv) dv {U) 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? , который распознает числа, мы можем выразить правила дифференцирования в виде следующей процедуры: (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))) |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||