Re: Smap: Collecting small programs

From: David Powers <david.powers_at_flinders.edu.au>
Date: Fri, 31 Oct 2014 02:35:47 +0000

Thanks very much for this Michael,

On 31 Oct 2014, at 3:28 am, Michael Hanus <mh_at_informatik.uni-kiel.de<mailto:mh_at_informatik.uni-kiel.de>> wrote:

Hi David,

this is only a partial answer to all the issues you pointed out.

3/4. There are issues relating to free variables and unification models
that prevent translation from Prolog.
...

In principle, any *logic program* can be translated to Curry
in a straightforward manner. However, for Prolog with all its
non-logic features, it is different.

Even adding in ensureNotFree doesn’t help as all disjunctions can suspend…
I do have a working (sicstus/swipl) Prolog version of this!

Just a comment: ensureNotFree only suspends computations but can't
be used as a case distinction. Hence, you can't do a case distinction
on difference lists (similar to logic programming) so that difference
lists should only be used for producing results. For instance,
the reverse operation takes a standard list and produces a difference
list:

revD :: [a] -> DList a
revD [] = (m#m) where m free
revD (x:xs) = appD (revD xs) (x:m # m) where m free

with difference list concatenation defined by

appD (a#b) (b#n) = (a#n)

In a similar way, you can also define quicksort with difference lists.

This is the nub of the problem. And why I zapped the differences to [].
The problem I was having came from unification with DLists in where tuples.
And yes I see that ensureNotFree doesn’t make sense in a Curry guard.
But in Prolog the blocking constructs do act as guards (delaying not failing).

My Prolog sorts are all cut/not/if/assert-free pure logic programs.
Some (notably permsort) use blocking and/or transformation (to quadratic).

I have tried two-way and three-way quicksorts in your Curry Dlist style:
viz. using the explicit call to appD to do the appending;
with fromD mapping back to a list before recursing quicksort...

http://www-ps.informatik.uni-kiel.de/smap/smap.cgi?28

This functional/generation style works but I’d still like to use a
more efficient logical/unification style (involving where patterns).

Cheers,
David


Best regards,

Michael
_______________________________________________
curry mailing list
curry_at_lists.RWTH-Aachen.DE<mailto:curry_at_lists.RWTH-Aachen.DE>
http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry




_______________________________________________
curry mailing list
curry_at_lists.RWTH-Aachen.DE
http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry
Received on Fri Oct 31 2014 - 15:37:12 CET

This archive was generated by hypermail 2.3.0 : Thu Sep 19 2019 - 07:15:09 CEST