После первого знакомства с программированием многие программисты перестают задумываться об управляющей логике, поскольку большинство языков располагает лишь малой частью ее элементов. Однако мир управляющей логики выходит далеко за рамки возможностей, предоставляемых большинством основных языков программирования. Во многих не так широко известных специализированных языках имеются интересные и продвинутые элементы управляющей логики.

Примеры продвинутой управляющей логики

Лучше всего начать с рассмотрения примеров элементов продвинутой управляющей логики, существующих в различных языках. Далее мы обобщим эти знания в единую структуру для ситуаций, где может потребоваться их применение.

Нелокальные выходы

Первый прием продвинутой управляющей логики вам, вероятно, уже знаком: нелокальные выходы. Существует несколько типов нелокальных выходов, каждый из которых можно поделить на две категории: структурированные и неструктурированные. Неструктурированные локальные выходы — это именно то, от чего вас предостерегал преподаватель информатики; например, страшный goto. Но истина состоит в том, что, при разумном и мудром использовании неструктурированные локальные выходы могут быть очень полезны. Например, они могут улучшить читаемость программ со сложной управляющей логикой. Если сложная управляющая логика не обладает естественной структурностью, то навязывание ей какого-либо структурирования ухудшает её читаемость, а не улучшает. Дополнительную информацию касательно «за» и «против» использования gotoсмотрите по ссылкам в разделе Ресурсы далее в этой статье.

Что касается структурированных нелокальных выходов, то вы, видимо, хорошо знакомы с их самым распространенным типом — исключениями. Если же последние 20 лет вы безвылазно занимались программированием на C, Fortran и Cobol, то вот краткое введение в исключения.

Исключение — это способ сообщить об ошибке в коде и локализовать ее. Обычно, если происходит ошибка, нам нужно, чтобы она обрабатывалась, а остальная часть кода бы не выполнялась без явного на то разрешения. В качестве примера рассмотрим простой код на языке Java ™ для работы с базой данных:

//Примечание: этот код не скомпилируется, но так оно и задумывалось.
import java.sql.*;
 ...
 public static int testdbcode(Connection conn) {
 //Приготовить оператор
 PreparedStatement s = conn.prepareStatement(
 "select id from test_table where name = ?");
 //Установить параметры
 s.setString(1, "fred");
 //Выполнить запрос
 ResultSet rs = s.executeQuery()
 //Перейти к первой строке результата
 rs.next();
 //Получить ответ (первый параметр результата)
 int id = rs.getInt(1);

 return id;
 }
 ...

Недостаток этого кода в том, что здесь не используется обработка ошибок, а при взаимодействии с базами данных или какими-либо другими внешними компонентами ошибки могут возникать практически на каждом шагу. При этом, получив где-либо в коде ошибку, нет особого смысла продолжать его выполнение. Например, если ошибка произошла при подготовке запроса, то уже нет смысла в дальнейшей установке параметров, выполнении запроса и получении ответа; после первой же ошибки запрос практически провален. Поэтому в Java имеются исключения, позволяющие охватить блок кода, который бы целиком пропускался при появлении ошибки. Чтобы сделать это на Java, код нужно переписать следующим образом:

import java.sql.*;
 ...
 public static int testdbcode(Connection conn) {
 try {
 //Приготовить оператор
 PreparedStatement s = conn.prepareStatement(
 "select id from test_table where name = ?");
 //Установить параметры
 s.setString(1, "fred");
 //Выполнить запрос
 ResultSet rs = s.executeQuery()
 //Перейти к первой строке результата
 rs.next();
 //Получить ответ (первый параметр результата)
 int id = rs.getInt(1);

 return id;
 } catch (Exception e) {
 //Здесь следует код обработки ошибок
 return -1;
 }
 }
 ...

Код в блоке try исполняется до тех пор, пока не закончится, либо один из операторов не приведет к ошибке. Если возникаетошибка, оставшийся код в блоке try пропускается и выполняется код в блоке catch , где информация об исключении хранится в переменной e . В Java выдаваемые ошибки сами по себе являются полноценными классами, поэтому в исключении можно разместить любое количество информации. На практике можно создать несколько блоков catch , каждый из которых обрабатывает отдельный класс исключений.

