Re: MIU in Curry

From: Michael Hanus <>
Date: Fri, 26 Apr 2013 18:38:38 +0200

On 04/26/2013 01:46 PM, Wolfgang Jeltsch wrote:
> Anyway, I have now rewritten the applyRules function in a traditional
> inductive style:
>> applyRules :: [Rule] -> Str -> [Str]
>> applyRules [] _ = []
>> applyRules (rule : rules) str = let
>> str' = applyRule rule str
>> in str' : applyRules rules str'
> Unfortunately, the program still doesn’t work.

Since it was unclear to us why this program does not work,
we made some experiments. It seems that this is actually
an efficiency bug(?) of KiCS2 due to a complicated combination
of functional patterns, unification, and search space explosion.
If we try to separate these things, it works quite well,
but the combination of all seems to cause a combinatorial explosion
of the representation and traversal of the computation space.
For instance, if we fix the number of rule applications,
PAKCS (based on backtracking) computes the solutions much
faster than KiCS2.

Currently, we have no concrete idea of the reasons causing
this problem, but, indeed, it is an interesting example
to test many aspects of our implementation.

Best regards,

curry mailing list
Received on Fr Apr 26 2013 - 18:40:21 CEST

This archive was generated by hypermail 2.3.0 : Mo Dez 04 2023 - 07:15:13 CET