Re: callcc/cps-style programming

[Xavier Leroy <Xavier.Leroy@inria.fr>]

> Is anyone working on callcc for OCaml?

No one that I know.  As Basile said, the problem is that the OCaml
system is resolutely stack-based, meaning that the only simple
implementation of call/cc is to copy the whole stack both at call/cc
time and when the continuation is invoked.  This is extremely slow and
not really usable.  I wrote a trivial implementation of call/cc along
these lines some time ago for an experiment with Olivier Danvy, but
it was really slow.

Faster implementations techniques for call/cc are known in the Scheme
world, such as split stacks with lazy copying, but this is hard to
implement and (in my opinion) not worth the effort given the limited
usefulness of call/cc.

Yet another direction is limited-extent continuations such as prompts,
for which a stack copying implementation might be fast enough (because
only part of the stack is copied).  Unfortunately, while there are a
bunch of papers on this topic, none gives any hints on how to do an
implementation in a stack-based execution model, and I haven't been
able to figure out the details myself.

> If the answer is no, and I want to use lightweight
> threads, I can program in CPS to make my own
> (non-preemptive) thread system.  Would large programs
> written in CPS incur any particular extra overhead
> from the current OCaml compiler/runtime?

You will incur the "normal" overhead for CPS, that is:
- lots of closure allocations (in the heap) to represent the continuations;
- no branch prediction when a continuation is invoked
  (current hardware predicts direct calls and direct returns very
  efficiently, but doesn't predict indirect jumps such as those you
  get out of invoking a continuation).

I don't think OCaml will add overhead in addition to this.  If you try
it, let us know how it goes.

> An unrelated question: suppose I have some combinators
> or whatnot that I use all the time.  If they are in
> their own file, then I assume I pay a
> cross-compilation module penalty every time I use
> them.  Is there a way to #include them instead?

Actually, there is no cross-module penalty.  The bytecode interpreter
uses the same generic, moderately efficient function call instructions
for inter-module calls and for cross-module calls.  The native-code
compiler optimizes calls to known functions, but is able to do this
equally well for local functions and for functions from other modules
(using cross-module optimization information stored in the .cmx files).
The only exception is functors, whereas calls to functions in the
functor argument are not optimized.

So, you shouldn't have to make your code less modular in order to make
it run fast, except perhaps manually inlining functors.

- Xavier Leroy