October 2006 - Haskell-prime

proposal: introduce lambda-match (explicit match failure and fall-through)
by Claus Reinke 20 Nov '06

20 Nov '06

name: introduce lambda-match (explicit match failure and fall-through) summary: Haskell 98 provides *two different translations* of lambda abstractions involving pattern matching, only one of which is directly accessible (Section 3.3 - the other is embedded in the translation of do-notation, see "ok" in Section 3.14). providing explicit source notation for the second translation, substantially simplifies programmability of pattern-match fall-through by reification of pattern-match failure, two central language features that are so far only available through the built-in, non-composable case construct. what: in Section 3.3, the translation for conventional lambda abstractions with patterns is given as [| \p1 .. pn-> e |] = \x1 .. xn-> case (x1,..,xn) of (p1,..,pn) -> e with xi fresh identifiers, and pattern-match failure resulting in _|_. the latter is unfortunate, and results in partial functions the coverage of which cannot be combined, but it is forced by translation into conventional lambda calculus. since computational lambda calculus (\-M) has become a central part of Haskell programming practice, there shall be an alternative form of lambda abstraction, dubbed here lambda-match, with associated translation into \-M: [| |p1 .. pn-> e |] = \x1 .. xn-> case (x1,..,xn) of { (p1,..,pn) -> return e; _ -> fail "no match" } [note1: this is the translation in principle - in practice, to enable composition of lambda-matches without further language extensions, a slight modification is needed, wrapping the right-hand sides of the case in a Match constructor, see library and patch] a library for composing these lambda-matches shall provide for composition of alternative lambda-matches (+++), match failure (nomatch) and embedding of the explicit match monad into pure expressions (splice, where "splice |p1..pn->e = \p1..pn->e"). [note2: an alternative translation would use do-notation instead of case as the target: [| |p1 .. pn-> e |] = \x1 .. xn-> do { (p1,..,pn) <- return (x1,..,xn); return e } both translations easily accomodate guards and pattern guards as well, the former by building on existing support for these two features in case constructs, the latter without requiring any previous implementation of pattern guards, by lifting (pattern) guards into the match monad] implementation impact: minimal - limited to an extension in parser/desugarer, employing previously inaccessible syntax for lambda-match, and a slight variation of the existing lambda translation; also adds a small library to support composition of matches. [note3: a first draft of the composition library and a patch for GHC (about a dozen new lines in the parser) are provided as attachments to this proposal, together with some examples] context: as has been pointed out in the thread on replacing and improving pattern guards, Haskell's pattern matching support, even before pattern guards, is monolithic (built-in case is the only way to handle multiple alternative matches) rather than compositional (lambdas represent individual alternatives, but cannot be composed on match fall-through). this implies increased complexity of the language definition and limited expressiveness of its features, when compared with alternative models (eg, adapting Wolfram's pattern match calculus for Haskell). see, eg.: http://www.haskell.org/pipermail/haskell-prime/2006-October/001713.html http://www.haskell.org/pipermail/haskell-prime/2006-October/001720.html http://www.haskell.org/pipermail/haskell-prime/2006-October/001723.html http://www.haskell.org/pipermail/haskell-prime/2006-October/001724.html in principle, replacing Haskell's current pattern matching support with a simpler, more compositional model, and defining the current constructs on top of that new core is the way forward, IMHO. in practice, however, I suspect that the committee is less than tempted to introduce such a substantial simplification for Haskell'. the present proposal is an attempt at a compromise, suggesting a minimal language change to introduce compositional pattern-match failure and fall-through. with lambda-match, it implements only a single language extension (as syntactic sugar), delegating the rest of the functionality to a library. without the sugar, the result of the by-hand translation becomes so hard to read as to be near unusable, while the chosen form of sugaring allows to provide most of the language features discussed in the earlier threads to be provided as a library. this does seem to be a useable balance. building constructs of the simpler pattern-match model on top of the more complex one is somewhat irksome from a language design perspective, but does at least gain the expressiveness of the simpler model. if programmers make substantial use of this new functionality in Haskell' (as I strongly suspect they will - I have been doing similar translations by hand for some time now), it will be up to Haskell'' to turn the table, and to define the current complex model on top of a compositional one. as a preview of this anticipated language refactoring;), it is instructive to compare the two alternative translations of lambda-match sketched above: - the first directly builds on the existing, complex case constructs with their built-in (pattern) guards and match fall-through support; this eases adding the new, simpler features to implementations that support the old, complex ones (like GHC), but completely foregoes any attempt to simplify those implementations in the process; [the attached patch for GHC follows this route] - the second translation avoids any direct reference to case, employing do-notation instead; this requires slightly more effort, eg. in translating pattern guards into the match monad, but is eminently suitable for adding the new features to implementations that do not support pattern guards yet, or that simply want to reduce the number of built-in constructs. [patchers for Hugs, etc., might want to follow this route?]

