Invoking a continuation vs a function call

Question

Let us consider a simple example of a factorial function, written in a pseudo-like CPS-style (enumeration&ordering of intermediate results is omitted, as will be very noisy):

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

Does invoking a continuation (k 1) (i.e. "returning" a value) is somehow technically different to a "normal" function call, as in else-branch? The one thing that comes to my mind is that in this case, a continuation is the only thing that does not have another continuation in it's argument :)

Also, can you say that this computation is resembling a DFS tree walk of a dynamically constructed tree, with current computation being the currently explored node and "other unexplored branches" is a call stack/continuation?

The point of continuations is that they don't return. They're Goto, not Call. — Bergi

dercz dercz · Accepted Answer · 2016-08-06T22:19:47

Well, you've answered your first question: the technical difference is there's no more passing continuations: this is the point where the tension built up to this point gets released, i.e. where the accumulated computations will actually be performed [by a sequence of beta reductions]. And of course from the point of view of the language's semantics, this is an ordinary function application.

As of second question, I may understand you wrong, but I'd say that every computation is a leaf-ward tree walk, but the tree is not dynamically constructed, but rather is a static (most often infinite) object [uniquiely] defined by the program. But then, the call stack [even if it's trivial, because of tail-calls] is what you already walked through (from root to current node), while the continuation is your future path, from the point of applying continuation to something (i.e. while you're applying this fact function, the next node is fact again unless n is 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

If you like thinking in these directions, you might like to read about process trees in e.g. Hatcliff's "An Introduction to Online and Offline Partial Evaluation" http://repository.readscheme.org/ftp/papers/pe98-school/hatcliff-DIKU-PE-summerschool.pdf -- btw the topic of PE is damn interesting), and perhaps you might like (at least the first 20 or so pages) of Scott's "Lattice of flow diagrams" (https://www.cs.ox.ac.uk/files/3223/PRG03.pdf -- actually imho this paper translates "more natural" to applicative functional languages).

Hope that gives you some insights.

Invoking a continuation vs a function call

1 Answers