Вызов продолжение против вызова функции

Question

Рассмотрим простой пример функции факториала, написанный в псевдо типа КПС-стиля (перечисление & упорядочение промежуточных результатов опущена, как будет очень шумно):

(def (fact n k) (if (eq? n 0) (k 1) (fact (- n 1) (\result (k (* n result)))))) 

Выполняет ли вызов продолжения (k 1) (т.е. «возвращает» значение) как-то технически отличается от «нормального» вызова функции, как в else-branch? Единственное, что приходит мне на ум, состоит в том, что в этом случае продолжение - это единственное, что не имеет другого продолжения в его аргументе :)

Также вы можете сказать, что это вычисление напоминает поведение дерева DFS динамически построенное дерево, с текущим вычислением, являющимся рассматриваемым в настоящее время узлом, и «другими неисследованными ветвями» является стек вызовов/продолжение?

Answer 1

Ну, вы ответили на свой первый вопрос: техническая разница в том, что больше нет продолжения: это точка, в которой напряжение, созданное до этой точки, освобождается, т. Е. Когда на самом деле будут выполняться накопленные вычисления [по последовательность бета-сокращений]. И, конечно, с точки зрения семантики языка это обычное приложение.

Что касается второго вопроса, то я могу понять, что вы ошибаетесь, но я бы сказал, что каждое вычисление - это дерево-дерево, но дерево не динамически построено, а скорее является статическим (чаще всего бесконечным) объектом [uniquiely], определенный программой. Но тогда стек вызовов [даже если это тривиально из-за хвостовых вызовов] - это то, что вы уже прошли (от корня до текущего узла), в то время как продолжение - это ваш будущий путь с точки зрения продолжения чего-то (т. Е. в то время как вы применяете эту функцию фактов, следующий узел снова является фактом, если n равно 0).

(fact _ id) 
/ \ 
(= _ 0)? otherwise 
    |   \ 
(id 1) (fact _ (λ (x) (id (* 2 x)))) 
    |  /  \ 
    1  (= _ 0)?  otherwise 
      |    \ 
     (id (* 2 1))) (fact _ (λ (x) (id (* 2 (* 1 x))))) 
      |     /  \ 
      (id 2)    (= _ 0)? otherwise 
      |     |   \ 
      2   (id (* 2 (* 1 1))) ... 
           | 
          (id (* 2 1)) 
           | 
           (id 2) 
           | 
           2 

Если вам нравится думать в этих направлениях, вы можете прочитать о деревьях процесса, например. «Введение в онлайн-и автономную частичную оценку» Хатклиффа http://repository.readscheme.org/ftp/papers/pe98-school/hatcliff-DIKU-PE-summerschool.pdf - Кстати, тема PE интересна), и, возможно, вам могут понравиться (по крайней мере, первые 20 или около того) Скотта «Решетка диаграмм потока» (https://www.cs.ox.ac.uk/files/3223/PRG03.pdf - на самом деле imho эта статья переводит «более естественную» на прикладные функциональные языки).

Надеюсь, что дает вам некоторые идеи.