Re: On the textual order of rules

From: Sebastian Fischer <sebf_at_informatik.uni-kiel.de>
Date: Thu, 27 Mar 2014 14:19:29 +0100

Hi Yi,

I see a distinction between the "Curry language" and "Curry
implementations". Regarding the language (semantics), the order of
rules is irrelevant. But some implementations let you observe the
order of rules by the order in which results are computed. If the
implementation uses an incomplete search strategy (like PAKCS does),
this sometimes has the effect that you observed - that some or all
results are missing. This effect is due to non-termination of
depth-first search in an infinite search space.

To summarize, rule order is relevant in certain Curry implementations
but irrelevant as far as the language is concerned. Regarding your
introductory quote, incomplete Curry implementations do not "fully
support non-determinism".

Best,
Sebastian

On Wed, Mar 26, 2014 at 11:33 AM, Yi D <plmday_at_gmail.com> wrote:
> Hi,
>
> Some time ago, we had a group discussion about the paper Functional
> Logic Programming. 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:35 CET

This archive was generated by hypermail 2.3.0 : Do Jun 20 2024 - 07:15:12 CEST