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

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