RE: callcc/cps-style programming

RE: callcc/cps-style programming

[Dave Berry]

Chet,

I agree with you about the (lack of) utility of call/cc.  (Although my
agreement might stem from my complete inability to understand any program
that uses it.  It really is the functional equivalent of the goto -- in
several ways).

What caught my attention in your message was your comments about threads.
Several people have found lightweight threads to be useful in GUI libraries,
and in writing server programs (although for the latter application, OS
threads offer advantages on multi-processors).  Erlang has found success,
and Erlang programs use a huge number of lightweight threads/processes.

I would like to know more about the Ousterhout paper on events vs. threads.
Does this paper put Erlang on the "events" side of the distinction, or the
"threads" side?  I.e. does "events" refer to separate processes
communicating by sending values down channels, or to the sort of event loops
found in many GUI libraries (and which are central to Windows and OS/2)?
Please could you post the full citation (or even a URL) for the paper?

Thanks,

Dave.



-----Original Message-----
From: Chet Murthy [mailto:chet@watson.ibm.com]
Sent: Saturday, December 09, 2000 18:49
To: STARYNKEVITCH Basile
Cc: Joe Lisp; caml-list@inria.fr
Subject: Re: callcc/cps-style programming 

As for lightweight threading, well, it's nice that you can implement
them with continuations, but the real purpose of threading is to
interface with some external source of events.  Every such source
(except for the lowest-level X windows protocol) requires operating
system-level thread-contexts, so you'll end up needing heavyweight
threads anyway.

Finally, well, as Ousterhout noted in his seminal paper on events
vs. threads, there are rarely any good reasons to use threads, if you
have sufficient abstraction power (closures!) in your language.

Re: callcc/cps-style programming

[Chet Murthy]

Dave,

I forget the reference -- I myself only saw it on the Web a few years
back, but I'm sure that if you find Ousterhout's publications, it
should be there.  In addition, it was (one of) the cause(s) of
Stallman's Great Anti-TCL Rant.  Not that I'm a fan of TCL.  Just
that, well, I have to give Ousterhout his props.  I give Stallman his
props, too, of course.

I do understand and agree that, often lightweight threads make certain
types of I/O-intensive applications easier to write.  But the come at
a considerable cost, which is in two forms -- performance and code
quality.

  (a) context-switching becomes expensive -- register-set swaps are
  required

  (b) programmers simply do not know how to write multi-threaded code

I've seen both of these problems in the real world.

It is well-understood at this point that unless you have
compute-intensive tasks, it is _always_ more efficient to use
user-level threads than it is to use kernel threads.  In addition, one
finds that most of the old-line operating systems did explicit
continuation-style suspension.  I.e., events, not kernel threads.
What all this means, is that the more explicitly you can get a handle
on the state that you need for your continuing computation, the more
efficient you can make that suspend/resume.  And that's important in a
server environment.

[My daily work for the past 6 years has been making high-volume
web-application servers work under extreme load conditions for large
enterprise customers.  CPU budgets matter as much as they ever did in
the '70's, if not more.  No reasonable number of extra CPUs from
CompUSA will catch up to a Super Bowl ad.]

Likewise, I've seen enough different examples, both from within the
JDK and from outside of it, of multi-threaded code causing horrors, to
believe that programmers simply don't know how to write it.

Stuff like:

  (i) allocating memory in the middle of a finalizer -- e.g., a
  finalizer which is pushing some reusable resource onto some stack
  (and the stack needs to be grown)

  (ii) locking some object in a finalizer, which can also be locked by
  some thread that which would allocate memory with that lock held.

  (iii) SMP-unsafe code galore -- race conditions, memory-incoherence,
  thrash-prone code.

This is but a short, short list.  What really bothers me about
threading, is that, well, the only good cases where threading is
palatable for vanilla programmers, are those where the threads do not
interact.  And, yeah, sure, that's nice.  But that's a pretty small
subset of the important applications in this world.

Even in transaction-processing, where all transactions are supposed to
be "isolated", that's just the _model_.  Of _course_ transactions
interact, in the way they access shared resources, pooled connections,
caches of precomputed (but slowly invalidated) data, etc.

Conclusion:

I'm not saying that threads are bad.  Rather, what I'm saying is,
there is little need, in a language like CAML, for _user-level_
threads.  Kernel threads, you need, for talking to DB2 or Oracle.
Period.  But user-level threads, implemented in the language, don't
give you much value.  Much better to do some sort of explicit (perhaps
semi-automated) CPS-conversion, and use an event-dispatcher.

Amongst other things, at least, you'll never have to worry about being
time-sliced where you didn't expect it.

--chet--

Re: callcc/cps-style programming

[T. Kurt Bond]

Chet Murthy writes:
> I'm not saying that threads are bad.  Rather, what I'm saying is,
> there is little need, in a language like CAML, for _user-level_
> threads.  Kernel threads, you need, for talking to DB2 or Oracle.
> Period.  But user-level threads, implemented in the language, don't
> give you much value.  Much better to do some sort of explicit (perhaps
> semi-automated) CPS-conversion, and use an event-dispatcher.
> 
> Amongst other things, at least, you'll never have to worry about being
> time-sliced where you didn't expect it.


