Re: Type-classes and call-time choice vs. run-time choice

From: Sebastian Fischer <sebf_at_informatik.uni-kiel.de>
Date: Fri, 28 Aug 2009 15:38:21 +0200

On Aug 27, 2009, at 11:55 AM, Wolfgang Lux wrote:

> A while ago, Sebastian Fischer made me aware of a subtle bug in the
> type-classes branch of MCC [...]
> This bug is easily explained by MCC's internal translation of
> type-classes, which uses the common dictionary approach. [...]
> Curry's call-time choice semantics means that the
> argument of the [dictionary] constructor [...] -- unintentionally --
> is shared [...]
> I believe it is a serious shortcoming of Curry [...]

Wolfgang goes on to propose two possible Curry extensions:

> For instance, one could extend the expression
> syntax with
> BasicExpr ::= ... | ({ Expr }) | ...
> where an expression ({ e }) is evaluated with run-time choice.
> [...]
> However, I'm a bit reluctant to such a change because it destroys
> the property that a variable in a function always refers to a
> single value.

I share your reluctance because I like the property that variables
denote values. Hence, I would also prefer your more modest proposal

> to restrict run-time choice to specially marked arguments of data
> constructors

where the exceptions to this rule are less intrusive.

In general, I would like to see some possibility for selective eval-
time choice in Curry. There are examples where ETC is preferable over
CTC like the regular expression matcher Sergio mentions in his paper
on "Evaluation Strategies for Functional Logic Programming" [1] I
consider the technique to introduce dummy arguments in order to avoid
sharing a hack which is only necessary because Curry lacks an
appropriate feature.

Incidentally, Wolfgangs proposal to add annotations to arguments of
data constructors (which prevent the annotated arguments from being
shared if the constructed value is shared) seems to be easily
expressible in the framework for monadic explicit sharing [2].

I have encoded Wolfgangs dictionary example in this framework [3] and
tried this other example to challenge my (and your) intuition about
the proposed extension. What should be the results of test1 and test2?

     data ETC a = ETC ?a

     dup :: a -> (a,a)
     dup x = (x,x)

     test1 = dup (ETC (False?True))

     shareInside :: Bool -> (ETC (Bool,Bool), ETC (Bool,Bool))
     shareInside x = dup (ETC (x,x))

     test2 = shareInside (False?True)

The explicit-sharing library computes these results:

     test1 ~> (ETC F,ETC F)
            ? (ETC F,ETC T)
            ? (ETC T,ETC F)
            ? (ETC T,ETC T)

     test2 ~> (ETC (F,F),ETC (F,F))
            ? (ETC (T,T),ETC (T,T))

So, arguments of constructors annotated using ? can still incorporate
sharing, especially, the sharing of 'x' in the definition of
'shareInside' is not destroyed by wrapping 'x' inside ETC.

No I am the third who refers to his own work when commenting on
Wolfgangs proposal. What are the differences between annotating

   - specific arguments of constructors in data-type declarations
(Wolfgang)
   - all arguments in specific function declarations (Juan)
   - specific (pattern?) variables (Bernd)

With respect to implementing such annotations I observe that I could
easily implement Wolfgangs approach. Of course, that is no convincing
argument to prefer it over the others. However, I wonder what is
special about the data centric approach that lets it stand out in this
respect.

Cheers,
Sebastian

[1]: http://web.cecs.pdx.edu/~antoy/homepage/publications/jsc/paper.pdf
[2]: http://sebfisch.github.com/explicit-sharing/
[3]: http://gist.github.com/176983

-- 
Underestimating the novelty of the future is a time-honored tradition.
(D.G.)
_______________________________________________
curry mailing list
curry_at_lists.RWTH-Aachen.DE
http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry
Received on Fr Aug 28 2009 - 18:15:11 CEST

This archive was generated by hypermail 2.3.0 : Sa Dez 07 2019 - 07:15:09 CET