In article <sflnirmz11.fsf@bstde026.bbn.hp.com>,
Jens_Kilian@bbn.hp.com says...
> OK, I may have been proven wrong (I don't speak Intel assembly, so I cannot
> really tell if the generated code is good; it is certainly shorter than I'd
> have expected).

It wasn't spectacularly wonderful or anything like that, but it wasn't
what anybody could honestly call particularly bad at all.

> This is a testimonial to the state of today's compiler technology;

That is true -- just for example, using egcs 1.1, the output was
_substantially_ inferior.  Clearly, this code is right at the point
that some optimizers deal with it FAR better than others (despite the
fact that both compilers in question seem to generally produce output
of similar quality for most straightforward input).

> but
> I still maintain that continuations in C/C++ are not a good idea.

I won't argue that.  However, my view is that they're either good or
bad in their own right, and that the generated code is more or less
beside the point.  The technology to compile them well (at least in
some cases) clearly exists.  If they became widespread because
they allowed greater flexibility and expressiveness than other
methods, more compilers could undoubtedly be rewritten to handle them
efficiently.

In the long term, IMO, the use made of the language should drive
optimizers, not the other way around.  In the short term, one may have
to compromise one's use of the language to accommodate performance
requirements, but of course this should be avoided when possible.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Jens Kilian <Jens_Kilian@bbn.hp.com> writes:
[...]
> Here's a simple tail recursive factorial function:
[...]
> Here's the same in continuation-passing style:

>  void tr_factorial(int n, int f, void (*c)(int))
>  {
>    if (n <= 1)
>      c(f);
>    tr_factorial(n - 1, f * n, c);
>  }

>  void factorial(int n, void (*c)(int))
>  {
>    tr_factorial(n, 1, c);
>  }
[...]

I found this example rather unsatisfying because the continuation here
is merely an external thing.  So instead I had a go at an example
where the factorial calculation itself makes essential use of a
product continuation, with factorial(n, c) specified to apply
continuation c to the factorial of n,

  #include <iostream.h>

  struct continuation {
   virtual void operator()(int) const {}
   };

  struct make_print_cont : public continuation {
   make_print_cont(void) {}
   virtual void operator()(int q) const { cout << q << "\n"; }
   };

  struct make_prod_cont : public continuation {
   const int p;
   const continuation &c;
   make_prod_cont(int p_, const continuation &c_) : p(p_), c(c_) {}
   virtual void operator()(int q) const { c(p*q); }
   };

  void factorial(int n, const continuation &c)
  {
   if (n>1)
    factorial(n-1, make_prod_cont(n, c));
   else c(1);
  }

  int main()
  {
   factorial(4, make_print_cont());
   return 0;
  }

So the language does accommodate the technique up to a point.  I find
the behaviour of temporaries complicated in C++, but I think this is
sound, since everything happens inside a single expression, and
temporary lifetime is guaranteed until the end of the expression.

Trying to replace the tail-recursion by iteration I wrote

  void iter_factorial(int n, const continuation &c)
  {
   const continuation *p = &c;
   while (n>1)
    {
    p = new make_prod_cont(n, *p);
    n--;
    }
   (*p)(1);
  }

which seems functionally sound but leaks memory like a sieve.
Presumably one could manage this linear calling structure with some
sort of destructor, but when it comes to essential recursion (eg the
inefficient simple Fibonacci example f(n) = f(n-1) + f(n-2)) things
soon become non-trivial.

--
# A E Bass                                      Tel: (01473) 645305
# MLB 3/19, BT Laboratories                     e-mail: aeb@saltfarm.bt.co.uk
# Martlesham Heath, Ipswich, Suffolk, IP5 3RE   Do not rely on From: line
#                                               Opinions are my own


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

OK, I may have been proven wrong (I don't speak Intel assembly, so I cannot
really tell if the generated code is good; it is certainly shorter than I'd
have expected).

This is a testimonial to the state of today's compiler technology; but
I still maintain that continuations in C/C++ are not a good idea.

Greetings,

 Jens.
--
mailto:jjk@acm.org                 phone:+49-7031-14-7698 (HP TELNET 778-7698)
  http://www.bawue.de/~jjk/          fax:+49-7031-14-7351
PGP:       06 04 1C 35 7B DC 1F 26 As the air to a bird, or the sea to a fish,
0x555DA8B5 BB A2 F0 66 77 75 E1 08 so is contempt to the contemptible. [Blake]
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <sflnivmxx2.fsf@bstde026.bbn.hp.com>,
Jens_Kilian@bbn.hp.com says...

[ ... ]

> Here's the same in continuation-passing style:
>
>  void tr_factorial(int n, int f, void (*c)(int))
>  {
>    if (n <= 1)
>      c(f);
>    tr_factorial(n - 1, f * n, c);
>  }
>
>  void factorial(int n, void (*c)(int))
>  {
>    tr_factorial(n, 1, c);
>  }
>
> Note: Smart compilers may optimize the first version to use iteration instead
>       of recursion, but IMHO no C/C++ compiler in existence will generate
>       good code for the second version.  So this is just a thought experiment;
>       continuations are possible in C/C++, but are quite useless.

Hmm...I'm not sure exactly what you call "good code" but, hopefully
you'll forgive a (necessarily platform specific) example of what this
compiles to.  Here's what one fairly well know compiler (MS VC++ 6.0
SP2) produces for the main section of tr_factorial above:

$L231:
; Line 3
        cmp     edi, 1
        jg      SHORT $L220
; Line 4
        mov     ecx, esi
        call    ebx
$L220:
; Line 5
        mov     eax, edi
        imul    esi, eax
        dec     edi
        jmp     SHORT $L231

(compiler invoked with: cl /Fa /c /Oxb2 /G5ry cont_fact.cpp)

If I were writing a factorial by hand in assembly language, I _could_
beat this by about three machine cycles per iteration (reducing it
from 15 to 12).  A quick look shows that on a Pentium, this will
execute at exactly the same speed as the most obvious code I could
think up for a factorial:

int fact(int val) {

    int ret = 1;

    for (int I=2; I<val; I++)
        ret *= I;
    return ret;
}

Now, if I wanted to get clever, I could write code something like:

int fact(int val) {

 if ( val == 0 || val == 1)
  return 1;

 int ret = 1;
 do
  ret *= val;
 while (--val > 0);

 return ret;
}

and even though I'm trying to be clever and using a fair number of
tricks to help out the compiler, I end up with code that runs the same
speed again.  Now, as it happens, there is one last thing I can do,
that happens to help out this particular compiler -- I can change the
comparison to ``--val != 0'' and this particular compiler actually
produces better code.  In fact, it produces as good of code as I know
how to write by hand, running in 12 clocks per iteration.

However, without knowing that particular bit of information about this
compiler, the best code somebody wrote might well be exactly the same
speed as the one you say "...no C/C++ compiler in existence will
generate good code for..."

The moral of the story: without either examining output code, or doing
profiling, you'll OFTEN be wrong about what kind of output you get
from particular input.  Comparing code thought to be particularly
inefficient with presumably far more efficient code showed that in
reality the two ran exactly the same speed.  The change necessary to
generate any real improvement was not particularly obvious and might
easily prove useless or even counterproductive with a different
implementation.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

> From: "Scalabroni, Luigi (FL51)" <Luigi.Scalabroni@stpete.honeywell.com>
[...]
> Eventhough not a C/C++ expert, I still prefer these languages as opposed to
> experimental ones like IO, and I was wondering if we still can implement
> CONTINUATIONS in C/C++...I appreciate your time in trying to answering my
> question/comment.

You can use continuation functions, but they are not first-class citizens
in C/C++; e.g., you cannot do call-with-current-continuation, and you cannot
do anything that requires true closures (e.g., passing a continuation out of
a function).

Here's a simple tail recursive factorial function:

 int tr_factorial(int n, int f)
 {
   if (n <= 1)
     return f;
   return tr_factorial(n - 1, f * n);
 }

 int factorial(int n)
 {
   return tr_factorial(n, 1);
 }

Here's the same in continuation-passing style:

 void tr_factorial(int n, int f, void (*c)(int))
 {
   if (n <= 1)
     c(f);
   tr_factorial(n - 1, f * n, c);
 }

 void factorial(int n, void (*c)(int))
 {
   tr_factorial(n, 1, c);
 }

Note: Smart compilers may optimize the first version to use iteration instead
      of recursion, but IMHO no C/C++ compiler in existence will generate
      good code for the second version.  So this is just a thought experiment;
      continuations are possible in C/C++, but are quite useless.

HTH,
 Jens.
--
mailto:jjk@acm.org                 phone:+49-7031-14-7698 (HP TELNET 778-7698)
  http://www.bawue.de/~jjk/          fax:+49-7031-14-7351
PGP:       06 04 1C 35 7B DC 1F 26 As the air to a bird, or the sea to a fish,
0x555DA8B5 BB A2 F0 66 77 75 E1 08 so is contempt to the contemptible. [Blake]


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]