Hmmm.  Well, try telling the Erlang folks that super-lightweight
user-level processes aren't useful.  Or the Gambit Scheme folks: their
next release has lightweight threads built on call/cc.  (Note: these
two things may be related.) 

http://x58.deja.com/=dnc/getdoc.xp?AN=622079764&CONTEXT=976821773.388825093&hitnum=0
http://www.ericsson.se/cslab/projects/etos.shtml
-- 
T. Kurt Bond, tkb@tkb.mpl.com

Re: callcc/cps-style programming

[Martin Berger]

"T. Kurt Bond" wrote:

> Hmmm.  Well, try telling the Erlang folks that super-lightweight
> user-level processes aren't useful.  Or the Gambit Scheme folks: their
> next release has lightweight threads built on call/cc.  (Note: these
> two things may be related.)

concerning lightweight threads and continuations, simon peyton-jones
and norman ramsey have a nice paper:

	http://www.cminusminus.org/abstracts/c--con.html

and then there's always mitch wand's classic "Continuation-Based Multiprocessing",
available from:

	http://www.ccs.neu.edu/home/wand/pubs.html

regarding the merits of using threads vs callback, i agree that
there are few working programmers who can be trusted with concurrency,
but well-designed multi-threaded programms tend to be easier to
understand. it comes down to education really. of course there are
also various performance trade-offs.


martin

Re: callcc/cps-style programming

[Julian Assange]

Chet Murthy <chet@watson.ibm.com> writes:

> Stuff like:
> 
>   (i) allocating memory in the middle of a finalizer -- e.g., a
>   finalizer which is pushing some reusable resource onto some stack
>   (and the stack needs to be grown)
> 
>   (ii) locking some object in a finalizer, which can also be locked by
>   some thread that which would allocate memory with that lock held.
> 
>   (iii) SMP-unsafe code galore -- race conditions, memory-incoherence,
>   thrash-prone code.

If code is written in a functional manner, almost all of these problems
disappear. This is why functional languages and concurrency dovetail so
nicely together. Further, in some cases you can use concurrency to hide
state changes; allowing one to write functional code where previously
it was unatural to do so.

--
 Julian Assange        |If you want to build a ship, don't drum up people
                       |together to collect wood or assign them tasks
 proff@iq.org          |and work, but rather teach them to long for the endless
 proff@gnu.ai.mit.edu  |immensity of the sea. -- Antoine de Saint Exupery

Re: callcc/cps-style programming

[Chet Murthy]

>>>>> "JA" == Julian Assange <proff@iq.org> writes:

    JA> Chet Murthy <chet@watson.ibm.com> writes:

    >> Stuff like:
    >> 
    >> (i) allocating memory in the middle of a finalizer -- e.g., a
    >> finalizer which is pushing some reusable resource onto some
    >> stack (and the stack needs to be grown)
    >> 
    >> (ii) locking some object in a finalizer, which can also be
    >> locked by some thread that which would allocate memory with
    >> that lock held.
    >> 
    >> (iii) SMP-unsafe code galore -- race conditions,
    >> memory-incoherence, thrash-prone code.

    JA> If code is written in a functional manner, almost all of these
    JA> problems disappear. This is why functional languages and
    JA> concurrency dovetail so nicely together. Further, in some
    JA> cases you can use concurrency to hide state changes; allowing
    JA> one to write functional code where previously it was unatural
    JA> to do so.

The sorts of code I described cannot be written functionally.  It
talks to the outside world, or pools resources (and no, the GC isn't
perfect, so you _do_ have to pool resoruces from time to time), or
does any of a number of other things that make it necessary to use
shared variables.

I'm an old ML programmer.  I've written lots and lots of ML code
(including what I believe was the first thread-safe SUNRPC stack -- in
SML/NJ).  But quite simply, there are things that can only be done in
a imperative manner.  Or that can only be done with shared variables.

--chet--

Re: callcc/cps-style programming

[forsyth]

Ousterhout's paper on the dangers of threading was remarkable
for failing even to mention years of research by Hoare and Milner
(amongst others) into much better ways of programming concurrent
applications than either 1960s style wait/notify style or 1970s monitors.
occam, Erlang and others applied the new techniques quite successfully.
Of course, the whole point of developing the techniques was to
address the problems listed in Ousterhout's paper!

>>Period.  But user-level threads, implemented in the language, don't
>>give you much value.  Much better to do some sort of explicit (perhaps
>>semi-automated) CPS-conversion, and use an event-dispatcher.

One reason for using them (and concurrent programming) is
simpler and clearer programs than the rats' nest that often
results from call backs and other attempts to emulate proper processes.

Re: callcc/cps-style programming

[John Max Skaller]

Chet Murthy wrote:

> As for lightweight threading, well, it's nice that you can implement
> them with continuations, but the real purpose of threading is to
> interface with some external source of events. 

	I disagree. The primary purpose of the notion of
logical thread of control is to isolate executing processes.

