The bike commute challenge – status

The Bike Commute Challenge is a wonderful Oregon tradition that Galois has participated in for the past 3 years. This year was a bit disruptive for Galois commuters, because we moved offices from Beaverton to downtown Portland. I think quite a few West-siders haven’t yet figured out the best way to get downtown by bike. Nevertheless, we’re holding steady at an overall 15% commute rate, with a few folks standing out from the crowd: Sigbjorn Finne at 360 miles and Paul Heinlein at 250 miles.The challenge web site has had a few ups and downs (er, mostly downs), but it seems to be back on-line, so I’m hoping folks are able to log their trips without troubles. One weird thing is I think they’re miscomputing the commute rate – it says Paul and Sigbjorn are around 80%, but I’m pretty sure they’re both at 100%, so perhaps there are still a few kinks left to work out. (and once they are worked out, I suspect our overall rate will be well-above 15%)Anyone reading this, please commend any of your bike-commuting colleagues, and I’ll take this opportunity to thank everyone for participating (Galwegians and everyone else!)

Read More

FMCAD’08 is coming to Portland!

Formal Methods in Computer Aided Design (FMCAD’08) is the preeminent conference in formal methods for hardware and systems, and this year, it’ll be held in downtown Portland, November 17-20. The advance program has been announced, and the lineup of technical papers, invited tutorials, invited speakers, and panel discussion looks awesome.Registration is open, so be sure to get your spot soon!Galois is sponsoring this year’s conference, along with Cadence, IBM, Intel, NEC, and Synopsis.  If you attend, stop by Galois; we’re only a few blocks from the conference hotel.

Read More

Left-fold enumerators: a safe, expressive and efficient I/O interface for Haskell

Johan Tibell, from Google, visited Galois on Monday 15th September, and gave a tech talk about efficient IO in Haskell, based on left-fold enumerators, along with a demo of his high perf. Haskell webserver, Hyena, based on left-fold IO. (.pdf slides).For more on left-fold, resource-managing IO subsystems, see Oleg Kiselyov’s work on the best collection traversal interface, From enumerators to cursors: turning the left fold inside out and Peng Li’s work on massively threaded Haskell web servers based on epoll. This stuff is quite hot, with Oleg coincidentally talking about left folds for web servers next week, at DEFUN.

Photo of roomLeft-fold IO

Abstract

I will describe a programming style for I/O operations that is based on left-fold enumerators. This style of programming is more expressive than imperative style I/O represented by the Unix functions read and write, and safer than lazy I/O using streams. Left-fold enumerators offers both high-performance using block based I/O and safety in terms of error handling and resource usage. I will demonstrate Hyena, a web server prototype written in Haskell, as an example of left-fold enumerator style of programming.This talk is intended as a starting point for further discussions on what would be a good interface for I/O rather than a presentation of finished research.

The talk was held at 1pm, on Monday 15th September, at Galois, in Portland.

Read More

Theorem Proving for Verification

This Galois Tech Talk was held on Tuesday September 16th, 10.30am, with John Harrison, Principal Engineer at Intel, talking about theorem proving for formal verification. (You can also check out his Handbook of Practical Logic and Automated Reasoning). (.pdf slides, proof demo)

Left-fold IO

Abstract

The theorem proving approach to verification involves modelling a system in a rich formalism such as higher-order logic or set theory, then performing a human-driven interactive correctness proof using a proof assistant. In a striking contrast, techniques like model checking, by limiting the user to a less expressive formalism (propositional logic, CTL etc.), can offer completely automated decision methods, making them substantially easier to use and often more productive. With this in mind, why should one be interested in the theorem proving approach? In this tutorial I will explain some of the advantages of theorem proving, showing situations where the generality of theorem proving is beneficial, allowing us to tackle domains that are beyond the scope of automated methods or providing other important advantages. I will talk about the state of the art in theorem proving systems and and give a little demonstration to give an impression of what it’s like to work with such a system.

John Harrison talking about theorem provingGalois 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. The talks are open and free.

Read More

Pretty-Printing a Really Long Formula (or, “What a Mathematician Could Learn from Haskell”)

The next Galois Tech Talk will be Tuesday September 9th, 10.30am, with Lee Pike, talking about how to visually present proofs and formal notation.(.pdf slides):What Mathematicians can learn from HaskellAbstract

To the typical engineer or evaluator, mathematics can be scary, logic can be scarier, and really long specifications can simply be overwhelming. This talk is about the problem of the visual presentation of formal specifications clearly and concisely. We take as our initial inspiration Leslie Lamport’s brief papers, “How to Write a Long Formula” and “How to Write a Proof” in which he proposes methods for writing the long and tedious formulas and proofs that appear in formal specification and verification.I will describe the problem and present one particular solution, as implemented in a simple pretty-printer I’ve written (in Haskell), that uses indentation and labels to more easily visually parse long formulas. Ultimately, I propose a “HOL Normal Form” for presenting specifications, much like BNF is used for presenting language definitions.

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. The talks are open and free.

Read More

Galois Open House

Please join us for an open house to celebrate our new office space in downtown Portland’s historic Commonwealth Building. Located on SW 6th Avenue between Stark and Washington streets, we’re easily accessible via MAX or TriMet buses. We’re up on the third floor.Parking will also be available in the Alder Street Star Park parking garage located at 615 SW Alder, just one block from our building; validation will be provided at the event.

What: Galois Open House
When: Thursday, September 18
Time: 4:00 pm – 6:00 pm
Where: The Commonwealth Building421 SW Sixth Ave., Ste. 300

RSVP: Anne Marie @ ph. 503.626.6616, x153 or email anne at galois.com

Read More

Bringing the Power of GPUs to Haskell

This Galois tech talk was held on Tuesday, September 2nd, 10.30am. Sean Lee from UNSW, Sydney, talked about programming GPUs from Haskell. Here’ s the abstract  (.pdf slides):Bringing the Power of GPUs into the Haskell WorldGpuGen: Bringing the Power of GPUs into the Haskell WorldAbstract

For the last decade, the performance of GPUs has out-grown CPUs, and their programmability has also improved to the level where they can be used for general-purpose computations. Nonetheless, GPU programming is still limited only to those who understand the hardware architecture and the parallel processing. This is because the current GPU programming systems are based on the specialized parallel processing model, and require low-level attention in many aspects such as thread launching and synchronization.The need for a programming system which provides a high-level abstraction layer on top of the GPU programming systems without losing the performance gain arises to facilitate the use of GPUs. Instead of writing a programming system from the scratch, the development of a Haskell extension has been chosen as the ideal approach, since the Haskell community has already accumulated a significant amount of research and resources for Nested Data Parallelism, which could be adopted to provide a high-level abstraction on GPU programming and even to broaden the applicability of GPU programming. In addition, the Foreign Function Interface of Haskell is sufficient to be the communication medium to the GPU.GpuGen is what connects these two dots: GPUs and Haskell. It compiles the collective data operations such as scan, fold, map, etc, which incur most computation cost, to the GPU. The design of the system, the structure of the GpuGen compiler, and the current development status are to be discussed in the talk.

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.The talks are open and free. If you’re planning to attend, dropping a note to dons at galois.com is appreciated, but not required. If you’re interested in giving a talk, we’re always looking for new speakers.

Read More

Galois Tech Talks

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 RefinementLarge 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.

Adventures in FFIsPolyML, 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 FusionStream 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.

Read More