- Generics - Haskell.org

multirec-rewriting status?
by Nicolas Frisby 01 Nov '12

01 Nov '12

Did anything ever come of this SVN repo? https://svn.science.uu.nl/repos/sci.jeuri101.libraries/Rewriting-multirec/t… Is there a reason it didn't reach hackage? Thank you for your time.

2 2

Call for Lightning Talks / Challenges, Workshop on Generic Programming 2012
by Andres Löh 04 Sep '12

04 Sep '12

-------------------------------------------------------------------------- CALL FOR LIGHTNING TALKS / CHALLENGES -------------------------------------------------------------------------- At the Workshop on Generic Programming 2012 on Sunday, September 9, 2012, we will have a discussion about OPEN PROBLEMS IN GENERIC PROGRAMMING The goal is to present and discuss one or more concrete examples where existing tools, libraries or mechanisms for generic programming in various programming languages fail. If you have the feeling that despite its promises, generic programming has failed to deliver, then this is your chance to step up and explain to the community what you would like to do, but currently cannot. We hope that this discussion will inspire the researchers within the community to work on the problems that will be proposed. If you have a challenge, please contact the workshop organizers by mail. We are offering a number of lightning talk slots to present the challenge to the audience as an introduction to the general discussion. Even if you cannot participate in the workshop, but have a challenge that is easy enough to describe, please contact us and if time permits we might try to present it. Ronald Garcia and Andres Loeh Workshop co-chairs

1 0

New scheme proposal: everythingWithContext
by Andrew Miller 19 Jun '12

19 Jun '12

