RE: n+k patterns
On 30 Jan 2002, at 12:01, [EMAIL PROTECTED] wrote: > Yet for floats there may not be such an x (y = positive zero), or there may > be more than one (y=2^n with n chosen so that 2^n+1 is not exactly representable but 2^n-1 is, then > x could be 2^n or 2^n-1). Well, I am just a newbie in Haskell, but this reason, together with the fact that n+k patterns were designed to be used in inductive definitions do make me strongly favor the restriction of n+k patterns to the class Integral (Malcolm Wallace pointed out that there may be a use for Rational n+k patterns, but I think it would only be advisable in the case that Rational numbers were implemented explicitly with numerators and denominators). Besides that, what about deprecating n+k patterns in future Haskell reports? :) just my $0.02, Carlos Eduardo Scheidegger ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: n+k patterns
Simon Peyton-Jones wrote: > | hbc is on the Integral side, if that counts. :-) > | Just because ghc doesn't follow the spec isn't a good reason > | to change the spec. :-) > > I absolutely didn't say that! All I'm saying is > > * Two of the four impls have to change regardless Only because two of the implementation teams didn't read the report. :-) -- Lennart ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
RE: n+k patterns
OK, OK, I give in! Integral it remains. I repent. Simon | -Original Message- | From: Rijk J. C. van Haaften [mailto:[EMAIL PROTECTED]] | Sent: 30 January 2002 17:00 | To: Simon Peyton-Jones | Cc: [EMAIL PROTECTED] | Subject: RE: n+k patterns | | | At 03:27 30-01-02 -0800, Simon Peyton-Jones wrote: | >| hbc is on the Integral side, if that counts. :-) | >| Just because ghc doesn't follow the spec isn't a good reason to | >| change the spec. :-) | > | >I absolutely didn't say that! All I'm saying is | > | >* Two of the four impls have to change regardless | >* The change is non-de-stabilising on the rest of the report | >* So we should think what the "best" answer is | > | >I argued that (Num a, Ord a) makes most sense to me. | >You argued that (Integral a) was a conscious choice | (something I don't | >remember but I'm sure you're right), and is the right one anyway. | > | >I'd be interested to know what others think. If there's any doubt, | >we'll stay with Integral. | | Personally I vote for keeping Integral. The strongest reason | for my choice is that if we want to be sure the pattern is | really correct, we need a bijection. For Integral, we have + | and - to form one, but we can't construct one for Float and | Double, though by this change they would be allowed in the pattern. | | Rijk-Jan van Haaften | | ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
RE: n+k patterns
At 03:27 30-01-02 -0800, Simon Peyton-Jones wrote: >| hbc is on the Integral side, if that counts. :-) >| Just because ghc doesn't follow the spec isn't a good reason >| to change the spec. :-) > >I absolutely didn't say that! All I'm saying is > >* Two of the four impls have to change regardless >* The change is non-de-stabilising on the rest of the report >* So we should think what the "best" answer is > >I argued that (Num a, Ord a) makes most sense to me. >You argued that (Integral a) was a conscious choice (something I >don't remember but I'm sure you're right), and is the right one anyway. > >I'd be interested to know what others think. If there's any doubt, >we'll stay with Integral. Personally I vote for keeping Integral. The strongest reason for my choice is that if we want to be sure the pattern is really correct, we need a bijection. For Integral, we have + and - to form one, but we can't construct one for Float and Double, though by this change they would be allowed in the pattern. Rijk-Jan van Haaften ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
RE: n+k patterns
I too am against broadening the scope of n+k patterns, for reasons that others have already given. In particular, I am absolutely against allowing n+k patterns to be used for Float/Double. If n+k patterns are to be meaningful at all, you want matching y against x+1, you want a unique x such that (x+1)=y. Yet for floats there may not be such an x (y = positive zero), or there may be more than one (y=2^n with n chosen so that 2^n+1 is not exactly representable but 2^n-1 is, then x could be 2^n or 2^n-1). ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: n+k patterns
I strongly disapprove of n+k patterns from a whole-language taste perspective, so I am most unkeen to broaden their scope. Because they are such a language kludge already it simply doesn't make sense to try to reason rationally about what the "best" answer for them is. It's like putting lipstick on a chicken. If anything, we should have restricted them to the very simplest case covered in the early textbooks, i.e. just Int. John > | hbc is on the Integral side, if that counts. :-) > | Just because ghc doesn't follow the spec isn't a good reason > | to change the spec. :-) > > I absolutely didn't say that! All I'm saying is > > * Two of the four impls have to change regardless > * The change is non-de-stabilising on the rest of the report > * So we should think what the "best" answer is > > I argued that (Num a, Ord a) makes most sense to me. > You argued that (Integral a) was a conscious choice (something I > don't remember but I'm sure you're right), and is the right one anyway. > > I'd be interested to know what others think. If there's any doubt, > we'll stay with Integral. > > Simon > > ___ > Haskell mailing list > [EMAIL PROTECTED] > http://www.haskell.org/mailman/listinfo/haskell ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: n+k patterns
> > I argued that (Num a, Ord a) makes most sense to me. > > You argued that (Integral a) was a conscious choice (something I > > don't remember but I'm sure you're right), and is the right one anyway. > > > > I'd be interested to know what others think. If there's any doubt, > > we'll stay with Integral. > > My view is that (n+k) patterns are evil, so it doesn't really matter > what we decide. :-) No, seriously, I'm a little worried about > widening the range of numeric types for which (n+k) patterns are > supposed to work. I can (just about) imagine wanting to use Rationals > in an (n+k) pattern, but Float and Double? I dimly remember that the justification for having n+k was to allow inductive definitions, which only applies to Integral. I'd vote for keeping it as it is, too. Jón ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
RE: n+k patterns
> I argued that (Num a, Ord a) makes most sense to me. > You argued that (Integral a) was a conscious choice (something I > don't remember but I'm sure you're right), and is the right one anyway. > > I'd be interested to know what others think. If there's any doubt, > we'll stay with Integral. My view is that (n+k) patterns are evil, so it doesn't really matter what we decide. :-) No, seriously, I'm a little worried about widening the range of numeric types for which (n+k) patterns are supposed to work. I can (just about) imagine wanting to use Rationals in an (n+k) pattern, but Float and Double? I'm not convinced that would be useful. f :: Double -> Double f (n+1) = n Main> print (f 3.0) 2.0 Main> print (f 2.0001) 1.00010002 Main> print (f 1.01) 1.00082740371e-10 Regards, Malcolm ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
RE: n+k patterns
| hbc is on the Integral side, if that counts. :-) | Just because ghc doesn't follow the spec isn't a good reason | to change the spec. :-) I absolutely didn't say that! All I'm saying is * Two of the four impls have to change regardless * The change is non-de-stabilising on the rest of the report * So we should think what the "best" answer is I argued that (Num a, Ord a) makes most sense to me. You argued that (Integral a) was a conscious choice (something I don't remember but I'm sure you're right), and is the right one anyway. I'd be interested to know what others think. If there's any doubt, we'll stay with Integral. Simon ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: n+k patterns
Simon Peyton-Jones wrote: > | Hugs "demands Integral" because that's what it was told to do > | to follow the report. So in that sense, yes, the code > | depends on having only one class. But it would be easy for > | someone to change that. > | > | Then again, if we're following the rules of minimal change > | for Haskell 98, then I wouldn't have thought this was up for > | grabs. (I'm thinking, for example, of the unnecessary "same > | context" restriction on mutually recursive binding groups, > | which has more practical impact, is very clearly a "bug", and > | has not (AFAIK) been fixed in Haskell 98. Then there's David > | Wakeling's generalized gap proposal, and ...) > > That is a fair point, and is exactly the reason I bother the Haskell > list with > these proposals rather than simply executing them. This is an unforced > change, as you point out, but in fact GHC and NHC currently do one > thing, and > Hugs does another (i.e. follows the spec!). So some of us have to > change > our implementations. hbc is on the Integral side, if that counts. :-) Just because ghc doesn't follow the spec isn't a good reason to change the spec. :-) -- Lennart ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: n+k patterns
Well, it was a deliberate decision to limit the n+k pattern to class Integral because people at that time felt that n+k was something that should only be used with integers. So it's not a fluke, it was quite deliberate. I kind of like Integral for this (as much as I can like anything about n+k :). Since this is not a typo, I don't see why it should be changed unless there is some really good reason. -- Lennart Simon Peyton-Jones wrote: > Folks > > The Haskell Report says of n+k patterns: > > "A n+k pattern can only be matched against a value in > the class Integral." > > This seems far too strong. All that is needed are Ord (for the >= and > -) > and Num (for fromInteger), and indeed that's what GHC requires. > Do Hugs or nhc actually require Integral? > > In any case, I propose to change "Integral" to "Ord and Num". > > Does anyone think this is the Wrong Thing? > > How this bug has lasted so long I don't know. > > Simon > > ___ > Haskell mailing list > [EMAIL PROTECTED] > http://www.haskell.org/mailman/listinfo/haskell ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
RE: n+k patterns
| Hugs "demands Integral" because that's what it was told to do | to follow the report. So in that sense, yes, the code | depends on having only one class. But it would be easy for | someone to change that. | | Then again, if we're following the rules of minimal change | for Haskell 98, then I wouldn't have thought this was up for | grabs. (I'm thinking, for example, of the unnecessary "same | context" restriction on mutually recursive binding groups, | which has more practical impact, is very clearly a "bug", and | has not (AFAIK) been fixed in Haskell 98. Then there's David | Wakeling's generalized gap proposal, and ...) That is a fair point, and is exactly the reason I bother the Haskell list with these proposals rather than simply executing them. This is an unforced change, as you point out, but in fact GHC and NHC currently do one thing, and Hugs does another (i.e. follows the spec!). So some of us have to change our implementations. It clearly isn't a big deal, because no one has ever reported this as a practical problem. Other things being equal, it would be better to make the spec make as much sense as possible; hence my proposal. But if it's really hard to change Hugs, maybe we should leave the spec and change GHC and nhc. But you say it would be easy. I agree it's a moot point. I lean towards making the change, but I'm willing to be persuaded. Simon ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
RE: n+k patterns
| On Tue, Jan 29, 2002 at 07:36:56AM -0800, Simon Peyton-Jones wrote: | > The Haskell Report says of n+k patterns: | > | > "A n+k pattern can only be matched against a value in | > the class Integral." | > | > This seems far too strong. All that is needed are Ord (for the >=) | > and Num (for - and fromInteger), and indeed that's what GHC requires. | > Do Hugs or nhc actually require Integral? | | Hugs demands Integral and the assumption that only one class is involved | seems deeply entwined in the code. Hugs "demands Integral" because that's what it was told to do to follow the report. So in that sense, yes, the code depends on having only one class. But it would be easy for someone to change that. Then again, if we're following the rules of minimal change for Haskell 98, then I wouldn't have thought this was up for grabs. (I'm thinking, for example, of the unnecessary "same context" restriction on mutually recursive binding groups, which has more practical impact, is very clearly a "bug", and has not (AFAIK) been fixed in Haskell 98. Then there's David Wakeling's generalized gap proposal, and ...) All the best, Mark ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
RE: n+k patterns
| Btw., in 3.17.2 Informal Semantics of Pattern Matching | the end of the following sentence should be changed: Actually I've changed the entire wording of that section in consultation with Ross who has read it rather carefully. You can find the current draft of the expressions chapter at http://research.microsoft.com/~simonpj/tmp/exps.html The numbered items in the Informal Semantics of Pattern Matching are substantially changed and IHMO much clearer. | Nonetheless I find using n+k patterns for floating point | numbers pretty horrible. And it raises the question why k | cannot be a rational ... But then n+k patterns are a wart anyway. Actually, you can only use integer 'k's. Simon ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: n+k patterns
> In any case, I propose to change "Integral" to "Ord and Num". I agree. And nhc98 seems to actually implement this. Nonetheless I find using n+k patterns for floating point numbers pretty horrible. And it raises the question why k cannot be a rational ... But then n+k patterns are a wart anyway. Btw., in 3.17.2 Informal Semantics of Pattern Matching the end of the following sentence should be changed: Matching a non-_|_ value x against a pattern of the form n+k (where n is a variable and k is a positive integer literal) succeeds if x>=k, resulting in the binding of n to x-k, and fails if x=k == False then x < k == True. So the sentence should end "..., and fails otherwise". Olaf -- OLAF CHITIL, Dept. of Computer Science, The University of York, York YO10 5DD, UK. URL: http://www.cs.york.ac.uk/~olaf/ Tel: +44 1904 434756; Fax: +44 1904 432767 ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: n+k patterns
On Tue, Jan 29, 2002 at 07:36:56AM -0800, Simon Peyton-Jones wrote: > The Haskell Report says of n+k patterns: > > "A n+k pattern can only be matched against a value in > the class Integral." > > This seems far too strong. All that is needed are Ord (for the >=) > and Num (for - and fromInteger), and indeed that's what GHC requires. > Do Hugs or nhc actually require Integral? Hugs demands Integral and the assumption that only one class is involved seems deeply entwined in the code. > In any case, I propose to change "Integral" to "Ord and Num". Without this change, the relevant rule of the formal semantics of patterns wouldn't preserve the static semantics. ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: n+k patterns, etc.
I think that we should try a different approach, forget about the importing mechanism, and make a single statement defining the intended semantics. Section 1.2 (The Haskell Kernel) is the place. I propose adding the following. The translations given, and the identities given for the semantics of case expressions, are not macros. A simple replacement of the right-hand-side for the left-hand-side with substitution of parameters does not give the intended semantics. The reason for this is that the translations make use of certain names defined in the standard prelude (see section 5.4), and macro substitution could result in the capture of these names by locally defined entities, or the use of a name in a context in which it is not defined at all because the part of the prelude in which it is defined has not been imported. The general rule is: the use of a name defined in the standard prelude in a translation intended to show the semantics of a construct always implies the definition in the standard prelude. Then, people can locally rebind as much as they want, but the constructs defined by translation will be unaffected. This sounds reasonable to me. -Paul
Re: n+k patterns, etc.
(I sent a similar message a few days ago which got lost somewhere) We have tried to express the semantics of some Haskell constructs by giving a translation into "Kernel" Haskell (Report section 1.2). This leads to difficulties because free variables in the translations can be captured by the context in which the construct is used. We have tried to use the importation rules applying to Prelude and PreludeCore to ensure the desired behaviour, but this is insufficient and unclear. Specifically 1) Everything exported by PreludeCore is implicitly imported into every module, and cannot be renamed or redefined at the top level. This covers standard classes, including their member functions, and types, including the operators used in the translation of n+k patterns, which means that these always refer to member functions of standard classes, except perhaps in inner scopes where names used in the translation have been locally rebound. It is intended that the Prelude meanings of locally rebound names should be used in the translation but there is nothing to enforce this. 2) Things exported by Prelude and not by PreludeCore are implicitly imported into every module unless Prelude is explicitly imported, when they can be subject to renaming or hiding. Despite this, we want names used in translations to refer to the Prelude entities even though these might not be visible at that point of the program because they are not imported, or renamed and the names reused, or locally redefined. I think that we should try a different approach, forget about the importing mechanism, and make a single statement defining the intended semantics. Section 1.2 (The Haskell Kernel) is the place. I propose adding the following. The translations given, and the identities given for the semantics of case expressions, are not macros. A simple replacement of the right-hand-side for the left-hand-side with substitution of parameters does not give the intended semantics. The reason for this is that the translations make use of certain names defined in the standard prelude (see section 5.4), and macro substitution could result in the capture of these names by locally defined entities, or the use of a name in a context in which it is not defined at all because the part of the prelude in which it is defined has not been imported. The general rule is: the use of a name defined in the standard prelude in a translation intended to show the semantics of a construct always implies the definition in the standard prelude. Then, people can locally rebind as much as they want, but the constructs defined by translation will be unaffected. The syntax makes it clear that the + and - used in patterns are not the same as the varops denoted by these symbols, so are unaffected by rebinding. I suppose a note could be added pointing this out if absolutely necessary. --brian
Re: n+k patterns, etc.
|What if (the appropriate parts of) the standard prelude is | explicitly *not* imported: | | import Prelude () | or | import Prelude hiding(map) | | (see section 5.4.3). | |Are then the hidden parts of the standard prelude still available via | n+k patterns, list comprehensions etc.? (Via some unseen and unhidable | intermediary module.) Or are constructs that use hidden parts of the | standard prelude (according to their translations given in the report) | not available? Yes. No. Respectively. The Report is obviously not clear enough on this point. The wording given for translations (eg list comprehensions) that "map" refers to the Prelude "map" is meant to indicate that it refers to the Prelude "map" whether or not the latter is explicitly in scope. That's the consistent story for all special syntax, to answer the latter part of your message. Simon
Re: n+k patterns, etc.
Some more questions concerning some constructs in Haskell: What if (the appropriate parts of) the standard prelude is explicitly *not* imported: import Prelude () or import Prelude hiding(map) (see section 5.4.3). Are then the hidden parts of the standard prelude still available via n+k patterns, list comprehensions etc.? (Via some unseen and unhidable intermediary module.) Or are constructs that use hidden parts of the standard prelude (according to their translations given in the report) not available? By the way, what about other special syntax constructs, like [...] for lists and (...,...,...) for tuples. Are these still available even if the standard prelude is not imported? Apparently lists and tuples cannot be selectively hidden, but the entire standard prelude can be hidden. Or, to rephrase the question, are such special syntax constructs reexported by the unseen and unhidable intermediary module mentioned in the previous paragraph? If so, then I think that the unhidable intermediary module for special syntax constructs should be made explicit (but, of course, still not codable in Haskell itself, due to the special syntax). Asking strange questions /kent k P.S. (Apropos Lennarts quiz) I think that the function names in "funlhs"es (in each let/where) should not be allowed to be rebound by some pattern whithin one of the "funlhs"es. I.e. id id = id should not be a definition of the identity function (while still allowing the definition id = \id.id). This would just naturally extend the "linearity restriction" in section 4.4.2, which disallows e.g. f x x = ... and f = \x x->... but allows f = \x->\x->... . (I don't dare go as far as proposing to ban "shadowing" completely.) /kn
Re: n+k patterns
>From my point of view (n+k)-patterns have a very special meaning. This natural numbers should be considered as a type like this: data Nat = Zero | Succ Nat Therefore a (n+k)-pattern is an abbreviation for Succ(Succ(...Zero...)). It's obvious that "+" in "(n+k)" doesn't mean a somewhere else defined (or locally rebound) function. If we keep this in mind there shouldn't be any problem. (Tell me if I'm wrong.) Greetings, Marc Rehmsmeier.
Re: n+k patterns
You are quite right. I'd forgotten about local rebinding, because I feel that all local rebinding should be disallowed. Anyone want to start a movement to eliminate local rebinding? (1/2 :-) Cheers, -- P - Begin Included Message - >From [EMAIL PROTECTED] Tue May 18 14:56:37 1993 Date: Tue, 18 May 93 15:55:42 +0200 From: Lennart Augustsson <[EMAIL PROTECTED]> To: [EMAIL PROTECTED] Cc: [EMAIL PROTECTED] Subject: Re: n+k patterns > Both (>=) and (-) belong to classes defined in PreludeCore, > and hence cannot be rebound. This was a deliberate decision, > made in order to turn your point into a non-problem. It's true that things from PreludeCore cannot be rebound on the top level, but they can be rebound locally. So the problem I state does occur. OK, I think that (>=), (-), etc. should refer to those from PreludeCore, but it doesn't say anywhere. Another question along the same lines: What if (+) has been rebound? Are n+k patterns still allowed? -- Lennart - End Included Message -
Re: n+k patterns
> Both (>=) and (-) belong to classes defined in PreludeCore, > and hence cannot be rebound. This was a deliberate decision, > made in order to turn your point into a non-problem. It's true that things from PreludeCore cannot be rebound on the top level, but they can be rebound locally. So the problem I state does occur. OK, I think that (>=), (-), etc. should refer to those from PreludeCore, but it doesn't say anywhere. Another question along the same lines: What if (+) has been rebound? Are n+k patterns still allowed? -- Lennart
Re: n+k patterns
Phil wrote: > Both (>=) and (-) belong to classes defined in PreludeCore, > and hence cannot be rebound. This was a deliberate decision, > made in order to turn your point into a non-problem. > > Long live (n+k)! -- P The Report tries to handle this by "always implicitly importing" PreludeCore. This is not sufficient to prevent rebinding, e.g. if somebody calls a formal parameter (>=). There is a related story w.r.t. the Definition of Standard ML. In its appendix, the SML report defines the meaning of some so-called "derived forms" in form of rewrite rules (e.g. it rewrites if-then-else into case-expressions and case-expressions into function application). These rewrite rules also use predefined identifiers (like true and false), which means that SML has exactly the same problems as Haskell. I took it for granted that the SML definition "meant" to refer to predefined identifiers, and all the standard implementations agreed on that. However, when I had an email-dispute with somebody who was involved in designing the SML definition about some of the problems relating to this, I was very surprised to find out that he was willing to understand the definitions literally and leave it to the user to modify the meaning of if-then-else by redefining true if s/he chooses to do so. I was even more surprised to hear from Dave Berry who works on Harlequin's SML compiler that their prototype indeed implemented these rules literally [well, almost: they did not get the "identifier status" bit right, a problem that does not exist in Haskell]; I am not sure whether their final release will still contain this feature, at least I discouraged them. Moral: do not take anything for granted, you can end up with somebody's implementation violating your hidden assumptions. -- Stefan Kahrs P.S. I join Lennart's "Ban n+k pattern"-movement.
Re: n+k patterns
Lennart Augustsson <[EMAIL PROTECTED]> writes: > PS. I'd like to start the "Ban n+k patterns"-movement, any followers? Count on me! I guess this makes it an organized movement ... two persons (movement) that know about each other (organized). Cheers, Karl-Filip
Re: n+k patterns
I like the capability to redefine syntax.
For example, I would like to be able to define syntax that looks like
EBNF when writing parsers. I would like to be able to write
E = T {(`+`|`-`) T}
rather than
e = concat1 (t,zeroOrMore (concat2 (alternative (lit '+',lit '-'),t)))
Of course infix operators help, but what about nice multiple
token symbols like { } ?
So, minimally, I am in favor of the local redefinition of symbols like
'+' and '>=', and think it unfortunate that there is a clash between
the redefinition and treatment of n+k patterns.
This is a vote for dumping n+k patterns, and a wish for more flexible
syntax not hampered by special cases.
Ken
Re: n+k patterns
The Haskell Committee was well aware of the problem of name capture in syntactic expansions. We discussed various solutions and opted for the simplest (if not most formal): whenever a name freshly appears on the right side of a translation, add a comment that says where it came from. If you look at the translations for expressions in Section 3 of the Report, you will see many instances of the phrase "as defined in the Standard Prelude". It was an oversight not to include such a phrase in the translation of patterns given in Section 3.14, the source of Lennart's original question. As for n+k patterns, I tried to get them out of Haskell on several occasions, even before the Report was released, but failed! Now that I've programmed in Haskell for a few years, I'm convinced more than ever that they should be removed. So add me to the movement! -Paul
Re: n+k patterns
Both (>=) and (-) belong to classes defined in PreludeCore,
and hence cannot be rebound. This was a deliberate decision,
made in order to turn your point into a non-problem.
Long live (n+k)! -- P
- Begin Included Message -
>From [EMAIL PROTECTED] Mon May 17 21:33:41 1993
From: Lennart Augustsson <[EMAIL PROTECTED]>
Subject: n+k patterns
Date: Mon, 17 May 93 22:25:03 +0200
To: [EMAIL PROTECTED]
Could those in charge of the formal semantics of Haskell (yes,
that's you folks in Glasgow!) tell me what the meaning of n+k patterns
are?
In the report it says that
case e0 of { x+k -> e; _ -> e' }
translates to
if e0 >= k then { let { x' = e0-k } in e[x'/x] else e'
Which >= and - does this refer to?
What if they have been locally rebound? E.g.
let x - y = x ++ f y
where f 0 = []
f (n+1) = f n
in [] - 0
Does the translated - still refer to the method in PreludeCore or
to the - in scope?
-- Lennart
PS. I'd like to start the "Ban n+k patterns"-movement, any followers?
- End Included Message -
Re: n+k patterns
|Another question along the same lines: What if (+) has been rebound? |Are n+k patterns still allowed? | |-- Lennart The answer should be that n+k patterns are still allowed, but (+), (-), and (>=) from PreludeCore are used in the translation. --Joe
Re: n+k patterns
Original-Via: uk.ac.ed.mrcvax; Thu, 28 Nov 91 08:51:34 GMT | Personally, I think n+k patterns are a baroque left-over from views that | someone thought would be nice to retain when views were abandonned. They | should either be thrown out or generalised in a more regular way. | | Let's throw them out. I wouldn't miss them. Ian
Re: n+k patterns
X-Comment1: # X-Comment2: # uk.ac.glasgow.cs has changed to uk.ac.glasgow.dcs # X-Comment3: # If this address does not work please ask your mail# X-Comment4: # administrator to update your NRS & mailer tables. # X-Comment5: # There's been an interesting debate about n+k patterns on this list. In this message I am only addressing the question of what changes, if any, should be made to the V1.1 Report (which I am trying to fix in the light of people's observations). The only issue seems to me to be this one, raised by Brian: | o Equality should be symmetric and transitive. Otherwise you're going |to start wondering whether f 0 = 1; f n = n * f (n-1) is interpre | ted |as f n = if n==0 then 1 else n * f (n-1) |or f n = if 0==n then 1 else n * f (n-1) | | This is good example. Should the Report state how implementations are to | translate matching of constant patterns? Or should it state that | implementations are free to assume symmetry here? Actually, the Report *does* state how implemenatations are to translate constant patterns (page 22). But on looking at it, I see that k patterns are translated to(k == e) but n+k patterns are translated to (e >= k) and (e - k) While this is unambiguous, it seems rather inconsistent. I suggest changing the translation of equality to (e == k). Only change required is page 22, line -11. Any objections? Any other V1.1 issues? Simon
Re: n+k patterns
Original-Via: uk.ac.nsf; Wed, 6 Nov 91 20:00:39 GMT
Original-Sender: [EMAIL PROTECTED]
> I would be very much in favour of missing out the >= test in both n+k and
> c*n+k. As Mark says there is no need for a restriction in the latter case.
> In the former, the restriction is only there because of a wish to model
> the Natural Numbers, a data type which is NOT native to Haskell.
>
> Tony
May I then propose yet another (sorry :-) arithmetic pattern: -n;
that matches only negative numbers:
case e0 of {-x -> e; _ -> e';}
= if e0 < 0 then case -(e0) of {x -> e; _ -> e';} else e'
E.g.
abs (-n) = n
abs n = n
x ^ (-n) = error "x^(-n) is undefined."
x ^0= 1
x ^1= x
x ^ (2*n+1) = x*xn*xn where xn = x^n
x ^ (2*n) =xn*xn where xn = x^n
x ^^ (-n) = 1/(x^n)
x ^^ n = x^n
/kent k
Re: n+k patterns
Original-Via: uk.ac.st-and.cs; Wed, 6 Nov 91 14:54:59 GMT
> > | Kent Karlsson asks:
> > | | Which semantics did you use?
> > |
> > | The following seemed sensible to me (Your first choice in each case):
> >
> > [ ... my attempt at a semantics for c*p and p+k patterns ... ]
> >
> >I had hoped not, since then a match can fail and fail the entier program,
> > even if a "later" patterns really matches, since in the above the "next"
> > pattern is not tested upon such a fail.
>
> I have been persuaded and would go along with Kent's proposed semantics
> for c*p and p+k patterns if these were introduced into the language.
> Specifically:
>
> | case e0 of {p+k -> e; _ -> e'}
> | either = if e0 >= k then case e0-k of {p -> e; _ -> e'} else e'
> | or = case e0-k of {p -> e; _ -> e'}
>
> But let's not use the second option here ... I'm a firm believer that (p+k)
> patterns should match only positive values.
>
> Note also that this includes the current semantics for Haskell n+k patterns
> as a special case (writing p as a variable which is guaranteed to match and
> simplifying the case expr on the rhs).
>
> | case e0 of {c*p -> e; _ -> e'}
> | either = if e0 >= 0 then case e0 `divRem` c of (p, 0) -> e; _ -> e'} else e'| or
> = case e0 `divRem` c of (p, 0) -> e; _ -> e'}
>
> The choice here isn't so clear. Should c*p patterns match only positive
> values (for uniformity with with p+k patterns, although there is no real
> need for the restriction in this case), or should we allow them to match
> arbitrary multiples of c? Perhaps someone with lots of examples of the
> use of c*p+k patterns could comment on which would be best? Tony?
>
> Thanks to Kent for straightening this out.
>
> Mark
>
I would be very much in favour of missing out the >= test in both n+k and
c*n+k. As Mark says there is no need for a restriction in the latter case.
In the former, the restriction is only there because of a wish to model
the Natural Numbers, a data type which is NOT native to Haskell.
Tony
Re: n+k patterns
Original-Via: uk.ac.ox.prg; Wed, 6 Nov 91 11:44:16 GMT
> | Kent Karlsson asks:
> | | Which semantics did you use?
> |
> | The following seemed sensible to me (Your first choice in each case):
>
> [ ... my attempt at a semantics for c*p and p+k patterns ... ]
>
>I had hoped not, since then a match can fail and fail the entier program,
> even if a "later" patterns really matches, since in the above the "next"
> pattern is not tested upon such a fail.
I have been persuaded and would go along with Kent's proposed semantics
for c*p and p+k patterns if these were introduced into the language.
Specifically:
| case e0 of {p+k -> e; _ -> e'}
| either = if e0 >= k then case e0-k of {p -> e; _ -> e'} else e'
| or = case e0-k of {p -> e; _ -> e'}
But let's not use the second option here ... I'm a firm believer that (p+k)
patterns should match only positive values.
Note also that this includes the current semantics for Haskell n+k patterns
as a special case (writing p as a variable which is guaranteed to match and
simplifying the case expr on the rhs).
| case e0 of {c*p -> e; _ -> e'}
| either = if e0 >= 0 then case e0 `divRem` c of (p, 0) -> e; _ -> e'} else e'| or
|= case e0 `divRem` c of (p, 0) -> e; _ -> e'}
The choice here isn't so clear. Should c*p patterns match only positive
values (for uniformity with with p+k patterns, although there is no real
need for the restriction in this case), or should we allow them to match
arbitrary multiples of c? Perhaps someone with lots of examples of the
use of c*p+k patterns could comment on which would be best? Tony?
Thanks to Kent for straightening this out.
Mark
Re: n+k patterns
Original-Via: uk.ac.nsf; Tue, 5 Nov 91 21:31:13 GMT Original-Sender: [EMAIL PROTECTED] Mark says: This problem isn't just restricted to pattern matching ... I'm interested in the assumptions that an implementation can legitimately make about the way overloaded functions behave. Other non-standard behaviour will affect the readability of the program, but will not give rise to complaints about compiler error. E.g. o n + 0 = n n * 1 = n If these properties don't hold, functions like sum, product, genericLength and so forth are going to give peculiar results. This, with most of the other examples, is a user's problem, because the system defined types behave sensibly. o Equality should be symmetric and transitive. Otherwise you're going to start wondering whether f 0 = 1; f n = n * f (n-1) is interpreted as f n = if n==0 then 1 else n * f (n-1) or f n = if 0==n then 1 else n * f (n-1) This is good example. Should the Report state how implementations are to translate matching of constant patterns? Or should it state that implementations are free to assume symmetry here? As in Brian's message, none of these properties can, in general, be guaranteed for arbitrary user-defined instances of a particular class: | While these hold for built-in types, there is no guarantee they hold for | all user-defined types with Integral instances, where the user is free to | define the various overloaded class operators IN ANY WAY WHATSOEVER. Does this mean we have to throw out the facilities for arbitrary user-defined instances? Absolutely not! Indeed, but we do need to state what properties implementations may assume, and while this is reasonable for small extensions to the language, it may become a problem for larger ones. My message was prompted more by Simon's response than by Tony's proposal. Personally, I favour an approach to programming with overloaded values in which each class declaration is accompanied by a number of laws which the operators of that class are expected to satisfy, and each instance declaration is accompanied by a `proof' that those laws are indeed satisfied for the particular instance involved. In reality, I would not expect most programmers to construct suitable proofs and it seems unreasonable to expect that the machines will (in general) be able to generate the proofs automatically. One compromise that might be worth considering is to extend the syntax of class declarations to include laws as part of the concrete syntax. This would have two benefits: a) the designer of a particular class has an opportunity to indicate his intentions about the way overloaded symbols behave, formally as part of the program. b) the Haskell type checker can be used to ensure that the stated laws are at least type safe. I agree. I'd like to see a discussion of this on this list. | Tony wants a c*n+k pattern to match a value v such that | v = c*n+k for some n >= 0, and then to bind n to (v-k) `div` c. | ... | For this to work sensibly, some laws must hold, e.g. | | (c * n) `div` c = n | (x `div` y) * y + (x `rem` y) = x | (n+k) - k = n I don't think these laws are particularly unreasonable... Nor I. But since they may not hold, implementations need to have the approval of the Report before assuming them. --brian PS I've been running Gofer here, and may use it for teaching next year, at least until the new Haskell implemetations appear, so please add me to your list of users (at both addresses). Brian Boutel, Usually [EMAIL PROTECTED], but currently [EMAIL PROTECTED] Phone (203) 432 1289
Re: n+k patterns
Original-Via: uk.ac.nsf; Mon, 4 Nov 91 17:00:37 GMT
> Kent Karlsson asks:
> | Which semantics did you use?
>
> The following seemed sensible to me (Your first choice in each case):
There was no ranking!
>
> For p+k patterns: (as in the report):
> case e0 of {p+k -> e; _ -> e'}
> = if e0 >= k then let {p = e0-k} in e else e'
>
> For c*p patterns:
> case e0 of {c*p -> e; _ -> e'}
> = if e0 >= 0 && e0 `rem` c == 0
> then let {p = e0 `div` c} in e
> else e'
>
I had hoped not, since then a match can fail and fail the entier program,
even if a "later" patterns really matches, since in the above the "next"
pattern is not tested upon such a fail. The ones I had hoped for was
one of the two last alternatives in each case (no ranking claimed among
these alternatives):
case e0 of {p+k -> e; _ -> e'}
either = if e0 >= k then case e0-k of {p -> e; _ -> e'} else e'
or = case e0-k of {p -> e; _ -> e'}
case e0 of {c*p -> e; _ -> e'}
either = if e0 >= 0 then case e0 `divRem` c of (p, 0) -> e; _ -> e'} else e'
or = case e0 `divRem` c of (p, 0) -> e; _ -> e'}
Here the "ensuing" patterns are given "a chance" to match, even if the
pattern (p) did not match after the subtraction/division.
/kent k
Re: n+k patterns
Original-Via: uk.ac.ox.prg; Mon, 4 Nov 91 13:52:20 GMT
Kent Karlsson asks:
| Which semantics did you use?
The following seemed sensible to me (Your first choice in each case):
For p+k patterns: (as in the report):
case e0 of {p+k -> e; _ -> e'}
= if e0 >= k then let {p = e0-k} in e else e'
For c*p patterns:
case e0 of {c*p -> e; _ -> e'}
= if e0 >= 0 && e0 `rem` c == 0
then let {p = e0 `div` c} in e
else e'
I think these would agree with Tony Davie's original proposal in the special
case of c*x+k patterns?
| Any syntactic restrictions on c or k (e.g. k >= 0, c >= 1)?
I think I had k>0, c>1, but I guess your limits are just as good.
| Note, I'm not opposing anything here, I'm just asking!
|
| /kent k
And I'm not suggesting that Haskell has p+k and c*p patterns.
I implemented them so that I could play with the ideas involved.
I'm not particularly convinced either way whether they should
be adopted or not.
Mark
Re: n+k patterns
X-Comment1: # X-Comment2: # uk.ac.glasgow.cs has changed to uk.ac.glasgow.dcs # X-Comment3: # If this address does not work please ask your mail# X-Comment4: # administrator to update your NRS & mailer tables. # X-Comment5: # In response to Tony Davie: Yes, generalising x+k pattens to c*x+k patterns is a possibility. An (x+k) pattern (with x a variable, and k a positive integral constant) matches the value i if i >= k, and binds x to (i-k). A (c*x+k) pattern (with x a variable, and c and k positive integral constants) matches the value i if i >= k and (i-k) `mod` c == 0, and binds x to (i-k) `div` c. I didn't suggest this extension because it wasn't clear that it had sufficient value to be worth the (small) extra complication. There seems to be no problem with it. -- P
Re: n+k patterns
Original-Via: uk.ac.nsf; Mon, 4 Nov 91 11:35:00 GMT
> Incidentally, I'd suggest that we have separate (c*n) and (n+k) forms of
> pattern ... extending the syntax of patterns to:
>
> pat ::= | int * pat | pat + k
>
> This would allow c*n+k patterns as a special case, but also permits other
> potentially useful constructions: (2*_+1). Even a pattern like (n,m)+1
> would make sense if you had an instance of the form Integral (a,b).
>
> What's more, using the two forms of pattern seems to give a cleaner system
> (I've just added it to Gofer and it seems fairly straightforward).
>
> Mark
>
Which semantics did you use?
case e0 of {p+k -> e; _ -> e'}
either = if e0 >= k then then let {p = e0-k} in e else e'
or = let {p = e0-k} in e
or = if e0 >= k then case e0-k of {p -> e; _ -> e'} else e'
or = case e0-k of {p -> e; _ -> e'}
(or something else?)
case e0 of {c*p -> e; _ -> e'}
either = if e0 >= 0 && e0 `rem` c == 0 then let {p = e0 `div` c} in e else e'
or = if e0 `rem` c == 0 then let {p = e0 `div` c} in e else e'
or = if e0 >= 0 then case e0 `divRem` c of (p, 0) -> e; _ -> e'} else e'
or = case e0 `divRem` c of (p, 0) -> e; _ -> e'}
(or something else?)
Any syntactic restrictions on c or k (e.g. k >= 0, c >= 1)?
Note, I'm not opposing anything here, I'm just asking!
/kent k
Re: n+k patterns
Original-Via: uk.ac.ox.prg; Fri, 1 Nov 91 18:04:12 GMT Brian Boutel writes: | With Haskell as it is currently defined, one can take an operational view, | that the syntactic translation given in the report defines the semantics | of n+k patterns, and too bad if the semantics of the introduced functions | are not what was expected. I suppose it would be possible to extend this | to other forms such as c*n+k patterns, but again givng specific | translations, but to generalise would require the compiler to assume | semantic properties of operators in order to derive inverse functions for | the extract-binder functions. This problem isn't just restricted to pattern matching ... After all, most Haskell programmers are going to expect certain properties of overloaded operator, regardless of the instances at which they are used: o Addition (+) and multiplication (*) are commutative. In addition, the standard prelude fixity declarations for these operators rely on an implicit assumption that they are associative. o n + 0 = n n * 1 = n If these properties don't hold, functions like sum, product, genericLength and so forth are going to give peculiar results. o Equality should be symmetric and transitive. Otherwise you're going to start wondering whether f 0 = 1; f n = n * f (n-1) is interpreted as f n = if n==0 then 1 else n * f (n-1) or f n = if 0==n then 1 else n * f (n-1) o Reading the string representation of a value of type in class Text which was originally produced by show, really ought to give the same value back (i.e. read . show = id) otherwise we cannot guarantee being able to write programs which store data in text files to be read back by other programs some time later. o All kinds of other familiar properties for other familiar operators... As in Brian's message, none of these properties can, in general, be guaranteed for arbitrary user-defined instances of a particular class: | While these hold for built-in types, there is no guarantee they hold for | all user-defined types with Integral instances, where the user is free to | define the various overloaded class operators IN ANY WAY WHATSOEVER. Does this mean we have to throw out the facilities for arbitrary user-defined instances? Absolutely not! Personally, I favour an approach to programming with overloaded values in which each class declaration is accompanied by a number of laws which the operators of that class are expected to satisfy, and each instance declaration is accompanied by a `proof' that those laws are indeed satisfied for the particular instance involved. In reality, I would not expect most programmers to construct suitable proofs and it seems unreasonable to expect that the machines will (in general) be able to generate the proofs automatically. One compromise that might be worth considering is to extend the syntax of class declarations to include laws as part of the concrete syntax. This would have two benefits: a) the designer of a particular class has an opportunity to indicate his intentions about the way overloaded symbols behave, formally as part of the program. b) the Haskell type checker can be used to ensure that the stated laws are at least type safe. | Tony wants a c*n+k pattern to match a value v such that | v = c*n+k for some n >= 0, and then to bind n to (v-k) `div` c. | ... | For this to work sensibly, some laws must hold, e.g. | | (c * n) `div` c = n | (x `div` y) * y + (x `rem` y) = x | (n+k) - k = n I don't think these laws are particularly unreasonable... Incidentally, I'd suggest that we have separate (c*n) and (n+k) forms of pattern ... extending the syntax of patterns to: pat ::= | int * pat | pat + k This would allow c*n+k patterns as a special case, but also permits other potentially useful constructions: (2*_+1). Even a pattern like (n,m)+1 would make sense if you had an instance of the form Integral (a,b). What's more, using the two forms of pattern seems to give a cleaner system (I've just added it to Gofer and it seems fairly straightforward). Mark
Re: n+k patterns
Original-Via: uk.ac.ed.mrcvax; Fri, 1 Nov 91 14:00:30 GMT > | Which leads me to one final comment. Does the Report say anywhere that > | an overflow gives rise to an undefined result? > > Yes it does (though you may not like the answer!). See Section 6.8.1, p56. > > Simon The relevant sentence states: "The results of exception conditions (such as overflow or underflow) on the fixed-precision numeric types are undefined; and implementations may choose error (bottom, semantically), a truncated value, or a special value such as infinity, indefinite, etc" Surely this is unacceptable? It is unavoidable that a program might run on one implementation and fail on another, but is it not a basic principle of the language that two implementations will deliver identical results if they deliver results at all? Ian
Re: n+k patterns
X-Comment1: # X-Comment2: # uk.ac.glasgow.cs has changed to uk.ac.glasgow.dcs # X-Comment3: # If this address does not work please ask your mail# X-Comment4: # administrator to update your NRS & mailer tables. # X-Comment5: # Yes it does (though you may not like the answer!). See Section 6.8.1, p56. Simon | Which leads me to one final comment. Does the Report say anywhere that | an overflow gives rise to an undefined result?
Re: n+k patterns
Original-Via: uk.ac.ed.mrcvax; Fri, 1 Nov 91 10:03:45 GMT | Which leads me to one final comment. Does the Report say anywhere that | an overflow gives rise to an undefined result? | | Tony Good question! I think it should, though I fear the efficiency implications. Ian
Re: n+k patterns
Original-Via: uk.ac.st-and.cs; Fri, 1 Nov 91 09:37:40 GMT Brian says there are two distinct problems with n+k patterns, 1) That laws relating * `div` `rem` + - might not hold. 2) A user defined >= might not be strict giving rise to a match of bottom to a refutable pattern converging. The second one could be 'solved` by changing the operational semantics of n+k patterns so that it didn't include the test. I suppose the reason why it was included was that n+k (usually n+1) patterns are traditionally associated with primitive recursive definitions of functions over the natural numbers rather than the integers. But Haskell doesn't have Nat as a `base` type, (though users could define it --- and then get the benefits of exactly the pattern match they needed). I'm not sure if Haskell even has Int as a base type -- or even Bool. Should a user really be allowed to redefine the operators on these types? The first of the problems above could possibly be solved by disallowing n+k patterns from being overloaded and insisting they be of BUILT-IN type Int. Though come to think of it, Ints don't obey the div,rem,*,+,- laws if an overflow is involved. Which leads me to one final comment. Does the Report say anywhere that an overflow gives rise to an undefined result? Tony
Re: n+k patterns
Original-Via: uk.ac.nsf; Fri, 1 Nov 91 01:19:12 GMT
Simon says:
This is certainly technically feasible. As it happens, our compiler is set
up so that it is easy to compile any pattern which you can express as a
predicate function ("does it match?") plus an extract-binder function ("tell
me the value of n, given the value of the arg").
The remaining issue is the usual judgement of language complexity vs
expressiveness. Myself, I like it.
Simon
In principle I like the idea of having more powerful pattern matching
constructs in Haskell, but unfortunately there is a problem with this
idea. Well, not just with this idea, but with the present language as
well.
Tony wants a c*n+k pattern to match a value v such that
v = c*n+k for some n >= 0, and then to bind n to (v-k) `div` c.
The predicate is then v >= k && (v-k) `rem` c == 0,
and the extract-binder is (v-k) `div` c.
(with suitable applications of fromInteger added).
For this to work sensibly, some laws must hold, e.g.
(c * n) `div` c = n
(x `div` y) * y + (x `rem` y) = x
(n+k) - k = n
While these hold for built-in types, there is no guarantee they hold for
all user-defined types with Integral instances, where the user is free to
define the various overloaded class operators IN ANY WAY WHATSOEVER.
This is even a problem with ordinary n+k patterns, where the
report implies a translation of f (n+1) = e
to something equivalent to
f v = if v >= 1 then (\n -> e) (v-1) else ...
and the definitions of + and - may be such that (v-1)+1 /= v.
In general, there is now way to construct the extract-binder function
without knowing inverses for the operations in the pattern, and inverse
functions are generally not known.
With Haskell as it is currently defined, one can take an operational view,
that the syntactic translation given in the report defines the semantics
of n+k patterns, and too bad if the semantics of the introduced functions
are not what was expected. I suppose it would be possible to extend this
to other forms such as c*n+k patterns, but again givng specific
translations, but to generalise would require the compiler to assume
semantic properties of operators in order to derive inverse functions for
the extract-binder functions.
Another related problem:
The report says (3.12.2) "Matching bottom against a refutable pattern
always diverges."
Not necessarily. Suppose in the above example, the user-defined Ord
instance makes >= non-strict. This is another example of unusual
behaviour in user-defined instances giving unexpected semantics.
I think pattern-matching needs a big rethink.
--brian
| From: Tony Davie <[EMAIL PROTECTED]>
| Date: Wed, 30 Oct 91 17:04:28 GMT
|
|
| It seems to me that some of the most useful arithmetic divide and
| conquer algorithms express a function of an integer n in terms of
| the same function applied to n `div` 2. Has any thought been given to
| generalising n+k patterns to c*n+k patterns? If these were allowed we
| would be able to express, for instance, the well known algorithm for
| raising numbers to an integer power by:
|
| x^0 = 1
| x^(2*n) = xn*xn where xn = x^n
| x^(2*n+1) = x * x^(2*n)
Re: n+k patterns
X-Comment1: #
X-Comment2: # uk.ac.glasgow.cs has changed to uk.ac.glasgow.dcs #
X-Comment3: # If this address does not work please ask your mail#
X-Comment4: # administrator to update your NRS & mailer tables. #
X-Comment5: #
This is certainly technically feasible. As it happens, our compiler is set
up so that it is easy to compile any pattern which you can express as a
predicate function ("does it match?") plus an extract-binder function ("tell
me the value of n, given the value of the arg").
The remaining issue is the usual judgement of language complexity vs
expressiveness. Myself, I like it.
Simon
| From: Tony Davie <[EMAIL PROTECTED]>
| Date: Wed, 30 Oct 91 17:04:28 GMT
|
|
| It seems to me that some of the most useful arithmetic divide and
| conquer algorithms express a function of an integer n in terms of
| the same function applied to n `div` 2. Has any thought been given to
| generalising n+k patterns to c*n+k patterns? If these were allowed we
| would be able to express, for instance, the well known algorithm for
| raising numbers to an integer power by:
|
| x^0 = 1
| x^(2*n) = xn*xn where xn = x^n
| x^(2*n+1) = x * x^(2*n)
