5767N/A{-# LANGUAGE UndecidableInstances #-}
5767N/ADescription : central interface (type class) for logics in Hets
5767N/ACopyright : (c) Till Mossakowski, and Uni Bremen 2002-2006
5767N/AMaintainer : till@informatik.uni-bremen.de
5767N/APortability : non-portable (various -fglasgow-exts extensions)
5767N/ACentral interface (type class) for logics in Hets
5767N/AProvides data structures for logics (with symbols). Logics are
5767N/A a type class with an /identity type/ (usually interpreted
5767N/A by a singleton set) which serves to treat logics as
5767N/A data. All the functions in the type class take the
5767N/A identity as first argument in order to determine the logic.
5767N/A This module uses multiparameter type classes with functional dependencies
5767N/A for defining an interface for the notion of logic. Multiparameter type
5767N/A classes are needed because a logic consists of a collection of types,
5767N/A together with operations on these. Functional dependencies
6101N/A are needed because no operation will involve all types of
5767N/A the multiparameter type class; hence we need a method to derive
5767N/A the missing types. We chose an easy way: for each logic, we
5767N/A introduce a new singleton type that is the name, or constitutes the identity
5767N/A of the logic. All other types of the multiparameter type class
5767N/A depend on this /identity constituting/ type, and all operations take
5767N/A the 'identity constituting' type as first arguments. The value
5767N/A of the argument of the /identity constituting/ type is irrelevant
5767N/A (note that there is only one value of such a type anyway).
5767N/A Note that we tend to use @lid@ both for the /identity type/
5767N/A of a logic, as well as for its unique inhabitant,
i.e. @lid :: lid@.
5767N/A The other types involved in the definition of logic are as follows:
5767N/A * sign: signatures, that is, contexts, or non-logical vocabularies,
5767N/A typically consisting of a set of declared sorts, predicates,
5767N/A function symbols, propositional letters etc., together with their
5767N/A * sentence: logical formulas.
5767N/A * basic_spec: abstract syntax of basic specifications. The latter are
5767N/A human-readable presentations of a signature together with some sentences.
5767N/A * symbol: symbols that may occur in a signature, fully qualified
5767N/A * raw_symbol: symbols that may occur in a signature, possibly not
5767N/A * morphism: maps between signatures (typically preserving the structure).
5767N/A * symb_items: abstract syntax of symbol lists, used for declaring some
5767N/A symbols of a signature as hidden.
5767N/A * symb_map_items: abstract syntax of symbol maps,
i.e. human-readable
5767N/A presentations of signature morphisms.
5767N/A * sublogics: sublogics of the given logic. This type might be a
6076N/A record of Boolean flags, indicating whether some feature is
5767N/A present in the sublogi of not.
5767N/A J. A. Goguen and R. M. Burstall
5767N/A Institutions: Abstract Model Theory for Specification and
5767N/A (general notion of logic - model theory only)
5767N/A Logic Colloquium 87, p. 275-329, North Holland, 1989
6076N/A (general notion of logic - also proof theory;
5767N/A notion of logic representation, called map there)
5767N/A Specification in an arbitrary institution with symbols
5767N/A 14th WADT 1999, LNCS 1827, p. 252-270
5767N/A (treatment of symbols and raw symbols, see also CASL semantics
5767N/A in the CASL reference manual)
5767N/A Institution Independent Static Analysis for CASL
5767N/A 15h WADT 2001, LNCS 2267, p. 221-237, 2002.
5767N/A (what is needed for static anaylsis)
5767N/A S. Autexier and T. Mossakowski
5767N/A Integrating HOLCASL into the Development Graph Manager MAYA
5767N/A FroCoS 2002, LNCS 2309, p. 2-17, 2002.
5767N/A CoFI (ed.): CASL Reference Manual, LNCS 2960, Springer Verlag, 2004.
5767N/A (static semantics of CASL structured and architectural specifications)
5767N/A Heterogeneous specification and the heterogeneous tool set
5767N/A Habilitation thesis, University of Bremen, 2005
5767N/A (the general picture of heterogeneous specification)
5767N/A-- | Stability of logic implementations
5767N/Adata Stability = Stable | Testing | Unstable | Experimental
5767N/A-- | shortcut for class constraints
5767N/Aclass ShATermConvertible a => Convertible a
5767N/Ainstance ShATermConvertible a => Convertible a
5767N/A-- | shortcut for class constraints
5767N/Aclass (Pretty a, Convertible a) => PrintTypeConv a
5767N/Ainstance (Pretty a, Convertible a) => PrintTypeConv a
5767N/A-- | shortcut for class constraints with equality
5767N/Aclass (Eq a, PrintTypeConv a) => EqPrintTypeConv a
5767N/Ainstance (Eq a, PrintTypeConv a) => EqPrintTypeConv a
5767N/A Define instances like "data CASL = CASL deriving Show"
5767N/Aclass Show lid => Language lid where
5767N/A language_name :: lid -> String
5767N/A description :: lid -> String
5767N/A description _ = "No description available"
{- | Categories are given as usual: objects, morphisms, identities,
domain, codomain and composition. The type id is the name, or
the identity of the category. It is an argument to all functions
of the type class, serving disambiguation among instances
(via the functional dependency lid -> object morphism).
The types for objects and morphisms may be restricted to
subtypes, using legal_obj and legal_mor. For example, for the
category of sets and injective maps, legal_mor would check
injectivity. Since Eq is a subclass of Category, it is also
possible to impose a quotient on the types for objects and morphisms.
Require Ord instances only for efficiency,
i.e. in sets or maps.
class (Ord object, Ord morphism)
=> Category object morphism | morphism -> object where
ide :: object -> morphism
-- | composition, in diagrammatic order,
-- if intermediate objects are equal (not checked!)
composeMorphisms :: morphism -> morphism -> Result morphism
-- | domain and codomain of morphisms
dom, cod :: morphism -> object
-- | the inverse of a morphism
inverse :: morphism -> Result morphism
-- | test if the signature morphism an inclusion
isInclusion :: morphism -> Bool
isInclusion _ = False -- in general no inclusion
-- | is a value of type morphism denoting a legal morphism?
legal_mor :: morphism -> Bool
comp :: Category object morphism => morphism -> morphism -> Result morphism
comp m1 m2 = if cod m1 == dom m2 then composeMorphisms m1 m2 else
fail "target of first and source of second morphism are different"
instance Ord sign => Category sign (DefaultMorphism sign) where
dom = domOfDefaultMorphism
cod = codOfDefaultMorphism
ide = ideOfDefaultMorphism
composeMorphisms = compOfDefaultMorphism
legal_mor = legalDefaultMorphism (const True)
{- | Abstract syntax, parsing and printing.
There are three types for abstract syntax:
basic_spec is for basic specifications (see CASL RefMan p. 5ff.),
symb_items is for symbol lists (see CASL RefMan p. 35ff.),
symb_map_items is for symbol maps (see CASL RefMan p. 35ff.).
class (Language lid, PrintTypeConv basic_spec,
EqPrintTypeConv symb_items,
EqPrintTypeConv symb_map_items)
=> Syntax lid basic_spec symb_items symb_map_items
| lid -> basic_spec symb_items symb_map_items
-- | parser for basic specifications
parse_basic_spec :: lid -> Maybe(AParser st basic_spec)
-- | parser for symbol lists
parse_symb_items :: lid -> Maybe(AParser st symb_items)
-- | parser for symbol maps
parse_symb_map_items :: lid -> Maybe(AParser st symb_map_items)
toAnnotedStrings :: lid -> basic_spec -> [Annoted String]
toItem :: lid -> basic_spec -> Item
-- default implementations
parse_basic_spec _ = Nothing
parse_symb_items _ = Nothing
parse_symb_map_items _ = Nothing
toAnnotedStrings _ _ = []
toItem l _ = error $ "toItem not yet implemented "
++ "for language " ++ (show l)
{- | Sentences, provers and symbols.
Provers capture the entailment relation between sets of sentences
and sentences. They may return proof trees witnessing proofs.
Signatures are equipped with underlying sets of symbols
(such that the category of signatures becomes a concrete category),
see CASL RefMan p. 191ff.
class (Language lid, Category sign morphism, Ord sentence,
Ord symbol, -- for efficient lookup
PrintTypeConv sign, PrintTypeConv morphism,
PrintTypeConv sentence, PrintTypeConv symbol)
=> Sentences lid sentence sign morphism symbol
| lid -> sentence sign morphism symbol
----------------------- sentences ---------------------------
-- | check whether a sentence belongs to a signature
is_of_sign :: lid -> sentence -> sign -> Bool
is_of_sign l _ _ = error $ statErrMsg l "is_of_sign"
-- | sentence translation along a signature morphism
map_sen :: lid -> morphism -> sentence -> Result sentence
map_sen l _ _ = statErr l "map_sen"
-- | simplification of sentences (leave out qualifications)
simplify_sen :: lid -> sign -> sentence -> sentence
simplify_sen _ _ = id -- default implementation
-- | parsing of sentences
parse_sentence :: lid -> Maybe (AParser st sentence)
parse_sentence _ = Nothing
print_sign :: lid -> sign -> Doc
-- | print a sentence with comments
print_named :: lid -> Named sentence -> Doc
print_named _ = printAnnoted (addBullet . pretty) . fromLabelledSen
----------------------- symbols ---------------------------
-- | set of symbols for a signature
sym_of :: lid -> sign ->
Set.Set symbol
sym_of l _ = error $ statErrMsg l "sym_of"
-- | symbol map for a signature morphism
symmap_of :: lid -> morphism -> EndoMap symbol
symmap_of l _ = error $ statErrMsg l "symmap_of"
-- | symbols have a name, see CASL RefMan p. 192
sym_name :: lid -> symbol -> Id
sym_name l _ = error $ statErrMsg l "sym_name"
-- | a dummy static analysis function to allow type checking *
.inline.hs files
inlineAxioms :: StaticAnalysis lid
basic_spec sentence symb_items symb_map_items
sign morphism symbol raw_symbol => lid -> String -> [Named sentence]
inlineAxioms _ _ = error "inlineAxioms"
-- | fail function for static analysis
statErr :: (Language lid, Monad m) => lid -> String -> m a
statErr lid = fail . statErrMsg lid
-- | error message for static analysis
statErrMsg :: (Language lid) => lid -> String -> String
statErrMsg lid str = "Logic." ++ str ++ " nyi for: " ++ language_name lid
This type class provides the data needed for an institution with symbols,
as explained in the structured specification semantics in the CASL
reference manual, chapter III.4.
The static analysis computes signatures from basic specifications,
and signature morphisms from symbol lists and symbol maps. The latter
needs an intermediate stage, so-called raw symbols, which are possibly
unqualified symbols. Normal symbols are always fully qualified.
In the CASL reference manual, our symbols are called "signature symbols",
and our raw symbols are called "symbols". (Terminology should be adapted.)
class ( Syntax lid basic_spec symb_items symb_map_items
, Sentences lid sentence sign morphism symbol
, GetRange raw_symbol, Ord raw_symbol, Pretty raw_symbol
basic_spec sentence symb_items symb_map_items
sign morphism symbol raw_symbol
| lid -> basic_spec sentence symb_items symb_map_items
sign morphism symbol raw_symbol
----------------------- static analysis ---------------------------
{- | static analysis of basic specifications and symbol maps.
The resulting bspec has analyzed axioms in it.
The resulting sign is an extension of the input sign
plus newly declared or redeclared symbols.
See CASL RefMan p. 138 ff. -}
Maybe((basic_spec, -- abstract syntax tree
sign, -- input signature, for the local
-- environment, carrying the previously
GlobalAnnos) -> -- global annotations
Result (basic_spec, ExtSign sign symbol
-- default implementation
basic_analysis _ = Nothing
-- | static analysis of symbol maps, see CASL RefMan p. 222f.
lid -> [symb_map_items] -> Result (EndoMap raw_symbol)
stat_symb_map_items l _ = statErr l "stat_symb_map_items"
-- | static analysis of symbol lists, see CASL RefMan p. 221f.
stat_symb_items :: lid -> [symb_items] -> Result [raw_symbol]
stat_symb_items l _ = statErr l "stat_symb_items"
------------------------- amalgamation ---------------------------
{- | Computation of colimits of signature diagram.
Indeed, it suffices to compute a coconce that is weakly amalgamable
Heterogeneous specification and the heterogeneous tool set
-- | architectural sharing analysis, see CASL RefMan p. 247ff.
ensures_amalgamability :: lid ->
([CASLAmalgOpt], -- the program options
Gr sign (Int,morphism), -- the diagram to be analyzed
[(Int, morphism)], -- the sink
Gr String String) -- the descriptions of nodes and edges
ensures_amalgamability l _ = warning Amalgamates
("amalgamability test not implemented for logic " ++ show l)
signature_colimit :: lid -> Gr sign (Int, morphism)
-> Result (sign,
Map.Map Int morphism)
signature_colimit l _ = statErr l "signature_colimit"
{- | rename and qualify the symbols considering a united incoming
morphisms, code out overloading and
create sentences for the overloading relation -}
qualify :: lid -> SIMPLE_ID -> LIB_ID -> morphism -> sign
-> Result (morphism, [Named sentence])
qualify l _ _ _ _ = statErr l "qualify"
-------------------- symbols and raw symbols ---------------------
{- | Construe a symbol, like f:->t, as a raw symbol.
This is a one-sided inverse to the function SymSySigSym
in the CASL RefMan p. 192. -}
symbol_to_raw :: lid -> symbol -> raw_symbol
symbol_to_raw l _ = error $ statErrMsg l "symbol_to_raw"
{- | Construe an identifier, like f, as a raw symbol.
See CASL RefMan p. 192, function IDAsSym -}
id_to_raw :: lid -> Id -> raw_symbol
id_to_raw l _ = error $ statErrMsg l "id_to_raw"
{- | Check wether a symbol matches a raw symbol, for
example, f:s->t matches f. See CASL RefMan p. 192 -}
matches :: lid -> symbol -> raw_symbol -> Bool
matches l _ _ = error $ statErrMsg l "matches"
--------------- operations on signatures and morphisms -----------
-- | the empty (initial) signature, see CASL RefMan p. 193
empty_signature :: lid -> sign
-- | union of signatures, see CASL RefMan p. 193
signature_union :: lid -> sign -> sign -> Result sign
signature_union l _ _ = statErr l "signature_union"
-- | intersection of signatures
intersection :: lid -> sign -> sign -> Result sign
intersection l _ _ = statErr l "intersection"
-- | final union of signatures, see CASL RefMan p. 194
final_union :: lid -> sign -> sign -> Result sign
final_union l _ _ = statErr l "final_union"
-- | union of signature morphims, see CASL RefMan p. 196
morphism_union :: lid -> morphism -> morphism -> Result morphism
morphism_union l _ _ = statErr l "morphism_union"
-- | subsignatures, see CASL RefMan p. 194
is_subsig :: lid -> sign -> sign -> Bool
{- | construct the inclusion morphisms between subsignatures,
see CASL RefMan p. 194 -}
subsig_inclusion :: lid -> sign -> sign -> Result morphism
subsig_inclusion l _ _ = statErr l "subsig_inclusion"
{- | the signature (co)generated by a set of symbols in another
signature is the smallest (largest) signature containing
(excluding) the set of symbols. Needed for revealing and
hiding, see CASL RefMan p. 197ff. -}
generated_sign, cogenerated_sign ::
lid ->
Set.Set symbol -> sign -> Result morphism
generated_sign l _ _ = statErr l "generated_sign"
cogenerated_sign l _ _ = statErr l "cogenerated_sign"
{- | Induce a signature morphism from a source signature and
a raw symbol map. Needed for translation (SP with SM).
See CASL RefMan p. 198 -}
lid -> EndoMap raw_symbol -> sign -> Result morphism
induced_from_morphism l _ _ = statErr l "induced_from_morphism"
{- | Induce a signature morphism between two signatures by a
raw symbol map. Needed for instantiation and views.
See CASL RefMan p. 198f. -}
induced_from_to_morphism ::
lid -> EndoMap raw_symbol -> ExtSign sign symbol
-> ExtSign sign symbol -> Result morphism
induced_from_to_morphism l _ _ _ =
statErr l "induced_from_to_morphism"
{- | Check whether a signature morphism is transportable.
See CASL RefMan p. 304f. -}
is_transportable :: lid -> morphism -> Bool
is_transportable _ _ = False -- safe default
{- | Check whether the underlying symbol map of a signature morphism
is_injective :: lid -> morphism -> Bool
is_injective _ _ = False -- safe default
-- | generate an ontological taxonomy, if this makes sense
theory_to_taxonomy :: lid
-> sign -> [Named sentence]
theory_to_taxonomy l _ _ _ _ = statErr l "theory_to_taxonomy"
inclusion :: StaticAnalysis lid basic_spec sentence symb_items symb_map_items
sign morphism symbol raw_symbol
=> lid -> sign -> sign -> Result morphism
inclusion lid s1 s2 = if is_subsig lid s1 s2 then subsig_inclusion lid s1 s2
else fail $ "Attempt to construct inclusion between non-subsignatures:\n"
{- | semi lattices with top (needed for sublogics). Note that `Ord` is
only used for efficiency and is not related to the /partial/ order given
by the lattice. Only `Eq` is used to define `isSubElem` -}
class (Ord l, Show l) => SemiLatticeWithTop l where
instance SemiLatticeWithTop () where
-- | less or equal for semi lattices
isSubElem :: SemiLatticeWithTop l => l -> l -> Bool
isSubElem a b = join a b == b
-- | class providing the minimal sublogic of an item
class MinSublogic sublogic item where
minSublogic :: item -> sublogic
-- | a default instance for no sublogics
instance MinSublogic () a where
-- | class providing also the projection of an item to a sublogic
class MinSublogic sublogic item => ProjectSublogic sublogic item where
projectSublogic :: sublogic -> item -> item
-- | a default instance for no sublogics
instance ProjectSublogic () b where
-- | like ProjectSublogic, but providing a partial projection
class MinSublogic sublogic item => ProjectSublogicM sublogic item where
projectSublogicM :: sublogic -> item -> Maybe item
-- | a default instance for no sublogics
instance ProjectSublogicM () b where
projectSublogicM _ = Just
-- | a class for providing a sublogi name
class SublogicName l where
sublogicName :: l -> String
instance SublogicName () where
{- Type class logic. The central type class of Hets, providing the
interface for logics. This type class is instantiated for many logics,
and it is used for the logic independent parts of Hets.
It hence provides an abstraction barrier between logic specific and
This type class extends the class StaticAnalysis by a sublogic mechanism.
Sublogics are important since they avoid the need to provide an own
instance of the class logic for each sublogic. Instead, the sublogic
can use the datastructures and operations of the main logic, and
functions are provided to test whether a given item lies within the
sublogic. Also, projection functions from a super-logic to a sublogic
class (StaticAnalysis lid
basic_spec sentence symb_items symb_map_items
sign morphism symbol raw_symbol,
SemiLatticeWithTop sublogics,
MinSublogic sublogics sentence,
ProjectSublogic sublogics basic_spec,
ProjectSublogicM sublogics symb_items,
ProjectSublogicM sublogics symb_map_items,
ProjectSublogic sublogics sign,
ProjectSublogic sublogics morphism,
ProjectSublogicM sublogics symbol,
Ord proof_tree, Show proof_tree,
basic_spec sentence symb_items symb_map_items
sign morphism symbol raw_symbol proof_tree
basic_spec sentence symb_items symb_map_items
sign morphism symbol raw_symbol proof_tree
-- | stability of the implementation
stability :: lid -> Stability
stability _ = Experimental
-- | for a process logic, return its data logic
data_logic :: lid -> Maybe AnyLogic
-- | the top sublogic, corresponding to the whole logic
top_sublogic :: lid -> sublogics
-- | list all the sublogics of the current logic
all_sublogics :: lid -> [sublogics]
all_sublogics li = [top_sublogic li]
{- | provide the embedding of a projected signature into the
proj_sublogic_epsilon :: lid -> sublogics -> sign -> morphism
proj_sublogic_epsilon _ _ s = ide s
----------------------- provers ---------------------------
-- | several provers can be provided. See module "
Logic.Prover"
provers :: lid -> [Prover sign sentence morphism sublogics proof_tree]
provers _ = [] -- default implementation
-- | consistency checkers
-> [ConsChecker sign sentence
sublogics morphism proof_tree]
cons_checkers _ = [] -- default implementation
-- | conservativity checkers
conservativityCheck :: lid
-> [ConservativityChecker sign sentence morphism]
conservativityCheck _ = []
-- | the empty proof tree
empty_proof_tree :: lid -> proof_tree
empty_proof_tree l = error $ statErrMsg l "empty_proof_tree"
----------------------- OMDoc ---------------------------
export_signToOmdoc :: lid -> SIMPLE_ID -> LIB_ID -> sign
-- default implementation
export_signToOmdoc lid _ _ _ =
error $ "export_signToOmdoc not yet implemented "
++ "for logic " ++ (show lid)
-- default implementation
export_morphismToOmdoc lid _ =
error $ "export_morphismToOmdoc not yet implemented "
++ "for logic " ++ (show lid)
export_senToOmdoc :: lid -> SIMPLE_ID -> LIB_ID -> sign
-- default implementation
export_senToOmdoc lid _ _ _ _ =
error $ "export_senToOmdoc not yet implemented "
++ "for logic " ++ (show lid)
-- default implementation
omdoc_metatheory _lid = Nothing
----------------------------------------------------------------
----------------------------------------------------------------
empty_theory :: StaticAnalysis lid
basic_spec sentence symb_items symb_map_items
sign morphism symbol raw_symbol =>
lid -> Theory sign sentence proof_tree
empty_theory lid = Theory (empty_signature lid)
Map.empty----------------------------------------------------------------
-- Existential type covering any logic
----------------------------------------------------------------
-- | the disjoint union of all logics
data AnyLogic = forall lid sublogics
basic_spec sentence symb_items symb_map_items
sign morphism symbol raw_symbol proof_tree .
basic_spec sentence symb_items symb_map_items
sign morphism symbol raw_symbol proof_tree =>
instance Show AnyLogic where
show (Logic lid) = language_name lid
instance Eq AnyLogic where
Logic lid1 == Logic lid2 = language_name lid1 == language_name lid2
StaticAnalysis (no sublogics)