- ghc-devs - Haskell.org

Re: Type-level generics
by David Feuer 03 Sep '17

03 Sep '17

Ah, nice. I was actually exploring the vague general idea behind that approach earlier this evening. Magalhães (unsurprisingly) has developed it much much further. David FeuerWell-Typed, LLP -------- Original message --------From: Ryan Scott <ryan.gl.scott(a)gmail.com> Date: 9/2/17 10:36 PM (GMT-05:00) To: ghc-devs(a)haskell.org Subject: Re: Type-level generics If you're willing to go a completely different route from GHC.Generics, then you might be interested in the paper Generic Programming with Multiple Parameters [1] (whose existence I just learned of—thanks to Pedro, the author, for pointing it out to me). It does present a single Generic class that is capable of working over any number of type parameters, although the interface presented is significantly more complex than the current GHC.Generics. The only reason I mention backwards compatibility is that if we are going to introduce a GHC.Generics 2.0 some day, it'd be nice to have a way to subsume the old interface with the new one, and fortunately, the aforementioned paper includes an algorithm for doing so. My hope was that we'd be able to incorporate these ideas into a design that also grants the ability to write Generic instances for GADTs, but I don't think GHC has a fancy enough type system to do this satisfactorily at the moment. Ryan S. ----- [1] http://dreixel.net/research/pdf/gpmp_colour.pdf _______________________________________________ ghc-devs mailing list ghc-devs(a)haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs

1 0

Re: Type-level generics
by Ryan Scott 02 Sep '17

02 Sep '17

Several good points were brought up. Let me go through them and try to make sense of what I can: > When I looked at it the last time, there were some apparent leftovers in the form of types or type parameters never used. Are you referring to the `p` type parameters that are found in most of the data types in GHC.Generics? If so, they are most definitely used—try deriving Generic1 to see this in action! It's true that in the context of Generic (without the 1 at the end) the `p` isn't used, but this is by design, as this allows us to share the same representation types across Generic and Generic1. > there is no possibility to work with types with more than one parameter. Quite true. But I posit that engineering GHC.Generics to work with more than one type parameter at a time is much harder than it sounds. After all, to profitably work with even a *single* type parameter (what Generic1 does), we must bring in three additional representation types: Par1, Rec1, and (:.:), depending on where in the datatype the last type parameter occurs. If we wanted to have, say, Generic2, we'd similarly need to be able to work with many more combinations of type parameter positions, such as: * data Foo1 a b = Foo1 a b * data Foo2 a b = Foo2 (Either a b) * data Foo3 a b = Foo3 (Either b a) * etc. A naïve approach would be to tack on another type parameter at the end of every representation type, and introduce more types to deal with all the combinations of the first and second type parameter that could arise. But this approach doesn't scale well—after all, at what number N do you stop introducing new representation types? So extending GHC.Generics to deal with more than one type parameter is far from obvious to me (let alone whether it could be made backwards compatible with the current API). > the GHC.Generics module looks a bit unpolished and ad-hoc at the moment. Yes, quite literally everything in GHC.Generics is one large, ad hoc hack. But it's also a darn useful one :) > It looks like there's still one confusing reference to Par0: "Note how Par0 and Rec0 both being mapped to K1 allows us to define a uniform instance here. " but at least it's not tangled up in the already very confusing examples and signatures. I think that sentence can be deleted entirely now? Indeed, an earlier part of the documentation in that module mentions that Par0 was deprecated (and removed, in fact), so we really shouldn't be mentioning it elsewhere. I'll remove that sentence. Ryan S.

2 1

Darwin Harbormaster builder down
by Ben Gamari 02 Sep '17

02 Sep '17

Hello everyone, It seems that the OS X Harbormaster builder has dropped off the face of the internet. I'm trying to get in touch with Futureice about this but in the meantime I've disabled the OS X build plan. This means that patches submitted won't be validated on OS X until this is resolved. Cheers, - Ben

1 0

Convenient URL alias for Trac tickets
by Ben Gamari 02 Sep '17

02 Sep '17

Hello everyone, Earlier today a contributor requested that we have an easier-to-remember URL for Trac tickets. Consequently, I've configured ghc.haskell.org to redirect URLs of the form, http://ghc.haskell.org/t/$n to the appropriate Trac ticket. For instance, https://ghc.haskell.org/t/14171 will bring you to the ticket for #14171. Hopefully others also will find this helpful. Cheers, - Ben

3 4

Type-level generics
by David Feuer 01 Sep '17

01 Sep '17

