2b4130336e941b7d01c78a6da55449a4c6eca609Till Mossakowski{- |

2b4130336e941b7d01c78a6da55449a4c6eca609Till MossakowskiModule : $Header$

2b4130336e941b7d01c78a6da55449a4c6eca609Till MossakowskiDescription : Derive induction schemes from sort generation constraints

2b4130336e941b7d01c78a6da55449a4c6eca609Till MossakowskiCopyright : (c) Till Mossakowski, Rainer Grabbe and Uni Bremen 2002-2006

2b4130336e941b7d01c78a6da55449a4c6eca609Till MossakowskiLicense : GPLv2 or higher, see LICENSE.txt

2b4130336e941b7d01c78a6da55449a4c6eca609Till Mossakowski

2b4130336e941b7d01c78a6da55449a4c6eca609Till MossakowskiMaintainer : till@informatik.uni-bremen.de

2b4130336e941b7d01c78a6da55449a4c6eca609Till MossakowskiStability : provisional

2b4130336e941b7d01c78a6da55449a4c6eca609Till MossakowskiPortability : portable

2b4130336e941b7d01c78a6da55449a4c6eca609Till Mossakowski

59d823de481014f68b8b024474bffac150b56e1eWiebke HerdingWe provide both second-order induction schemes as well as their

cc6df32dd55910aac7de12b30cc5049d96b8f770Wiebke Herdinginstantiation to specific first-order formulas.

2b4130336e941b7d01c78a6da55449a4c6eca609Till Mossakowski-}

e4e1509ff358e739fddf1483ad39467e0e1becc2Christian Maeder

e4e1509ff358e739fddf1483ad39467e0e1becc2Christian Maedermodule CASL.Induction (inductionScheme, generateInductionLemmas) where

e4e1509ff358e739fddf1483ad39467e0e1becc2Christian Maeder

e4e1509ff358e739fddf1483ad39467e0e1becc2Christian Maederimport CASL.AS_Basic_CASL

e4e1509ff358e739fddf1483ad39467e0e1becc2Christian Maederimport CASL.Sign

e4e1509ff358e739fddf1483ad39467e0e1becc2Christian Maederimport CASL.Fold

e4e1509ff358e739fddf1483ad39467e0e1becc2Christian Maederimport CASL.Quantification (flatVAR_DECLs)

c36c47428b2f42fe09eab533acf6be19d6d9f259Wiebke Herdingimport CASL.ToDoc

10e8873de4a89035222d077fe80b9fd7b9631473Wiebke Herding

cc6df32dd55910aac7de12b30cc5049d96b8f770Wiebke Herdingimport Common.AS_Annotation as AS_Anno

b1f52a36d45c5031c462291e263cec114975add1Wiebke Herdingimport Common.Id

b1f52a36d45c5031c462291e263cec114975add1Wiebke Herdingimport Common.Utils (combine, number)

b1f52a36d45c5031c462291e263cec114975add1Wiebke Herding

b1f52a36d45c5031c462291e263cec114975add1Wiebke Herdingimport qualified Data.Set as Set

b1f52a36d45c5031c462291e263cec114975add1Wiebke Herdingimport Data.List

2b4130336e941b7d01c78a6da55449a4c6eca609Till Mossakowskiimport Data.Maybe

2b4130336e941b7d01c78a6da55449a4c6eca609Till Mossakowski

b1f52a36d45c5031c462291e263cec114975add1Wiebke Herding{- | derive a second-order induction scheme from a sort generation constraint

b1f52a36d45c5031c462291e263cec114975add1Wiebke Herdingthe second-order predicate variables are represented as predicate

2b4130336e941b7d01c78a6da55449a4c6eca609Till Mossakowskisymbols P[s], where s is a sort -}

b1f52a36d45c5031c462291e263cec114975add1Wiebke HerdinginductionScheme :: FormExtension f => [Constraint] -> FORMULA f

b1f52a36d45c5031c462291e263cec114975add1Wiebke HerdinginductionScheme constrs =

