Я нашел этот раздел в замешательстве и в первом чтении, и только начал его получать после того, как я прочитал в другом месте о продолжениях и стилях продолжения прохождения (вот что это такое).
С риском объяснить что-то, что у вас уже есть, один из способов взглянуть на него, который помог мне, - подумать о «сборщике» или «продолжении» как о замене нормального способа возврата функции. В нормальном стиле программирования вы вызываете функцию, получаете значение и делаете что-то с ним в вызывающем. Например, стандартная рекурсивная функция length включает в себя выражение (+ 1 (length (cdr list))) для непустого случая. Это означает, что после того, как (length (cdr list)) вернет значение, произойдет подсчет ожидаемого результата с любым значением, которое мы можем назвать (+ 1 [returned value]). В обычном программировании интерпретатор отслеживает эти ожидающие вычисления, которые имеют тенденцию «складываться», как вы можете видеть в первых парах глав книги. Например, при вычислении длины списка рекурсивно мы имеем гнездо «ожидающих вычислений» как много уровней в глубину, так как список длинный.
В продолжении прохождения стиля вместо вызова функции и использования возвращаемого вызывается функция вызова, мы сообщаем функции, что делать, когда она производит свое значение, предоставляя ей «продолжение» для вызова. (Это похоже на то, что вы делаете с обратными вызовами в асинхронном программировании Javascript, например: вместо записи result = someFunction(); вы пишете someFunction(function (result) { ... }), а весь код, который использует result, входит в функцию обратного вызова).
Вот length в продолжении прохождения стиля, просто для сравнения. Я вызвал параметр продолжения return, который должен предлагать, как он функционирует здесь, но помните, что это обычная переменная Scheme, как и любая другая. (Часто параметр продолжения называется k в этом стиле).
(define (length/k lis return)
(cond ((null? lis) (return 0))
(else
(length/k (cdr lis)
(lambda (cdr-len)
(return (+ cdr-len 1)))))))
Существует полезный совет для чтения этого кода в an article on continuations by Little Schemer co-author Dan Friedman. (См. Раздел II-5, начиная со страницы 8).Перефразируя, вот что оговорка else выше говорит:
представьте, что вы есть результат вызова length/k на (cdr lis) и называют его cdr-len, затем добавьте и передать результат этого добавления вашему продолжение (return) ,
Обратите внимание, что это почти то, что переводчик должен сделать в оценке (+ 1 (length (cdr lis))) в нормальной версии функции (кроме того, что он не должен дать название промежуточного результата (length (cdr lis)). Пропуская вокруг продолжениях или обратных вызовах, мы сделали явный поток управления (и имена промежуточных значений) явным, вместо того, чтобы интерпретатор отслеживал его.
Давайте применим этот метод к каждому пункту в evens-only*&co. факт, что эта функция производит три значения, а не один: вложенный список с нечетными номерами удален; произведение четных чисел; и сумма нечетных чисел. Вот первый пункт, где (car l), как известен, четное число:
(evens-only*&co (cdr l)
(lambda (newl product sum)
(col (cons (car l) newl)
(opx (car l) product)
sum)))
Представьте себе, что у вас есть результаты удаления нечетных чисел, умножаются эвены, и добавления нечетных чисел из cdr списка, и назовите их newl, product и sum соответственно. cons глава списка на newl (так как это четное число, оно должно пойти в результате); умножить product на головку списка (с мы вычисляем произведение эвенов); оставить только sum; и передайте эти три значения в ожидаемое продолжение col.
Вот случай, когда голова списка является нечетным числом:
(evens-only*&co (cdr l)
(lambda (newl product sum)
(col newl product (op+ (car l) sum))))
Как и раньше, но проходят одни и те же значения newl и product продолжения (то есть «возвращение» их), вместе с суммой sum и главой списка, так как мы суммируем нечетные числа.
И вот последняя, где (car l) вложенный список, и который немного усложнен двойная рекурсия:
(evens-only*&co (car l)
(lambda (newl product sum)
(evens-only*&co (cdr l)
(lambda (dnewl dproduct dsum)
(col (cons newl dnewl)
(opx product dproduct)
(op+ sum dsum))))))
Imagine у вас есть результаты от удаления, суммирования и сложения чисел в (car l) и называть их newl, product и sum; то представьте, что у вас есть результаты от того же дела до (cdr l), и назовите их dnewl, dproduct и dsum.К вашему ожиданию продолжение, дайте значения, полученные cons ing newl и dnewl (так как мы составляем список списков); умножение вместе product и dproduct; и добавление sum и dsum.
Примечание: каждый раз, когда мы делаем рекурсивный вызов, мы строим новое продолжение для рекурсивного вызова, который «закрывает над» текущими значениями аргумента, l и возвратную продолжение - col, другими словами, , вы можете думать о цепочке продолжений, которую мы создаем во время рекурсии, как моделирование «стека вызовов» более условно написанной функции!
Надеюсь, что дает часть ответа на ваш вопрос. Если я немного переусердствовал, то только потому, что я думал, что после рекурсии, продолжения являются второй по-настоящему опрятной, расширяющей разум идеей в The Little Schemer и программирования в целом.
Для настройки шагомера см. Http://stackoverflow.com/questions/10499514/y-combinator-discussion-in-the-little-schemer/10500358#10500358 – soegaard