search

chaos-lang / chaos

The Chaos Programming Language
https://chaos-lang.org
GNU General Public License v3.0
280 stars 17 forks source link

[RFC] Tail Call Optimization #95

Closed mertyildiran closed 3 years ago

mertyildiran commented 3 years ago

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 commented 3 years ago

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 commented 3 years ago

Another one:

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

f1(1)
mertyildiran commented 3 years ago

Implemented with:

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.