John Harrison - Введение в функциональное программирование (1108517), страница 24
Текст из файла (страница 24)
Подобные вызовы называются хвостовыми вызовами(потому что самые последние в теле функции), а функция, в которой все рекурсивныевызовы суть хвостовые, называется функцией с хвостовой рекурсией.Что знаменательно в хвостовых вызовах? При рекурсивном вызове tfact нетнеобходимости сохранять предыдущие значения локальных переменных. Можноиспользовать одну и ту же фиксированную область памяти для храненияпеременных.
Будет ли это происходить на самом деле, разумеется, зависит оттого, насколько компилятор способен обнаружить наличие хвостовой рекурсиив коде. Большинство известных компиляторов, включая CAML, хвостовую1Такая уж сложилась традиция - стек "растёт"вниз.98Глава 8. Эффективный ML8.2. Создание эффективного кодарекурсию обнаруживают. Следовательно, оформление функции таким образом,что рекурсивный вызов является хвостовым, может существенно сократитьиспользование памяти. Для таких функций как факториал, едва ли возможен вызовна столь больших значениях аргументов n, что переполнится стек.
Однако, наивнаяреализация многих функций над списками, может привести к подобному результату,когда списки длинны.Дополнительный аргумент x функции tfact называется аккумулятором, потомучто он накапливает промежуточные результаты по ходу рекурсивных вызовов и,в конце концов, возвращается как значение функции. Оформление кода такимспособом – самый простой способ сделать рекурсивную функцию хвостовойрекурсией.Мы отметили, что в функциях с хвостовой рекурсией для аргументов можетиспользоваться фиксированная область памяти. С этой точки зрения можнорассматривать рекурсию как завуалированную реализацию императивного цикла.Вот очевидная параллель с реализацией факториала на C:int fact(int{ int x = 1;while (n >{ x = x *n = n }return x;}n)0)n;1;Инициализация x = 1 соответствует присваиванию 1 переменной x.
Основнойцикл соответствует рекурсивным вызовам, с тем лишь отличием, что для функциис хвостовой рекурсией мы явно передаём состояние2 через аргументы. Вместоприсваивания и введения циклов, мы делаем рекурсивный вызов с обновлённымипеременными. Используя похожие приёмы и выражая состояние явно, можно легкописать, в сущности, императивный код в якобы функциональном стиле.
Мы ведьзнаем, после оптимизаций стандартными компиляторами машинный код будет одини тот же в обоих случаях.8.2.2Минимизация операций consМы рассмотрели, как используется пространство стековой памяти. Но различныеконструкции в функциональных программах могут использовать память идругого типа, память, обычно выделяемую в области, называемой кучей.Тогда как стек последовательным образом растёт и сокращается, управляемыйпоследовательностью вызовов функций, эта память не может быть освобожденатаким же простым способом.
Вместо этого исполняющей системе, время от времени,требуется проверять, какая часть выделенной памяти больше не используется, иосвобождать её для дальнейших вычислений, этот процесс известен как сборкамусора. Особенно важный пример здесь – это память, используемая конструкторамирекурсивных типов, например, при вызове ::. Так, когда следующий фрагментвыполняется:2Под «состоянием» здесь понимается набор переменных, которые меняются по ходу цикла.998.2. Создание эффективного кодаГлава 8. Эффективный MLl e t l = 1 : : [ ] in t l l ; ;новый блок памяти, именуемый «cons-ячейка», выделяется для хранения результатаработы конструктора :: . Обычно это три слова памяти, одно являетсяидентификатором конструктора, а два других являются указателями на голову ихвост списка. В общем случае, решение по поводу того, когда память может бытьосвобождена, представляет собой сложную задачу.
Для нашего примера, мы сразувозвращаем хвост списка, так что, очевидно, cons-ячейка может быть освобождёнанемедленно. Но, в общем случае, из текста программы столь очевидные выводысделать затруднительно, поскольку l может быть, например, передан различнымфункциям, которые, могут просматривать элементы списка. Так что необходимодинамически анализировать использование памяти и выполнять сборку мусора. Впротивном случае мы рискуем исчерпать память.Разработчики функциональных языков усердно работают над алгоритмами болееэффективной сборки мусора.
Некоторые заявляют, что автоматическое выделениепамяти и сборка мусора работают быстрее, чем в обычном использовании явноговыделения памяти в языках подобных C (malloc и пр.). Хотя мы не пойдёмтак далеко, конечно, хорошо, что память всегда выделяется автоматически. Этопозволяет избежать многих тех моментов в программировании, которые печальноизвестны своей утомительностью и подверженностью к ошибкам.Многие конструкции, излюбленные функциональными программистами,используют память, а она управляется сборщиком мусора.
Хотя чрезмерноевнимание к этому может повредить функциональному стилю программ, естьнекоторые простые соображения, которые стоит учитывать во избежаниенеуместного расходования памяти. Очень простое правило заключается втом, следует избегать использования append если возможно. Как видим, приразвёртывании рекурсивных вызовов согласно определению#let rec append l1 l2 =match l1 with[] -> l2| (h::t) -> h::(append t l2);;порождает n cons-ячеек, где n длина первого списка. Есть много способов заменитьappend, например, с помощью добавления к функциям дополнительных аргументов –аккумуляторов.
Замечательный пример – функция обращения списка, которую мыраньше записывали как:#let rec rev =fun [] -> []| (h::t) -> append (rev t) [h];;Что порождает порядка n2 /2 cons-ячеек, где n это длина списка. Следующаяальтернатива, используя аккумулятор, генерирует только n из них:#let rev =let rec reverse acc =fun [] -> acc| (h::t) -> reverse (h::acc) t inreverse [];;100Глава 8. Эффективный ML8.2.
Создание эффективного кодаБолее того, ядро рекурсии reverse – хвостовая рекурсия, так что мы такжесохраняем стековую память и, таким образом, дважды в выигрыше.Как пример другой типичной ситуации, когда посредством разумногоиспользования аккумуляторов мы можем избежать вызовов append, рассмотримзадачу по нахождению списка терминальных элементов бинарного дерева. Если мызададим тип бинарных деревьев следующим образом:#type btree = Leaf of string| Branch of btree * btree;;то решением задачи будет:#let rec fringe =fun (Leaf s) -> [s]| (Branch(l,r)) -> append (fringe l) (fringe r);;Однако следующая улучшенная версия выполняется с меньшими затратами:#let fringe =let rec fr t acc =match t with(Leaf s) -> s::acc| (Branch(l,r)) -> fr l (fr r acc) infun t -> fr t [];;Заметьте, мы переписали второй аргумент – аккумулятор, так что теперьрекурсивный вызов более понятен при чтении слева - направо.
Вот простой пример,как может использоваться каждая из версий fringe:#fringe (Branch(Branch(Leaf "a",Leaf "b"),Branch(Leaf "c",Leaf "d")));;- : string list = ["a"; "b"; "c"; "d"]Первая версия создаёт 6 cons-ячеек, вторая – только 4.
На бо́льших деревьяхразность будет более впечатляющей. Ещё неуместное использование конструкторовтипа происходит при сопоставлении с образцом. Например, рассмотрим фрагменткода:fun [ ] −> [ ]| ( h : : t ) −> i f h < 0 then t e l s e h : : t ; ;Ветка, соответствующая ‘else’ создаёт cons-ячейку, несмотря на то, что эта жеконструкция уже передавалась как аргумент функции. То есть, аргумент берётся иповторно реконструируется. Чтобы подобных издержек не было, следует кодироватьфункцию следующим образом:fun l −>match l with[ ] −> [ ]| ( h : : t ) −> i f h < 0 then t e l s e l ; ;1018.2. Создание эффективного кодаГлава 8. Эффективный MLТем не менее, ML предлагает более гибкую альтернативу: использованиеключевого слова as.
С его помощью мы можем именовать определённые частиобразцов, так что впоследствии возможно их использование без реконструкции.Например:fun [ ] −> [ ]| ( h : : t as l ) −> i f h < 0 then t e l s e l ; ;8.2.3Принудительное вычислениеМы отмечали, что можно использовать лямбда-абстракцию для приостановкивычислений, так как ML не вычисляет выражения под лямбдами. Некоторыеинтересные примеры мы рассмотрим позже.
С другой стороны, кому-то можетпотребоваться принудительное вычисление выражений. Например:#let rec tfact x n =if n = 0 then xelse tfact (x * n) (n - 1);;#let fact n = tfact 1 n;;Поскольку мы в действительности никогда непосредственно tfact не используем,представляется нецелесообразным закреплять имя за этой функцией. Взамен мыможем сделать её локальной:#let fact1 n =let rec tfact x n =if n = 0 then xelse tfact (x * n) (n - 1) intfact 1 n;;Здесь, однако, недостаток: локальное рекурсивное определение вычисляетсятолько после того, как fact1 получает свой аргумент, поскольку до этого ононаходится под лямбдой. Более того, оно вычисляется каждый раз, при вызове fact.Мы можем поправить это так:#let fact2 =let rec tfact x n =if n = 0 then xelse tfact (x * n) (n - 1) intfact 1;;Теперь локальное связывание вычисляется лишь один раз, во время объявленияfact2.
В соответствии с нашими испытаниями, вторая версия fact примерно на 20%быстрее, при заданном аргументе 6. В тех случаях, когда при локальном связываниитребуется больше вычислений, отличие может быть более впечатляющим. Насамом деле, ведутся сложные исследования в области «частичных вычислений»посвящённые этим, а также более изощрённым оптимизациям. В известном смысле,это обобщение стандартных оптимизаций, таких как «сворачивание констант» длякомпилятора обычных языков. Однако в рабочих системах ML ответственность за102Глава 8. Эффективный ML8.3. Императивные возможностипринудительные вычисления обычно возлагается на пользователя, как в примеревыше.Мимоходом заметим, что для функций собранных из совокупности комбинаторов,без навешенных лямбд, больше возможностей во время объявления вычислитьнастолько большую часть выражения, насколько возможно. То есть, вот простейшийпример: f ◦ g выполнит все вычисления возможные в f и g, тогда как λx.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
