Fwd: [Agda] Parallel or

Alan Jeffrey ajeffrey at bell-labs.com
Thu Nov 17 16:27:58 CET 2011


The problem with or-patterns is that if they still have fall-through 
semantics, then defining:

 >       or True _ || or _ True = True
 >       or False False = False

gives True as the left and right zero for or, but doesn't give False as 
a unit, compared with:

   true  or y     = true
   x     or true  = true
   false or y     = y
   x     or false = x

which would give both zeros and units.

A.

On 11/17/2011 01:21 AM, wren ng thornton wrote:
> On 11/16/11 4:39 PM, Alan Jeffrey wrote:
>> Of course this would come with its own problems, e.g. checking critical
>> pairs may be expensive, throws up algorithmic issues (e.g. checking
>> unification of critical pairs may include recursive calls to the
>> function being checked, eeks) and it's yet another syntactic
>> approximation to a semantic property. So I can well believe there is a
>> tar-pit there.
>
> Alternatively, rather than trying to automatically determine the
> equivalence of the RHS, we could enforce it syntactically / require it
> intensionally by introducing or-patterns a la OCaml. Thus,
>
>       or True _ || or _ True = True
>       or False False = False
>
> (using whatever syntax you'd prefer.)
>
> That's still just a syntactic approximation to semantic properties, but
> at least it's a relatively decent syntactic approximation instead of
> something completely ad hoc.
>
>
>
> Yet a different alternative is that we could take the masking as a
> feature rather than a burden. Thus defining,
>
>       or False False = False
>       or _ _ = True
>
> In theory, given (or x y) if we can prove either x=True or y=True, then
> we should be able to force the whole expression to evaluate to True.
> This approach would also work for addition on naturals. However, it
> doesn't scale as well as the or-pattern option, because it's not clear
> how to get it to cover non-atomic cases like
>
>       mplus Nothing (Just x) || mplus (Just x) Nothing = Just x
>
> and the moral equivalents, where we're binding variables but we don't
> care about exactly where they come from.
>


More information about the Agda mailing list