SBV ve Haskell kullanarak kanıtlayan sembolik teori

Question

Bazı teori geliştiricileri oluşturmak için Haskell'de SBV (Z3 arka uçlu) kullanıyorum. Verilen kısıtlarla (x + y = y + x, +'un "artı operatörü" olduğu gibi) x ve y forall olup olmadığını kontrol etmek istiyorum, diğer bazı terimler geçerlidir. + ifadesi ile ilgili aksiyomları tanımlamak istiyorum (ilişkilendirme, kimlik gibi) ve daha sonra a + (b + c) == (a + c) + b'un geçerli resmi a, b ve c geçerli olup olmadığını kontrol edin.

ben gibi bir şey kullanarak gerçekleştirmek için çalışıyordu:

main = do 
    let x = forall "x" 
    let y = forall "y" 
    out <- prove $ (x .== x) 
    print "end" 

Ama biz sembolik değerlere .== operatörünü kullanamazsınız görünüyor. Bu eksik bir özellik mi yoksa yanlış kullanım mı? Bunu bir şekilde SBV kullanarak yapabilir miyiz?

Answer 1

Hakkında bilgi edinmek için bilgisayar korsanlığı sitesinde sağlanan örneklerin birçoğuna göz atmanızı tavsiye ederim. Bu tür bir mantık yürütme, gerçekten yorumlanamayan türler ve işlevler kullanılarak yapılabilir. Bununla birlikte, bu tür yapılara ilişkin akıl yürütmenin genellikle sayısallaştırılmış aksiyomlar gerektirdiği konusunda uyarılmalıdır ve SMT-çözücüler, niceleyicilerle akıl yürütmede genellikle çok iyi değildir.

Bunu söyledikten sonra, SBV'yi kullanarak bunu nasıl yapacağım. Bunu yaptığınızda

{-# LANGUAGE DeriveDataTypeable #-} 

import Data.Generics 
import Data.SBV 

-- Uninterpreted type T 
data T = TBase() deriving (Eq, Ord, Data, Typeable, Read, Show) 
instance SymWord T 
instance HasKind T 
type ST = SBV T 

, bir Uninterpreted tip T ve sembolik muadili ST erişebileceksiniz:

Birincisi, bazı kazan plakalı kod Uninterpreted tip T olsun. sağ türleri ile yine sadece Uninterpreted sabitleri plus ve zero, beyan edelim:

-- Uninterpreted addition 
plus :: ST -> ST -> ST 
plus = uninterpret "plus" 

-- Uninterpreted zero 
zero :: ST 
zero = uninterpret "zero" 

Şimdiye kadar, SBV söylenen tüm bir tür T ve bir işlev plus ve sabit zero varolduğudur; açıkça yorumlanmıyor. Yani, SMT çözücü, verilen türlere sahip oldukları gerçeğinden başka hiçbir varsayım yapmaz.

Let ilk 0+x = x kanıtlamak için deneyin: Ne SMT çözücü anlatıyor özelliği olmasıdır

*Main> bad 
Falsifiable. Counter-example: 
    s0 = T!val!0 :: T 

: Bu denerseniz

bad = prove $ \x -> zero `plus` x .== x 

, aşağıdaki yanıtı alırsınız tutmaz, ve burada tutulmadığı bir değer.T!val!0 değeri, bir Z3 spesifik yanıttır; diğer çözücüler başka şeyler geri verebilir. Aslında, T türünde bir habitant için dahili bir tanımlayıcıdır; ve bunun dışında hiçbir şey bilmiyoruz. Bu, elbette çok yararlı değil çünkü aslında plus ve zero için hangi ilişkilendirmelerin yapıldığını bilmiyorsunuz, ancak beklenecek.

Özelliği kanıtlamak için SMT çözücüsüne iki şey daha söyleyelim. İlk olarak, plus değişkendir. Ve ikincisi, sağa eklenen zero o hiçbir şey yapmaz. Bunlar addAxiom çağrıları ile yapılır. Ne yazık ki, SBV, Haskell kullanılarak yazılmış aksiyomları desteklemediğinden (en azından henüz), aksiyomlarınızı SMTLib sözdiziminde yazmalısınız. Not Ayrıca biz burada Symbolic monad kullanmaya geçiş: Biz çözücüsü x+y = y+x ve x+0 = x söyledi ve bunu sordu nasıl

good = prove $ do 
     addAxiom "plus-zero-axioms" 
        [ "(assert (forall ((x T) (y T)) (= (plus x y) (plus y x))))" 
        , "(assert (forall ((x T)) (= (plus x zero) x)))" 
        ] 
     x <- free "x" 
     return $ zero `plus` x .== x 

Not 0+x = x kanıtlamak için. Bu şekilde aksiyomları yazmak SMTLib sözdizimini kullanmanız gerektiğinden çok çirkin görünüyor, ama bu şu anki durum.

*Main> good 
Q.E.D. 

nicel aksiyomlar ve Uninterpreted-türleri/fonksiyonlar değil SBV arayüzü üzerinden kullanımı en kolay şeyler var, ama bu şekilde bunun dışında bazı kilometre alabilirsiniz: Şimdi var. Eğer aksiyomlarınızda çok miktarda niceleyiciniz varsa, çözücünün sorgularınıza cevap vermesi olası değildir; ve muhtemelen unknown yanıt verecektir. Her şey kullandığınız çözücüye ve kanıtlanacak özelliklerin ne kadar zorlandığına bağlıdır.

Answer 2

API kullanımınız tam olarak doğru değil. Matematiksel eşitlikleri kanıtlamanın en basit yolu basit fonksiyonları kullanmaktır. Eğer daha programlı bir arayüze ihtiyaç (ve bazen olacak) ise

prove $ \x y z -> x + (y + z) .== (x + y) + (z :: SInteger) 

, o zaman Symbolic monad kullanabilirsiniz, thusly:

plusAssoc = prove $ do x <- sInteger "x" 
         y <- sInteger "y" 
         z <- sInteger "z" 
         return $ x + (y + z) .== (x + y) + z 

Örneğin, sınırsız Tamsayılar üzerinde birleşebilirlik bu şekilde ifade edilebilir

API: https://hackage.haskell.org/package/sbv