5 ms·

Okay, very cute, but what if you want your language to have significant semantic differences from C and the like? What if you want to write a Scheme interpreter

Okay, very cute, but what if you want your language to have significant semantic differences from C and the like? What if you want to write a Scheme interpreter, for instance? Can I have Continuations? Can I have Tail Call Optimization? I very much doubt it. If you want to write a language that is semantically like C for the most part, than go ahead and use Truffle, but that's not where interesting language design is happening. Show me that Truffle's Ruby implementation hasn't removed callcc (yes, Ruby has callcc), and maybe I'll reconsider.

kovrik 10y ago
Don't know why you get downvoted. That's exactly what I thought. Java is my main lang and currently I'm working on my hobby project - implementing Scheme r5rs in Java. That is hard! And I doubt I'll be able to implement full r5rs even close. I have no idea (yet) how to implement Continuations: In theory yes, you can implement Continuations in any lang which has Exceptions (the only way in Java to unwind a stack). Like: https://www.politesi.polimi.it/bitstream/10589/108685/3/2015_07_Bernardini.pdf https://www.politesi.polimi.it/bitstream/10589/108685/3/2015... Proper TCO: AFAIK it is impossible in general case in object-oriented lang. That is one of the reasons why Rich Hickey decided to have explicit recur in Clojure, Yeah, you can implement your own stack and stop using Java's stack, but then you lose performance and interop: "Interop, speed, TCO -- Pick two." Rich Hickey See https://news.ycombinator.com/item?id=4922848 https://news.ycombinator.com/item?id=4922848 Then Full Numeric Tower is hard! Mostly due to the fact that Java's type system is not strong enough. I think Kawa is the best implementation of Scheme for JVM you can get now. But even Kawa has some limitations (due to JVM limits): https://www.gnu.org/software/kawa/Compatibility.html https://www.gnu.org/software/kawa/Compatibility.html
- hencq 10y ago
  You're not compiling to Java though. You're writing an AST walking interpreter, so you should be able to implement continuations and TCO just fine.
  - kovrik 10y ago
    Can you please elaborate? Because I don't see how it is different. Are you still using Java stack, Java calling convention, still able to do Java interop? When you are writing your own language on top of Java (Scheme, for example), you have full control of your lang AST (S-expressions, for example). How does it help to implement TCO and continuations (assuming you don't want to lose Java interop, Java calling convention, Java stack and performance)?
    - hencq 10y ago
      I'm definitely not an expert on this, but how the article describes it is you basically implement an AST with "execute" methods on its nodes. So that's just an interpreter that happens to use the Truffle framework to implement that AST. You can then implement continuations or TCO however you see fit. As I understand it, Graal is able to 'magically' turn that into a JIT. Again, I'm not an expert (I just read the article), but that seems very similar to how PyPy does it. The actual optimizations are different; PyPy uses tracing, while Graal uses Hotspot I think. Now, as you point out, you lose Java interop that way. However, you can imagine using Truffle + Graal to also build a similar interpreter for Java. For interop, your interpreter 'simply' has to merge in the AST for the Java interpreter (with its own 'execute' methods). As I understand it the RubyTruffle project uses a similar trick to do C interop.
      - qwertyuiop924 10y ago
        But if the calling and stack semantics are different from Java's (and the kind of have to be), than you can't just merge the ASTs. Ruby, provided you don't implement callcc, is almost, if not entirely identical in calling convention to C. So if truffle supports magical AST merging, as described, I don't think you can implement anything with a different set of conventions to C/Java.
        qwertyuiop924 10y ago
        Wait, nevermind. See above.
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.

kovrik 10y ago

Don't know why you get downvoted. That's exactly what I thought. Java is my main lang and currently I'm working on my hobby project - implementing Scheme r5rs in Java. That is hard! And I doubt I'll be able to implement full r5rs even close. I have no idea (yet) how to implement Continuations: In theory yes, you can implement Continuations in any lang which has Exceptions (the only way in Java to unwind a stack). Like: https://www.politesi.polimi.it/bitstream/10589/108685/3/2015_07_Bernardini.pdf https://www.politesi.polimi.it/bitstream/10589/108685/3/2015... Proper TCO: AFAIK it is impossible in general case in object-oriented lang. That is one of the reasons why Rich Hickey decided to have explicit recur in Clojure, Yeah, you can implement your own stack and stop using Java's stack, but then you lose performance and interop: "Interop, speed, TCO -- Pick two." Rich Hickey See https://news.ycombinator.com/item?id=4922848 https://news.ycombinator.com/item?id=4922848 Then Full Numeric Tower is hard! Mostly due to the fact that Java's type system is not strong enough. I think Kawa is the best implementation of Scheme for JVM you can get now. But even Kawa has some limitations (due to JVM limits): https://www.gnu.org/software/kawa/Compatibility.html https://www.gnu.org/software/kawa/Compatibility.html

hencq 10y ago
You're not compiling to Java though. You're writing an AST walking interpreter, so you should be able to implement continuations and TCO just fine.
- kovrik 10y ago
  Can you please elaborate? Because I don't see how it is different. Are you still using Java stack, Java calling convention, still able to do Java interop? When you are writing your own language on top of Java (Scheme, for example), you have full control of your lang AST (S-expressions, for example). How does it help to implement TCO and continuations (assuming you don't want to lose Java interop, Java calling convention, Java stack and performance)?
  - hencq 10y ago
    I'm definitely not an expert on this, but how the article describes it is you basically implement an AST with "execute" methods on its nodes. So that's just an interpreter that happens to use the Truffle framework to implement that AST. You can then implement continuations or TCO however you see fit. As I understand it, Graal is able to 'magically' turn that into a JIT. Again, I'm not an expert (I just read the article), but that seems very similar to how PyPy does it. The actual optimizations are different; PyPy uses tracing, while Graal uses Hotspot I think. Now, as you point out, you lose Java interop that way. However, you can imagine using Truffle + Graal to also build a similar interpreter for Java. For interop, your interpreter 'simply' has to merge in the AST for the Java interpreter (with its own 'execute' methods). As I understand it the RubyTruffle project uses a similar trick to do C interop.
    - qwertyuiop924 10y ago
      But if the calling and stack semantics are different from Java's (and the kind of have to be), than you can't just merge the ASTs. Ruby, provided you don't implement callcc, is almost, if not entirely identical in calling convention to C. So if truffle supports magical AST merging, as described, I don't think you can implement anything with a different set of conventions to C/Java.
      - qwertyuiop924 10y ago
        Wait, nevermind. See above.

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.