[Agda] Parallel or
Alan Jeffrey
ajeffrey at bell-labs.com
Wed Nov 16 20:39:54 CET 2011
A niave question about dependent pattern-matching...
One of the problems I keep hitting in writing Agda programs is having to
choose an order for pattern matches, because of the fall-through
semantics. The prototypical example is boolean or:
_or_ : Bool -> Bool -> Bool
true or y = true
x or true = true
false or false = false
This definition of or gives true as a left unit up to beta-reduction,
but true as a right unit only up to propositional equality. (Ditto the
units for natural addition, list concatenation, etc. etc.)
I have a half-baked idea that the semantics of pattern-matching could
instead be nondeterministic, so any pattern that matches does so and
causes beta-reduction, without worrying about if it is masked by an
earlier case. In the case above, (M or true) would reduce to true, even
if M is a (meta-)variable.
Of course to get normalization, the compiler would have to check
critical pairs and ensure syntactic identity of the rhs, and I can
imagine that this might be painful.
Has anyone already baked (or burned) this idea?
A.
More information about the Agda
mailing list