-- 
John (Max) Skaller, mailto:skaller@maxtal.com.au
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
checkout Vyper http://Vyper.sourceforge.net
download Interscript http://Interscript.sourceforge.net

Re: callcc/cps-style programming

[Chet Murthy]

Hmm ... I'm not sure I believe this.  I worked a lot with SML/NJ, and
aside from using continuations to implement lightweight threading, and
using them to do backtracking, there were really no good uses for
them.

We can dispatch backtracking quite easily -- in modern main-line
business and scientific applications, naive use of backtracking (which
is all that call/cc really buys you) isn't really very useful.  It's
about as useful as constraint logic programming was to operations
research.  I'm talking about economic utility -- helping problems that
matter to somebody with either money, or lives, to save.

[It's not that logic-programming doesn't have its place -- certainly,
business-rule systems could benefit from a healthy dose of
logic-programming rigor -- but rather that naive application of
techniques from programming-language research almost always falls on
its sword.  It takes a pretty careful application of all this advanced
research, to "get it right".  Witness that out of all the
implementation of ML, only CAML-Light really is fast enough, small
enough, and portable enough, to be worth bothering with.  That's a
stunning failure rate, considering how many different ML
implementations there are out there.]

As for lightweight threading, well, it's nice that you can implement
them with continuations, but the real purpose of threading is to
interface with some external source of events.  Every such source
(except for the lowest-level X windows protocol) requires operating
system-level thread-contexts, so you'll end up needing heavyweight
threads anyway.

Finally, well, as Ousterhout noted in his seminal paper on events
vs. threads, there are rarely any good reasons to use threads, if you
have sufficient abstraction power (closures!) in your language.

So, well, no, I guess I don't really see how call/cc would be a good
thing to add to CAML, or, for that matter, to any language.

I can understand that it's very useful in academic languages, like
Scheme or SML/NJ.  But for languages that (perhaps also) aspire to
real-world use, and to solving problems posed from outside the world
of programming-language semantics, well, I greatly doubt that call/cc
is a good thing.

--chet--

>>>>> "SB" == STARYNKEVITCH Basile <Basile.Starynkevitch@cea.fr> writes:
>>>>> "Joe" == Joe Lisp <joelisp@yahoo.com> writes:

    Joe> Is anyone working on callcc for OCaml?

    SB> I am not working on it (although I would like to...)

    SB> However, adding explicit continuations to Ocaml is an
    SB> important task:

Re: callcc/cps-style programming

[eijiro_sumii]

> Is anyone working on callcc for OCaml?

I have a related question: in _Scheme_, there are some implementations
of call/cc using threads.  Is this approach viable in OCaml?  That is,
is it possible to implement callcc in OCaml by using the standard
"Threads" library?  Or is it diffiult because of a typing problem or
whatever?

// Eijiro Sumii (http://www.yl.is.s.u-tokyo.ac.jp/~sumii/)
// 
// Ph.D. Student at Department of IS, University of Tokyo
// Visiting Scholar at Department of CIS, University of Pennsylvania

Re: callcc/cps-style programming

[Xavier Leroy]

> 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

callcc/cps-style programming

[STARYNKEVITCH Basile]

>>>>> "Joe" == Joe Lisp <joelisp@yahoo.com> writes:

    Joe> Is anyone working on callcc for OCaml?  

I am not working on it (although I would like to...) 

However, adding explicit continuations to Ocaml is an important task:

the naive approach -a la Appel 1989, like SML/NJ0.93- would be to
reify all continuations, ie to replace call frames by explicit
continuation closures. This means drastically changing both the
runtime (garbage collector) and the compiler system. Also, this would
slow down every OCaml application (probably by at least 10%) - but
call/cc would be rather fast (since in constant time)

another approach is to segment the call stack, and to copy the call
stack on each call/cc. This also require a GC change and probably some
(easier) compiler change. However, each call/cc would take a time
proportional to the call stack depth (which is copied). Calling a
continuation obtained by call/cc would also require copying a stack segment.

What I am missing more is the ability to dynamically load some
compiled functions (at least the Dynlink package implemented in the
native code ocamlopt, with ability to dynamically load native machine
code generated by ocamlopt; ideally I would even like to generate
garbage collected code on the fly and be able to call and marshall it)

Regards.

N.B. Any opinions expressed here are only mine, and not of my organization.
N.B. Les opinions exprimees ici me sont personnelles et n engagent pas le CEA.

---------------------------------------------------------------------
Basile STARYNKEVITCH   ----  Commissariat à l Energie Atomique 
DTA/LETI/DEIN/SLA * CEA/Saclay b.528 (p111f) * 91191 GIF/YVETTE CEDEX * France
phone: 1,69.08.60.55; fax: 1.69.08.83.95 home: 1,46.65.45.53
email: Basile point Starynkevitch at cea point fr 
web perso: http://perso.wanadoo.fr/starynkevitch/basile/

callcc/cps-style programming

[Joe Lisp]

Is anyone working on callcc for OCaml?

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?

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?

Thanks!


__________________________________________________
Do You Yahoo!?
Yahoo! Shopping - Thousands of Stores. Millions of Products.
http://shopping.yahoo.com/