October 2006 - Haskell-prime

Replacing and improving pattern guards with PMC syntax
by kahl＠cas.mcmaster.ca 04 Oct '06

04 Oct '06

One of the problems of pattern matching in Haskell is that it might well be regarded as not very declarative: function definition lines cease being generalisable equations, and the definition of the rewriting strategy involved in Haskell pattern matching extends over about three pages, no matter whether you look in the Haskell report, or for a definition of the ``functional rewriting strategy'' in the theoretical literature. <shameless plug> To fix exactly this problem was my original goal when I started developing a family of Pattern Matching Calculi, see http://www.cas.mcmaster.ca/~kahl/PMC/ . </shameless plug> (Other pattern matching calculi in the literature have different goals.) The original calculus, which I shall call ``PMC'' for the remainder of this message, is a confluent rewriting system with a normalising strategy that incorporates Haskell pattern matching --- the confluence proof has been mechanised using Isabelle. So far I never considered it important to devise a concrete syntax for PMC, but triggered by the current pattern guards thread on haskell-prime, I now try to give a PMC syntax that blends well with Haskell. PMC ``automatically'' includes the ``expression pattern'' of pattern guards, but organised differently, see below. I am now presenting a series of syntactic extensions to Haskell. without assuming that the reader is familiar with PMC, but I will also explain how these extensions relate with PMC. One of my gripes with Haskell pattern matching is that the anonymous variant, namely case expressions, has an application to an argument built in, and therefore does not by itself produce a function. However, lambda-abstraction already allows single-alternative pattern matching, so I propose to relax this to multi-alternative pattern matching: > length = \ > [] -> 0 > x : xs -> 1 + length xs (Lists of alternatives correspond to the ``matchings'' of PMC, and concatenation of those lists (using ``;'' or layout) corresponds to matching alternative in PMC. ``\ m'' then corresponds to ``{| m |}'' in PMC. ) For multi-argument pattern matching, I propose to allow nested matchings: > zip = \ > x : xs -> y : ys -> (x,y) : zip xs ys > _ -> _ -> [] > take' = \ > 0 -> _ -> [] > n -> { [] -> [] > ; x : xs -> x : take (pred n) xs > } This means that the alternative ``->'' now can have either an expression or a list of alternatives as its right argument. (Having an expression there corresponds to ``lifting'' $\leftharpoonup \_ \rightharpoonup$ in PMC.) Pattern guards now can be seen as a special case of alternatives-level argument application (``argument supply'' $\righttriangle$ in PMC). I find it useful to write the argument first, as in PMC. I see two options of writing argument supply in Haskell: either using new keywords, giving rise to the syntax production alt -> match exp with alts or using a keyword infix operator: alt -> exp |> alts (Using this kind of argument supply instead of pattern guards also has the advantage that multiple alternatives become possible.) I start with Simon Peyton Jones' standard example: > clunky env v1 v2 | Just r1 <- lookup env v1 > , Just r2 <- lookup env v2 = r1 + r2 > | otherwise = v1 + v2 This could now be written using either ``match _ with _'': > clunky env v1 v2 = \ > match lookup env v1 with > Just r1 -> match lookup env v2 with > Just r2 -> r1 + r2 > v1 + v2 or infix ``_ |> _'': > clunky env v1 v2 = \ > lookup env v1 |> Just r1 -> > lookup env v2 |> Just r2 -> r1 + r2 > v1 + v2 Note that the syntactic structure is different from pattern guards; here is the fully parenthesised version: > clunky env v1 v2 = \ > { lookup env v1 |> { Just r1 -> > { lookup env v2 |> { Just r2 -> r1 + r2 }}} > ; v1 + v2 > } Boolean guards are matches against True: > take = \ > 0 -> _ -> [] > n -> match n > 0 with > True -> > { [] -> [] > ; x : xs -> x : take (pred n) xs > } > _ -> error "take: negative argument" But Boolean guards can also be kept as syntactic sugar: > take = \ > 0 -> _ -> [] > n | n > 0 -> > { [] -> [] > ; x : xs -> x : take (pred n) xs > } > | otherwise -> error "take: negative argument" Now we have all the syntax in place --- PMC's ``failure'' is of course the empty alternative (allowed in Haskell 98). For the grammar, the relevant productions in Haskell 98 are: exp10 -> \ apat1 ... apatn -> exp (lambda abstraction, n>=1) | "case" exp "of" { alts } (case expression) alts -> alt1 ; ... ; altn (n>=1) alt -> pat "->" exp [where decls] | pat gdpat [where decls] | (empty alternative) gdpat -> gd "->" exp [ gdpat ] gd -> | exp This would change to the following, where I propose to rename ``alt'' to ``match'' for ``matching'' as in PMC, since this is now a full-fledged syntactic category of importance similar to that of expressions (PMC works essentially because of this separation of syntactic categories): exp10 -> \ { matchs } (lambda abstraction) | "case" exp "of" { matchs } (case expression) matchs -> match1 ; ... ; matchn (alternative, n>=1) match -> expr (result) | pat "->" { matchs } [where decls] (pattern matching) | pat gdpat [where decls] (pat. mat. w. Boolean guards) | (empty alternative) | "match" exp "with" { matchs } (pattern argument supply) gdpat -> gd "->" { matchs } [ gdpat ] gd -> | exp (case expressions would than be syntactic sugar: > case exp of {matchs} = \ match exp with {matchs} ) These productions imply that we would loose multiple abstraction: \ x y z -> 3 becomes \ x -> y -> z -> 3 . For reasons of declarativity, I am also tempted to argue that ``='' should only be allowed for one-line definitions, so we would write: > f 0 -> 1 > f n -> n * f (n - 1) An easy-to-remember motto for this could be ``if it can fall through, use ->''. This would of course break every single textbook and tutorial, so I won't insist... No matter whether with ``->'' or with ``='', the above would of course be syntactic sugar for: > f = \ > 0 -> 1 > n -> n * f (n - 1) LAWS ==== The most important nice thing is that we can now use equational reasoning for expressions involving pattern matching. The PMC laws (see the papers for more explanation) translate into the syntax presented above as follows (note that most of these equations are between matchings, i.e., between (lists of) alternatives, and only some are between expressions): --------------------------------------------------------------------- Failure as unit: > {- empty alternative -} ; alts = alts Failure lifting: > \ { } = undefined Result lifting: > \ { exp } = exp Argument propagation into matching: > (\ { alts }) exp = \ { match exp with { alts } } Argument propagation into expression: > match arg with { exp } = exp arg First match wins (no backtracking after first success): > exp ; alts = exp Failure-strictness of argument supply: > match arg with { } = {- empty alternative -} Distributivity of argument supply over alternative: > match arg with { alts1 ; alts2 } = > match arg with { alts1 } ; match arg with { alts2 } beta (v is a variable): > match arg with { v -> { alts } } = alts[v \ arg] -- substitution Match when matching the same constructor: > match c(e1,...,en) with {c(p1,...,pn) -> {alts}} > = match e1 with {p1 -> ... -> match en with pn -> {alts}} Mismatch when matching different constructors: > match c(e1,...,em) with {d(p1,...,pn) -> {alts}} > = {- empty alternative -} Strictness of matching against constructors: > match undefined with {c(p1,...,pn) -> {alts}} = undefined --------------------------------------------------------------------- Together with Strictness of function application in the function: > undefined arg = undefined -- already in Haskell , these laws, when oriented as rules, produce a confluent rewriting system, and the standard definition of strong head normal form induces a normalising strategy. Besides extending syntactic convenience even beyond pattern guards, adopting the abstract syntax of PMC would therefore also simplify the definition of the semantics of pattern matching in Haskell, and extend the scope of equational reasoning to pattern matching. For the concrete syntax I have no strong feelings, but hope that I provided a starting point for discussion. Wolfram

