Tail Calls

Google Group
1

Hi there,

Do all the possible tail calls in ATS translate to jumps? For example,
consider the Ackerman
function below:

fun ack {n:int | n >= 0} {m:int | m >= 0} (x:int(n), y:int(m)) : [k:int | k

= 0] int(k) =
if (x > 0) then
if (y > 0) then
ack(x - 1, ack(x, y - 1))
else
ack(x - 1, 1)
else
y + 1

Ideally, I would like this to translate to a C code as below and my first
question is if this is
indeed the case:

int ack(int x, int y)
{
while (x > 0)
{
y = ack(x, y - 1);
x = x - 1;
}
return y + 1;
}

Also, another somehow related question is how to read the C file generated
by ATS. I tried
to answer my own question above by looking at the C code that ATS generates
but I could
not understand anything from it. So, my second question is if there is a
way to view
ATS-generated code in a more human-friendly manner?

Thanks,
Shahab

2

Yes, all the tail-calls are translated into jumps. For instance,
the first tail-call in the body of ack translates into the following
sequence:

ATSINSmove(tmp4, ack_0(arg0, tmp5)) ;
ATStailcalbeg()
ATSINSmove_tlcal(argx0, tmp3) ;
ATSINSmove_tlcal(argx1, tmp4) ;
ATSINSargmove_tlcal(arg0, argx0) ;
ATSINSargmove_tlcal(arg1, argx1) ;
ATSgoto(__patsflab_ack_0) ;
ATStailcalend()

The second one translates to the following:

ATStailcalbeg()
ATSINSmove_tlcal(argx0, tmp6) ;
ATSINSmove_tlcal(argx1, ATSPMVi0nt(1)) ;
ATSINSargmove_tlcal(arg0, argx0) ;
ATSINSargmove_tlcal(arg1, argx1) ;
ATSgoto(__patsflab_ack_0) ;
ATStailcalend()

Currently, there is no documentation on the C code generated from ATS
source.
This is something I intend to be working on in the near future. Hopefully,
I can still
remember what I did :slight_smile:

The C code is hard to read largely because of the very heavy use of
templates in
the code.On Thursday, March 20, 2014 8:55:45 PM UTC-4, Shahab Tasharrofi wrote:

Hi there,

Do all the possible tail calls in ATS translate to jumps? For example,
consider the Ackerman
function below:

fun ack {n:int | n >= 0} {m:int | m >= 0} (x:int(n), y:int(m)) : [k:int |k

= 0] int(k) =
if (x > 0) then
if (y > 0) then
ack(x - 1, ack(x, y - 1))
else
ack(x - 1, 1)
else
y + 1

Ideally, I would like this to translate to a C code as below and my first
question is if this is
indeed the case:

int ack(int x, int y)
{
while (x > 0)
{
y = ack(x, y - 1);
x = x - 1;
}
return y + 1;
}

Also, another somehow related question is how to read the C file generated
by ATS. I tried
to answer my own question above by looking at the C code that ATS
generates but I could
not understand anything from it. So, my second question is if there is a
way to view
ATS-generated code in a more human-friendly manner?

Thanks,
Shahab

3

Ok, great :slight_smile: It would be very nice to see the translation of a piece of
code in readable C.
It would help tremendously with writing the code.

So, I assume that tail calls would also be translated into C even if they
are not the same
function. That is, if the last part of computing function “f” is to call a
different function “g”,
then it is translated into a jump as well. Am I right?

4

No. If it is a different function, then it cannot be translated into a jump
in general as it is not clear where is the location to jump to.

You can use the keyword ‘fnx’ to combine f and g; then the compiler is
able to turn mutually tail-recursive calls into jumps. See:

http://www.ats-lang.org/EXAMPLE/EFFECTIVATS/loop-as-tailrec/main.htmlOn Thursday, March 20, 2014 9:28:26 PM UTC-4, Shahab Tasharrofi wrote:

Ok, great :slight_smile: It would be very nice to see the translation of a piece of
code in readable C.
It would help tremendously with writing the code.

So, I assume that tail calls would also be translated into C even if they
are not the same
function. That is, if the last part of computing function “f” is to call a
different function “g”,
then it is translated into a jump as well. Am I right?