Discussion:
[gambit-list] A question about CPS conversion
C K Kashyap
2018-07-10 21:54:16 UTC
Permalink
Hi Marc et al,

I've been exploring the 90-minutes scheme to c and trying to get my head
around it. I think I am pretty close to the aha moment.

I have a question though - Is there any limitation to CPS conversation? As
in, are there programs that cannot be transformed such that all calls are
tail calls?

If I understood it right - the 90 minutes scheme to C implementation has
not taken any short cut and is turning complete - my logic of arriving at
this conclusion is simple - you can define functions and call them so it's
complete lambda calculus and so turning complete :) - is that correct?

Regards,
Kashyap
C K Kashyap
2018-07-10 22:26:35 UTC
Permalink
Pardon my typo - I meant Turing complete :) - it was perhaps a case of my
subconscious rendering the state of my head :) (Thanks to Bakul for
pointing it out).
Regards,
Kashyap
Post by C K Kashyap
Hi Marc et al,
I've been exploring the 90-minutes scheme to c and trying to get my head
around it. I think I am pretty close to the aha moment.
I have a question though - Is there any limitation to CPS conversation? As
in, are there programs that cannot be transformed such that all calls are
tail calls?
If I understood it right - the 90 minutes scheme to C implementation has
not taken any short cut and is turning complete - my logic of arriving at
this conclusion is simple - you can define functions and call them so it's
complete lambda calculus and so turning complete :) - is that correct?
Regards,
Kashyap
Alex Silva
2018-07-11 07:40:18 UTC
Permalink
Hi,
Post by C K Kashyap
I have a question though - Is there any limitation to CPS conversation?
As in, are there programs that cannot be transformed such that all calls
are tail calls?
There are no limitations, the CPS conversion is a total transformation.
The evaluation of any expression in Scheme has necessarily a
continuation, the transformation just makes this continuation explicit.
Post by C K Kashyap
If I understood it right - the 90 minutes scheme to C implementation has
not taken any short cut and is turning complete - my logic of arriving
at this conclusion is simple - you can define functions and call them so
it's complete lambda calculus and so turning complete :) - is that correct?
Basically, yes.

Cheers,
--
-alex
https://unendli.ch/
Loading...