Proofs.hs revision ce8b15da31cd181b7e90593cbbca98f47eda29d6
456238178f89e5a3de2988ee6c8af924297d52d9Christian MaederModule : $Header$
5191fa24c532d1f67e7a642e9aece65efb8a0975Christian MaederCopyright : (c) Jorina F. Gerken, Till Mossakowski, Uni Bremen 2002-2004
456238178f89e5a3de2988ee6c8af924297d52d9Christian MaederLicence : similar to LGPL, see HetCATS/LICENCE.txt or LIZENZ.txt
5191fa24c532d1f67e7a642e9aece65efb8a0975Christian MaederMaintainer : jfgerken@tzi.de
5191fa24c532d1f67e7a642e9aece65efb8a0975Christian MaederStability : provisional
43b4c41fbb07705c9df321221ab9cb9832460407Christian MaederPortability : non-portable(Logic)
f4a2a20e49f41b2afa657e5e64d9e349c7faa091Christian Maeder Proofs in development graphs.
f2f9df2e17e70674f0bf426ed1763c973ee4cde0Christian Maeder Follows Sect. IV:4.4 of the CASL Reference Manual.
63f0e65a37b95621334db9ee4ba0cd9d826f5c0fChristian Maeder T. Mossakowski, S. Autexier and D. Hutter:
a1ed34933c266ce85066acb0d7b20c90cb8eb213Christian Maeder Extending Development Graphs With Hiding.
c0c2380bced8159ff0297ece14eba948bd236471Christian Maeder H. Hussmann (ed.): Fundamental Approaches to Software Engineering 2001,
404166b9366552e9ec5abb87a37c76ec8a815fb7Klaus Luettich Lecture Notes in Computer Science 2029, p. 269-283,
b1f59a4ea7c96f4c03a4d7cfcb9c5e66871cfbbbChristian Maeder Springer-Verlag 2001.
4d56f2fa72e4aec20eb827c11ed49c8cbb7014bdChristian Maedertodo in general:
8ef75f1cc0437656bf622cec5ac9e8ea221da8f2Christian MaederOrder of rule application: try to use local links induced by %implies
404166b9366552e9ec5abb87a37c76ec8a815fb7Klaus Luettichfor subsumption proofs (such that the %implied formulas need not be
d23b0cc79c0d204e6ec758dff8d0ba71c9f693f7Christian MaederIntegrate stuff from Saarbr�cken
3e8b136f23ed57d40ee617f49bcac37830b58cabChristian MaederAdd proof status information
bab2d88d650448628730ed3b65c9f99c52500e8cChristian Maeder what should be in proof status:
ef9e8535c168d3f774d9e74368a2317a9eda5826Christian Maeder- proofs of thm links according to rules
63f0e65a37b95621334db9ee4ba0cd9d826f5c0fChristian Maeder- cons, def and mono annos, and their proofs
63f0e65a37b95621334db9ee4ba0cd9d826f5c0fChristian Maedertodo for Jorina:
f4a2a20e49f41b2afa657e5e64d9e349c7faa091Christian Maeder - bei GlobDecomp hinzuf�gen:
f4a2a20e49f41b2afa657e5e64d9e349c7faa091Christian Maeder zus�tzlich alle Pfade K<--theta-- M --sigma-->N in den aktuellen
dcbd32289a7bdf1e6edd06c6ab0698c6a9dbf37aChristian Maeder Knoten N, die mit einem HidingDef anfangen, und danach nur GlobalDef
05a62e84edac8c64de04f8349dee418598d216b9Christian Maeder theta ist der Signaturmorphismus des HidingDef's (geht "falsch rum")
1cd4f6541984962658add5cfaa9f28a93879881bChristian Maeder sigma ist die Komposition der Signaturmorphismen auf dem restl. Pfad
1aee4aaddde105264c1faf394d88e302c05094ffChristian Maeder f�r jeden solchen Pfad: einen HidingThm theta einf�gen. sigma ist
8b767d09a78927b111f5596fdff9ca7d2c1a439fChristian Maeder der normale Morphismus (wie bei jedem anderen Link)
8b767d09a78927b111f5596fdff9ca7d2c1a439fChristian Maeder siehe auch Seite 302 des CASL Reference Manual
363939beade943a02b31004cea09dec34fa8a6d9Christian Maederimport Common.Lib.Set (fromList)
014dc30f64ec25e4790cca987d4d1e6635430510Christian Maederimport qualified Common.Lib.Map as Map
f04e8f3ff56405901be968fd4c6e9769239f1a9bKlaus Luettichimport List(nub)
6dc9bc98d0854fe2e3dd3bfc4275096a0c28ee1cChristian Maeder proof status = (DG0,[(R1,DG1),...,(Rn,DGn)])
6dc9bc98d0854fe2e3dd3bfc4275096a0c28ee1cChristian Maeder DG0 is the development graph resulting from the static analysis
6dc9bc98d0854fe2e3dd3bfc4275096a0c28ee1cChristian Maeder Ri is a list of rules that transforms DGi-1 to DGi
23ffcc44ca8612feccbd8fda63fa5be7ab5f9dc3Christian Maeder With the list of intermediate proof states, one can easily implement
61fa0ac06ede811c7aad54ec4c4202346727368eChristian Maeder an undo operation
63f0e65a37b95621334db9ee4ba0cd9d826f5c0fChristian Maedertype ProofStatus = (GlobalContext,LibEnv,[([DGRule],[DGChange])],DGraph)
63f0e65a37b95621334db9ee4ba0cd9d826f5c0fChristian Maeder TheoremHideShift
9e748851c150e1022fb952bab3315e869aaf0214Christian Maeder | HideTheoremShift
51d769d55d88dfa88bdf54bee78d8fa85a2deba8Christian Maeder | Composition
a5e5b8c3e5c11177e5034ef2423813a5d28979edChristian Maeder | GlobDecomp (LEdge DGLinkLab) -- edge in the conclusion
a42fbfe7becf0eae2d624123eb0db73a794593f0Christian Maeder | LocDecomp (LEdge DGLinkLab)
a42fbfe7becf0eae2d624123eb0db73a794593f0Christian Maeder | GlobSubsumption (LEdge DGLinkLab)
b363eb04791e7f735633b9b4088502c2bc50ebfcChristian Maeder | LocalInference
a42fbfe7becf0eae2d624123eb0db73a794593f0Christian Maeder | BasicInference Edge BasicProof
1cd4f6541984962658add5cfaa9f28a93879881bChristian Maeder | BasicConsInference Edge BasicConsProof
2d130d212db7208777ca896a7ecad619a8944971Christian Maederdata DGChange = InsertNode (LNode DGNodeLab)
6a79849bed67264c396dddb3e9c184bdfc1a1bc9Christian Maeder | DeleteNode Node
6ff7a91875597d6e4dfaa68c79187d01473e8341Christian Maeder | InsertEdge (LEdge DGLinkLab)
6ff7a91875597d6e4dfaa68c79187d01473e8341Christian Maeder | DeleteEdge (LEdge DGLinkLab)
6a79849bed67264c396dddb3e9c184bdfc1a1bc9Christian Maeder deriving (Eq)
6a79849bed67264c396dddb3e9c184bdfc1a1bc9Christian Maederdata BasicProof =
4017ebc0f692820736d796af3110c3b3018c108aChristian Maeder forall lid sublogics
a9b59eb2ce961014974276cdae0e9df4419bd212Christian Maeder basic_spec sentence symb_items symb_map_items
6a79849bed67264c396dddb3e9c184bdfc1a1bc9Christian Maeder sign morphism symbol raw_symbol proof_tree .
6a79849bed67264c396dddb3e9c184bdfc1a1bc9Christian Maeder Logic lid sublogics
6a79849bed67264c396dddb3e9c184bdfc1a1bc9Christian Maeder basic_spec sentence symb_items symb_map_items
6a79849bed67264c396dddb3e9c184bdfc1a1bc9Christian Maeder sign morphism symbol raw_symbol proof_tree =>
6a79849bed67264c396dddb3e9c184bdfc1a1bc9Christian Maeder BasicProof lid (Proof_status sentence proof_tree)
dc679edd4ca027663212afdf00926ae2ce19b555Christian Maeder | Conjectured
63f0e65a37b95621334db9ee4ba0cd9d826f5c0fChristian Maeder | Handwritten
63f0e65a37b95621334db9ee4ba0cd9d826f5c0fChristian Maederdata BasicConsProof = BasicConsProof -- more detail to be added ...
ca074a78b8dcccbb8c419586787882f98d0c6163Christian Maeder{- todo: implement apply for GlobDecomp and Subsumption
ca074a78b8dcccbb8c419586787882f98d0c6163Christian Maeder the list of DGChage must be constructed in parallel to the
4017ebc0f692820736d796af3110c3b3018c108aChristian Maeder new DGraph -}
b568982efd0997d877286faa592d81b03c8c67b8Christian MaederapplyRule :: DGRule -> DGraph -> Maybe ([DGChange],DGraph)
ca074a78b8dcccbb8c419586787882f98d0c6163Christian MaederapplyRule = error "Proofs.hs:applyRule"
ca074a78b8dcccbb8c419586787882f98d0c6163Christian Maeder-- ---------------------
63f0e65a37b95621334db9ee4ba0cd9d826f5c0fChristian Maeder-- global decomposition
63f0e65a37b95621334db9ee4ba0cd9d826f5c0fChristian Maeder-- ---------------------
f2f9df2e17e70674f0bf426ed1763c973ee4cde0Christian Maeder{- apply rule GlobDecomp to all global theorem links in the current DG
d946c1bfdd7d58aa7c023efe864d5999eb44a61bChristian Maeder current DG = DGm
d946c1bfdd7d58aa7c023efe864d5999eb44a61bChristian Maeder add to proof status the pair ([GlobDecomp e1,...,GlobDecomp en],DGm+1)
d946c1bfdd7d58aa7c023efe864d5999eb44a61bChristian Maeder where e1...en are the global theorem links in DGm
d946c1bfdd7d58aa7c023efe864d5999eb44a61bChristian Maeder DGm+1 results from DGm by application of GlobDecomp e1,...,GlobDecomp en -}
63f0e65a37b95621334db9ee4ba0cd9d826f5c0fChristian Maeder{- applies global decomposition to all unproven global theorem edges
63f0e65a37b95621334db9ee4ba0cd9d826f5c0fChristian Maeder if possible -}
ca074a78b8dcccbb8c419586787882f98d0c6163Christian MaederglobDecomp :: ProofStatus -> ProofStatus
ca074a78b8dcccbb8c419586787882f98d0c6163Christian MaederglobDecomp proofStatus@(globalContext,libEnv,history,dgraph) =
63f0e65a37b95621334db9ee4ba0cd9d826f5c0fChristian Maeder (globalContext, libEnv, ((newHistoryElem):history), newDgraph)
ca074a78b8dcccbb8c419586787882f98d0c6163Christian Maeder globalThmEdges = filter isUnprovenGlobalThm (labEdges dgraph)
d23b0cc79c0d204e6ec758dff8d0ba71c9f693f7Christian Maeder (newDgraph, newHistoryElem) = globDecompAux dgraph globalThmEdges ([],[])
f1541d4a151dbd08002dbd14e7eb1d5dde253689Christian Maeder{- auxiliary function for globDecomp (above)
6dc9bc98d0854fe2e3dd3bfc4275096a0c28ee1cChristian Maeder actual implementation -}
d946c1bfdd7d58aa7c023efe864d5999eb44a61bChristian MaederglobDecompAux :: DGraph -> [LEdge DGLinkLab] -> ([DGRule],[DGChange])
e6d5dbbc3308f05197868806e0b860f4f53875f1Christian Maeder -> (DGraph,([DGRule],[DGChange]))
363939beade943a02b31004cea09dec34fa8a6d9Christian MaederglobDecompAux dgraph [] historyElem = (dgraph, historyElem)
e4f4d096e5e6d60dd91c746d0e833d0ac7a29c50Christian MaederglobDecompAux dgraph (edge:edges) historyElem =
eb74267cf39e4e95f9eeb5c765f4c8dac33971b4Christian Maeder globDecompAux newDGraph edges newHistoryElem
61fa0ac06ede811c7aad54ec4c4202346727368eChristian Maeder (newDGraph, newChanges) = globDecompForOneEdge dgraph edge
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder newHistoryElem = (((GlobDecomp edge):(fst historyElem)),
f1541d4a151dbd08002dbd14e7eb1d5dde253689Christian Maeder (newChanges++(snd historyElem)))
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder-- applies global decomposition to a single edge
6cd33d6101fb1b93baa6d86fac158af18a115108Christian MaederglobDecompForOneEdge :: DGraph -> LEdge DGLinkLab -> (DGraph,[DGChange])
6cd33d6101fb1b93baa6d86fac158af18a115108Christian MaederglobDecompForOneEdge dgraph edge =
6cd33d6101fb1b93baa6d86fac158af18a115108Christian Maeder globDecompForOneEdgeAux dgraph edge [] paths
b2ac5a92cf36382e8deea5661c1964566caf72b3Christian Maeder pathsToSource
59138b404f12352d103eeffbeaeb3957b90e75fdChristian Maeder = getAllLocOrHideGlobDefPathsTo dgraph (getSourceNode edge) []
b2ac5a92cf36382e8deea5661c1964566caf72b3Christian Maeder paths = [(node, path++(edge:[]))| (node,path) <- pathsToSource]
6cd33d6101fb1b93baa6d86fac158af18a115108Christian Maeder{- auxiliary funktion for globDecompForOneEdge (above)
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder actual implementation -}
10883d13973c46cac98964b66ace7a52b2d059abChristian MaederglobDecompForOneEdgeAux :: DGraph -> LEdge DGLinkLab -> [DGChange] ->
c9a7e6af169a2adfb92f42331cd578065ed83a2bChristian Maeder [(Node, [LEdge DGLinkLab])] -> (DGraph,[DGChange])
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder{- if the list of paths is empty from the beginning, nothing is done
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder otherwise the unprovenThm edge is replaced by a proven one -}
0e5b095a19790411e5352fa7cf57cb0388e70472Christian MaederglobDecompForOneEdgeAux dgraph edge@(source,target,edgeLab) changes [] =
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder if null changes then (dgraph, changes)
f1a913f880e409e7327b5deae95738b5448379a1Christian Maeder if isDuplicate provenEdge dgraph changes
f1a913f880e409e7327b5deae95738b5448379a1Christian Maeder then (delLEdge edge dgraph,
f1a913f880e409e7327b5deae95738b5448379a1Christian Maeder ((DeleteEdge edge):changes))
f1a913f880e409e7327b5deae95738b5448379a1Christian Maeder else ((insEdge provenEdge (delLEdge edge dgraph)),
f1a913f880e409e7327b5deae95738b5448379a1Christian Maeder ((DeleteEdge edge):((InsertEdge provenEdge):changes)))
5191fa24c532d1f67e7a642e9aece65efb8a0975Christian Maeder (GlobalThm _ conservativity conservStatus) = (dgl_type edgeLab)
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder proofBasis = getLabelsOfInsertedEdges changes
93f5b72fdb9ee734caa750b43dd79bbb590dcd73Christian Maeder provenEdge = (source,
93f5b72fdb9ee734caa750b43dd79bbb590dcd73Christian Maeder DGLink {dgl_morphism = dgl_morphism edgeLab,
328a85c807f2a95c3f147d10b05927eaf862ebebChristian Maeder (GlobalThm (Proven proofBasis)
a6db617ca58eb6a0587b6366e913107dfecb71b5Heng Jiang conservativity conservStatus),
06dd4e7c29f33f6122a910719e3bd9062256e397Andy Gimblett dgl_origin = DGProof}
4ba08bfca0cc8d9da65397b8dfd2654fdb4c0e62Christian Maeder-- for each path an unproven localThm edge is inserted
bff4b3f816be4c1e1d8ded76f1d5af786839e1a9Christian MaederglobDecompForOneEdgeAux dgraph edge@(source,target,edgeLab) changes
5b818f10e11fc79def1fdd5c8a080d64a6438d87Christian Maeder ((node,path):list) =
8b0f493ae42bad8b94918cc0957f1af57096cda4Felix Reckers if isDuplicate newEdge dgraph changes
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder then globDecompForOneEdgeAux dgraph edge changes list
819e29dba060687cf391e444e0f6ff88c1908cc3Christian Maeder else globDecompForOneEdgeAux newGraph edge newChanges list
d6697ad2479099b816203fd2c36f593c72c73c76Christian Maeder isHiding = not (null path) && isHidingDef (head path)
54ea981a0503c396c2923a1c06421c6235baf27fChristian Maeder morphismPath = if isHiding then tail path else path
aded505f9b42cc38975559c2a5d175ae95de436bChristian Maeder morphism = case calculateMorphismOfPath morphismPath of
3e8b136f23ed57d40ee617f49bcac37830b58cabChristian Maeder Just morph -> morph
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder error "globDecomp: could not determine morphism of new edge"
9e748851c150e1022fb952bab3315e869aaf0214Christian Maeder newEdge = if isHiding then hidingEdge else localEdge
383aa66e5142365fe9b1f88b18c1da5b27cc8c04Christian Maeder DGLink {dgl_morphism = morphism,
383aa66e5142365fe9b1f88b18c1da5b27cc8c04Christian Maeder dgl_type = (HidingThm (dgl_morphism (getLabelOfEdge (head path))) (Static.DevGraph.Open)),
383aa66e5142365fe9b1f88b18c1da5b27cc8c04Christian Maeder dgl_origin = DGProof})
383aa66e5142365fe9b1f88b18c1da5b27cc8c04Christian Maeder localEdge = (node,
aded505f9b42cc38975559c2a5d175ae95de436bChristian Maeder DGLink {dgl_morphism = morphism,
aded505f9b42cc38975559c2a5d175ae95de436bChristian Maeder dgl_type = (LocalThm (Static.DevGraph.Open)
aded505f9b42cc38975559c2a5d175ae95de436bChristian Maeder dgl_origin = DGProof}
383aa66e5142365fe9b1f88b18c1da5b27cc8c04Christian Maeder newGraph = insEdge newEdge dgraph
383aa66e5142365fe9b1f88b18c1da5b27cc8c04Christian Maeder newChanges = ((InsertEdge newEdge):changes)
a14767aeac3e78ed100f5b75e210ba563ee10dbaChristian Maeder-- -------------------
a14767aeac3e78ed100f5b75e210ba563ee10dbaChristian Maeder-- global subsumption
d23b0cc79c0d204e6ec758dff8d0ba71c9f693f7Christian Maeder-- -------------------
d23b0cc79c0d204e6ec758dff8d0ba71c9f693f7Christian Maeder-- applies global subsumption to all unproven global theorem edges if possible
54ea981a0503c396c2923a1c06421c6235baf27fChristian MaederglobSubsume :: ProofStatus -> ProofStatus
54ea981a0503c396c2923a1c06421c6235baf27fChristian MaederglobSubsume proofStatus@(globalContext,libEnv,history,dGraph) =
54ea981a0503c396c2923a1c06421c6235baf27fChristian Maeder (globalContext, libEnv, nextHistoryElem:history, nextDGraph)
697e63e30aa3c309a1ef1f9357745111f8dfc5a9Christian Maeder globalThmEdges = filter isUnprovenGlobalThm (labEdges dGraph)
f9e0b18852b238ddb649d341194e05d7200d1bbeChristian Maeder result = globSubsumeAux libEnv dGraph ([],[]) globalThmEdges
aded505f9b42cc38975559c2a5d175ae95de436bChristian Maeder nextDGraph = fst result
f9e0b18852b238ddb649d341194e05d7200d1bbeChristian Maeder nextHistoryElem = snd result
819e29dba060687cf391e444e0f6ff88c1908cc3Christian Maeder{- auxiliary function for globSubsume (above)
819e29dba060687cf391e444e0f6ff88c1908cc3Christian Maeder the actual implementation -}
d23b0cc79c0d204e6ec758dff8d0ba71c9f693f7Christian MaederglobSubsumeAux :: LibEnv -> DGraph -> ([DGRule],[DGChange]) ->
254df6f22d01eacf7c57b85729e0445747b630d9Christian Maeder [LEdge DGLinkLab] -> (DGraph,([DGRule],[DGChange]))
d23b0cc79c0d204e6ec758dff8d0ba71c9f693f7Christian MaederglobSubsumeAux _ dgraph historyElement [] = (dgraph, historyElement)
d23b0cc79c0d204e6ec758dff8d0ba71c9f693f7Christian MaederglobSubsumeAux libEnv dgraph (rules,changes) ((ledge@(src,tgt,edgeLab)):list) =
254df6f22d01eacf7c57b85729e0445747b630d9Christian Maeder if not (null proofBasis) || isIdentityEdge ledge libEnv dgraph
d23b0cc79c0d204e6ec758dff8d0ba71c9f693f7Christian Maeder if isDuplicate newEdge dgraph changes then
254df6f22d01eacf7c57b85729e0445747b630d9Christian Maeder globSubsumeAux libEnv (delLEdge ledge dgraph)
d23b0cc79c0d204e6ec758dff8d0ba71c9f693f7Christian Maeder (newRules,(DeleteEdge ledge):changes) list
aded505f9b42cc38975559c2a5d175ae95de436bChristian Maeder globSubsumeAux libEnv (insEdge newEdge (delLEdge ledge dgraph))
d23b0cc79c0d204e6ec758dff8d0ba71c9f693f7Christian Maeder (newRules,(DeleteEdge ledge):((InsertEdge newEdge):changes)) list
ac34194a668399bb8ef238da77c3a09e93fb253bChristian Maeder globSubsumeAux libEnv dgraph (rules,changes) list
d23b0cc79c0d204e6ec758dff8d0ba71c9f693f7Christian Maeder morphism = dgl_morphism edgeLab
1842453990fed8a1bd7a5ac792d7982c1d2bfcd5Christian Maeder allPaths = getAllGlobPathsOfMorphismBetween dgraph morphism src tgt
4fc9de0da898448f1d3597ebbd8c04a066464c21Christian Maeder filteredPaths = [path| path <- allPaths, notElem ledge path]
df5eb1b8e587946c9d072f4ee6ac7d001719b034Christian Maeder proofBasis = selectProofBasis edgeLab filteredPaths
1842453990fed8a1bd7a5ac792d7982c1d2bfcd5Christian Maeder (GlobalThm _ conservativity conservStatus) = dgl_type edgeLab
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder newEdge = (src,
986d3f255182539098a97ac86da9eeee5b7a72e3Christian Maeder DGLink {dgl_morphism = morphism,
61fa0ac06ede811c7aad54ec4c4202346727368eChristian Maeder dgl_type = (GlobalThm (Proven proofBasis)
4561227a776bdf0ab679b19fb92f1eaaed8786f7Christian Maeder conservativity conservStatus),
01e278bdd7dce13b9303ed3d79683d83c89d09f9Liam O'Reilly dgl_origin = DGProof}
5ad5dffe06818a13e1632b1119fbca7881085fc1Dominik Luecke newRules = (GlobSubsumption ledge):rules
8c812cd83569e973f10cf69a342424ceabc07af9Christian Maeder-- --------------------
8c812cd83569e973f10cf69a342424ceabc07af9Christian Maeder-- local decomposition
1535e1d8c82db5f7e2402261983c4c2ef39f4f39Mihai Codescu-- --------------------
1535e1d8c82db5f7e2402261983c4c2ef39f4f39Mihai Codescu{- a merge of the rules local subsumption, local decomposition I and
7a3fe82695aa32657693e05712f84d7f81672f2eJonathan von Schroeder local decomposition II -}
7a3fe82695aa32657693e05712f84d7f81672f2eJonathan von Schroeder-- applies this merge of rules to all unproven localThm edges if possible
7a3fe82695aa32657693e05712f84d7f81672f2eJonathan von SchroederlocDecomp :: ProofStatus -> ProofStatus
7a3fe82695aa32657693e05712f84d7f81672f2eJonathan von SchroederlocDecomp proofStatus@(globalContext,libEnv,history,dGraph) =
05a206508bc898f87fe6ab6e069814df3c29d303Dominik Luecke (globalContext, libEnv, nextHistoryElem:history, nextDGraph)
d54cd08a4cfa26256c38d8ed12c343adbfe1a0e3Christian Maeder localThmEdges = filter isUnprovenLocalThm (labEdges dGraph)
d54cd08a4cfa26256c38d8ed12c343adbfe1a0e3Christian Maeder result = locDecompAux libEnv dGraph ([],[]) localThmEdges
d54cd08a4cfa26256c38d8ed12c343adbfe1a0e3Christian Maeder nextDGraph = fst result
3b06e23643a9f65390cb8c1caabe83fa7e87a708Till Mossakowski nextHistoryElem = snd result
63f0e65a37b95621334db9ee4ba0cd9d826f5c0fChristian Maeder{- auxiliary function for locDecomp (above)
8c812cd83569e973f10cf69a342424ceabc07af9Christian Maeder actual implementation -}
0b349288edfa50fdf38fda1a14e1562d03f92574Christian MaederlocDecompAux :: LibEnv -> DGraph -> ([DGRule],[DGChange]) -> [LEdge DGLinkLab]
5afff1a0f62394414c33b06141175b3ab0b117a5Christian Maeder -> (DGraph,([DGRule],[DGChange]))
5afff1a0f62394414c33b06141175b3ab0b117a5Christian MaederlocDecompAux libEnv dgraph historyElement [] = (dgraph, historyElement)
61fa0ac06ede811c7aad54ec4c4202346727368eChristian MaederlocDecompAux libEnv dgraph (rules,changes) ((ledge@(src,tgt,edgeLab)):list) =
1b3a2f98d1cd01fc9e0591f69507e20526727559Dominik Luecke if (null proofBasis && not (isIdentityEdge ledge libEnv dgraph))
247cc88aa55d0a7b6831767cd593ea885c6747a0Christian Maeder locDecompAux libEnv dgraph (rules,changes) list
f8e1a1eca871a26a535a4ee7d51902ba94b1db1eChristian Maeder if isDuplicate newEdge dgraph changes
ea3bff3e547a1ac714d4db39c5efef95e02b2e7dChristian Maeder then locDecompAux libEnv auxGraph
dd6f22b9dcff2695181b86372e4df03d5b96e92dKristina Sojakova (newRules,(DeleteEdge ledge):changes) list
005e0f0c6b0cc898003b03801158c208f3071fc5Kristina Sojakova else locDecompAux libEnv newGraph (newRules,newChanges) list
23b4e542dca35852f58d1fb3f7d9078c1de5ab06Christian Maeder morphism = dgl_morphism edgeLab
23b4e542dca35852f58d1fb3f7d9078c1de5ab06Christian Maeder allPaths = getAllLocGlobPathsBetween dgraph src tgt
76b9b2974795a6fb31f242fd032de3ff66df6204Christian Maeder sens = getSentenceList libEnv dgraph src
76b9b2974795a6fb31f242fd032de3ff66df6204Christian Maeder pathsWithoutEdgeItself = [path|path <- allPaths, notElem ledge path]
8a78868bae2ec6838c87366c35c57e109154c51eChristian Maeder filteredPaths = filterByTranslation sens morphism pathsWithoutEdgeItself
624e6701e0deb7ac6c03c0cba0190fbc5033cf93Ewaryst Schulz proofBasis = selectProofBasis edgeLab filteredPaths
c2e192ace9ef7cfb0e59563f1b24477b2b65cff3Dominik Dietrich auxGraph = delLEdge ledge dgraph
6b75c206b317eb30a08d88a8f27e0295ffeb1546Christian Maeder (LocalThm _ conservativity conservStatus) = (dgl_type edgeLab)
9a4b469ca0a7f44a598e551a973c75195207db58Eugen Kuksa newEdge = (src,
01645eac73dbc789392674930adc5745c935f3a0Christian Maeder DGLink {dgl_morphism = morphism,
bff4b3f816be4c1e1d8ded76f1d5af786839e1a9Christian Maeder (LocalThm (Proven proofBasis)
bff4b3f816be4c1e1d8ded76f1d5af786839e1a9Christian Maeder conservativity conservStatus),
b5da047a9a875dec3f968b6c0df96af326f90fa9Alexis Tsogias dgl_origin = DGProof}
0a03acf9fa28e6ff00f4d7c9c6acbae64cf09c56Ewaryst Schulz newGraph = insEdge newEdge auxGraph
0a03acf9fa28e6ff00f4d7c9c6acbae64cf09c56Ewaryst Schulz newRules = (LocDecomp ledge):rules
bab2d88d650448628730ed3b65c9f99c52500e8cChristian Maeder newChanges = (DeleteEdge ledge):((InsertEdge newEdge):changes)
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder{- returns the sentence list of the given node -}
456238178f89e5a3de2988ee6c8af924297d52d9Christian MaedergetSentenceList :: LibEnv -> DGraph -> Node -> Maybe G_l_sentence_list
456238178f89e5a3de2988ee6c8af924297d52d9Christian MaedergetSentenceList libEnv dgraph node =
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder if isDGRef nodeLab
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder then case Map.lookup (dgn_libname nodeLab) libEnv of
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder Just (_,_,refDgraph) -> getSentenceList libEnv refDgraph (dgn_node nodeLab)
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder Nothing -> Nothing
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder else Just (dgn_sens nodeLab)
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder where nodeLab = lab' (context node dgraph)
7a3fe82695aa32657693e05712f84d7f81672f2eJonathan von Schroeder{- returns the sentence list of the given node -}
1535e1d8c82db5f7e2402261983c4c2ef39f4f39Mihai CodescugetSignature :: LibEnv -> DGraph -> Node -> Maybe G_sign
1535e1d8c82db5f7e2402261983c4c2ef39f4f39Mihai CodescugetSignature libEnv dgraph node =
1535e1d8c82db5f7e2402261983c4c2ef39f4f39Mihai Codescu if isDGRef nodeLab
1535e1d8c82db5f7e2402261983c4c2ef39f4f39Mihai Codescu then case Map.lookup (dgn_libname nodeLab) libEnv of
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder Just (_,_,refDgraph) ->
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder getSignature libEnv refDgraph (dgn_node nodeLab)
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder Nothing -> Nothing
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder else Just (dgn_sign nodeLab)
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder where nodeLab = lab' (context node dgraph)
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder{- removes all paths from the given list of paths whose morphism does not translate the given sentence list to the same resulting sentence list as the given morphism-}
456238178f89e5a3de2988ee6c8af924297d52d9Christian MaederfilterByTranslation :: Maybe G_l_sentence_list -> GMorphism -> [[LEdge DGLinkLab]] -> [[LEdge DGLinkLab]]
456238178f89e5a3de2988ee6c8af924297d52d9Christian MaederfilterByTranslation maybeSens morphism paths =
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder case maybeSens of
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder Just sens -> [path| path <- paths, isSameTranslation sens morphism path]
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder Nothing -> []
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder-- isSameTranslation sens morphism (calculateMorphismOfPath path)]
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder{- checks if the given morphism and the morphism of the given path translate the given sentence list to the same resulting sentence list -}
456238178f89e5a3de2988ee6c8af924297d52d9Christian MaederisSameTranslation :: G_l_sentence_list -> GMorphism -> [LEdge DGLinkLab] -> Bool
456238178f89e5a3de2988ee6c8af924297d52d9Christian MaederisSameTranslation sens morphism path =
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder case calculateMorphismOfPath path of
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder Just morphismOfPath -> isSameTranslationAux sens morphism morphismOfPath
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder Nothing -> False
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder{- checks if the two given morphisms translate the given sentence list to the same resulting sentence list
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maederif the calculation of one of the resulting sentence lists fails, False is returned -}
456238178f89e5a3de2988ee6c8af924297d52d9Christian MaederisSameTranslationAux :: G_l_sentence_list -> GMorphism -> GMorphism -> Bool
456238178f89e5a3de2988ee6c8af924297d52d9Christian MaederisSameTranslationAux sens mor1 mor2 =
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder case maybeResult maybeSens1 of
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder Nothing -> False
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder Just sens1 ->
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder case maybeResult maybeSens2 of
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder Nothing -> False
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder Just sens2 -> eq_G_l_sentence_set sens1 sens2
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder maybeSens1 = translateG_l_sentence_list mor1 sens
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder maybeSens2 = translateG_l_sentence_list mor2 sens
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder-- ----------------------------------------------
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder-- methods that calculate paths of certain types
3e8b136f23ed57d40ee617f49bcac37830b58cabChristian Maeder-- ----------------------------------------------
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder{- returns a list of all proven global paths of the given morphism between
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder the given source and target node-}
456238178f89e5a3de2988ee6c8af924297d52d9Christian MaedergetAllGlobPathsOfMorphismBetween :: DGraph -> GMorphism -> Node -> Node
9f85afecbd79b3df5a0bb17bd28cd0b288dc3213Kristina Sojakova -> [[LEdge DGLinkLab]]
48aa0645e25883048369afc02aac3f49b14a50daChristian MaedergetAllGlobPathsOfMorphismBetween dgraph morphism src tgt =
9f85afecbd79b3df5a0bb17bd28cd0b288dc3213Kristina Sojakova filterPathsByMorphism morphism allPaths
79834070d6d3c63a098e570b12fa3405c607dc70Kristina Sojakova allPaths = getAllGlobPathsBetween dgraph src tgt
23b4e542dca35852f58d1fb3f7d9078c1de5ab06Christian Maeder{- returns all paths from the given list whose morphism is equal to the
8a78868bae2ec6838c87366c35c57e109154c51eChristian MaederfilterPathsByMorphism :: GMorphism -> [[LEdge DGLinkLab]]
8a78868bae2ec6838c87366c35c57e109154c51eChristian Maeder -> [[LEdge DGLinkLab]]
624e6701e0deb7ac6c03c0cba0190fbc5033cf93Ewaryst SchulzfilterPathsByMorphism morphism paths =
624e6701e0deb7ac6c03c0cba0190fbc5033cf93Ewaryst Schulz [path| path <- paths, (calculateMorphismOfPath path) == (Just morphism)]
7165a916d2fa1bf87c4741ec63b253413eebbf69Karl Luc{- returns a list of all paths to the given node
7165a916d2fa1bf87c4741ec63b253413eebbf69Karl Luc that consist of globalDef edge only
01645eac73dbc789392674930adc5745c935f3a0Christian Maeder that consist of a localDef or hidingDef edge
01645eac73dbc789392674930adc5745c935f3a0Christian Maeder followed by any number of globalDef edges -}
bff4b3f816be4c1e1d8ded76f1d5af786839e1a9Christian MaedergetAllLocOrHideGlobDefPathsTo :: DGraph -> Node -> [LEdge DGLinkLab]
bff4b3f816be4c1e1d8ded76f1d5af786839e1a9Christian Maeder -> [(Node, [LEdge DGLinkLab])]
bff4b3f816be4c1e1d8ded76f1d5af786839e1a9Christian MaedergetAllLocOrHideGlobDefPathsTo =
b5da047a9a875dec3f968b6c0df96af326f90fa9Alexis Tsogias getAllGlobDefPathsBeginningWithTypesTo
b5da047a9a875dec3f968b6c0df96af326f90fa9Alexis Tsogias ([isLocalDef, isHidingDef]::[LEdge DGLinkLab -> Bool])
0a03acf9fa28e6ff00f4d7c9c6acbae64cf09c56Ewaryst Schulz{- returns a list of all paths to the given node
0a03acf9fa28e6ff00f4d7c9c6acbae64cf09c56Ewaryst Schulz that consist of globalDef edges only
bab2d88d650448628730ed3b65c9f99c52500e8cChristian Maeder that consist of a localDef edge followed by any number of globalDef edges -}
bab2d88d650448628730ed3b65c9f99c52500e8cChristian MaedergetAllLocGlobDefPathsTo :: DGraph -> Node -> [LEdge DGLinkLab]
0a03acf9fa28e6ff00f4d7c9c6acbae64cf09c56Ewaryst Schulz -> [(Node, [LEdge DGLinkLab])]
456238178f89e5a3de2988ee6c8af924297d52d9Christian MaedergetAllLocGlobDefPathsTo = getAllGlobDefPathsBeginningWithTypesTo
c70ef4c3b3a62764f715510c9fd67dde3acfe454Christian Maeder ([isLocalDef]::[LEdge DGLinkLab -> Bool])
61fa0ac06ede811c7aad54ec4c4202346727368eChristian Maeder{- (node,path):(locGlobPaths ++
8b0f493ae42bad8b94918cc0957f1af57096cda4Felix Reckers [getAllLocGlobDefPathsTo dgraph (getSourceNode edge) path|
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder (_, path@(edge:edges)) <- globalPaths]))
61fa0ac06ede811c7aad54ec4c4202346727368eChristian Maeder inEdges = inn dgraph node
5191fa24c532d1f67e7a642e9aece65efb8a0975Christian Maeder globalEdges = [edge| edge <- filter isGlobalDef inEdges, notElem edge path]
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder localEdges = [edge| edge <- filter isLocalDef inEdges, notElem edge path]
2b33802ca26124644f4311db4319376ecffdc8d2Christian Maeder globalPaths = [(getSourceNode edge, (edge:path))| edge <- globalEdges]
9e748851c150e1022fb952bab3315e869aaf0214Christian Maeder locGlobPaths = [(getSourceNode edge, (edge:path))| edge <- localEdges]
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder{- returns a list of all paths to the given node
43b4c41fbb07705c9df321221ab9cb9832460407Christian Maeder that consist of globalDef edges only
61fa0ac06ede811c7aad54ec4c4202346727368eChristian Maeder that consist of an edge of one of the given types
5191fa24c532d1f67e7a642e9aece65efb8a0975Christian Maeder followed by any number of globalDef edges -}
5191fa24c532d1f67e7a642e9aece65efb8a0975Christian MaedergetAllGlobDefPathsBeginningWithTypesTo :: [LEdge DGLinkLab -> Bool] -> DGraph -> Node -> [LEdge DGLinkLab]
5191fa24c532d1f67e7a642e9aece65efb8a0975Christian Maeder -> [(Node, [LEdge DGLinkLab])]
3e61f574717499939bd8e0ff538ea9e7b72d4e2dKlaus LuettichgetAllGlobDefPathsBeginningWithTypesTo types dgraph node path =
1aee4aaddde105264c1faf394d88e302c05094ffChristian Maeder (node,path):(typeGlobPaths ++
10883d13973c46cac98964b66ace7a52b2d059abChristian Maeder (concat ( [getAllGlobDefPathsBeginningWithTypesTo
f443a57f2a8e0ca3daa7431b0c89a18ba52c337aChristian Maeder types dgraph (getSourceNode edge) path |
e284004f10a315dbdb624c8b2522f65d485eaa48Martin Kühl (_, path@(edge:edges)) <- globalPaths])
dcbd32289a7bdf1e6edd06c6ab0698c6a9dbf37aChristian Maeder inEdges = inn dgraph node
dcbd32289a7bdf1e6edd06c6ab0698c6a9dbf37aChristian Maeder globalEdges = [edge| edge <- filter isGlobalDef inEdges, notElem edge path]
27785f379d6810811b4e6d23feab18845fde9a98Christian Maeder = [edge| edge <- filterByTypes types inEdges, notElem edge path]
2d130d212db7208777ca896a7ecad619a8944971Christian Maeder globalPaths = [(getSourceNode edge, (edge:path))| edge <- globalEdges]
2d130d212db7208777ca896a7ecad619a8944971Christian Maeder typeGlobPaths = [(getSourceNode edge, (edge:path))| edge <- edgesOfTypes]
33d042fe6a9eb27a4c48f840b80838f3e7d98e34Christian Maeder{- returns all paths consisting of global edges only
fa21fba9ceb1ddf7b3efd54731a12ed8750191d8Christian Maeder of one local edge followed by any number of global edges-}
fa21fba9ceb1ddf7b3efd54731a12ed8750191d8Christian MaedergetAllLocGlobPathsBetween :: DGraph -> Node -> Node -> [[LEdge DGLinkLab]]
e7757995211bd395dc79d26fe017d99375f7d2a6Christian MaedergetAllLocGlobPathsBetween dgraph src tgt =
0c355dd0b739631ee472f9a656e266be27fa4e64Christian Maeder locGlobPaths ++ globPaths
c7ec85d1103173e089aa5048fd7afb2f9b505124Klaus Luettich outEdges = out dgraph src
c7ec85d1103173e089aa5048fd7afb2f9b505124Klaus Luettich locEdges = [(edge,target)|edge@(_,target,_) <-
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder (filterByTypes [isLocalEdge] outEdges)]
c7ec85d1103173e089aa5048fd7afb2f9b505124Klaus Luettich locGlobPaths = (concat [map ([edge]++)
c7ec85d1103173e089aa5048fd7afb2f9b505124Klaus Luettich (getAllPathsOfTypesBetween dgraph [isGlobalEdge] node tgt [])|
810746aea00b81c1eec27dae84d73a43599ff056Christian Maeder (edge,node) <- locEdges])
a883cd4d01fe39d23219cf5333425f195be24d8bChristian Maeder globPaths = getAllPathsOfTypesBetween dgraph [isGlobalEdge] src tgt []
33d042fe6a9eb27a4c48f840b80838f3e7d98e34Christian Maeder{- returns all paths of globalDef edges or globalThm edges
5191fa24c532d1f67e7a642e9aece65efb8a0975Christian Maeder between the given source and target node -}
f38b3687c5558128515e34fb85d8b466d22dc300Christian MaedergetAllGlobPathsBetween :: DGraph -> Node -> Node -> [[LEdge DGLinkLab]]
e112e83352048f3db8c8f93ae104193e7338c10fChristian MaedergetAllGlobPathsBetween dgraph src tgt =
f38b3687c5558128515e34fb85d8b466d22dc300Christian Maeder getAllPathsOfTypesBetween dgraph [isGlobalDef,isGlobalThm] src tgt []
f38b3687c5558128515e34fb85d8b466d22dc300Christian Maeder{- gets all paths consisting of local/global thm/def edges
f38b3687c5558128515e34fb85d8b466d22dc300Christian Maeder of the given morphism -}
a204259b2a95cf632336c164ff58331e9fd807e2Christian MaedergetAllThmDefPathsOfMorphismBetween :: DGraph -> GMorphism -> Node -> Node
a545f813d2f8006ef79617e4fedc841d89195e2dChristian Maeder -> [[LEdge DGLinkLab]]
ef67402074be14deb95e4ff564737d5593144130Klaus LuettichgetAllThmDefPathsOfMorphismBetween dgraph morphism src tgt =
e112e83352048f3db8c8f93ae104193e7338c10fChristian Maeder filterPathsByMorphism morphism allPaths
e05fd774e0181e93963d4302303b20698603a505Christian Maeder allPaths = getAllPathsOfTypesBetween dgraph types src tgt []
aebb0b18fe5e6ba7dd7e4c66a16a905611ef7ba9Christian Maeder [isGlobalThm,
ac0bbbcb2774629bb87986e69cf53d3402c5f575Christian Maeder isProvenLocalThm,
63f0e65a37b95621334db9ee4ba0cd9d826f5c0fChristian Maeder isProvenLocalThm,
e05fd774e0181e93963d4302303b20698603a505Christian Maeder isUnprovenLocalThm,
483333cb1e873b6d55f5ef0bfbf061861f0493abChristian Maeder{- returns all paths of globalDef edges between the given source and
fdb2d618144159395f7bf8ce3327b3c112a17dd3Till Mossakowski target node -}
1dfba1f850f6a43094962b459998d1ea11472461Christian MaedergetAllGlobDefPathsBetween :: DGraph -> Node -> Node -> [[LEdge DGLinkLab]]
1dfba1f850f6a43094962b459998d1ea11472461Christian MaedergetAllGlobDefPathsBetween dgraph src tgt =
1dfba1f850f6a43094962b459998d1ea11472461Christian Maeder getAllPathsOfTypeBetween dgraph isGlobalDef src tgt
e7757995211bd395dc79d26fe017d99375f7d2a6Christian Maeder{- returns all paths consiting of edges of the given type between the
99afa6000472f3d291fdf9193ea19d334a58658dChristian Maeder given node -}
fa0f3519d71f719d88577b716b1579776b4a2535Christian MaedergetAllPathsOfTypeBetween :: DGraph -> (LEdge DGLinkLab -> Bool) -> Node
99afa6000472f3d291fdf9193ea19d334a58658dChristian Maeder -> Node -> [[LEdge DGLinkLab]]
5bb7eeaca10ea76595229375f907a5a388b7c882Christian MaedergetAllPathsOfTypeBetween dgraph isType src tgt =
5bb7eeaca10ea76595229375f907a5a388b7c882Christian Maeder getAllPathsOfTypesBetween dgraph (isType:[]) src tgt []
c59d1c38ef94b4fb1c8d9fda9573bc1e1d2801e7Christian Maeder{- returns all paths consisting of edges of the given types between
cd36bffee51c77cdadcb9f916b34fa512e311946Christian Maeder the given nodes -}
99afa6000472f3d291fdf9193ea19d334a58658dChristian MaedergetAllPathsOfTypesBetween :: DGraph -> [LEdge DGLinkLab -> Bool] -> Node
ac0bbbcb2774629bb87986e69cf53d3402c5f575Christian Maeder -> Node -> [LEdge DGLinkLab]
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder -> [[LEdge DGLinkLab]]
3e61f574717499939bd8e0ff538ea9e7b72d4e2dKlaus LuettichgetAllPathsOfTypesBetween dgraph types src tgt path =
3e61f574717499939bd8e0ff538ea9e7b72d4e2dKlaus Luettich [edge:path| edge <- edgesFromSrc]
3e61f574717499939bd8e0ff538ea9e7b72d4e2dKlaus Luettich [getAllPathsOfTypesBetween dgraph types src nextTgt (edge:path)|
3e61f574717499939bd8e0ff538ea9e7b72d4e2dKlaus Luettich (edge,nextTgt) <- nextStep] )
3e61f574717499939bd8e0ff538ea9e7b72d4e2dKlaus Luettich inGoingEdges = inn dgraph tgt
3e61f574717499939bd8e0ff538ea9e7b72d4e2dKlaus Luettich edgesOfTypes =
3e61f574717499939bd8e0ff538ea9e7b72d4e2dKlaus Luettich [edge| edge <- filterByTypes types inGoingEdges, notElem edge path]
3e61f574717499939bd8e0ff538ea9e7b72d4e2dKlaus Luettich edgesFromSrc =
3e61f574717499939bd8e0ff538ea9e7b72d4e2dKlaus Luettich [edge| edge@(source,_,_) <- edgesOfTypes, source == src]
e7757995211bd395dc79d26fe017d99375f7d2a6Christian Maeder [(edge, source)| edge@(source,_,_) <- edgesOfTypes, source /= src]
8b0f493ae42bad8b94918cc0957f1af57096cda4Felix Reckers-- removes all edges that are not of the given types
3e61f574717499939bd8e0ff538ea9e7b72d4e2dKlaus LuettichfilterByTypes :: [LEdge DGLinkLab -> Bool] -> [LEdge DGLinkLab]
a80c28bb8b7a23ccdf7e08d0fe216fc19cc97273Klaus Luettich -> [LEdge DGLinkLab]
82e29b77f0ef4cccd7ed734692c5e1e93dbbc645Christian MaederfilterByTypes [] edges = []
a80c28bb8b7a23ccdf7e08d0fe216fc19cc97273Klaus LuettichfilterByTypes (isType:typeChecks) edges =
5f0e3e4cb7dd31033c9682cafa712d2a66b2f3bcChristian Maeder (filter isType edges)++(filterByTypes typeChecks edges)
b9625461755578f3eed04676d42a63fd2caebd0cChristian Maeder-- --------------------------------------
e7757995211bd395dc79d26fe017d99375f7d2a6Christian Maeder-- methods to determine or get morphisms
5191fa24c532d1f67e7a642e9aece65efb8a0975Christian Maeder-- --------------------------------------
210aa1071465039588fa9e38c10e343631c34655Christian Maeder-- determines the morphism of a given path
363939beade943a02b31004cea09dec34fa8a6d9Christian MaedercalculateMorphismOfPath :: [LEdge DGLinkLab] -> Maybe GMorphism
5191fa24c532d1f67e7a642e9aece65efb8a0975Christian MaedercalculateMorphismOfPath [] = Nothing
b1f59a4ea7c96f4c03a4d7cfcb9c5e66871cfbbbChristian MaedercalculateMorphismOfPath path@((src,tgt,edgeLab):furtherPath) =
3e61f574717499939bd8e0ff538ea9e7b72d4e2dKlaus Luettich case maybeMorphismOfFurtherPath of
3e61f574717499939bd8e0ff538ea9e7b72d4e2dKlaus Luettich Nothing -> if null furtherPath then Just morphism else Nothing
4ba08bfca0cc8d9da65397b8dfd2654fdb4c0e62Christian Maeder Just morphismOfFurtherPath ->
4ba08bfca0cc8d9da65397b8dfd2654fdb4c0e62Christian Maeder resultToMaybe $ compHomInclusion morphism morphismOfFurtherPath
4ba08bfca0cc8d9da65397b8dfd2654fdb4c0e62Christian Maeder morphism = dgl_morphism edgeLab
3e61f574717499939bd8e0ff538ea9e7b72d4e2dKlaus Luettich maybeMorphismOfFurtherPath = calculateMorphismOfPath furtherPath
5191fa24c532d1f67e7a642e9aece65efb8a0975Christian Maeder-- ------------------------------------
1aee4aaddde105264c1faf394d88e302c05094ffChristian Maeder-- methods to get the nodes of an edge
1aee4aaddde105264c1faf394d88e302c05094ffChristian Maeder-- ------------------------------------
2d130d212db7208777ca896a7ecad619a8944971Christian MaedergetSourceNode :: LEdge DGLinkLab -> Node
10883d13973c46cac98964b66ace7a52b2d059abChristian MaedergetSourceNode (source,_,_) = source
83394c6b6e6de128e71b67c9251ed7a84485d082Christian Maeder{- Benutzung derzeit auskommentiert ... -}
68d10d143f29fcff3c637ba24f90e983995ceae6Christian Maeder{-getTargetNode :: LEdge DGLinkLab -> Node
e7757995211bd395dc79d26fe017d99375f7d2a6Christian MaedergetTargetNode (_,target,_) = target -}
340706b6c0c6e3dbacdd7003e20e9cab7f9aa765Christian Maeder-- -------------------------------------
3e61f574717499939bd8e0ff538ea9e7b72d4e2dKlaus Luettich-- methods to check the type of an edge
4ba08bfca0cc8d9da65397b8dfd2654fdb4c0e62Christian Maeder-- -------------------------------------
5191fa24c532d1f67e7a642e9aece65efb8a0975Christian MaederisProven :: LEdge DGLinkLab -> Bool
68d10d143f29fcff3c637ba24f90e983995ceae6Christian MaederisProven edge = isGlobalDef edge || isLocalDef edge
e1559d046eb2c6dde0e6e272b37b6756eac0e8adChristian Maeder || isProvenGlobalThm edge || isProvenLocalThm edge
5191fa24c532d1f67e7a642e9aece65efb8a0975Christian MaederisGlobalEdge :: LEdge DGLinkLab -> Bool
2c619a4dfdc1df27573eba98e81ed1ace906941dChristian MaederisGlobalEdge edge = isGlobalDef edge || isGlobalThm edge
5191fa24c532d1f67e7a642e9aece65efb8a0975Christian MaederisLocalEdge :: LEdge DGLinkLab -> Bool
e284004f10a315dbdb624c8b2522f65d485eaa48Martin KühlisLocalEdge edge = isLocalDef edge || isLocalThm edge
e284004f10a315dbdb624c8b2522f65d485eaa48Martin KühlisGlobalThm :: LEdge DGLinkLab -> Bool
e284004f10a315dbdb624c8b2522f65d485eaa48Martin KühlisGlobalThm edge = isProvenGlobalThm edge || isUnprovenGlobalThm edge
50515239e7e190f4a34ca581dd685d002148fbddChristian MaederisLocalThm :: LEdge DGLinkLab -> Bool
50515239e7e190f4a34ca581dd685d002148fbddChristian MaederisLocalThm edge = isProvenLocalThm edge || isUnprovenLocalThm edge
0b349288edfa50fdf38fda1a14e1562d03f92574Christian MaederisProvenGlobalThm :: LEdge DGLinkLab -> Bool
0b349288edfa50fdf38fda1a14e1562d03f92574Christian MaederisProvenGlobalThm (_,_,edgeLab) =
5191fa24c532d1f67e7a642e9aece65efb8a0975Christian Maeder case dgl_type edgeLab of
5191fa24c532d1f67e7a642e9aece65efb8a0975Christian Maeder (GlobalThm (Proven _) _ _) -> True
5191fa24c532d1f67e7a642e9aece65efb8a0975Christian Maeder otherwise -> False
5191fa24c532d1f67e7a642e9aece65efb8a0975Christian MaederisUnprovenGlobalThm :: LEdge DGLinkLab -> Bool
5191fa24c532d1f67e7a642e9aece65efb8a0975Christian MaederisUnprovenGlobalThm (_,_,edgeLab) =
8b4c68db8b465107cabef8b9cd5b6bc216e1b156Till Mossakowski case dgl_type edgeLab of
8b4c68db8b465107cabef8b9cd5b6bc216e1b156Till Mossakowski (GlobalThm Static.DevGraph.Open _ _) -> True
8b4c68db8b465107cabef8b9cd5b6bc216e1b156Till Mossakowski otherwise -> False
df29370ae8d8b41587957f6bcdcb43a3f1927e47Christian MaederisProvenLocalThm :: LEdge DGLinkLab -> Bool
bcaf979d9babe6346aa343687aa7d596e2894cccPaolo TorriniisProvenLocalThm (_,_,edgeLab) =
5ce19352a9cc47d982819cc889a71cd0a61ac171Christian Maeder case dgl_type edgeLab of
5ce19352a9cc47d982819cc889a71cd0a61ac171Christian Maeder (LocalThm (Proven _) _ _) -> True
c9a7e6af169a2adfb92f42331cd578065ed83a2bChristian Maeder otherwise -> False
23ab8855c58adfbd03a0730584b917b24c603901Christian MaederisUnprovenLocalThm :: LEdge DGLinkLab -> Bool
df29370ae8d8b41587957f6bcdcb43a3f1927e47Christian MaederisUnprovenLocalThm (_,_,edgeLab) =
23ab8855c58adfbd03a0730584b917b24c603901Christian Maeder case dgl_type edgeLab of
e50e41135ece589f7202bd4ef8d6b97531c2a56eKlaus Luettich (LocalThm (Static.DevGraph.Open) _ _) -> True
47b0e9f3cb008cb7997f4e3bae26e4d62dcc887aChristian Maeder otherwise -> False
5191fa24c532d1f67e7a642e9aece65efb8a0975Christian MaederisGlobalDef :: LEdge DGLinkLab -> Bool
431d34c7007a787331c4e5ec997badb0f8190fc7Christian MaederisGlobalDef (_,_,edgeLab) =
5191fa24c532d1f67e7a642e9aece65efb8a0975Christian Maeder case dgl_type edgeLab of
5191fa24c532d1f67e7a642e9aece65efb8a0975Christian Maeder GlobalDef -> True
99afa6000472f3d291fdf9193ea19d334a58658dChristian Maeder otherwise -> False
88318aafc287e92931dceffbb943d58a9310001dChristian MaederisLocalDef :: LEdge DGLinkLab -> Bool
d5d349836d8b1fa93ea49a59d977b106c6e9233bKlaus LuettichisLocalDef (_,_,edgeLab) =
d5d349836d8b1fa93ea49a59d977b106c6e9233bKlaus Luettich case dgl_type edgeLab of
88318aafc287e92931dceffbb943d58a9310001dChristian Maeder LocalDef -> True
5191fa24c532d1f67e7a642e9aece65efb8a0975Christian Maeder otherwise -> False
43b4c41fbb07705c9df321221ab9cb9832460407Christian MaederisHidingDef :: LEdge DGLinkLab -> Bool
43b4c41fbb07705c9df321221ab9cb9832460407Christian MaederisHidingDef (_,_,edgeLab) =
e62d49c0dc2893da75faad896bd135e2e9a7087bKlaus Luettich case dgl_type edgeLab of
9096f6c6aaded6cd8288656ceccd4c7b3bd0747eChristian Maeder HidingDef -> True
9096f6c6aaded6cd8288656ceccd4c7b3bd0747eChristian Maeder otherwise -> False
e112e83352048f3db8c8f93ae104193e7338c10fChristian Maeder-- ----------------------------------------------------------------------------
e62d49c0dc2893da75faad896bd135e2e9a7087bKlaus Luettich-- other methods on edges
e62d49c0dc2893da75faad896bd135e2e9a7087bKlaus Luettich-- ----------------------------------------------------------------------------
e62d49c0dc2893da75faad896bd135e2e9a7087bKlaus Luettich{- returns true, if an identical edge is already in the graph or marked to be inserted,
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder false otherwise-}
e112e83352048f3db8c8f93ae104193e7338c10fChristian MaederisDuplicate :: LEdge DGLinkLab -> DGraph -> [DGChange] -> Bool
456238178f89e5a3de2988ee6c8af924297d52d9Christian MaederisDuplicate newEdge dgraph changes =
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder elem (InsertEdge newEdge) changes || elem newEdge (labEdges dgraph)
456238178f89e5a3de2988ee6c8af924297d52d9Christian MaederisIdentityEdge :: LEdge DGLinkLab -> LibEnv -> DGraph -> Bool
1aee4aaddde105264c1faf394d88e302c05094ffChristian MaederisIdentityEdge (src,tgt,edgeLab) libEnv dgraph =
363939beade943a02b31004cea09dec34fa8a6d9Christian Maeder if isDGRef nodeLab then
c72c1e75a969ff4c336e77481c2a8e42603f13eeChristian Maeder case Map.lookup (dgn_libname nodeLab) libEnv of
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder Just globContext@(_,_,refDgraph) -> isIdentityEdge (dgn_node nodeLab,tgt,edgeLab) libEnv refDgraph
fdef3358918491badb0e29e42b5d3b5a01950716Christian Maeder Nothing -> False
6ff7a91875597d6e4dfaa68c79187d01473e8341Christian Maeder else if src == tgt && (dgl_morphism edgeLab) == (ide Grothendieck (dgn_sign nodeLab)) then True else False
6ff7a91875597d6e4dfaa68c79187d01473e8341Christian Maeder where nodeLab = lab' (context src dgraph)
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder{- returns the DGLinkLab of the given LEdge -}
d23b0cc79c0d204e6ec758dff8d0ba71c9f693f7Christian MaedergetLabelOfEdge :: (LEdge b) -> b
88318aafc287e92931dceffbb943d58a9310001dChristian MaedergetLabelOfEdge (_,_,label) = label
88318aafc287e92931dceffbb943d58a9310001dChristian Maeder-- ----------------------------------------------------------------------------
5191fa24c532d1f67e7a642e9aece65efb8a0975Christian Maeder-- methods to determine the labels of the inserted edges in the given dgchange
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder-- ----------------------------------------------------------------------------
88318aafc287e92931dceffbb943d58a9310001dChristian Maeder{- filters the list of changes for insertions of edges and returns the label
bf76f4fcf07abaebea587df8135de8356c26a363Till Mossakowski of one of these; or Nothing if no insertion was found -}
88318aafc287e92931dceffbb943d58a9310001dChristian MaedergetLabelsOfInsertedEdges :: [DGChange] -> [DGLinkLab]
fdb2d618144159395f7bf8ce3327b3c112a17dd3Till MossakowskigetLabelsOfInsertedEdges changes =
e7757995211bd395dc79d26fe017d99375f7d2a6Christian Maeder [label | (_,_,label) <- getInsertedEdges changes]
473bc1f3f3443f18e0ee83e4642fab42183470f2Christian Maeder{- returns all insertions of edges from the given list of changes -}
473bc1f3f3443f18e0ee83e4642fab42183470f2Christian MaedergetInsertedEdges :: [DGChange] -> [LEdge DGLinkLab]
6e049108aa87dc46bcff96fae50a4625df1d9648Klaus LuettichgetInsertedEdges [] = []
5191fa24c532d1f67e7a642e9aece65efb8a0975Christian MaedergetInsertedEdges (change:list) =
5191fa24c532d1f67e7a642e9aece65efb8a0975Christian Maeder case change of
f4505a64a089693012a3f5c3b1f12a82cd7a2a5aKlaus Luettich (InsertEdge edge) -> edge:(getInsertedEdges list)
5191fa24c532d1f67e7a642e9aece65efb8a0975Christian Maeder otherwise -> getInsertedEdges list
f4505a64a089693012a3f5c3b1f12a82cd7a2a5aKlaus Luettich-- ----------------------------------------
5191fa24c532d1f67e7a642e9aece65efb8a0975Christian Maeder-- methods to check and select proof basis
5191fa24c532d1f67e7a642e9aece65efb8a0975Christian Maeder-- ----------------------------------------
5191fa24c532d1f67e7a642e9aece65efb8a0975Christian Maeder{- determines all proven paths in the given list and tries to selet a
5191fa24c532d1f67e7a642e9aece65efb8a0975Christian Maeder proof basis from these (s. selectProofBasisAux);
5191fa24c532d1f67e7a642e9aece65efb8a0975Christian Maeder if this fails the same is done for the rest of the given paths, i.e.
5191fa24c532d1f67e7a642e9aece65efb8a0975Christian Maeder for the unproven ones -}
1a6464613c59e35072b90ca296ae402cbe956144Christian MaederselectProofBasis :: DGLinkLab -> [[LEdge DGLinkLab]] -> [DGLinkLab]
8b767d09a78927b111f5596fdff9ca7d2c1a439fChristian MaederselectProofBasis label paths =
8b767d09a78927b111f5596fdff9ca7d2c1a439fChristian Maeder if null provenProofBasis then selectProofBasisAux label unprovenPaths
8b767d09a78927b111f5596fdff9ca7d2c1a439fChristian Maeder else provenProofBasis
8b767d09a78927b111f5596fdff9ca7d2c1a439fChristian Maeder provenPaths = filterProvenPaths paths
8b767d09a78927b111f5596fdff9ca7d2c1a439fChristian Maeder provenProofBasis = selectProofBasisAux label provenPaths
0be0db405c49906bd7057255069bf6df53395ac9Klaus Luettich unprovenPaths = [path | path <- paths, notElem path provenPaths]
0be0db405c49906bd7057255069bf6df53395ac9Klaus Luettich{- selects the first path that does not form a proof cycle with the given
0be0db405c49906bd7057255069bf6df53395ac9Klaus Luettich label (if such a path exits) and returns the labels of its edges -}
0be0db405c49906bd7057255069bf6df53395ac9Klaus LuettichselectProofBasisAux :: DGLinkLab -> [[LEdge DGLinkLab]] -> [DGLinkLab]
0be0db405c49906bd7057255069bf6df53395ac9Klaus LuettichselectProofBasisAux _ [] = []
0be0db405c49906bd7057255069bf6df53395ac9Klaus LuettichselectProofBasisAux label (path:list) =
0be0db405c49906bd7057255069bf6df53395ac9Klaus Luettich if notProofCycle label path then nub (calculateProofBasis path)
0be0db405c49906bd7057255069bf6df53395ac9Klaus Luettich else selectProofBasisAux label list
0be0db405c49906bd7057255069bf6df53395ac9Klaus Luettich{- calculates the proofBasis of the given path,
2e62113845a35e07cb46db05714627c95450f267Klaus Luettich i.e. the list of all DGLinkLabs the proofs of the edges contained in the path
0be0db405c49906bd7057255069bf6df53395ac9Klaus Luettich are based on, plus the DGLinkLabs of the edges themselves;
0be0db405c49906bd7057255069bf6df53395ac9Klaus Luettich duplicates are not removed here, but in the calling method
0be0db405c49906bd7057255069bf6df53395ac9Klaus Luettich selectProofBasisAux -}
0be0db405c49906bd7057255069bf6df53395ac9Klaus LuettichcalculateProofBasis :: [LEdge DGLinkLab] -> [DGLinkLab]
438f9bd974c8e668203e636b0f2bc80c589af043Klaus LuettichcalculateProofBasis [] = []
d23b0cc79c0d204e6ec758dff8d0ba71c9f693f7Christian MaedercalculateProofBasis ((_,_,lab):edges) =
9e748851c150e1022fb952bab3315e869aaf0214Christian Maeder lab:((getProofBasis lab)++(calculateProofBasis edges))
438f9bd974c8e668203e636b0f2bc80c589af043Klaus Luettich{- returns the proofBasis contained in the given DGLinkLab -}
88318aafc287e92931dceffbb943d58a9310001dChristian MaedergetProofBasis :: DGLinkLab -> [DGLinkLab]
feac53e31a8351e3e3c6621f6a14b5714008bfc7Heng JianggetProofBasis lab =
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder case dgl_type lab of
f78ce817f35574674d54e30ad1861a9b4ced20caChristian Maeder (GlobalThm (Proven proofBasis) _ _) -> proofBasis
f78ce817f35574674d54e30ad1861a9b4ced20caChristian Maeder (LocalThm (Proven proofBasis) _ _) -> proofBasis
f78ce817f35574674d54e30ad1861a9b4ced20caChristian Maeder{- returns all proven paths from the given list -}
f78ce817f35574674d54e30ad1861a9b4ced20caChristian MaederfilterProvenPaths :: [[LEdge DGLinkLab]] -> [[LEdge DGLinkLab]]
456238178f89e5a3de2988ee6c8af924297d52d9Christian MaederfilterProvenPaths [] = []
89c9d707aa817684b88036a2dad66c3437840677Heng JiangfilterProvenPaths (path:list) =
f78ce817f35574674d54e30ad1861a9b4ced20caChristian Maeder if (and [isProven edge| edge <- path]) then path:(filterProvenPaths list)
f78ce817f35574674d54e30ad1861a9b4ced20caChristian Maeder else filterProvenPaths list
f041c9a6bda23de33a38490e35b831ae18d96b45Christian Maeder{- opposite of isProofCycle -}
f041c9a6bda23de33a38490e35b831ae18d96b45Christian MaedernotProofCycle :: DGLinkLab -> [LEdge DGLinkLab] -> Bool
f041c9a6bda23de33a38490e35b831ae18d96b45Christian MaedernotProofCycle label = not.(isProofCycle label)
bf7b17b0e19362e9228672782218678cab275d1eDominik Luecke{- checks if the given label is contained in the ProofBasis of one of the
456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder edges of the given path -}
c802a1041ed9251f8ad79139454267e802900e2aChristian MaederisProofCycle :: DGLinkLab -> [LEdge DGLinkLab] -> Bool
c802a1041ed9251f8ad79139454267e802900e2aChristian MaederisProofCycle _ [] = False
c802a1041ed9251f8ad79139454267e802900e2aChristian MaederisProofCycle label (edge:path) =
c802a1041ed9251f8ad79139454267e802900e2aChristian Maeder if (elemOfProofBasis label edge) then True else (isProofCycle label path)
f9442174f64331ccf0bf08178632af7302ccfc96Christian Maeder{- checks if the given label is contained in the ProofBasis of the given
f9442174f64331ccf0bf08178632af7302ccfc96Christian MaederelemOfProofBasis :: DGLinkLab -> (LEdge DGLinkLab) -> Bool
f9442174f64331ccf0bf08178632af7302ccfc96Christian MaederelemOfProofBasis label (_,_,dglink) =
f9442174f64331ccf0bf08178632af7302ccfc96Christian Maeder case dgl_type dglink of
c802a1041ed9251f8ad79139454267e802900e2aChristian Maeder (GlobalThm (Proven proofBasis) _ _) -> elem label proofBasis
53bbc1c9a4e986d1ee9c081d6f0ac7b9546f212bDominik Luecke (LocalThm (Proven proofBasis) _ _) -> elem label proofBasis
bf7b17b0e19362e9228672782218678cab275d1eDominik Luecke-- | Calculate the morphism of a path with given start node
bf7b17b0e19362e9228672782218678cab275d1eDominik LueckecalculateMorphismOfPathWithStart :: DGraph -> (Node,[LEdge DGLinkLab])
bf7b17b0e19362e9228672782218678cab275d1eDominik Luecke -> Maybe GMorphism
bf7b17b0e19362e9228672782218678cab275d1eDominik LueckecalculateMorphismOfPathWithStart dg (n,[]) = do
75b0c0c2cbfb7edd3f4c0555227aabbe6c1aa195Christian Maeder ctx <- fst $ match n dg
bf7b17b0e19362e9228672782218678cab275d1eDominik Luecke return $ ide Grothendieck (dgn_sign (lab' ctx)) -- ??? to simplistic
where cms = Map.toList
$ Map.insert ("Id_"++language_name lid)
-- nextHistoryElem = error "Proofs.Proofs: basic inference"
if True then proveLocalEdgesAux (rules,(DeleteEdge edge):((InsertEdge provenEdge):changes)) (insEdge provenEdge(delLEdge edge dGraph)) edges
-- nextHistoryElem = error "Proofs.Proofs: basic inference"