4 3

Pattern guards
by Yitzchak Gale 03 Oct '06

03 Oct '06

I would like to suggest a correction to ticket #56, "Pattern Guards". It is easy to show that every expression written using pattern guards can also be written in Haskell 98 in a way that is essentially equivalent in simplicity. (Proof below.) In my opinion, the Haskell 98 version below is more clear than the pattern guard version - it makes the monad explicit. Even if you disagree, I think it would be very difficult to argue that the difference is important enough to justify the extreme measure of adding new syntax to the language. Therefore, the first two items under "Pros" are false, and should be removed. The only remaining "Pro" is that the extension is well-specified, which has no value on its own. The purpose of Haskell' is to remove warts from Haskell, not add new ones. Pattern guards are a serious wart - they further overload syntax that is arguably already overused, as pointed out in the referenced paper by Martin Erwig and Simon Peyton Jones [EPJ]. I hope that there is still time to retract the evil decree of "definitely in" Proposal Status for this ticket. Regards, Yitz Proof: We first assume that the following declarations are available, presumably from a library: > data Exit e a = Continue a | Exit {runExit :: e} > instance Monad (Exit e) where > return = Continue > Continue x >>= f = f x > Exit e >>= _ = Exit e (Note that this is essentially the same as the Monad instance for Either defined in Control.Monad.Error, except without the restriction that e be an instance of Error.) > maybeExit :: Maybe e -> Exit e () > maybeExit = maybe (return ()) Exit Now given any function binding using pattern guards: funlhs | qual11, qual12, ..., qual1n = exp1 | qual21, qual22, ..., qual2n = exp2 ... we translate the function binding into Haskell 98 as: funlhs = runExit $ do maybeExit $ do {qual11'; qual12'; ...; qual1n'; return (exp1)} maybeExit $ do {qual21'; qual22'; ...; qual2n'; return (exp2)} ... where qualij' -> pat <- return (e) if qualij is pat <- e qualij' -> guard (qualij) if qualij is a boolean expression qualij' -> qualij if qualij is a let expression For a conventional guard: | p = exp we can simplify the translation to: when (p) $ Exit (exp) Simplifications are also possible for other special cases. This concludes the proof. Here are some examples, taken from [EPJ]: > clunky env var1 var2 > | Just val1 <- lookup env var1 > , Just val2 <- lookup env var2 > = val1 + val2 > ...other equations for clunky translates to: > clunky env var1 var2 = runExit $ do > maybeExit $ do > val1 <- lookup env var1 > val2 <- lookup env var2 > return (val1 + val2) > ...other equations for clunky > filtSeq :: (a->Bool) -> Seq a -> Seq a > filtSeq p xs > | Just (y,ys) <- lview xs, p y = lcons y (filtSeq p ys) > | Just (y,ys) <- lview xs = filtSeq p ys > | otherwise = nil translates to: > filtSeq :: (a->Bool) -> Seq a -> Seq a > filtSeq p xs = runExit $ do > maybeExit $ do > (y,ys) <- lview xs > guard $ p y > return $ lcons y $ filtSeq p ys > maybeExit $ do > (y,ys) <- lview xs > return $ filtSeq p ys > Exit nil Note that in this case, the Maybe monad alone is sufficient. That eliminates both the double lookup and the double pattern match, as discussed in [EPJ]: > filtSeq :: (a->Bool) -> Seq a -> Seq a > filtSeq p xs = fromMaybe nil $ do > (y,ys) <- lview xs > return $ if (p y) > then lcons y (filtSeq p ys) > else filtSeq p ys