В примере кода выше мы имели дело с исключениями, генерируемыми системой. Однако точно так же можно создавать и обрабатывать исключения на уровне приложений. Приложение может в любой момент сообщить об ошибке при помощи ключевого слова throw Например, пусть в вышеприведённом коде, в случае получения идентификационного номера 0, это будет исключением на уровне приложения. Можно сделать следующее:

import java.sql.*;
 ...
 public static int testdbcode(Connection conn) {
 try {
 //Приготовить оператор
 PreparedStatement s = conn.prepareStatement(
 "select id from test_table where name = ?");
 //Установить параметры
 s.setString(1, "fred");
 //Выполнить запрос
 ResultSet rs = s.executeQuery()
 //Перейти к первой строке результата
 rs.next();
 //Получить ответ (первый параметр результата)
 int id = rs.getInt(1);

 //Проверить исключение приложения
 if(id == 0) {
 //Сообщить об исключении
 //Предполагается, что класс InvalidUserIDException где-то определен
 throw new InvalidUserIDException();
 }

 return id;
 } catch (InvalidUserIDException e) {
 //Обработать конкретную ошибку
 return -1;
 } catch (Exception e) {
 //Обработать все остальные ошибки
 return -1;
 }
 }
 ...

В дополнение нужно сказать, что код, содержащий исключение, не обязательно должен располагаться в самой функции. Операторы try и catch и catch могут находиться в любой охватывающей функции. Механизм обработки исключений раскрутит стек до подходящего обработчика и запустит в той точке код обработки исключений. Возможность производить структурированные нелокальные выходы может сильно упростить написание и поддержку кода, поскольку обработка ошибок в некоторых случаях может быть полностью отделена от самого рабочего кода. Конечно, простота процесса обманчива: с обработкой исключений связано несколько серьезных подводных камней, обсуждение которых лежит за пределами этой статьи, но в разделе Ресурсы можно найти полезные рекомендации по этим вопросам.

Функции-генераторы

Другая разновидность структур продвинутой управляющей логики — генераторы. Это функции, которые могут генерировать наборы значений и возвращать их по одному при каждом вызове. Генератор может создать «закладку» на своем месте в текущей функции, тем самым облегчив написание программы.

Например, нам требуется функция, возвращающая последовательность чисел, начиная с 1 и с приращением при каждом вызове. Хотя это было бы несложно сделать и при помощи замыканий или даже глобальной переменной, это также очень просто сделать с помощью генератора. Вот пример реализации генератора на Python:

#Это наша функция-генератор
def sequence(start):
 current = start
 while true:
 yield current
 current = current + 1

generator_func = sequence(1) 
 #Создать новый генератор последовательности, начинающейся с 1
print generator_func.next() #выводит 1
print generator_func.next() #выводит 2
print generator_func.next() #выводит 3

Как видим, генератор каждый раз возвращается туда, где остановился, и затем продолжает работу, пока не наткнется на оператор yield . Такие возможности создания “закладки” и последующего возобновления работы с места “закладки” не являются стандартными в большинстве языков, но они очень удобны и могут сделать сложную управляющую логику более читаемой и простой для реализации.

Логическое программирование

Другая разновидность продвинутой управляющей логики, интенсивно используемая в языках типа Prolog — логическое программирование. В Prolog вы даете компьютеру набор определений, и он «волшебным образом» отвечает на запросы и устанавливает для нас наборы значений. Например, рассмотрим следующую программу на Prolog (заглавные буквы обозначают переменные):

likes(john,sports). %это объявляет, что Джон любит спорт
likes(john,food). %это объявляет, что Джон любит поесть
likes(amy,X) :- likes(john,X). %Эми любит X, если X любит Джон
likes(brad,food). %Брэд любит поесть
likes(brad,television). %Брэд любит смотреть телевизор

%запросить и вывести, что любит и Эми, и Брэд.
?- likes(amy,X), likes(brad,X), write(X).

Таким образом, Prolog создает списки того, что любит Джон и Брэд. Также устанавливается правило для того, что любит Эми – она любит всё, что любит Джон. Далее, когда выполняется запрос, то сначала находится ответ на вопрос: «Что любит Эми?» Ответ — «Всё, что любит Джон». Далее осуществляется проход по списку того, что любит Джон, и выбирается первый элемент — спорт. Затем осуществляется переход к следующему утверждению: Брэд должен любить то же самое, что и Эми (в этом выражении обозначено как X ). Однако спорт не входит в список Брэда. Значит, Prolog откатывается и находит новое значение для X из списка Эми. Следующее значение — еда. Далее проверяется, есть ли она в списке Брэда. Есть, поэтому система переходит к следующему шагу — записывает найденное значение X.