b1f52a36d45c5031c462291e263cec114975add1Wiebke Herding induction $ map predSubst constrs

2b4130336e941b7d01c78a6da55449a4c6eca609Till Mossakowski where sorts = map newSort constrs

b1f52a36d45c5031c462291e263cec114975add1Wiebke Herding injective = isInjectiveList sorts

2b4130336e941b7d01c78a6da55449a4c6eca609Till Mossakowski predSubst constr =

2b4130336e941b7d01c78a6da55449a4c6eca609Till Mossakowski (constr, \ t -> Predication predSymb [t] nullRange)

b1f52a36d45c5031c462291e263cec114975add1Wiebke Herding where

b1f52a36d45c5031c462291e263cec114975add1Wiebke Herding predSymb = Qual_pred_name ident typ nullRange

b1f52a36d45c5031c462291e263cec114975add1Wiebke Herding Id ts cs ps =

b1f52a36d45c5031c462291e263cec114975add1Wiebke Herding if injective then newSort constr else origSort constr

b1f52a36d45c5031c462291e263cec114975add1Wiebke Herding ident = Id [mkSimpleId $ genNamePrefix ++ "P_"

++ showId (Id ts [] ps) ""] cs ps

typ = Pred_type [newSort constr] nullRange

{- | Function for derivation of first-order instances of sort generation

constraints.

Given a list of formulas with a free sorted variable, instantiate the

sort generation constraint for this list of formulas

It is assumed that the (original) sorts of the constraint

match the sorts of the free variables -}

instantiateSortGen :: FormExtension f

=> [(Constraint, (FORMULA f, (VAR, SORT)))] -> FORMULA f

instantiateSortGen phis =

induction (map substFormula phis)

where substFormula (c, (phi, (v, s))) = (c, \ t -> substitute v s t phi)

-- | substitute a term for a variable in a formula

substitute :: FormExtension f => VAR -> SORT -> TERM f -> FORMULA f -> FORMULA f

substitute v s t = foldFormula

(mapRecord id) { foldQual_var = \ t2 v2 s2 _ ->

if v == v2 && s == s2 then t else t2

, foldQuantification = \ t2 q vs p r ->

if elem (v, s) $ flatVAR_DECLs vs

then t2 else Quantification q vs p r

}

{- | derive an induction scheme from a sort generation constraint

using substitutions as induction predicates -}

induction :: FormExtension f => [(Constraint, TERM f -> FORMULA f)] -> FORMULA f

induction constrSubsts =

let mkVar i = mkSimpleId ("x_" ++ show i)

sortInfo = map (\ ((cs, sub), i) -> (sub, (mkVar i, newSort cs)))

$ number constrSubsts

mkConclusion (subst, v) =

mkForall [uncurry mkVarDecl v] $ subst $ uncurry mkVarTerm v

inductionConclusion = conjunct $ map mkConclusion sortInfo

inductionPremises = map (mkPrems $ map snd constrSubsts) constrSubsts

inductionPremise = conjunct $ concat inductionPremises

in mkImpl inductionPremise inductionConclusion

{- | construct premise set for the induction scheme

for one sort in the constraint -}

mkPrems :: FormExtension f => [TERM f -> FORMULA f]

-> (Constraint, TERM f -> FORMULA f) -> [FORMULA f]

mkPrems substs (constr, sub) = map (mkPrem substs sub) (opSymbs constr)

-- | construct a premise for the induction scheme for one constructor

mkPrem :: FormExtension f => [TERM f -> FORMULA f] -> (TERM f -> FORMULA f)

-> (OP_SYMB, [Int]) -> FORMULA f

mkPrem substs subst (opSym@(Qual_op_name _ (Op_type _ argTypes _ _) _), idx) =

mkForall qVars phi

where

qVars = map (\ (a, i) -> mkVarDeclStr ("y_" ++ show i) a) $ number argTypes

phi = if null indHyps then indConcl

else mkImpl (conjunct indHyps) indConcl

indConcl = subst $ mkAppl opSym $ map toQualVar qVars

