Re: Proposal: Change semantics of pattern matching

From: Wolfgang Lux <lux_at_wi.uni-muenster.de>
Date: Wed, 25 Oct 2000 12:26:51 +0200

Michael Hanus <mh_at_informatik.uni-kiel.de> wrote:

> [...]
> Thus, "eval choice" only influences the completeness of
> the operational semantics but not the declarative semantics.

Ok. I agree on that.

> [...]
> > with more than argument or nested arguments? For example, 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
>
> From my point of view, this is a bad programming style
> since the pattern matching with top-to-bottom order
> makes it difficult to understand the evaluation order.
> For instance, one would assume that a goal like (foo B inf)
> would evaluate to 1 due to the third rule, but it does
> not terminate if "inf" is a nonterminating computation.
> Using default rules and Jaime's proposal of auxiliary
> functions, I would rewrite this as
>
> foo A _ = 0
> foo B _ = 1
> default foo x y = foo_ x y
> where foo_ _ A = 0
> foo_ _ B = 1
> default foo_ _ _ = 2

But this is wrong because now foo B A returns 1 while it should
return 0. In order to get the intended semantics of foo you have
to use a few more default rules (like Jaime's translation does).

> [...]
>
> Therefore, I am very much in favor of introducing default
> rules syntactically (if I remember right, there was no
> serious argument against this) but without an extension
> of existing backends. This could be done, for instance,
> by the following proposal:
>
> - Allow at most one default rule per function f which has the form
> default f x1...xn = e (or default f x1...xn | c = e)
> i.e., default rules always have the most general pattern
> (several default rules are seldom(?) and could be introduced
> by auxiliary functions, see above)
>
> - Define the meaning of a default rule "default f x1...xn = e" as the set
> of rules "f \sigma(x1...xn) = \sigma(e)" where \sigma(x1...xn)
> is a pattern not covered by another rule for f
> (this notion must be made more precise; intuitively, this means
> that we fill all undefined branches in a definitional tree
> with this default rule)
>
> - Do not allow or-branches in the presence of default rules
> (this could be weakened by issuing a warning but the
> example above shows that the combination of or-branches and
> default rules results in complicated code)

I do not object to this addition. But still I would like to have some
more syntactic sugar for the definition of functionslike foo. Taking
up a suggestion of Mario, we could introduce case expressions to
perform such "top-down" pattern-matching. Using the default rules
extension an obvious translation for case expressions into the Kernel
of Curry which performs this pattern matching would be as follows:

  case e of {} => failed
  case e of { t -> e'; alts } =>
    let f t = e'
        default f x = case x of { alts }
    in f e

where f and x are fresh names which do not occur in e, e', t, and alts.
The extension to guarded patterns and local definitions in case
alternative should be obvious.

Thus my foo example could now be written as

foo x y =
  case (x,y) of
    (A,_) -> 0
    (_,A) -> 0
    (B,_) -> 1
    (_,B) -> 1
    (_,_) -> 2

Regards
Wolfgang

P.S.: I just noticed that the failed function is no longer in the
standard prelude. Is there any reason for that?


--
Wolfgang Lux				  Phone: +49-251-83-38263
Institut fuer Wirtschaftinformatik	    FAX: +49-251-83-38259
Universitaet Muenster		      Email: wlux_at_uni-muenster.de
_______________________________________________
curry mailing list
curry_at_lists.RWTH-Aachen.DE
http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry
Received on Wed Oct 25 2000 - 12:36:30 CEST

This archive was generated by hypermail 2.3.0 : Mon Nov 18 2019 - 07:15:05 CET