Re: call/cc

[address@hidden (Kragen Sitaker)]

jmarshall@mak.com writes:
> kragen@pobox.com writes:
> > It also depends on how well your language supports closures.  Writing
> > explicit CPS is more of a problem in C than in JavaScript or Scheme.
> 
> You can get away with it in C because you can cast types to void *,
> but since C (and C++) don't have recursive function types, it is
> difficult to write CPS style code `in the language' (i.e., making use
> of the language features as intended).

Yes.  Also, C requires your functions to be at the top level and
doesn't have lambda, not even a lambda that doesn't create closures.

> > I like to think I already have CPS in my repertoire; I've written a
> > few thousand lines in C and JavaScript that way, and I still think

(also a few thousand lines in Python with asyncore; I'd forgotten
about that, partly because it wasn't as bad.  I was writing an HTTP
server, which doesn't need to interleave computation and
possibly-blocking operations very much.)

> > it's hard to read and understand.  You can't write compound
> > expressions, your only control structure is "goto", and the extra
> > noise in your source code introduced by defining functions, anonymous
> > and otherwise, all over the place makes it still harder to follow.
> 
> You can use recursion and constructs other than `goto' (tail-recursive
> calls) in CPS.

We must be talking about different things.  In the CPS I'm talking
about, you can't use recursion in the ordinary way, because none of
your calls ever return.  'Recursion' becomes 'goto with values'.
Writing a peremptory sequence of four I/O operations requires writing
four functions, each of which explicitly points to its successor.  (If
the I/O operations do conditional branching, each must point to its
successor twice.)  It reminds me of Mel and the Royal McBee.  ("Put
that in Pascal's pipe and smoke it.")

> I don't find the excess noise that distracting in Scheme, but I really
> wish there was a truly concise syntax for lambda expressions,
> especially if they are to be used for CPS.  In other languages (such
> as Java), the amount of excess noise is horrendous.

I don't understand Smalltalk's blocks (I wish David Simmons would
explain in more detail; I thought they were just lambdas, and I don't
understand what they have to do with continuations) but I think they
express (lambda (x) (+ x 1)) as [:x | x + 1].  Perl (in some special
contexts) expresses it as { $_ + 1 } (which pg said he wanted to
emulate in Arc), but that doesn't extend cleanly to general functions.
Haskell expresses it as (\x -> x + 1), which is roughly as noisy as
Smalltalk.

Here's a little bit of interlingual comparison --- what does it take
to construct a new anonymous function that adds its two arguments and
apply it to two numbers?

Perl: sub { $_[0] + $_[1] }->(3, 5)      18 tokens ($_ and -> are 1 token each)
JavaScript: function(x, y){return x + y}(3, 5)
                                         17 tokens
Lisp: ((lambda (x y) (+ x y)) 3 5)       16 tokens
Smalltalk: [:x :y | x + y] valueWithArguments: #(3 5)
                                         15 tokens
Python: (lambda x, y: x + y)(3, 5)       15 tokens
OCaml: (fun x y -> x + y) 3 5            10 tokens
Haskell: (\x y -> x + y) 3 5             10 tokens (\x is 2 tokens, -> is 1)
FORTH: marker foo  3 5 :noname + ; execute  foo
                                         9 tokens (explicit cleanup)
FORTH: 3 5 :noname + ; execute           6 tokens (cheating because no GC)
PostScript: 3 5 {add} exec               6 tokens
dc: 3 5 [+] x                            6 tokens

6 tokens is probably the minimal a reasonable language can hope to do
here (although none of the languages I think of as reasonable made it
there.)

What does it look like in Java?

An approximate C version follows.

struct twoargs { int x; int y; };
int addtwoargs(void *arg) {
    twoargs *argt = arg;
    return argt->x + argt->y;
}
...
   struct twoargs foo = {3, 5};
   int (*argp)(void *) = addtwoargs;
   argp((void*)foo)

66 tokens, by my count.