I've been thinking for several weeks that it might be useful to offer type-level generics. That is, along with to :: Rep a k -> a from :: a -> Rep a perhaps we should also derive type family To (r :: Rep a x) :: a type family From (v :: a) :: Rep a x This would allow us to use generic programming at the type level For example, we could write a generic ordering family: class OrdK (k :: Type) where type Compare (x :: k) (y :: k) :: Ordering type Compare (x :: k) (y :: k) = GenComp (Rep k ()) (From x) (From y) instance OrdK Nat where type Compare x y = CmpNat x y instance OrdK Symbol where type Compare x y = CmpSymbol x y instance OrdK [a] -- No implementation needed! type family GenComp k (x :: k) (y :: k) :: Ordering where GenComp (M1 i c f p) ('M1 x) ('M1 y) = GenComp (f p) x y GenComp (K1 i c p) ('K1 x) ('K1 y) = Compare x y GenComp ((x :+: y) p) ('L1 m) ('L1 n) = GenComp (x p) m n GenComp ((x :+: y) p) ('R1 m) ('R1 n) = GenComp (y p) m n GenComp ((x :+: y) p) ('L1 _) ('R1 _) = 'LT GenComp ((x :+: y) p) ('R1 _) ('L1 _) = 'GT GenComp ((x :*: y) p) (x1 ':*: y1) (x2 ':*: y2) = PComp (GenComp (x p) x1 x2) (y p) y1 y2 GenComp (U1 p) _ _ = 'EQ GenComp (V1 p) _ _ = 'EQ type family PComp (c :: Ordering) k (x :: k) (y :: k) :: Ordering where PComp 'EQ k x y = GenComp k x y PComp x _ _ _ = x For people who want to play around with the idea, here are the definitions of To and From for lists: To ('M1 ('L1 ('M1 'U1))) = '[] To ('M1 ('R1 ('M1 ('M1 ('K1 x) ':*: 'M1 ('K1 xs))))) = x ': xs From '[] = 'M1 ('L1 ('M1 'U1)) From (x ': xs) = 'M1 ('R1 ('M1 ('M1 ('K1 x) ':*: 'M1 ('K1 xs)))) David

4 4

[broken HEAD] In which the strict state monad fails at basic arithmetic
by Moritz Angermann 01 Sep '17

01 Sep '17

Hi *, while working on some related code. I came across a rather peculiar behavior with GHC built from the current master branch at b2c2e3e8. After condensing the application quite a bit[1], the test case now produces 8 with ghc 8.2.1 and -6 with ghc 8.3 @ b2c2e3e8 The sample application is essentially a strict `State Int a` monad, that is being advanced by 1 and then by another 7. ``` module Lib where import Control.Monad.Trans.State.Strict eval :: Int -> State Int a -> a eval p = fst . flip runState p advance :: Int -> State Int () advance = modify' . (+) loc :: State Int Int loc = get emit1 :: State Int () emit1 = advance 1 emitN :: Int -> State Int () -- adding in the 0 case, breaks with HEAD. 8.2.1 is fine with it. -- emitN 0 = advance 0 emitN 0 = pure () emitN n = advance n align8 :: State Int () align8 = do bits <- (`mod` 8) <$> loc emitN (8 - bits) ``` with the test driver ``` module Main where import Lib import System.Exit main :: IO () main = do let p = eval 0 (emit1 >> align8 >> loc) putStrLn $ show p if p == 8 then putStrLn "OK" >> exitSuccess else putStrLn "FAIL" >> exitFailure ``` Compiling both with ghc, will *NOT* exhibit the issue. Only when the `Lib` module is packed, and `Main` is linked against the package is the issue visible. A cabal file for this is contained in [1]. Using the following git bisect script (where [1] is in `../break` relative to ghc) ``` #!/bin/bash git submodule update --init --recursive make -s clean make -s distclean ./boot > /dev/null if ./configure --silent --disable-large-address-space && make -s -j9 then (cd ../break && rm -fR dist-newstyle && cabal new-run test -w ../ghc/inplace/bin/ghc-stage2) status=$? else status=125 fi exit $status ``` $ git bisect $PWD/bisect.sh yields: ``` 193664d42dbceadaa1e4689dfa17ff1cf5a405a0 is the first bad commit commit 193664d42dbceadaa1e4689dfa17ff1cf5a405a0 Author: Simon Peyton Jones <simonpj(a)microsoft.com> Date: Wed Mar 8 10:26:47 2017 +0000 Re-engineer caseRules to add tagToEnum/dataToTag See Note [Scrutinee Constant Folding] in SimplUtils * Add cases for tagToEnum and dataToTag. This is the main new bit. It allows the simplifier to remove the pervasive uses of case tagToEnum (a > b) of False -> e1 True -> e2 and replace it by the simpler case a > b of DEFAULT -> e1 1# -> e2 See Note [caseRules for tagToEnum] and Note [caseRules for dataToTag] in PrelRules. * This required some changes to the API of caseRules, and hence to code in SimplUtils. See Note [Scrutinee Constant Folding] in SimplUtils. * Avoid duplication of work in the (unusual) case of case BIG + 3# of b DEFAULT -> e1 6# -> e2 Previously we got case BIG of DEFAULT -> let b = BIG + 3# in e1 3# -> let b = 6# in e2 Now we get case BIG of b# DEFAULT -> let b = b' + 3# in e1 3# -> let b = 6# in e2 * Avoid duplicated code in caseRules A knock-on refactoring: * Move Note [Word/Int underflow/overflow] to Literal, as documentation to accompany mkMachIntWrap etc; and get rid of PrelRuls.intResult' in favour of mkMachIntWrap ``` I do not yet understand exactly where this goes wrong. But I hope someone else will be able to help out? I do find it curious though that this bug seems to have gone unnoticed (assuming the commit git bisect found is indeed the underlying issue) for almost half a year. And please, if my analysis is faulty at some point don’t hesitate to point that out! Cheers, Moritz PS: can we have a folder in ghc, which contains cabal packages, and part of the validation is just iterating over all those packages with `cabal new-test -w /path/to/inplace/bin/ghc-stage2`? In that case, one could simply change the executable target in [1] into a testsuite, and drop the package into that folder? — [1]: https://gist.github.com/angerman/c6ee51e4892ce6efdbcabb8c5ab990fa

