[RFC] Tail Call Optimization

[mertyildiran]

Right now the below Chaos program ends with a Maximum recursion depth 1000 exceeded! error:

void def f1()
    print "f1"
    f2()
end

void def f2()
    print "f2"
    f1()
end


f1()

$ chaos dev.kaos
...
f2
f1
f2
f1
f2
f1
f2
  Chaos Error:                                 
    Module: dev.kaos                           
    Line: 7                                    
    Maximum recursion depth 1000 exceeded!     

1000 maximum recursion depth limit added to prevent stack overflow. A functional language should be tail recursion optimized. So there should be no such limit. The recursive function calls should be done with goto or longjmp instead of direct C function calls.

Here is another example to demonstrate the maximum recursion depth limit:

void def f1(num x)
    x++
    print x
    f1(x)
end


f1(1)

$ chaos dev.kaos
...
995
996
997
998
999
1000
1001
  Chaos Error:                                 
    Module: dev.kaos                           
    Line: 3                                    
    Maximum recursion depth 1000 exceeded!     

[mertyildiran]

Here is another example that demonstrates the same problem inside decision blocks:

void def f1()
    print "f1"
end {
    default: f2()
}

void def f2()
    print "f2"
end {
    default: f1()
}


f1()

[mertyildiran]

Another one:

void def f1(num x)
    x++
    print x
end {
    default : f1(x)
}


f1(1)

[mertyildiran]

Implemented with:

• a414834
• 5a4807f
• e5e3f9f
• d4567d6
• 294a62f
• 94677f9
• a3a2480
• 6204121
• 352e2f8

Clang on Windows does not supported because the linker does support setting the stack size.

Considering the above examples;

Non-tail call recursion:

void def f1(num x)
    x++
    print x
    f1(x)
end


f1(1)

$ timeout 10 chaos dev.kaos
...
12981
12982
12983
$ chaos -c dev.kaos
$ timeout 10 build/main
...
13647
13648
13649

Tail call recursion:

void def f1(num x)
    x++
    print x
end {
    default : f1(x)
}


f1(1)

$ timeout 10 chaos dev.kaos
...
1514549
1514550
1514551
$ chaos -c dev.kaos
$ timeout 10 build/main
...
1755181
1755182
1755183

Conclusion

Tail calls in Chaos are approximately 120 times faster than the generic recursion. Therefore the tail calls are optimized in Chaos.