indHyps = mapMaybe indHyp (zip qVars idx)

indHyp (v1, i) =

if i < 0 then Nothing -- leave out sorts from outside the constraint

else Just $ (substs !! i) $ toQualVar v1

mkPrem _ _ (opSym, _) =

error ("CASL.Induction. mkPrems: "

++ "unqualified operation symbol occuring in constraint: "

++ show opSym)

-- | for goals try to generate additional implications based on induction

generateInductionLemmas :: FormExtension f => Bool

-> (Sign f e, [Named (FORMULA f)]) -> (Sign f e, [Named (FORMULA f)])

generateInductionLemmas b (sig, sens) = let

sortGens = foldr (\ s cs -> case sentence s of

Sort_gen_ax c _ -> c : cs

_ -> cs) [] axs

(axs, goals) = partition isAxiom sens

in (sig, (if b then sens else axs)

++ generateInductionLemmasAux b sortGens goals)

generateInductionLemmasAux

:: FormExtension f => Bool

-- ^ if True create additional implication otherwise replace goals

-> [[Constraint]] -- ^ the constraints of a theory

-> [AS_Anno.Named (FORMULA f)] -- ^ all goals of a theory

-> [AS_Anno.Named (FORMULA f)]

{- ^ all the generated induction lemmas

and the labels are derived from the goal-names -}

generateInductionLemmasAux b sort_gen_axs goals = let

findVar s [] = error ("CASL.generateInductionLemmas:\n"

++ "No VAR found of SORT " ++ show s ++ "!")

findVar s ((vl, sl) : lst) = if s == sl then vl else findVar s lst

removeVarsort v s f = case f of

Quantification Universal varDecls formula rng ->

let vd' = newVarDecls varDecls

in if null vd' then formula

else Quantification Universal vd' formula rng

_ -> f

where

newVarDecls = filter (\ (Var_decl vs _ _) -> not $ null vs) .

map (\ var_decl@(Var_decl vars varsort r) ->

if varsort == s

then Var_decl (filter (/= v) vars) s r

else var_decl)

(uniQuantGoals, restGoals) =

foldr ( \ goal (ul, rl) -> case sentence goal of

Quantification Universal varDecl _ _ ->

((goal, flatVAR_DECLs varDecl) : ul, rl)

_ -> (ul, goal : rl)) ([], []) goals

{- For each constraint we get a list of goals out of uniQuantGoals

which contain the constraint's newSort. Afterwards all combinations

are created. -}

constraintGoals = combine

. map (\ c -> filter (any ((newSort c ==) . snd) . snd)

uniQuantGoals)

combis =

{- returns big list containing tuples of constraints and a matching

combination (list) of goals. -}

concatMap (\ c -> map (\ combi -> (c, combi)) $ constraintGoals c)

sort_gen_axs

singleDts = map head $ filter isSingle sort_gen_axs

indSorts = Set.fromList $ map newSort singleDts

(simpleIndGoals, rest2) = foldr (\ (gs, vs) (ul, rl) ->

case dropWhile (not . (`Set.member` indSorts) . snd) vs of

[] -> (ul, gs : rl)

(v, s) : _ -> case find ((== s) . newSort) singleDts of

Nothing -> (ul, gs : rl)

Just c -> ((gs, (v, s), c) : ul, rl)) ([], []) uniQuantGoals

toIndPrem (gs, (v, s), c) =

let f = removeVarsort v s $ sentence gs

sb t = substitute v s t f

ps = mkPrems [sb] (c, sb)

in gs { sentence = conjunct ps }

in if b then

map (\ (cons, formulas) ->

let formula = instantiateSortGen

$ map (\ (c, (f, varsorts)) ->

let s = newSort c

vs = findVar s varsorts

in (c, (removeVarsort vs s $ sentence f, (vs, s))))

$ zip cons formulas

sName = tail $ concatMap (('_' :) . senAttr . fst) formulas

++ "_induction"

in makeNamed sName formula

) combis

else map toIndPrem simpleIndGoals ++ rest2 ++ restGoals