Download Report

Transcript
different logics. In particular we are interested in its logic HOL, a classical higher-order
logic based on the simply typed lambda calculus. It allows to specify functional programs
and to prove properties about them quite efficiently.
Our aim is to combine these two systems by providing an automated translation from
Haskell into Isabelle/HOL. The focus of our endeavour is set on producing Isabelle/HOL
theories which are still close to the original formulation in Haskell and which, therefore,
alleviate the effort of constructing proofs. This is the reason for choosing Isabelle/HOL
as the target languages rather than a richer logic like Isabelle/HOLCF. Isabelle/HOLCF
[17] is a conservative extension of Isabelle/HOL by Scott’s Logic of Computable Functions. This logic is well suited to describe Haskell’s non-strict semantics as well as partial
functions. We do not attempt to achieve similar results within Isabelle/HOL.
In fact the choice of the target logic Isabelle/HOL causes a number of difficulties
when trying to formalise a Haskell program. This includes Isabelle/HOL’s weaker type
system as well as it’s inability to formalise partial functions. The latter is indeed a
problem for Haskell’s non-strict semantics. Therefore, our implementation will not be
able to translate programs correctly which depend on Haskell’s non-strict semantics.
The problem that we are facing, regarding Isabelle/HOL’s type system, is its inability
to express type constructor classes. This has significant consequences, as this prevents
a proper translation of monadic Haskell programs.
Nevertheless, the implementation we are presenting here is able to translate most of
the Haskell 98 language [12]. This includes
• case, if-then-else, and let expressions;
• list comprehensions;
• where bindings and guards;
• mutually recursive functions and data type definitions;
• simple pattern bindings;
• definitions and instantiations of type classes; and
• monomorphic uses of monads including the do notation.
On the other hand the translation is not able to treat
• constructor type classes and consequently polymorphic uses of monads;
• non-simple pattern bindings; and
• irrefutable patterns.
In other words this translation is not complete. Furthermore, due to the semantics
of Isabelle/HOL, Haskell programs that depend on the non-strict semantics of Haskell
cannot be translated correctly. This leads to an translation which is in general unsound.
2