Этот подход называется логическим программированием, так как позволяет определять цели с точки зрения логических соотношений и перекладывает на компьютер всю черновую работу по поиску подходящих решений для этих логических соотношений. Самый важный для наших целей элемент такого процесса — используемая при этом особенная управляющая логика: перебор с возвратами (backtracking). Это означает, что на любой стадии расчетов, если не найдено подходящее значение в конкретной переменной, либо определенное отношение между группами переменных не выполняется, то программа может «откатиться назад» и задать новое значение. Такой подход к программированию упрощает огромное количество задач, особенно в области интеллектуальных систем.

Продолжения: универсальные инструменты управляющей логики

Итак, мы рассмотрели три разновидности продвинутой управляющей логики: нелокальные выходы, функции-генераторы и перебор с возвратами. Что между ними общего? По сути, каждая выполняет определённые манипуляции с программным стеком и указателем команд. В нелокальных выходах стек с блоками выхода отмечается “закладкой”, как и блок обработки выхода. Когда вызывается нелокальный выход, стек раскручивается до отмеченной точки, и указатель команд перемещается к обрабатывающему блоку. В функциях-генераторах переменная содержит указатель на стек генератора, а также на ту точку функции, где генератор в последний раз остановился. В переборе с возвратами “закладка” сохраняется там, где произошло присваивание, и управляющая логика переходит на это место, если расчет не удается и требуется возврат.

Эти закладки можно называть «точками продолжения» — позициями, где программа продолжит исполнение, если будет вызвана структура продвинутой управляющей логики. Или если точнее, то они известны как продолжения (continuations). В действительности все эти структуры управляющей логики можно реализовать при помощи одной функции: call-with-current-continuation.

call-with-current-continuation — это функция языка программирования Scheme, которая принимает текущий стек и указатель команд и объединяет их в единую вызываемую сущность ( продолжение) , после чего вызывает другую функцию с продолжением в качестве единственного её параметра. Продолжение — вызываемая сущность, принимающая один параметр, который затем возвращается в точку создания продолжения. Звучит несколько путано, но так оно и есть. Рассмотрим несколько примеров, чтобы получить представление о том, как всё выглядит на практике.

Для начала — небольшой пример использования продолжения:

(display
 ;;Вызов продолжения вернет параметр как возвращаемое значение для функции
 ;;the call-with-current-continuation function. Это место, где помещается «закладка»
 (call-with-current-continuation
 ;;Чтобы лучше запомнить, переменные продолжения часто пишутся с «k» или
 ;;«kont» — от «continuation». В этом примере продолжением будет «kont».
 ;;Это функция, которая при вызове вернет в помеченное “закладкой” место свой
 ;;параметр.
 (lambda (kont)
 ;;В этом примере мы просто выполним продолжение. Оно возвращает число 5
 ;;в отмеченное “закладкой” место.
 (kont 5))))
(newline)

Предыдущая программа просто выводит число 5. Заметьте, что вызов продолжения с одним параметром возвращает это значение в отмеченное закладкой место. Теперь рассмотрим чуть более сложный пример. В этом случае продолжение должно использоваться для преждевременного выхода. Это несколько надуманный пример, но он хорош в качестве иллюстрации. В этой программе каждое число списка возводится в квадрат, но если в списке есть какие-либо не-числа, то вместо списка просто возвращается символ *error*.

