core.logic

fd/* and fd/+ interaction bug

Details

  • Type: Defect Defect
  • Status: Closed Closed
  • Priority: Major Major
  • Resolution: Completed
  • Affects Version/s: None
  • Fix Version/s: None
  • Component/s: None
  • Labels:
    None

Description

Via this StackOverflow question http://stackoverflow.com/questions/15671823/unexpected-results-with-clojure-core-logic-using-clp-fd

(defn product-pluso [factor1 factor2 number sum]
  (fd/eq (= sum (+ number (* factor1 factor2)))))

(run* [x y]
  (fd/in x y (fd/interval 1 38))
  (product-pluso x y 2 40))

Returns too many answers. Even if we desugar into:

(run* [q]
  (fresh [x y p]
    (fd/in x y (fd/interval 1 38))
    (fd/* x y p)
    (fd/+ p 2 40)
    (== q [x y p])))

We see results which clearly violate the fd/+ constraint.

Activity

Hide
David Nolen added a comment -

To be clear get-dom has different contract than walk - get-dom will return a not found value instead of a logic var. It would be nice to be able to return nil but we could image CLP(Set) and other cases where the possible values includes nil.

Show
David Nolen added a comment - To be clear get-dom has different contract than walk - get-dom will return a not found value instead of a logic var. It would be nice to be able to return nil but we could image CLP(Set) and other cases where the possible values includes nil.
Hide
David Nolen added a comment -

After digging into this some it looks like we have a fairly nice opportunity to refactor and make things considerably faster. In the Scheme version get-dom / walk are necessarily separate operations because of the implementation. This is not necessary in core.logic because of SubstValue. get-dom should always do the right thing - return the value in the substitution if present or domain otherwise. The constraint writers need not bother with walk at all.

Show
David Nolen added a comment - After digging into this some it looks like we have a fairly nice opportunity to refactor and make things considerably faster. In the Scheme version get-dom / walk are necessarily separate operations because of the implementation. This is not necessary in core.logic because of SubstValue. get-dom should always do the right thing - return the value in the substitution if present or domain otherwise. The constraint writers need not bother with walk at all.
Hide
David Nolen added a comment -

It seems like we should be able to fix this at the level of update-var-dom by checking that the var doesn't already have a value in the substitution, but oddly by doing this we run into some strange non-termination behavior. I've experienced this before when trying to flip the order of checks in let-dom, but at the time I was too busy with bigger problems to look at the issue more closely.

Show
David Nolen added a comment - It seems like we should be able to fix this at the level of update-var-dom by checking that the var doesn't already have a value in the substitution, but oddly by doing this we run into some strange non-termination behavior. I've experienced this before when trying to flip the order of checks in let-dom, but at the time I was too busy with bigger problems to look at the issue more closely.

People

Vote (0)
Watch (0)

Dates

  • Created:
    Updated:
    Resolved: