Re: Continuations

BGB <cr88192@gmail.com> writes:

On 7/13/2024 2:50 AM, Lawrence D'Oliveiro wrote:

Has there ever been a hardware architecture that managed the flow of
control via "continuations"?

RISCs usually have no architectural support for stack-based calling
conventions, so they work just as well for managing the flow of
control via continuations.

Doing an ABI based around continuations would basically wreck performance;
Conventional thread-based multitasking is cheaper to implement and gives
better performance.
>
There is basically no real way to get dynamically allocated stack-frames
and argument copying to be performance competitive with adjusting a
stack pointer and passing arguments in registers. Function calls are
also, not exactly rare.

Quite a while ago "continuation-passing style" was a hot research
topic (see some references below; I found [appel&jim89] more inspiring
than [appel92]), and AFAIK a number of compilers used this concept
(and some probably still use it, especially Scheme compilers, where
continuations are a language feature).

Around that time there was the argument (maybe also by Appel, but I
don't remember) that, in the limit, garbage collection is cheaper than
stack-based allocation (never mind malloc/free): If you delay garbage
collection long enough, the cost of a copying garbage collector will
be smaller than the cost of stack-deallocating the garbage.  That's a
copying garbage collector only accesses and copies the non-garbage.

In practice, you don't want to provide so much memory that this point
will be reached, plus stack-based allocation has better cache
characteristicts.

@InProceedings{appel&jim89,
  author = "Andrew W. Appel and Trevor Jim",
  title = "Continuation-Passing, Closure-Passing style",
  booktitle = "Sixteenth Annual {ACM} Symposium on Principles of
Programming Languages",
  year = "1989",
  pages = "293--302",
  address = "Austin, Texas",
  annote = "ML compiler based on continuation passing style.
After the translation into CPS and optimization
closures are made explicit and registers are
allocated. No stack is used for the closures. Instead
the compiler relies on garbage collection."
}

@Book{appel92,
  author = "Andrew W. Appel",
  title = "Compiling with Continuations",
  publisher = "Cambridge University Press",
  year = "1992"
}

@InProceedings{flanagan+93,
  author = "Cormac Flanagan and Amr Sabry and Bruce F. Duba and
  Matthias Felleisen",
  title = "The Essence of Compiling with Continuations",
  crossref = "sigplan93",
  pages = "237--247",
  annote = "CPS compilers convert into CPS form, optimize the
  program and convert back. Isomorphic optimizations can
  be performed on the original program, saving the
  transformation to and from CPS form."
}

@Proceedings{sigplan93,
  booktitle = "SIGPLAN '93 Conference on Programming Language
  Design and Implementation",
  title = "SIGPLAN '93 Conference on Programming Language
  Design and Implementation",
  year = "1993",
  key = "SIGPLAN '93",
  note = "SIGPLAN Notices 28(6)"
}

@InProceedings{bruggeman+96,
  author = {Carl Bruggeman and Oscar Waddel and R. Kent Dybvig},
  title = {Representing Control in the Presence of One-Shot
                  Continuations},
  crossref = {sigplan96},
  pages = {99--107},
  annote = {Discuss how to represent multi-shot continuations
                  and one-shot continuations in a stack-based Scheme
                  implementation. One-shot continuations are
                  programmer-specified (with the \emph{call/1cc}
                  call). They offer a small (about 13\% in the threads
                  benchmarks) performance benefit over multi-shot
                  continuations, if they are applicable.}
}

@Proceedings{sigplan96,
  booktitle = "SIGPLAN '96 Conference on Programming Language
  Design and Implementation",
  title = "SIGPLAN '96 Conference on Programming Language
  Design and Implementation",
  year = "1996",
  key = "PLDI '96"
}

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
  Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>