Thursday, October 05, 2006

call/cc

Единственный оператор языка программирования, который вполне заслуживает звания "культового" -- это замечательный оператор call/cc, впервые появившийся в диалекте лиспа, scheme в середине 80-х годов. call/cc -- это call with current continuation. То бишь вызов функции (обычно -- лямбда-функции) с параметром, содержащим как бы контекст выполнения программы в точке вызова, который называется словом continuation. Проще показать :) Пример на ruby, где тоже есть call/cc:

def foo
for i = 1..100
    c = nil #сюда мы будем сохранять continuation
    callcc {def |x| c = x} # (**) 
                           # в фигурных скобках -
                           # лямбда-функция 
                           # сохраняет переданный 
                           # ей continuation в 
                           # переменную c
    puts i 
    return c if (i % 3) == 0 # прерываем выполнение 
                             # функции и возвращаем 
                             # continuation каждые 
                             # три итерации
end
end
Это обычная функция, печатающая числа от 1 до 100, но каждые три итерации она возвращает управление тому кто ее вызвал, а потом может продолжать работу с места где ее остановили. т.е. работает это вот так:
> t = foo()
1
2
3
> t.call # вызываем continuation, и выполнение 
         # продолжается с (**)
4
5
6
> t.call # еще разок
7
8
9
Если есть call/cc, то можно легко реализовать выходы из середины циклов, исключения, да и сами циклы. Еще стоит упомянуть про Continuation Passing Style, когда функции в качестве аргумента передается некоторый continuation в который она должна по завершении передать результат. Если функциональные языки вам не очень близки, то call/cc это суть coroutines, то бишь функции, которые возвращают значение много раз по ходу выполнения. А coroutines сейчас есть в большинстве мейнстримных языков: итераторы в C# (см. оператор yield), coroutines в lua и python. (А с точки зрения computer science оператор call/cc тесно связан с такой фундаментальной вещью как рекурсивные функции, точнее, с понятнием fixed point combinator). Линки по теме:

6 comments:

Left said...

Либо я ничего не понимаю, либо в тексте должно быть:

return c if (i % 3) == 0

Или я всё-таки ничего не понял?

lrrr said...

Да, точно, опечатался, спасибо :)

Left said...

В свою очередь хотел поблагодарить за замечательную статью :) Просто эта опечатка заставила лишних минут 10-15 поломать голову :) Но в любом случае - большое спасибо.

e.v.e said...

Может, я тоже чего-то не понимаю, но вы запускали этот пример?

когда позовётся c исполнение должно начаться с puts i (следующего оператора за callcc) выведется предыдущее значение i=3 (поскольку случился возврат и i не увеличивалось) значит случится опять же возврат всё того же c.

p.s. у меня ruby не стоит, поэтому я могу гнать...

e.v.e said...

Поставил какую-то древнюю версию ruby (1.8.5, годичной давности), сначала нифига не собралось (ошибка в синтаксисе цикла и лямбды), попинал получил предсказанный эффект: если написать прямо в программе

t = foo()
t.call

то зацикливается на выводе тройки, поскольку сохраняется глобальный контекст (т.е. и стэк вызовов)

e.v.e said...

блин, вот я некромант... этому посту сто лет в обед