Re: On the textual order of rules

From: Nikolay Orlyuk <virkony_at_gmail.com>
Date: Thu, 27 Mar 2014 15:41:02 +0200

Hi,

I think that Currey doesn't know that (1 + (1 + ...) + (1 + ...)) =:= 3
can't succeed and there is no reason to walk further.
Without any additional information that will cut off branch that definitely
can't unify there is infinite amount of try/backtrack.
When you treat infinite you that depends on from which side you treat it.
In original code you try to calculate infinitely long tree at beginning and
thus you wait infinite amount of time.
In second variant you walk starting from "1".

As I know Curry have special meaning for order of declaration. And this
behavior totally suits it (in a same way as _ ? _ generates first and then
second).


You may want to consider using Nat to represent size. That may cut-off
branch with 4+ size automatically due to (Succ (Succ (Succ (Succ _)))) =:=
(Succ (Succ (Succ Zero))) can't succeed. But I'm not sure if that will work
out.

Cheers



On Wed, Mar 26, 2014 at 12:33 PM, Yi D <plmday_at_gmail.com> wrote:

> Hi,
>
> Some time ago, we had a group discussion about the paper Functional
> Logic Programming<https://www.informatik.uni-kiel.de/~mh/publications/papers/CACM10.pdf>.
> In the 2nd paragraph on Page 5, it goes:
>
> To fully support non-determinism, in a functional logic program the
> textual order of the rules defining an operation is irrelevant.
>
> Curiously, one of our group members tried the following code:
>
>
> data BTree = Leaf Int | Branch BTree BTree
>
> size :: BTree -> Int
> size (Branch l r) = 1 + size l + size r
> size (Leaf _) = 1
>
> in the online interpreter with the following query:
>
> size t =:= 3 where t free
>
> but got time out. However, after switching the order of the two rules,
> he got the expected answer. Suspecting the solution needs longer time
> than 5 seconds, I installed PAKCS (which is the implementation running
> behind the web interface) locally and tried the same code with the same
> query, it diverged! This clearly violates the statement quoted above.
> I searched through the documentation but could not find any explicit
> statement like the one quoted above regarding the textual order of rules.
> Afterward, I installed the KiCS2 implementation of Curry, tried the same
> code and query, and got the expected answer. Then we were confused, the
> two implementations have different behavior of the same language. What
> should we expect? Is the statement quoted above a feature or functional
> logic language or not?
>
> Later, I found out that PAKCS compile Curry code to Prolog while KiCS2
> targets Haskell. So it seems that the behavior of PAKCS is due to the
> inheritance of the (mis-)feature of Prolog. But the question remains:
> What is the expected behavior of the Curry language we should expect?
>
> Best,
>
> Yi
>
> _______________________________________________
> curry mailing list
> 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 Do Mär 27 2014 - 15:09:44 CET

This archive was generated by hypermail 2.3.0 : Do Feb 01 2024 - 07:15:11 CET