(звонок/cc): Что такое продолжение?

Этот вопрос задавался несколько раз на SO, но ни один из них не решает мой вопрос. Что такое продолжение?

Рассмотрим следующий код:

( (lambda (pair)
     (begin (print (car pair))
            ((cdr pair) (cons (+ 1 (car pair)) 
                              (cdr pair)))))

  (call/cc (lambda (k) 
             (cons 0 k))))

Эта программа бесконечно зацикливается, печатая последовательность целых чисел, начиная с 0.

Я понимаю:

Шаг 1: оценивается (call/cc (lambda (k) (cons 0 k))), возвращается пара (0 . #continuation) (что здесь #continuation)

Шаг 2: Примените пару из шага 1 к лямбда-функции. Лямбда-функция сначала выводит car, что равно 0.

Теперь я совсем потерялся. Программа оценивает (#continuation (1 . #continuation)), что мне не очень понятно. Является ли #continuation процедурой?

Что заставляет программу продолжать применять (call/cc (lambda (k) (cons 0 k))) к лямбда-функции? Чтобы он мог продолжать называть себя


functional-programming continuations scheme racket
person 齐天大圣    schedule 19.10.2015    source источник

Ответы (1)


arrow_upward
3
arrow_downward

Думаю, я понял это.

Продолжение – текущее состояние программы.

Учитывая это, прежде всего мы должны спросить: каково продолжение или текущее состояние этой программы?

Это лямбда-функция, ожидающая пары.

#continuation = ( lambda-function <placeholder>)

<placeholder> будет тем, что мы передадим этой лямбда-функции, но мы еще этого не сделали.

Теперь наша программа начинает работать, она оценивает лямбда-функцию, затем оценивает пару, возвращаемую call/cc, которая равна (0 . #continuation).

(print (car pair)) => Далее лямбда-функция выводит 0

((cdr pair) (cons (+ 1 (car pair)) (cdr pair))))) => Здесь (cdr pair) это наше continuation, которое есть (lambda-function <placeholder>), тогда наша программа передает в него новую пару. Затем программа запускает свой бесконечный цикл

person 齐天大圣    schedule 19.10.2015
comment
Ты понял. оценка ( f x ) в схеме означает оценку f для нахождения ее значения и то же самое для x (в каком-то неопределенном порядке), а затем вызов значения f со значением x в качестве приложения функции. Таким образом, контекстом для x является вызов f с предоставленным значением, которое является продолжением в этой точке. k захватывает его; cons передает его как часть пары cons. - person Will Ness; 20.10.2015
comment
и, кстати, это не связано с CPS. - person Will Ness; 20.10.2015