4 ms·

You can do TCO relatively simply. You throw a special exception class for nonlocal control flow (eg. tail calls, breaks from loops, continues, etc.) and Graal k

by Veedrac 10y ago

You can do TCO relatively simply. You throw a special exception class for nonlocal control flow (eg. tail calls, breaks from loops, continues, etc.) and Graal knows how to optimize the cost away to a normal jump. http://cesquivias.github.io/blog/2015/01/15/writing-a-language-in-truffle-part-4-adding-features-the-truffle-way/#a-lisp-birthright-tail-call-optimization http://cesquivias.github.io/blog/2015/01/15/writing-a-langua... ZipPy (an incomplete Python implementation) supports Python's coroutines, which are faster than any other implementation. In theory these might be directly generalizable to get continuations. http://thezhangwei.com/documents/oopsla113-zhang.pdf http://thezhangwei.com/documents/oopsla113-zhang.pdf

qwertyuiop924 10y ago
The TCO sounds like an ugly hack to me, but I'll take it. How would this interact with the magical AST merging? I would assume that languages with different calling conventions can't just merge like that.
- grashalm 10y ago
  If you do it in a language specific way, you would probably need to catch those TC exceptions when calling into functions of your language. That is very easy to do, as every Truffle language controls how its functions get called in a foreign languages.
  - qwertyuiop924 10y ago
    Ah.
- Veedrac 10y ago
  Imagine you have an AST. You execute it directly, by running a node. This node will run its sub-nodes, etc. The implemented language has its own stack frames stored in specific objects. Thus the stack is actually split between those variables in the Java call stack and those in the explicit object. Let's say you're in a particular function at a tail call node. Since the tail call node is semantically (from the point of view of the Java program) many function calls deep into the implemented language's function and we want to get back to the start, we want some way of exiting a whole stack of function calls in one jump. Exceptions offer a simple and neat way to do this. You throw from the call site and catch back at the start of the function. Graal will inline all of the internal function calls up to this point, since Graal uses inlining extremely heavily. This means that Graal will see the throw site and the call site next to each other in one block of code, and consider it to just be a jump. Because Graal is just inlining Java functions, and the actual target language's call stack is stored separately as a particular object, the target language's calling convention for a large part doesn't matter. The jump to the first node doesn't invalidate any of the target language's stack - that has to be done by the language implementor manually at that point.

by Veedrac 10y ago

qwertyuiop924 10y ago

The TCO sounds like an ugly hack to me, but I'll take it. How would this interact with the magical AST merging? I would assume that languages with different calling conventions can't just merge like that.

grashalm 10y ago
If you do it in a language specific way, you would probably need to catch those TC exceptions when calling into functions of your language. That is very easy to do, as every Truffle language controls how its functions get called in a foreign languages.
- qwertyuiop924 10y ago
  Ah.
Veedrac 10y ago
Imagine you have an AST. You execute it directly, by running a node. This node will run its sub-nodes, etc. The implemented language has its own stack frames stored in specific objects. Thus the stack is actually split between those variables in the Java call stack and those in the explicit object. Let's say you're in a particular function at a tail call node. Since the tail call node is semantically (from the point of view of the Java program) many function calls deep into the implemented language's function and we want to get back to the start, we want some way of exiting a whole stack of function calls in one jump. Exceptions offer a simple and neat way to do this. You throw from the call site and catch back at the start of the function. Graal will inline all of the internal function calls up to this point, since Graal uses inlining extremely heavily. This means that Graal will see the throw site and the call site next to each other in one block of code, and consider it to just be a jump. Because Graal is just inlining Java functions, and the actual target language's call stack is stored separately as a particular object, the target language's calling convention for a large part doesn't matter. The jump to the first node doesn't invalidate any of the target language's stack - that has to be done by the language implementor manually at that point.