Re: Proposal: Change semantics of pattern matching

From: Michael Hanus <mh_at_informatik.uni-kiel.de>
Date: Tue, 24 Oct 2000 15:17:47 +0200 (MEST)

Sorry for the delay, but now I want to follow up the discussion
on default rules and pattern matching for Curry (which we
also discussed at the WFLP'00).

Wolfgang wrote to my suggestion of introducing default
rules instead of a special eval annotation:

> But we already have eval choice in the language, which *does* change
> the declarative meaning of the program.

I might be interesting to clarify (my view of) the "eval choice":
I think that this does not change the declarative meaning
of a function but restricts the completeness of the operational
semantics. Since one does not know which rule of a function
defined by several rules with "eval choice" is taken at run time,
each rule must be valid in the intended model. This means
that the intended model consists of the union of all choices
but the "choice" annotation forces the implementation to take
at most one rule and ignore all others, i.e., some of the
solutions in the intended model might not be computed.
Thus, "eval choice" only influences the completeness of
the operational semantics but not the declarative semantics.

> I don't know Juanjo's proposal. How does it generalize to functions
> 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

Therefore, it is questionable whether the first code is
clearer than the second. At least, the evaluation strategy
becomes clearer with the second code since now (foo B inf)
indeed reduces to 1.

Jaime's proposal of using a failure function to express
default rules is also interesting and a very general approach
to this problem, but it has the disadvantage that this requires
a significant extension of the underlying machinery.

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)

This proposal has the advantage that default rules are a purely
syntactic abbreviation for a set of rules in the kernel language.
Thus, existing backends and the computation model of Curry need
no extension. Furthermore, no fixed order is required for default
rules, i.e., we could also define a function by

  default foo _ _ = 0
  foo A _ = 1
  foo B C = 2

which is synactic sugar for the definition

  foo A _ = 1
  foo B C = 2
  foo C _ = 0
  foo D _ = 0
  foo B A = 0
  foo B B = 0
  foo B D = 0

I don't know whether there are important applications of default
rules not covered by this proposal, so please let me know.

Best regards,

Michael

_______________________________________________
curry mailing list
curry_at_lists.RWTH-Aachen.DE
http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry
Received on Tue Oct 24 2000 - 15:30:28 CEST

This archive was generated by hypermail 2.3.0 : Mon Sep 23 2019 - 07:15:05 CEST