2 4

lambda-match vs PMC
by Claus Reinke 07 Nov '06

07 Nov '06

It is encouraging that separate groups have come to similar approaches wrt to more modular pattern match facilities (though perhaps it isn't all that surprising, eg, my own musings on this topic started after one of the early functional logic programming high periods, in the early 1990s, and have since been shaped by the developments in monadic and type class programming in Haskell; PMC seems to have come from a rewriting background, shaped by monadic semantics and type theory; these would imply the same influences, moderated via different communities?). There are, however, some differences that might be worth further inspection. Referring to http://www.cas.mcmaster.ca/~kahl/PMC/ , and especially to the MPC 2006 paper, in no particular order, with no claim to completeness (and please read comments like "odd" as purely subjective, reflecting only my personal reactions as I'm trying to figure out the relation!-): - matchings are not first-class expressions in PMC the only syntactically correct way to mention a matching in an expression is inside a splice ( {| match |} ). this is fairly surprising given the aims of PMC, as one would expect operations on matchings, matchings as parameters and results of functions, etc. .. until one notices that not only the operations on matchings, but - *all* the interesting action in PMC is at the level of matchings, not at the level of expressions lambda-abstraction doesn't even exist at expression level, but is replaced by spliced matching; application exists, but is not needed, because (f e) = {| e |> {| f |} |} (unless I'm mistaken?) if one eliminated the oddity of having two applications, but only one abstraction, the category of expressions would be nearly empty, apart from constructor terms, and the separation of expressions and matchings seems needed only to support conversions between the two: {| _ |} :: Match -> Expression ^ _ ^ :: Expression -> Match which directly brings up the next oddity, in that there are no such types in PMC: - the difference between matchings and expressions is maintained in the typing contexts/labels, not in the types in spite of the monadic semantics, there are no monads in the type system, and instead of .. |- pattern |> match :: a -> m b (as Haskellers might expect to see), one has .. |M- pattern |> match :: a -> b I was looking into these details because I was trying to compare lambda-match and PMC, and while most of the differences seemed merely cosmetic at first, the one difference I couldn't account for was that PMC examples seemed to imply an implicit flattening of the monadic type structure, whereas I had to join nested lambda-matches explicitly (I would find the ability to join nested matchings quite useful on occasion, but I fail to see how this could be done implicitly/ automatically, unless by giving up the ability to express nested matches). if I now understand all these items correctly in combination, PMC is a flattened monadic framework, ie., one cannot even construct the equivalent of a ( <nested> :: m (m a))? or am I missing the obvious?-) cheers, claus ps. after reading the MPC 2006 paper, I have to support the referees' recommendation: as one of many who only occasionally dive into the most shallow parts of category theory, I don't find the monadic semantics in its current presentation helpful. A "running commentary" in computational lambda-calculus, as apparently suggested by the referees, would have made all the difference (I think, because that kind of presentation usually translates easily into Haskell;-). As it stands, I fear you are limiting your audience needlessly. -- <interactive>:1:0:-) Couldn't match `Categories' against `Haskell' Expected type: Haskell Inferred type: Categories In the first argument of `readPaper', namely `PMC_MPC2006' In the definition of `it' : it = readPaper PMC_MPC2006

