Welcome to the Galois blog!Galois has been holding weekly technical seminars for several years on topics from functional programming, formal methods, compiler and language design, to cryptography, and operating system construction, with talks by many figures from the programming language and formal methods communities.To kick things off, we’ll start with slides from the past three tech talks, covering formal verification of microkernels, foreign function interface games for Isabelle, and making Haskell arrays faster.
Large Scale Monadic Refinement – Tales from L4.verifiedThomas Sewell, proof engineer from NICTA’s L4.verified project, gave a great tech talk about the process of engineering large scale proofs (in this case, for the sel4 microkernel). (.pdf slides)Abstract
Components of operating systems have emerged as an attractive target for formal analysis, thanks to the key importance of operating system correctness in establishing the security of a range of applications. These systems present a number of unique challenges for analysis, including their low level implementation and their detailed view of the system state. This talk will address none of these, instead focusing on the challenges of reasoning about (relatively) large, non-modular, inherently imperative software artefacts.The talk will describe the formalisation of the seL4 microkernel using a state monad with nondeterminism and exceptions, present a refinement and Hoare calculus, and discuss the impact of this chosen approach on the effectiveness of the overall verificationeffort.
PolyML, C, OCaml: Adventures in Foreign Function InterfacesThe August 19th tech talk was Joel Stanley, describing his adventures getting PolyML and OCaml to talk to each other, so that DPT and Isabelle could be friends. (.pdf slides)Abstract
In-process integration and data exchange between multiple language runtimes is a classic software engineering challenge. This talk describes our experiences in building an open-source tool for generating an “FFI bridge” between Poly/ML and OCaml, via the common C FFI provided by both language’s runtimes.The first intended use of this tool is to programmatically generate a bridge between Isabelle (on the Poly/ML side) and Intel’s Decision Procedure Toolkit API (on the OCaml side).
Stream Fusion for Haskell ArraysThe July 15th tech talk was Don Stewart, talking about stream fusion on Haskell arrays. (.pdf slides)Abstract
Arrays have traditionally been an awkward data structure for Haskell programmers. Despite the large number of array libraries available, they have remained relatively awkward to use in comparison to the rich suite of purely functional data structures, such as fingertrees or finite maps. Arrays have simply not been first class citizens in the language.In this talk we’ll begin with a survey of the more than a dozen array types available, including some new matrix libraries developed in the past year. I’ll then describe a new efficient, pure, and flexible array library for Haskell with a list like interface, based on work in the Data Parallel Haskell project, that employs stream fusion to dramatically reduce the cost of pure arrays. The implementation will be presented from the ground up, along with a discussion of the entire compilation process of the library, from source to assembly.