Re: Proposal: Change semantics of pattern matching

From: Jaime Sánchez Hernández <>
Date: Tue, 03 Oct 2000 15:03:34 +0200


we are currently working on failure in functional logic programming (for
those interested, see [1]) since we think that language constructions to
express and manage failure should be useful in FLP, as it happens with
negation as failure in logic programming. One of such constructions are
Juanjo's default rules ([2]) and we agree with Michael when he suggests to
use them. With default rules the definition of a function f (of, say, arity
2) might take the form (for simplicity, we write here unconditional rules)

   f t1 s1 = e1
   ... (t1,tn,s1,sn are patterns, e1,en,e expressions)
   f tn sn = en
   default f x y = e

with the intuitive (operational) meaning: to reduce (f e e'), proceed with
the n first equations, as in a 'normal' definition. If the reduction fails,
then use the default rule.

>how is the
>following Haskell function translated into a deterministic Curry
>function with default rules?
> data T = A | B | C | D
> foo A _ = 0
> foo _ A = 0
> foo B _ = 1
> foo _ B = 1
> foo _ _ = 2

This can be done by using auxiliary functions, each using a default rule:

foo A _ = 0
default foo x y = foo' x y
        where foo' _ A = 0
              default foo' x y = foo'' x y
              where foo'' B _ = 1
                    default foo'' x y = foo''' x y
                    where foo''' _ B = 1
                          default foo''' x y = foo'''' x y
                          where foo'''' _ _ = 2

Of course, some syntactic support (e.g, to allow consecutive default rules)
could be provided in the language to avoid such complicated definitions.

Nevertheless there is a problem with default rules:

As mentioned by Michael, the default rule does not have an equational reading
in itself, because its meaning depends on the previous rules. Things are
better (with respect to this issue) if we express default rules by means of a
new, more general construction , to express failure:

    fail e ::= succeedes if the expression e fails to be reduced

The definition
   f t1 s1 = e1
   f tn sn = en
   default f x y = e

can be now written as
   f t1 s1 = e1
   f tn sn = en
   f x y = e <== fail (f' x y) (conditional rule, probably in wrong
Curry syntax; sorry for that)
         where f' t1 s1 = e1
               f' tn sn = en

and all the rules for f, including the last one, have a declarative reading
by themselves.
The original default rule syntax could be seen as syntactic sugaring.

[1] F.J. Lopez-Fraguas, J. Sanchez-Hernandez: Proving Failure in
Logic Programs, CL2000, LNAI 1861, 179-193.
[2] J.J. Moreno-Navarro: Extending constructive negation for partial
functions in lazy functional-logic languages, ELP'96,LNAI 1050, 213-227.
(Juanjo has also a previous paper for non-lazy functions in ICLP'95).


Jaime Sanchez Hernandez, Francisco Javier Lopez Fraguas
Dep. Sistemas Informaticos y Programacion
Universidad Complutense de Madrid


curry mailing list
Received on Mi Okt 04 2000 - 08:39:29 CEST

This archive was generated by hypermail 2.3.0 : Do Aug 06 2020 - 07:15:04 CEST