Re: [Haskell-cafe] Code generation and optimisation for compiling Haskell
JHC itself is based upon Boquist's GRIN language described in his PhD thesis: Code Optimization Techniques for Lazy Functional Languages http://mirror.seize.it/papers/Code%20Optimization%20Techniques%20for%20Lazy%20Functional%20Languages.pdf On 13 January 2012 01:50, Jason Dagit dag...@gmail.com wrote: On Tue, Jan 10, 2012 at 9:25 AM, Steve Horne sh006d3...@blueyonder.co.uk wrote: Also, what papers should I read? Am I on the right lines with the ones I've mentioned above? Thomas Schilling gave you a good response with papers so I will give you a different perspective on where to look. Most of the Haskell implementations were written by academics studying languages and compilers. This is good but it also implies that the implementors are likely to share biases and assumptions. I know of one Haskell compiler in particular that was written by someone who did not know Haskell when starting the project. The compiler was developed to be different than GHC. That person was John Meacham. He created JHC, a work in progress, so you might want to study his compiler and implementation notes as they should provide a different perspective on how to tackle Haskell implementation and optimization. http://repetae.net/computer/jhc/ I hope that helps, Jason ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Push the envelope. Watch it bend. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Code generation and optimisation for compiling Haskell
On 11/01/2012 15:20, Thomas Schilling wrote: Based on your stated background, the best start would be the (longer) paper on the Spineless Tagless G-machine [1]. Thanks for the tips. I haven't read much yet, but considering [1], I guess I shouldn't have dismissed SPJs early 90's stuff so quickly. Should be interesting. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Code generation and optimisation for compiling Haskell
On Tue, Jan 10, 2012 at 9:25 AM, Steve Horne sh006d3...@blueyonder.co.uk wrote: Also, what papers should I read? Am I on the right lines with the ones I've mentioned above? Thomas Schilling gave you a good response with papers so I will give you a different perspective on where to look. Most of the Haskell implementations were written by academics studying languages and compilers. This is good but it also implies that the implementors are likely to share biases and assumptions. I know of one Haskell compiler in particular that was written by someone who did not know Haskell when starting the project. The compiler was developed to be different than GHC. That person was John Meacham. He created JHC, a work in progress, so you might want to study his compiler and implementation notes as they should provide a different perspective on how to tackle Haskell implementation and optimization. http://repetae.net/computer/jhc/ I hope that helps, Jason ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Code generation and optimisation for compiling Haskell
On 1/12/12 8:50 PM, Jason Dagit wrote: On Tue, Jan 10, 2012 at 9:25 AM, Steve Horne sh006d3...@blueyonder.co.uk wrote: Also, what papers should I read? Am I on the right lines with the ones I've mentioned above? Thomas Schilling gave you a good response with papers so I will give you a different perspective on where to look. Most of the Haskell implementations were written by academics studying languages and compilers. This is good but it also implies that the implementors are likely to share biases and assumptions. I know of one Haskell compiler in particular that was written by someone who did not know Haskell when starting the project. The compiler was developed to be different than GHC. That person was John Meacham. He created JHC, a work in progress, so you might want to study his compiler and implementation notes as they should provide a different perspective on how to tackle Haskell implementation and optimization. http://repetae.net/computer/jhc/ JHC is also notable as a point of contrast because GHC strives to have a uniform representation in order to simplify adding high-level optimizations, whereas JHC is especially focused on the low-level optimizations obtainable by using non-uniform representations. More and more of these representational issues have been creeping into GHC over the years, so you should definitely take a look at JHC to get a different perspective on the space of possibilities than just those illuminated by the trajectory of GHC. On the other end of things, if your heart lies in the compiler itself rather than the generated code per se, you should definitely take a look at UHC. We often talk about Haskell as if it were a language, when in fact it is a family of related languages with subtly different features and properties. One of the principal goals of EHC/UHC is to design a compiler as a series of small passes in order to better disentangle the issues surrounding trying to compile an entire family of languages. They also have some novel code for dealing with the parsing end of the compiler, which is worth exploring separately from the overall design. -- Live well, ~wren ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Code generation and optimisation for compiling Haskell
Based on your stated background, the best start would be the (longer) paper on the Spineless Tagless G-machine [1]. It describes how graph reduction is actually implemented efficiently. Since then there have been two major changes to this basic implementation: Use of eval/apply (a different calling convention) [2] and constructor tagging [3] (which drastically reduces the number of indirect branches from the original STG approach). In addition to this fairly low-level stuff, there are very powerful optimisations performed at a higher level. For a taste see stream fusion [4]. If you're done with these, feel free to ask for more. :) [1]: http://research.microsoft.com/apps/pubs/default.aspx?id=67083 [2]: http://research.microsoft.com/en-us/um/people/simonpj/papers/eval-apply/ [3]: http://research.microsoft.com/en-us/um/people/simonpj/papers/ptr-tag/index.htm [4]: http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.104.7401 On 10 January 2012 17:25, Steve Horne sh006d3...@blueyonder.co.uk wrote: Although I'm far from being an expert Haskell programmer, I think I'm ready to look into some of the details of how it's compiled. I've a copy of Modern Compiler Design (Grune, Bal, Jacobs and Langendoen) - I first learned a lot of lexical and parsing stuff from it quite a few years ago. Today, I started looking through the functional languages section - I've read it before, but never absorbed much of it. Graph reduction, lambda lifing, etc - it seems pretty simple. Far too simple. It's hard to believe that decent performance is possible if all the work is done by a run-time graph reduction engine. Simon Peyton Jones has written a couple of books on implementing functional languages which are available for free download. At a glance, they seem to covers similar topics in much more detail. However, they're from 1987 and 1992. Considering SPJs period of despair when he couldn't get practical performance for monadic I/O, these seem very dated. Some time ago, I made a note to look up the book Functional Programming and Parallel Graph Rewriting (I forget why) but again that's from the early 90's. I've also got a note to look up Urban Boquists thesis. SPJ also has some papers on compilation - http://research.microsoft.com/en-us/um/people/simonpj/papers/papers.html#compiler - and the papers on optimisation by program transformation have caught my eye. Are there any current text-books that describe the techniques used by compilers like GHC to generate efficient code from functional languages? It's OK to assume some knowledge of basic compiler theory - the important stuff is code generation and optimisation techniques for lazy functional languages in particular. Also, what papers should I read? Am I on the right lines with the ones I've mentioned above? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Push the envelope. Watch it bend. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] code generation
Sorry for referring to a post, a bit ago. http://www-users.cs.york.ac.uk/~ndm/derive/ (Deriving Generic Functions by Example). Thanks for the pointer, it was already on my to-read-pile :-) I think using Template Haskell for your work would fit very nicely, so is a good choice to learn :-) I already got used to TH a bit, but I am not sure if it is appropriate for my purpose, or at least not completely. I want to load Haskell code into my program at runtime in an abstract representation (as TH), modify it and then type-check it or coerce it into a value (or execute it). For me it looks like I need a combination of Hint and TH. However, Hint can only interpret strings and to get a string from a QExp I have to enter the IO Monad using runQ. So, wouldn't it deteriorate my performance to do it all in the IO? Is there another way? Thanks, Martin ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] code generation
I think using Template Haskell for your work would fit very nicely, so is a good choice to learn :-) I already got used to TH a bit, but I am not sure if it is appropriate for my purpose, or at least not completely. I want to load Haskell code into my program at runtime in an abstract representation (as TH), modify it and then type-check it or coerce it into a value (or execute it). For me it looks like I need a combination of Hint and TH. Perhaps. You might be able to use the GHC API to get some of what you want too. However, Hint can only interpret strings and to get a string from a QExp I have to enter the IO Monad using runQ. So, wouldn't it deteriorate my performance to do it all in the IO? Is there another way? I wouldn't worry about performance just yet. In general, Haskell code in the IO Monad is just as efficient as normal code - the IO Monad gets almost entirely optimised away by GHC. Thanks Neil == Please access the attached hyperlink for an important electronic communications disclaimer: http://www.credit-suisse.com/legal/en/disclaimer_email_ib.html == ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] code generation
We try to learn functional programs from examples, but our system is not yet ported to Haskell, though we are working on it. However, we thought about using TH. Do you have any pointers to papers, etc. ? You'll find our project, system and papers here: http://www.cogsys.wiai.uni-bamberg.de/effalip/ I've only had a quick glance at the description however it looks like you should have a look at derive ( http://hackage.haskell.org/cgi-bin/hackage-scripts/package/derive, http://www-users.cs.york.ac.uk/~ndm/derive/ ) which I think tries to do a similar job. It has similarities, but there are many differences too. I'd certainly recommend taking a look around derive to get a feel for how to do Template Haskell stuff, and to look at the derivation by guess thing - see the manual, and the paper at: http://www-users.cs.york.ac.uk/~ndm/derive/ (Deriving Generic Functions by Example). I think using Template Haskell for your work would fit very nicely, so is a good choice to learn :-) To learn Template Haskell, I recommend you look at the Haddock documentation page: http://hackage.haskell.org/packages/archive/template-haskell/2.2.0.0/doc /html/Language-Haskell-TH.html And perhaps use Hoogle and a text editor to search around the definitions: http://haskell.org/hoogle/?hoogle=%2BLanguage.Haskell.TH+Exp Template Haskell is quite large, in that it defines a lot of data types, but none of it is particularly complex. Thanks Neil == Please access the attached hyperlink for an important electronic communications disclaimer: http://www.credit-suisse.com/legal/en/disclaimer_email_ib.html == ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] code generation
On Tue, Oct 21, 2008 at 03:04:27PM +0200, Martin Hofmann wrote: We try to learn functional programs from examples, but our system is not yet ported to Haskell, though we are working on it. However, we thought about using TH. Do you have any pointers to papers, etc. ? You'll find our project, system and papers here: http://www.cogsys.wiai.uni-bamberg.de/effalip/ I've only had a quick glance at the description however it looks like you should have a look at derive ( http://hackage.haskell.org/cgi-bin/hackage-scripts/package/derive, http://www-users.cs.york.ac.uk/~ndm/derive/ ) which I think tries to do a similar job. About everything else: try haskell.org, #haskell and there is even a TH mailinglist. You should know that you can make ghci print a lot of terms for you. Eg put the following into your ~/.ghci file :set -fth :m +Language.Haskell.TH :m +Language.Haskell.TH.Syntax then run ghci -package template-haskell and enter ghci: Prelude Language.Haskell.TH.Syntax Language.Haskell.TH runQ [| (*2) |] result: InfixE Nothing (VarE GHC.Num.*) (Just (LitE (IntegerL 2))) etc.. Also note that there is the module Language.Haskell.TH.Lib which does a lot of lifting for you automatically.. I hope this does help you getting more productive in addition to reading some of those existing texts. Marc Weber ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] code generation
zghost123: hello, im interested in using haskell to generate code and make little AI applications for fun.. is anyone already doing this sort of thing? it would be fun to collaborate with people on this. Lots of people are generating code from Haskell. Some useful libraries to look at: Language.C http://hackage.haskell.org/cgi-bin/hackage-scripts/package/language-c Language.X86ASM http://hackage.haskell.org/cgi-bin/hackage-scripts/package/harpy Language.JavaScript http://hackage.haskell.org/cgi-bin/hackage-scripts/package/HJavaScript http://hackage.haskell.org/cgi-bin/hackage-scripts/package/HJScript http://hackage.haskell.org/cgi-bin/hackage-scripts/package/WebBits Language.Parrot http://hackage.haskell.org/cgi-bin/hackage-scripts/package/HsParrot Language.Haskell http://hackage.haskell.org/cgi-bin/hackage-scripts/package/haskell-src ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] code generation
2008/10/20 z ghost [EMAIL PROTECTED]: hello, im interested in using haskell to generate code and make little AI applications for fun.. is anyone already doing this sort of thing? it would be fun to collaborate with people on this. I've been doing some work with Haskell code-generation in Haskell, but I've been using the haskell-src package to do it instead of Template Haskell, as I've been generating whole modules at a time. I have a bunch of convenience functions that I use over here: http://community.haskell.org/~aslatter/code/xhb/HaskellCombinators.hs It doesn't have a very consistent API, though. Let me know if you have any questions about it. -Antoine ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] code generation
Thanks for that! I don't know yet what would be the easiest way to automatically build up haskell code (Template haskell's Exps or the HsDecls in your link). Generating is only a part of what i need, though. I would like some feedback from GHC about the generated code (to see if the expressions typecheck, ..) I've been using the Hint package (which calls GHC) to typecheck strings http://hackage.haskell.org/cgi-bin/hackage-scripts/package/hint I've only managed to get it half working. Have you tried this and would this be the best approach? It would be great to get machine-readable error data back from GHC somehow (in stead of an error string). I don't if this is possible. --- On Tue, 10/21/08, Antoine Latter [EMAIL PROTECTED] wrote: From: Antoine Latter [EMAIL PROTECTED] Subject: Re: [Haskell-cafe] code generation To: [EMAIL PROTECTED] Cc: haskell-cafe@haskell.org Date: Tuesday, October 21, 2008, 3:50 PM 2008/10/20 z ghost [EMAIL PROTECTED]: hello, im interested in using haskell to generate code and make little AI applications for fun.. is anyone already doing this sort of thing? it would be fun to collaborate with people on this. I've been doing some work with Haskell code-generation in Haskell, but I've been using the haskell-src package to do it instead of Template Haskell, as I've been generating whole modules at a time. I have a bunch of convenience functions that I use over here: http://community.haskell.org/~aslatter/code/xhb/HaskellCombinators.hs It doesn't have a very consistent API, though. Let me know if you have any questions about it. -Antoine __ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] code generation
you can also write an interpreter in haskell that will typecheck using GADT's http://www.informatik.uni-bonn.de/~ralf/publications/With.pdf http://www.haskell.org/pipermail/haskell/2005-May/015815.html ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe