Re: Pattern guards.

[Kent Karlsson <kent>]

Original-Via: uk.ac.nsf; Tue, 9 Oct 90 14:09:33 BST
From: Kent Karlsson <kent>
Date: Tue, 9 Oct 90 13:59:07 +0100
To: haskell@cs.yale.edu
Subject: Re: Pattern guards.
Original-Sender: kent%se.chalmers.cs@yale.edu
Sender: haskell-request@cs.glasgow.ac.uk

> accommodate more expressive guards, but it is certainly a topic worth
> pursuing for Haskell 2.  I suppose that's what you're doing?

Yes.

>       The report does not say whether duplicate identifiers in patterns
>    are allowed or not, 
> 
> The Report says clearly that they are NOT allowed -- patterns must be
> "linear".

OK, I missed that...  

> 
>       Making things smaller does *not* necessarily make it simpler.
>    (Otherwise we would probably write our programs as bit-patterns in
>    some standardized machine code... :-)  The system must have integrity
>    for it to have simplicity.  If you make cutaways that destroy the
>    integrity, then the result will inevitably be complicated.
> 
> Lots of philosophy here...:-)

(So intended :-)

> 
> OK, here's a nice simple property:
> 
>    Argument order may always be changed without changing the scope of ids.
> 
> This property holds under the current proposal, but not under yours.
> Seems a shame.

1. Yes, but I still would not recommend a programmer to use a guard 
   "in the middle" of a pattern unless it's "necessary".
   
2. Under my (hinted) proposal it's best to make all variables bound by
   a pattern "unbound" at the start of the pattern, thus catching
   any scope problems as static errors.
   
3. My proposal allows for a simple and straightforward explanation of
   the patterns in e.g. "f 0 0 = ...".  And since duplicate identifiers
   are not allowed in patterns, it's still easy *in my proposal* to write
   their equivalent.  If that cannot easily be done in Haskell currently,
   then that seems a shame...

4. Here is another nice simple property:
     Argument order may always be changed without changing the strictness
     properties.
   This is not true in the current proposal... (nor in mine).
   
> 
>    > than to keep things simple, the chief objection being the following:
>    >   x = 1
>    >   f y | (x>1) x = x+y
>    > Does the x in the guard refer to f's formal parameter or the outer x?
> 
>    It cannot possibly refer to f's second formal parameter, it has not been
>    bound yet!  
> 
> yes, by YOUR definition of "bound".
> 
>    It can refer to the outer x, or it can (better yet) be illegal.
>    This is perhaps a bit clearer when using another example:
> 	     f y | (x>1)   (SOME_CONSTRUCTOR x) = x+y
>    The pattern for the second argument must not be matched before the
>    evaluation of the guard ...
> 
> Why not?  (I'm not saying it should, just asking for the rationale
> behind your decision.) 

Because that may change the strictness properties of some function
definitions.  E.g. (quoting my first note on this matter):
| h 0 (C1 x) = ...
| ===
| h   0                           (C1 x)   = ...
| ===
| h   y | (y == fromInteger 0)    (C1 x)   = ...
| 
| If the guard was to be moved to the end:
| 
| h   y                           (C1 x)   | (y == fromInteger 0) = ...
| 
| the "pattern matching" would be done "from right to left" in this example, 
| if it was the "h 0 (C1 x) = ..." clause that was transformed into
| "h y (C1 x) | (y == fromInteger 0) = ...", whereas Haskell specifies that
| it should be done from left to right, which is still the case with
| "h y | (y == fromInteger 0) (C1 x) = ..."

Evaluating a guard "where it stands" would also be what a neophite expects.

>                        For example, consider:
> 
>   f ~(SOME_CONSTRUCTOR x) | x>1 = ...
> 
> Here the match was "lazy" but the guard forced it to be "strict" -- so
> already one must understand the subtleties of what gets matched when.

1. I think ~-patterns are a hack, and I try to avoid them.

2. But if you can give *easy* translations of patterns with numerals, e.g.
   "f 0 0 = ...", using ~-patterns, and *easily* write the equivalent
   of duplicate identifiers in a pattern using ~-patterns, etc.,        (****)
   then so be it, and I will withdraw my proposal.  (My only goal
   is simplicity, believe it or not! :-)

> 
>       In general a guard can only depend upon things that are bound where
>    the guard occurs.
> 
> Of course; but again I ask: by what definition of bound?

Informally:
A variable in a guard in an "lhs" (or "pat") part of a
clause (or case entry) is bound if

- it's bound outside of the "lhs" (or "pat") and not (re)bound
  *by* the "lhs" (or "pat") nor *by* a where-definition attached
  to the clause (or case entry), or
  
- it's bound *by* the "lhs" (or "pat") *"to the left of"* the guard, or

- it's bound *by* a where-definition *attached to the clause (or
  case entry)*  *and* its definition only depends upon variables
  bound in the guard (note the greatest fixed point assumed here), or

- it's bound by a where-definition attached to (the appropriate part
  of) the guard.  (Recall that a guard is an expression...)



Remarks:
* Under no circumstances would I recommend a programmer to attach a
  where-definition directly to (a part of) a guard!

* Only a small part of this is unnecessary if you succeed with (****)
  above. :-)

* The 'and not (re)bound *by* the "lhs"...'-part is there in order
  to catch scope errors statically.

* the variables bound *in* a where-definition are:
  - the variables bound outside of the where-definition (though some of them
    may be *re*bound by the where-definition)
  - the variables bound *by* the where-definition
  - the variables bound by a where-definition attached to (the appropriate
    part of) the expressions in the where-definition.
  (but this is as it used to be.)
  
* E.g. in  "g  x | G1  y | G2  z | G3  = ..."
  x is available in G1, x and y in G2, and x, y, and z in G3.

* This is in accordance with the rule that pattern matching is
  done from left to right in Haskell.  This binding rule is probably
  what a neophite would expect, having heard the pattern matching rule...

* For clarity maybe parenthesis should be used (esp. if guards occur inside
  patterns...):  "g  (x | G1)  (y | G2)  (z | G3)  = ..."
     But you maybe have some grammars for this in stock...


> 
>    This would hold also if there is a where-definition
>    attached to the clause ((as opposed to just the expression...)).  So, in
> 	   g  x | (G1)  y | (G2) = ...
> 	   where   z1 = ...y...
> 		   z2 = ...x... -- no occurence of y, nor of z1
>    z1 may not occur in G1
> 
> Why not? 

Since y is still unbound in G1, and the definition of z1 depends upon y!

>          Are you proposing that a static error should result?

Yes.

> 
>    (since y is still unbound; *of course* it should *not* refer 
>    to an outer y), 
> 
> Why not?  

If y in the definition of z1 could refer to an outer y, then z1
would have different meanings in G1 and G2 (since in G2, y has been bound),
I'm sure that that would be *very* unexpected!

> 
>    but it may occur in G2 (since y has then been bound).
>    z2 may occur in both G1 and G2 though.
> 
> Your proposal is sounding more and more complex every minute.

Yes, we're getting into the same problems as with comments:
The simple solution *looks* much more complicated than
the very complicated solutions (which *look* very simple)!  (:-!)

(You can still choose the really simple solution:
 - (Repeated variables are already banned.)
 - Ban "n+k"-patterns.
 - Ban numeral patterns...			:-)

> It was for reasons such as these that we chose the current design.
> 
> (Hopefully it's clear that I'm just playing devil's advocate here:
> tell me what the binding rules are, and convince me that they are
> simple enough for the neophite.  If you succeed I may support the
> proposal for Haskell 2.)
> 
>   -Paul

		/kent k