John Harrison - Введение в функциональное программирование (1108517), страница 27
Текст из файла (страница 27)
Сначала давайте вспомним, чему нас обучали в школе:• Если выражение - одна из элементарных функций дифференцируемогоаргумента, например sin(x), то результат дифференцирования – известнаяпроизводная этой функции.• Если выражение представимо в форме f (x) + g(x), то по правилу суммы,результат дифференцирования есть f 0 (x) + g 0 (x). Аналогично для разности.• Если выражение задано в форме f (x) ∗ g(x), применяется правило Лейбница,т.е.
возвращается f 0 (x) ∗ g(x) + f (x) ∗ g 0 (x).• Если выражение является одной из композицией стандартных функций:f (g(x)), то применяется правило последовательного дифференцирования,результат которого: g 0 (x) ∗ f 0 (g(x)).Таким образом, эти правила представляют собой рекурсивный алгоритм,хотя такая терминология редко используется в школах. Мы можем дословнозапрограммировать его в ML:2ТамтакжеестьучебникнаАдрес: http://caml.inria.fr/index-eng.htmlэту116тему,написанныйPierreWeis.Глава 9. Примеры9.1. Символьное дифференцирование#let rec differentiate x tm = match tm withVar y -> if y = x then Const "1" else Const "0"| Const c -> Const "0"| Fn("-",[t]) -> Fn("-",[differentiate x t])| Fn("+",[t1;t2]) -> Fn("+",[differentiate x t1;differentiate x t2])| Fn("-",[t1;t2]) -> Fn("-",[differentiate x t1;differentiate x t2])| Fn("*",[t1;t2]) ->Fn("+",[Fn("*",[differentiate x t1; t2]);Fn("*",[t1; differentiate x t2])])| Fn("inv",[t]) -> chain x t(Fn("-",[Fn("inv",[Fn("^",[t;Const "2"])])]))| Fn("^",[t;n]) -> chain x t(Fn("*",[n; Fn("^",[t; Fn("-",[n; Const "1"])])]))| Fn("exp",[t]) -> chain x t tm| Fn("ln",[t]) -> chain x t (Fn("inv",[t]))| Fn("sin",[t]) -> chain x t (Fn("cos",[t]))| Fn("cos",[t]) -> chain x t(Fn("-",[Fn("sin",[t])]))| Fn("/",[t1;t2]) -> differentiate x(Fn("*",[t1; Fn("inv",[t2])]))| Fn("tan",[t]) -> differentiate x(Fn("/",[Fn("sin",[t]); Fn("cos",[t])]))and chain x t u = Fn("*",[differentiate x t; u]);;Функция chain предназначена просто для упрощения последовательногодифференцирования.
Мы также систематически используем правила для сумм,произведений и пр. а также производные стандартных функций. Конечно, мымогли бы, по желанию, добавить и другие функции, например, гиперболические илиобратные тригонометрические. В паре случаев, а именно, для деления и функции tan,мы избегаем усложнённого определения за счёт альтернативной формулировки.9.1.4УпрощениеЕсли мы опробуем differentiate на нашем рабочем примере, она будет работатьдовольно хорошо:#t;;- : term = ‘sin(x + y) / cos(x - exp(y)) - ln(1 + x)‘#differentiate "x" t;;- : term =‘(((1 + 0) * cos(x + y)) * inv(cos(x - exp(y))) +sin(x + y) * (((1 - 0 * exp(y)) * -(sin(x - exp(y)))) *-(inv(cos(x - exp(y)) ^ 2)))) - (0 + 1) * inv(1 + x)‘#differentiate "y" t;;- : term =‘(((0 + 1) * cos(x + y)) * inv(cos(x - exp(y))) +sin(x + y) * (((0 - 1 * exp(y)) * -(sin(x - exp(y)))) *-(inv(cos(x - exp(y)) ^ 2)))) - (0 + 0) * inv(1 + x)‘#differentiate "z" t;;- : term =‘(((0 + 0) * cos(x + y)) * inv(cos(x - exp(y))) +sin(x + y) * (((0 - 0 * exp(y)) * -(sin(x - exp(y)))) *-(inv(cos(x - exp(y)) ^ 2)))) - (0 + 0) * inv(1 + x)‘1179.1.
Символьное дифференцированиеГлава 9. ПримерыОднако она не выполняет различные очевидные упрощения, такие как 0 ∗ x =0 и x + 0 = x. Некоторые из этих избыточных выражений создаются нашейпрямолинейной стратегией дифференцирования, которая, например, применяетправило последовательного дифференцирования f (t) даже когда t – всеголишь переменная дифференцирования. Вместо избыточного усложнения функциидифференцирования давайте зададим отдельную функцию упрощения, котораябудет избавляться от необязательных выражений.#let simp =fun (Fn("+",[Const "0"; t])) -> t| (Fn("+",[t; Const "0"])) -> t| (Fn("-",[t; Const "0"])) -> t| (Fn("-",[Const "0"; t])) -> Fn("-",[t])| (Fn("+",[t1; Fn("-",[t2])])) -> Fn("-",[t1; t2])| (Fn("*",[Const "0"; t])) -> Const "0"| (Fn("*",[t; Const "0"])) -> Const "0"| (Fn("*",[Const "1"; t])) -> t| (Fn("*",[t; Const "1"])) -> t| (Fn("*",[Fn("-",[t1]); Fn("-",[t2])])) -> Fn("*",[t1; t2])| (Fn("*",[Fn("-",[t1]); t2])) -> Fn("-",[Fn("*",[t1; t2])])| (Fn("*",[t1; Fn("-",[t2])])) -> Fn("-",[Fn("*",[t1; t2])])| (Fn("-",[Fn("-",[t])])) -> t| t -> t;;Упрощение применяется, начиная с корня дерева выражения.
Мы выполняем егов обходе снизу - вверх. В некоторых случаях было бы более эффективно упрощениепри обходе сверху - вниз, например, для 0 ∗ t и сложного выражения t, но этопотребует повторения в случае термов вроде (0+0)∗2. Выбор здесь напоминает выбормежду нормальным и аппликативным порядком редукции в лямбда-исчислении.#let rec dsimp =fun (Fn(fn,args)) -> simp(Fn(fn,map dsimp args))| t -> simp t;;Теперь мы получаем лучшие результаты:#dsimp(differentiate "x" t);;- : term =‘(cos(x + y) * inv(cos(x - exp(y))) +sin(x + y) * (sin(x - exp(y)) *inv(cos(x - exp(y)) ^ 2))) - inv(1 + x)‘#dsimp(differentiate "y" t);;- : term =‘cos(x + y) * inv(cos(x - exp(y))) sin(x + y) * ((exp(y) * sin(x - exp(y))) *inv(cos(x - exp(y)) ^ 2))‘#dsimp(differentiate "z" t);;- : term = ‘0‘В общем, всегда можно добавить более усложнённые правила упрощения.Например, рассмотрим:118Глава 9.
Примеры9.2. Синтаксический анализ#let t2 = Fn("tan",[Var "x"]);;t2 : term = ‘tan(x)‘#differentiate "x" t2;;- : term =‘(1 * cos(x)) * inv(cos(x)) +sin(x) * ((1 * -(sin(x))) * -(inv(cos(x) ^ 2)))‘#dsimp(differentiate "x" t2);;- : term = ‘cos(x) * inv(cos(x)) +sin(x) * (sin(x) * inv(cos(x) ^ 2))‘Мы хотим упростить cos(x) * inv(cos(x)) до 1, пренебрегая, как этоделает большинство коммерческих систем компьютерной алгебры, возможностьюобращения cos(x) в нуль.
Мы, конечно, можем добавить дополнительные правилаупрощения. В то же время, можно было бы сгруппировать множители вовтором слагаемом. И здесь, мы начинаем понимать, имеет значение человеческаяпсихология. Что предпочтительней? Для машины самостоятельное решение будетзатруднительно.sin(x) * (sin(x) * inv(cos(x) ^ 2))sin(x) ^ 2 * inv(cos(x) ^ 2)sin(x) ^ 2 / cos(x) ^ 2(sin(x) / cos(x)) ^ 2tan(x) ^ 2Выбрав второй вариант, затем следует заменить1 + tan(x) ^ 2наsec(x) ^ 2Такая запись и короче, и более привычна.
Тем не менее, такое решениеосновывается на том, что мы знаем определения довольно редко используемыхтригонометрических функций, вроде sec. Что бы машина не решила делать,вероятно, найдётся пользователь, которого это не устроит.9.2Синтаксический анализНедостатком предыдущего примера является необходимость задавать входныеданные в виде композиции конструкторов типов. В этом разделе мы рассмотримзадачу построения формального языка описания выражений и разработки егосинтаксического анализатора. Изложенный подход будет при этом достаточнообщим, чтобы впоследствие легко применяться к аналогичным языкам.Сформулируем задачу синтаксического анализа в общем виде.
Формальный языкопределяется своей грамматикой, которая задает множество продукций (правилвывода) для каждой синтаксической категории. Для языка термов, включающих1199.2. Синтаксический анализГлава 9. Примерылишь две инфиксные операции, + и *, а также числовые константы (0, 1, . . . ) ипеременные с алфавитно-цифровыми именами, грамматика может выглядеть так:term −→||||||termlist −→|name(termlist)name(term)numeral-termterm + termterm * termterm,termlisttermНа данный момент будем предполагать, что нам заранее известны множествадопустимых имен и числовых констант, но мы могли бы также определить ихпри помощи аналогичных правил на основе символов входного алфавита.
Заданноемножество продукций предоставляет нам способ порождения конкретного линейногопредставления всевозможных термов. Отметим, что имена вида name, numeral, termи termlist обозначают синтаксические метапеременные, а набранные полужирнымшрифтом символы «+», «(» и так далее — принадлежат входному языку. Рассмотримпример применения правил вывода:term −→−→−→−→−→term * termterm * (term)term * (term + term)term * (term + term * term)numeral * (name + name * name)откуда, подставив вместо name и numeral некоторые значения из соответствующихмножеств, мы можем породить такую строку:10 * (x + y * z)Задача синтаксического анализа (разбора) преследует прямо противоположнуюцель — восстановить последовательность применения правил вывода, то есть позаданной строке определить, каким образом она могла быть порождена.
Какправило, результатом анализа является дерево разбора, наглядно демонстрирующеепорядок выбора продукций.Одной из проблем, возникающей в ходе синтаксического анализа, являетсянеоднозначность грамматики, т. е. возможность порождения заданной строкинесколькими различными способами. В рассмотренном выше примере та же самаястрока могла быть порождена иным путём:term −→−→−→−→−→term * termterm * (term)term * (term * term)term * (term + term * term)numeral * (name + name * name)120Глава 9.
Примеры9.2. Синтаксический анализОчевидная возможность устранения неоднозначности — назначение инфикснымоперациям приоритетов и ассоциативности. Кроме того, мы можем добиться такогоже эффекта без привлечения дополнительных механизмов за счёт добавления новыхсинтаксических категорий:atom −→||||mulexp −→|term −→|termlist −→|name(termlist)namenumeral(term)-atomatom * mulexpatommulexp + termmulexpterm, termlisttermОтметим, что такая модификация грамматики делает обе инфиксные операцииправоассоциативными. Более сложным примером использования этого приёмаслужит формальное определение понятия «выражение» в стандарте ANSI C.9.2.1Метод рекурсивного спускаСтроение правил вывода подсказывает очень простой алгоритм синтаксическогоанализа при помощи множества взаимно рекурсивных функций.
Его суть втом, что для каждой синтаксической категории вводится своя функция, причемструктура рекурсивных вызовов соответствует зависимости одних продукций отдругих. Например, процедура анализа термов term при получении из входнойпоследовательности символа - будет рекурсивно вызывать саму себя для анализааргумента операции, а при встрече имени, за которым следует открывающая скобка,обратится к процедуре termlist. Последняя, в свою очередь, вызовет term неменее одного раза, и так далее. Такой подход естественно выражается на языке,подобном ML, для которого рекурсия служит одной из основных управляющихконструкций.Предположим, что наш синтаксический анализатор, реализованныйсредствами ML, получает в качестве входной последовательности список объектовнекоторого типа α. Возможно, чтобы входная последовательность состояла изпростых символов, но на практике обычно вводится дополнительный уровеньлексического анализа, в ходе которого символы группируются в лексемы (токены),например, «x12», «:=» и «96», так что входная последовательность состоит уже излексем, о типе которых мы не будем делать предположений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
