Re: [Haskell-cafe] Missing join and split
Josef Svenningsson writes:
> On Dec 28, 2007 11:40 PM, Mitar <[EMAIL PROTECTED]> wrote:
> > Would not it be interesting and useful (but not really efficient) to
> > have patterns something like:
> >
> > foo :: Eq a => a -> ...
> > foo (_{4}'b') = ...
> >
> > which would match a list with four elements ending with an element 'b'. Or:
> >
> > foo (_+';'_+';'_) = ...
> >
> > which would match a list with embedded two ';' elements. (Last _
> > matched the remaining of the list.)
> >
> I suggest you take at look at HaRP, Haskell Regular Patterns:
> http://www.cs.chalmers.se/~d00nibro/harp/
>
> It hasn't been updated for a while but it should still be useable.
>
Also of interest might be XHaskell
http://taichi.ddns.comp.nus.edu.sg/taichiwiki/XhaskellHomePage
which adds XDuce style regular expression pattern matching to Haskell.
Martin
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Basic question concerning data constructors
On Jan 1, 2008 3:43 PM, Yitzchak Gale <[EMAIL PROTECTED]> wrote: > The classical definition of "general recursive function" > refers to functions in Integer -> Integer to begin > with, so there can only be countably many values by > construction. Except that there are uncountably many (2^Aleph_0) functions in Integer -> Integer. That doesn't change the fact that there are countably many computable functions, as you guys have been saying. But I think you need to refer to the LC or Turing machine definition to get countability. Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Missing join and split
On Dec 28, 2007 11:40 PM, Mitar <[EMAIL PROTECTED]> wrote:
> Would not it be interesting and useful (but not really efficient) to
> have patterns something like:
>
> foo :: Eq a => a -> ...
> foo (_{4}'b') = ...
>
> which would match a list with four elements ending with an element 'b'. Or:
>
> foo (_+';'_+';'_) = ...
>
> which would match a list with embedded two ';' elements. (Last _
> matched the remaining of the list.)
>
I suggest you take at look at HaRP, Haskell Regular Patterns:
http://www.cs.chalmers.se/~d00nibro/harp/
It hasn't been updated for a while but it should still be useable.
Cheers,
Josef
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Compiler backend question
Peter Verswyvelen wrote: > Well, I don't know about the licensing, but according to > http://en.wikipedia.org/wiki/GNU_Compiler_Collection#Front_ends, a new > cleaner intermediate language was created in 2005 for GCC, which might be > more "general"? It's still very difficult to work with GCC from the perspective of an external tool. Its current IR is still targeted towards the languages it currently supports and the needs of its back end, so it omits a fair bit of information that third-party tools would find useful. > I just wanted to see if it is *possible* to feed just all the C code from > GHC into a C compiler, and then generate a single executable from that C > code (including the GHC runtime). It would be a fair bit of work. My recollection is that GHC "knows" that it is talking to GCC when you go through -fvia-c, so it uses some gcc extensions to handle things like register reservation. A few compilers support some of those gcc extensions, so you might have some level of success with those. The Intel and PathScale compilers do, for example, and LLVM's clang front end has some level of gcc compatibility already. In the case of the PathScale compiler (which I used to work on), when invoked in whole-program mode it emits files that look like regular .o files, but are in fact just the serialised IR for a compilation unit. It's also open source, so it would be easier to tinker with than the Intel compiler. > Actually this LTCG thingy was first supported by the > Intel compiler I believe. No, that kind of whole-program optimisation long predates its inclusion in the Intel compiler. The earliest I saw it in deployment was in MIPS compilers circa 1992, and I don't recall it being a new idea at the time. Anyway, the point about GCC being an unsuitable vehicle for this sort of thing remains. You'd do better looking at LLVM, for which I've lately been working on nice Haskell bindings: darcs get http://darcs.serpentine.com/llvm http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] Compiler backend question
Neil Mitchell wrote: > GCC is optimised for dealing with code that comes from C, and the back > end language is much like C. GCC is also not really set up to be used > by bolting different front ends on to different back ends - part of > this is a license issue - if the front and back ends were well split > and available separately you could write a commerical backend onto a > GPL front end. Well, I don't know about the licensing, but according to http://en.wikipedia.org/wiki/GNU_Compiler_Collection#Front_ends, a new cleaner intermediate language was created in 2005 for GCC, which might be more "general"? > You would get much better improvements on whole program at the Haskell > level. By the time you get to the generated C you have obfustcated all > the structure of the program, and are unlikely to benefit that much. Yes that would be great! Or even at JIT time ;-) But, given the time GHC takes to optimize a single module, I guess it would not really be practical to let those optimization take place on the full program? It would take ages no? I just wanted to see if it is *possible* to feed just all the C code from GHC into a C compiler, and then generate a single executable from that C code (including the GHC runtime). For example, for the XBOX DEVKIT, Microsoft shipped LTCG versions for all the core libraries, which gave a nice performance improvement for free (if I'm not mistaking, this gives 10% to 15% faster code). Actually this LTCG thingy was first supported by the Intel compiler I believe. Thanks, Peter ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Compiler backend question
Peter Verswyvelen wrote: ... I was wondering, why doesn't GHC use the GCC (or any other standard compiler) backend intermediate code? The backend of GCC generates highly optimized code no? Or is the intermediate code format of GCC (or other compilers) not suitable for Haskell? ... My guess is that there is scope for producing assembly code that out-performs GCC. I speak as someone who has no actual knowledge of how GCC works :) I have a theory that the back-end of most compilers, including GCC, are an accretion of many hand-coded hard-coded functions to perform very specific optimisations for particular instructions for particular processors. These have been developed over the years by relatively ad-hoc timings of the precise assembly code the individual who wrote the function wanted to improve. So what's wrong with this approach? When a new processor is introduced it needs a different set of optimisations, which take time to develop, which means the compiler is sub-optimal for a while for new processors. Also, the number of processors we would like the compiler optimised for is large if we're really trying to get the last few percent from every processor. Modern processors aren't simple things like the old 6502 or Z80 which had definite, easily predictable, timings. Think different cache sizes, multiple pipelines, branch prediction etc. "The microarchitecture of Intel and AMD CPU’s: An optimization guide for assembly programmers and compiler makers" here http://www.agner.org/optimize/ It seems unlikely therefore that the code generation for every modern processor variant will be hand-optimised to account for all the small details. Even in GCC, which no doubt has a huge amount of continuous effort applied to it by many clever people, they are never going to hand-code every complexity of every processor. Take a small example : integer multiplication. Looking at the table in the conclusion of the microarchitecture PDF we see that different x86 processors have different relative speed of adding and multiplying. Something like this Execution latencies, typical AMD64 P4EPM Core2 integer addition 1 1 1 1 integer multiplication 3 10 4 3 We can compute 4 * 371 faster on P4E by doing 371 + 371 + 371 + 371 but on Core2 and AMD64 we should do 4 * 371 and on PM it might depend on other factors, I don't know. Now supposing we allow powers of two by shifting as well as integer addition, can we immediately say the best way of multiplying two integers on all these processors? Maybe roughly, but do we always get the absolute fastest code? For example it will depend on the values of the integers. If we know one of them in advance as I've assumed above, or if we know they frequently have particular values we might handle them first etc. This is just one small optimisation out of many. And the optimisations might interact. So the inevitable conclusion is that the precise assembly code optimisations must not be hand-coded directly into the back-end of the compiler, as I expect they are currently in most compilers, but that they need to be expressed at a higher level "repeated addition is equivalent to multiplication" and adapted down to particular processors and situations based on extensive, genetic algorithm guided, timing runs. Anyway, that's my wild idea thrown in the pot. Might be a nice research paper in there for someone :) Richard. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Compiler backend question
Peter Verswyvelen <[EMAIL PROTECTED]> wrote: > Another question regarding the backend: a cool feature of the > Microsoft Visual C++ (MVC) compiler is its ability to perform "LTCG" > (link-time-code-generation), performing whole program optimization. > It something like this possible with Haskell / (or the GCC backend?). > Would it be possible to feed all the generated C code of the GHC > compiler into the MVC compiler, to generate one big MVC / LTCG > generated executable? It would be interesting to see how much the > whole program optimization approach (which can do analysis on the > program as if it was a single module) would improve performance... > jhc does that. Or rather, it doesn't compile Haskell modules separately but throws them together (presumably) in the first pass. Regarding C, it's actually only a high-level assembly language, with compiler optimisations only optimising heavily if you use those idioms... say inlining, loop-unrolling. If your compiler backend outputs something that is already close to some generalisation of different assembly languages, containing no superfluous code and compile-time evaluable expressions and looking generally like a mess of mov's and jmp's, nothing much more than optimisating register allocation and pipeline usage optimisation can be done, which are both highly processor-specific bastards, and likely to be hard to write better than . I figure it's being lazy in the right way(TM) -- (c) this sig last receiving data processing entity. Inspect headers for past copyright information. All rights reserved. Unauthorised copying, hiring, renting, public performance and/or broadcasting of this signature prohibited. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Basic question concerning data constructors
Andrew Bromage wrote: >> [*] Theoretical nit: It's not technically a "set". >> >> Consider the data type: >> >> data Foo = Foo (Foo -> Bool) >> >> This declaration states that there's a bijection between the elements of >> Foo and the elements of 2^Foo, which by Cantor's diagonal theorem cannot >> be true for any set. That's because we only allow computable functions, >> and Foo -> Bool is actually an exponential object in the category Hask. I wrote: > Data types consist only of computable elements. Since there > are only countably many computable functions, What I meant by that is that there are only countably many lambdas, and we can define a "computable value" as a lambda. The classical definition of "general recursive function" refers to functions in Integer -> Integer to begin with, so there can only be countably many values by construction. > every data type > has at most countably many elements. In particular, it is a set. > > The least fixed point under these restrictions is not a bijection > between Foo and 2^Foo. It is only a bijection between Foo and > the subset of computable 2^Foo. -Yitz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Basic question concerning data constructors
Andrew Bromage wrote: > [*] Theoretical nit: It's not technically a "set". > > Consider the data type: > > data Foo = Foo (Foo -> Bool) > > This declaration states that there's a bijection between the elements of > Foo and the elements of 2^Foo, which by Cantor's diagonal theorem cannot > be true for any set. That's because we only allow computable functions, > and Foo -> Bool is actually an exponential object in the category Hask. Data types consist only of computable elements. Since there are only countably many computable functions, every data type has at most countably many elements. In particular, it is a set. The least fixed point under these restrictions is not a bijection between Foo and 2^Foo. It is only a bijection between Foo and the subset of computable 2^Foo. -Yitz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Basic question concerning data constructors
On Dec 31, 2007 7:17 AM, <[EMAIL PROTECTED]> wrote: > This declaration states that there's a bijection between the elements of > Foo and the elements of 2^Foo, which by Cantor's diagonal theorem cannot > be true for any set. That's because we only allow computable functions, Nit the nit: Or (more commonly, I think) all continuous functions. > and Foo -> Bool is actually an exponential object in the category Hask. - Benja ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Compiler backend question
Hi > If I understand it correctly, the GHC compiler either directly generates > machinecode, or it uses C as an intermediate language. > > I also read somewhere that C is not the most efficient intermediate > representation for functional languages, and that one gets better > performance when generating native machine code. > > However, from the discussions in this list, I could conclude that the low > level machine code optimizer of GHC is far from state-of-the-art compared to > industry standard C/C++ compilers. These all seem fair comments, based on my understanding. One other thing to remember is that the GHC people know this, and much work has been done, and will continue to be done until the back end is up to the standard of the front end. > I was wondering, why doesn't GHC use the GCC (or any other standard > compiler) backend intermediate code? The backend of GCC generates highly > optimized code no? Or is the intermediate code format of GCC (or other > compilers) not suitable for Haskell? GCC is optimised for dealing with code that comes from C, and the back end language is much like C. GCC is also not really set up to be used by bolting different front ends on to different back ends - part of this is a license issue - if the front and back ends were well split and available separately you could write a commerical backend onto a GPL front end. > Another question regarding the backend: a cool feature of the Microsoft > Visual C++ (MVC) compiler is its ability to perform "LTCG" > (link-time-code-generation), performing whole program optimization. It > something like this possible with Haskell / (or the GCC backend?). Would it > be possible to feed all the generated C code of the GHC compiler into the > MVC compiler, to generate one big MVC / LTCG generated executable? It would > be interesting to see how much the whole program optimization approach > (which can do analysis on the program as if it was a single module) would > improve performance... You would get much better improvements on whole program at the Haskell level. By the time you get to the generated C you have obfustcated all the structure of the program, and are unlikely to benefit that much. Thanks Neil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Compiler backend question
If I understand it correctly, the GHC compiler either directly generates machinecode, or it uses C as an intermediate language. I also read somewhere that C is not the most efficient intermediate representation for functional languages, and that one gets better performance when generating native machine code. However, from the discussions in this list, I could conclude that the low level machine code optimizer of GHC is far from state-of-the-art compared to industry standard C/C++ compilers. I was wondering, why doesn't GHC use the GCC (or any other standard compiler) backend intermediate code? The backend of GCC generates highly optimized code no? Or is the intermediate code format of GCC (or other compilers) not suitable for Haskell? Another question regarding the backend: a cool feature of the Microsoft Visual C++ (MVC) compiler is its ability to perform "LTCG" (link-time-code-generation), performing whole program optimization. It something like this possible with Haskell / (or the GCC backend?). Would it be possible to feed all the generated C code of the GHC compiler into the MVC compiler, to generate one big MVC / LTCG generated executable? It would be interesting to see how much the whole program optimization approach (which can do analysis on the program as if it was a single module) would improve performance... Cheers, Peter ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
