You are viewing palm_mute

palm_mute - shift/reset для самых маленьких, часть 1 [entries|archive|friends|userinfo]
palm_mute

[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

shift/reset для самых маленьких, часть 1 [Oct. 28th, 2007|08:28 pm]
Previous Entry Share Next Entry
[Tags|, , , ]
[Current Mood |tiredtired]

Введение



Мы познакомимся с очень мощным и опасным инструментом управления
ходом программы - 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


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

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

Comments:
[User Picture]From: cmm
2007-10-28 07:46 pm (UTC)

(Link)

интересная тема, спасибо!
цимес, если я правильно понимаю, в том что можно реализовать эти самые delimited continuations поверх "нормального" стэка, в отличие от обычных?
а extent у них динамический, а не лексический, ведь правда ведь?

(киньте хотя бы ссылку в ру-лямбду, там остро необходимо что-то по теме сообщества :)).
[User Picture]From: cmm
2007-10-28 08:04 pm (UTC)

(Link)

а extent у них динамический, а не лексический

фигню сказал, вообще-то (какой-такой "лексический" extent, лексический бывает разве что scope), но надеюсь что был понят правильно. :)
From: ex_feuerbach769
2007-10-28 07:53 pm (UTC)

(Link)

Пока почти ничего нового, так что пиши исчо :)
А круглые и квадратные скобки в Scheme взаимозаменямы?
[User Picture]From: cmm
2007-10-28 08:05 pm (UTC)

(Link)

в MzScheme — да, у аффтаров вкуса нет. :)
[User Picture]From: palm_mute
2007-10-28 09:14 pm (UTC)

(Link)

Ну не факт, что что-то новое для тебя появится - как понимаешь, я сам недавно чуть-чуть разобрался в азах и спешу поделиться радостью.
[User Picture]From: migmit
2007-10-28 09:56 pm (UTC)

(Link)

Писарь, паки твори!
В смысле, очень интересно, спасибо, будем читать дальше.
[User Picture]From: palm_mute
2007-10-29 08:45 am (UTC)

(Link)

Спасибо на добром слове
[User Picture]From: deni_ok
2007-10-28 10:54 pm (UTC)

(Link)

Спасибо, ждём continuation про continuations :)
[User Picture]From: palm_mute
2007-10-29 11:59 am (UTC)

(Link)

А чего его ждать? Захватывать надо!
[User Picture]From: antilamer
2007-10-29 10:05 am (UTC)

(Link)

Очень интересно, жду продолжения с нетерпением.
[User Picture]From: palm_mute
2007-10-29 12:04 pm (UTC)

(Link)

Очень рад. Я помню, ты о зипперах докладывал? Как говорят знающие люди, delimited continuations и zippers - родственники.
[User Picture]From: vshabanov
2007-10-30 12:07 am (UTC)

(Link)

Во-первых, спасибо за ликбез )

Два вопроса. Что такое #f и зачем она в example 3:
(define (find pred xs)
  (call/cc (lambda (return)
             (begin
               (for-each (lambda (x) (when (pred x) (return x))) xs)
               #f))))

Нельзя ли просто написать:
(define (find pred xs)
  (call/cc (lambda (return)
             (for-each (lambda (x) (when (pred x) (return x))) xs))))
?

И про example 8:
    (reset
        (begin
            (shift k (cons 1 (k (void)))) ;; (1)
            (shift k (cons 2 (k (void)))) ;; (2)
            null))

Правильно ли я понял, что если внутри reset находится begin, for-each или любое другое выражение с последовательными действиями, то последовательные shift как-бы последовательно "вырезают" (shift-ят?) контекст, т.е. у первого shift-а контекст:
        (begin
            [*]
            (shift k (cons 2 (k (void)))) ;; (2)
            null))

а у второго уже
        (begin
            [*]
            null))

А то очень долго думал, чем example 8 принципиально отличается от example 6 )

Надо бы получше раскрыть разницу между
reset ... shift k [.. (k ..) (k ..)]
и
reset ... [shift k (.. (k ..))] .. [shift k (.. (k ..))]

[User Picture]From: palm_mute
2007-10-30 08:35 am (UTC)

(Link)

Спасибо за вопросы и замечания, чуть позже попробую ответить.
#f в Схеме - это булевская константа false.
[User Picture]From: vshabanov
2007-10-30 12:11 am (UTC)

(Link)

Т.е. хотелось бы чтобы было написано не только о том что происходит внутри единичного shift-а в reset-е (захватили стек и вызываем его сколько угодно раз, возвращая тело шифта). А еще хочется подробностей о том что происходит, когда шифтов в резете много.
[User Picture]From: lomeo
2007-10-30 12:05 pm (UTC)

(Link)

Уф, наконец то нашёл время почитать!

Спасибо. Я только про call/cc знал, shift/reset удобнее в ряде случаев.

(reset (f (shift k (g k)))) ;; это (g f) если нет сайд эффектов, верно я понимаю?

т.е. (дадада, я опять про Хаскель) чтобы это было полезно, надо завернуть shift/reset в монаду (кстати, тогда мы и контекст сможем вытащить, дойдя до shift. Надо будет побаловаться позже, мне кажется, всё должно получиться.
[User Picture]From: palm_mute
2007-10-30 04:48 pm (UTC)

(Link)

>(reset (f (shift k (g k)))) ;; это (g f) если нет сайд эффектов, верно я понимаю?
Хм, вроде верно. Хотя я торможу и не вижу, что изменится здесь при наличии сайд-эффектов.

Теперь пара замечаний про continuations в Haskell.
1) Т.к. callcc там существует только в монаде Cont, callcc получается не настоящий - он по определению захватывает не весь стек, а только до runCont, потому кое-какие эффекты shift/reset можно получить при помощи монады Cont.

2) Монада такая уже есть, правда, для более сложного набора операторов (они все друг через друга выражаются): http://research.microsoft.com/~simonpj/papers/control/.
Реализацию, описанную в статье, можно скачать. Вдобавок один гражданин по имени Dan Doel зачем-то написал свою реализацию того же интерфейса, назвал ее CC-delcont и написал туториал: http://www.haskell.org/haskellwiki/Library/CC-delcont.

Я пока на них с близкого расстояния не смотрел, все-таки нетипизированная Схема - более родная среда для continuations, монады добавляют свои ограничения. Когда я буду хорошо понимать, как работают нетипизированные continuations, можно переходить к монадным.

3) С некоторыми оговорками delimited continuations можно считать альтернативным механизмом разделения чистого и грязного кода, причем более эффективным механизмом.
[User Picture]From: antilamer
2007-11-09 08:55 pm (UTC)

(Link)

Я все еще с нетерпением жду продолжения :) Как оно, ожидается?
[User Picture]From: palm_mute
2007-11-12 11:50 am (UTC)

Чувствую себя негодяем

(Link)

Я, конечно, несколько поторопился с анонсами. Дело в том, что я подготовил несколько примеров кода, только потом взялся за текст - оказалось, что внятный текст писать тяжелее, и примеры пообъемнее по-человечески разобрать не получается; выложил то, что получилось описать.

Сейчас мне примеры, которые в текст не вошли, уже кажутся неубедительными и местами проблематичными - например, я собирался показать, как можно получить нечто вроде автоматических объектов с деструкторами, но в тот момент я не знал, что в большинстве реализаций continuations плохо взаимодействуют с исключениями.

В общем, надо думать. Статей в ближайшее время не предвидится, но если я наткнусь на интересный пример использования continuations - напишу.
[User Picture]From: voidex
2007-11-30 01:14 am (UTC)

Супер

(Link)

Супер, статью на РСДН по-любому надо :)
Написано очень понятно и интересно :)
Хочется примеров поинтереснее и посложнее + правильно сказал vshabanov,
хотелось бы чуть-чуть разжевать случаи, когда внутри можно шифтов, чтобы проще было ДАО достигнуть :)

С нетерпением жду продолжения :)
[User Picture]From: palm_mute
2007-11-30 08:13 am (UTC)

Re: Супер

(Link)

Спасибо на добром слове, рад быть полезным.

На статью на РСДН точно времени и вдохновения нет.
Старые идеи для продолжения, как я уже отвечал antilamer'у, были забракованы; если неожиданно возникнут новые - буду писать. О монадах, например, уже написал. Честно говоря, я знаю немногим больше того, что уже написано :).
[User Picture]From: lazma
2008-04-30 08:50 pm (UTC)

Прописан путь в корень философии.

(Link)

"...Любое выражение (или инструкция) в программе вычисляется с какой-то
целью. Влияние, которое оказывает вычисление выражения на результат
программы в целом, зависит от контекста. Например, одно и то же
выражение "1" имеет различный эффект в различных контекстах..." Вот вот, видимо контекст вашего настроения на мою (предпредыдущую) реплику таки повлиял.
А...побудьте в тупике...вот здорово, вот прикольно!
[User Picture]From: ivan_gandhi
2011-11-26 06:00 am (UTC)

(Link)

Ну спасибо! Наверное мне мою фигню ни блоггере надо просто выкинуть - ну нету в джаваскрипте delimited continuations...
[User Picture]From: palm_mute
2011-11-29 09:16 pm (UTC)

(Link)

>...ну нету в
джаваскрипте delimited continuations.

обычных как будто тоже нет
[User Picture]From: ivan_gandhi
2011-11-27 09:10 pm (UTC)

(Link)

Поработал немножко над статьёй в вики: http://en.wikipedia.org/wiki/Delimited_continuation
Посмотрите, может чего пофиксите тоже. А то там как-то было не очень.
[User Picture]From: palm_mute
2011-11-28 09:01 am (UTC)

(Link)

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