Re: [Haskell-cafe] New GHC Features for 7.10.1 and Beyond
Michael Snoyman wrote: On Tue, Apr 1, 2014 at 8:07 AM, Kazu Yamamoto k...@iij.ad.jp wrote: Hi Gershom, We've also seen a lot of interest in distribution and cloud computing. From the articles I've read, efficient concurrent programming involves using node.js, so I think we should put some work into writing a new-new-new-IO Manager built on top of this technology. As a member of Mio developers, I don't understand this sentence. Would you concretely explain what kind of node.js technologies should be taken into new-new-new-IO Manager? It's really simple: node.js is webscale, Mio is not. I'm sorry, but you simply didn't do a good enough job making sure that random packets were lost when sending network traffic, or that writing data to disk may sporadically fail. Better luck next time. I think Michael about sums it up. Erik -- -- Erik de Castro Lopo http://www.mega-nerd.com/ ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Eta Reduction
In the past year or two, there have been multiple performance problems in various areas related to the fact that lambda abstraction is not free, though we tend to think of it as so. A major example of this was deriving of Functor. If we were to derive Functor for lists, we would end up with something like: instance Functor [] where fmap _ [] = [] fmap f (x:xs) = f x : fmap (\y - f y) xs This definition is O(n^2) when fully evaluated,, because it causes O(n) eta expansions of f, so we spend time following indirections proportional to the depth of the element in the list. This has been fixed in 7.8, but there are other examples. I believe lens, [1] for instance, has some stuff in it that works very hard to avoid this sort of cost; and it's not always as easy to avoid as the above example. Composing with a newtype wrapper, for instance, causes an eta expansion that can only be seen as such at the core level. The obvious solution is: do eta reduction. However, this is not operationally sound currently. The problem is that seq is capable of telling the difference between the following two expressions: undefined \x - undefined x The former causes seq to throw an exception, while the latter is considered defined enough to not do so. So, if we eta reduce, we can cause terminating programs to diverge if they make use of this feature. Luckily, there is a solution. Semantically one would usually identify the above two expressions. While I do believe one could construct a semantics that does distinguish them, it is not the usual practice. This suggests that there is a way to not distinguish them, perhaps even including seq. After all, the specification of seq is monotone and continuous regardless of whether we unify ⊥ with \x - ⊥ x or insert an extra element for the latter. The currently problematic case is function spaces, so I'll focus on it. How should: seq : (a - b) - c - c act? Well, other than an obvious bottom, we need to emit bottom whenever our given function is itself bottom at every input. This may first seem like a problem, but it is actually quite simple. Without loss of generality, let us assume that we can enumerate the type a. Then, we can feed these values to the function, and check their results for bottom. Conal Elliot has prior art for this sort of thing with his unamb [2] package. For each value x :: a, simply compute 'f x `seq` ()' in parallel, and look for any successes. If we ever find one, we know the function is non-bottom, and we can return our value of c. If we never finish searching, then the function must be bottom, and seq should not terminate, so we have satisfied the specification. Now, some may complain about the enumeration above. But this, too, is a simple matter. It is well known that Haskell programs are denumerable. So it is quite easy to enumerate all Haskell programs that produce a value, check whether that value has the type we're interested in, and compute said value. All of this can be done in Haskell. Thus, every Haskell type is programatically enumerable in Haskell, and we can use said enumeration in our implementation of seq for function types. I have discussed this with Russell O'Connor [3], and he assures me that this argument should be sufficient even if we consider semantic models of Haskell that contain values not denoted by any Haskell program, so we should be safe there. The one possible caveat is that this implementation of seq is not operationally uniform across all types, so the current fully polymorphic type of seq may not make sense. But moving back to a type class based approach isn't so bad, and this time we will have a semantically sound backing, instead of just having a class with the equivalent of the current magic function in it. Once this machinery is in place, we can eta reduce to our hearts' content, and not have to worry about breaking semantics. We'd no longer put the burden on programmers to use potentially unsafe hacks to avoid eta expansions. I apologize for not sketching an implementation of the above algorithm, but I'm sure it should be elementary enough to make it into GHC in the next couple versions. Everyone learns about this type of thing in university computer science programs, no? Thoughts? Comments? Questions? Cheers, -- Dan [1] http://hackage.haskell.org/package/lens [2] http://hackage.haskell.org/package/unamb [3] http://r6.ca/ ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Buildbots
It having been suggested that a buildbot for Windows may be needed, and it being possible that I may receive permission from management for setting one up in my department's server room, I set about attempting to discover what this actually entails. A Google search led me to https://ghc.haskell.org/trac/ghc/wiki/BuildBot, which tells me that Buildbot is currently down, and we are working on a replacement. See Builder for more details. If I follow the 'down' link , I get to the GHC status April 2010 page, which says that buildbot has been abandoned, suggesting that the page should be deleted. Could someone confirm before I go ahead and delete it? The Builder page has clear instructions on how to set up a build slave, and a link to the build results. The build results contains an assortment of dud links and builds from August and earlier. What is the current state of automated builds? -- View this message in context: http://haskell.1045720.n5.nabble.com/Buildbots-tp5746770.html Sent from the Haskell - Glasgow-haskell-users mailing list archive at Nabble.com. ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Buildbots
Hi, Gabor Pali provides his own builder server infrastructure for now when GHC's HQ is not working. Please have a look at http://haskell.inf.elte.hu/builders/ and contact Gabor for more details (he is cced). Thanks! Karel On 04/ 1/14 09:42 AM, harry wrote: It having been suggested that a buildbot for Windows may be needed, and it being possible that I may receive permission from management for setting one up in my department's server room, I set about attempting to discover what this actually entails. A Google search led me to https://ghc.haskell.org/trac/ghc/wiki/BuildBot, which tells me that Buildbot is currently down, and we are working on a replacement. See Builder for more details. If I follow the 'down' link , I get to the GHC status April 2010 page, which says that buildbot has been abandoned, suggesting that the page should be deleted. Could someone confirm before I go ahead and delete it? The Builder page has clear instructions on how to set up a build slave, and a link to the build results. The build results contains an assortment of dud links and builds from August and earlier. What is the current state of automated builds? -- View this message in context: http://haskell.1045720.n5.nabble.com/Buildbots-tp5746770.html Sent from the Haskell - Glasgow-haskell-users mailing list archive at Nabble.com. ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Buildbots
We now have a (Linux) travis-ci buildbot so we should be able to use whatever script that buildbot runs. To make a full validate you simply check out the source repos and run: CPUS=N sh validate (CPUS=N is optional of course.) On Tue, Apr 1, 2014 at 9:42 AM, harry volderm...@hotmail.com wrote: It having been suggested that a buildbot for Windows may be needed, and it being possible that I may receive permission from management for setting one up in my department's server room, I set about attempting to discover what this actually entails. A Google search led me to https://ghc.haskell.org/trac/ghc/wiki/BuildBot, which tells me that Buildbot is currently down, and we are working on a replacement. See Builder for more details. If I follow the 'down' link , I get to the GHC status April 2010 page, which says that buildbot has been abandoned, suggesting that the page should be deleted. Could someone confirm before I go ahead and delete it? The Builder page has clear instructions on how to set up a build slave, and a link to the build results. The build results contains an assortment of dud links and builds from August and earlier. What is the current state of automated builds? -- View this message in context: http://haskell.1045720.n5.nabble.com/Buildbots-tp5746770.html Sent from the Haskell - Glasgow-haskell-users mailing list archive at Nabble.com. ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Buildbots
Johan Tibell-2 wrote We now have a (Linux) travis-ci buildbot so we should be able to use whatever script that buildbot runs. Does this mean that the Builder page is also no longer relevant? And if so, how could a Windows buildbot be set up? -- View this message in context: http://haskell.1045720.n5.nabble.com/Buildbots-tp5746770p5746774.html Sent from the Haskell - Glasgow-haskell-users mailing list archive at Nabble.com. ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Buildbots
On Tue, Apr 1, 2014 at 10:07 AM, harry volderm...@hotmail.com wrote: Johan Tibell-2 wrote We now have a (Linux) travis-ci buildbot so we should be able to use whatever script that buildbot runs. Does this mean that the Builder page is also no longer relevant? And if so, how could a Windows buildbot be set up? I don't know whether the old buildbot is still in use. I haven't seen any emails from it in quite a while. I'll wait for some other people on the list to chime in. ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
RE: Buildbots
Friends The nightly-build infrastructure for GHC is in disarray, and we could really do with help. We really want * Continuous integration so that new test failures show up fast * Nightly builds on a variety of platforms, giving snapshots that are easy to install Originally we used Buildbot (http://buildbot.net/). Then in 2010 Ian Lynagh put a lot of work into a build-bot infrastructure, implemented in Haskell as an open-source project, GHC Builder (https://ghc.haskell.org/trac/ghc/wiki/Builder). See https://ghc.haskell.org/trac/ghc/wiki/Status/Apr10#Nightlybuilds for the reasoning at the time. As I understand it, Builder never caught fire, and now that Ian has moved on I don't know that anyone is maintaining it; nor are the various builders working so far as I know. Perhaps competing technology has moved on, so that the original rationale no longer holds? I'm not sure. Regardless, we lack leadership in this area. Joachim Breitner has set up Travis-CI. (I don't know exactly what that is, but it sounds useful.) Others have indicated interest/willingness. But it would be fantastic to have a person, or (more plausibly) a small group who assumed leadership. An early question would be: to continue to use a DIY system (Builder), or to move to some other better-supported (but perhaps less malleable) system. I don't even know what the options are. Others will be better informed than me about all this... we'd love to hear from you. Thank you! Simon | -Original Message- | From: Glasgow-haskell-users [mailto:glasgow-haskell-users- | boun...@haskell.org] On Behalf Of harry | Sent: 01 April 2014 08:42 | To: glasgow-haskell-users@haskell.org | Subject: Buildbots | | It having been suggested that a buildbot for Windows may be needed, and | it | being possible that I may receive permission from management for setting | one | up in my department's server room, I set about attempting to discover | what | this actually entails. | | A Google search led me to https://ghc.haskell.org/trac/ghc/wiki/BuildBot, | which tells me that Buildbot is currently down, and we are working on a | replacement. See Builder for more details. If I follow the 'down' link , | I | get to the GHC status April 2010 page, which says that buildbot has been | abandoned, suggesting that the page should be deleted. Could someone | confirm | before I go ahead and delete it? | | The Builder page has clear instructions on how to set up a build slave, | and | a link to the build results. The build results contains an assortment of | dud | links and builds from August and earlier. | | What is the current state of automated builds? | | | | -- | View this message in context: | http://haskell.1045720.n5.nabble.com/Buildbots-tp5746770.html | Sent from the Haskell - Glasgow-haskell-users mailing list archive at | Nabble.com. | ___ | Glasgow-haskell-users mailing list | Glasgow-haskell-users@haskell.org | http://www.haskell.org/mailman/listinfo/glasgow-haskell-users ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Buildbots
Hi, Am Dienstag, den 01.04.2014, 10:25 + schrieb Simon Peyton Jones: Joachim Breitner has set up Travis-CI. (I don't know exactly what that is, but it sounds useful.) Travis is a free cloud service that runs arbitrary tests (in our case, a stripped version of validate) upon pushes to git repositories on github. I set it up to validate our master, so we get a nice history of successes and failures on https://travis-ci.org/nomeata/ghc-complete/builds and I get mails when things fail; that is when I send hopefully polite enough mails to ghc-dev, asking people to fix their commits. (Unless I broke it myself; then I silently fix it and hide.) It is a makeshift solution until we get our own infrastructure working. An early question would be: to continue to use a DIY system (Builder), or to move to some other better-supported (but perhaps less malleable) system. I don't even know what the options are. Sigh, test infrastructure are like content management systems: There are plenty out there to choose from, all can do lots of things one does not need, but none can do all, so one starts writing something selfmade, which eventually evolves in yet another of these beasts, just with fewer users. I’d recommend a move to existing, proven tools. Unfortunately, I cannot give advice as to what tool to move to. But if all these¹ projects are happy with buildbot, it might not be the worst choice. ¹ http://trac.buildbot.net/wiki/SuccessStories Greetings, Joachim -- Joachim “nomeata” Breitner m...@joachim-breitner.de • http://www.joachim-breitner.de/ Jabber: nome...@joachim-breitner.de • GPG-Key: 0x4743206C Debian Developer: nome...@debian.org signature.asc Description: This is a digitally signed message part ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
RE: Haskell Support on Windows
| I've been getting the impression that a lot of the stickier GHC bugs are | Windows specific, while very few GHC hackers actually use Windows, other | than to ensure that GHC works on it. ... | Perhaps it should be demoted to second-tier GHC support as well, at | least to the extent that Windows bugs won't hold up a release? That's true. But many, many people *use* GHC on Windows. It would be terribly sad to abandon them. What we need is more developers to volunteer to help look after the Windows version of GHC. One or two are doing so, but we need more. Please! Simon ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Buildbots
Hi Joachim: From what I understand Travis CI limits running time for each build. We may be able to create binaries of stage1 and/or stage2 in one build and test them in another. We could also fan out the test process using a Build Matrix to let GHC's full suite fit into the time limit as fragments. That would require some changes to the testsuite or some lengthy build scripts for each segment that explicitly run many make TEST=sometest commands. I had to do something similar at Verafin because the whole test suite was taking too long as a whole unit. I split it into builds for each separate module and used more build agents so they could run in parallel. Verafin is using TeamCity, but I think the concepts are achievable in Buildbot or Travis CI. In my opinion, the best build and CI system is the one you can get working. Best, Alain On Apr 1, 2014, at 10:46, Joachim Breitner m...@joachim-breitner.de wrote: Hi, Am Dienstag, den 01.04.2014, 10:25 + schrieb Simon Peyton Jones: Joachim Breitner has set up Travis-CI. (I don't know exactly what that is, but it sounds useful.) Travis is a free cloud service that runs arbitrary tests (in our case, a stripped version of validate) upon pushes to git repositories on github. I set it up to validate our master, so we get a nice history of successes and failures on https://travis-ci.org/nomeata/ghc-complete/builds and I get mails when things fail; that is when I send hopefully polite enough mails to ghc-dev, asking people to fix their commits. (Unless I broke it myself; then I silently fix it and hide.) It is a makeshift solution until we get our own infrastructure working. An early question would be: to continue to use a DIY system (Builder), or to move to some other better-supported (but perhaps less malleable) system. I don't even know what the options are. Sigh, test infrastructure are like content management systems: There are plenty out there to choose from, all can do lots of things one does not need, but none can do all, so one starts writing something selfmade, which eventually evolves in yet another of these beasts, just with fewer users. I’d recommend a move to existing, proven tools. Unfortunately, I cannot give advice as to what tool to move to. But if all these¹ projects are happy with buildbot, it might not be the worst choice. ¹ http://trac.buildbot.net/wiki/SuccessStories Greetings, Joachim -- Joachim “nomeata” Breitner m...@joachim-breitner.de • http://www.joachim-breitner.de/ Jabber: nome...@joachim-breitner.de • GPG-Key: 0x4743206C Debian Developer: nome...@debian.org ___ ghc-devs mailing list ghc-d...@haskell.org http://www.haskell.org/mailman/listinfo/ghc-devs ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
RE: GHC API: getting the unfolding of a strange Id
These absent thunks appear when the strictness analyser works out that a function does not use an argument at all. Suppose 'f' does not use its first argument. Then a call f (...big expression...) will be replaced with f (absentError blah) Such thunks almost invariably turn out to be dead code in the end, and are discarded. It's very unusual for them to survive to the end of compilation, let alone as a top-level value. But it's not impossible. Just for curiosity, can you compile with -dverbose-core2core, and leave the results somewhere I can see them? In short, it doesn't look as if there is anything wrong. If there's a good reason you want to see the unfolding anyway, that's not impossible, but at least you understand what is happening now. Simon | -Original Message- | From: Christiaan Baaij [mailto:christiaan.ba...@gmail.com] | Sent: 28 March 2014 09:57 | To: Simon Peyton Jones | Cc: glasgow-haskell-users | Subject: Re: GHC API: getting the unfolding of a strange Id | | | I don't really get why this GHC.TypeLits constraint is a bottom | dictionary... | Is it because all Coercions/Constraints are bottom? | Is there perhaps a set of flags I can use so that I can see the Core | term corresponding to CLaSH.Sized.Fixed.$fNumFixed2 during compilation? | | | I guess I straight away answer my own question, sorry for the noise: | | CLaSH.Sized.Fixed.$fNumFixed2 | :: forall (n_a5SH :: GHC.TypeLits.Nat). 1 GHC.TypeLits.= n_a5SH | [GblId, Str=DmdType b] | CLaSH.Sized.Fixed.$fNumFixed2 = | \ (@ (n_a5SH :: GHC.TypeLits.Nat)) - | Control.Exception.Base.absentError | @ (1 GHC.TypeLits.= n_a5SH) | ww_s9JT{v} [lid] 1 base:GHC.TypeLits.={tc r1W} n{tv a5SH} [tv]# | | I must say... I have never seen, in any of my programs, the error that | Control.Exception.Base.absentError is supposed to give: | absentError s = error (Oops! Entered absent arg ++ | unpackCStringUtf8# s) | | -- Christiaan ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Buildbots
Hi, On Apr 1, 2014, at 11:11, Joachim Breitner m...@joachim-breitner.de wrote: Hi, Am Dienstag, den 01.04.2014, 11:08 + schrieb Alain O'Dea: From what I understand Travis CI limits running time for each build. We may be able to create binaries of stage1 and/or stage2 in one build and test them in another. We could also fan out the test process using a Build Matrix to let GHC's full suite fit into the time limit as fragments. That would require some changes to the testsuite or some lengthy build scripts for each segment that explicitly run many make TEST=sometest commands. The main problem with Travis is that it only tests on one architecture. There are more (e.g. very undetailed reporting compared to a buildbot waterfall/grid) Good points. Hence: Travis is _not_ going to be a solution for us; we will want our own infrastructure. I'm happy to assist with getting whatever system fits the bill working. It seems like Buildbot should. Where can we get infrastructure on multiple architectures easily? I imagine we may need to mix and match. Greetings, Joachim -- Joachim “nomeata” Breitner m...@joachim-breitner.de • http://www.joachim-breitner.de/ Jabber: nome...@joachim-breitner.de • GPG-Key: 0x4743206C Debian Developer: nome...@debian.org ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Buildbots
Hi, I'm curious why not to use what's already written by Ian and others and which is currently running again? E.g. Janos Gabor Pali was so nice to start and keep builder server running on http://haskell.inf.elte.hu/builders/ Just few are there, but others may be added. Just send email to Janos to get the credentials and more information about what to get from where (recent builder client is needed). Perhaps we shall more advertise this option on GHC's builder wiki page? Thanks, Karel On 04/ 1/14 01:11 PM, Joachim Breitner wrote: Hence: Travis is _not_ going to be a solution for us; we will want our own infrastructure. ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
RE: Buildbots
Indeed, there is no reason not to use Ian et al's Builder stuff. It's one of the options. But it depends on a critical evaluation of what the advantages and disadvantages of different approaches are Simon | -Original Message- | From: Glasgow-haskell-users [mailto:glasgow-haskell-users- | boun...@haskell.org] On Behalf Of Karel Gardas | Sent: 01 April 2014 12:46 | To: Joachim Breitner; ghc-d...@haskell.org; Páli Gábor János | Cc: glasgow-haskell-users@haskell.org | Subject: Re: Buildbots | | | Hi, | | I'm curious why not to use what's already written by Ian and others and | which is currently running again? E.g. Janos Gabor Pali was so nice to | start and keep builder server running on | http://haskell.inf.elte.hu/builders/ | | Just few are there, but others may be added. Just send email to Janos to | get the credentials and more information about what to get from where | (recent builder client is needed). | | Perhaps we shall more advertise this option on GHC's builder wiki page? | | Thanks, | Karel | | | On 04/ 1/14 01:11 PM, Joachim Breitner wrote: | Hence: Travis is _not_ going to be a solution for us; we will want our | own infrastructure. | ___ | Glasgow-haskell-users mailing list | Glasgow-haskell-users@haskell.org | http://www.haskell.org/mailman/listinfo/glasgow-haskell-users ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Buildbots
I'm going to read up on Ian's Buildbot work and experiment with that in the meantime. If other challenges come up I'm glad to dive in and help. On Apr 1, 2014, at 12:03, Simon Peyton Jones simo...@microsoft.com wrote: Indeed, there is no reason not to use Ian et al's Builder stuff. It's one of the options. But it depends on a critical evaluation of what the advantages and disadvantages of different approaches are Simon | -Original Message- | From: Glasgow-haskell-users [mailto:glasgow-haskell-users- | boun...@haskell.org] On Behalf Of Karel Gardas | Sent: 01 April 2014 12:46 | To: Joachim Breitner; ghc-d...@haskell.org; Páli Gábor János | Cc: glasgow-haskell-users@haskell.org | Subject: Re: Buildbots | | | Hi, | | I'm curious why not to use what's already written by Ian and others and | which is currently running again? E.g. Janos Gabor Pali was so nice to | start and keep builder server running on | http://haskell.inf.elte.hu/builders/ | | Just few are there, but others may be added. Just send email to Janos to | get the credentials and more information about what to get from where | (recent builder client is needed). | | Perhaps we shall more advertise this option on GHC's builder wiki page? | | Thanks, | Karel | | | On 04/ 1/14 01:11 PM, Joachim Breitner wrote: | Hence: Travis is _not_ going to be a solution for us; we will want our | own infrastructure. | ___ | Glasgow-haskell-users mailing list | Glasgow-haskell-users@haskell.org | http://www.haskell.org/mailman/listinfo/glasgow-haskell-users ___ ghc-devs mailing list ghc-d...@haskell.org http://www.haskell.org/mailman/listinfo/ghc-devs ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Eta Reduction
I think this is a great idea and should become a top priority. I would probably start by switching to a type-class-based seq, after which perhaps the next step forward would become more clear. John L. On Apr 1, 2014 2:54 AM, Dan Doel dan.d...@gmail.com wrote: In the past year or two, there have been multiple performance problems in various areas related to the fact that lambda abstraction is not free, though we tend to think of it as so. A major example of this was deriving of Functor. If we were to derive Functor for lists, we would end up with something like: instance Functor [] where fmap _ [] = [] fmap f (x:xs) = f x : fmap (\y - f y) xs This definition is O(n^2) when fully evaluated,, because it causes O(n) eta expansions of f, so we spend time following indirections proportional to the depth of the element in the list. This has been fixed in 7.8, but there are other examples. I believe lens, [1] for instance, has some stuff in it that works very hard to avoid this sort of cost; and it's not always as easy to avoid as the above example. Composing with a newtype wrapper, for instance, causes an eta expansion that can only be seen as such at the core level. The obvious solution is: do eta reduction. However, this is not operationally sound currently. The problem is that seq is capable of telling the difference between the following two expressions: undefined \x - undefined x The former causes seq to throw an exception, while the latter is considered defined enough to not do so. So, if we eta reduce, we can cause terminating programs to diverge if they make use of this feature. Luckily, there is a solution. Semantically one would usually identify the above two expressions. While I do believe one could construct a semantics that does distinguish them, it is not the usual practice. This suggests that there is a way to not distinguish them, perhaps even including seq. After all, the specification of seq is monotone and continuous regardless of whether we unify ⊥ with \x - ⊥ x or insert an extra element for the latter. The currently problematic case is function spaces, so I'll focus on it. How should: seq : (a - b) - c - c act? Well, other than an obvious bottom, we need to emit bottom whenever our given function is itself bottom at every input. This may first seem like a problem, but it is actually quite simple. Without loss of generality, let us assume that we can enumerate the type a. Then, we can feed these values to the function, and check their results for bottom. Conal Elliot has prior art for this sort of thing with his unamb [2] package. For each value x :: a, simply compute 'f x `seq` ()' in parallel, and look for any successes. If we ever find one, we know the function is non-bottom, and we can return our value of c. If we never finish searching, then the function must be bottom, and seq should not terminate, so we have satisfied the specification. Now, some may complain about the enumeration above. But this, too, is a simple matter. It is well known that Haskell programs are denumerable. So it is quite easy to enumerate all Haskell programs that produce a value, check whether that value has the type we're interested in, and compute said value. All of this can be done in Haskell. Thus, every Haskell type is programatically enumerable in Haskell, and we can use said enumeration in our implementation of seq for function types. I have discussed this with Russell O'Connor [3], and he assures me that this argument should be sufficient even if we consider semantic models of Haskell that contain values not denoted by any Haskell program, so we should be safe there. The one possible caveat is that this implementation of seq is not operationally uniform across all types, so the current fully polymorphic type of seq may not make sense. But moving back to a type class based approach isn't so bad, and this time we will have a semantically sound backing, instead of just having a class with the equivalent of the current magic function in it. Once this machinery is in place, we can eta reduce to our hearts' content, and not have to worry about breaking semantics. We'd no longer put the burden on programmers to use potentially unsafe hacks to avoid eta expansions. I apologize for not sketching an implementation of the above algorithm, but I'm sure it should be elementary enough to make it into GHC in the next couple versions. Everyone learns about this type of thing in university computer science programs, no? Thoughts? Comments? Questions? Cheers, -- Dan [1] http://hackage.haskell.org/package/lens [2] http://hackage.haskell.org/package/unamb [3] http://r6.ca/ ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Eta Reduction
Can we throw some whole program partial evaluation with a termination decision oracle into the mix? On Tuesday, April 1, 2014, John Lato jwl...@gmail.com wrote: I think this is a great idea and should become a top priority. I would probably start by switching to a type-class-based seq, after which perhaps the next step forward would become more clear. John L. On Apr 1, 2014 2:54 AM, Dan Doel dan.d...@gmail.comjavascript:_e(%7B%7D,'cvml','dan.d...@gmail.com'); wrote: In the past year or two, there have been multiple performance problems in various areas related to the fact that lambda abstraction is not free, though we tend to think of it as so. A major example of this was deriving of Functor. If we were to derive Functor for lists, we would end up with something like: instance Functor [] where fmap _ [] = [] fmap f (x:xs) = f x : fmap (\y - f y) xs This definition is O(n^2) when fully evaluated,, because it causes O(n) eta expansions of f, so we spend time following indirections proportional to the depth of the element in the list. This has been fixed in 7.8, but there are other examples. I believe lens, [1] for instance, has some stuff in it that works very hard to avoid this sort of cost; and it's not always as easy to avoid as the above example. Composing with a newtype wrapper, for instance, causes an eta expansion that can only be seen as such at the core level. The obvious solution is: do eta reduction. However, this is not operationally sound currently. The problem is that seq is capable of telling the difference between the following two expressions: undefined \x - undefined x The former causes seq to throw an exception, while the latter is considered defined enough to not do so. So, if we eta reduce, we can cause terminating programs to diverge if they make use of this feature. Luckily, there is a solution. Semantically one would usually identify the above two expressions. While I do believe one could construct a semantics that does distinguish them, it is not the usual practice. This suggests that there is a way to not distinguish them, perhaps even including seq. After all, the specification of seq is monotone and continuous regardless of whether we unify ⊥ with \x - ⊥ x or insert an extra element for the latter. The currently problematic case is function spaces, so I'll focus on it. How should: seq : (a - b) - c - c act? Well, other than an obvious bottom, we need to emit bottom whenever our given function is itself bottom at every input. This may first seem like a problem, but it is actually quite simple. Without loss of generality, let us assume that we can enumerate the type a. Then, we can feed these values to the function, and check their results for bottom. Conal Elliot has prior art for this sort of thing with his unamb [2] package. For each value x :: a, simply compute 'f x `seq` ()' in parallel, and look for any successes. If we ever find one, we know the function is non-bottom, and we can return our value of c. If we never finish searching, then the function must be bottom, and seq should not terminate, so we have satisfied the specification. Now, some may complain about the enumeration above. But this, too, is a simple matter. It is well known that Haskell programs are denumerable. So it is quite easy to enumerate all Haskell programs that produce a value, check whether that value has the type we're interested in, and compute said value. All of this can be done in Haskell. Thus, every Haskell type is programatically enumerable in Haskell, and we can use said enumeration in our implementation of seq for function types. I have discussed this with Russell O'Connor [3], and he assures me that this argument should be sufficient even if we consider semantic models of Haskell that contain values not denoted by any Haskell program, so we should be safe there. The one possible caveat is that this implementation of seq is not operationally uniform across all types, so the current fully polymorphic type of seq may not make sense. But moving back to a type class based approach isn't so bad, and this time we will have a semantically sound backing, instead of just having a class with the equivalent of the current magic function in it. Once this machinery is in place, we can eta reduce to our hearts' content, and not have to worry about breaking semantics. We'd no longer put the burden on programmers to use potentially unsafe hacks to avoid eta expansions. I apologize for not sketching an implementation of the above algorithm, but I'm sure it should be elementary enough to make it into GHC in the next couple versions. Everyone learns about this type of thing in university computer science programs, no? Thoughts? Comments? Questions? Cheers, -- Dan [1] http://hackage.haskell.org/package/lens [2]
Re: [Haskell-cafe] Eta Reduction
John, Check the date and consider the process necessary to enumerate all Haskell programs and check their types. -Edward On Tue, Apr 1, 2014 at 9:17 AM, John Lato jwl...@gmail.com wrote: I think this is a great idea and should become a top priority. I would probably start by switching to a type-class-based seq, after which perhaps the next step forward would become more clear. John L. On Apr 1, 2014 2:54 AM, Dan Doel dan.d...@gmail.com wrote: In the past year or two, there have been multiple performance problems in various areas related to the fact that lambda abstraction is not free, though we tend to think of it as so. A major example of this was deriving of Functor. If we were to derive Functor for lists, we would end up with something like: instance Functor [] where fmap _ [] = [] fmap f (x:xs) = f x : fmap (\y - f y) xs This definition is O(n^2) when fully evaluated,, because it causes O(n) eta expansions of f, so we spend time following indirections proportional to the depth of the element in the list. This has been fixed in 7.8, but there are other examples. I believe lens, [1] for instance, has some stuff in it that works very hard to avoid this sort of cost; and it's not always as easy to avoid as the above example. Composing with a newtype wrapper, for instance, causes an eta expansion that can only be seen as such at the core level. The obvious solution is: do eta reduction. However, this is not operationally sound currently. The problem is that seq is capable of telling the difference between the following two expressions: undefined \x - undefined x The former causes seq to throw an exception, while the latter is considered defined enough to not do so. So, if we eta reduce, we can cause terminating programs to diverge if they make use of this feature. Luckily, there is a solution. Semantically one would usually identify the above two expressions. While I do believe one could construct a semantics that does distinguish them, it is not the usual practice. This suggests that there is a way to not distinguish them, perhaps even including seq. After all, the specification of seq is monotone and continuous regardless of whether we unify ⊥ with \x - ⊥ x or insert an extra element for the latter. The currently problematic case is function spaces, so I'll focus on it. How should: seq : (a - b) - c - c act? Well, other than an obvious bottom, we need to emit bottom whenever our given function is itself bottom at every input. This may first seem like a problem, but it is actually quite simple. Without loss of generality, let us assume that we can enumerate the type a. Then, we can feed these values to the function, and check their results for bottom. Conal Elliot has prior art for this sort of thing with his unamb [2] package. For each value x :: a, simply compute 'f x `seq` ()' in parallel, and look for any successes. If we ever find one, we know the function is non-bottom, and we can return our value of c. If we never finish searching, then the function must be bottom, and seq should not terminate, so we have satisfied the specification. Now, some may complain about the enumeration above. But this, too, is a simple matter. It is well known that Haskell programs are denumerable. So it is quite easy to enumerate all Haskell programs that produce a value, check whether that value has the type we're interested in, and compute said value. All of this can be done in Haskell. Thus, every Haskell type is programatically enumerable in Haskell, and we can use said enumeration in our implementation of seq for function types. I have discussed this with Russell O'Connor [3], and he assures me that this argument should be sufficient even if we consider semantic models of Haskell that contain values not denoted by any Haskell program, so we should be safe there. The one possible caveat is that this implementation of seq is not operationally uniform across all types, so the current fully polymorphic type of seq may not make sense. But moving back to a type class based approach isn't so bad, and this time we will have a semantically sound backing, instead of just having a class with the equivalent of the current magic function in it. Once this machinery is in place, we can eta reduce to our hearts' content, and not have to worry about breaking semantics. We'd no longer put the burden on programmers to use potentially unsafe hacks to avoid eta expansions. I apologize for not sketching an implementation of the above algorithm, but I'm sure it should be elementary enough to make it into GHC in the next couple versions. Everyone learns about this type of thing in university computer science programs, no? Thoughts? Comments? Questions? Cheers, -- Dan [1] http://hackage.haskell.org/package/lens [2] http://hackage.haskell.org/package/unamb [3] http://r6.ca/
Re: Buildbots
2014-04-01 14:03 GMT+02:00 Simon Peyton Jones simo...@microsoft.com: Indeed, there is no reason not to use Ian et al's Builder stuff. It's one of the options. But it depends on a critical evaluation of what the advantages and disadvantages of different approaches are I found Ian's buildbot an appealing alternative as it does a full build, including testing, and uploads the resulting binaries to a common place where anybody can access them (but it can be configured to do almost anything). The builders may be configured individually from a single (Haskell-language) configuration file and they are run on various volunteer-supplied systems so it is also distributed. I use this to keep track of the status of the FreeBSD builds to make my work easier on building the releases and maintaining the associated ports in the FreeBSD Ports Collection, while offering regular developer snapshots for the users. This approach also allows me to control and maintain the builder environment too as it may require minor or major changes and fixes over time that I can do myself as a FreeBSD developer. In the past, there were cases where the build was failing due to bugs in the kernel or the userland, so this is not purely about GHC itself (unfortunately). In my humble opinon, there are merits for the Travis-based Continuous Integration, so as for the daily snapshot building on each supported platform. I do not care if it is not Haskell-based or it is hosted at a central place with individual Virtual Machines for each platform -- until I can keep doing what I have been doing for 4 years now. ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: New GHC Features for 7.10.1 and Beyond
On Mon, Mar 31, 2014 at 9:37 PM, Gershom Bazerman gersh...@gmail.comwrote: There's been lots of exciting work going into the forthcoming GHC 7.8.1 release. But even with all these new features, our language is far from complete and I wouldn't want the GHC team to rest on their laurels. Especially with so much renewed community involvement in GHC development, it seems appropriate to share some ideas some of us have been discussing for future releases, and take a poll of community consensus regarding which ones people might be excited to jump in and help out with, or might find particularly helpful. Thanks Gershom! I was going to wait till things were more mature before announcing them, but given the enthusiasm generated by your post I think I'll share what we've been working on early. Given the importance of BigData in today's business world and the complexities of writing software to support it, we have started working on an extension to Haskell to make BigData the language of choice for BigData applications. The first hurdle we face is how to represent BigData. Previously, we could work with the data but not give it a consistent or unified type. The data was simply too large! To make the representation as natural and manageable as possible we have introduced -XBigTypes. Note: For technical reasons this also implies -XImpredicativeTypes and allows construction of infinite types. With these sorts of restrictions lifted we are able to construct much larger types than before such as the type of all types and the type a such that `a = [a]`. Jason ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Buildbots
hey all, I just exported the igloo builder code from darcs to git, and put it here https://github.com/cartazio/ghc-builder would this be something worth adding to github.com/haskell ? (i can easily add it if other folks it should be surfaced more visibly) On Tue, Apr 1, 2014 at 11:04 AM, Páli Gábor János pali.ga...@gmail.comwrote: 2014-04-01 14:03 GMT+02:00 Simon Peyton Jones simo...@microsoft.com: Indeed, there is no reason not to use Ian et al's Builder stuff. It's one of the options. But it depends on a critical evaluation of what the advantages and disadvantages of different approaches are I found Ian's buildbot an appealing alternative as it does a full build, including testing, and uploads the resulting binaries to a common place where anybody can access them (but it can be configured to do almost anything). The builders may be configured individually from a single (Haskell-language) configuration file and they are run on various volunteer-supplied systems so it is also distributed. I use this to keep track of the status of the FreeBSD builds to make my work easier on building the releases and maintaining the associated ports in the FreeBSD Ports Collection, while offering regular developer snapshots for the users. This approach also allows me to control and maintain the builder environment too as it may require minor or major changes and fixes over time that I can do myself as a FreeBSD developer. In the past, there were cases where the build was failing due to bugs in the kernel or the userland, so this is not purely about GHC itself (unfortunately). In my humble opinon, there are merits for the Travis-based Continuous Integration, so as for the daily snapshot building on each supported platform. I do not care if it is not Haskell-based or it is hosted at a central place with individual Virtual Machines for each platform -- until I can keep doing what I have been doing for 4 years now. ___ ghc-devs mailing list ghc-d...@haskell.org http://www.haskell.org/mailman/listinfo/ghc-devs ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Buildbots
Thank you Carter. I think it's reasonable to incubate it on your Github profile for now until we are certain it is fully working again. Either way works though :) Best, Alain On Apr 1, 2014, at 17:45, Carter Schonwald carter.schonw...@gmail.com wrote: hey all, I just exported the igloo builder code from darcs to git, and put it here https://github.com/cartazio/ghc-builder would this be something worth adding to github.com/haskell ? (i can easily add it if other folks it should be surfaced more visibly) On Tue, Apr 1, 2014 at 11:04 AM, Páli Gábor János pali.ga...@gmail.com wrote: 2014-04-01 14:03 GMT+02:00 Simon Peyton Jones simo...@microsoft.com: Indeed, there is no reason not to use Ian et al's Builder stuff. It's one of the options. But it depends on a critical evaluation of what the advantages and disadvantages of different approaches are I found Ian's buildbot an appealing alternative as it does a full build, including testing, and uploads the resulting binaries to a common place where anybody can access them (but it can be configured to do almost anything). The builders may be configured individually from a single (Haskell-language) configuration file and they are run on various volunteer-supplied systems so it is also distributed. I use this to keep track of the status of the FreeBSD builds to make my work easier on building the releases and maintaining the associated ports in the FreeBSD Ports Collection, while offering regular developer snapshots for the users. This approach also allows me to control and maintain the builder environment too as it may require minor or major changes and fixes over time that I can do myself as a FreeBSD developer. In the past, there were cases where the build was failing due to bugs in the kernel or the userland, so this is not purely about GHC itself (unfortunately). In my humble opinon, there are merits for the Travis-based Continuous Integration, so as for the daily snapshot building on each supported platform. I do not care if it is not Haskell-based or it is hosted at a central place with individual Virtual Machines for each platform -- until I can keep doing what I have been doing for 4 years now. ___ ghc-devs mailing list ghc-d...@haskell.org http://www.haskell.org/mailman/listinfo/ghc-devs ___ ghc-devs mailing list ghc-d...@haskell.org http://www.haskell.org/mailman/listinfo/ghc-devs ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Buildbots
2014-04-01 20:15 GMT+02:00 Alain O'Dea alain.o...@gmail.com: until we are certain it is fully working again. In what sense? I have been using the latest checkout from the darcs repository for both the server and the clients, I seldom experienced any serious problems. Of course, there is place for improvements and there are some rough edges, but I think it is quite usable, even in its current state. ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Buildbots
good to know (i assumed it was in working order from your remarks) I think making it more surfaced / discoverable might enable a lot more volunteer build bots (which is an issue aside from maintaining it) of course, officially moving it to github should be with ian's blessing, its mostly his work afaik :) On Tue, Apr 1, 2014 at 2:45 PM, Páli Gábor János pali.ga...@gmail.comwrote: 2014-04-01 20:15 GMT+02:00 Alain O'Dea alain.o...@gmail.com: until we are certain it is fully working again. In what sense? I have been using the latest checkout from the darcs repository for both the server and the clients, I seldom experienced any serious problems. Of course, there is place for improvements and there are some rough edges, but I think it is quite usable, even in its current state. ___ ghc-devs mailing list ghc-d...@haskell.org http://www.haskell.org/mailman/listinfo/ghc-devs ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Bang Patterns
Greetings, I've been thinking about bang patterns as part of implementing our own Haskell-like compiler here, and have been testing out GHC's implementation to see how it works. I've come to one case that seems like it doesn't work how I think it should, or how it is described, and wanted to ask about it. Specifically, consider: case Nothing of !(~(Just x)) - 5 Nothing - 12 Now, the way I'd expect this to work, and how I think the spec says it works, is that my Nothing is evaluated, and then the irrefutable ~(Just x) matches Nothing, giving a result of 5. In fact, GHC warns about overlapping patterns for this. However, this actually evaluates to 12, meaning that !(~p) appears to cancel out and be equivalent to p. It seems to me this might be a side effect of the logic used to implement 'let !p = ...', but I'm not certain. So, my question is whether this is intentional. If it is, then the bang patterns description should probably mention it, since it's subtly different than the rest of the specification. Also the warning should be removed, because there is no overlapping in the above case statement. If it is unintentional, we should probably decide either to make it intentional (and perform the above changes), or to change the implementation. :) Cheers, -- Dan ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Buildbots
2014-04-01 20:50 GMT+02:00 Carter Schonwald carter.schonw...@gmail.com: I think making it more surfaced / discoverable might enable a lot more volunteer build bots (which is an issue aside from maintaining it) As Karel has indicated, I have been already running an instance of the server and I am generally open to adding further clients, if you think this would be useful. Perhaps the only limitation would be the disk space for storing all the snapshots builds for all the all clients, but I could easily solve this problem :-) Or, if you want to move the whole service to some more official place, e.g. under the haskell.org infrastructure, I am happy to help with restarting the service, I already earned some experience in running both sides over the years. ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Buildbots
On Tue, Apr 1, 2014 at 12:46 PM, Joachim Breitner m...@joachim-breitner.dewrote: Hi, Am Dienstag, den 01.04.2014, 10:25 + schrieb Simon Peyton Jones: Joachim Breitner has set up Travis-CI. (I don't know exactly what that is, but it sounds useful.) Travis is a free cloud service that runs arbitrary tests (in our case, a stripped version of validate) upon pushes to git repositories on github. I set it up to validate our master, so we get a nice history of successes and failures on https://travis-ci.org/nomeata/ghc-complete/builds and I get mails when things fail; that is when I send hopefully polite enough mails to ghc-dev, asking people to fix their commits. (Unless I broke it myself; then I silently fix it and hide.) If the false positive rate is low, feel free to automatically have the emails sent to ghc-devs@. We want to know when we broke stuff ASAP. ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Buildbots
On Tue, Apr 01, 2014 at 12:46:05PM +0200, Joachim Breitner wrote: happy with buildbot, it might not be the worst choice. For reference, the reason we moved away from buildbot is that it needs to maintain a TCP connection for the duration of the build. With some builds taking many hours (either on old platforms, or on modern hardware but with a full testsuite run and nofib etc) it was common that a brief network glitch caused a build to not finish. Thanks Ian ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: [Haskell-cafe] Eta Reduction
Hi Edward, Yes, I'm aware of that. However, I thought Dan's proposal especially droll given that changing seq to a class-based function would be sufficient to make eta-reduction sound, given appropriate instances (or lack thereof). Meaning we could leave the rest of the proposal unevaluated (lazily!). And if somebody were to suggest that on a different day, +1 from me. John On Apr 1, 2014 10:32 AM, Edward Kmett ekm...@gmail.com wrote: John, Check the date and consider the process necessary to enumerate all Haskell programs and check their types. -Edward On Tue, Apr 1, 2014 at 9:17 AM, John Lato jwl...@gmail.com wrote: I think this is a great idea and should become a top priority. I would probably start by switching to a type-class-based seq, after which perhaps the next step forward would become more clear. John L. On Apr 1, 2014 2:54 AM, Dan Doel dan.d...@gmail.com wrote: In the past year or two, there have been multiple performance problems in various areas related to the fact that lambda abstraction is not free, though we tend to think of it as so. A major example of this was deriving of Functor. If we were to derive Functor for lists, we would end up with something like: instance Functor [] where fmap _ [] = [] fmap f (x:xs) = f x : fmap (\y - f y) xs This definition is O(n^2) when fully evaluated,, because it causes O(n) eta expansions of f, so we spend time following indirections proportional to the depth of the element in the list. This has been fixed in 7.8, but there are other examples. I believe lens, [1] for instance, has some stuff in it that works very hard to avoid this sort of cost; and it's not always as easy to avoid as the above example. Composing with a newtype wrapper, for instance, causes an eta expansion that can only be seen as such at the core level. The obvious solution is: do eta reduction. However, this is not operationally sound currently. The problem is that seq is capable of telling the difference between the following two expressions: undefined \x - undefined x The former causes seq to throw an exception, while the latter is considered defined enough to not do so. So, if we eta reduce, we can cause terminating programs to diverge if they make use of this feature. Luckily, there is a solution. Semantically one would usually identify the above two expressions. While I do believe one could construct a semantics that does distinguish them, it is not the usual practice. This suggests that there is a way to not distinguish them, perhaps even including seq. After all, the specification of seq is monotone and continuous regardless of whether we unify ⊥ with \x - ⊥ x or insert an extra element for the latter. The currently problematic case is function spaces, so I'll focus on it. How should: seq : (a - b) - c - c act? Well, other than an obvious bottom, we need to emit bottom whenever our given function is itself bottom at every input. This may first seem like a problem, but it is actually quite simple. Without loss of generality, let us assume that we can enumerate the type a. Then, we can feed these values to the function, and check their results for bottom. Conal Elliot has prior art for this sort of thing with his unamb [2] package. For each value x :: a, simply compute 'f x `seq` ()' in parallel, and look for any successes. If we ever find one, we know the function is non-bottom, and we can return our value of c. If we never finish searching, then the function must be bottom, and seq should not terminate, so we have satisfied the specification. Now, some may complain about the enumeration above. But this, too, is a simple matter. It is well known that Haskell programs are denumerable. So it is quite easy to enumerate all Haskell programs that produce a value, check whether that value has the type we're interested in, and compute said value. All of this can be done in Haskell. Thus, every Haskell type is programatically enumerable in Haskell, and we can use said enumeration in our implementation of seq for function types. I have discussed this with Russell O'Connor [3], and he assures me that this argument should be sufficient even if we consider semantic models of Haskell that contain values not denoted by any Haskell program, so we should be safe there. The one possible caveat is that this implementation of seq is not operationally uniform across all types, so the current fully polymorphic type of seq may not make sense. But moving back to a type class based approach isn't so bad, and this time we will have a semantically sound backing, instead of just having a class with the equivalent of the current magic function in it. Once this machinery is in place, we can eta reduce to our hearts' content, and not have to worry about breaking semantics. We'd no longer put the burden on programmers to use potentially unsafe
Re: [Haskell-cafe] Eta Reduction
Unfortunately the old class based solution also carries other baggage, like the old data type contexts being needed in the language for bang patterns. :( -Edward On Apr 1, 2014, at 5:26 PM, John Lato jwl...@gmail.com wrote: Hi Edward, Yes, I'm aware of that. However, I thought Dan's proposal especially droll given that changing seq to a class-based function would be sufficient to make eta-reduction sound, given appropriate instances (or lack thereof). Meaning we could leave the rest of the proposal unevaluated (lazily!). And if somebody were to suggest that on a different day, +1 from me. John On Apr 1, 2014 10:32 AM, Edward Kmett ekm...@gmail.com wrote: John, Check the date and consider the process necessary to enumerate all Haskell programs and check their types. -Edward On Tue, Apr 1, 2014 at 9:17 AM, John Lato jwl...@gmail.com wrote: I think this is a great idea and should become a top priority. I would probably start by switching to a type-class-based seq, after which perhaps the next step forward would become more clear. John L. On Apr 1, 2014 2:54 AM, Dan Doel dan.d...@gmail.com wrote: In the past year or two, there have been multiple performance problems in various areas related to the fact that lambda abstraction is not free, though we tend to think of it as so. A major example of this was deriving of Functor. If we were to derive Functor for lists, we would end up with something like: instance Functor [] where fmap _ [] = [] fmap f (x:xs) = f x : fmap (\y - f y) xs This definition is O(n^2) when fully evaluated,, because it causes O(n) eta expansions of f, so we spend time following indirections proportional to the depth of the element in the list. This has been fixed in 7.8, but there are other examples. I believe lens, [1] for instance, has some stuff in it that works very hard to avoid this sort of cost; and it's not always as easy to avoid as the above example. Composing with a newtype wrapper, for instance, causes an eta expansion that can only be seen as such at the core level. The obvious solution is: do eta reduction. However, this is not operationally sound currently. The problem is that seq is capable of telling the difference between the following two expressions: undefined \x - undefined x The former causes seq to throw an exception, while the latter is considered defined enough to not do so. So, if we eta reduce, we can cause terminating programs to diverge if they make use of this feature. Luckily, there is a solution. Semantically one would usually identify the above two expressions. While I do believe one could construct a semantics that does distinguish them, it is not the usual practice. This suggests that there is a way to not distinguish them, perhaps even including seq. After all, the specification of seq is monotone and continuous regardless of whether we unify ⊥ with \x - ⊥ x or insert an extra element for the latter. The currently problematic case is function spaces, so I'll focus on it. How should: seq : (a - b) - c - c act? Well, other than an obvious bottom, we need to emit bottom whenever our given function is itself bottom at every input. This may first seem like a problem, but it is actually quite simple. Without loss of generality, let us assume that we can enumerate the type a. Then, we can feed these values to the function, and check their results for bottom. Conal Elliot has prior art for this sort of thing with his unamb [2] package. For each value x :: a, simply compute 'f x `seq` ()' in parallel, and look for any successes. If we ever find one, we know the function is non-bottom, and we can return our value of c. If we never finish searching, then the function must be bottom, and seq should not terminate, so we have satisfied the specification. Now, some may complain about the enumeration above. But this, too, is a simple matter. It is well known that Haskell programs are denumerable. So it is quite easy to enumerate all Haskell programs that produce a value, check whether that value has the type we're interested in, and compute said value. All of this can be done in Haskell. Thus, every Haskell type is programatically enumerable in Haskell, and we can use said enumeration in our implementation of seq for function types. I have discussed this with Russell O'Connor [3], and he assures me that this argument should be sufficient even if we consider semantic models of Haskell that contain values not denoted by any Haskell program, so we should be safe there. The one possible caveat is that this implementation of seq is not operationally uniform across all types, so the current fully polymorphic type of seq may not make sense. But moving back to a type class based approach isn't so bad, and this time we will have a semantically sound backing,
Re: [Haskell-cafe] Eta Reduction
I'm already uneasy using bang patterns on polymorphic data because I don't know exactly what it will accomplish. Maybe it adds too much strictness? Not enough? Simply duplicates work? Perhaps it's acceptable to remove that feature entirely (although that may require adding extra strictness in a lot of other places). Alternatively, maybe it's enough to simply find a use for that good-for-nothing syntax we already have? On Apr 1, 2014 5:32 PM, Edward Kmett ekm...@gmail.com wrote: Unfortunately the old class based solution also carries other baggage, like the old data type contexts being needed in the language for bang patterns. :( -Edward On Apr 1, 2014, at 5:26 PM, John Lato jwl...@gmail.com wrote: Hi Edward, Yes, I'm aware of that. However, I thought Dan's proposal especially droll given that changing seq to a class-based function would be sufficient to make eta-reduction sound, given appropriate instances (or lack thereof). Meaning we could leave the rest of the proposal unevaluated (lazily!). And if somebody were to suggest that on a different day, +1 from me. John On Apr 1, 2014 10:32 AM, Edward Kmett ekm...@gmail.com wrote: John, Check the date and consider the process necessary to enumerate all Haskell programs and check their types. -Edward On Tue, Apr 1, 2014 at 9:17 AM, John Lato jwl...@gmail.com wrote: I think this is a great idea and should become a top priority. I would probably start by switching to a type-class-based seq, after which perhaps the next step forward would become more clear. John L. On Apr 1, 2014 2:54 AM, Dan Doel dan.d...@gmail.com wrote: In the past year or two, there have been multiple performance problems in various areas related to the fact that lambda abstraction is not free, though we tend to think of it as so. A major example of this was deriving of Functor. If we were to derive Functor for lists, we would end up with something like: instance Functor [] where fmap _ [] = [] fmap f (x:xs) = f x : fmap (\y - f y) xs This definition is O(n^2) when fully evaluated,, because it causes O(n) eta expansions of f, so we spend time following indirections proportional to the depth of the element in the list. This has been fixed in 7.8, but there are other examples. I believe lens, [1] for instance, has some stuff in it that works very hard to avoid this sort of cost; and it's not always as easy to avoid as the above example. Composing with a newtype wrapper, for instance, causes an eta expansion that can only be seen as such at the core level. The obvious solution is: do eta reduction. However, this is not operationally sound currently. The problem is that seq is capable of telling the difference between the following two expressions: undefined \x - undefined x The former causes seq to throw an exception, while the latter is considered defined enough to not do so. So, if we eta reduce, we can cause terminating programs to diverge if they make use of this feature. Luckily, there is a solution. Semantically one would usually identify the above two expressions. While I do believe one could construct a semantics that does distinguish them, it is not the usual practice. This suggests that there is a way to not distinguish them, perhaps even including seq. After all, the specification of seq is monotone and continuous regardless of whether we unify ⊥ with \x - ⊥ x or insert an extra element for the latter. The currently problematic case is function spaces, so I'll focus on it. How should: seq : (a - b) - c - c act? Well, other than an obvious bottom, we need to emit bottom whenever our given function is itself bottom at every input. This may first seem like a problem, but it is actually quite simple. Without loss of generality, let us assume that we can enumerate the type a. Then, we can feed these values to the function, and check their results for bottom. Conal Elliot has prior art for this sort of thing with his unamb [2] package. For each value x :: a, simply compute 'f x `seq` ()' in parallel, and look for any successes. If we ever find one, we know the function is non-bottom, and we can return our value of c. If we never finish searching, then the function must be bottom, and seq should not terminate, so we have satisfied the specification. Now, some may complain about the enumeration above. But this, too, is a simple matter. It is well known that Haskell programs are denumerable. So it is quite easy to enumerate all Haskell programs that produce a value, check whether that value has the type we're interested in, and compute said value. All of this can be done in Haskell. Thus, every Haskell type is programatically enumerable in Haskell, and we can use said enumeration in our implementation of seq for function types. I have discussed this with Russell O'Connor [3], and he assures me that this argument should be sufficient even if we consider semantic models