Ziele Untersuchung
mit Columbo Integrität von
Datenbanken Interaktion und
Portierbarkeit Ergonomie der
Schnittstellen

Angebot Produkte Projekt Beratung

Mittel Analytik Modellierung Sprachen Algebra Logik Hardware Denken Kreativität

Zusammenhänge Gesellschaft Wirtschaft Branche Firma

Benutzer


products/Sources/formale Sprachen/Isabelle/HOL/Imperative_HOL/ (Isabelle Prover Version 2025-1^©) Datei vom 16.11.2025 mit Größe 7 kB

SSL Overview.thy

Sprache: Isabelle

(*  Title:      HOL/Imperative_HOL/Overview.thy
    Author:     Florian Haftmann, TU Muenchen
*)

(*<*)
theory Overview
imports Imperative_HOL "HOL-Library.LaTeXsugar"
begin

unbundle constrain_space_syntax
(*>*)

text ‹
‹Imperative HOL› is a lightweight framework for reasoning
about imperative data structures in ‹Isabelle/HOL›
cite‹"Nipkow-et-al:2002:tutorial"›. Its basic ideas are described in
cite‹"Bulwahn-et-al:2008:imp_HOL"›. However their concrete
realisation has changed since, due to both extensions and
refinements. Therefore this overview wants to present the framework
\qt{as it is} by now. It focusses on the user-view, less on matters
of construction. For details study of the theory sources is
encouraged.
›

section ‹A polymorphic heap inside a monad›

text ‹
Heaps (🚫‹heap›) can be populated by values of class 🚫‹heap›; HOL's default types are
already instantiated to class 🚫‹heap›. Class 🚫‹heap› is a subclass of 🚫‹countable›;
see theory ‹Countable› for ways to instantiate types as 🚫‹countable›.

The heap is wrapped up in a monad typ‹'a Heap› by means of the
following specification:

\begin{quote}
🚫‹Heap›
\end{quote}

Unwrapping of this monad type happens through

\begin{quote}
🚫‹execute› \\
@{thm execute.simps [no_vars]}
\end{quote}

This allows for equational reasoning about monadic expressions; the
fact collection ‹execute_simps› contains appropriate rewrites
for all fundamental operations.

Primitive fine-granular control over heaps is available through rule
‹Heap_cases›:

\begin{quote}
@{thm [break] Heap_cases [no_vars]}
\end{quote}

Monadic expression involve the usual combinators:

\begin{quote}
🚫‹return› \\
🚫‹bind› \\
🚫‹raise›
\end{quote}

This is also associated with nice monad do-syntax. The typ‹string› argument to const‹raise› is
just a codified comment.

Among a couple of generic combinators the following is helpful for
establishing invariants:

\begin{quote}
🚫‹assert› \\
@{thm assert_def [no_vars]}
\end{quote}
›

section ‹Relational reasoning about 🚫‹Heap› expressions›

text ‹
To establish correctness of imperative programs, predicate

\begin{quote}
🚫‹effect›
\end{quote}

provides a simple relational calculus. Primitive rules are ‹effectI› and ‹effectE›, rules
appropriate for reasoning about imperative operations are available in the ‹effect_intros› and
‹effect_elims› fact collections.

Often non-failure of imperative computations does not depend
on the heap at all; reasoning then can be easier using predicate

\begin{quote}
🚫‹success›
\end{quote}

Introduction rules for const‹success› are available in the
‹success_intro› fact collection.

const‹execute›, const‹effect›, const‹success› and const‹bind›
are related by rules ‹execute_bind_success›, ‹success_bind_executeI›, ‹success_bind_effectI›,
‹effect_bindI›, ‹effect_bindE› and ‹execute_bind_eq_SomeI›.
›

section ‹Monadic data structures›

text ‹
The operations for monadic data structures (arrays and references)
come in two flavours:

\begin{itemize}

\item Operations on the bare heap; their number is kept minimal
to facilitate proving.

\item Operations on the heap wrapped up in a monad; these are designed
for executing.

\end{itemize}

Provided proof rules are such that they reduce monad operations to
operations on bare heaps.

Note that HOL equality coincides with reference equality and may be
used as primitive executable operation.
›

subsection ‹Arrays›

text ‹
Heap operations:

\begin{quote}
🚫‹Array.alloc› \\
🚫‹Array.present› \\
🚫‹Array.get› \\
🚫‹Array.set› \\
🚫‹Array.length› \\
🚫‹Array.update› \\
🚫‹Array.noteq›
\end{quote}

Monad operations:

\begin{quote}
🚫‹Array.new› \\
🚫‹Array.of_list› \\
🚫‹Array.make› \\
🚫‹Array.len› \\
🚫‹Array.nth› \\
🚫‹Array.upd› \\
🚫‹Array.map_entry› \\
🚫‹Array.swap› \\
🚫‹Array.freeze›
\end{quote}
›

subsection ‹References›

text ‹
Heap operations:

\begin{quote}
🚫‹Ref.alloc› \\
🚫‹Ref.present› \\
🚫‹Ref.get› \\
🚫‹Ref.set› \\
🚫‹Ref.noteq›
\end{quote}

Monad operations:

\begin{quote}
🚫‹Ref.ref› \\
🚫‹Ref.lookup› \\
    \<^term_type>\<open>Ref.update\<close> \\
    \<^term_type>\<open>Ref.change\<close>
  \end{quote}
\<close>

section \<open>Code generation\<close>

text \<open>
  Imperative HOL sets up the code generator in a way that imperative
  operations are mapped to suitable counterparts in the target
  language.  For \<open>Haskell\<close>, a suitable \<open>ST\<close> monad is used;
  for \<open>SML\<close>, \<open>Ocaml\<close> and \<open>Scala\<close> unit values ensure
  that the evaluation order is the same as you would expect from the
  original monadic expressions.  These units may look cumbersome; the
  target language variants \<open>SML_imp\<close>, \<open>Ocaml_imp\<close> and
  \<open>Scala_imp\<close> make some effort to optimize some of them away.
\<close>

section \<open>Some hints for using the framework\<close>

text \<open>
  Of course a framework itself does not by itself indicate how to make
  best use of it.  Here some hints drawn from prior experiences with
  Imperative HOL:

  \begin{itemize}

    \item Proofs on bare heaps should be strictly separated from those
      for monadic expressions.  The first capture the essence, while the
      latter just describe a certain wrapping-up.

    \item A good methodology is to gradually improve an imperative
      program from a functional one.  In the extreme case this means
      that an original functional program is decomposed into suitable
      operations with exactly one corresponding imperative operation.
      Having shown suitable correspondence lemmas between those, the
      correctness prove of the whole imperative program simply
      consists of composing those.

    \item Whether one should prefer equational reasoning (fact
      collection \<open>execute_simps\<close> or relational reasoning (fact
      collections \<open>effect_intros\<close> and \<open>effect_elims\<close>) depends
      on the problems to solve.  For complex expressions or
      expressions involving binders, the relation style is usually
      superior but requires more proof text.

    \item Note that you can extend the fact collections of Imperative
      HOL yourself whenever appropriate.

  \end{itemize}
\<close>

end

Messung V0.5 in Prozent

¤ Dauer der Verarbeitung: 0.76 Sekunden ¤

Wurzel

Suchen

PVS Prover

Isabelle Prover

NIST Cobol Testsuite

Cephes Mathematical Library

Vienna Development Method

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.