shift/reset для самых маленьких, часть 1

Введение

Мы познакомимся с очень мощным и опасным инструментом управления
ходом программы - delimited continuations, а точнее, с операторами
shift/reset. Творческое применение shift/reset открывает куда
большие возможности по запутыванию программ, чем могло бы сниться
несчастному goto. Но с другой стороны, continuations можно применять
и в мирных целях, причем в тех областях, где continuations
действительно нужны, их очень трудно чем-либо заменить. В конце
концов, о delimited continuations в последнее время довольно много
пишут, потому любому, кто интересуется теоретической информатикой,
полезно иметь представление об этом звере.


Изложение будет неформальным, по возможности - "на пальцах", в
случае необходимости будут применяться не совсем корректные
аналогии: наша цель - интуитивное понимание предмета, за
математической строгостью всегда можно обратиться к статьям.

О терминологии: русскоязычной литературы по теме я не встречал,
потому термины "continuations", "delimited (partial, composable,
sub-) continuations" оставляю без перевода.

Prerequisites

Большинство примеров кода будет на Scheme.
Язык Scheme выбран по следующим причинам:

1) родная поддержка интересующих нас операторов call/cc и
shift/reset.

Все примеры будут работать в MzScheme 371, если
предварительно импортировать модуль "control.ss":

(require (lib "control.ss"))

2) динамическая типизация (типизация continuations - это отдельная
тема, которой бы не хотелось сейчас касаться).

Контексты и стеки вызова

Любое выражение (или инструкция) в программе вычисляется с какой-то
целью. Влияние, которое оказывает вычисление выражения на результат
программы в целом, зависит от контекста. Например, одно и то же
выражение "1" имеет различный эффект в различных контекстах:

// example 1

int i=1;            // 1
printf("i=%d\n", i);
exit(1);            // 2

Контекст, в котором вычисляется выражение, называют
continuation. Грубо говоря, continuation - это стек вызовов
в данной точке программы.

В традиционных языках (например, Java), прямого доступа к стеку
вызовов у программиста нет, стек вызовов используется специальными
управляющими операторами. Например, инструкция "return 5;" возвращает
управление в точку, из которой была вызвана функция, заменяя вызов
функции значением 5, адрес возврата определяется вершиной стека
вызовов. Инструкция "throw new SomeException();"
"разматывает" стек вызовов до первого подходящего блока catch,
передавая ему объект исключения.

Если бы программист имел доступ к стеку вызовов, он мог бы
самостоятельно реализовать операторы, подобные return или
throw/catch.

В языке Scheme для этого существует оператор call-with-current-continuation, или call/cc.

call/cc

Оператор call/cc захватывает текущий контекст (стек вызовов) и
передает его функции, которая передается оператору call/cc как
аргумент:

    (call/cc (lambda (cont) expression))

cont - это контекст, в котором вычисляется выражение
(call/cc ...). Синтаксически вызов continuation выглядит как вызов
функции, но в отличие от вызова функции, управление из вызова
continuation не возвращается - точно так же, как не возвращается
управление из инструкций return или throw в Java. Вызов (cont x)
в теле expression немедленно передает управление программе в точку
после вызова call/cc, и все выражение принимает значение x. Если в
теле expression обращения к cont не происходит, вычисление выражения
expression завершается обычным образом, и его значение
становится значением всего выражения, завернутого в call/cc.

Рассмотрим пример. В фрагменте кода на языке C, приведенном ниже,
функция div может завершиться "нормально", или, если y=0,
"аварийно":

// example 2

int div(int x, int y)
{
    if (y==0)
        return 0;
    return x/y;
}

void call_site()
{
...
    int a = div(7, 3);
    int b = div(1, 0);
...
}

Ниже приведен аналогичный код на Scheme. Для аварийного выхода из
функции div используется call/cc:

;; example 2

(define (div x y)
  (call/cc (lambda (return)
             (if (= y 0)
                 (return 0)
                 (/ x y)))))

(define (call-site)
  (let ([a (div 7 3)]
        [b (div 1 0)])
    ...))

В следующем примере call/cc используется для досрочного выхода из
функции for-each, благодаря чему мы можем определить функцию find,
которая находит первый элемент списка, удовлетворяющий условию:

;; example 3

(define (find pred xs)
  (call/cc (lambda (return)
             (begin
               (for-each (lambda (x) (when (pred x) (return x))) xs)
               #f))))

(define test-find
  (find odd? (list 2 4 8 19 10 14 13))) ;; возвращает 19

Возможности call/cc не ограничиваются досрочным выходом из функции, в
сети можно найти множество головоломных примеров применения call/cc в
сочетании с set!, с помощью которых реализуют "зеленые потоки",
интерактивные веб-страницы и т.д. Мы не будем вдаваться здесь в
подробности, заметим лишь, что применение изменяемого состояния в
связке с call/cc является признаком эмуляции delimited continuations.

Проблема оператора call/cc - он захватывает весь стек вызовов, в то
время как в большинстве интересных случаев нам нужен лишь его фрагмент.

Знакомимся с shift/reset

Если мы хотим захватывать фрагменты стека вызовов, нам нужен способ
обозначать нужную его часть. Для обозначения границы интересующего
нас контекста служит оператор reset. Если в области действия
оператора reset не происходит обращения к оператору shift, reset не
имеет никакого эффекта: выражение (reset 1) равносильно просто 1,
(reset (+ 1 2 3)) равносильно (+ 1 2 3). (Аналогично, при применении
call/cc, если вызова continuation не происходит, call/cc не имеет
эффекта, (call/cc (lambda (k) 1)) принимает значение 1).


Примечание: в тексте ниже мы будем называть reset-выражением
выражение вида (reset ...), а shift-выражением - выражение вида
(shift k ...)


Все становится значительно интереснее при наличии оператора shift.
Выражение (shift k body):
1) Захватывает фрагмент стека вызовов вплоть до ближайшего
окружающего reset и присваивает его идентификатору k.

2) Прерывает выполнение текущего контекста до ближайшего reset,
значением всего reset-выражения становится body.

3) В body можно обращаться к захваченному контексту k как к функции
произвольное число раз.

Здесь, конечно, необходимы примеры:

;; example 4
(reset (+ 10 (shift k 17))) ;; 17

В последнем примере контекстом вычисления выражения (shift k 17)
является (+ 10 [*]), символом [*] мы обозначим "дыру". Другими
словами, k принимает значение (lambda (x) (+ 10 x)). Но т.к. в теле
оператора shift мы ни разу не вызываем функцию k, контекст
игнорируется, и значением всего выражения становится 17.

;; example 5
(reset (+ 10 (shift k (k 17)))) ;; 27

example 5 отличается от example 4 тем, что после захвата контекста
мы сразу его вызываем. т.к. k = (lambda (x) (+ 10 x)), тело
оператора shift и, следовательно, все выражение принимает значение
27. Обратите внимание, выражение (shift k (k something)) всегда будет
равносильно просто something, потому код в example 5 равносилен

(+ 10 17)

;; example 6

  (let ([xs (reset
             (+ 1 (shift k
                         (list (k 10)
                               (k 20)
                               (k 30)))))]) ;; (11 21 31)
    (for-each (lambda (x) (display (format "~a\n" x))) xs))

В примере 6 мы видим, что захваченный контекст можно использовать как
обычную функцию, которую можно вызывать несколько раз. Контекст
выражения (shift k (list (k 10) (k 20) (k 30))) до reset выглядит так:

(+ 1 [*])

k принимает значение (lambda (x) (+ 1 x)), результатом вычисления
reset-выражения становится список (11 21 31), который затем присваивается
переменной xs и элементы которого печатаются в консоли.

При работе с shift/reset полезно думать о двух видах
контекстов. Во-первых, контекст вычисления reset-выражения, который в
примере 6 выглядит так:

(let ([xs [*]])
    (for-each (lambda (x) (display (format "~a\n" x))) xs))

Из этого контекста видно, что переменная xs используется, как список -
следовательно, reset-выражение при вычислении должно возвращать список.

Тело shift-выражения (list (k 10) (k 20) (k 30)) тоже возвращает
список - именно этот список становится значением всего
reset-выражения.

Во-вторых, контекст, который захватывается оператором shift, в данном
случае это (+ 1 [*]). Чтобы из этого контекста получить осмысленное
выражение, на месте "дырки" нужно подставить число. При каждом из
вызовов (k 10), (k 20), (k 30) аргумент функции k подставляется на
место "дырки", получается эффект многократных возвратов из shift-выражения.

Генерируем последовательности

При помощи shift/reset легко определить операции, подобные оператору
yield в языке Python.

Рассмотрим выражение (reset null). Его значением будет, очевидно,
null - пустой список. Усложним:

    ;; example 7
    (reset
        (begin
            (shift k (cons 1 (k (void)))) ;; (1)
            null))
  

Оператор shift на строке (1) захватывает текущий контекст k вплоть
до ближайшего reset. Захваченный контекст можно представить в виде выражения с дырой:

    (begin
        [*]
        null)
  

Как обычно при работе с delimited continuations, нужно определить:
1) что k принимает на вход
2) что k возвращает
3) что станет значением всего reset-выражения

Если мы попробуем подставить произвольные выражения на место дыры в
контексте, мы увидим, что их значения игнорируются - в любом случае
получим null. Значит, continuation k игнорирует свой аргумент,
потому мы будем вызывать его с (void) в качестве аргумента.

Таким образом, k принимает (void) и возвращает список - в данном
случае null. Значением выражения (cons 1 (k (void))) будет список
из одного элемента: (list 1). Т.к. тело оператора shift определяет
значение всего reset-выражения, значением всего выражения в примере 7
будет тоже (list 1).

Еще раз усложним исходный пример:

    ;; example 8
    (reset
        (begin
            (shift k (cons 1 (k (void)))) ;; (1)
            (shift k (cons 2 (k (void)))) ;; (2)
            null))
  

Если закомментировать строку (1), мы получим выражение, процесс вычисления
которого мы только что разобрали - возвращаемым значением будет
(list 2). Потому example 8 можно переписать:

    (reset
        (begin
            (shift k (cons 1 (k (void)))) ;; (1)
            (list 2)))
  

Форма полученного выражения нам уже знакома. Повторяя рассуждения,
проделанные для example 7, получим значение example 8: (list 1 2)

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

  (define (yield x) (shift k (cons x (k (void)))))
  

В контексте выражения, возвращающего список, yield x добавляет x в
голову этого списка. Пример:

 ;; example 9
  (reset (begin
           (yield 1)
           (yield 2)
           (yield 3)
           null))    ;; (list 1 2 3)

Пользуясь yield и for-each, мы можем написать свою версию функции
map:

 ;; example 10

 (define (my-map f xs)
  (reset (begin
           (for-each (lambda (x) (yield (f x))) xs)
           null)))

(define (test)
  (my-map 1+ (list 1 2 3)))  ;; (list 2 3 4)

Если в определении yield заменить cons на stream-cons, мы сможем
генерировать ленивые потоки:

;; example 11

(define (stream-yield x) (shift k (stream-cons x (k (void)))))

(define example3
  (reset (begin
           (stream-yield 1)
           (stream-yield 2)
           (stream-yield 3)
           stream-null)))

Примечание: в MzScheme библиотека потоков, в которой определены
stream-cons и stream-null, импортируется строчкой

(require (lib "40.ss" "srfi"))

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

;; example 12

(define (list->stream xs)
  (reset (begin
           (for-each stream-yield xs)
           stream-null)))

Обход дерева и получение списка/потока узлов остается в качестве
упражнения читателю.

Ссылки

Delimited continuations in operating systems, Oleg Kiselyov,
Chung-chieh Shan

A static simulation of dynamic delimited control, Chung-chieh Shan

A short introduction to call-with-current-continuation



Composable continuations tutorial

Спасибо за внимание.

здесь были невыполненные обещания написать продолжение (извините, дорогие читатели!)