4 3

Re: Type-level generics
by Ryan Scott 01 Sep '17

01 Sep '17

While we're on the topic, I'll mention that at one point I attempted to modify the singletons [1] library so that it would automatically generate promoted (i.e., type-level) and singled versions of Generic instances for any data type that derived Generic. I wasn't successful, since it turns out singletons are difficult to adapt to data types with higher-kinded types [2] and type classes with associated type families [3], but I did manage to write some examples on a very limited subset of GHC.Generics in this gist [4]. The promoted version of Generic (PGeneric) in that gist works pretty much identically to Oleg's version, but with one notable difference: I don't attempt to put the Generic laws as a superclass of PGeneric. Instead, I make the laws class methods of the singled version of Generic (SGeneric). I found it more convenient to do it this way since I needed to pattern-match on these proofs directly in a generic implementation of decidable equality, but I'm sure this isn't the only way it could be done. Speaking of which, it astounds me that the Generic laws aren't documented in the Haddocks! We really should do that. Ryan S. ----- [1] http://hackage.haskell.org/package/singletons [2] See the extended discussion in https://github.com/goldfirere/singletons/issues/150 [3] https://github.com/goldfirere/singletons/issues/198 [4] https://gist.github.com/RyanGlScott/daeb63be7885244d9882dcbb1bbc10cc

1 0

Re: dll-split
by Ryan Scott 30 Aug '17

30 Aug '17

Thanks for putting so much effort into this work, Tamar! > When I do turn it on, by default you will get a large ~45min hit in compile time. Yikes, that's really bad! Bad enough that I have to wonder: would it be worth including genlib among the other executables that we bundle with GHC? Fortunately, us GHC developers have the foresight to know that we should install genlib, but I imagine less informed Windows users probably won't get the memo and will start to wonder why compilation became so slow all of a sudden. Ryan S.

3 3

dll-split
by lonetiger＠gmail.com 29 Aug '17

29 Aug '17

Hi All, I have just killed off dll-split, this means that you no longer need to maintain a list of modules in GHC.mk. If you’re a non-Windows programmer you can stop reading here, for those that build on Windows: The replacement for dll-split is called gen-dll, and it is able to automatically partition any library we build, so this issue is hopefully solved once and for all. Currently dynamic linking is still turned off as I have a few more patches to upstream. When I do turn it on, by default you will get a large ~45min hit in compile time. This is because dlltool which BFD based is quite slow. To mitigate this gen-dll supports the use of the msys2 project’s genlib tool. This tool finishes in seconds instead of tens of minutes like dlltool. To install it just run pacman -Sy mingw-w64-$(uname -m)-tools-git The wiki pages have been updated accordingly already. If you install this now you won’t notice any difference in build time later. Thanks, Tamar

1 0

Crossreferenced GHC 8.0.2
by Robin Palotai 29 Aug '17

29 Aug '17

Hello GHC devs, I ran haskell-indexer [1] on the GHC 8.0.2 tarball, partly because I find myself reading GHC source from time to time while working on the indexer, and partly since it's fun. First, here you can click around [2] and find where beloved functions are called from: http://stuff.codereview.me/#ghc/compiler/hsSyn/HsBinds.hs?corpus&signature (scroll down a bit, imports are not linked yet). Second, the way I indexed was pretty simple. I took the output of `make`, replaced the ghc used with the ghc_kythe_wrapper, and filtered the lines which included '-c', since I noticed that those duplicate previous large compile lines. This only indexes the stage1 compilation AFAIU. Feel free to suggest a better way to tap into the compilations to get everything properly indexed (and possibly only once). Any comments welcome! Robin [1]: https://github.com/google/haskell-indexer [2]: TLDR UI quirks: - Click the :: in top-left to navigate file tree - Ctrl-Click (on linux) to go directly to definition (otherwise click stuff from bottom pane) - Bottom pane often hides content, close it if stuck.

3 7