Re: [Haskell-cafe] Haskell on JVM
Claus Reinke wrote: |Basically, the JVM lacks a native ability to do tail calls. It does |not have an instruction to remove/replace a stack frame without |executing an actual return to the calling method/function. There is a conflict between preserving stack layout and efficient tail calls. Unfortunately, stack inspection appears to be used for security aspects in JVM. That doesn't make tail calls impossible, but may have slowed down progress as this argument always comes up in discussing tail calls on the JVM (since its byte code isn't just an internal detail, but an externally used API). It's a bugbear, but it's not impossible: http://www.ccs.neu.edu/scheme/pubs/esop2003-cf.pdf http://www.ccs.neu.edu/scheme/pubs/cf-toplas04.pdf Maybe one day it'll be here. -- Live well, ~wren ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell on JVM
Incidentally, I am looking for someone well versed in the JVM who wants to help spearhead a JVM back end for jhc. I would love to see this! With the current advent of all those languages targeting at the JVM (Groovy, Scala, Clojure) I think a JVM backend for a Haskell compiler could, together with proper Java interop, make for a major breakthrough of Haskell in general. Unforunately, as I can tell from my halfknowledge, the JVM lacks some important functionality required for properly targeting functional language features on the JVM. And here comes my question: If there is anybody with proper knowledge about this issue, I would really like to know what are those things that are missing? For example, Clojure lacks proper tail recrusion optimization due to some missing functionality in the JVM. But does anybody know the details? Thanks, Timo ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell on JVM
Although I don't know what the current JVM lacks to properly act as a functional backend, it appears that JVM 1.7 will be at least better suitable to support dynamic languages. See: The Da Vinci Machine Project http://openjdk.java.net/projects/mlvm/ Arvid On Fri, Jun 26, 2009 at 2:09 PM, Timo B. Hübelt...@gmx.info wrote: Incidentally, I am looking for someone well versed in the JVM who wants to help spearhead a JVM back end for jhc. I would love to see this! With the current advent of all those languages targeting at the JVM (Groovy, Scala, Clojure) I think a JVM backend for a Haskell compiler could, together with proper Java interop, make for a major breakthrough of Haskell in general. Unforunately, as I can tell from my halfknowledge, the JVM lacks some important functionality required for properly targeting functional language features on the JVM. And here comes my question: If there is anybody with proper knowledge about this issue, I would really like to know what are those things that are missing? For example, Clojure lacks proper tail recrusion optimization due to some missing functionality in the JVM. But does anybody know the details? Thanks, Timo ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell on JVM
On 26 Jun 2009, at 14:09, Timo B. Hübel wrote: And here comes my question: If there is anybody with proper knowledge about this issue, I would really like to know what are those things that are missing? For example, Clojure lacks proper tail recrusion optimization due to some missing functionality in the JVM. But does anybody know the details? Basically, the JVM lacks a native ability to do tail calls. It does not have an instruction to remove/replace a stack frame without executing an actual return to the calling method/function. With the heavy use of recursion in functional programs, this is an important feature in a language implementation to avoid stack overflows. Some language implementations (Scala) can do partial workarounds by turning the generated code into a loop in the compiler, but this is frequently limited to only deal with self-recursive calls, and does not deal with the general case (X-calls-Y-calls-Z-calls-X...), which a proper implementation of tail- calls at the JVM level would allow. At the JIT level (below the JVM spec level) some implementations may actually do the tail call optimization anyway, but this is beyond the control of a language implementation, and would result in a situation where the behaviour of your program depends on particular implementations/versions/parameters of the JVM running it. That is something to be avoided if possible. Maarten Hazewinkel maarten.hazewin...@gmail.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell on JVM
There has been a scheme with tail recursion on the JVM for a long time IIRC. SISC right? At least I am fairly certain it does. On Friday, June 26, 2009, Timo B. Hübel t...@gmx.info wrote: Incidentally, I am looking for someone well versed in the JVM who wants to help spearhead a JVM back end for jhc. I would love to see this! With the current advent of all those languages targeting at the JVM (Groovy, Scala, Clojure) I think a JVM backend for a Haskell compiler could, together with proper Java interop, make for a major breakthrough of Haskell in general. Unforunately, as I can tell from my halfknowledge, the JVM lacks some important functionality required for properly targeting functional language features on the JVM. And here comes my question: If there is anybody with proper knowledge about this issue, I would really like to know what are those things that are missing? For example, Clojure lacks proper tail recrusion optimization due to some missing functionality in the JVM. But does anybody know the details? Thanks, Timo ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell on JVM
Hi Timo, On Fri, Jun 26, 2009 at 5:09 AM, Timo B. Hübel t...@gmx.info wrote: Incidentally, I am looking for someone well versed in the JVM who wants to help spearhead a JVM back end for jhc. I would love to see this! With the current advent of all those languages targeting at the JVM (Groovy, Scala, Clojure) I think a JVM backend for a Haskell compiler could, together with proper Java interop, make for a major breakthrough of Haskell in general. Unforunately, as I can tell from my halfknowledge, the JVM lacks some important functionality required for properly targeting functional language features on the JVM. And here comes my question: If there is anybody with proper knowledge about this issue, I would really like to know what are those things that are missing? For example, Clojure lacks proper tail recrusion optimization due to some missing functionality in the JVM. But does anybody know the details? My brief research into why the JVM lacks tail calls indicated that tail calls do not play nicely with the JVM security model and make stack traces harder to manage. Although, I have also heard that tail call of some form is expected to appear in java 1.7. Jason ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell on JVM
On Fri, Jun 26, 2009 at 7:12 AM, David Leimbach leim...@gmail.com wrote: There has been a scheme with tail recursion on the JVM for a long time IIRC. SISC right? Ah SISC is interpreted. Clojure is compiled. At least that may be the key difference to making it work or not. At least I am fairly certain it does. On Friday, June 26, 2009, Timo B. Hübel t...@gmx.info wrote: Incidentally, I am looking for someone well versed in the JVM who wants to help spearhead a JVM back end for jhc. I would love to see this! With the current advent of all those languages targeting at the JVM (Groovy, Scala, Clojure) I think a JVM backend for a Haskell compiler could, together with proper Java interop, make for a major breakthrough of Haskell in general. Unforunately, as I can tell from my halfknowledge, the JVM lacks some important functionality required for properly targeting functional language features on the JVM. And here comes my question: If there is anybody with proper knowledge about this issue, I would really like to know what are those things that are missing? For example, Clojure lacks proper tail recrusion optimization due to some missing functionality in the JVM. But does anybody know the details? Thanks, Timo ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell on JVM
For example, Clojure lacks proper tail recrusion optimization due to some missing functionality in the JVM. But does anybody know the details? |Basically, the JVM lacks a native ability to do tail calls. It does |not have an instruction to remove/replace a stack frame without |executing an actual return to the calling method/function. There is a conflict between preserving stack layout and efficient tail calls. Unfortunately, stack inspection appears to be used for security aspects in JVM. That doesn't make tail calls impossible, but may have slowed down progress as this argument always comes up in discussing tail calls on the JVM (since its byte code isn't just an internal detail, but an externally used API). None of the various partial workarounds are quite satisfactory (jumps work only locally, there is an upper size limit on how much code can be considered as local, trampolines return before each call, there are alternatives that clear the stack not before each call, but every n calls, ..., see the various Haskell to Java/JVM papers). I was curious about the current state (the issue is as old as JVM), and here's what I've found so far (more concrete/official info would be appreciated): tail calls in the VM [2007] http://blogs.sun.com/jrose/entry/tail_calls_in_the_vm RFE: Tail Call Optimization [2002] http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4726340 [2009] http://wikis.sun.com/display/mlvm/TailCalls Tail Call Optimization in the Java HotSpot(TM) VM [2009] http://www.ssw.uni-linz.ac.at/Research/Papers/Schwaighofer09Master/ Still cooking, still not done, it seems, but perhaps closer than ever? Claus ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell on JVM
Since the JVM doesn't seem to support tail call optimization, I suppose one could could directly manipulate the bytecodes generated by jhc to do TCO. One challenge would be the garbage collector, since Haskell and Java have very different working sets of what is still being used. -- Regards, Casey ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell on JVM
JVM 7 has tail calls, and if you don't want to wait for that, goto works perfectly well for self-recursive functions. Other techniques can deal with mutual recursion, albeit at the cost of performance. Regards, John A. De Goes N-Brain, Inc. The Evolution of Collaboration http://www.n-brain.net|877-376-2724 x 101 On Jun 26, 2009, at 6:26 AM, Maarten Hazewinkel wrote: On 26 Jun 2009, at 14:09, Timo B. Hübel wrote: And here comes my question: If there is anybody with proper knowledge about this issue, I would really like to know what are those things that are missing? For example, Clojure lacks proper tail recrusion optimization due to some missing functionality in the JVM. But does anybody know the details? Basically, the JVM lacks a native ability to do tail calls. It does not have an instruction to remove/replace a stack frame without executing an actual return to the calling method/function. With the heavy use of recursion in functional programs, this is an important feature in a language implementation to avoid stack overflows. Some language implementations (Scala) can do partial workarounds by turning the generated code into a loop in the compiler, but this is frequently limited to only deal with self-recursive calls, and does not deal with the general case (X-calls-Y-calls-Z-calls-X...), which a proper implementation of tail-calls at the JVM level would allow. At the JIT level (below the JVM spec level) some implementations may actually do the tail call optimization anyway, but this is beyond the control of a language implementation, and would result in a situation where the behaviour of your program depends on particular implementations/versions/parameters of the JVM running it. That is something to be avoided if possible. Maarten Hazewinkel maarten.hazewin...@gmail.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell on JVM
Maybe the JVM could be abused so that all of the haskell code is within one function, so as to avoid java's notion of a function boundary and implement our own using just goto? Or does the JIT operate on entire functions at a time? On Fri, Jun 26, 2009 at 1:23 PM, John A. De Goesj...@n-brain.net wrote: JVM 7 has tail calls, and if you don't want to wait for that, goto works perfectly well for self-recursive functions. Other techniques can deal with mutual recursion, albeit at the cost of performance. Regards, John A. De Goes N-Brain, Inc. The Evolution of Collaboration http://www.n-brain.net | 877-376-2724 x 101 On Jun 26, 2009, at 6:26 AM, Maarten Hazewinkel wrote: On 26 Jun 2009, at 14:09, Timo B. Hübel wrote: And here comes my question: If there is anybody with proper knowledge about this issue, I would really like to know what are those things that are missing? For example, Clojure lacks proper tail recrusion optimization due to some missing functionality in the JVM. But does anybody know the details? Basically, the JVM lacks a native ability to do tail calls. It does not have an instruction to remove/replace a stack frame without executing an actual return to the calling method/function. With the heavy use of recursion in functional programs, this is an important feature in a language implementation to avoid stack overflows. Some language implementations (Scala) can do partial workarounds by turning the generated code into a loop in the compiler, but this is frequently limited to only deal with self-recursive calls, and does not deal with the general case (X-calls-Y-calls-Z-calls-X...), which a proper implementation of tail-calls at the JVM level would allow. At the JIT level (below the JVM spec level) some implementations may actually do the tail call optimization anyway, but this is beyond the control of a language implementation, and would result in a situation where the behaviour of your program depends on particular implementations/versions/parameters of the JVM running it. That is something to be avoided if possible. Maarten Hazewinkel maarten.hazewin...@gmail.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell on JVM
On Fri, Jun 26, 2009 at 10:44 AM, Daniel Peeblespumpkin...@gmail.com wrote: Maybe the JVM could be abused so that all of the haskell code is within one function, so as to avoid java's notion of a function boundary and implement our own using just goto? Or does the JIT operate on entire functions at a time? As I recall, this has been tried, but there's a limit (64k?) on function body size that you immediately run in to. Also, this would seem likely to get seriously in the way of optimizations and use of the JVM's slightly-higher-than-assembly level of abstraction. I think the second reason, for example, is why people (to my knowledge) haven't tried the otherwise well suited Cheney-on-the-MTA scheme...Stack as nursery is cute, but I think you want to work with the JVM, not against it. AHH ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell on JVM
JVM 7 has tail calls, Source, please? JSR-292 seems the most likely candidate so far, and its draft doesn't seem to mention tail calls yet. As of March this year, the people working on tail calls for mlvm [1], which seems to be the experimentation ground for this, did not seem to expect any fast route: http://mail.openjdk.java.net/pipermail/mlvm-dev/2009-March/000405.html There have been years of rumours and plans, so it would be nice to have concrete details, before any fp-on-jvm implementation design starts to rely on this. Claus [1] http://openjdk.java.net/projects/mlvm/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell on JVM
I don't have a source, but I know tail calls have been implemented (in a patch) and tested, and at the JVM Summit everyone was saying this was definitely going to be released in JVM 7. Regards, John A. De Goes N-Brain, Inc. The Evolution of Collaboration http://www.n-brain.net|877-376-2724 x 101 On Jun 26, 2009, at 11:27 AM, Claus Reinke wrote: JVM 7 has tail calls, Source, please? JSR-292 seems the most likely candidate so far, and its draft doesn't seem to mention tail calls yet. As of March this year, the people working on tail calls for mlvm [1], which seems to be the experimentation ground for this, did not seem to expect any fast route: http://mail.openjdk.java.net/pipermail/mlvm-dev/2009-March/000405.html There have been years of rumours and plans, so it would be nice to have concrete details, before any fp-on-jvm implementation design starts to rely on this. Claus [1] http://openjdk.java.net/projects/mlvm/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell on JVM
On Fri, Jun 26, 2009 at 03:26:34PM +0200, Maarten Hazewinkel wrote: On 26 Jun 2009, at 14:09, Timo B. Hübel wrote: And here comes my question: If there is anybody with proper knowledge about this issue, I would really like to know what are those things that are missing? For example, Clojure lacks proper tail recrusion optimization due to some missing functionality in the JVM. But does anybody know the details? Basically, the JVM lacks a native ability to do tail calls. It does not have an instruction to remove/replace a stack frame without executing an actual return to the calling method/function. With the heavy use of recursion in functional programs, this is an important feature in a language implementation to avoid stack overflows. This is part of the reason I think jhc might be a good haskell compiler for the jvm, it requires no special tail call support of its back end. It translates all recursion into explicit code flow operations. (even complex things, like co-recursive functions and join points) John -- John Meacham - ⑆repetae.net⑆john⑈ - http://notanumber.net/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell on JVM
2009/06/24 Greg Meredith lgreg.mered...@biosimilarity.com: Better support for std Haskell syntax What does this mean, actually? Better support for standard Haskell syntax than what? -- Jason Dusek ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell on JVM
Jason, CAL's syntax is not std Haskell syntax. Best wishes, --greg On Thu, Jun 25, 2009 at 11:10 AM, Jason Dusek jason.du...@gmail.com wrote: 2009/06/24 Greg Meredith lgreg.mered...@biosimilarity.com: Better support for std Haskell syntax What does this mean, actually? Better support for standard Haskell syntax than what? -- Jason Dusek -- L.G. Meredith Managing Partner Biosimilarity LLC 1219 NW 83rd St Seattle, WA 98117 +1 206.650.3740 http://biosimilarity.blogspot.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell on JVM
Incidentally, I am looking for someone well versed in the JVM who wants to help spearhead a JVM back end for jhc. If someone is interested, please join the j...@haskell.org mailing list. Jhc already cross compiles to a number of architectures so it may be an easier task than a ghc port. (or good practice for eventually writing the ghc port :)). I have a basic plan for how to go about it, but just don't know enough about the JVM internals/API to do it on my own. John -- John Meacham - ⑆repetae.net⑆john⑈ - http://notanumber.net/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell and JVM
Hello, I stumbled upon your discussion on haskell-cafe and this theme seems to pop up one time or another. If someone is interested, I have some Java code for compiling Haskell98 to bytecode that I would be more than willing to share. It is not in the best shape and does not implement all of haskell but most low-level work to generate classes and bytecode from haskell code is implemented (patternmatching, data constructors, lazy functions, ...). This is a project I started some years ago and used for specification of simple functional behaviour (without complex type system) in Java. Regards, -- Arnaud Bailly, Dr. - Ingénieur de Recherche NORSYS 1, rue de la Cense des Raines ZAC du Moulin 59710 ENNEVELIN Tel : (33) 3 28 76 56 76 Mob : (33) 6 17 12 19 78 Fax : (33) 3 28 76 57 00 Web : http://www.norsys.fr ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell and JVM
Hi, up one time or another. If someone is interested, I have some Java code for compiling Haskell98 to bytecode that I would be more than willing to share. It is not in the best shape and does not implement You might also be interested in: http://www.brianweb.net/personal/blog/entry.php?id=18 Currently this is only a runtime, which allows running full Haskell in a JVM. A bytecode translator was being worked on, although I don't know the progress that has been made recently. Thanks Neil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell and JVM
Questions about Haskell for JVM or .NET was asked quite often and it is really interesting question. Since the JVM and .NET machines have a lot of common if there was a compiler for one of them then it can retargeted to the other quite easily. The major problem with such compilers is the performance. Many attempts exists but no one has managed to build a complete solution. There are several major problems: - How to represent the G/STG machine stack in JVM/.NET? The naive solution is to use an array but it is proven to be inefficient. - How to minimize the runtime typecasts? They are necessary because the JVM/.NET type system is a lot weaker than the Haskell's one. - How to efficiently represent the IO monad and exceptions? - How to make the integration of Haskell with Java/C# easier? Since usually the performance of all VM languages is worse than those of the native compiled (C/C++), I think that it is acceptable for Haskell for JVM/.NET to be slower than GHC for example. Even that if the performance isn't so worse then it will be usable since it can be used in existing Java/.NET projects. Cheers, Krasimir 2006/2/2, Arnaud Bailly [EMAIL PROTECTED]: Hello, I stumbled upon your discussion on haskell-cafe and this theme seems to pop up one time or another. If someone is interested, I have some Java code for compiling Haskell98 to bytecode that I would be more than willing to share. It is not in the best shape and does not implement all of haskell but most low-level work to generate classes and bytecode from haskell code is implemented (patternmatching, data constructors, lazy functions, ...). This is a project I started some years ago and used for specification of simple functional behaviour (without complex type system) in Java. Regards, -- Arnaud Bailly, Dr. - Ingénieur de Recherche NORSYS 1, rue de la Cense des Raines ZAC du Moulin 59710 ENNEVELIN Tel : (33) 3 28 76 56 76 Mob : (33) 6 17 12 19 78 Fax : (33) 3 28 76 57 00 Web : http://www.norsys.fr ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe