Re: Language changes: Committed choice

From: Frank Steiner <steiner_at_informatik.rwth-aachen.de>
Date: Tue, 27 Oct 1998 17:24:27 +0100

Dear Herbert,

Herbert Kuchen wrote:

> If we assume that we are interested in a lazy polymorphic
> version of merge, then the present syntax does not
> adequately enable this.

Ok, I do agree with your comments on my little-bit-lazy merge.

But I disagree about the rest, i.e.

> You are right that providing committed choice as a third evaluationannotation
> is less powerful than the present concept. The question
> is whether you really need to have committed choice based on arbitrary
> constraints in practical applications. I doubt that. In fact, I think
> that typical programs use committed choice at very few places
> and that all of them can be handled by the approach using evaluation
> annotations. In most (if not all) cases, it will be possible to just
> replace func1 and func2 by func1' and func2' of type a -> Bool
> and the boolean result could be used for "pattern matching" (with
> annotation "choice").

I still believe that there are cases where arbitrary constraints
as guards of a committed choice expressions are neccessary, e.g. in
the function 'one' defined in the prelude:

  one :: (a->Constraint) -> [a->Constraint]
  one g = dfs \x -> {x = choice {g y} -> y where y free}

The idea is to use the fair strategy of choice to find a solution
in a real fair manner. But here the constraint type in the guard
is neccessary if we want to stay compatible with the other
search algorithms. This example also shows that non-determinism
during evaluation of a choice guard is a wanted feature and therefore
must be considered as it can be easily done in Michaels proposal.

Michael Hanus wrote:

> The general idea of a committed choice is to evaluate the different
> guards (or pattern matching tasks) locally and then commit to
> a successful guard. Thus, I propose the following operational
> behavior for a function call with evaluation annotation "choice":
>
> Evaluate this function call as usual (with a fair evaluation of
> alternatives) but
> - do not bind variables occurring in this call
> - ignore all alternatives if one rule matches and its guard is
> entailed (i.e., satisfiable without binding goal variables)

I think that this is a good way to go because it combines the
the advantage of pattern matching with the power of the old
choice.

Best regards,

Frank


-- 
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Dipl.-Inform. Frank Steiner   
  Lehrstuhl fuer Informatik II
  RWTH Aachen, D-52056 Aachen
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  Phone:  +49 241 80-21241
  Fax:    +49 241 8888-217
  mailto: steiner_at_informatik.rwth-aachen.de
  http://www-i2.informatik.rwth-aachen.de/steiner/
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Received on Tue Oct 27 1998 - 17:25:00 CET

This archive was generated by hypermail 2.3.0 : Wed Sep 18 2019 - 07:15:04 CEST