10 21

All Monads are Functors
by Jon Fairbairn 03 Oct '06

03 Oct '06

I find myself dismayed that the mathematical relationship between Monads and Functors isn't available in Haskell98; if I use fmap in a Monad m=>... typed function, I get an extra Functor m required in the context, but not only are all mathematical monads functors, any instance of Monad has fmap in the form (>>= return . f), so it's annoying. There has been discussion in the past about whether Monad should be defined as > class Functor m => Monad m where ... (or some other means of making all Monads instances of Functor) I think the general consensus on the libraries mailing list in this thread http://thread.gmane.org/gmane.comp.lang.haskell.libraries/2815/focus=2815 which refers to this: http://www.cs.chalmers.se/~rjmh/Haskell/Messages/Display.cgi?id=444 was that it would be a good thing, but it breaks Haskell98 programmes. Surely Haskell' can get this right? On haskell prime I can find http://thread.gmane.org/gmane.comp.lang.haskell.prime/1328/focus=1427 which agrees with me, but I don't see a definite decision either there or in the Trac. I'd favour the above method as most conservative in terms of the language, but I'm not too fussed how it happens. Jón -- Jón Fairbairn Jon.Fairbairn at cl.cam.ac.uk

11 17

Re: [Haskell] Replacing and improving pattern guards with PMC syntax
by kahl＠cas.mcmaster.ca 02 Oct '06

02 Oct '06

