John Harrison - Введение в функциональное программирование (1108517), страница 26
Текст из файла (страница 26)
Предложите пример использования данного или подобного рекурсивногоисключения.108Глава 8. Эффективный ML8.3. Императивные возможности#exception Recurse of exn;;5. Напишите простую версию быстрой сортировки на массивах. Сначала массивразделяется на две части по некоторому элементу, затем на левой части ина правой рекурсивно вызывается sort. Какой рекурсивный вызов являетсяхвостовым? Сколько требуется памяти в худшем случае? Как с помощьюнебольшого изменения в коде добиться значительной оптимизации?6. Докажите, что обе версии rev, что мы упомянули, всегда дают одинаковыйрезультат.1098.3. Императивные возможностиГлава 8. Эффективный ML110Глава 9ПримерыКак мы говорили, ML изначально был спроектирован как метаязык дляавтоматизированного доказательства теорем.
Однако он пригоден и для многихдругих приложений, по большей части из области «символьных вычислений». В этойглаве мы дадим несколько характерных примеров использования ML. От читателя нетребуется досконального знания всех деталей, как, например, в случае приближениявещественных чисел, приведённом далее. Однако важно позапускать эти программы,выполнить упражнения. Поскольку нет лучшего способа почувствовать, как MLиспользуется в действительности.9.1Символьное дифференцированиеФраза «символьное вычисление» довольно неопределённа, но грубо говоря,она охватывает приложения занимающиеся не просто численными расчётами, аманипуляциями над математическими выражениями, в общем случае содержащимипеременные. Есть несколько успешных «систем компьютерной алгебры» таких какMaxima, Maple и Mathematica. Они могут выполнять полезные математическиеоперации: разложение многочленов на множители, дифференцирование иинтегрирование выражений и т.д.
Они также пригодны и для обычных вычислений.Мы покажем, как задачи такого рода могут быть решены с помощью ML.Мы выбрали символьное дифференцирование для нашего примера, потому чтодля него есть довольно простой и известный алгоритм. Читатель, возможно, знаком сdsin(x) = cos(x), а также с правиламипроизводными основных функций, например dxдифференцирования произведения и композиции функций. Поскольку каждыйможет систематически использовать эти правила для нахождения производных, товозможно и запрограммировать их на ML.9.1.1Термы первого порядкаМы будем допускать математические выражения в весьма общей форме.
Онимогут быть построены из переменных и констант, с использованием операторов.Операторы могут быть унарными, бинарными, тернарными, или, в общем случае,арности n. Это выражается с помощью следующего рекурсивного типа данных:1119.1. Символьное дифференцированиеГлава 9. Примеры#type term = Var of string| Const of string| Fn of string * (term list);;Type term defined.Например, выражение:sin(x + y)/cos(x − exp(y)) − ln(1 + x)представляется:Fn("-",[Fn("/",[Fn("sin",[Fn("+",[Var "x"; Var "y"])]);Fn("cos",[Fn("-",[Var "x"; Fn("exp",[Var "y"])])])]);Fn("ln",[Fn("+",[Const "1"; Var "x"])])]);;9.1.2ПечатьЧтение и запись выражений в сыром виде довольно неудобны.
Это общаяпроблема для всех систем символьных вычислений, и обычно интерфейссистемы содержит синтаксический анализатор (парсер) и систему ввода-вывода,позволяющую вводить и выводить данные в читаемой форме. Отложим покаподробное обсуждение синтаксического разбора, поскольку эта, сама по себе важнаятема, будет обсуждаться далее, а сейчас мы напишем простенькую систему выводадля наших выражений. Чтобы, по крайней мере, можно было видеть что происходит.Мы хотим, чтобы поддерживались обычные соглашения, как-то:• Переменные и константы записываются по их именам.• Обычные n-арные функции, выводятся в виде f (x1 , . .
. , xn ), т.е. записываетсяимя функции и рядом, в скобках список аргументов.• Инфиксные бинарные функции, такие как + записываются между своимиаргументами.• Скобки используются по необходимости.• В целях сокращения использования скобок, для инфиксных операторовопределён приоритет.Сначала мы объявим список инфиксных операторов – список пар из имениоператора и его приоритета.#let infixes = ["+",10; "-",10; "*",20; "/",20];;Использование списков для представления конечных частичных функцийявляется стандартной практикой. Они обычно называются ассоциативнымисписками и весьма распространены в функциональном программировании.1 Для тогочтобы конвертировать список в частичную функцию мы используем assoc:1Для более тяжеловесных приложений больше подойдут альтернативы, такие как хеш-таблицы,но для простых приложений, в которых списки не слишком длинны, решение в виде линейногосписка является простым и адекватным.112Глава 9. Примеры9.1.
Символьное дифференцирование#let rec assoc a ((x,y)::rest) = if a = x then y else assoc a rest;;Toplevel input:>let rec assoc a ((x,y)::rest) = if a = x then y else assoc a rest;;>^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^Warning: this matching is not exhaustive.assoc : ’a -> (’a * ’b) list -> ’b = <fun>Компилятор предупреждает нас - вычисление функции может прерваться, еслиподходящие данные не будут найдены в списке. Теперь мы можем определитьфункцию, возвращающую приоритет оператора:#let get_precedence s = assoc s infixes;;get_precedence : string -> int = <fun>#get_precedence "+";;- : int = 10#get_precedence "/";;- : int = 20#get_precedence "%";;Uncaught exception: Match_failure ("", 6544, 6601)Обратите внимание, если мы когда - либо изменим этот список операторов,то всякую функцию, вроде get_precedence, использующую его, потребуетсяпереопределить.
Это является основной причиной, по которой многие LISPпрограммисты предпочитают динамическое связывание. Множество инфиксныхоператоров можно сделать произвольно расширяемым, используя обращение поссылке:#let infixes = ref ["+",10; "-",10; "*",20; "/",20];;infixes : (string * int) list ref =ref ["+", 10; "-", 10; "*", 20; "/", 20]#let get_precedence s = assoc s (!infixes);;get_precedence : string -> int = <fun>#get_precedence "^";;Uncaught exception: Match_failure ("", 6544, 6601)#infixes := ("^",30)::(!infixes);;- : unit = ()#get_precedence "^";;- : int = 30Отметим, что по правилам вычисления в ML, разыменование указателяприменяется только после того, как get_precedence получает свои аргументы,и, следовательно, результаты во множестве операторов.
Мы также можем задатьфункцию, определяющую, является ли некоторая функция инфиксным оператором.Можно просто использовать get_precedence и смотреть сработала ли она:#let is_infix s =try get_precedence s; truewith _ -> false;;Альтернатива заключается в использовании общей функции can, котораяпроверяет успешность вычисления другой функции:1139.1.
Символьное дифференцированиеГлава 9. Примеры#let can f x = try f x; true with _ -> false;;can : (’a -> ’b) -> ’a -> bool = <fun>#let is_infix = can get_precedence;;is_infix : string -> bool = <fun>Мы будем использовать следующие функции из уже рассмотренных:#let hd(h::t) = h;;#let tl(h::t) = t;;#let rec length l = if l = [] then 0 else 1 + length(tl l);;Без дальнейших хлопот, вот функция для конвертации терма в строку.#let rec string_of_term prec =fun (Var s) -> s| (Const c) -> c| (Fn(f,args)) ->if length args = 2 & is_infix f thenlet prec’ = get_precedence f inlet s1 = string_of_term prec’ (hd args)and s2 = string_of_term prec’ (hd(tl args)) inlet ss = s1^" "^f^" "^s2 inif prec’ <= prec then "("^ss^")" else sselsef^"("^(string_of_terms args)^")"and string_of_terms t =match t with[] -> ""| [t] -> string_of_term 0 t| (h::t) -> (string_of_term 0 h)^","^(string_of_terms t);;Первый аргумент prec обозначает уровень приоритета оператора, для котороготекущее рассматриваемое выражение является непосредственным подтермом.
Такчто если текущее выражение имеет инфиксный оператор с некоторым приоритетом,то скобки необходимы, если приоритет этого оператора ниже prec. Например,если мы рассматриваем правую часть x ∗ (y + z). На самом деле, для болеенаглядной группировки мы используем скобки даже когда prec и приоритеттекущего оператора равны. В случае ассоциативных операторов, вроде + это неважно, но мы должны различать x − (y − z) и (x − y) − z. (Более усложнённаясхема могла бы учитывать ассоциативность каждого оператора.) Вторая, взаимнорекурсивная, функция string_of_terms используется для печати списка термовчерез запятую, как они идут в неинфиксной форме f (t1 , .
. . , tn ). Давайте посмотримэто в действии:114Глава 9. Примеры9.1. Символьное дифференцирование#let t =Fn("-",[Fn("/",[Fn("sin",[Fn("+",[Var "x"; Var "y"])]);Fn("cos",[Fn("-",[Var "x";Fn("exp",[Var "y"])])])]);Fn("ln",[Fn("+",[Const "1"; Var "x"])])]);;t : term =Fn("-",[Fn("/",[Fn ("sin", [Fn ("+", [Var "x"; Var "y"])]);Fn ("cos", [Fn ("-", [Var "x"; Fn ("exp", [Var "y"])])])]);Fn ("ln", [Fn ("+", [Const "1"; Var "x"])])])#string_of_term 0 t;;- : string = "sin(x + y) / cos(x - exp(y)) - ln(1 + x)"На самом деле, нам даже не требуется самостоятельно конвертировать терм встроку.
CAML Light позволяет нам настроить свою систему вывода. Это требуетнесколько специальных команд:##open "format";;#let print_term s =open_hvbox 0;print_string("‘"^(string_of_term 0 s)^"‘");close_box();;print_term : term -> unit = <fun>#install_printer "print_term";;- : unit = ()Почувствуйте разницу:#let t =Fn("-",[Fn("/",[Fn("sin",[Fn("+",[Var "x"; Var "y"])]);Fn("cos",[Fn("-",[Var "x";Fn("exp",[Var "y"])])])]);Fn("ln",[Fn("+",[Const "1"; Var "x"])])]);;t : term = ‘sin(x + y) / cos(x - exp(y)) - ln(1 + x)‘#let x = tx : term = ‘sin(x + y) / cos(x - exp(y)) - ln(1 + x)‘После того как новый принтер установлен, он будет использоваться всякий разпри печати типа term, даже если он представляет собой составной тип данных, как,например, кортеж:#(x,t);;- : term * term =‘sin(x + y) / cos(x - exp(y)) - ln(1 + x)‘,‘sin(x + y) / cos(x - exp(y)) - ln(1 + x)‘или список:#[x; t; x];;- : term list[‘sin(x + y)‘sin(x + y)‘sin(x + y)=/ cos(x - exp(y)) - ln(1 + x)‘;/ cos(x - exp(y)) - ln(1 + x)‘;/ cos(x - exp(y)) - ln(1 + x)‘]1159.1.
Символьное дифференцированиеГлава 9. ПримерыПодобная печать всё же довольно груба, поскольку большие выражения неразбиваются аккуратно на линии. Библиотека format, из которой мы использовалинесколько функций выше, предлагает лучшее решение. Вместо конвертациитерма в строку и печати, мы можем выполнить отдельные вызовы печати длякаждой его части, с помощью специальной функции, помогающей системе печатиразбивать строки. Многие из принципов, использующиеся в этой и подобныхсистемах форматированного вывода рассматриваются в Oppen (1980). Мы не будемрассматривать их в книге, за подробностями обращайтесь к руководству по CAML.29.1.3ДифференцированиеПерейдём теперь к довольно простой задаче нахождения производной отфункции.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