2 3

Re: Proposal for stand-alone deriving declarations?
by John Hughes 03 Nov '06

03 Nov '06

What I implemented in GHC is an extension of the proposal below. The proposal just mentions: deriving Class for Type In GHC I also added a form for newtype deriving of multi-parameter type classes: deriving (Class t1 ... tn) for Type I think that it's close to what we ended up with when talking about it at the Hackathon. My intuition about this syntax is that except for the "for Type" part, it looks the same as a normal deriving clause. The "for" part is just there to connect it to a data/newtype declaration. This lets it pretty much use the normal code for deriving declarations. Stand-alone deriving declarations are currently a little bit weaker than normal deriving clauses, since the current implementation does not let you reference the type arguments of a newtype in the arguments of an MPTC. See my response to Bulat on cvs-ghc(a)haskell.org for more details. /Björn > > > A suggestion re syntax: With the newtype-deriving extension, the instances named in a deriving clause are not just class names, but partial applications of class names to all but the last argument. Why all but the last one? Because the last one is the type being defined. Once deriving clauses are separated from type definitions, then there is no type being defined any more--hence the need for "for Type" in your syntax, and the introduction of another keyword. But why single out one class parameter, once deriving clauses are separated from type definitions? Why not simply write the FULL application of the class in the deriving list? Thus: deriving (Eq Foo, Ord Foo) instead of deriving (Eq, Ord) for Foo I find the former syntax clearer and more readable, actually. John

10 20

Re[2]: [Hugs-users] Record puns, time for removal?
by Bulat Ziganshin 01 Nov '06

01 Nov '06

Hello Simon, Monday, October 30, 2006, 3:11:23 PM, you wrote: > I always thought it was a mistake to remove record puns in H98. I would > not be against re-introducing them into GHC, since they appear to remain > in Hugs and are in Yhc. what you (and all) think about wildcarded puns: data Command = Command { cmd_name :: !String , cmd_arcspec :: String , cmd_arclist :: [FilePath] , cmd_arcname :: FilePath , cmd_arc_filter :: !(FileInfo -> Bool) , cmd_filespecs :: ![String] , cmd_added_arcnames :: !(IO [FilePath]) , cmd_diskfiles :: !(IO [FileInfo]) , cmd_subcommand :: !Bool .... } process_cmd (Command{*}) = do print cmd_name ... because Haskell encourage using of structure name as part of field's name, this will not create mess (at least for my programs), it will work like Pascal's 'with' operator -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

2 3

Indentation of If-Then-Else
by Henning Thielemann 30 Oct '06

30 Oct '06

I object strongly to the proposal http://hackage.haskell.org/trac/haskell-prime/wiki/DoAndIfThenElse because it solves problems with syntactic sugar with even more sugar, where no sugar is needed at all. In order to solve the trouble I propose enhancements to teachers, compilers and standard libraries: 1. 'if' syntax should be teached as if a then b else c This indentation makes pretty clear, what is condition, and what is the result in both cases. It just resembles case a of True -> b False -> c . 2. Add 'if :: Bool -> a -> a -> a' or '(?) :: Bool -> (a,a) -> a' or both to the standard library, as discussed in the thread starting with http://www.haskell.org/pipermail/haskell-cafe/2006-July/016914.html 3. If a compiler suspects that a parsing problem is related to 'do' and 'if' it should suggest indentation if a then b else c or even better, the usage of if- or (?)-function. So, please add this to the 'Cons' list.

18 38

Proposal for stand-alone deriving declarations?
by Bjorn Bringert 30 Oct '06

30 Oct '06