Brandon, > Both of these constructs amount to minor syntactical overloading, > allowing lambda and "case" constructs in the expression grammar and the > match grammar with slightly different meanings. This seems to be pretty > similar to the way we already allow (Constr x y z) as an expression or a > pattern. I'm afraid this could easily lead to ambiguity on the grammar level and, independently, to confusion in the human head. But if these issues can be resolved, I currently do not feel strongly either way. Note however that > f xs = case xs of > (x : xs) -> case xs of > (y : ys) -> 1 > _ -> 2 and > g xs = case xs of > (x : xs) -> match xs with > (y : ys) -> 1 > _ -> 2 are different: f "01" = 1 g "01" = 1 f "0" = undefined g "0" = 2 f "" = 2 g "" = 2 f is in Haskell 98, and g can be rewritten using pattern guards: > g xs = case xs of > (x : xs) | (y : ys) <- xs -> 1 > _ -> 2 That is what I mean with ``fall-through'' --- and from this you see that you need an indicator for whether what is coming after the ``->'' is a matching or an expression. As long as the production alt -> expr is included, nothing that parses as an expression can be allowed to also parse as a matching according to a different production. In PMC, the corresponding production is match -> \leftharpoonup expr \rightharpoonup , so there, using ``case'' both for expressions and for matchings would ``only'' be confusing... But using delimiters is of course an option. (I also considered a different arrow for one of the two cases, for example ``|=>'' as in PMC, or even ``=>'', but I thought that the delimiter-less option was more ``Haskell-ish'', and with care in the grammar design can be made to work.) Several of your suggestions, including > I suggested whitespace rather than -> to separate sequential patterns could be feasible alternatives for the concrete syntax --- but we first need agreement on the abstract syntax. Perhaps the extension alt -> "match" exp "with" { alts } could be considered as an independent extension; this is more powerful than pattern guards, and probably less controversial than multi-alternative lambda. Wolfram

1 0

[brandonm@yahoo-inc.com: Re: [Haskell] Replacing and improving pattern guards with PMC syntax]
by kahl＠cas.mcmaster.ca 02 Oct '06

02 Oct '06

