Вызовы функций, стек, куча и продолжения. Часть 2
В первой части статьи мы рассмотрели общую семантику применения функции в различных языках программирования и реализацию императивного вызова функции в машинном коде в стековом и бесстековом вариантах. Теперь мы рассмотрим теорию и практику реализации императивного вызова функции в модели продолжений (continuations): что такое продолжения, зачем нужны явные и неявные продолжения, как при помощи продолжений реализовать различные используемые в языках программирования управляющие конструкции.
Как уже упоминалось в первой части, концепция продолжений (continuations), впервые была реализована в языке Scheme (и это — основное отличие Scheme от классического Лиспа). Продолжения представляют собой универсальный механизм представления семантики различных управляющих конструкций. По сути, так же как лямбда-выражение представляет собой базовую абстракцию операций с данными, также и продолжение представляет собой базовую абстракцию операций с управлением. В современных оптимизирующих компиляторах используется специальная техника CPS-преобразования, позволяющая автоматически преобразовывать функциональные вызовы в последовательности продолжений, а это, в свою очередь, позволяет выполнять сквозные оптимизирующие преобразования через несколько вложенных вызовов функций.
Что такое продолжения?
Давайте разберёмся, о чём идёт речь. На взгляд автора, многие объяснения концепции продолжений, представленные в сети, являются весьма запутанными, и мы постараемся здесь объяснить вопрос проще — тем более, что ничего сложного в продолжениях по существу и нет. Перед дальнейшим чтением читателю настоятельно рекомендуется освежить в памяти материал первой части статьи, особенно раздел про реализацию императивного вызова функции в машинном коде мейнфреймов IBM z, то есть с передачей адреса возврата через регистр. Это очень близко к тому, о чём мы будем говорить дальше.
Единственным небольшим затруднением для неподготовленного читателя будет префиксный скобочный синтаксис языка Scheme (и Lisp), без которого, однако, нам было бы сложно обойтись. Например, выражение:
cos (0.1) + sin (0.2) + 0.3записывается в Scheme как:
(+ (cos 0.1) (sin 0.2) 0.3)Любое применение функции записывается в виде формы, ограниченной круглыми скобками, внутри которой через пробел перечисляются сама функция и её фактические параметры. Сколько элементов в форме (минус сама функция) — столько фактических параметров у функции. Порядок вычисления выражений (форм) в Scheme строго определён. Договоримся, что формы всегда вычисляются аппликативно слева направо. Поэтому в нашем выражении порядок вычисления будет такой:
значение имени + (им является код функции сложения)
значение имени cos (код функции косинуса)
значение литерала 0.1 (им является вещественное число 0.1)
значение результата функции (cos 0.1), то есть 0.995
значение имени sin (код функции синуса)
значение литерала 0.2 (0.2)
значение результата функции (sin 0.2), то есть 0.199
значение литерала 0.3 (0.3)
значение результата функции (+ 0.995 0.199 0.3), то есть 1.494.
Можно записать это в нашей нотации со стрелочкой, использовавшейся в предыдущей части, для простоты синтаксиса опуская преобразование записи имён функций и литеральных констант в их значения:
(+ (cos 0.1) (sin 0.2) 0.3) → (+ 0.995 (sin 0.2) 0.3) → (+ 0.995 0.199 0.3) → 1.494.
Напомним, что здесь мы говорим об императивном вызове функций, то есть буквально о вычислении фактических параметров функции, исполнении кода, являющегося её телом, и возврате результата в место вызова функции.
Теперь мы готовы дать (неформальное) определение продолжению.
Продолжение [вызова функции] — это всё то, что нам осталось сделать в программе после получения результата этой функции.
Так как в общем случае дальнейшие действия программы зависят от результата нашей функции, то продолжение в первом приближении можно представить, как некоторую функцию (лямбда-форму) от одного параметра, а именно от этого результата.
Вернёмся к нашему примеру со сложением синуса и косинуса. Продолжение вызова (sin 0.2) — это в таком понимании вот что:
(lambda (y) (+ 0.995 y 0.3))То есть это остающийся этап вычисления нашего плюса, когда 0.995 мы уже давно посчитали, в качестве формального параметра продолжения y мы подставляем результат синуса, и дальше нам осталось осуществить сложение.
Соответственно, продолжение вызова (cos 0.1) в нашем примере — это:
(lambda (x) (+ x (sin 0.2) 0.3))А у вызова плюса (+ (cos 0.1) (sin 0.2) 0.3) нет никакого продолжения, так как на нём заканчивается наша программа:
(lambda (z) #!void)Или же, если считать, что выражение (+ (cos 0.1) (sin 0.2) 0.3) мы вводим в командной строке интерпретатора, и интерпретатор должен напечатать его значение и продолжить работу, то тогда продолжением этого выражения будет командный цикл интерпретатора read-eval-print-loop, начиная с точки print.
Зачем всё это нужно? А всё дело как раз в том, что продолжение — это лямбда-форма только в первом приближении. На самом деле продолжение имеет важнейшее отличие от лямбда-формы: из продолжения никогда не выполняется возврат.По определению, продолжение простирается в будущее до конца программы.
CPS-преобразование
И вот теперь мы приходим к понятию CPS-преобразования (continuation passing style transformation). Если мы в каждый вызов функции в нашей программе добавим дополнительный параметр k, который примет значение продолжения этого вызова, и после выполнения тела функции будем вызывать это продолжение k, передавая ему результат функции, то в нашей программе больше не будет возвратов из функций! А значит, например, не нужен стек возвратов. Это похоже на то, как на мейнфрейме мы в 14 регистре передавали вызываемой функции адрес возврата, который в таком случае является просто адресом перехода дальше по программе.
Напомним исходный код нашей могущественной программы на Scheme:
(+ (cos 0.1) (sin 0.2) 0.3)Произведём CPS-преобразование этого кода. При этом нам вместо функций +, cos и sin понадобятся некие функции, которые мы обозначим +!, cos! и sin!, отличающиеся тем, что принимают дополнительный параметр — продолжение. Итак, CPS-преобразование будет таким:
(cos!
0.1
(lambda (x)
(sin!
0.2
(lambda (y)
(+!
x y 0.3
(lambda (z) #!void))))))Выглядит это более странно для человека, чем функциональная запись, однако для оптимизирующего компилятора здесь открывается просто золотое дно.
Прежде всего, видно, что конечным результатом всех этих вычислений является последнее продолжение, возвращающее #! void, а значит, всё это выражение вообще можно не считать, потому что его результат никак не используется и никому не нужен!
Ну, допустим, что там в последнем продолжении стояла бы какая-нибудь фукция печати или цикл REPL.
Тогда мы видим, что вместо вложенных вызовов у нас образовалось одно большое выражение, которое мы можем оптимизировать целиком. В том числе это относится и к рекурсивным вызовам. Появляется возможность совместно оптимизировать разные уровни функциональных вызовов, в том числе и разные шаги рекурсии.
Например, рассмотрим наивное рекурсивное вычисление чисел Фибоначчи (отметим, что условная форма if в Scheme состоит из трёх выражений — условия, ветки «истина» и ветки «ложь»):
(define (fib x)
(if
(< x 2)
1
(+ (fib (- x 1)) (fib (- x 2)))))В исходном виде это крайне проблемный алгоритм, который на каждом шаге удваивает количество рекурсивных вызовов, и мы получаем экспоненциальную по времени и по памяти сложность вычисления.
Однако, если мы проведём CPS-преобразование приведённого кода и подставим получившиеся преобразованные функции хотя бы на два шага, то мы обнаружим, что продолжение вызова(fib (- x 1)) дважды включает в себя вызов (fib (- x 2))— как своё собственное непосредственное продолжение перед сложением и как продолжение плюса в результате шага рекурсии. А значит, коль скоро у нас нет побочных эффектов, мы можем оставить только один из этих двух вызовов, схлопнуть два шага с двумя развилками рекурсии в один монотонный шаг и автоматически оптимизировать таким образом экспоненциальный алгоритм до линейного!
Хвостовые вызовы и хвостовая рекурсия
Определение термина «хвостовой вызов» (он же «концевой вызов») может немножко различаться в зависимости от того, в какой задаче он применяется, и насколько расширительно мы готовы его понимать. Применительно к нуждам нашего изложения и синтаксису языка Scheme, будем неформально называть хвостовым вызовом такой вызов функции, после которого по ходу выполнения вызывающей функции уже не остаётся ничего вычислять. Например, в такой функции:
(define (fact x acc)
(if
(zero? x)
acc
(fact (- x 1) (* x acc))))рекурсивный вызов fact находится в хвостовой позиции, то есть мы имеем дело с хвостовой рекурсией (вычисляющей факториал с использованием аккумулятора).
Если мы попробуем применить к этой функции CPS-преобразование, то обнаружим, что у внутреннего вызова нет никакого продолжения, отличающегося от вызова внешнего. Иными словами, результат CPS-преобразования будет такой:
(define (fact! x acc k)
(if
(zero? x)
(k acc)
(fact! (- x 1) (* x acc) k)))то есть продолжение внутреннего вызова совпадает с продолжением внешнего (параметр k передаётся без изменения на следующий шаг рекурсии), и на последнем шаге рекурсии мы просто передаём значение аккумулятора самому внешнему продолжению (то есть контексту самого первого вызова). Это означает, что CPS-преобразование совершенно автоматически и без каких-либо наших усилий произвело нам оптимизацию хвостовой рекурсии (и любых хвостовых вызовов вообще).
Таким образом, модель вызова функций через продолжения сама по себе оптимизирует хвостовые вызовы (формальнее говоря, в этой модели просто не возникают хвостовые возвраты, так как нет возвратов вообще, а продолжение в хвосте остаётся неизменным).
Продолжения и семантика языка Scheme
Семантика языка Scheme такова, что при любом вызове функции в Scheme ей неявно передаётся тот самый параметр k, о котором мы говорили — её продолжение. И вместо «возврата» функция осуществляет переход на своё продолжение, передавая этому продолжению свой результат. (Это не совсем то же самое, что CPS-преобразование вызовов функций, так как при CPS-преобразовании мы выписываем продолжение в явном виде лямбда-формы, а в Scheme продолжение задаётся динамически, специальной структурой данных, описывающей контекст возврата).
Специально подчеркнём этот момент: функции в Scheme могут быть интерпретированы так, как будто бы они осуществляют обычный императивный вызов с возвратом, но на самом деле операционно реализуются с помощью механизма продолжений.
Само продолжение представляет собой не только адрес конкретной точки в программе, но и её лексический контекст. То есть, вызывая продолжение, мы восстанавливаем то окружение, которое действовало при создании этого продолжения. Если нам была доступна при создании продолжения какая-то переменная var, то она и будет доступной при активации продолжения. Но динамический контекст, то есть уже вычисленные значения переменных, конечно, не восстанавливается, иначе программа ходила бы по бесконечному циклу, полностью воспроизводя своё состояние.
Управление памятью в Scheme полностью автоматическое, используется выделение памяти в куче и сборщик мусора. Память под локальные переменные автоматически выделяется в куче при их первом использовании и освобождается сборщиком мусора в том случае, когда на эти переменные не остаётся активных ссылок. А активных ссылок не останется ровно тогда, когда переменная не находится в лексическом контексте текущей выполняемой функции и прямо или косвенно не используется её продолжением, то есть, другими словами, не существует путей выполнения в программе, которые могут привести к повторному использованию этой переменной. Это автоматически прослеживается по ссылкам из структуры данных продолжения. Как видим, для стека тут просто нет места. Хотя стек процессора на некоторых архитектурах может использоваться компилятором для оптимизации отдельных локальных фрагментов кода.
Функции в Scheme благодаря такой реализации являются глубоко рекурсивными (контекст цепочки вызовов может при необходимости занимать весь размер оперативной памяти, но при этом используется оптимизация хвостовой рекурсии) и реентерабельными. Функции сами по себе асинхронны, так как каждый инстанс функции, образно выражаясь, едет по своим собственным рельсам продолжений к концу программы, не используя общие ресурсы. Нет никаких фундаментальных причин ждать выполнения функции после её вызова, так как вызывающая функция не отвечает за результат вызываемой, передавая эти заботы её продолжению.
Далее посмотрим, как можно использовать эти свойства на доступном программисту уровне.
Продолжения как объекты первого класса
Выше мы говорили о том, что продолжение функции в Scheme передаётся ей в виде неявного параметра, скрытого от программиста. Между тем, существует возможность продублировать этот неявный параметр в виде явного. Для этого предназначена форма call-with-current-continuation, или сокращённо call/cc. Единственным параметром формы call/cc является лямбда, принимающая в виде своего явного параметра своё продолжение (которое является и продолжением call/cc тоже, так как лямбда находится в хвостовой позиции).
Проиллюстрируем сказанное для начала несколько искусственным, но детальным примером.
;; Объявим переменную для запоминания продолжения
(define cont)
;; Объявим функцию, печатающую значение,
;; равное нулю, и запоминающую продолжение
;; вычисления этого значения
(define (myprint)
(println "Значение="
(call/cc
(lambda (k)
(set! cont k) ; запоминаем продолжение
0) ; значение лямбды и call/cc
;; вот здесь, после лямбды – контекст продолжения
)
)
)Вызовем нашу функцию:
> (myprint)
Значение=0
Наша функция выполнилась, лямбда через call/cc вернула своё значение, равное нулю, и это значение подставилось в вызов функции печати. Но вместе с этим продолжение call/cc было запомнено в переменной cont.
Вызовем наше запомненное продолжение, передав ему новый результат 100:
> (cont 100)
Значение=100
Можно ещё раз:
> (cont 200)
Значение=200
Как видим, вызов продолжения восстанавливает контекст и передаёт ему управление.
Однако, переход внутрь ранее завершившихся функций не является самой востребованной операцией в практическом программировании, поэтому приведём какие-нибудь более прагматически ценные примеры.
Цикл с управляющей переменной (семантика for):
(define (myloop n1 n2)
(define for-iteration)
(let
((i (call/cc
(lambda (cc)
(set! for-iteration cc)
n1))))
(when (<= i n2)
(println i)
(for-iteration (+ i 1)))))Форма let связывает переменную i со значением, возвращаемым call/cc.
Контекстом продолжения for-iteration в данном случае является сам момент связывания переменнойi, то есть, грубо говоря, точка между правой и левой частью присваивания.
Форма when является упрощённой формой if без ветки «ложь», но зато содержащей несколько выполняемых форм без их дополнительного группирования.
Досрочный возврат из функции (семантика return):
(define (mysqrt x return-context)
(when (negative? x)
(return-context 0)) ; досрочный выход
(sqrt x))
(define (call-mysqrt x) ; вызов с передачей контекста
(call/cc
(lambda (cc) (mysqrt x cc))))Мы видим, как на базе продолжений можно конструировать различные управляющие конструкции. По сути, продолжение напоминает усиленный оператор goto, который управляет не только адресом текущего исполняемого оператора в программе, но и контекстом (именно в связи с этим, кстати, современные оптимизирующие компиляторы запрещают в программах на классических императивных языках переходы по goto в обход инициализации контекста — программа с таким goto не может быть представлена в модели продолжений и, как следствие, CPS-преобразована).
Недетерминированное программирование
С использованием продолжений может быть легко реализована техника недетерминированного программирования, относительно мало известная и редко используемая, но позволяющая получить значительный оптимизационный эффект в переборных задачах путём введения отсечения.
Процитируем в сокращённом виде другую нашу статью, в которой разбирается пример использования недетерминированного программирования.
Форма amb принимает произвольное число параметров и имеет следующую семантику:
(amb) означает выбор из нуля альтернатив, то есть то, что алгоритм зашёл не туда.
(amb x) означает выбор из одной альтернативы, то есть то же самое, что просто x.
(amb x1 x2 ... xN), где N ⩾ 2, означает выбор из N альтернатив. При этом наша программа как бы распадается в мультивселенной на N разных программ, в каждой из которых реализовался свой вариант значения функции amb. Буквально как если бы мы кинули игральный кубик с N значениями, и рассматривали бы разные миры, в каждом из которых на кубике выпало бы своё значение. В дальнейшем (в отличие от квантовых мультивселенных) эти программы можно вновь собрать из разных миров в множество их результатов в одном мире формой set-of.
(assert condition) — форма, означающая, что в этом месте программы должно выполняться условие condition (и сама имеющая значение этого условия). Если условие ложно, то мы оказались в неправильном мире, то есть наш алгоритм зашёл в тупик.
(set-of expr) — форма, возвращающая список всех допустимых значений выражения expr в разных мирах.
(define fail)
(define-syntax amb
(syntax-rules ()
((amb) (fail))
((amb a) a)
((amb a b ...)
(let ((fail0 fail))
(call/cc
(lambda (cc)
(set! fail
(lambda ()
(set! fail fail0)
(cc (amb b ...))))
(cc a)))))))
(define-syntax set-of
(syntax-rules ()
((set-of s)
(let ((acc '()))
(amb (let ((v s))
(set! acc (cons v acc))
(fail))
(reverse! acc))))))
(define (assert pred)
(or pred (amb)))
(call/cc
(lambda (cc)
(set! fail
(lambda ()
(cc 'no-choise)))))Напишем при помощи техники недетерминированного программирования программу, находящую все тройки чисел x, y и z, имеющих значения от 1 до 5 каждое, такие, что их сумма равна 10:
(define (triple)
(let
((x (amb 1 2 3 4 5))
(y (amb 1 2 3 4 5))
(z (amb 1 2 3 4 5)))
(assert (= (+ x y z) 10))
(list x y z)))
(set-of (triple))Идея состоит в том, что здесь при помощи продолжений мы возвращаемся к точке выбора конкретного значения в форме amb и пробуем новый вариант до тех пор, пока варианты не закончатся.
Вывод
Легко видеть, что если лямбда-формы — это элемент функционального программирования, то прямое использование продолжений в исходном коде является чисто императивной техникой. Оно основывается на присваиваниях состояния контекста и работе с явными передачами управления. В то же время, поскольку формализм продолжений очень хорошо исследован, то это — тот мостик, который позволяет соединить императивную семантику с теорией вычислений и формальной семантикой, а значит — обеспечить базу для автоматического синтеза и преобразования кода программ за пределами функционального программирования.
Использование формализма продолжений позволяет устранить синтаксический разрыв между вызывающей и вызываемой функциями (особенно глубокий в случае рекурсивного вызова), позволяя компилятору выполнять сквозную оптимизацию кода между разными уровнями вложенности вызовов.
Код, написанный в формализме продолжений, не использует концепцию «возврата управления» ни в денотационной, ни в операционной семантике (то есть ни на абстрактном уровне, ни в своей реализации). В связи с этим отпадает необходимость учитывать при анализе текста программы незримо находящийся где-то за пределами синтаксиса стек или другой механизм управления возвратами.
Habrahabr.ru прочитано 4745 раз
