/* 
 * Fibonacci(topdown) in CHR(chr)
 * Author: Seiji OGAWA, 2011-03-31
 *
 * Examples are taken from:
 *   http://dtai.cs.kuleuven.be/CHR/examples.shtml
 *
 * If you'd like to change parameter N, 
 * please change the 1st argument of query: start("N").
 *
 */

:- use_module(library(chr)).

:- chr_constraint 
  fibonacci(+dense_int, +dense_int),
  start(+int),
  time/1.
:- chr_option(optimize, full).
%:- chr_trace.

unify @ fibonacci(N,M1) # ID \ fibonacci(N,M2) <=>  M1 = M2 pragma passive(ID).
fib1 @ fibonacci(0,M) ==> M = 1.
fib2 @ fibonacci(1,M) ==> M = 1.
fib3 @ fibonacci(N,M) ==>
	N > 1 | 
		N1 is N-1,
		fibonacci(N1,M1),
		N2 is N-2,
		fibonacci(N2,M2),
		M is M1 + M2.

start(S) <=>
  cputime(X),
  fibonacci(S, M),
  cputime(Y),
  Z is Y-X,
  time(Z).

time(_) \ fibonacci(_, _) <=> true.