# Understanding computational complexity of CHR head selection **URL:** \ **Category:** General\ **Created:** [December 4, 2023, 5:06pm UTC](https://swi-prolog.discourse.group/t/understanding-computational-complexity-of-chr-head-selection/7028 "2023-12-04T17:06:30Z")\ **Posts on this page:** 7\ **Page:** 1
**Author:** ![meditans](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/meditans/32/1768_2.png) [@meditans](https://swi-prolog.discourse.group/u/meditans)\ **Post date:** [December 4, 2023, 5:06pm UTC](https://swi-prolog.discourse.group/t/understanding-computational-complexity-of-chr-head-selection/7028/1 "2023-12-04T17:06:30Z")
I’m a bit confused about term indexing in CHR constraints. The question I have stems from a sentence in the [famous CHR tutorial slides](https://dtai.cs.kuleuven.be/CHR/files/tutorial_iclp2008.pdf) in which it is asserted (slide 151) that ```prolog foo(a, Y), foo(a, Z) ==> more stuff.. ``` means: ```prolog foo(X,Y), foo(W,Z) ==> X==W | more stuff... ``` I’d like to know if that equivalence is true only in a semantical sense, or also in an operational one. In the first case, I can call `foo(a,X), foo(a,Y)` and pay a price that goes with the square of the number of `a`s, in the second case, I would have to pay a price proportional to the square of `foo/2` constraints. In other words, can we expect the usual good indexing behavior that we have in prolog also in CHR rules? ---
**Author:** ![meditans](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/meditans/32/1768_2.png) [@meditans](https://swi-prolog.discourse.group/u/meditans)\ **Post date:** [December 5, 2023, 9:55pm UTC](https://swi-prolog.discourse.group/t/understanding-computational-complexity-of-chr-head-selection/7028/2 "2023-12-05T21:55:07Z")
Here’s is an experiment to test a couple of possibilities: ```prolog :- use_module(library(chr)). :- chr_constraint foo/1, twice/1. foo(X), foo(X) ==> twice(X). prepare_foo :- numlist(0,10,Xs), maplist(foo, Xs). study_foo :- chr_notrace, prepare_foo, chr_trace, foo(6). :- chr_constraint bar/1, adjacent/2. bar(X), bar(Y) ==> X #= Y+1 | adjacent(X,Y). prepare_bar :- numlist(0,10,Xs), maplist([X]>>(X1 is 2*X+1, bar(X1)), Xs). study_bar :- chr_notrace, prepare_bar, chr_trace, bar(10). ``` It seems to me from reading the chr\_traces that the CHR store is never trying all the constraints before finding the right rule. Does this mean that the CHR store is indexed in this case, or am I reading this wrong @jan ? ---
**Author:** ![jan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jan/32/4_2.png) [@jan](https://swi-prolog.discourse.group/u/jan)\ **Post date:** [December 6, 2023, 10:36am UTC](https://swi-prolog.discourse.group/t/understanding-computational-complexity-of-chr-head-selection/7028/3 "2023-12-06T10:36:21Z")
> [@meditans](#): > > Does this mean that the CHR store is indexed in this case, or am I reading this wrong @jan ? Don’t ask me 🙂 The CHR version in SWI-Prolog is mostly the PhD Thesis work of Tom Schrijvers. He surely wrote publications on it 🙂 But yes, AFAIK the store uses a hash index to find candidate constraints. Don’t ask for the details … ---
**Author:** ![meditans](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/meditans/32/1768_2.png) [@meditans](https://swi-prolog.discourse.group/u/meditans)\ **Post date:** [December 6, 2023, 11:47am UTC](https://swi-prolog.discourse.group/t/understanding-computational-complexity-of-chr-head-selection/7028/4 "2023-12-06T11:47:16Z")
Thanks, wasn’t sure who to ping! Pinging @TomSchrijvers then! 😊 ---
**Author:** ![TomSchrijvers](https://avatars.discourse-cdn.com/v4/letter/t/f19dbf/32.png) [@TomSchrijvers](https://swi-prolog.discourse.group/u/TomSchrijvers)\ **Post date:** [December 6, 2023, 3:23pm UTC](https://swi-prolog.discourse.group/t/understanding-computational-complexity-of-chr-head-selection/7028/5 "2023-12-06T15:23:32Z")
Hi meditans, To answer your initial question, the equivalence of the behavior mentioned in that presentation does not concern performance. My CHR compiler uses some indexing structures, but when and how they are used is quite different from Prolog. Is there a particular use case you are concerned about? Best, Tom ---
**Author:** ![meditans](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/meditans/32/1768_2.png) [@meditans](https://swi-prolog.discourse.group/u/meditans)\ **Post date:** [December 6, 2023, 7:05pm UTC](https://swi-prolog.discourse.group/t/understanding-computational-complexity-of-chr-head-selection/7028/6 "2023-12-06T19:05:13Z")
Hi, thank you very much for your answer. My question stems from the fact that I lack a clear operational model, an thus I often fear of writing non-performant code. The examples I have come from the bottom-up parsing world, in which constraints in the head are deterministically related, but not simply by variable unification. Something like: ```prolog foo(X), foo(Y) ==> X #= Y+1 | more... ``` or ```prolog foo(X), foo(Y), foo(Z) ==> computation(X,Y,Z) | more... ``` in which `X` determines `Y` and both together determine `Z` in `computation`. In this case above, for example, would I be paying a cost proportional to the cube of the number of `foo` constraints? Another example: imagine I have two types of points in the (lattice) 2D plane, `a/1`, and `b/1`, and I want to do something based on adjacency. For example, I might have: ```prolog a(X1-Y1), b(X2-Y2) :- adjacent(X1-Y1, X2-Y2) | more... ``` obviously, given an `a`, there is only a certain number of `b` locations that I should check, but does the code do that? Or does it try every combination (which could be unacceptable for some problems)? And how do I determine which is the case? Bonus question: is there a mechanism with which I could decide dynamically which _rules_ are active in a chr computation? Or, start two computations with the same constraints but slightly different rules? ---
**Author:** ![meditans](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/meditans/32/1768_2.png) [@meditans](https://swi-prolog.discourse.group/u/meditans)\ **Post date:** [December 17, 2023, 12:09pm UTC](https://swi-prolog.discourse.group/t/understanding-computational-complexity-of-chr-head-selection/7028/7 "2023-12-17T12:09:20Z")
@TomSchrijvers in case you missed the reply above 🙂