Вызов с продолжением тока - концепция сохранения состояния
После прочтения "Закаленного интригана" я почувствовал, что понял call/cc должным образом. Но, увидев некоторые трюки WOW с call/cc Я обнаружил, что был неправ.
(define cc 0)
(define (f)
(call/cc (lambda (k)
(set! cc k)
3)))
(+ 1 2 4 (f)) ; eval's to 10
(cc 13) ; eval's to 20
Это идеально соответствует моему пониманию. Я думаю, когда я достигну call/cc вызов я просто сохраняю состояние программы. и вызывая функцию рядом с ней с помощью функции. Если эта функция (k) называется откуда-то, чем я просто заменяю весь (call/cc ...) материал с заданным ему параметром. Вышеупомянутая программа, кажется, работала так же
Но,
(define (itr lst)
(define (state k)
(for-each (lambda (item)
(call/cc (lambda (h)
(set! state h)
(k item))))
lst)
(k 'done))
(define (generator)
(call/cc (lambda (k) (state k))))
generator)
(define (next)
(itr (range 2)))
призвание next 3 раза выдает 0, 1 и 'done, Это означает, что когда state использовал функцию k дано generator это не восстановило состояние программы. Я только что показал тебе, что пытался это понять.
Итак, как же call/cc на самом деле работа?
2 ответа
С продолжением прохождения стиля (без call/cc)
Может быть легче понять этот пример, если вы реализуете версию, которая использует явный стиль передачи продолжения, а не call/cc первый. В этом случае, давайте начнем с продолжения прохождения версии map:
(define (kmap fn list k)
(if (null? list)
(k list)
(fn (car list)
(lambda (head)
(kmap fn
(cdr list)
(lambda (tail)
(k (cons head tail))))))))
(define (identity x) x)
(kmap (lambda (x k) (k (+ 1 x))) '(1 2 3 4) identity)
;=> (2 3 4 5)
Если вы не знакомы со стилем прохождения продолжения, это может быть немного, чтобы обернуть голову, но это не слишком сложно. Помни что kmap а также fn каждый принимает в конце дополнительный параметр, который должен вызываться с "результатом". Поэтому, когда мы звоним fn с (car list)и проходим процедуру (lambda (head) ...) это ответственно за заботу об остальной части картирования для нас. Остальная часть отображения определяется в терминах kmap снова. Каждый звонок kmap принимает окончательное продолжение, которое ожидает получить список, полученный в результате сопоставления fn по списку.
Теперь, поскольку мы можем видеть, как отображение может быть реализовано с использованием стиля передачи продолжения, мы можем написать процедуру генерации итератора, используя его. Процедура iterator берет список и возвращает процедуру, которую мы можем вызвать, чтобы получить каждый элемент list,
(define (iterator list)
(define (next k)
(kmap (lambda (item more-next)
(set! next more-next)
(k item))
list
(lambda (results)
(k 'done))))
(lambda ()
(next identity)))
> (define get (iterator '(1 2)))
> (get)
1
> (get)
2
> (get)
done
> (get)
done
> (define get (iterator '(a b c)))
> (get)
a
> (get)
b
> (get)
c
> (get)
done
> (get)
done
Хитрость в том, что мы определяем локальную процедуру next, Это вызывает kmap с процедурой, которая уточняет next когда каждый элемент list обрабатывается как процедура, которая будет обрабатывать оставшуюся часть list, После переопределения nextэто вызывает k с элементом. Финальное продолжение перешло к kmap фактически игнорирует результаты, переданные ему, и просто вызывает k с символом done, От чего мы возвращаемся iterator это не ценность next, но процедура, которая вызывает next с продолжением identity, Отклонение здесь означает, что мы всегда называем последнее значение next с identity, Переходя identity поскольку продолжение означает, что мы просто возвращаем элемент списка.
С call/cc
Теперь, когда мы видим, как мы можем сделать это без call/ccмы лучше подготовлены, чтобы увидеть, как мы можем использовать call/cc сделать это. Напомним определение из вопроса:
(define (itr lst)
(define (state k)
(for-each (lambda (item)
(call/cc (lambda (h)
(set! state h)
(k item))))
lst)
(k 'done))
(define (generator)
(call/cc (lambda (k) (state k))))
generator)
Возврат генератора
Первое замечание, что
(define (generator)
(call/cc (lambda (k) (state k))))
generator
можно упростить до
(lambda () (call/cc (lambda (k) (state k))))
и это только то, что мы сделали в нашей реализации. Когда вы звоните это из REPL, все, что k хочет сделать, это получить значение и вернуть его (и распечатать). В нашей версии мы приближаем это, просто возвращая его без изменений. То есть мы используем identityи мы использовали имя next вместо state, Так
(lambda () (call/cc (lambda (k) (state k))))
так же, как
(lambda () (next identity))
state (или же next) процедура
Остальное
(define (state k)
(for-each (lambda (item)
(call/cc (lambda (h)
(set! state h)
(k item))))
lst)
(k 'done))
очень похоже на то, что мы сделали. Вместо того, чтобы использовать kmap и fn который принимает два аргумента (элемент и продолжение), мы используем for-each который принимает процедуру одного аргумента (элемента) и внутри этой процедуры мы используем call/cc захватить продолжение. Так
(for-each
(lambda (item)
(call/cc (lambda (h)
...
так же, как
(kmap (lambda (item h)
...
for-each не нужен окончательный аргумент продолжения, поэтому мы не можем передать игнорирование результата (lambda () (k 'done)), Вместо этого мы просто называем (k 'done) после for-each вызов. То есть,
(for-each fn list)
(k 'done)
так же, как
(kmap fn
list
(lambda (result)
(k 'done)))
Сохранение состояния программы
В обеих этих реализациях вы в некотором смысле "сохраняете состояние программы". Важное состояние, которое вы сохраняете, - это то, которое будет продолжать перебирать список.
Ваше подозрение, что что-то не так, верно. Код полностью нарушен, и это очевидно из того факта, что генератору не удается перехватить новое продолжение для основной программы всякий раз, когда он вызывается для вызова элемента. Вернее, он шарит и выбрасывает это продолжение. В результате неверное продолжение вызывается при попытке получить второй элемент, что приводит к бесконечному циклу.
Во-первых, давайте исправим что-то из формулировки вашего вопроса. призвание next не дает предметы; призвание next дает функцию генератора. Путь next Предполагается, что он будет использоваться, например:
(let ((g (next)))
(list (g) (g) (g))) ;; should return (0 1 done)
Но на самом деле это не может работать. Давайте рассмотрим это:
(define (itr lst)
(define (state k)
(for-each (lambda (item)
(call/cc (lambda (h)
(set! state h)
(k item))))
lst)
(k 'done))
(define (generator)
(call/cc (lambda (k) (state k))))
generator)
(define (next)
(itr (range 2)))
Давайте проследим, что происходит.
Настройка: когда (next) называется, выражение (iter (range 2)) возвращается generator закрытие захвачено в среде, где itr, lst а также state переменные связаны.
Первая итерация: первый вызов генератора возвращается next поэтому призывает generator, Сейчас generator фиксирует свое собственное продолжение, которое выглядит как k в lambda и передает его state, Итак, тогда state работает, и имеет generator продолжение связано с k, Он входит в первую итерацию и сохраняет свое собственное состояние, заменяя себя новым продолжением: (set! state h), На этом этапе предыдущая привязка state к define -d функция перезаписана; state теперь функция продолжения для возобновления for-each, Следующим шагом является получение item назад к k продолжение, которое возвращает нас к generator который возвращает элемент. Отлично, вот как первый элемент появляется из первого звонка (next),
Вторая итерация: с этого момента дела идут плохо. Второй вызов генератора, который был возвращен next снова, снова захватывает продолжение и вызывает state который теперь является продолжением генерации подпрограммы. Генератор передает свое собственное продолжение в state, Но state больше не та функция, которая была define по itr! И вот вновь захваченное продолжение в generator не соединяется с k параметр, который находится в лексической области for-each , когда (k item) вызывается для получения второго элемента, это k до сих пор относится к оригиналу k привязка, которая содержит первоначально захваченное продолжение в первом вызове generator, Это аналогично обратному переходу и приводит к не прекращающемуся поведению.
Вот как мы можем это исправить:
(define (itr lst)
(define yield '()) ;; forward definition (could use let for this).
(define (state) ;; k parameter is gone
(for-each (lambda (item)
(call/cc (lambda (h)
(set! state h)
(yield item)))) ;; call yield, not k
lst)
(yield 'done)) ;; yield, not k.
(define (generator)
(call/cc (lambda (self)
(set! yield self) ;; save new escape on each call
(state))))
generator)
;; test
(let ((g (itr (range 2))) ;; let's eliminate the "next" wrapper
(display (list (g) (g) (g))))
Выход (0 1 done),