Re: Invertible nondeterminism?

From: Sebastian Fischer <sebf_at_informatik.uni-kiel.de>
Date: Fri, 17 Dec 2010 08:38:51 +0900

Hi Sergio,

thank you for the example.

On Thu, 2010-12-16 at 11:45 -0800, Sergio Antoy wrote:
> All right. I think I am getting it, and it is an interesting and
> elegant idea. Can the following be a less contrived example?
>
> Suppose a robot moves in an integer plane stepping 1 unit along
> either axis direction, but is not allowed to step on the origin.
> Could you define a move as
>
> move (x,y) = (x-1,y)
> ? (x+1,y)
> ? (x,y-1)
> ? (x,y+1)
> ? anti (0,0)

Yes, this would work.

> This could be better than some other coding alternatives, except
> maybe the constrained constructor pattern.

I should look into other uses of the constrained constructor pattern to
see how a solution using anti would compare.

> However, there may be a drawback from an implementation
> standpoint. Evaluating choices is already expensive. With the
> new meaning, it would become even more expensive.
>
> With the traditional meaning, any solution, say s, of x in x?y can
> be immediately used, e.g., output. With the new meaning, before
> using s, one should compute all the solution of x and y, to make
> sure that an anti s is not found.

I agree. In fact, my current implementation only works for finite
solutions spaces for this reason and cannot express my oddNat example.

At the moment, however, I'm more interested in new "design patterns"
that anti-results would allow. I'm happy to postpone implementation
details until later.

Best regards,
Sebastian

_______________________________________________
curry mailing list
curry_at_lists.RWTH-Aachen.DE
http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry
Received on Fri Dec 17 2010 - 11:10:17 CET

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