(define a '(1 2 3 4 5))
(define b '(1 b 2 e f))
(define (square-list the-list)
 ;;Здесь закладка
 (call-with-current-continuation
 ;;early-exit-k вернет нас к закладке
 (lambda (early-exit-k)
 ;;Выполнить процедуру
 (map
 (lambda (x)
 ;;Проверить, является ли числом
 (if (number? x)
 ;;да, является, выполнить умножение
 (* x x)
 ;;нет, не является, сделать _сейчас_ выход со значением *error*
 (early-exit-k '*error*)))
 the-list))))
;;Это возведет элементы списка в квадрат
(display (square-list a))
(newline)
;;Это выдаст ошибку
(display (square-list b))
(newline)

Будем надеяться, что приведенный выше пример подскажет вам, как использовать продолжения для реализации исключений.

Следующий пример демонстрирует другое своеобразное свойство продолжений — их неограниченную область действия. Это означает, что, в отличие от исключений, продолжения можно задействовать вне их исходного кодового блока. Когда вы делаете «закладку» при помощи продолжения, она заставляет этот стек сохраняться до тех пор, пока существует значение продолжения. Значит, даже после возврата из создавшего продолжение блока, если возвращается его значение, то вызов продолжения восстановит исходное состояние стека и продолжит выполнение с него.

Следующий пример сохраняет продолжение в глобальной переменной и затем при вызове продолжения восстанавливает исходное состояние стека.

;;Глобальная переменная под продолжениеn
(define k-global #f)

;;Мы используем let* вместо let, чтобы обеспечить нужный
;;порядок вычисления
(let* (
 (my-number 3)
 (k
 ;;оставить здесь закладкуe
 (call-with-current-continuation
 ;;Продолжение будет записано в kont
 (lambda (kont)
 ;;вернуть продолжение
 kont))))

 ;;Мы используем my-number, чтобы показать, что старый стек
 ;;сохранён. Когда мы второй раз перейдем к продолжению, значение
 ;;останется измененным
 (display "The value of my-number is: ")
 (display my-number)
 (newline)
 (set! my-number (+ my-number 1))

 ;;Сохранить продолжение в глобальной переменной.
 (set! k-global k))

;;«kontinuation» — это продолжение
(if (procedure? k-global)
 (begin
 (display "This is the first run, k-global is a continuation")
 (newline)
 ;;Передать 4 продолжению, которое перейдет в закладку, которая присвоит
 ;;его переменной k
 (k-global 4))
 (begin
 ;;Это вызывает вторичное исполнение
 (display "This is the second run, k-global is not a continuation, it is ")
 (display k-global)
 (newline)))

Такими средствами можно создавать любопытные алгоритмы и макросы, эмулирующие любые другие конструкции.

Исключения на основе продолжений

Рассмотрим, как выглядят исключения:

try {
 //Код, который должен сгенерировать исключение
} catch(SQLException e) { //catch a specific exception
 //Код обработки ошибок
} catch(Exception e) { //catch a general exception
 //Код обработки ошибок
}

//Остальной код

Итак, в первую очередь нужно написать макрос, который задает:

• блок обработки ошибок
• позицию остального кода
• исполняемый код

Так что результат раскрытия макроса должен выглядеть примерно так:

;;Здесь функция throw определяется как доступная глобально, но при ее вызове вне
;;блока try будет выдано сообщение об ошибке
(define throw (lambda (x) (display "No try clause is active!") (newline)))

(let* (
 ;сохранить старый охватывающий блок try
 (old-throw throw)
 ;мы сохраняем результаты в retval, так как должны «прибраться»
 ;перед выходом
 (retval (call-with-current-continuation
 ;Исключение будет использовать это продолжение для возврата
 ;к оставшемуся коду
 (lambda (k-exit-to-remaining-code)
 (let (
 ;Это определяет обработчик выхода
 (error-handler
 (lambda (exception)
 (k-exit-to-remaining-code
 ;;Здесь код обработки ошибок...
 ))))
 ;Это устанавливает наш обработчик как официальную
 ;функцию throw
 (set! throw error-handler)
 ;;Здесь обычный код...
 ;;Исключение можно выдать при помощи
 (throw 'test-exception))))))

 ;Восстановить прежний блок try
 (set! throw old-throw)

 ;Возвратить результат
 retval)

Вложенность настроена, так, чтобы throw всегда относился к внутреннему блоку try . Теперь, когда известно, как должен выглядеть код, можно написать макрос, который бы обеспечивал настройку всей инфраструктуры.

;;Это задает функцию throw
(define throw (lambda (x) (display "No try clause is active!") (newline)))

;;Задает синтаксис блока try
(define-syntax try
 (lambda (x)
 (syntax-case x (catch)
 (
 (try expression (catch exception exception-handler-expression))
 (syntax
 (let* (
 (old-throw throw)
 (retval
 (call-with-current-continuation
 (lambda (k-exit)
 (let (
 (error-handler
 (lambda (exception)
 (k-exit exception-handler-expression))))
 (set! throw error-handler)
 expression)))))
 (set! throw old-throw)
 retval))))))

;;Небольшой набор тестов

;Функция, которая выдает ошибку
(define (test-function)
 (throw 'ERROR))

;Функция, которая не выдает ошибку
(define (test-function-2)
 (display "No error is generated.")
 (newline))

;Проверка нашего блока try
(try (test-function) (catch e (begin (display "Exception! e is: ")
 (display e) (newline))))
(try (test-function-2) (catch e (begin (display "Exception! e is: ")
 (display e) (newline))))

Хотя основные аспекты мы обсудили, всё еще остается несколько проблем. Одна из них - возможная путаница с продолжениями. Например, если продолжения используются не только для исключений, но и для других разновидностей логики преждевременного выхода, то возможны затруднения. Рассмотрим следующий код:

;;Использует ранее определенный макрос try/catch
(try
 (begin
 (call-with-current-continuation
 (lambda (kont)
 (try
 (kont 'value) ;;выходит за продолжение, но также пропускает
 ;;сброс действующего продолжения
 (catch e (begin
 (display "Interior exception handler. Exception e is: ")
 (display e)
 (newline))))))
 ;;Так как мы не выходим через блок try обычным образом, то это 
 ;;при первом вызове отправит нас _назад_ ко внутреннему блоку catch!
 (throw 'ERROR))
 (catch e (begin
 (display "Exterior exception handler. Exception e is: ")
 (display e)
 (newline))))

Как видим, такие свободные перескоки могут вызвать определенные сложности с хранением закладок. Для облегчения подобных проблем в Scheme существует специальная процедура dynamic-wind. Она замечает, когда продолжение перескакивает через заданный стек, и это можно использовать для сброса стека, когда продолжение перескакивает назад и вперед. Процедура dynamic-wind принимает три аргумента, каждый из которых представляет собой процедуру без аргументов. Первый — процедура для выполнения при каждом входе в стек, второй — собственно процедура для запуска, третий — процедура для выполнения при каждом выходе из стека. Следующий код дает краткий пример работы dynamic-wind:

(let (
 (k-var (call-with-current-continuation
 (lambda (kont)
 (dynamic-wind
 (lambda () (display "Entering frame") (newline))
 (lambda ()
 (begin
 (display "Running")
 (newline)
 (call-with-current-continuation
 (lambda (inner-kont)
 ;;Выйти через границу dynamic-wind,
 ;;сохраняя текущее продолжение
 (kont inner-kont)))))
 (lambda () (display "Leaving frame") (newline)))))))
 (if (procedure? k-var)
 (k-var 'the-value)
 (begin
 (display k-var)
 (newline))))

Сначала создается внешнее продолжение. Затем программа входит в стек, вызывая процедуру «входа». Далее выполняется процедура, создающая новое продолжение внутри dynamic-wind. Это продолжение затем возвращается через точку исходного продолжения. Однако, поскольку оно пересекает линию dynamic-wind , то выполняется процедура «выхода». Далее снова выполняется внутреннее продолжение, перемещающее управление через dynamic-wind a, которая снова вызывает процедуру «входа». Далее происходит возврат назад через dynamic-windс очередным вызовом процедуры «выхода».

Это довольно путаная последовательность вызовов, но она имеет смысл, если представить dynamic-wind как «защитную линию» от далеко идущих продолжений. Для того чтобы управляющая логика могла пересечь «защитную линию» (при помощи продолжения, либо обычной управляющей конструкции), должна быть выполнена соответствующая процедура «уборки» («входа» или «выхода», в зависимости от направления).

С помощью этого можно защитить себя от некоторых проблем с макросом try . dynamic-wind можно использовать для перезагрузки информации о том, в каком блоке try/catch исполняется код. Вот пример:

;;Здесь функция throw определяется как доступная глобально, но при ее вызове внеn
;;блока try будет выдано сообщение об ошибке
(define throw (lambda (x) (display "No try clause is active!") (newline)))

;;Задает синтаксис блока try
(define-syntax try
 (lambda (x)
 (syntax-case x (catch)
 (
 (try expression (catch exception exception-handler-expression))
 (syntax
 ;;Точка выхода при помощи продолжения k-exit
 (call-with-current-continuation
 (lambda (k-exit)
 (let (
 ;;Это два обработчика исключений: старый и новый.
 ;;dynamic-wind устанавливает их и сносит
 ;;при входе и выходе из блока
 (old-throw throw)
 (error-handler
 (lambda (exception)
 (k-exit exception-handler-expression))))
 (dynamic-wind
 ;;Вход в блок — установить обработчик ошибок
 (lambda () (set! throw error-handler))
 ;;Собственно обработка
 (lambda () expression)
 ;;Выход из блока — установить старое значение обработчика
 (lambda () (set! throw old-throw)))))))))))

Эта версия, с одной стороны, короче, а с другой - подходит и к исходным тестовым примерам и к тем, где используются продолжения. Также, если вы считаете, что нечестно добавлять новую управляющую структуру с помощью dynamic-wind, то Кент Дибвиг продемонстрировал, что dynamic-wind можно реализовать средствами call-with-current-continuation.

Мы коснулись не всех моментов, когдаe try/catch может сгенерировать непредвиденное поведение, но изложенного достаточно для большинства случаев. В следующем разделе мы вернемся к некоторым возможным проблемам.

Генераторы на основе продолжений

Как ранее говорилось, генераторы — это разновидности структур управляющей логики. Python — самый распространенный язык из тех, в которых реализованы генераторы. Подумаем о том, как работают генераторы и как для их реализации можно использовать продолжения.

Сначала генератор нужно создать. Это обязательно влечет за собой создание стека при помощи либо продолжения либо замыкания. Далее возвращается значение и запоминается текущее положение в функции. Это также означает, что вы уже должны были сделать закладку в том месте, куда возвращаетесь.

Таким образом, наш генератор располагает двумя закладками, реализованными при помощи продолжений. Первая закладка — переменная, записываемая при создании генератора, она хранит позицию, в которой в данный момент находится функция-генератор. Далее, при запуске генератора у нас также имеется продолжение, соответствующее точке возврата вызывающей функции. Непосредственно перед возвратом создаётся продолжение, соответствующее текущему положению, и сохраняется для следующего вызова.

Теперь рассмотрим интерфейс на Scheme, который может понадобиться для генераторов в стиле Python:

(define-syntax generator
 (syntax-rules ()
 (
 (generator (yieldfunc) body ...)
 (let (
 (placeholder #f) ;;позиция в этой функции
 (return-proc #f) ;;как выйти
 (finished #f)) ;;завершилась ли работа генератора
 ;;это вход в генератор
 (lambda ()
 (call-with-current-continuation
 (lambda (tmp-return-proc)
 ;;сохранить выход в return-proc"
 (set! return-proc tmp-return-proc)
 (let (
 ;;yieldfunc сбрасывает позицию и возвращает значени
 (yieldfunc
 (lambda (x)
 (call-with-current-continuation
 (lambda (current-placeholder)
 ;;новая позиция
 (set! placeholder current-placeholder)
 ;;вернуть значение
 (return-proc x))))))

 ;;Вернуть специальное значение, если генератор завершил работу
 (if finished
 'generator-finished

 ;;Если это первый вызов, то позиция не указана,
 ;;так что мы просто запускаем тело генератора.
 ;;Если позиция есть, то мы возвращаемся к той точке.
 (if placeholder
 (placeholder 'unspecified)
 (let (
 (final-value (begin body ...)))
 (set! finished #t)
 (return-proc final-value))))))))))))

(define sequence-generator
 ;;Исходные параметры
 (lambda (start end increment)
 ;;yield будет использоваться для генерирования одного значения
 (generator (yield)
 ;;Тело основной функци
 (let loop ((curval start))
 (if (eqv? curval end)
 curval
 (begin
 ;;выдать значение
 (yield curval)
 ;;перейти далее
 (loop (+ curval increment))))))))

;;Пример использования
(define my-sequence (sequence-generator 1 3 1))
(display (my-sequence))(newline)
(display (my-sequence))(newline)
(display (my-sequence))(newline)
(display (my-sequence))(newline)

Этот код несколько трудноват для понимания. Он становится еще сложнее, если добавить возможность запроса возможных существующих значений генератора, либо других запросов состояния. Однако обратите внимание на две общие функции генератора. Одна — это процедура для возврата в вызывающую программу, а другая — текущее положение, где выполняется генератор. Может показаться странным, что процедура возврата хранится в переменной, чья область видимости ограничивается генератором, но это необходимо, чтобы правильная версия переменной была активной после вызова продолжения. Иначе после первого вызова произойдет возврат к версии, которая была активной во время создания продолжения с позицией внутри функции.

Как уже упоминалось, с продолжениями, опирающимися на исключения, могут возникать проблемы. В целом вопрос стоит так: если имеется блок try для запуска генератора и блок try для вызова генератора, а также исключение, которое выдает генерирующая функция, то какой из блоков catch будет выполнен? В тех реализациях, которые использую я, был бы вызван первый блок catch Самый ли это очевидный исход? Зависит от конкретной ситуации. Однако эти виды взаимодействия продолжений могут быть проблематичными, потому что не до конца ясно, какое действие считается «подходящим».

Перебор с возвратами на основе продолжений

Наконец, рассмотрим перебор с возвратами. Интерфейсом к нашей системе поиска с возвратами будет служить функция amb. Она принимает список значений. Для каждого из них amb делает закладку для возврата. Если текущее значение списка не удовлетворяет условиям (что сообщается вызовом функции amb:fail ), то программа возвращается к последней закладке и пробует новое значение. Вспомогательная функция amb:assert вызывает amb:fail , если ее параметр не равен true. Листинг 16 показывает эти функции в действии:

(let* (
 (a (amb 1 2 3 4 5 6 7))
 (b (amb 5 6 7 8 9 10)))
 (amb:assert (> a b))
 (display "a is ") (display a) (newline)
 (display "b is ") (display b) (newline))

Когда функция запускается первый раз, она выбирает 1 для a и 5 для b. Так как a не больше b, то функция терпит неудачу и возвращается к последней точке, где оставлена закладка. В этом случае это будет присваивание значения b. Далее программа попробует все возможные значения b. Ни одно из них не подходит, поэтому далее произойдет возврат к присваиванию значения a . Далее будет перепробовано 2 со всеми значениями b. Так будет продолжаться до тех пор, пока не будет найдено значение a , которое больше b, и с этого места программа возобновит работу.

Реализация показана в листинге 17:

;Определение AMB
(define amb:fail '*)

(define amb:initialize-fail
 (lambda x
 (set! amb:fail
 (if (null? x)
 (lambda () (error "amb tree exhausted!"))
 (car x)))))

(amb:initialize-fail)

(define amb
 (lambda alternatives
 (letrec (
 (amb-internal
 ;;sk возвращает значение (удачное продолжение),
 ;;alts — список значений
 (lambda (sk alts)
 ;;неудачный исход, если вариантов нет
 (if (null? alts)
 (prev-amb-fail)
 (begin
 (call/cc
 ;;fk — точка для перехода при неудачномn
 ;;варианте (неудачное продолжение)
 (lambda (fk)
 ;;задать функцию неудачи для возврата в эту точку
 (set! amb:fail
 (lambda ()
 (set! amb:fail prev-amb-fail)
 (fk 'fail)))
 ;;вернуть первый вариант
 (sk (car alts))))
 ;;Мы попадаем сюда после неудачи, поэтому
 ;;снова запускаем функцию для оставшейся
 ;;части списка
 (amb-internal sk (cdr alts))))))
 ;;это предыдущая функция неудачи
 (prev-amb-fail amb:fail))
 (call/cc
 ;;сделать закладку на месте присваивания значения sk
 (lambda (sk)
 ;;перебрать все варианты
 (amb-internal sk alternatives)
 ;;После прохода по ним отметить, что у нас неудача
 (prev-amb-fail))))))

;;Вызов amb без аргументов приведет к неудаче. Эта функция
;;просто делает более очевидным то, что должно происходить.
(define amb:assert-failure
 (lambda () (amb)))

(define amb:assert
 (lambda (pred)
 (if (not pred) (amb:assert-failure))))

При чтении кода помните, что «неудачное продолжение» — это путь, по которому система поиска возвращается обратно к списку значений, а «удачное продолжение» — путь, по которому функция возвращает следующее значение в обычный ход программы.

Продолжения: всё, что вы хотели от управляющей логики

Как видим, продолжения можно использовать для реализации любых конструкций продвинутой управляющей логики. Всего несколькими строками кода можно создавать из продолжений исключения, генераторы, системы перебора с возвратами и прочие сложные элементы. Но эта статья лишь вскользь касается всех возможностей. Используя продолжения, также можно, например, преобразовать Web-приложения в структуру с более привычной управляющей логикой и реализовать потоки на уровне пользователя. К сожалению, во многих языках продолжения отсутствуют, что лишает пользователей многих возможностей построения структур управляющей логики. Если в языке есть только продолжения, то на нем почти элементарно реализуются другие возможности продвинутой управляющей логики.