On http://hackage.haskell.org/trac/haskell-prime/wiki/ DerivedInstances it says: "- There is no way to derive an instance of a class for a data type that is defined elsewhere (in another module)." Though there is no proposal to fix this. Would such a proposal be appropriate for Haskell'? If so, I propose to add a top-level declaration on the form: 'deriving' qtycls 'for' qtycon which produces the same instance as a deriving clause in the declaration of the datatype or newtype would. I have recently (thanks to the GHC Hackathon) implemented this in GHC. /Björn

9 16

Re: seq vs. pseq
by Malcolm Wallace 27 Oct '06

27 Oct '06

Simon Marlow <simonmarhaskell(a)gmail.com> wrote: > The difference is subtle. The semantics of seq and pseq are > identical; however, GHC can see that seq is strict in both its > arguments and hence could choose to evaluate them in either order, > whereas pseq is only strict in its first argument as far as the > strictness analyser is concerned. The point is that pseq is useful > for controlling evaluation order, which is what you want for adding > parallelism to a program. seq, on the other hand, is not useful for > controlling evaluation order. This is a rather weird thing, and I would consider it a bug in the Haskell Report, rather than a bug in ghc. (It bites hard when you are trying to implement something like HPC.) The very name 'seq' surely suggests that you are controlling the evaluation order. "Please evaluate this thing on the left first". But that is _not_ what the Haskell Report says! Ghc takes the Report literally, and so the thing on the right is just as likely to be evaluated before the thing on the left! Surely the language designers did not intend this consequence. For Haskell-prime, can we fix this bug, and ensure that 'seq' really implies ordering of evaluation? [ If you just want strictness annotations, with the compiler free to reorder computations, I would say ($!) is a better bet, and could be redefined to use not the natural `seq`, but the strict-in-both-arguments variation. ] Regards, Malcolm

1 0

Re: Indentation of If-Then-Else
by Neil Mitchell 25 Oct '06

25 Oct '06

> > Actually if-then-else isn't used that often today. Most programmers > > gave it up in favor of guards. > > I question both these statements. Can you cite some evidence here? I have 501 if statements in my current project. Yhc has 626. Hoogle has 101. If's seem pretty well used to me! Thanks Neil

5 5

Module imports anywhere
by Henning Thielemann 24 Oct '06

24 Oct '06

I don't see the benefit of allowing imports anywhere at top-level. http://hackage.haskell.org/trac/haskell-prime/wiki/AllowImportAnywhere As with declarations I expect that imported identifiers are visible everywhere in a module. Thus the search for an imported identifier becomes even more complicated as it is today (due to anonymously imported identifiers and re-exported modules). Sometimes I missed a feature from the Modula-2 derivative named "Cluster", namely local imports of modules. Locally imported identifiers would be invisible to other functions. However I don't think that it is so important to be worth the trouble of implementing it.

4 4

Re: Standard syntax for preconditions, postconditions, and invariants
by John Hughes 22 Oct '06

22 Oct '06

> >> I propose that haskell' include a standard syntax for invariants that >> the programmer wants to express. > >> The intent is not to have standardized checks on the invariants, its >> just to supply a common way to specify invariants to that the various >> strategies for checking them can all work from the same data. For >> example, one tool might use the invariants to generate QuickCheck >> properties > I think it's too early for this. As others have pointed out, it's not even clear what the semantics of these things should be. What's more, the way you write such properties depends partly on what you intend to do with them. QuickCheck properties aren't just logical properties, they're restricted to make them testable, and carry extra information to control test case generation. Other tools, like partly automated provers, may need other additional information, such as induction variables. We spent a lot of time looking for a unified property notation in the Cover project, and we didn't find one we were really happy with. The P-logic that Programmatica uses, and the preconditions that Dana Xu used in her Haskell workshop paper, are quite different from each other. We need more research on the tools that would use these annotations, before we try to fix their syntax. John

1 0