Re: [Haskell-cafe] Parsec bug, or...?
Brandon S. Allbery KF8NH wrote: My fix would be to have myPrefixOf require the prefix be terminated in whatever way is appropriate (end of input, white space, operator?) instead of simply accepting as soon as it gets a prefix match regardless of what follows. Maybe you can use notFollowedBy for this. HTH, Martijn. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] MTL vs Transformers?
Erik de Castro Lopo wrote: However after reading the hackage descriptions of both Transformers and MTL, it seems that they share a very similar heritage. I therefore hacked the iteratee.cabal file and replaced the build-depends on transformers with one on mtl and the package built quite happily. I'll play with it a bit to see if its working correctly. I think the standard solutions are * use Cabal for your project and/or * use the PackageImports extension. HTH, Martijn. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] Type-level naturals multiplication
| Is there any way to define type-level multiplication without requiring | undecidable instances? | | No, not at the moment. The reasons are explained in the paper Type | Checking with Open Type Functions (ICFP'08): | |http://www.cse.unsw.edu.au/~chak/papers/tc-tfs.pdf | | We want to eventually add closed *type families* to the system (ie, | families where you can't add new instances in other modules). For | such closed families, we should be able to admit more complex | instances without requiring undecidable instances. It's also worth noting that while undecidable instances sound scary, but all it means is that the type checker can't prove that type inference will terminate. We accept this lack-of-guarantee for the programs we *run*, and type inference can (worst case) take exponential time which is not so different from failing to terminate; so risking non-termination in type inference is arguably not so bad. Simon ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] MTL vs Transformers?
On Tuesday 13 October 2009 02:46:29 Erik de Castro Lopo wrote: Hi all, I've just received the following error message: headers.hs:6:7: Could not find module `Control.Monad.Identity': it was found in multiple packages: transformers-0.1.4.0 mtl-1.1.0.2 I'm trying to use the Iteratee module which depends on Transformers but I use MTL in other stuff. Whats the preferred solution here? Erik Hi, alternative to ghc-pkg: {-# LANGUAGE -XPackageImports #-} module Blub where import mtl Control.Monad.State -- Daniel ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: MTL vs Transformers?
From: Erik de Castro Lopo mle...@mega-nerd.com Well Iteratee built with MTL passes all the tests that shipped with it so I suppose it must be correct. Unfortunately the iteratee tests aren't exhaustive, but if it builds with MTL it should work. I'm more surprised that it built just by changing the .cabal file; I would expect you'd have to hack up the imports in the source code. John ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] What *is* a DSL?
On 2009-10-07 17:29, Robert Atkey wrote: A deep embedding of a parsing DSL (really a context-sensitive grammar DSL) would look something like the following. I think I saw something like this in the Agda2 code somewhere, but I stumbled across it when I was trying to work out what free applicative functors were. The Agda code you saw may have been due to Ulf Norell and me. There is a note about it on my web page: http://www.cs.nott.ac.uk/~nad/publications/danielsson-norell-parser-combinators.html Note that these grammars are strictly less powerful than the ones that can be expressed using Parsec because we only have a fixed range of possibilities for each rule, rather than allowing previously parsed input to determine what the parser will accept in the future. Previously parsed input /can/ determine what the parser will accept in the future (as pointed out by Peter Ljunglöf in his licentiate thesis). Consider the following grammar for the context-sensitive language {aⁿbⁿcⁿ| n ∈ ℕ}: data NT a where Start ::NT () -- Start ∷= aⁿbⁿcⁿ ABC :: Nat - NT () -- ABC n ∷= aˡbⁿ⁺ˡcⁿ⁺ˡ X :: Char - Nat - NT () -- X x n ∷= xⁿ g :: Grammar NT g Start = nt (ABC 0) g (ABC n) = char 'a' * nt (ABC (succ n)) | nt (X 'b' n) * nt (X 'c' n) g (X c n) | n == 0= pure () | otherwise = char c * nt (X c (pred n)) And a general definition for parsing single-digit numbers. This works for any set of non-terminals, so it is a reusable component that works for any grammar: Things become more complicated if the reusable component is defined using non-terminals which take rules (defined using an arbitrary non-terminal type) as arguments. Exercise: Define a reusable variant of the Kleene star, without using grammars of infinite depth. -- /NAD This message has been checked for viruses but the contents of an attachment may still contain software viruses, which could damage your computer system: you are advised to perform your own checks. Email communications with the University of Nottingham may be monitored as permitted by UK legislation. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] Re: Libraries for Commercial Users
There is no difficulty in principle with Haskell on JVM. There are, however, some obstacles in practice, as this page describes: http://haskell.org/haskellwiki/GHC:FAQ#Why_isn.27t_GHC_available_for_.NET_or_on_the_JVM.3F The way stands open for someone with design taste, knowledge of the JVM, and sustained willingness to roll up sleeves, to make a significant contribution. Simon | -Original Message- | From: haskell-cafe-boun...@haskell.org [mailto:haskell-cafe-boun...@haskell.org] On | Behalf Of wren ng thornton | Sent: 12 October 2009 01:54 | To: Haskell Cafe | Subject: Re: [Haskell-cafe] Re: Libraries for Commercial Users | | Patrick LeBoutillier wrote: | Don, | | Having painless Haskell - Java interoperability would be great. I'm | curious though: could it really be so simple as a one-line ``import | foreign jvm'' directive? I imagine the purity mismatch between | Haskell and Java would be very troublesome. | No more so than C, surely. We're used to stateful APIs. They're a pain. | | | With this hypothetical ``import foreign jvm'' mechanism, what would | the be type of imported Java stuff? Would it all be done in IO? | | The more I think about it, the trickier it seems. Beside the purity | mismatch of Haskell and Java, there is an OO/functional mismatch. | That's more of an issue. But the prior work has been done. | | Do you have any references to this work? | | | It was a major research topic about a decade ago, though the projects | have died since. And the topic comes up about every 4 months on the | Cafe, so I'd recommend sifting through the archives. I know last time it | came up (or the time before?) I gave a rather extensive list of | projects. And the wiki[1] still lists a few of them. | | The last time this discussion came up people got involved enough to | revive LambdaVM[2], which was one of the more mature options back in the | day. If you're interested in the topic, I suggest getting in touch with | the author and helping out. | | On the topic of automatically embedding OO-style languages into Haskell, | you should also check out hprotoc[3]. It's a package for Google's | protocol buffers, which are ostensibly language agnostic but actually | assume a (weakly) OO language. The hprotoc library will create a family | of virtual modules based on the protocol spec and makes a pretty nice | interface out of them. | | | [1] | http://www.haskell.org/haskellwiki/Applications_and_libraries/Interfacing_other_lang | uages | [2] http://wiki.brianweb.net/LambdaVM/LambdaVM | [3] http://hackage.haskell.org/package/hprotoc | | -- | Live well, | ~wren | ___ | 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] Time Typeable Instances
Hugo Gomes wrote: The Glorious Glasgow Haskell Compilation System, version 6.10.4 with old-time-1.0.0.2 and time-1.1.2.4 This is a standard haskell platform on a windows xp. Cabal install didn't work complaining about missing instances of typeable for posix time and other datatypes, yet, after removing the macros (thus, adding those instances), hdbc and convertible compiled and installed fine. Removing the macros might be a bit overkill, probably finetuning them so that they add only the necessary instances for typeable in ghc 610 might be a better solution. I'm going to CC haskell-cafe on this because I am confused. Hugo, can you confirm what version of convertible you have? Back on May 21, I started a thread [1] on haskell-cafe complaining that GHC 6.10.3 included a newer time that included instances of Typeable for NominalDiffTime and UTCTime. This broke my code, which had manually defined instances for these types, as they were needed. Things got complicated, as only time's minor version number got incremented (x.x.x.Y) [2]. Cabal can't test against that version number. I wanted my code to work with old and new versions of GHC. Since testing against the version of time was impossible, I did the next best thing: tested against the version of GHC. #if __GLASGOW_HASKELL__ = 610 -- instances added in GHC 6.10.3 #else instance Typeable NominalDiffTime where typeOf _ = mkTypeName NominalDiffTime instance Typeable UTCTime where typeOf _ = mkTypeName UTCTime #endif Also, in the .cabal, there is a build-depends on time=1.1.2.4. Now, that would break for GHC 6.10.1 and 6.10.2 users, but will work for 6.10.3 and above, or 6.8 and below. Or so I thought. Now I'm getting complaints from people using 6.10.4 saying that there are now missing instances of Typeable with time 1.1.2.4. 1) Did the Typeable instances get dropped again from time? 2) What exactly should I do so this library compiles on GHC 6.8 and 6.10.x? I'm looking at the darcs repo for time and don't see the instances ever getting dropped. [1] http://osdir.com/ml/haskell-cafe@haskell.org/2009-05/msg00982.html [2] http://osdir.com/ml/haskell-cafe@haskell.org/2009-05/msg00985.html later addendum so it appears that what's happening here is that GHC 6.10.3 extralibs included time 1.1.3, but then haskell-platform standardized on 1.1.2.4. This is pretty annoying -- that haskell-platform would standardize on a version older than what shipped with a GHC release -- but I guess I can work around it by restricting my build-dep to be time 1.1.3 and re-adding the instances. Does this sound right? On Tue, Oct 13, 2009 at 2:51 AM, John Goerzen jgoer...@complete.org mailto:jgoer...@complete.org wrote: Hugo Gomes wrote: Hi, convertible and hdbc packages fail to compile in my standard instalation of the haskell platform. I think this has to do with those if ghc = 610 macros on the typeable instances for some datatypes. I removed them and now they work fine... What version of GHC and time do you have? -- John ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parsec bug, or...?
On 10/12/09, Martijn van Steenbergen mart...@van.steenbergen.nl wrote: Brandon S. Allbery KF8NH wrote: My fix would be to have myPrefixOf require the prefix be terminated in whatever way is appropriate (end of input, white space, operator?) instead of simply accepting as soon as it gets a prefix match regardless of what follows. Maybe you can use notFollowedBy for this. HTH, Martijn. Yes, I've looked at that and am thinking about it. I'm not quite certain it's needed in my real program... I seem to have convinced myself that if I actually specify a proper set of unique prefixes, ie, set the required lengths for both frito and fromage to 3 in the test program, I won't get into this situation. Assuming I haven't committed another brain-fart there, that would be sufficient; presumably, in a real program one would want to actually specify the unique prefix, rather than a non-unique pre-prefix. It seems to work fine in my real program, anyway. Uwe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Type-level naturals multiplication
On Tue, Oct 13, 2009 at 3:37 AM, Simon Peyton-Jones simo...@microsoft.com wrote: [...] It's also worth noting that while undecidable instances sound scary, but all it means is that the type checker can't prove that type inference will terminate. We accept this lack-of-guarantee for the programs we *run*, and type inference can (worst case) take exponential time which is not so different from failing to terminate; so risking non-termination in type inference is arguably not so bad. Simon Indeed! On a related note, template instantiation in C++ is undecidable. See ``C++ Templates are Turing Complete'' by Todd Veldhuizen: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.14.3670. And similarly, heavy use of templates in C++ can be *extremely* compute-intensive. Sincerely, Brad ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Exponential complexity of type checking (Was: Type-level naturals multiplication)
On Tue, Oct 13, 2009 at 3:37 AM, Simon Peyton-Jones simo...@microsoft.com wrote: | Is there any way to define type-level multiplication without requiring | undecidable instances? | | No, not at the moment. The reasons are explained in the paper Type | Checking with Open Type Functions (ICFP'08): | | http://www.cse.unsw.edu.au/~chak/papers/tc-tfs.pdf | | We want to eventually add closed *type families* to the system (ie, | families where you can't add new instances in other modules). For | such closed families, we should be able to admit more complex | instances without requiring undecidable instances. It's also worth noting that while undecidable instances sound scary, but all it means is that the type checker can't prove that type inference will terminate. We accept this lack-of-guarantee for the programs we *run*, and type inference can (worst case) take exponential time which is not so different from failing to terminate; so risking non-termination in type inference is arguably not so bad. Simon I have written code that makes heavy use of multi-parameter type classes in the ``finally tagless'' tradition, which takes several seconds and many megabytes of memory for GHCI to infer its type. However, that example is rather complicated, and I am not sure its type inference complexity is exponential---it is at least very bad. Are there any simple, well-known examples where Haskell type inference has exponential complexity? Or Hindley-Milner type inference, for that matter? (Haskell 98 is not quite Hindley-Milner?) Sincerely, Brad Larsen ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Exponential complexity of type checking (Was: Type-level naturals multiplication)
Yes, there are simple H-M examples that are exponential. x0 = undefined x1 = (x1,x1) x2 = (x2,x2) x3 = (x3,x3) ... xn will have a type with 2^n type variables so it has size 2^n. -- Lennart On Tue, Oct 13, 2009 at 6:04 PM, Brad Larsen brad.lar...@gmail.com wrote: On Tue, Oct 13, 2009 at 3:37 AM, Simon Peyton-Jones simo...@microsoft.com wrote: | Is there any way to define type-level multiplication without requiring | undecidable instances? | | No, not at the moment. The reasons are explained in the paper Type | Checking with Open Type Functions (ICFP'08): | | http://www.cse.unsw.edu.au/~chak/papers/tc-tfs.pdf | | We want to eventually add closed *type families* to the system (ie, | families where you can't add new instances in other modules). For | such closed families, we should be able to admit more complex | instances without requiring undecidable instances. It's also worth noting that while undecidable instances sound scary, but all it means is that the type checker can't prove that type inference will terminate. We accept this lack-of-guarantee for the programs we *run*, and type inference can (worst case) take exponential time which is not so different from failing to terminate; so risking non-termination in type inference is arguably not so bad. Simon I have written code that makes heavy use of multi-parameter type classes in the ``finally tagless'' tradition, which takes several seconds and many megabytes of memory for GHCI to infer its type. However, that example is rather complicated, and I am not sure its type inference complexity is exponential---it is at least very bad. Are there any simple, well-known examples where Haskell type inference has exponential complexity? Or Hindley-Milner type inference, for that matter? (Haskell 98 is not quite Hindley-Milner?) Sincerely, Brad Larsen ___ 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] Exponential complexity of type checking (Was: Type-level naturals multiplication)
2009/10/13 Lennart Augustsson lenn...@augustsson.net: Yes, there are simple H-M examples that are exponential. x0 = undefined x1 = (x1,x1) x2 = (x2,x2) x3 = (x3,x3) ... xn will have a type with 2^n type variables so it has size 2^n. Reformulated: let dup x = (x,x) :t dup . dup . dup . dup ... type will be 2^(number of dup's). I experimented and found that GHC can stand pretty long line of dup's. More than 20, at least. One part of our program took too much time to typecheck some time ago. 3 and half minutes for ~900 lines module. Most of operations was inside heavily parametrized monad (5 parameters, each is a Peano number). Then my colleague moved parameters into associated types of relevant type class and now it typechecks in ten seconds. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Exponential complexity of type checking (Was: Type-level naturals multiplication)
On Tue, Oct 13, 2009 at 12:32 PM, Serguey Zefirov sergu...@gmail.com wrote: 2009/10/13 Lennart Augustsson lenn...@augustsson.net: Yes, there are simple H-M examples that are exponential. x0 = undefined x1 = (x1,x1) x2 = (x2,x2) x3 = (x3,x3) ... xn will have a type with 2^n type variables so it has size 2^n. Reformulated: let dup x = (x,x) :t dup . dup . dup . dup ... type will be 2^(number of dup's). I experimented and found that GHC can stand pretty long line of dup's. More than 20, at least. One part of our program took too much time to typecheck some time ago. 3 and half minutes for ~900 lines module. Most of operations was inside heavily parametrized monad (5 parameters, each is a Peano number). Then my colleague moved parameters into associated types of relevant type class and now it typechecks in ten seconds. Good example! I have a feeling that the `dup' example is a bit contrived, not something that one would be likely to find in the wild. Heavily parameterized type classes, on the other hand, are more common in real code. Hence, that is more likely where someone would run into really awful type inference performance without expecting it. Brad ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: [Haskell-beginners] using quickcheck for blackbox testing for 3rd party apps.
Am Dienstag 13 Oktober 2009 18:04:52 schrieb Brent Yorgey: Brent * Some smart-alecks might pipe up with something about unsafePerformIO here. But that's not a cure, it's more like performing an emergency tracheotomy with a ballpoint pen. Quote of the month! ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Reverse dependencies in Hackage
A few weeks ago I wrote a patch that adds reverse dependencies to hackage [1]. I have know hosted a small test hackage which demonstrates this feature. It can be found here: http://bifunctor.homelinux.net/~roel/hackage Browse to your favorite packages and find out how much other packages depend on them! I also noticed that work is underway to implement a new hackage-server [2] based on happstack. If people find this feature useful I could also write a patch against the hackage-server code base [3]. Regards, Roel van Dijk [1] - http://hackage.haskell.org/trac/hackage/ticket/576 [2] - http://sparky.haskell.org:8080/ [3] - http://code.haskell.org/hackage-server/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ** for nested applicative functors?
Hi Kim-Ee, This pattern shows up in Applicative programming with effects in showing that the composition of applicatives is applicative: (*) = liftA2 (*), and pure = pure.pure . (Really, you have to manage newtype wrappers as well. See the TypeCompose library.) - Conal On Mon, Oct 12, 2009 at 9:52 AM, Kim-Ee Yeoh a.biurvo...@asuhan.com wrote: That's it: liftA2 (*), so obvious in hindsight. Mustn't ... code ... when ... drained Thanks to Jeremy and Josef. Jeremy Shaw-3 wrote: This looks like what is described in Section 4 to me: http://www.haskell.org/haskellwiki/Applicative_functor#Applicative_transfomers - jeremy On Oct 12, 2009, at 11:22 AM, Kim-Ee Yeoh wrote: ** :: (Applicative m, Applicative n) = m (n (a-b)) - m (n a) - m (n b) -- View this message in context: http://www.nabble.com/%3C**%3E-for-nested-applicative-functors--tp25858792p25859274.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.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] GHC core packages: same core?
Hi Dimitry, ghc-core is a pretty-printer for GHC's internal Core language (you can get a non-pretty-printed version simply by compiling with (IIRC) -dverbose-core2core). This is what we actually optimize and generate code from, and the formatting of this output might change at any time. This is probably what you should be looking at, as a human trying to understand how your programs are being complied. extcore is a library that parses external Core, which is an alternative format intended to be stable and hence a suitable target for consumption by non-GHC tooling. You can have GHC output external core instead of machine code / C. I don't believe this is widely used yet. Cheers, Max 2009/10/12 Dimitry Golubovsky golubov...@gmail.com: Hi, Just curious whether package http://hackage.haskell.org/package/ghc-core and http://hackage.haskell.org/package/extcore operate on the same flavor of GHC Core? There seem to be external [1] and internal [2] flavors of GHC Core. [1] http://www.haskell.org/ghc/docs/6.10.2/html/ext-core/core.pdf [2] http://hackage.haskell.org/trac/ghc/wiki/Commentary/Compiler/CoreSynType Thanks. -- Dimitry Golubovsky Anywhere on the Web ___ 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] a library for control of terminal driver modes?
Yes, ansi-terminal supports this. Try: setSGR [SetBlinkSpeed NoBlink] (http://hackage.haskell.org/packages/archive/ansi-terminal/0.5.0/doc/html/System-Console-ANSI.html) Cheers, Max 2009/10/12 Iain Barnett iainsp...@gmail.com: On 11 Oct 2009, at 15:30, Andrew Coppin wrote: Iain Barnett wrote: I'm looking for a library like Perl's Term-Readkey, so that I can turn on and off the echo for secure password input from a terminal. Anyone know which library I need to use for this? The package ansi-terminal allows you to do various things to the terminal; I think it might include turning local echo on/off. Alternatively, there was an announcement recently about a text-mode UI package, which might do what you want. (I don't recall the name...) Thanks Iain ___ 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] a library for control of terminal driver modes?
Err, I managed to completely misread your email. Sorry. Unfortunately, ansi-terminal does NOT support disabling the echo and I don't plan to support it. However, given that I already provide non-ANSI features from it, patches would be happily accepted :-) Cheers, Max 2009/10/13 Max Bolingbroke batterseapo...@hotmail.com: Yes, ansi-terminal supports this. Try: setSGR [SetBlinkSpeed NoBlink] (http://hackage.haskell.org/packages/archive/ansi-terminal/0.5.0/doc/html/System-Console-ANSI.html) Cheers, Max 2009/10/12 Iain Barnett iainsp...@gmail.com: On 11 Oct 2009, at 15:30, Andrew Coppin wrote: Iain Barnett wrote: I'm looking for a library like Perl's Term-Readkey, so that I can turn on and off the echo for secure password input from a terminal. Anyone know which library I need to use for this? The package ansi-terminal allows you to do various things to the terminal; I think it might include turning local echo on/off. Alternatively, there was an announcement recently about a text-mode UI package, which might do what you want. (I don't recall the name...) Thanks Iain ___ 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] GHC core packages: same core?
Max, Thanks for the explanation. So, the extcore library is expected to match the spec in http://www.haskell.org/ghc/docs/6.10.4/html/ext-core/core.pdf and the core itself can be produced with -fext-core, correct? I think it might be interesting for people working on alternative backends (inlcuding myself). On Tue, Oct 13, 2009 at 4:53 PM, Max Bolingbroke batterseapo...@hotmail.com wrote: [skip] extcore is a library that parses external Core, which is an alternative format intended to be stable and hence a suitable target for consumption by non-GHC tooling. You can have GHC output external core instead of machine code / C. I don't believe this is widely used yet. -- Dimitry Golubovsky Anywhere on the Web ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Reverse dependencies in Hackage
On Tue, 2009-10-13 at 21:30 +0200, Roel van Dijk wrote: I also noticed that work is underway to implement a new hackage-server [2] based on happstack. If people find this feature useful I could also write a patch against the hackage-server code base [3]. That would be much appreciated. Duncan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] why does iterateNTimes (10^6) (ap . liftM (:) . return $ 0) (return []) produce output in the IO monad, but stack overflow in the maybe monad?
Can someone explain why the one stack overflows and the other one doesn't? iterateNTimes i f x = foldr (.) id (replicate i f) $ x tntIO :: IO Int -- same as replicateM (10^6) $ return 0 , and same as sequence . replicate (10^6) $ return 0 tntIO = iterateNTimes (10^6) (ap . liftM (:) . return $ ) (return []) -- produces output tntMb :: Maybe Int -- overflows tntMb = iterateNTimes (10^6) (ap . liftM (:) . return $ ) (return []) -- stack overflow ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Fwd: [Haskell-cafe] Haskell for Physicists
Don Stewart d...@galois.com writes: Hey all, Following up on this, I'm presenting a position paper tomorrow on the use of EDSLs to improve productivity and lower cost when developing code for new high performance architectures (like GPUs). http://www.galois.com/blog/2009/10/13/domain-specific-languages-for-domain-specific-problems/ It advocates for Haskell + EDSLs, much as we have been discussing in this thread. I'm very interested in EDSL in high performance architectures. Can you give me some idea what the performance might be using code written in Haskell+EDSL compared to C/C++? I think, in high performance computing, the efficiency in the resulting binary code largely depends on the problem domain. Can haskell help a lot in optimizing the EDSL to machine binary? And what would be the efficiency in terms of space and time? Xiao-Yong -- c/*__o/* \ * (__ */\ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Exponential complexity of type checking (Was: Type-level naturals multiplication)
On Tuesday 13 October 2009 1:06:41 pm Brad Larsen wrote: Good example! I have a feeling that the `dup' example is a bit contrived, not something that one would be likely to find in the wild. This is, after all, why HM is useful. In general, there are programs that take exponential time/space to type check, but those programs don't come up much in real code. Also, you can do better than 2^n: f0 x = (x,x) f1 = f0 . f0 f2 = f1 . f1 f3 = f2 . f2 ... Here, if fN results in a nested tuple of size M, then f(N+1) results in a tuple of size M^2, since we replace all the variables with a copy of the tuple. So we have 2, 4, 16, 256, ... 2^(2^N) Turning f0 into an M-tuple gets you M^(2^N), I believe, and composing K times at each step would get you M^(K^N). But anyhow, we have not merely an exponential, but a double exponential. :) f4 takes a noticeable amount of time to check here (in ghci), and f5 makes my machine start swapping. Of course, one isn't likely to write code like this, either. -- Dan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Type-level naturals multiplication
On Tue, Oct 13, 2009 at 9:37 AM, Simon Peyton-Jones simo...@microsoft.comwrote: | Is there any way to define type-level multiplication without requiring | undecidable instances? | | No, not at the moment. The reasons are explained in the paper Type | Checking with Open Type Functions (ICFP'08): | | http://www.cse.unsw.edu.au/~chak/papers/tc-tfs.pdfhttp://www.cse.unsw.edu.au/%7Echak/papers/tc-tfs.pdf | | We want to eventually add closed *type families* to the system (ie, | families where you can't add new instances in other modules). For | such closed families, we should be able to admit more complex | instances without requiring undecidable instances. It's also worth noting that while undecidable instances sound scary, but all it means is that the type checker can't prove that type inference will terminate. We accept this lack-of-guarantee for the programs we *run*, and type inference can (worst case) take exponential time which is not so different from failing to terminate; so risking non-termination in type inference is arguably not so bad. Some further details to shed some light on this topic. Undecidable instances means that there exists a program for which there's an infinite reduction sequence. By undecidable I refer to instances violating the conditions in the icfp'08 and in the earlier jfp paper Understanding Functional Dependencies via Constraint Handling Rules. Consider the classic example Add (Succ x) x ~ x -- Succ (Add x x) ~ x substitute for x and you'll get another redex of the form Add (Succ ..) ... and therefore the reduction won't terminate To fix this problem, i.e. preventing the type checker to non-terminate, we could either (a) spot the loop in Add (Succ x) x ~ x and reject this unsatisfiable constraint and thus the program (b) simply stop after n steps The ad-hoc approach (b) restores termination but risks incompleteness. Approach (a) is non-trivial to get right, there are more complicated loopy programs where spotting the loops gets really tricky. The bottom line is this: Running the type checker on undecidable instances means that there are programs for which - the type checker won't terminate, or - wrongly rejects the program (incompleteness) So, the situation is slightly more scary, BUT programs exhibiting the above behavior are (in my experience) rare/contrived. -Martin ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: why does iterateNTimes (10^6) (ap . liftM (:) . return $ 0) (return []) produce output in the IO monad, but stack overflow in the maybe monad?
correction, should be: iterateNTimes i f x = foldr (.) id (replicate i f) $ x tntIO :: IO Int -- same as replicateM (10^6) $ return 0 tntIO = return . head = (iterateNTimes (10^6) (ap . liftM (:) . return $ 0) (return [])) -- produces output tntMb :: Maybe Int -- overflows tntMb = return . head = (iterateNTimes (10^6) (ap . liftM (:) . return $ 0) (return [])) -- stack overflow which now compiles. 2009/10/13 Thomas Hartman tphya...@gmail.com: Can someone explain why the one stack overflows and the other one doesn't? iterateNTimes i f x = foldr (.) id (replicate i f) $ x tntIO :: IO Int -- same as replicateM (10^6) $ return 0 , and same as sequence . replicate (10^6) $ return 0 tntIO = iterateNTimes (10^6) (ap . liftM (:) . return $ ) (return []) -- produces output tntMb :: Maybe Int -- overflows tntMb = iterateNTimes (10^6) (ap . liftM (:) . return $ ) (return []) -- stack overflow ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Fwd: [Haskell-cafe] Haskell for Physicists
Of all the projects that are in the HackageDB, how many, or what % do you say developed an EDSL? daryoush On Tue, Oct 13, 2009 at 3:06 PM, Xiao-Yong Jin xj2...@columbia.edu wrote: Don Stewart d...@galois.com writes: Hey all, Following up on this, I'm presenting a position paper tomorrow on the use of EDSLs to improve productivity and lower cost when developing code for new high performance architectures (like GPUs). http://www.galois.com/blog/2009/10/13/domain-specific-languages-for-domain-specific-problems/ It advocates for Haskell + EDSLs, much as we have been discussing in this thread. I'm very interested in EDSL in high performance architectures. Can you give me some idea what the performance might be using code written in Haskell+EDSL compared to C/C++? I think, in high performance computing, the efficiency in the resulting binary code largely depends on the problem domain. Can haskell help a lot in optimizing the EDSL to machine binary? And what would be the efficiency in terms of space and time? Xiao-Yong -- c/*__o/* \ * (__ */\ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Daryoush Weblog: http://perlustration.blogspot.com/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] (no subject)
Martin Sulzmann wrote: Undecidable instances means that there exists a program for which there's an infinite reduction sequence. I believe this may be too strong of a statement. There exists patently terminating type families that still require undecidable instances in GHC. Here is an example: {-# LANGUAGE TypeFamilies #-} type family I x :: * type instance I x = x type family B x :: * type instance B x = I x GHC 6.8.3 complaints: Application is no smaller than the instance head in the type family application: I x (Use -fallow-undecidable-instances to permit this) In the type synonym instance declaration for `B' But there cannot possibly be any diverging reduction sequence here, can it? The type family I is the identity, and the type family B is its alias. There is no recursion. The fact that type families are open is not relevant here: our type families I and B are effectively closed, because one cannot define any more instance for I and B (or risk overlap, which is rightfully not supported for type families). The reason GHC complains is because it checks termination instance-by-instance. To see the termination in the above program, one should consider instances I and B together. Then we will see that I does not refer to B, so there are no loops. But this global termination check -- for a set of instances -- is beyond the abilities of GHC. This is arguably the right decision: after all, GHCi is not a full-blown theorem prover. Thus there are perfectly decidable type programs that require undecidable instances. Indeed, there is no reason to be afraid of that extension. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe