Now class invariants names use internally the class name
as a user Binding.qualifier.
This way one can use the same name for an invariant
in two different classes in the same theory:
doc_class "hypothesis" = math_content +
referentiable :: bool <= "True"
level :: "int option" <= "Some 2"
mcc :: "math_content_class" <= "hypt"
invariant d :: "mcc σ = hypt"
doc_class "math_proof" = math_content +
referentiable :: bool <= "True"
level :: "int option" <= "Some 2"
mcc :: "math_content_class" <= "prf_stmt"
invariant d :: "mcc σ = prf_stmt"
find_consts name:"math_proof.d_inv"
find_consts name:"hypothesis.d_inv"
Examples with value* that now work:
value*‹@{scholarly-paper.author ‹church'›}›
value*‹@{author ‹church›}›
value*‹@{Concept-High-Level-Invariants.author ‹church›}›
value*‹@{scholarly-paper.author-instances}›
value*‹@{author-instances}›
value*‹@{Concept-High-Level-Invariants.author-instances}›
Theory names should use Isabelle inner syntax to allow
objects referencing using long names.
For inner syntax, see the isar-ref manual
about syntax category "longid",
which is the same as "long_ident" of outer syntax
(but not "name" or "system_name").
ci/woodpecker/push/build Pipeline was successfulDetails
- Update term context section
- Add option to define a default class for declare_reference*
- Use defined symbol identifiers \<quote> and \<doublequote>
to simplify caveat section about lexical conventions
- Rename Manual theories to avoid issues
when using Syntax.parse_term that is not compatible with
with long-names staring with a number or an underscore
- Rewrite names used as mixfix annotation
for the term-antiquotations to rule out
mixform form excluded symbols
ci/woodpecker/push/build Pipeline was successfulDetails
- Add tests for monitors spanning two theories.
- Fix monitors trace update bug.
When updating a monitor trace when we define a new instance,
the monitor instance is already defined.
But we can not update the instance using the update_instance function
because this function needs a binding, i.e. a short name,
and then it will update or define a new instance if we want
to update a monitor in a super theory whose name is the same as
a monitor defined in the current theory.
Example:
in the super theory:
doc_class monitor_M =
tmM :: int
rejects "test_monitor_A"
accepts "test_monitor_head ~~ test_monitor_B ~~ test_monitor_C"
open_monitor*[test_monitor_M::monitor_M]
in the current theory:
doc_class monitor_M =
tmM :: int
rejects "test_monitor_B"
accepts "test_monitor_E ~~ test_monitor_C"
text*[test_monitor_head2::Concept_MonitorTest1.test_monitor_head]‹›
open_monitor*[test_monitor_M3::monitor_M]
...
==> ERROR : the instantiation of test_monitor_head2
will define a new instance current.test_monitor_M3
when updating the trace of super.test_monitor_M3
Hence we use the update_instance_entry function
which uses long names and only updates the entry.
ci/woodpecker/push/build Pipeline was successfulDetails
Use metalogic to generate meta term anti-quotations
The idea is for the Very_Deep_Interpretation
to source the shallow material,
and then update the checking and elaboration functions
of the term anti-quotations.
To achieve this, the mechanism of removing and reading the notations
(mixfixes) of the term-antiquotations, after the metalogic
is sourced, is used.
Example:
With shallow:
datatype "typ" = Isabelle_DOF_typ string ("@{typ _}")
Generate a datatype whose Constructor Isabelle_DOF_typ has
the notation @{typ ...}.
You get:
find_consts name:"Isabelle_DOF_typ"
find_consts
name: "Isabelle_DOF_typ"
found 1 constant(s):
Shallow_Interpretation.typ.Isabelle_DOF_typ :: "char list ⇒ typ"
With Deep:
no_notation "Isabelle_DOF_typ" ("@{typ _}")
consts Isabelle_DOF_typ :: "string ⇒ typ" ("@{typ _}")
The notation is removed and then added to the new Isabelle_DOF_typ constant.
You get:
find_consts name:"Isabelle_DOF_typ"
find_consts
name: "Isabelle_DOF_typ"
found 2 constant(s):
Deep_Interpretation.Isabelle_DOF_typ :: "char list ⇒ Core.typ"
Shallow_Interpretation.typ.Isabelle_DOF_typ :: "char list ⇒ Shallow_Interpretation.typ"
But only the Deep_Interpretation constant has the notation (mixfix).
Then new interpretation of term anti-quotations is available
for the user.
Id in instance datatype entry
and name, id and thy_name in onto_class datatype entry are now
useless, as this information is given by the name space.
Remove them
- Use a name space table to store ML inariants objects
- Remove docclass_inv_tab, docclass_eager_inv_tab,
and docclass_lazy_inv_tab tables and accesses
- Name spaces offer the possibility to make reporting
by embedding entries position. Use this possibility
for instances (docitems) reporting
- Position and theory entries in an Instance record are now
useless, as this information is given by the name space.
Remove them
- Use a name space table to store monitor infos objects
- Remove monitor_tab table, as monitor infos were moved
to the name space table
- It offers the possibility to define scoped versions
of monitors
- Use a name space table to store docitem (instance) objects
- Remove docobj table, as instances were moved to the name space table
- It offers the possibility to define scoped versions
of docitems declaration
for text* (and others docitems definition command like value*)
and declare_reference*.
Avoid reporting for meta arguments attributes of isabelle_DOF
commands and for text input of text*
The last reporting duplication not resolved comes
from the document_command command in Isa_DOF,
which parses the meta arguments twice,
one time for the creation of the docitem
with create_and_check_docitem which will add reporting
for the attributes value
(see conv_attrs whichs calls Syntax.read_term_global,
which iwill add reporting)
and the other for the document output
with document_output which also adds reporting
(see meta_args_2_latex which calls
(Syntax.check_term ctxt o Syntax.parse_term ctxt) with
ltx_of_markup and Syntax.parse_term also adds reporting)
- Make optional meta arguments completely optional
- Make meta arguments context of ML* available in its ML context
- Make meta arguments of ML* mandatory to mimic text*.
Without meta arguments, its behavior is already captured by
the ML command
ci/woodpecker/push/build Pipeline was successfulDetails
Support invariants on attributes of classes atttributes.
Example:
doc_class inv_test1 =
a :: int
doc_class inv_test2 =
b :: "inv_test1"
c:: int
invariant inv_test2 :: "c σ = 1"
invariant inv_test2' :: "a (b σ) = 2"
doc_class inv_test3 = inv_test1 +
b :: "inv_test1"
c:: int
invariant inv_test3 :: "a σ = 1"
invariant inv_test3' :: "a (b σ) = 2"
To support invariant on attributes in attributes
and invariant on attributes of the superclasses,
we check that the type of the attribute of the subclass is ground:›
ML‹
val Type(st, [ty]) = \<^typ>‹inv_test1›
val Type(st', [ty']) = \<^typ>‹'a inv_test1_scheme›
val t = ty = \<^typ>‹unit›
›
ci/woodpecker/push/build Pipeline was successfulDetails
- The current implementation triggers a warning when
rejected classes are find in the monitor,
and an error if monitor_strict_checking is enable.
It follows these rules:
Inside the scope of a monitor,
all instances of classes mentioned in its accepts_clause
(the ∗‹accept-set›) have to appear in the order specified
by the regular expression.
Instances not covered by an accept-set may freely occur.
Monitors may additionally contain a rejects_clause
with a list of class-ids (the reject-list).
This allows specifying ranges of
admissible instances along the class hierarchy:
- a superclass in the reject-list and a subclass in the
accept-expression forbids instances superior to the subclass, and
- a subclass S in the reject-list and a superclass T in the
accept-list allows instances of superclasses of T to occur freely,
instances of T to occur in the specified order and forbids
instances of S.
- No message is triggered for the free classes,
but two theory options, free_class_in_monitor_checking
and free_class_in_monitor_strict_checking,
are added and can be used if we want to trigger warnings or errors,
in the case we do not want free classes inside a monitor.
- Fix the checking warning when defining a monitor,
as the monitor was added to the monitor table and then
the instance of the monitor was added to the theory.
So a monitor had the bad behavior to check itself.
ci/woodpecker/push/build Pipeline was successfulDetails
By default invariants checking generates warnings.
If invariants_strict_checking theory option is enabled,
the checking generates errors.
- Update 2018-cicm-isabelle_dof-applications/IsaDofApplications.thy
and 2020-iFM-CSP/paper.thy to pass the checking of
the low level invariant checking function "check"
in scholarly_paper.thy,
which checks that the instances in a sequence of the same class
have a growing level.
For a sequence:
section*[intro::introduction]‹ Introduction ›
text*[introtext::introduction, level = "Some 1"]‹...›
introtext must have a level >= than intro.
- Bypass the checking of high-level invariants
when the class default_cid = "text",
the top (default) document class.
We want the class default_cid to stay abstract
and not have the capability to be defined with attribute,
invariants, etc.
Hence this bypass handles docitem without a class associated,
for example when you just want a document element to be referenceable
without using the burden of ontology classes.
ex: text*[sdf]\<open> Lorem ipsum @{thm refl}\<close>
The functions get_doc_class_global and get_doc_class_local trigger
an error when the class is "text" (default_cid),
then the functions like check_invariants which use it will fail
if the checking is enabled by default for all the theories.
ci/woodpecker/push/build Pipeline was successfulDetails
Trigger error when the attribute is not specified as an argument
of the antiquatation and is not an attribujte of the instance.
(In these case, the position of the attribute is NONE)
ci/woodpecker/push/build Pipeline was successfulDetails
- Make doc_class type and constant used by regular expression
in monitors ground
- Make class tag attribute ground (with serial())
- The previous items make possible
the evaluation of the trace attribute
and the definition of the trace-attribute term annotation
ci/woodpecker/push/build Pipeline was successfulDetails
- Add an eager and lazy invariants checking functions mechanism
for low level invariants to allow the checking of invariants
only when opening or closing a monitor instance.
The state of the monitor instances traces evolves when declaring
instances between open_monitor* and close_monitor* commands.
This mechanism can capture the changes be defining
invariants before or after traces are populated but not
before and after, with the current mechanism.
Two tables were added: docclass_eager_inv_tab
and docclass_lazy_inv_tab to store these invariants
- Implement CENELEC_50128 Table A.1 using this mechanism
ci/woodpecker/push/build Pipeline was successfulDetails
When defining low level invariants checking functions,
access to the monitor table might be useful.
So the table should be populated before the checking takes place.
ci/woodpecker/push/build Pipeline was successfulDetails
- Update phase datatype to be accurate with 7.3 in the standard
- Update cenelec_document class: according to the table C.1 in the
standard, written by, first check, and second check can be optional.
See Phase Planning line 4 in the table, for example
- Some specifications are external to the standard: implement them
as external_specification subclasses
- Fix phases attributes of classes
- Isabelle uses eager evaluation, so should the elaboration of terms
which are evaluated.
The value of instances are now registered in the data tables
of Isabelle/DOF when fully elaborated, ie,
term annotation antiquotations proposed by Isabelle/DOF in
an instance value are replaced by its value before registration
in Isabelle/DOF data
A new field, input_term, stores the lazy elaboration
and is used when elaboration is not wished
(to print the original input term declared by the user, for example)
- Clean up the simplication mechanism of the internal trace attribute
(used by monitor classes)
Loosen the dependency of the implementation of value* and term*
on Toplevel.transition.
Toplevel.transition should be avoided as it has specific behaviors
like only allowing atomic transactions.
- Use antiquotations when possible to reference
classes and attributes in text (typ, type and const antiquotations)
- Add explanation for cid, obj-id and oid
- Update ML*, text* an value* railroads
- Fix typos
- Add some TODOs for the next revision of the manual
- Fix some minor issues:
- Some figures did not longer correspond to their descriptions
- Some mechanisms (definitions - examples - etc.) in referencing
did not work any longer in the setting that we distribute.
- Fix typos
- Use antiquotations when possible to reference
classes and attributes in text (typ and const antiquotations)
- Update some isar code examples
- Fix typos
- Warning: the current implementation does yet not support
some use-cases, like invariant on monitors,
or the initialization of docitem without a class associated.
- Add first draft of the checking of invariants.
For now, it is disabled by default because some cases
are not yet supported, like the initialization of docitem
without a class associated.
ex: text*[sdf]‹ Lorem ipsum @{thm refl}›
- To enable the checking, one can use the theory attribute
"invariants_checking" by declaring it in a theory like this:
declare [[invariants_strict_checking = true]]
- A checking using basic tactics (unfolding and auto) can be enable
with the "invariants_checking_with_tactics" theory attribute
for specific use-cases
- The specification of invariants is now automatically abstracted,
so one must define an invariant like this now:
doc_class W =
w::"int"
invariant w :: "w σ ≥ 3"
The old form:
doc_class W =
w::"int"
invariant w :: "λσ. w σ ≥ 3"
is now deprecated.
The specification of the invariant still uses the σ-notation
and is defined globally by the name component "invariantN"
- Update the invariants definition in the theories to match
the new implementation
- Update the manual to explain this new feature
- Add small examples in src/tests/High_Level_Syntax_Invariants.thy
and src/tests/Ontology_Matching_Example.thy
- Add a new Term Annotation Antiquotation (TA)
to allow requests on instances.
Example:
@{C-instances} will return all the instances of the class "C"
defined in the generated theory
- Update ISA_transformers elaborate function signature to
take into account the case where the term argument
of a TA is irrelevant, for example when a TA has no argument.
Example with the TA of the instances of a class:
@{A-instances}
Here the TA has no argument and none second level type checking is
wished, so its associated check function can be the identity function
with respect to the ISA_transformers chek function type.
- Add some request examples in Evaluation.thy
- Fix typos
- Fix the generation of the record associated with
a class and used for the logic.
The old implementation generated a new attribute
for each attribute defined by a subclass,
even the ones that were overriding ones of the superclass.
The new implementation generates the attributes of the subclass
which are not overriding ones.
Warning:
It implies that overridden attributes in a subclass are not
new attributes added to the theory context.
So the base name of an attribute will refer to the attribute
of the last declared class where it is defined.
If ones wants to refer to atttributes, one should use
long names, even in the invariants of a subclass definition
which overrides the attribute used in the invariant.
For example,
in ~~/src/ontologies/scholarly_paper/scholarly_paper.thy:
doc_class technical = text_section +
definition_list :: "string list" <= "[]"
status :: status <= "description"
formal_results :: "thm list"
invariant L1 :: "λσ::technical. the (level σ) > 0"
type_synonym tc = technical (* technical content *)
doc_class example = text_section +
referentiable :: bool <= True
status :: status <= "description"
short_name :: string <= "''''"
doc_class math_content = tc +
referentiable :: bool <= True
short_name :: string <= "''''"
status :: status <= "semiformal"
mcc :: "math_content_class" <= "thm"
invariant s1 :: "λ σ::math_content. ¬referentiable σ ⟶ short_name σ = ''''"
invariant s2 :: "λ σ::math_content. technical.status σ = semiformal"
The class math_content overrride the attribute status
of the class technical, by using the type synonym tc,
but the base name of this attribute refers
to the attribute of the class example where it is last defined
and not just overridden.
So in the invariant s2 of the class math_content,
we must use the long name of the attribute,
i.e. the base name "status" with its qualifier which refers
to the superclass where it is defined, the class technical.
Type synonyms as qualifiers are not yet supported.
- Qualify classes that only override attributes of their superclass
as vitual classes by adding a virtual attribute.
This attribute is used to discriminate virtual classes and generate
an adequate make function to initialize their associated record.
The implementation uses an hidden attribute (the tag_attribute)
to force the virtual class to be concrete or the logic
by having a full new record definition associated with it.
For example:
doc_class W =
a::"int" <= "1"
doc_class X = W +
a::"int" <= "2"
The class X is tagged as a virtual class and
the record make functions of the classes W and X are:
W.make W_tag_attribute W_a
X.make X_tag_attribute X_a X_tag_attribute
So a record definition is added to the theory context for each class,
even though a virtual class only overrides
attributes of its superclass.
This behavior allows us to support definitions of new default values
for attributes in the subclass, as shown in the example.
- Factorize make name components
- Use Record name components instead of strings to refer to Record
components
- Fix typos
- Add a first implementation of a referential equivalence
for the built-ins term annotations (TA)
- Some built-ins remain as unspecified constants:
- the docitem TA offers a way to check the reference of
class instances without checking the instances type.
It must be avoided for certification
- the termrepr TA is left as an unspecified constant for now.
A major refactoring of code should be done to enable
referential equivalence for termrepr, by changing the dependency
between the Isa_DOF theory and the Assert theory.
The assert_cmd function in Assert should use the value* command
functions, which make the elaboration of the term
referenced by the TA before passing it to the evaluator
- Update the Evaluation test theory to test the referential equivalence
and expose some of current implementation limitations
- Add a warning about the docitem TA in the TermAntiquotations theory
The philosophy is for the tag attribute to be unique
for each class.
So this commit updates the implementation of this attribute
to match the philosophy.
The previous implementation associated a tag attribute
with a class but also with each super-class of this class
up to the top (default) class "text".
Now a class with super-classes has only one tag attribute.
Add a command value*
- The value* command uses the same code as the value command
and adds the possibility to evaluate
Term Annotation Antiquotations (TA)
with the help of the DOF_core.transduce_term_global function.
The DOF_core.transduce_term_global function,
in addition to the validation of a term
(also called a second level type checking),
is now able to make a so called elaboration:
it will construct the term referenced by a TA before
passing it to the evaluator.
- For a term to be evaluated, it must not be contain
the "undefined" constant whose evaluation always fails.
(See the code generation documentation).
Furthermore, the instance class generation is updated in such a way
that each of its attributes is initialized with a free variable
whose name shows to the final user that this attribute
is not initialized.
It implies that an instance class evaluation will be pass
to the normalization by evaluation (nbe) evaluator by default
if the final user does not specify a class instance entirely,
i.e. by specifying each attribute of the instance.
This choice is considered a decent compromise, considering
the speed and trustworthiness of the nbe evaluator.
(See the article
A Compiled Implementation of Normalization by Evaluation from 2008)
- Update the ISA transformer tab to add a function
which is used for the elaboration of the term referenced by the TA.to pass
- Add a first really basic draft of the implementation
of the elaboration of the built-ins TA and of an instance class:
- For the built-ins, the term referenced by the TA is returned
as it is;
- For an instance class, the value of the instance is returned.
- Make the tag attribute global by moving it to DOF_core structure
- Add a first draft for some evaluation tests
and expose the limitations of the current implementation
in Evaluation.thy
- Add a term antiquotation for document classes
and add the term* command which mimics the classical term command
and adds the possibility to use a term antiquotation
which references document classes:
one can use @{A ''A_instance''} to reference
an instance of the class A in a term* command.
- Reuse and update the ML_isa_check_generic visitor pattern
to add the function which checks the class instance of a class,
used by the term antiquotation for document classes.
Also, the update_isa functions now expect long name
(See builtin term antiquotations setup)
- The merge of ISA_transformer_tab has been update to avoid conflicts.
Indeed, the merge is ultra-critical: the transformer tabs were
just extended by letting *the first* entry
with the same long-name win.
Since the range is a (call-back) function, a comparison on its content
is impossible and some choice has to be made.
An alternative may be to use Symtab.join
- As classes names as constants are already bound to
"doc_class Regular_Exp.rexp" constants by add_doc_class_cmd function,
we use a prefix "doc_class_" when adding
document classes term antiquotations
abstract = {While Isabelle is mostly known as part of Isabelle/HOL (an interactive theorem prover), it actually provides a framework for developing a wide spectrum of applications. A particular strength of the Isabelle framework is the combination of text editing, formal verification, and code generation.\\\\Up to now, Isabelle's document preparation system lacks a mechanism for ensuring the structure of different document types (as, e.g., required in certification processes) in general and, in particular, mechanism for linking informal and formal parts of a document.\\\\In this paper, we present Isabelle/DOF, a novel Document Ontology Framework on top of Isabelle. Isabelle/DOF allows for conventional typesetting \emph{as well} as formal development. We show how to model document ontologies inside Isabelle/DOF, how to use the resulting meta-information for enforcing a certain document structure, and discuss ontology-specific IDE support.},
address = {Heidelberg},
author = {Achim D. Brucker and Idir Ait-Sadoune and Paolo Crisafulli and Burkhart Wolff},
booktitle = {Conference on Intelligent Computer Mathematics (CICM)},
doi = {10.1007/978-3-319-96812-4_3},
keywords = {Isabelle/Isar, HOL, Ontologies},
language = {USenglish},
location = {Hagenberg, Austria},
number = {11006},
pdf = {https://www.brucker.ch/bibliography/download/2018/brucker.ea-isabelle-ontologies-2018.pdf},
publisher = {Springer-Verlag},
series = {Lecture Notes in Computer Science},
title = {Using The Isabelle Ontology Framework: Linking the Formal with the Informal},
Communicating Sequential Processes (\<^csp>) is a language to specify and verify patterns of
interaction of concurrent systems. Together with CCS and LOTOS, it belongs to the family of
\<^emph>\<open>process algebras\<close>. \<^csp>'s rich theory comprises denotational, operational and algebraic semantic
facets and has influenced programming languages such as Limbo, Crystal, Clojure and most notably
Golang @{cite "donovan2015go"}. \<^csp> has been applied in industry as a tool for specifying and
verifying the concurrent aspects of hardware systems, such as the T9000 transansputer
@{cite "Barret95"}.
The theory of \<^csp> was first described in 1978 in a book by Tony Hoare @{cite "Hoare:1985:CSP:3921"},
but has since evolved substantially @{cite "BrookesHR84" and "brookes-roscoe85" and "roscoe:csp:1998"}.
\<^csp> describes the most common communication and synchronization mechanisms with one single language
primitive: synchronous communication written \<open>_\<lbrakk>_\<rbrakk>_\<close>. \<^csp> semantics is described by a fully abstract
model of behaviour designed to be \<^emph>\<open>compositional\<close>: the denotational semantics of a process \<open>P\<close>
encompasses all possible behaviours of this process in the context of all possible environments
\<open>P \<lbrakk>S\<rbrakk> Env\<close> (where \<open>S\<close> is the set of \<open>atomic events\<close> both \<open>P\<close> and \<open>Env\<close> must synchronize). This
design objective has the consequence that two kinds of choice have to be distinguished: \<^vs>\<open>0.1cm\<close>
\<^enum> the \<^emph>\<open>external choice\<close>, written \<open>_\<box>_\<close>, which forces a process "to follow" whatever
the environment offers, and \<^vs>\<open>-0.4cm\<close>
\<^enum> the \<^emph>\<open>internal choice\<close>, written \<open>_\<sqinter>_\<close>, which imposes on the environment of a process
"to follow" the non-deterministic choices made.\<^vs>\<open>0.3cm\<close>
\<close>
text\<open> \<^vs>\<open>-0.6cm\<close>
Generalizations of these two operators \<open>\<box>x\<in>A. P(x)\<close> and \<open>\<Sqinter>x\<in>A. P(x)\<close> allow for modeling the concepts
of \<^emph>\<open>input\<close> and \<^emph>\<open>output\<close>: Based on the prefix operator \<open>a\<rightarrow>P\<close> (event \<open>a\<close> happens, then the process
proceeds with \<open>P\<close>), receiving input is modeled by \<open>\<box>x\<in>A. x\<rightarrow>P(x)\<close> while sending output is represented
by \<open>\<Sqinter>x\<in>A. x\<rightarrow>P(x)\<close>. Setting choice in the center of the language semantics implies that
deadlock-freeness becomes a vital property for the well-formedness of a process, nearly as vital
as type-checking: Consider two events \<open>a\<close> and \<open>b\<close> not involved in a process \<open>P\<close>, then
\<open>(a\<rightarrow>P \<box> b\<rightarrow>P) \<lbrakk>{a,b}\<rbrakk> (a\<rightarrow>P \<sqinter> b\<rightarrow>P)\<close> is deadlock free provided \<open>P\<close> is, while
\<open>(a\<rightarrow>P \<sqinter> b\<rightarrow>P) \<lbrakk>{a,b}\<rbrakk> (a\<rightarrow>P \<sqinter> b\<rightarrow>P)\<close> deadlocks (both processes can make "ruthlessly" an opposite choice,
but are required to synchronize).
Verification of \<^csp> properties has been centered around the notion of \<^emph>\<open>process refinement orderings\<close>,
most notably \<open>_\<sqsubseteq>\<^sub>F\<^sub>D_\<close> and \<open>_\<sqsubseteq>_\<close>. The latter turns the denotational domain of \<^csp> into a Scott cpo
@{cite "scott:cpo:1972"}, which yields semantics for the fixed point operator \<open>\<mu>x. f(x)\<close> provided
that \<open>f\<close> is continuous with respect to \<open>_\<sqsubseteq>_\<close>. Since it is possible to express deadlock-freeness and
livelock-freeness as a refinement problem, the verification of properties has been reduced
traditionally to a model-checking problem for finite set of events \<open>A\<close>.
We are interested in verification techniques for arbitrary event sets \<open>A\<close> or arbitrarily
parameterized processes. Such processes can be used to model dense-timed processes, processes
with dynamic thread creation, and processes with unbounded thread-local variables and buffers.
However, this adds substantial complexity to the process theory: when it comes to study the
interplay of different denotational models, refinement-orderings, and side-conditions for
continuity, paper-and-pencil proofs easily reach their limits of precision.
Several attempts have been undertaken to develop a formal theory in an interactive proof system,
mostly in Isabelle/HOL @{cite "Camilleri91" and "tej.ea:corrected:1997" and "IsobeRoggenbach2010"
and "DBLP:journals/afp/Noce16"}.
This paper is based on @{cite "tej.ea:corrected:1997"}, which has been the most comprehensive
attempt to formalize denotational \<^csp> semantics covering a part of Bill Roscoe's Book
@{cite "roscoe:csp:1998"}. Our contributions are as follows:
\<^item> we ported @{cite "tej.ea:corrected:1997"} from Isabelle93-7 and ancient
ML-written proof scripts to a modern Isabelle/HOL version and structured Isar proofs,
and extended it substantially,
\<^item> we introduced new refinement notions allowing a deeper understanding of the \<^csp>
Failure/Divergence model, providing some meta-theoretic clarifications,
\<^item> we used our framework to derive new types of decomposition rules and
stronger induction principles based on the new refinement notions, and
\<^item> we integrate this machinery into a number of advanced verification techniques, which we
apply to two generalized paradigmatic examples in the \<^csp> literature,
the CopyBuffer and Dining Philosophers@{footnote \<open>All proofs concerning the
HOL-CSP 2 core have been published in the Archive of Formal Proofs @{cite "HOL-CSP-AFP"};
all other proofs are available at
\<^url>\<open>https://gitlri.lri.fr/burkhart.wolff/hol-csp2.0\<close>. In this paper, all Isabelle proofs are
Let two processes be defined as follows:\<^vs>\<open>0.2cm\<close>
\<^enum> \<open>P\<^sub>d\<^sub>e\<^sub>t = (a \<rightarrow> Stop) \<box> (b \<rightarrow> Stop)\<close>
\<^enum> \<open>P\<^sub>n\<^sub>d\<^sub>e\<^sub>t = (a \<rightarrow> Stop) \<sqinter> (b \<rightarrow> Stop)\<close>
\<close>
text\<open>These two processes \<open>P\<^sub>d\<^sub>e\<^sub>t\<close> and \<open>P\<^sub>n\<^sub>d\<^sub>e\<^sub>t\<close> cannot be distinguished by using
the trace semantics: \<open>\<T>(P\<^sub>d\<^sub>e\<^sub>t) = \<T>(P\<^sub>n\<^sub>d\<^sub>e\<^sub>t) = {[],[a],[b]}\<close>. To resolve this problem, Brookes @{cite "BrookesHR84"}
proposed the failures model, where communication traces were augmented with the
constraint information for further communication that is represented negatively as a refusal set.
A failure \<open>(t, X)\<close> is a pair of a trace \<open>t\<close> and a set of events \<open>X\<close> that a process can refuse if
any of the events in \<open>X\<close> were offered to him by the environment after performing the trace \<open>t\<close>.
The semantic function \<open>\<F>\<close> in the failures model maps a process to a set of refusals.
Let \<open>\<Sigma>\<close> be the set of events. Then, \<open>{([],\<Sigma>)} \<subseteq> \<F> Stop\<close> as the process \<open>Stop\<close> refuses all events.
For Example 1, we have \<open>{([],\<Sigma>\{a,b}),([a],\<Sigma>),([b],\<Sigma>)} \<subseteq> \<F> P\<^sub>d\<^sub>e\<^sub>t\<close>, while
\<open>{([],\<Sigma>\{a}),([],\<Sigma>\{b}),([a],\<Sigma>),([b],\<Sigma>)} \<subseteq> \<F> P\<^sub>n\<^sub>d\<^sub>e\<^sub>t\<close> (the \<open>_\<subseteq>_\<close> refers to the fact that
the refusals must be downward closed; we show only the maximal refusal sets here).
Thus, internal and external choice, also called \<^emph>\<open>nondeterministic\<close> and \<^emph>\<open>deterministic\<close>
choice, can be distinguished in the failures semantics.
However, it turns out that the failures model suffers from another deficiency with respect to
the phenomenon called infinite internal chatter or \<^emph>\<open>divergence\<close>.\<close>
text*[ex2::example, status=semiformal] \<open>
The following process \<open>P\<^sub>i\<^sub>n\<^sub>f\<close> is an infinite process that performs \<open>a\<close> infinitely
many times. However, using the \<^csp> hiding operator \<open>_\_\<close>, this activity is concealed:
\<^enum> \<open>P\<^sub>i\<^sub>n\<^sub>f = (\<mu> X. a \<rightarrow> X) \ {a}\<close>
\<close>
text\<open>where \<open>P\<^sub>i\<^sub>n\<^sub>f\<close> will be equivalent to \<open>\<bottom>\<close> in the process cpo ordering.
To distinguish divergences from the deadlock process, Brookes and Roscoe
proposed failure/divergence model to incorporate divergence traces @{cite "brookes-roscoe85"}.
A divergence trace is the one leading to a possible divergent behavior.
A well behaved process should be able to respond to its environment in a finite amount of time.
Hence, divergences are considered as a kind of a catastrophe in this model.
Thus, a process is represented by a failure set \<open>\<F>\<close>,
together with a set of divergence traces \<open>\<D>\<close>;
in our example, the empty trace \<open>[]\<close> belongs to \<open>\<D> P\<^sub>i\<^sub>n\<^sub>f\<close>.
The failure/divergence model has become the standard semantics for an enormous range of \<^csp>
research and the implementations of @{cite "fdr4" and "SunLDP09"}. Note, that the work
of @{cite "IsobeRoggenbach2010"} is restricted to a variant of the failures model only.
text\<open> First, we need a slight revision of the concept
of \<^emph>\<open>trace\<close>: if \<open>\<Sigma>\<close> is the type of the atomic events (represented by a type variable), then
we need to extend this type by a special event \<open>\<checkmark>\<close> (called "tick") signaling termination.
Thus, traces have the type \<open>(\<Sigma>\<uplus>\<checkmark>)\<^sup>*\<close>, written \<open>\<Sigma>\<^sup>\<checkmark>\<^sup>*\<close>; since \<open>\<checkmark>\<close> may only occur at the end of a trace,
we need to define a predicate \<open>front\<^sub>-tickFree t\<close> that requires from traces that \<open>\<checkmark>\<close> can only occur
at the end.
Second, in the traditional literature, the semantic domain is implicitly described by 9 "axioms"
over the three semantic functions \<open>\<T>\<close>, \<open>\<F>\<close> and \<open>\<D>\<close>.
Informally, these are:
\<^item> the initial trace of a process must be empty;
\<^item> any allowed trace must be \<open>front\<^sub>-tickFree\<close>;
\<^item> traces of a process are \<^emph>\<open>prefix-closed\<close>;
\<^item> a process can refuse all subsets of a refusal set;
\<^item> any event refused by a process after a trace \<open>s\<close> must be in a refusal set associated to \<open>s\<close>;
\<^item> the tick accepted after a trace \<open>s\<close> implies that all other events are refused;
\<^item> a divergence trace with any suffix is itself a divergence one
\<^item> once a process has diverged, it can engage in or refuse any sequence of events.
\<^item> a trace ending with \<open>\<checkmark>\<close> belonging to divergence set implies that its
maximum prefix without \<open>\<checkmark>\<close> is also a divergent trace.
More formally, a process \<open>P\<close> of the type \<open>\<Sigma> process\<close> should have the following properties:
@{cartouche [display, indent=10] \<open>([],{}) \<in> \<F> P \<and>
(\<forall> s X. (s,X) \<in> \<F> P \<longrightarrow> front_tickFree s) \<and>
(\<forall> s t . (s@t,{}) \<in> \<F> P \<longrightarrow> (s,{}) \<in> \<F> P) \<and>
(\<forall> s X Y. (s,Y) \<in> \<F> P \<and> X\<subseteq>Y \<longrightarrow> (s,X) \<in> \<F> P) \<and>
(\<forall> s X Y. (s,X) \<in> \<F> P \<and> (\<forall>c \<in> Y. ((s@[c],{}) \<notin> \<F> P)) \<longrightarrow> (s,X \<union> Y) \<in> \<F> P) \<and>
(\<forall> s X. (s@[\<checkmark>],{}) \<in> \<F> P \<longrightarrow> (s,X-{\<checkmark>}) \<in> \<F> P) \<and>
(\<forall> s t. s \<in> \<D> P \<and> tickFree s \<and> front_tickFree t \<longrightarrow> s@t \<in> \<D> P) \<and>
(\<forall> s X. s \<in> \<D> P \<longrightarrow> (s,X) \<in> \<F> P) \<and>
(\<forall> s. s@[\<checkmark>] \<in> \<D> P \<longrightarrow> s \<in> \<D> P)\<close>}
Our objective is to encapsulate this wishlist into a type constructed as a conservative
theory extension in our theory \<^holcsp>.
Therefore third, we define a pre-type for processes \<open>\<Sigma> process\<^sub>0\<close> by \<open> \<P>(\<Sigma>\<^sup>\<checkmark>\<^sup>* \<times> \<P>(\<Sigma>\<^sup>\<checkmark>)) \<times> \<P>(\<Sigma>\<^sup>\<checkmark>)\<close>.
Forth, we turn our wishlist of "axioms" above into the definition of a predicate \<open>is_process P\<close>
of type \<open>\<Sigma> process\<^sub>0 \<Rightarrow> bool\<close> deciding if its conditions are fulfilled. Since \<open>P\<close> is a pre-process,
we replace \<open>\<F>\<close> by \<open>fst\<close> and \<open>\<D>\<close> by \<open>snd\<close> (the HOL projections into a pair).
And last not least fifth, we use the following type definition:
Isabelle requires a proof for the existence of a witness for this set,
but this can be constructed in a straight-forward manner. Suitable definitions for
\<open>\<T>\<close>, \<open>\<F>\<close> and \<open>\<D>\<close> lifting \<open>fst\<close> and \<open>snd\<close> on the new \<open>'\<alpha> process\<close>-type allows to derive
the above properties for any \<open>P::'\<alpha> process\<close>. \<close>
\<open>\<^csp> Operators over the Process Type\<close>
text\<open> Now, the operators of \<^csp> \<open>Skip\<close>, \<open>Stop\<close>, \<open>_\<sqinter>_\<close>, \<open>_\<box>_\<close>, \<open>_\<rightarrow>_\<close>,\<open>_\<lbrakk>_\<rbrakk>_\<close> etc.
for internal choice, external choice, prefix and parallel composition, can
be defined indirectly on the process-type. For example, for the simple case of the internal choice,
we construct it such that \<open>_\<sqinter>_\<close> has type \<open>'\<alpha> process \<Rightarrow> '\<alpha> process \<Rightarrow> '\<alpha> process\<close> and
such that its projection laws satisfy the properties \<open>\<F> (P \<sqinter> Q) = \<F> P \<union> \<F> Q\<close> and
\<open>\<D> (P \<sqinter> Q) = \<D> P \<union> \<D> Q\<close> required from @{cite "roscoe:csp:1998"}.
This boils down to a proof that an equivalent definition on the pre-process type \<open>\<Sigma> process\<^sub>0\<close>
maintains \<open>is_process\<close>, \<^ie> this predicate remains invariant on the elements of the semantic domain.
For example, we define \<open>_\<sqinter>_\<close> on the pre-process type as follows:
\<^item> \<^theory_text>\<open>definition "P \<sqinter> Q \<equiv> Abs_process(\<F> P \<union> \<F> Q , \<D> P \<union> \<D> Q)"\<close>
where \<open>Rep_process\<close> and \<open>Abs_process\<close> are the representation and abstraction morphisms resulting
from the type definition linking the type \<open>'\<alpha> process\<close> isomorphically to the set \<open>'\<alpha> process\<^sub>0\<close>.
The projection into \<^emph>\<open>failures\<close> is defined by \<open>\<F> = fst \<circ> Rep_process\<close>, whereas the
\<^emph>\<open>divergences\<close> are defined bz \<open>\<D> = snd \<circ> Rep_process\<close>. Proving the above properties for
\<open>\<F> (P \<sqinter> Q)\<close> and \<open>\<D> (P \<sqinter> Q)\<close> requires a proof that \<open>(\<F> P \<union> \<F> Q , \<D> P \<union> \<D> Q)\<close>
satisfies the well-formedness conditions of \<open>is_process\<close>, which is fairly simple in this case.
The definitional presentation of the \<^csp> process operators according to @{cite "roscoe:csp:1998"}
follows always this scheme. This part of the theory comprises around 2000 loc.
What we are interested in this paper is the following refinement orderings for the
failure/divergence model.
\<^enum> \<open>P \<sqsubseteq>\<^sub>\<F>\<^sub>\<D> Q \<equiv> \<F> P \<supseteq> \<F> Q \<and> \<D> P \<supseteq> \<D> Q\<close>
\<^enum> \<open>P \<sqsubseteq>\<^sub>\<T>\<^sub>\<D> Q \<equiv> \<T> P \<supseteq> \<T> Q \<and> \<D> P \<supseteq> \<D> Q\<close>
\<^enum> \<open>P \<sqsubseteq>\<^sub>\<FF> Q \<equiv> \<FF> P \<supseteq> \<FF> Q, \<FF>\<in>{\<T>,\<F>,\<D>}\<close> \<close>
text\<open> Notice that in the \<^csp> literature, only \<open>\<sqsubseteq>\<^sub>\<F>\<^sub>\<D>\<close> is well studied for failure/divergence model.
Our formal analysis of different granularities on the refinement orderings
allows deeper understanding of the same semantics model. For example, \<open>\<sqsubseteq>\<^sub>\<T>\<^sub>\<D>\<close> turns
out to have in some cases better monotonicity properties and therefore allow for stronger proof
principles in \<^csp>. Furthermore, the refinement ordering \<open>\<sqsubseteq>\<^sub>\<F>\<close> analyzed here
is different from the classical
failure refinement in the literature that is studied for the stable failure model
@{cite "roscoe:csp:1998"}, where failures are only defined for stable
states, from which no internal progress is possible.
text\<open> For any denotational semantics, the fixed point theory giving semantics to systems
of recursive equations is considered as keystone. Its prerequisite is a complete partial ordering
\<open>_\<sqsubseteq>_\<close>. The natural candidate \<open>_\<sqsubseteq>\<^sub>\<F>\<^sub>\<D>_\<close> is unfortunately not complete for infinite \<open>\<Sigma>\<close> for the
generalized deterministic choice, and thus for the building block of the read-operations.
Roscoe and Brooks @{cite "Roscoe1992AnAO"} finally proposed another ordering, called the
\<^emph>\<open>process ordering\<close>, and restricted the generalized deterministic choice in a particular way such
that completeness could at least be assured for read-operations. This more complex ordering
is based on the concept \<^emph>\<open>refusals after\<close> a trace \<open>s\<close> and defined by \<open>\<R> P s \<equiv> {X | (s, X) \<in> \<F> P}\<close>.\<close>
text\<open>While the original work @{cite "tej.ea:corrected:1997"} was based on an own --- and different ---
fixed-point theory, we decided to base HOL-\<^csp> 2 on HOLCF (initiated by @{cite "muller.ea:holcf:1999"}
and substantially extended in @{cite "huffman.ea:axiomatic:2005"}).
HOLCF is based on parametric polymorphism with type classes. A type class is actually a
constraint on a type variable by respecting certain syntactic and semantics
requirements. For example, a type class of partial ordering, denoted by \<open>\<alpha>::po\<close>, is restricted to
all types \<open>\<alpha>\<close> possessing a relation \<open>\<le>:\<alpha>\<times>\<alpha>\<rightarrow>bool\<close> that is reflexive, anti-symmetric, and transitive.
Isabelle possesses a construct that allows to establish, that the type \<open>nat\<close> belongs to this class,
with the consequence that all lemmas derived abstractly on \<open>\<alpha>::po\<close> are in particular applicable on
\<open>nat\<close>. The type class of \<open>po\<close> can be extended to the class of complete partial ordering \<open>cpo\<close>.
A \<open>po\<close> is said to be complete if all non-empty directed sets have a least upper bound (\<open>lub\<close>).
Finally the class of \<open>pcpo\<close> (Pointed cpo) is a \<open>cpo\<close> ordering that has a least element,
denoted by \<open>\<bottom>\<close>. For \<open>pcpo\<close> ordering, two crucial notions for continuity (\<open>cont\<close>) and fixed-point operator
(\<open>\<mu>X. f(X)\<close>) are defined in the usual way. A function from one \<open>cpo\<close> to another one is said
to be continuous if it distributes over the \<open>lub\<close> of all directed sets (or chains).
One key result of the fixed-point theory is the proof of the fixed-point theorem:
\<open>HOL-CSP provides an important proof principle, the fixed-point induction:
@{cartouche [display, indent=5] \<open>cont f \<Longrightarrow> adm P \<Longrightarrow> P \<bottom> \<Longrightarrow> (\<And>X. P X \<Longrightarrow> P(f X)) \<Longrightarrow> P(\<mu>X. f X)\<close>}
\<close>
text\<open>Fixed-point induction of @{theorem th2} requires a small side-calculus for establishing the admissibility
of a predicate; basically, predicates are admissible if they are valid for any least upper bound
of a chain \<open>x\<^sub>1 \<sqsubseteq> x\<^sub>2 \<sqsubseteq> x\<^sub>3 ... \<close> provided that \<open>\<forall>i. P(x\<^sub>i)\<close>. It turns out that \<open>_\<sqsubseteq>_\<close> and \<open>_\<sqsubseteq>\<^sub>F\<^sub>D_\<close> as
well as all other refinement orderings that we introduce in this paper are admissible.
Fixed-point inductions are the main proof weapon in verifications, together with monotonicities
and the \<^csp> laws. Denotational arguments can be hidden as they are not needed in practical
In our framework, we implemented the pcpo process refinement together with the five refinement
orderings introduced in @{technical "orderings"}. To enable fixed-point induction, we first have
the admissibility of the refinements.
@{cartouche [display, indent=7] \<open>cont u \<Longrightarrow> mono v \<Longrightarrow> adm(\<lambda>x. u x \<sqsubseteq>\<^sub>\<FF> v x) where \<FF>\<in>{\<T>,\<F>,\<D>,\<T>\<D>,\<F>\<D>}\<close>}
Next we analyzed the monotonicity of these refinement orderings, whose results are then used as
decomposition rules in our framework.
Some \<^csp> operators, such as multi-prefix and non-deterministic choice, are monotonic
under all refinement orderings, while others are not.
\<^item> External choice is not monotonic only under \<open>\<sqsubseteq>\<^sub>\<F>\<close>, with the following monotonicities proved:
@{cartouche [display,indent=5]
\<open>P \<sqsubseteq>\<^sub>\<FF> P' \<Longrightarrow> Q \<sqsubseteq>\<^sub>\<FF> Q' \<Longrightarrow> (P \<box> Q) \<sqsubseteq>\<^sub>\<FF> (P' \<box> Q') where \<FF>\<in>{\<T>,\<D>,\<T>\<D>,\<F>\<D>}\<close>}
\<^item> Sequence operator is not monotonic under \<open>\<sqsubseteq>\<^sub>\<F>\<close>, \<open>\<sqsubseteq>\<^sub>\<D>\<close> or \<open>\<sqsubseteq>\<^sub>\<T>\<close>:
All refinements are right-side monotonic but \<open>\<sqsubseteq>\<^sub>\<F>\<close>, \<open>\<sqsubseteq>\<^sub>\<D>\<close> and \<open>\<sqsubseteq>\<^sub>\<T>\<close> are not left-side monotonic,
which can be explained by the interdependence relationship of failure and divergence projections
for the first component. We thus proved:
\<^item> Hiding operator is not monotonic under \<open>\<sqsubseteq>\<^sub>\<D>\<close>:
@{cartouche [display,indent=5] \<open>P \<sqsubseteq>\<^sub>\<FF> Q \<Longrightarrow> P \ A \<sqsubseteq>\<^sub>\<FF> Q \ A where \<FF>\<in>{\<T>,\<F>,\<T>\<D>,\<F>\<D>}\<close>}
Intuitively, for the divergence refinement of the hiding operator, there may be
some trace \<open>s\<in>\<T> Q\<close> and \<open>s\<notin>\<T> P\<close> such that it becomes divergent in \<open>Q \ A\<close> but
not in \<open>P \ A\<close>.
\<^item> Parallel composition is not monotonic under \<open>\<sqsubseteq>\<^sub>\<F>\<close>, \<open>\<sqsubseteq>\<^sub>\<D>\<close> or \<open>\<sqsubseteq>\<^sub>\<T>\<close>:
@{cartouche [display,indent=5] \<open>P \<sqsubseteq>\<^sub>\<FF> P' \<Longrightarrow> Q \<sqsubseteq>\<^sub>\<FF> Q' \<Longrightarrow> (P \<lbrakk>A\<rbrakk> Q) \<sqsubseteq>\<^sub>\<FF> (P' \<lbrakk>A\<rbrakk> Q') where \<FF>\<in>{\<T>\<D>,\<F>\<D>}\<close>}
The failure and divergence projections of this operator are also interdependent, similar to the
sequence operator. Hence, this operator is not monotonic with \<open>\<sqsubseteq>\<^sub>\<F>\<close>, \<open>\<sqsubseteq>\<^sub>\<D>\<close> and \<open>\<sqsubseteq>\<^sub>\<T>\<close>, but monotonic
\<open>Reference Processes and their Properties\<close>
text\<open>
We now present reference processes that exhibit basic behaviors, introduced in
fundamental \<^csp> works @{cite "Roscoe:UCS:2010"}. The process \<open>RUN A\<close> always
accepts events from \<open>A\<close> offered by the environment. The process \<open>CHAOS A\<close> can always choose to
accept or reject any event of \<open>A\<close>. The process \<open>DF A\<close> is the most non-deterministic deadlock-free
process on \<open>A\<close>, \<^ie>, it can never refuse all events of \<open>A\<close>.
To handle termination better, we added two new processes \<open>CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P\<close> and \<open>DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P\<close>.
%Note that we do not redefine \<open>RUN\<close> with \<open>SKIP\<close> because this process is supposed to never terminate,
%thus must be without it.
\<close>
(*<*) (* a test ...*)
text*[X22 ::math_content, level="Some 2" ]\<open>\<open>RUN A \<equiv> \<mu> X. \<box> x \<in> A \<rightarrow> X\<close> \<close>
text*[X32::"definition", level="Some 2", mcc=defn]\<open>\<open>CHAOS A \<equiv> \<mu> X. (STOP \<sqinter> (\<box> x \<in> A \<rightarrow> X))\<close> \<close>
Definition*[X42, level="Some 2"]\<open>\<open>CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P A \<equiv> \<mu> X. (SKIP \<sqinter> STOP \<sqinter> (\<box> x \<in> A \<rightarrow> X))\<close> \<close>
Definition*[X52::"definition", level="Some 2"]\<open>\<open>CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P A \<equiv> \<mu> X. (SKIP \<sqinter> STOP \<sqinter> (\<box> x \<in> A \<rightarrow> X))\<close> \<close>
text\<open> The \<open>RUN\<close>-process defined @{math_content X22} represents the process that accepts all
events, but never stops nor deadlocks. The \<open>CHAOS\<close>-process comes in two variants shown in
@{definition X32} and @{definition X42} @{definition X52}: the process that non-deterministically
stops or accepts any offered event, whereas \<open>CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P\<close> can additionally terminate.\<close>
(*>*)
Definition*[X2, level="Some 2"]\<open>\<open>RUN A \<equiv> \<mu> X. \<box> x \<in> A \<rightarrow> X\<close> \<close>
Definition*[X3, level="Some 2"]\<open>\<open>CHAOS A \<equiv> \<mu> X. (STOP \<sqinter> (\<box> x \<in> A \<rightarrow> X))\<close> \<close>
Definition*[X4, level="Some 2"]\<open>\<open>CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P A \<equiv> \<mu> X. (SKIP \<sqinter> STOP \<sqinter> (\<box> x \<in> A \<rightarrow> X))\<close>\<close>
Definition*[X5, level="Some 2"]\<open>\<open>DF A \<equiv> \<mu> X. (\<sqinter> x \<in> A \<rightarrow> X)\<close> \<close>
Definition*[X6, level="Some 2"]\<open>\<open>DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P A \<equiv> \<mu> X. ((\<sqinter> x \<in> A \<rightarrow> X) \<sqinter> SKIP)\<close> \<close>
text\<open>In the following, we denote \<open> \<R>\<P> = {DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P, DF, RUN, CHAOS, CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P}\<close>.
All five reference processes are divergence-free.
which was proven by using a particular lemma \<open>\<D> (\<mu> x. f x) = \<Inter>\<^sub>i\<^sub>\<in>\<^sub>\<nat> \<D> (f\<^sup>i \<bottom>)\<close>.
@{cartouche
[display,indent=8] \<open> D (\<PP> UNIV) = {} where \<PP> \<in> \<R>\<P> and UNIV is the set of all events\<close>
}
Regarding the failure refinement ordering, the set of failures \<open>\<F> P\<close> for any process \<open>P\<close> is
a subset of \<open>\<F> (CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P UNIV)\<close>.
\<^enum> \<open>CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P A \<sqsubseteq>\<^sub>\<F> CHAOS A\<close>
\<^enum> \<open>CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P A \<sqsubseteq>\<^sub>\<F> DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P A\<close>
\<^enum> \<open>CHAOS A \<sqsubseteq>\<^sub>\<F> DF A\<close>
\<^enum> \<open>DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P A \<sqsubseteq>\<^sub>\<F> DF A\<close>
\<^enum> \<open>DF A \<sqsubseteq>\<^sub>\<F> RUN A\<close> \<^vs>\<open>0.3cm\<close>
where 1 and 2 are immediate, and where 4 and 5 are directly obtained from our monotonicity
results while 3 requires an argument over the denotational space.
Thanks to transitivity, we can derive other relationships.\<close>
text\<open> Lastly, regarding trace refinement, for any process P,
its set of traces \<open>\<T> P\<close> is a subset of \<open>\<T> (CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P UNIV)\<close> and of \<open>\<T> (DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P UNIV)\<close> as well.
%As we already proved that \<open>CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P\<close> covers all failures,
%we can immediately infer that it also covers all traces.
%The \<open>DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P\<close> case requires a longer denotational proof.
text\<open>\<^noindent> A process \<open>P\<close> is deadlock-free if and only if after any trace \<open>s\<close> without \<open>\<checkmark>\<close>, the union of \<open>\<checkmark>\<close>
and all events of \<open>P\<close> can never be a refusal set associated to \<open>s\<close>, which means that \<open>P\<close> cannot
\<^noindent> We want to verify that \<open>SYSTEM\<close> implements \<open>COPY\<close>. As shown below, we apply fixed-point induction
to prove that \<open>SYSTEM\<close> refines \<open>COPY\<close> using the \<open>pcpo\<close> process ordering \<open>\<sqsubseteq>\<close> that implies all other
The copy buffer refinement proof \<open>DF UNIV \<sqsubseteq> COPY\<close> is a typical one step induction proof
with two goals:
\<open>base: \<bottom> \<sqsubseteq> Q\<close> and \<open>1-ind: X \<sqsubseteq> Q \<Longrightarrow> (_ \<rightarrow> X) \<sqsubseteq> Q\<close>. Now, if unfolding the fixed-point process \<open>Q\<close>
reveals two steps, the second goal becomes
\<open>X \<sqsubseteq> Q \<Longrightarrow> _ \<rightarrow> X \<sqsubseteq> _ \<rightarrow> _ \<rightarrow> Q\<close>. Unfortunately, this way, it becomes improvable
using monotonicities rules.
We need here a two-step induction of the form \<open>base0: \<bottom> \<sqsubseteq> Q\<close>, \<open>base1: _ \<rightarrow> \<bottom> \<sqsubseteq> Q\<close> and
\<open>2-ind: X \<sqsubseteq> Q \<Longrightarrow> _ \<rightarrow> _ \<rightarrow> X \<sqsubseteq> _ \<rightarrow> _ \<rightarrow> Q\<close> to have a sufficiently powerful induction scheme.
For this reason, we derived a number of alternative induction schemes (which are not available
in the HOLCF library), which are also relevant for our final Dining Philophers example.
These are essentially adaptions of k-induction schemes applied to domain-theoretic
setting (so: requiring \<open>f\<close> continuous and \<open>P\<close> admissible; these preconditions are
skipped here):\<^vs>\<open>0.2cm\<close>
\<^item> \<open>... \<Longrightarrow> \<forall>i<k. P (f\<^sup>i \<bottom>) \<Longrightarrow> (\<forall>X. (\<forall>i<k. P (f\<^sup>i X)) \<longrightarrow> P (f\<^sup>k X)) \<Longrightarrow> P (\<mu>X. f X)\<close>
\<^item> \<open>... \<Longrightarrow> \<forall>i<k. P (f\<^sup>i \<bottom>) \<Longrightarrow> (\<forall>X. P X \<longrightarrow> P (f\<^sup>k X)) \<Longrightarrow> P (\<mu>X. f X)\<close>
\<^noindent> In the latter variant, the induction hypothesis is weakened to skip \<open>k\<close> steps. When possible,
it reduces the goal size.
Another problem occasionally occurring in refinement proofs happens when the right side term
involves more than one fixed-point process (\<^eg> \<open>P \<lbrakk>A\<rbrakk> Q \<sqsubseteq> S\<close>). In this situation,
we need parallel fixed-point inductions. The HOLCF library offers only a basic one:
\<^item> \<open>... \<Longrightarrow> P \<bottom> \<bottom> \<Longrightarrow> (\<forall>X Y. P X Y \<Longrightarrow> P (f X) (g Y)) \<Longrightarrow> P (\<mu>X. f X) (\<mu>X. g X)\<close>
\<^noindent> This form does not help in cases like in \<open>P \<lbrakk>\<emptyset>\<rbrakk> Q \<sqsubseteq> S\<close> with the interleaving operator on the
right-hand side. The simplifying law is:
@{cartouche [display, indent=3]\<open>
(\<box>x\<in>A\<rightarrow>P x \<lbrakk>\<emptyset>\<rbrakk> \<box>x\<in>B\<rightarrow>Q x) = (\<box>x\<in>A \<rightarrow> ( P x \<lbrakk>\<emptyset>\<rbrakk> \<box>x\<in>B \<rightarrow> Q x)
\<box> (\<box>x\<in>B \<rightarrow> (\<box>x\<in>A \<rightarrow> P x \<lbrakk>\<emptyset>\<rbrakk> Q x))\<close>}
Here, \<open>(f X \<lbrakk>\<emptyset>\<rbrakk> g Y)\<close> does not reduce to the \<open>(X \<lbrakk>\<emptyset>\<rbrakk> Y)\<close> term but to two terms \<open>(f X \<lbrakk>\<emptyset>\<rbrakk> Y)\<close> and
\<open>(X \<lbrakk>\<emptyset>\<rbrakk> g Y)\<close>.
To handle these cases, we developed an advanced parallel induction scheme and we proved its
correctness:
\<^item> @{cartouche [display] \<open>... \<Longrightarrow> (\<forall>Y. P \<bottom> Y) \<Longrightarrow> (\<forall>X. P X \<bottom>)
\<Longrightarrow> \<forall>X Y. (P X Y \<and> P (f X) Y \<and> P X (g Y)) \<longrightarrow> P (f X) (g Y)
\<Longrightarrow> P (\<mu>X. f X) (\<mu>X. g X)\<close>}
\<^noindent> which allows for a "independent unroling" of the fixed-points in these proofs.
The astute reader may notice here that if the induction step is weakened (having more hypothesises),
% this should be theory_text, but is rejected for lexical reasons
Note that both philosophers and forks are pairwise independent
but both synchronize on \<open>picks\<close> and \<open>putsdown\<close> events. The philosopher of index 0 is left-handed
whereas the other \<open>N-1\<close> philosophers are right-handed. We want to prove that any configuration
is deadlock-free for an arbitrary number N.
First, we put the fork process under normal form. It has three states:
(1) on the table, (2) picked by the right philosopher or (3) picked by the left one:
@{theory_text [display,indent=5]
\<open>definition trans\<^sub>f i \<sigma> \<equiv> if \<sigma> = 0 then {picks i i, picks (i+1)%N i}
else if \<sigma> = 1 then {putsdown i i}
else if \<sigma> = 2 then {putsdown (i+1)%N i}
else {}
definition upd\<^sub>f i \<sigma> e \<equiv> if e = (picks i i) then 1
else if e = (picks (i+1)%N) i then 2
else 0
definition FORK\<^sub>n\<^sub>o\<^sub>r\<^sub>m i \<equiv> P\<^sub>n\<^sub>o\<^sub>r\<^sub>m\<lbrakk>trans\<^sub>f i, upd\<^sub>f i\<rbrakk> \<close>}
To validate our choice for the states, transition function \<open>trans\<^sub>f\<close> and update function \<open>upd\<^sub>f\<close>,
we prove that they are equivalent to the original process components: \<open>FORK\<^sub>n\<^sub>o\<^sub>r\<^sub>m i = FORK i\<close>.
The anti-symmetry of refinement breaks this down to the two refinement proofs \<open>FORK\<^sub>n\<^sub>o\<^sub>r\<^sub>m i \<sqsubseteq> FORK i\<close>
and \<open>FORK i \<sqsubseteq> FORK\<^sub>n\<^sub>o\<^sub>r\<^sub>m i\<close>, which are similar to the CopyBuffer example shown in
@{technical "illustration"}. Note, again, that this fairly automatic induct-simplify-proof just
involves reasoning on the derived algebraic rules, not any reasoning on the level of the
denotational semantics.
%Second we prove that the normal form process is equivalent to the original fork process
%by proving refinements in both directions. We note here that the first refinement \<open>FORK\<^sub>n\<^sub>o\<^sub>r\<^sub>m i \<sqsubseteq> FORK i\<close>
%requires a two steps induction as unfolding the original fixed-point process brings two steps
%\<open>FORK i = picks \<rightarrow> putsdown \<rightarrow> FORK i\<close>. After that we apply the same method
%to get the philosopher process under a normal form.
Thanks to @{theorem \<open>T3\<close>}, we obtain normalized processes
for \<open>FORKs\<close>, \<open>PHILs\<close> and \<open>DINING\<close>:
@{theory_text [display,indent=5]
\<open>definition "trans\<^sub>F \<equiv> \<lambda>fs. (\<Inter>\<^sub>i\<^sub><\<^sub>N. trans\<^sub>f i (fs!i))"
definition upd\<^sub>F \<equiv> \<lambda>fs e. let i=(fork e) in fs[i:=(upd\<^sub>f i (fs!i) e)]
, frametitle = \<open>\<open>\<open>Example Slide\<^sub>t\<^sub>e\<^sub>s\<^sub>t\<close> with items @{thm "HOL.refl"}\<close>\<close>
, framesubtitle = "''Subtitle''"]
\<open>This is an example!
\<^item> The term \<^term>\<open>refl\<close> is...
\<^item> and the term encoding the title of this frame is \<^term_>\<open>frametitle @{frame \<open>test_frame\<close>}\<close>\<close>
frame*[test_frame2
, frametitle = "''Example Slide''"
, framesubtitle = \<open>\<open>\<open>Subtitle\<^sub>t\<^sub>e\<^sub>s\<^sub>t:\<close> the value of \<^term>\<open>(3::int) + 3\<close> is @{value "(3::int) + 3"}\<close>\<close>]
frame*[test_frame3, frametitle = "''A slide with a Figure''"]
\<open>A figure
@{figure_content (width=45, caption=\<open>\<open>Figure\<^sub>t\<^sub>e\<^sub>s\<^sub>t\<close> is not the \<^term>\<open>refl\<close> theorem (@{thm "refl"}).\<close>)
"figures/A.png"}\<close>
frame*[test_frame4
, options = "''allowframebreaks''"
, frametitle = "''Example Slide with frame break''"
, framesubtitle = \<open>\<open>\<open>Subtitle\<^sub>t\<^sub>e\<^sub>s\<^sub>t:\<close> the value of \<^term>\<open>(3::int) + 3\<close> is @{value "(3::int) + 3"}\<close>\<close>]
\<open>
\<^item> The term \<^term>\<open>refl\<close> is...
\<^item> and the term encoding the title of this frame is \<^term_>\<open>frametitle @{frame \<open>test_frame4\<close>}\<close>
\<^item> The term \<^term>\<open>refl\<close> is...
\<^item> The term \<^term>\<open>refl\<close> is...
\<^item> The term \<^term>\<open>refl\<close> is...
\<^item> The term \<^term>\<open>refl\<close> is...
\<^item> The term \<^term>\<open>refl\<close> is...
\<^item> The term \<^term>\<open>refl\<close> is...
\<^item> The term \<^term>\<open>refl\<close> is...
\<^item> The term \<^term>\<open>refl\<close> is...
\<^item> The term \<^term>\<open>refl\<close> is...
\<^item> The term \<^term>\<open>refl\<close> is...
\<^item> The term \<^term>\<open>refl\<close> is...
\<^item> The term \<^term>\<open>refl\<close> is...
\<^item> The term \<^term>\<open>refl\<close> is...
\<^item> The term \<^term>\<open>refl\<close> is...
\<^item> The term \<^term>\<open>refl\<close> is...
\<^item> The term \<^term>\<open>refl\<close> is...
\<^item> The term \<^term>\<open>refl\<close> is...
\<^item> The term \<^term>\<open>refl\<close> is...
\<comment> \<open>Cells must have at least one nucleus. However, this should be executable.\<close>
find_theorems (70)name:"eucaryotic_cells"
find_theorems name:has_nucleus
value "is\<^sub>n\<^sub>u\<^sub>c\<^sub>l\<^sub>e\<^sub>u\<^sub>s (mk\<^sub>n\<^sub>u\<^sub>c\<^sub>l\<^sub>e\<^sub>u\<^sub>s X)"
term \<open>eucaryotic_cells.organelles\<close>
value \<open>(eucaryotic_cells.organelles(eucaryotic_cells.make X Y Z Z Z [] []))\<close>
value \<open>has_nucleus_inv(eucaryotic_cells.make X Y Z Z Z [] [])\<close>
value \<open>has_nucleus_inv(eucaryotic_cells.make X Y Z Z Z [] [upcast\<^sub>n\<^sub>u\<^sub>c\<^sub>l\<^sub>e\<^sub>u\<^sub>s (nucleus.make a b c )])\<close>
, frametitle = \<open>\<open>\<open>Example Slide\<^sub>t\<^sub>e\<^sub>s\<^sub>t\<close> with items @{thm "HOL.refl"}\<close>\<close>
, framesubtitle = "''Subtitle''"]
\<open>This is an example!
\<^item> The term \<^term>\<open>refl\<close> is...
\<^item> and the term encoding the title of this frame is \<^term_>\<open>frametitle @{frame \<open>test_frame\<close>}\<close>\<close>
frame*[test_frame2
, frametitle = "''Example Slide''"
, framesubtitle = \<open>\<open>\<open>Subtitle\<^sub>t\<^sub>e\<^sub>s\<^sub>t:\<close> the value of \<^term>\<open>(3::int) + 3\<close> is @{value "(3::int) + 3"}\<close>\<close>]
, frametitle = "''Example Slide with frame break''"
, framesubtitle = \<open>\<open>\<open>Subtitle\<^sub>t\<^sub>e\<^sub>s\<^sub>t:\<close> the value of \<^term>\<open>(3::int) + 3\<close> is @{value "(3::int) + 3"}\<close>\<close>]
\<open>
\<^item> The term \<^term>\<open>refl\<close> is...
\<^item> and the term encoding the title of this frame is \<^term_>\<open>frametitle @{frame \<open>test_frame3\<close>}\<close>
\<^item> The term \<^term>\<open>refl\<close> is...
\<^item> The term \<^term>\<open>refl\<close> is...
\<^item> The term \<^term>\<open>refl\<close> is...
\<^item> The term \<^term>\<open>refl\<close> is...
\<^item> The term \<^term>\<open>refl\<close> is...
\<^item> The term \<^term>\<open>refl\<close> is...
\<^item> The term \<^term>\<open>refl\<close> is...
\<^item> The term \<^term>\<open>refl\<close> is...
\<^item> The term \<^term>\<open>refl\<close> is...
\<^item> The term \<^term>\<open>refl\<close> is...
\<^item> The term \<^term>\<open>refl\<close> is...
\<^item> The term \<^term>\<open>refl\<close> is...
\<^item> The term \<^term>\<open>refl\<close> is...
\<^item> The term \<^term>\<open>refl\<close> is...
\<^item> The term \<^term>\<open>refl\<close> is...
\<^item> The term \<^term>\<open>refl\<close> is...
\<^item> The term \<^term>\<open>refl\<close> is...
\<^item> The term \<^term>\<open>refl\<close> is...