LeventErkok / sbv

SMT Based Verification in Haskell. Express properties about Haskell programs and automatically prove them using SMT solvers.
https://github.com/LeventErkok/sbv
Other
240 stars 33 forks source link

Improve renderSMTFunction #663

Closed LeventErkok closed 1 year ago

LeventErkok commented 1 year ago

Current implementation of renderSMTFunction only works for non-recursive definitions. We need a better variant that can handle both recursive and non-recursive ones, so long as they're named. We probably want to change the whole API for this, shouldn't need a name or anything like that, just take a definition that's been defined with smtFunction. Given:

import Data.SBV

foo, bar :: SInteger -> SInteger
foo = smtFunction "foo" (\a -> bar a + 1)
bar = smtFunction "bar" (\a -> foo a + 1)

We currently get:

*Main> putStrLn =<< renderSMTFunction "foo" foo
; -- user given definition: foo [Recursive]
(define-fun-rec foo ((l1_s0 Int)) Int
  (foo l1_s0))

I'm not sure why this is actually rendered as such. The actual output is:

*Main> satWith z3{verbose=True} $ \x -> foo x .== 5
** Calling: z3 -nw -in -smt2
[GOOD] ; Automatically generated by SBV. Do not edit.
[GOOD] (set-option :print-success true)
[GOOD] (set-option :global-declarations true)
[GOOD] (set-option :smtlib2_compliant true)
[GOOD] (set-option :diagnostic-output-channel "stdout")
[GOOD] (set-option :produce-models true)
[GOOD] (set-logic ALL) ; has unbounded values, using catch-all.
[GOOD] ; --- uninterpreted sorts ---
[GOOD] ; --- tuples ---
[GOOD] ; --- sums ---
[GOOD] ; --- literal constants ---
[GOOD] (define-fun s2 () Int 5)
[GOOD] ; --- top level inputs ---
[GOOD] (declare-fun s0 () Int)
[GOOD] ; --- constant tables ---
[GOOD] ; --- non-constant tables ---
[GOOD] ; --- arrays ---
[GOOD] ; --- uninterpreted constants ---
[GOOD] ; --- user defined functions ---
[GOOD] ; -- user given mutually-recursive definitions: bar, foo
[GOOD] (define-funs-rec
         ((bar ((l2_s0 Int)) Int)
          (foo ((l1_s0 Int)) Int))
         (; Definition of: bar. [Refers to: foo]
          (let ((l2_s2 1))
          (let ((l2_s1 (foo l2_s0)))
          (let ((l2_s3 (+ l2_s1 l2_s2)))
          l2_s3)))
          ; Definition of: foo. [Refers to: bar]
          (let ((l1_s2 1))
          (let ((l1_s1 (bar l1_s0)))
          (let ((l1_s3 (+ l1_s1 l1_s2)))
          l1_s3)))))
[GOOD] ; --- assignments ---
[GOOD] (define-fun s1 () Int (foo s0))
[GOOD] (define-fun s3 () Bool (= s1 s2))
[GOOD] ; --- arrayDelayeds ---
[GOOD] ; --- arraySetups ---
[GOOD] ; --- delayedEqualities ---
[GOOD] ; --- formula ---
[GOOD] (assert s3)
[SEND] (check-sat)
[RECV] unsat
*** Solver   : Z3
*** Exit code: ExitSuccess
Unsatisfiable

Need to accomplish the same directly from a function API.