Hi, One thing that is hard to do with SYB (as well as with alternative generics packages in Haskell) at present is to query while keeping state that is carried down the tree but not to siblings, and use that in deciding what to return from the query. I propose a new scheme be added to Data.Generics.Schemes, called everythingWithContext (as defined below). An everywhereWithContext might also be useful, but I don't think you would be able to define the transformation using the existing combinators, so I have limited my proposal to everythingWithContext for now. Yours Sincerely, Andrew Miller {- | Summarise all nodes in top-down, left-to-right order, carrying some state down the tree during the computation, but not left-to-right to siblings. Example: Suppose you want to compute the maximum depth of adds in the below simple co-recursive structure, ignoring all the other constructors. You could write code like the following: data MyStructure = SomeConst Int | Add MyStructure MyStructure | Times MyStructure MyStructure | Wrapped Wrapper deriving (Data, Typeable) data Wrapper = Wrapper MyStructure deriving (Data, Typeable) myExample = Add (SomeConst 10) (Add (Wrapped . Wrapper $ (Add (Add (Add (Times (SomeConst 30) (SomeConst 90)) (SomeConst 70)) (SomeConst 40)) (SomeConst 50))) (Add (SomeConst 20) (Add (SomeConst 60) (SomeConst 80)))) computeDepth = everythingWithContext 0 max ((\s -> (0, s)) `mkQ` depthOfAdd) where depthOfAdd (Add _ _) s = (s, s + 1) depthOfAdd _ s = (s, s) main = print $ computeDepth myExample -} everythingWithContext :: s -> (r -> r -> r) -> GenericQ (s -> (r, s)) -> GenericQ r everythingWithContext s0 f q x = foldl f r (gmapQ (everythingWithContext s' f q) x) where (r, s') = q x s0

2 1

Final CFP: Workshop on Generic Programming (WGP) 2012
by Andres Löh 28 May '12

28 May '12

The deadline is on Friday! Cheers, Andres

1 0

MPC2012 Call for Participation
by Jeremy.Gibbons＠cs.ox.ac.uk 24 May '12

24 May '12

CALL FOR PARTICIPATION 11th International Conference on Mathematics of Program Construction (MPC 2012) Madrid, Spain, 25-27 June 2012 http://babel.ls.fi.upm.es/mpc2012 Hotel rooms reserved until: *** 30th May 2012 *** Early registration deadline: *** 6th June 2012 *** BACKGROUND The biennial MPC conferences aim to promote the development of mathematical principles and techniques that are demonstrably practical and effective in the process of constructing computer programs, broadly interpreted. The 2012 MPC conference will be held in Madrid, Spain, from 25th to 27th June 2012. VENUE The conference will take place in Madrid, the capital of Spain, in the Sala de Grados of the Facultad de Informática of Universidad Complutense de Madrid, right in Madrid's Ciudad Universitaria (city campus), not far from the city centre and other major tourist attractions. Accommodation has been reserved in a nearby 4-star hotel, the VP Jardin Metropolitano. REGISTRATION Conference registration is now open; see http://babel.ls.fi.upm.es/mpc2012/registration.html Registration fees have been kept low thanks to a grant from the Spanish Ministerio de Economia y Competitividad. The early registration fee is €240, which includes lunches, coffees, and social events. The early registration deadline is 6th June 2012; after this point, the registration fee rises to €340. Hotel reservation is handled separately; see http://babel.ls.fi.upm.es/mpc2012/accom.html We have a block booking of rooms at the conference hotel at a special reduced rate, but only until 30th May 2012; after this point, the rooms will be released and the special rate unavailable. (There are few well-connected budget hotels in the area, and June marks the start of Spain's tourist season with a sharp rise in hotel rates; so we strongly advise you to meet this hotel registration deadline.) INVITED SPEAKERS * Gilles Barthe, IMDEA Software Institute (http://software.imdea.org/people/gilles.barthe/) "Probabilistic Relational Hoare Logics for Computer-Aided Security Proofs" * Dan Ghica, University of Birmingham (http://www.cs.bham.ac.uk/~drg/) "The Geometry of Synthesis: How to Make Hardware out of Software" * Tony Hoare, Microsoft Research (http://research.microsoft.com/en-us/people/thoare/) "The Laws of Programming Unify Process Calculi" ACCEPTED PAPERS * "Scheduler-Independent Declassification" Alexander Lux, Heiko Mantel and Matthias Perner * "Elementary Probability Theory in the Eindhoven Style" Carroll Morgan * "Scheduling and Buffer Sizing of n-Synchronous Systems: Typing of Ultimately Periodic Clocks in Lucy-n" Louis Mandel and Florence Plateau * "Deriving Real-Time Action Systems Controllers from Multiscale System Specifications" Brijesh Dongol and Ian J. Hayes * "Calculating Graph Algorithms for Dominance and Shortest Path" Ilya Sergey, Jan Midtgaard and Dave Clarke * "First-Past-the-Post Games" Roland Backhouse * "Reverse Exchange for Concurrency and Local Reasoning" Han-Hing Dang and Bernhard Möller * "Unifying Correctness Statements" Walter Guttmann * "Dependently Typed Programming based on Automated Theorem Proving" Alasdair Armstrong, Simon Foster and Georg Struth * "An Algebraic Calculus of Database Preferences" Bernhard Möller, Patrick Roocks and Markus Endres * "Modular Tree Automata" Patrick Bahr * "Constructing Applicative Functors" Ross Paterson * "Kan Extensions for Program Optimisation, Or: Art and Dan Explain an Old Trick" Ralf Hinze SOCIAL EVENTS The conference excursion will be a guided tour of Madrid's Royal Palace. The banquet will be Northern Spanish cuisine at the Sidreria-Asador Gaztemanu. PROGRAMME COMMITTEE Jeremy Gibbons University of Oxford, UK (co-chair) Pablo Nogueira Universidad Politécnica de Madrid, ES (co-chair) Ralph Back Åbo Akademi, FI Roland Backhouse University of Nottingham, UK Eerke Boiten University of Kent, UK William Cook University of Texas at Austin, US Jules Desharnais Université Laval, CA Lindsay Groves Victoria University of Wellington, NZ Ian Hayes University of Queensland, AU Ralf Hinze University of Oxford, UK Graham Hutton University of Nottingham, UK Johan Jeuring Utrecht Universiteit, NL Christian Lengauer Universität Passau, DE Larissa Meinicke University of Queensland, AU Bernhard Möller Universität Augsburg, DE Carroll Morgan University of New South Wales, AU Shin-Cheng Mu Academia Sinica, TW Dave Naumann Stevens Institute of Technology, US Jose Oliveira Universidade do Minho, PT Steve Reeves University of Waikato, NZ Wouter Swierstra Utrecht Universiteit, NL Anya Tafliovich University of Toronto Scarborough, CA LOCAL ORGANIZERS Pablo Nogueira Universidad Politécnica de Madrid Ricardo Peña Universidad Complutense de Madrid Alvaro García IMDEA Software Institute and Universidad Politécnica de Madrid Manuel Montenegro Universidad Complutense de Madrid For queries about local matters, please write to pablo(a)babel.ls.fi.upm.es.

1 0

CFP: Workshop on Generic Programming 2012 (co-located with ICFP)
by Andres Löh 07 May '12

07 May '12

====================================================================== CALL FOR PAPERS WGP 2012 8th ACM SIGPLAN Workshop on Generic Programming Copenhagen, Denmark Sunday, September 9th, 2012 http://www.wgp-sigplan.org/2012 Co-located with the International Conference on Functional Programming (ICFP 2012) ====================================================================== Goals of the workshop --------------------- Generic programming is about making programs more adaptable by making them more general. Generic programs often embody non-traditional kinds of polymorphism; ordinary programs are obtained from them by suitably instantiating their parameters. In contrast with normal programs, the parameters of a generic program are often quite rich in structure; for example they may be other programs, types or type constructors, class hierarchies, or even programming paradigms. Generic programming techniques have always been of interest, both to practitioners and to theoreticians, and, for at least 20 years, generic programming techniques have been a specific focus of research in the functional and object-oriented programming communities. Generic programming has gradually spread to more and more mainstream languages, and today is widely used in industry. This workshop brings together leading researchers and practitioners in generic programming from around the world, and features papers capturing the state of the art in this important area. We welcome contributions on all aspects, theoretical as well as practical, of * generic programming, * programming with (C++) concepts, * meta-programming, * programming with type classes, * programming with modules, * programming with dependent types, * type systems for generic programming, * polytypic programming, * adaptive object-oriented programming, * component-based programming, * strategic programming, * aspect-oriented programming, * family polymorphism, * object-oriented generic programming, * implementation of generic programming languages, * static and dynamic analyses of generic programs, * and so on. Program Committee ----------------- Anya Helene Bagge, University of Bergen Jacques Carette, McMaster University Manuel Chakravarty, University of New South Wales Ronald Garcia (co-chair), University of British Columbia Jacques Garrigue, Nagoya University Andy Gill, University of Kansas Douglas Gregor, Apple Andrew Kennedy, Microsoft Research Cambridge Neelakantan Krishnaswami, Max Planck Institute for Software Systems Andres Löh (co-chair), Well-Typed LLP Zoltan Porkolab, Eötvös Loránd University Chung-chieh Shan, University of Tsukuba Proceedings and Copyright ------------------------- We plan to have formal proceedings, published by the ACM. Authors must transfer copyright to ACM upon acceptance (for government work, to the extent transferable), but retain various rights (http://www.acm.org/publications/policies/copyright_policy) Authors are encouraged to publish auxiliary material with their paper (source code, test data, etc.); they retain copyright of auxiliary material. Submission details ------------------ Deadline for submission: Friday 2012-06-01 Notification of acceptance: Wednesday 2012-06-27 Final submission due: Tuesday 2012-07-10 Workshop: Sunday 2012-09-09 Papers should be submitted via EasyChair at https://www.easychair.org/conferences/?conf=wgp2012 Submitted papers should be in portable document format (PDF), formatted using the ACM SIGPLAN style guidelines (two-column, 9pt). The length is restricted to 12 pages. Travel Support -------------- Student attendees with accepted papers can apply for a SIGPLAN PAC grant to help cover travel expenses. PAC also offers other support, such as for child-care expenses during the meeting or for travel costs for companions of SIGPLAN members with physical disabilities, as well as for travel from locations outside of North America and Europe. For details on the PAC program, see its web page (http://www.sigplan.org/PAC.htm) History of the Workshop on Generic Programming ---------------------------------------------- Earlier Workshops on Generic Programming have been held in * Tokyo, Japan 2011 (affiliated with ICFP11), * Baltimore, Maryland, US 2010 (affiliated with ICFP10), * Edinburgh, UK 2009 (affiliated with ICFP09), * Victoria, BC, Canada 2008 (affiliated with ICFP), * Portland 2006 (affiliated with ICFP), * Ponte de Lima 2000 (affiliated with MPC), * Marstrand 1998 (affiliated with MPC). Furthermore, there were a few informal workshops * Utrecht 2005 (informal workshop), * Dagstuhl 2002 (IFIP WG2.1 Working Conference), * Nottingham 2001 (informal workshop). There were also (closely related) DGP workshops in Oxford (June 3-4 2004), and a Spring School on DGP in Nottingham (April 24-27 2006, which had a half-day workshop attached). WGP Steering Committee ---------------------- Patrik Jansson (chair) Sibylle Schupp Bruno Oliveira Marcin Zalewski Jaako Järvi Shin-Cheng Mu Jeremy Gibbons Magne Haveraaen Tim Sheard

1 0

A new Haskell wiki generics page
by José Pedro Magalhães 21 Apr '12

21 Apr '12

Hi all, I've updated the haskell wiki page for Generics [1] to mention approaches other than GHC.Generics. Please feel free to edit this page, or add more libraries. Cheers, Pedro [1] http://www.haskell.org/haskellwiki/Generics

1 0

Inlining and generic programming
by José Pedro Magalhães 14 Mar '12

14 Mar '12

Hello all, First of all, I'm sorry that this email is so absurdly long. But it's not easy to explain the problem at hand, so I took a step-by-step approach. The executive summary is: GHC can do a *great *job with inlining, but often it doesn't, and I don't understand why. So I have some questions, which are highlighted in the text below. In general, any insights regarding inlining or improving the performance of generics are welcome. My final goal is to be able to state that generic functions (in particular using GHC.Generics) will have no runtime overhead whatsoever when compared to a handwritten type-specific version. The setting Generic programming is based on representing datatypes in a uniform way using a small set of representation types. Functions defined on those representation types can then be applied to all datatypes, because we can convert between datatypes and their representations. However, generic functions tend to be slower than their specialised counterparts, because they have to deal with the conversions. But clever inlining (together with other compiler optimisations) can completely remove this overhead. The problem I'm tackling is how to tell GHC exactly what it should in the particular case of optimisation of generic code. Simplified example I'll focus on the problem of optimising a non-trivial function for generic enumeration of terms. My experience shows that GHC does quite good at optimising simple functions, especially consumers (like generic equality). But producers are trickier. First, we'll need some auxiliary functions: -- | Interleave elements from two lists. Similar to (++), but swap left and > -- right arguments on every recursive application. > -- > -- From Mark Jones' talk at AFP2008 > {-# NOINLINE (|||) #-} > (|||) :: [a] -> [a] -> [a] > [] ||| ys = ys > (x:xs) ||| ys = x : ys ||| xs > > > -- | Diagonalization of nested lists. Ensure that some elements from every > -- sublist will be included. Handles infinite sublists. > -- > -- From Mark Jones' talk at AFP2008 > {-# NOINLINE diag #-} > diag :: [[a]] -> [a] > diag = concat . foldr skew [] . map (map (\x -> [x])) > > skew :: [[a]] -> [[a]] -> [[a]] > skew [] ys = ys > skew (x:xs) ys = x : combine (++) xs ys > > combine :: (a -> a -> a) -> [a] -> [a] -> [a] > combine _ xs [] = xs > combine _ [] ys = ys > combine f (x:xs) (y:ys) = f x y : combine f xs ys > The particular implementation of these functions doesn't really matter. What's important is that we have a way to interleave lists (|||) and a way to diagonalise a matrix into a list (diag). We mark these functions as NOINLINE because inlining them will only make the core code more complicated (and may prevent rules from firing). Suppose we have a type of Peano natural numbers: data Nat = Ze | Su Nat deriving Eq > Implementing enumeration on this type is simple: enumNat :: [Nat] > enumNat = [Ze] ||| map Su enumNat > Now, a generic representation of Nat in terms of sums and products could look something like this: type RepNat = Either () Nat > That is, either a singleton (for the Ze case) or a Nat (for the Su case). Note that I am building a shallow representation, since at the leaves we have Nat, and not RepNat. This mimics the situation with current generic programming libraries (in particular GHC.Generics). We'll need a way to convert between RepNat and Nat: toNat :: RepNat -> Nat > toNat (Left ()) = Ze > toNat (Right n) = Su n > > fromNat :: Nat -> RepNat > fromNat Ze = Left () > fromNat (Su n) = Right n > (In fact, since we're only dealing with a generic producer we won't need the fromNat function.) To get an enumeration for RepNat, we first need to know how to enumerate units and sums: enumU :: [()] > enumU = [()] > > enumEither :: [a] -> [b] -> [Either a b] > enumEither ea eb = map Left ea ||| map Right eb > Now we can define an enumeration for RepNat: enumRepNat :: [RepNat] > enumRepNat = enumEither enumU enumNatFromRep > With the conversion function toNat, we can use enumRepNat to get an enumeration for Nat directly: enumNatFromRep :: [Nat] > enumNatFromRep = map toNat enumRepNat > First, convince yourself that enumNatFromRep and enumNat are equivalent functions: take 100 enumNat == take 100 enumNatFromRep > Now, what I want is that enumNatFromRep generates the same core code as enumNat. That should be possible; here are the necessary steps: map toNat enumRepNat > > == { inline enumRepNat } > > map toNat (enumEither enumU enumNatFromRep) > > == { inline enumEither } > > map toNat (map Left enumU ||| map Right enumNatFromRep) > > == { inline enumU } > > map toNat (map Left [()] ||| map Right enumNatFromRep) > > == { inline map } > > map toNat ([Left ()] ||| map Right enumNatFromRep) > > == { free theorem (|||): forall f a b. map f (a ||| b) = map f a ||| map f > b } > > map toNat [Left ()] ||| map toNat (map Right enumNatFromRep) > > == { inline map } > > [toNat (Left ())] ||| map toNat (map Right enumNatFromRep) > > == { definition of toNat (or inline toNat + case of constant) } > > [Ze] ||| map toNat (map Right enumNatFromRep) > > == { functor composition law: forall f g l. map f (map g l) = map (f . g) > l } > > [Ze] ||| map (toNat . Right) enumNatFromRep > > == { definition of toNat (or inline toNat + case of constant) } > > [Ze] ||| map Su enumNatFromRep > Now let's see what the compiler generates. I'm using GHC-7.4.1. Let's compile with -O1 and use -ddump-simpl to see the final simplifier output (core code) for enumNatFromRep: EnumAlone.enumNatFromRep :: [EnumAlone.Nat] > [GblId, > Str=DmdType, > Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=0, Value=False, > ConLike=False, Cheap=False, Expandable=False, > Guidance=IF_ARGS [] 30 0}] > EnumAlone.enumNatFromRep = > GHC.Base.map > @ EnumAlone.RepNat > @ EnumAlone.Nat > EnumAlone.toNat > EnumAlone.enumRepNat > > EnumAlone.enumRepNat [Occ=LoopBreaker] :: [EnumAlone.RepNat] > [GblId, Str=DmdType] > EnumAlone.enumRepNat = > EnumAlone.||| > @ (Data.Either.Either () EnumAlone.Nat) lvl4_rvV lvl5_rvW > Ah, it didn't even inline enumRepNat because it made it a loop breaker. We certainly want to inline it, so let's add a pragma: {-# INLINE enumRepNat #-} > Recompiling, we get: EnumAlone.enumRepNat [InlPrag=INLINE (sat-args=0)] > :: [EnumAlone.RepNat] > [GblId, > Str=DmdType, > Unf=Unf{Src=InlineStable, TopLvl=True, Arity=0, Value=False, > ConLike=False, Cheap=False, Expandable=False, > Guidance=ALWAYS_IF(unsat_ok=False,boring_ok=False) > Tmpl= EnumAlone.enumEither > @ () @ EnumAlone.Nat EnumAlone.enumU > EnumAlone.enumNatFromRep}] > EnumAlone.enumRepNat = > EnumAlone.||| > @ (Data.Either.Either () EnumAlone.Nat) lvl4_rvV lvl5_rvW > > EnumAlone.enumNatFromRep [Occ=LoopBreaker] :: [EnumAlone.Nat] > [GblId, Str=DmdType] > EnumAlone.enumNatFromRep = > GHC.Base.map > @ EnumAlone.RepNat > @ EnumAlone.Nat > EnumAlone.toNat > EnumAlone.enumRepNat > So no real difference in the generated code, other than the reassignment of loop breakers. For some reason enumRepNat still doesn't get inlined. *Question: why won't GHC inline enumRepNat, even when I tell it to do so with an INLINE pragma?* Well, let's inline it ourselves, then. We redefine enumNatFromRep to: enumNatFromRep = map toNat (enumEither enumU enumNatFromRep) > This however doesn't help much. We get the following core: lvl6_rw5 :: [Data.Either.Either () EnumAlone.Nat] > [GblId] > lvl6_rw5 = > EnumAlone.||| > @ (Data.Either.Either () EnumAlone.Nat) lvl4_rw3 lvl5_rw4 > > EnumAlone.enumNatFromRep [Occ=LoopBreaker] :: [EnumAlone.Nat] > [GblId, Str=DmdType] > EnumAlone.enumNatFromRep = > GHC.Base.map > @ EnumAlone.RepNat @ EnumAlone.Nat EnumAlone.toNat lvl6_rw5 > GHC is really keen on floating that (|||) out. Let's be very explicit about inlining: {-# INLINE toNat #-} > {-# INLINE enumU #-} > {-# INLINE enumEither #-} > Also, maybe it's floating it out because it doesn't have anything else to do to it. Let's add the free theorem of (|||) as a rule: {-# RULES "ft |||" forall f a b. map f (a ||| b) = map f a ||| map f b #-} > We needed this in our manual derivation, so GHC should need it too. Recompiling, we see we've made some progress: lvl5_ryv :: [Data.Either.Either () EnumAlone.Nat] > [GblId] > lvl5_ryv = > GHC.Base.map > @ EnumAlone.Nat > @ (Data.Either.Either () EnumAlone.Nat) > (Data.Either.Right @ () @ EnumAlone.Nat) > EnumAlone.enumNatFromRep > > lvl6_ryw :: [EnumAlone.Nat] > [GblId] > lvl6_ryw = > GHC.Base.map > @ (Data.Either.Either () EnumAlone.Nat) > @ EnumAlone.Nat > EnumAlone.toNat > lvl5_ryv > > EnumAlone.enumNatFromRep [Occ=LoopBreaker] :: [EnumAlone.Nat] > [GblId, Str=DmdType] > EnumAlone.enumNatFromRep = > EnumAlone.||| @ EnumAlone.Nat lvl4_ryu lvl6_ryw > enumNatFromRep finally starts with (|||) directly. But its second argument, lvl6_ryw, is a map of lvl5_ryv, which is itself a map! At this stage I expected GHC to be aware of the fusion law for map, but it seems that it isn't. *Question: why is map fusion not happening automatically?* Let's add it as a rule: {-# RULES "map/map1" forall f g l. map f (map g l) = map (f . g) l #-} > And now we're in a much better situation: lvl3_ryD :: [Data.Either.Either () EnumAlone.Nat] > [GblId, Caf=NoCafRefs] > lvl3_ryD = > GHC.Types.: > @ (Data.Either.Either () EnumAlone.Nat) > EnumAlone.fromNat1 > (GHC.Types.[] @ (Data.Either.Either () EnumAlone.Nat)) > > lvl4_ryE :: [EnumAlone.Nat] > [GblId] > lvl4_ryE = > GHC.Base.map > @ (Data.Either.Either () EnumAlone.Nat) > @ EnumAlone.Nat > EnumAlone.toNat > lvl3_ryD > > lvl5_ryF :: [EnumAlone.Nat] > [GblId] > lvl5_ryF = > GHC.Base.map > @ EnumAlone.Nat > @ EnumAlone.Nat > EnumAlone.Su > EnumAlone.enumNatFromRep > > EnumAlone.enumNatFromRep [Occ=LoopBreaker] :: [EnumAlone.Nat] > [GblId, Str=DmdType] > EnumAlone.enumNatFromRep = > EnumAlone.||| @ EnumAlone.Nat lvl4_ryE lvl5_ryF > Note how toNat is entirely gone from the second part of the enumeration (lvl5_ryF). Strangely enough, the enumerator for Ze (lvl4_ryE) is still very complicated: map toNat ([Left ()]). Why doesn't GHC simplify this to just [Ze]? Apparently because GHC doesn't simplify map over a single element list. *Question: why doesn't GHC optimise map f [x] to [f x]?* Let's tell it to do so: {-# RULES "map/map2" forall f x. map f (x:[]) = (f x):[] #-} > Now we're finally where we wanted: lvl_ryA :: [EnumAlone.Nat] > [GblId, Caf=NoCafRefs] > lvl_ryA = > GHC.Types.: > @ EnumAlone.Nat EnumAlone.Ze (GHC.Types.[] @ EnumAlone.Nat) > > lvl3_ryD :: [EnumAlone.Nat] > [GblId] > lvl3_ryD = > GHC.Base.map > @ EnumAlone.Nat > @ EnumAlone.Nat > EnumAlone.Su > EnumAlone.enumNatFromRep > > EnumAlone.enumNatFromRep [Occ=LoopBreaker] :: [EnumAlone.Nat] > [GblId, Str=DmdType] > EnumAlone.enumNatFromRep = > EnumAlone.||| @ EnumAlone.Nat lvl_ryA lvl3_ryD > This is what I wanted: no more representation types (Either or ()), and the code looks exactly like what is generated for the handwritten enumNat. More realistic generic programming Now let's see if we can transport this to the setting of a generic programming library. I'll use a bare-bones version of GHC.Generics: infixr 5 :+: > infixr 6 :*: > > data U = U deriving (Show, Read) > data a :+: b = L a | R b deriving (Show, Read) > data a :*: b = a :*: b deriving (Show, Read) > newtype Var a = Var a deriving (Show, Read) > newtype Rec a = Rec a deriving (Show, Read) > > class Representable a where > type Rep a > to :: Rep a -> a > from :: a -> Rep a > Let's represent Nat in this library: instance Representable Nat where > type Rep Nat = U :+: (Rec Nat) > from Ze = L U > from (Su n) = R (Rec n) > to (L U) = Ze > to (R (Rec n)) = Su n > (Note, in particular, that we do not need INLINE pragmas on the from/to methods. This might just be because GHC thinks these are small and inlines them anyway, but in general we want to make sure they are inlined, so we typically use pragmas there.) Now we need to implement enumeration generically. We do this by giving an instance for each representation type: class GEnum' a where > genum' :: [a] > > instance GEnum' U where > {-# INLINE genum' #-} > genum' = [U] > > instance (GEnum a) => GEnum' (Rec a) where > {-# INLINE genum' #-} > genum' = map Rec genum > > instance (GEnum a) => GEnum' (Var a) where > {-# INLINE genum' #-} > genum' = map Var genum > > instance (GEnum' f, GEnum' g) => GEnum' (f :+: g) where > {-# INLINE genum' #-} > genum' = map L genum' ||| map R genum' > > instance (GEnum' f, GEnum' g) => GEnum' (f :*: g) where > {-# INLINE genum' #-} > --genum' = diag [ [ x :*: y | y <- genum' ] | x <- genum' ] > genum' = diag (map (\x -> map (\y -> x :*: y) genum') genum') > We explicitly tell GHC to inline each case, as before. Note that for products I'm not using the more natural list comprehension syntax because I don't quite understand how that gets translated into core. In the cases for Var and Rec we use genum from the GEnum class: class GEnum a where > genum :: [a] > {-# INLINE genum #-} > default genum :: (Representable a, GEnum' (Rep a)) => [a] > genum = map to genum' > GEnum' is the class used for instantiating the generic representation types, and GEnum is used for user types. We use a default signature to provide a default method that can be used when we have a Representable instance for the type in question. This makes instantiating Nat very easy: instance GEnum Nat > Unfortunately, the core code generated in this situation (with the same RULES as before) is not nice at all: Main.$fGEnumNat_$cgenum [Occ=LoopBreaker] :: [Base.Nat] > [GblId, Str=DmdType] > Main.$fGEnumNat_$cgenum = > GHC.Base.map > @ (Base.Rep Base.Nat) > @ Base.Nat > Base.$fRepresentableNat_$cto > (lvl37_r79y > `cast` (Sym (GEnum.NTCo:GEnum') <Base.U Base.:+: (Base.Rec Base.Nat)> > ; > (GEnum.GEnum' (Sym > (Base.TFCo:R:RepNat)) ; > GEnum.NTCo:GEnum' <Base.Rep > Base.Nat>) > :: [Base.C Base.Nat_Ze_ Base.U > Base.:+: Base.C Base.Nat_Su_ (Base.Rec Base.Nat)] > ~# > [Base.Rep Base.Nat])) > We see a map of the `to` function, which is definitely not what we want. Oddly enough, if we give an explicit definition of genum for Nat, with the inlined default... instance GEnum Nat where genum = map to genum' > ... then we get the optimised code we want: lvl34_r79p :: [Base.Nat] > [GblId, Caf=NoCafRefs] > lvl34_r79p = > GHC.Types.: @ Base.Nat Base.Ze (GHC.Types.[] @ Base.Nat) > > lvl35_r79q :: [Base.Nat] > [GblId] > lvl35_r79q = > GHC.Base.map @ Base.Nat @ Base.Nat Base.Su Main.$fGEnumNat_$cgenum > > Main.$fGEnumNat_$cgenum [Occ=LoopBreaker] :: [Base.Nat] > [GblId, Str=DmdType] > Main.$fGEnumNat_$cgenum = > GEnum.||| @ Base.Nat lvl34_r79p lvl35_r79q > Again, no representation types, no `to`, just the same code that is generated for enumNat. Perfect. But we had to avoid using the default definition, which is a pity. *Question: why won't GHC inline the default method of a class, even when I have a pragma telling it to do so?* Let's look at one more datatype, because Nat does not use products. So let's consider trees: data Tree a = Leaf | Bin a (Tree a) (Tree a) > > instance Representable (Tree a) where > type Rep (Tree a) = U :+: (Var a :*: Rec (Tree a) :*: Rec (Tree a)) > from (Bin x l r) = R (Var x :*: Rec l :*: Rec r) > from Leaf = L U > to (R (Var x :*: (Rec l) :*: (Rec r))) = Bin x l r > to (L U) = Leaf > We give a GEnum instance using the same trick as before: instance GEnum (Tree Int) where genum = map to genum' > (For simplicity only for trees of integers.) The generated code for trees is unfortunately not as nice: a2_r79M > :: [Base.Rec (Base.Tree GHC.Types.Int) > Base.:*: Base.Rec (Base.Tree GHC.Types.Int) > [GblId, Str=DmdType] > a2_r79M = > GEnum.diag > @ (Base.Rec (Base.Tree GHC.Types.Int) > Base.:*: Base.Rec (Base.Tree GHC.Types.Int)) > lvl8_r79L > > lvl9_r79N :: [Base.Tree GHC.Types.Int] > [GblId] > lvl9_r79N = > GHC.Base.map > @ (Base.Rec (Base.Tree GHC.Types.Int) > Base.:*: Base.Rec (Base.Tree GHC.Types.Int)) > @ (Base.Tree GHC.Types.Int) > lvl5_r79H > a2_r79M > > Main.$fGEnumTree_$cgenum [Occ=LoopBreaker] > :: [Base.Tree GHC.Types.Int] > [GblId, Str=DmdType] > Main.$fGEnumTree_$cgenum = > GEnum.||| @ (Base.Tree GHC.Types.Int) lvl4_r79G lvl9_r79N > Note how lvl9_r79N is a map over a2_r79M, and a2_r79M is a `diag`. Ok, we need the free theorem of `diag` to tell GHC how to commute the `diag` with map: {-# RULES "ft/diag" forall f l. map f (diag l) = diag (map (map f) l) #-} > Unfortunately this doesn't change the generated core code. With some more debugging looking at the generated code at each simplifier iteration, I believe that this is because a2_r79M got lifted out too soon, prevent the rule from applying. With some imagination I decided to try the -fno-full-laziness flag to prevent let-floating. I'm not sure this is a good idea in general, but in this particular case it gives much better results: a1_r72i :: [Base.Rec (Base.Tree GHC.Types.Int) > [GblId, Str=DmdType] > a1_r72i = > GHC.Base.map > @ (Base.Tree GHC.Types.Int) > @ (Base.Rec (Base.Tree GHC.Types.Int)) > ((\ (tpl_B1 :: Base.Tree GHC.Types.Int) -> tpl_B1) > `cast` (<Base.Tree GHC.Types.Int> > -> Sym (Base.NTCo:Rec <Base.Tree GHC.Types.Int>) > :: (Base.Tree GHC.Types.Int -> Base.Tree GHC.Types.Int) > ~# > (Base.Tree GHC.Types.Int -> Base.Rec (Base.Tree > GHC.Types.Int)))) > Main.$fGEnumTree_$cgenum > > Main.$fGEnumTree_$cgenum [Occ=LoopBreaker] > :: [Base.Tree GHC.Types.Int] > [GblId, Str=DmdType] > Main.$fGEnumTree_$cgenum = > GEnum.||| > @ (Base.Tree GHC.Types.Int) > (GHC.Types.: > @ (Base.Tree GHC.Types.Int) > (Base.Leaf @ GHC.Types.Int) > (GHC.Types.[] @ (Base.Tree GHC.Types.Int))) > (GEnum.diag > @ (Base.Tree GHC.Types.Int) > (GHC.Base.map > @ (Base.Rec (Base.Tree GHC.Types.Int)) > @ [Base.Tree GHC.Types.Int] > (\ (x_a1yQ :: Base.Rec (Base.Tree GHC.Types.Int)) -> > GHC.Base.map > @ (Base.Rec (Base.Tree GHC.Types.Int)) > @ (Base.Tree GHC.Types.Int) > (\ (x1_X1zB :: Base.Rec (Base.Tree GHC.Types.Int)) -> > Base.Bin > @ GHC.Types.Int > a_r72h > (x_a1yQ > `cast` (Base.NTCo:Rec <Base.Tree GHC.Types.Int> > :: Base.Rec (Base.Tree GHC.Types.Int) ~# > Base.Tree GHC.Types.Int)) > (x1_X1zB > `cast` (Base.NTCo:Rec <Base.Tree GHC.Types.Int> > :: Base.Rec (Base.Tree GHC.Types.Int) ~# > Base.Tree GHC.Types.Int))) > a1_r72i) > a1_r72i)) > Note how our enum is now of the shape `[Leaf] ||| diag y`, which is good. The only catch is that there are some `Rec`s still laying around, with their associated newtype coercions, and a function a1_r72i that basically wraps the recursive enumeration in a Rec, only to be unwrapped in the body of `$fGEnumTree_$cgenum`. I don't know how to get GHC to simplify this code any further. *Question: why do I need -fno-full-laziness for the ft/diag rule to apply?* *Question: why is GHC not getting rid of the Rec newtype in this case?* I have also played with -O2, in particular because of the SpecConstr optimisation, but found that it does not affect these particular examples (perhaps it only becomes important with larger datatypes). I have also experimented with phase control in the rewrite rules and the inline pragmas, but didn't find it necessary for this example. In general, anyway, my experience with the inliner is that it is extremely fragile, especially across different GHC versions, and it's hard to get any guarantees of optimisation. I have also played with the -funfolding-* options before, with mixed results. [1] It's also a pity that certain flags are not explained in detail in the user's manual [2,3], like -fliberate-case, and -fspec-constr-count and threshold, for instance. Thank you for reading this. Any insights are welcome. In particular, I'm wondering if I might be missing some details regarding strictness. Cheers, Pedro [1] http://dreixel.net/research/pdf/ogie.pdf [2] http://www.haskell.org/ghc/docs/latest/html/users_guide/flag-reference.html [3] http://www.haskell.org/ghc/docs/latest/html/users_guide/options-optimise.ht…

2 3

Generics and data families
by Reiner Pope 14 Mar '12

14 Mar '12

Hi all, The DeriveGeneric language extension in ghc 7.4 does not support data families, so the following will not compile: > data family D a > data instance D Int = DInt deriving Generic > data instance D Bool = DBool deriving Generic On http://hackage.haskell.org/trac/ghc/ticket/5936, I provided a patch for ghc which makes the above compile, giving the (approximately) the following instances for Rep and Generic: > type instance Rep (D Int) = D1 DIntInfo_D (C1 DIntInfo_C U1) > type instance Rep (D Bool) = D1 DBoolInfo_D (C1 DBoolInfo_C U1) > > instance Generic (D Int) where ... > instance Generic (D Bool) where ... Note in particular that D Int and D Bool are considered completely distinct types as far as generics are concerned. Is this the right approach to take to handle generics for data families? Are there alternative approaches? On the Trac ticket linked above, Pedro suggested we discuss these questions here. Regards, Reiner

2 2

CFP: Workshop on Generic Programming 2012
by Andres Loeh 29 Feb '12

29 Feb '12

====================================================================== CALL FOR PAPERS WGP 2012 8th ACM SIGPLAN Workshop on Generic Programming Copenhagen, Denmark Sunday, September 9th, 2012 http://www.wgp-sigplan.org/2012 Co-located with the International Conference on Functional Programming (ICFP 2012) ====================================================================== Goals of the workshop --------------------- Generic programming is about making programs more adaptable by making them more general. Generic programs often embody non-traditional kinds of polymorphism; ordinary programs are obtained from them by suitably instantiating their parameters. In contrast with normal programs, the parameters of a generic program are often quite rich in structure; for example they may be other programs, types or type constructors, class hierarchies, or even programming paradigms. Generic programming techniques have always been of interest, both to practitioners and to theoreticians, and, for at least 20 years, generic programming techniques have been a specific focus of research in the functional and object-oriented programming communities. Generic programming has gradually spread to more and more mainstream languages, and today is widely used in industry. This workshop brings together leading researchers and practitioners in generic programming from around the world, and features papers capturing the state of the art in this important area. We welcome contributions on all aspects, theoretical as well as practical, of * generic programming, * programming with (C++) concepts, * meta-programming, * programming with type classes, * programming with modules, * programming with dependent types, * type systems for generic programming, * polytypic programming, * adaptive object-oriented programming, * component-based programming, * strategic programming, * aspect-oriented programming, * family polymorphism, * object-oriented generic programming, * implementation of generic programming languages, * static and dynamic analyses of generic programs, * and so on. Program Committee ----------------- Anya Helene Bagge, University of Bergen Jacques Carette, McMaster University Manuel Chakravarty, University of New South Wales Ronald Garcia (co-chair), University of British Columbia Jacques Garrigue, Nagoya University Andy Gill, University of Kansas Douglas Gregor, Apple Andrew Kennedy, Microsoft Research Cambridge Neelakantan Krishnaswami, Max Planck Institute for Software Systems Andres Löh (co-chair), Well-Typed LLP Zoltan Porkolab, Eötvös Loránd University Chung-chieh Shan, University of Tsukuba Proceedings and Copyright ------------------------- We plan to have formal proceedings, published by the ACM. Authors must transfer copyright to ACM upon acceptance (for government work, to the extent transferable), but retain various rights (http://www.acm.org/publications/policies/copyright_policy) Authors are encouraged to publish auxiliary material with their paper (source code, test data, etc.); they retain copyright of auxiliary material. Submission details ------------------ Deadline for submission: Friday 2012-06-01 Notification of acceptance: Wednesday 2012-06-27 Final submission due: Tuesday 2012-07-10 Workshop: Sunday 2012-09-09 Papers should be submitted via EasyChair at https://www.easychair.org/conferences/?conf=wgp2012 Submitted papers should be in portable document format (PDF), formatted using the ACM SIGPLAN style guidelines (two-column, 9pt). The length is restricted to 12 pages. Travel Support -------------- Student attendees with accepted papers can apply for a SIGPLAN PAC grant to help cover travel expenses. PAC also offers other support, such as for child-care expenses during the meeting or for travel costs for companions of SIGPLAN members with physical disabilities, as well as for travel from locations outside of North America and Europe. For details on the PAC program, see its web page (http://www.sigplan.org/PAC.htm) History of the Workshop on Generic Programming ---------------------------------------------- Earlier Workshops on Generic Programming have been held in * Tokyo, Japan 2011 (affiliated with ICFP11), * Baltimore, Maryland, US 2010 (affiliated with ICFP10), * Edinburgh, UK 2009 (affiliated with ICFP09), * Victoria, BC, Canada 2008 (affiliated with ICFP), * Portland 2006 (affiliated with ICFP), * Ponte de Lima 2000 (affiliated with MPC), * Marstrand 1998 (affiliated with MPC). Furthermore, there were a few informal workshops * Utrecht 2005 (informal workshop), * Dagstuhl 2002 (IFIP WG2.1 Working Conference), * Nottingham 2001 (informal workshop). There were also (closely related) DGP workshops in Oxford (June 3-4 2004), and a Spring School on DGP in Nottingham (April 24-27 2006, which had a half-day workshop attached). WGP Steering Committee ---------------------- Patrik Jansson (chair) Sibylle Schupp Bruno Oliveira Marcin Zalewski Jaako Järvi Shin-Cheng Mu Jeremy Gibbons Magne Haveraaen Tim Sheard

1 0