Brandon asked me to forward this --- I already posted a small clarification. Wolfram ------- Start of forwarded message ------- Date: Mon, 02 Oct 2006 00:07:17 -0700 From: Brandon Moore <brandonm(a)yahoo-inc.com> To: kahl(a)cas.mcmaster.ca CC: haskell-prime(a)haskell.org Subject: Re: [Haskell] Replacing and improving pattern guards with PMC syntax In-Reply-To: <20061002003307.15687.qmail(a)schroeder.cas.mcmaster.ca> kahl(a)cas.mcmaster.ca wrote: ... > So far I never considered it important to devise a concrete syntax for PMC, > but triggered by the current pattern guards thread on haskell-prime, > I now try to give a PMC syntax that blends well with Haskell. I think with some alterations your syntax would blend even better. In particular, it would be really nice to have a backwards-compatible syntax. > One of my gripes with Haskell pattern matching is > that the anonymous variant, namely case expressions, > has an application to an argument built in, > and therefore does not by itself produce a function. > > However, lambda-abstraction already allows single-alternativepattern matching, so I propose to relax this to multi-alternative > pattern matching: >> length = \ >> [] -> 0 >> x : xs -> 1 + length xs I'm with you here. Extending lambda to introduce a layout group of alternatives makes sense even without the rest of the changes to matching. This isn't completely backwards-compatible, but it's pretty close. While we're at it, why not have the identifier of a top level definition introduce a layout group of alternatives, rather than requiring the name to be repeated all the time. How about take 0 _ = [] _ [] = [] n (x:xs) = x : take (pred n) ns > (Lists of alternatives correspond to the ``matchings'' of PMC, > and concatenation of those lists (using ``;'' or layout) corresponds > to matching alternative in PMC. > ``\ m'' then corresponds to ``{| m |}'' in PMC. > ) > > For multi-argument pattern matching, > I propose to allow nested matchings: >> zip = \ >> x : xs -> y : ys -> (x,y) : zip xs ys >> _ -> _ -> [] This deviates from the current syntax of multi-argument lambda, and introduces overloading on ->. Perhaps -> could be reserved for "match and lift", and whitespace could separate several alternatives: zip = \ (x:xs) (y:ys) -> (x,y) : zip xs ys _ _ -> [] There is some tension in the current between argument lists which allow several arguments and require parentheses around constructor applications to delimit patterns, and case expression which match only one item, but without grouping. If we are trying to unify things, perhaps case could be extended to support matching several values together, perhaps separating expressions with commas in the head and using the syntax of a lambda for the cases. Perhaps '=' in function declarations vs. "->" for other matching could also be simplified somehow. I don't have any ideas here. >> take' = \ >> 0 -> _ -> [] >> n -> { [] -> [] >> ; x : xs -> x : take (pred n) xs >> } I'm not sure how to handle a case like this. Introducing layout at whitespace seems a bit excessive, but requiring explicit separators looks a bit heavy on punctuation next to the current grammar, where only records (and perhaps Maybe the '\' could be reiterated to introduce the layout group: take' = \ 0 _ -> [] n \[] -> [] (x:x) -> x : take (pred n) xs > > Pattern guards now can be seen as a special case of > alternatives-level argument application > (``argument supply'' $\righttriangle$ in PMC). > I find it useful to write the argument first, as in PMC. > > I see two options of writing argument supply in Haskell: > either using new keywords, giving rise to the syntax production > > alt -> match exp with alts Maybe reuse "case", unless a new keyword is needed to avoid confusion. > or using a keyword infix operator: > > alt -> exp |> alts > > (Using this kind of argument supply instead of pattern guards > also has the advantage that multiple alternatives become possible.) I'm not using -> to separate patterns, but some leading symbol is required to separate the last pattern from the expression. I like '|' from the current syntax, selected with hopes of incorporating and extending the current guard syntax. I'm pretty sure incorporating the existing guard syntax will require that the grammar keep track whether the last "bit" of the matching was a pattern or a guard (just like currently | switches from patterns separated by whitespace to a list of guards separated by commas). Pattern guards can be translated to matching plus argument supply, so argument supply needs to be part of the primitive matching syntax. I like the suggestion alt | exp |> alts It would be unambiguous but require unbounded lookahead to allow a case to begin with argument supply: foo :: [Int] -> [Int] foo = \lookup env v |> (Just r) [] -> [r] Given argument supply, we can sugar in the existing guard syntax by allowing alt | guard, guards, exp |> alts and alt | guards -> expr The sequence "->\" will transition from guards back to matching more arguments. It might be nice to abbreviate that to '\'. Guards can be eliminated with the translations alt | exp, guards ... ==> alt | exp |> True |guards alt | exp -> expr ==> alt | exp |> True -> expr alt | pat <- exp, guards ==> alt | exp |> {pat | guards ... } alt | pat <- exp -> expr ==> alt | exp |> pat -> expr > > I start with Simon Peyton Jones' standard example: > >> clunky env v1 v2 | Just r1 <- lookup env v1 >> , Just r2 <- lookup env v2 = r1 + r2 >> | otherwise = v1 + v2 I'd like to accepts this unchanged. I think the treatment of guards above will work. > This could now be written using either ``match _ with _'': > >> clunky env v1 v2 = \ >> match lookup env v1 with >> Just r1 -> match lookup env v2 with >> Just r2 -> r1 + r2 >> v1 + v2 > > or infix ``_ |> _'': > >> clunky env v1 v2 = \ >> lookup env v1 |> Just r1 -> >> lookup env v2 |> Just r2 -> r1 + r2 >> v1 + v2 Because I'm using space to separate patterns, I would require parentheses (or the pat <- exp sugar) clunky env v1 v2 | lookup env v1 |> (Just r1) , lookup env v2 |> (Just r2) -> r1 + r2 > Boolean guards are matches against True: >> take = \ >> 0 -> _ -> [] >> n -> match n > 0 with >> True -> >> { [] -> [] >> ; x : xs -> x : take (pred n) xs >> } >> _ -> error "take: negative argument" take = \ 0 _ -> [] n | n > 0 \[] -> [] (x:xs) -> x : take (pred n) ns This syntax has a pretty nice pronunciation, reading | as "such that", a comma as an "and" (between guards), and both space between patterns or '\' after a guard as "and" or "and then" (either way, introducing a pattern for another argument). This PMC stuff seems like a description/semantics for pattern matching. Hopefully my attempts at backwards-compatible syntax help people give the semantics a deeper look. Brandon ------- End of forwarded message -------

1 0

Re: [Haskell] Replacing and improving pattern guards with PMC syntax
by kahl＠cas.mcmaster.ca 02 Oct '06

02 Oct '06

Brandon Moore <brandonm(a)yahoo-inc.com> wrote in his answer to my PMC syntax proposal: > > Maybe the '\' could be reiterated to introduce the layout group: > > take' = \ > 0 _ -> [] > n \[] -> [] > (x:x) -> x : take (pred n) xs Definitely not, since the lambda gets us back into expressions, destroying the fall-through properties of matchings. (In this particular case this is no problem, but in general it would destroy fall-through.) > > > alt -> match exp with alts > Maybe reuse "case", unless a new keyword is needed to avoid confusion. We definitely need this construct to produce a matching (or ``alt''). If we use ``case'' here, then case expressions don't exist anymore. Wolfram

1 0