Search code examples
functionz3smtz3pyinference

z3py: how to make constraints for "else" value when inferring a function


I am inferring a function using z3py as follows

f = Function('f',IntSort(),IntSort(),IntSort())

After asserting a set of constraints like:

s.add(f(a1,b1)==c1)
s.add(f(a2,b2)==c2)
s.add(f(a3,b3)==c3)...

The function is inferred as

[(a1,b1) -> c1,
(a2,b2) -> c2,
(a3,b3) -> c3,
...,
else -> 2]

How could I constraint the "else" value to a fixed number? So that the output of inferred f will be

[(a1,b1) -> c1,
(a2,b2) -> c2,
(a3,b3) -> c3,
...,
else -> some number that I assert]

Edit:

from z3 import *

s = Solver()
k = Int('k')
f = Function('f',IntSort(),IntSort())

s.add(And(f(1)==1,f(2)==2))

list1 = []
list1.append(k!=1)
list1.append(k!=2)
s.add(ForAll(k,Implies(And(list1),f(k)==5)))

print s.check()
print s.model()

The output is

sat
[f = [1 -> 1, 2 -> 2, else -> 5]]

This seems to work fine for this simple case.

However, when the input for function 'f' in the constraints is undecided. The output can be weird. For example

from z3 import *

s = Solver()

f = Function('f',IntSort(),IntSort(),IntSort())

i = Int('i')
j = Int('j')
k = Int('k')
l = Int('l')


s.add(i>=0,i<5)
s.add(j>=0,j<5)

s.add(And(f(j,1)==i,f(i,2)==j))

list1 = []
list1.append(And(k==1,l==j))
list1.append(And(k==2,l==i))
s.add(ForAll([k,l],Implies(Not(Or(list1)),f(l,k)==5)))

print s.check()
print s.model()

The output is

[i = 0,
 k!6 = 0,
 j = 3,
 k!12 = 6,
 f = [else -> f!15(k!13(Var(0)), k!14(Var(1)))],
 f!15 = [(3, 1) -> 0, (0, 2) -> 3, else -> 5],
 k!13 = [0 -> 0, 3 -> 3, else -> 6],
 k!14 = [2 -> 2, 1 -> 1, else -> 0]]

Then it is hard to interpret the inferred f.


Solution

  • It is a great question and very informed analysis. Yes, you can control the default values by using quantifiers. Z3 will have no choice but agree. However, the encoding of models is based on how the quantifier instantiation engine (see Complete quantifier instantiation by Yeting Ge and Leonardo de Moura). Z3 does not beta-reduce the expressions in the models and has left it to applications to perform the beta-reduction, if desired. You can have Z3 beta reduce else branches by plugging in your arguments to the parameters of the functions (use the substitution routines exposed by the API), and then call the model evaluator to reduce the resulting expression with respect to the model.