Performance issues with unintepreted functions and sorts about cvc5 HOT 7 OPEN

Thanks for the benchmark.

The reason for the difference in performance is that we use a very different version of enumeration when the synthesis conjecture involves multiple functions to synthesize.

In particular, for conjectures with multiple functions-to-synthesize, we use "smart" enumeration by default.

The output tag -o sygus-enumerator will show this, with/without the extra synth-fun:

% cvc5 issue10708.sy -o sygus-enumerator
(sygus-enumerator :synth-fun aType :role MULTI_SOLUTION :type SMART)
(sygus-enumerator :synth-fun bType :role MULTI_SOLUTION :type SMART)
(sygus-enumerator :synth-fun cType :role MULTI_SOLUTION :type SMART)
(sygus-enumerator :synth-fun X :role MULTI_SOLUTION :type SMART)
^Ccvc5 interrupted by user.

% cvc5 issue10708.sy -o sygus-enumerator
(sygus-enumerator :synth-fun X :role POOL :type FAST)
(sygus-enumerator :synth-fun X :role POOL :type FAST)

For the latter, 2 fast enumerators are allocated, which is for decision tree learning (role POOL). This technique is only available when a single function-to-synthesize is present.

For details on these techniques and when we choose fast vs. smart, see this paper: https://homepage.divms.uiowa.edu/~ajreynol/cav19b.pdf

In principle, we could do an optimization here to recognize when the conjecture does not contain a function-to-synthesize, where the "dummy" synth-fun will essentially be ignored in this example. This is something I can add.

from cvc5.

FYI, I opened a PR to address performance issues for unconstrained functions.

There are some issues to address concerning values for uninterpreted sorts.

from cvc5.

Hi!
Thanks a lot for the quick response and the reading material! I will go through the paper (and the CVC5 one, so I have info from there) and see what my translation may break
I will try the PR to see how it works and if I hit any more performance issues. Can you explain a little more about the issues for uninterpreted sorts? I am open to investing some time (a couple of days) into helping fix some lower-hanging fruits (apologies if it sounds naively optimistic that I can help).

from cvc5.

I tested that PR and got the expected performance. Thanks a lot!
I would also like to mention another case that is weird for me (or possibly because I have a different interpretation of the input).

(synth-fun X ((x Int) (y Int)) Int
  ((Start Int) (StartBool Bool))
  ((Start Int (0 1 2 3 4 5 6 x y
               (+ Start Start)
               (- Start Start)
               (ite StartBool Start Start)))
   (StartBool Bool ((and StartBool StartBool)
                    (not StartBool)
                    (= Start Start)
                    (<= Start Start))))
)


(synth-fun aType () Int)
; alternative
;(synth-fun aType () Int
;  ((Start Int) (StartBool Bool))
;  ((Start Int (0 1 2 3 4 5 6 
;               (+ Start Start)
;               (- Start Start)
;               (ite StartBool Start Start)))
;   (StartBool Bool ((and StartBool StartBool)
;                    (not StartBool)
;                    (= Start Start)
;                    (<= Start Start))))
; )

;(assume (= aType 0)) <- breaks correctness
;(constraint (= aType 0)) <- is okay

(constraint (= (X 2 0) 1)) 
(constraint (and (= (X 0 1) 5)  (= (X 0 0) 6)))

I want to use assume to assume some universal quantifier constraints and a couple such equalities. The quantifiers were okay (albeit with an expected speed cost which is in the change of the solver). The moment I include this sort of statement and things break and the value for X becomes 0. Is this normal? Thank you in advance!

from cvc5.

assume is a command that is used to give a precondition on the entire synthesis conjecture, so (assume (= aType 0)) means "My synthesis conjecture is only relevant when aType is 0". A trivial way to satisify this is to make aType anything except 0.

from cvc5.

The issue with "uninterpreted sort values" is that uninterpreted sorts do not have a fixed interpretation. For example, if one asserts:
(constraint (forall ((x U)) (= x a)))
where a : U, then the interpretation of U must contain exactly one element.

Thus, it may be unsound to refer to values of type U (beyond the first one) since they may not even exist in a model.

This poses issues when using (Constant U) in sygus grammars. In general, cvc5 will instead use "dummy" free constants when this is specified, which can lead to unintuitive behavior. We may disallow (Constant U) for this purpose.

from cvc5.

I see. These issues make sense. In a way the SMT setup of this and the Sygus behavior diverge and I kind of see why it has to be like that. Thanks a lot! Then, one (possibly last) question out of curiosity: How can one encode properties of uninterpreted functions as a way to represent axioms for said function in sygus?

from cvc5.