Galois Tech Talks

abstract:
A polymorphic function may be instantiated at many different types; if the function is parametrically polymorphic, then all of its instances must behave uniformly. Reynolds' parametricity theorem expresses this precisely, in terms of binary relations derived from types. One application of the parametricity theorem is to derive Wadler-style "free theorems" about a polymorphic function from its type; e.g. rev :: [a] -> [a] must satisfy map f (rev xs) = rev (map f xs).
In this talk, I will show how to apply many of the ideas behind parametricity and free theorems in a new setting: formal reasoning about quotient types. Using types-as-binary-relations, we can automatically prove that corresponding propositions about quotient types and their representation types are logically equivalent. This design is implemented as the Transfer package in the Isabelle theorem prover, where it is used to automate many proofs about quotient types.

bio:
Brian Huffman is a recent PhD graduate from the Department of Computer Science at Portland State University, now at Galois after completing a postdoc at the Technical University of Munich. He has been an avid Haskell programmer since 2001, and has contributed to the development of the Isabelle interactive theorem prover since 2005, with an emphasis on tools for verifying lazy functional programs. Several of Brian's formalizations can be found online at the Archive of Formal Proofs.

# vimeo.com/61653951 Uploaded 112 Plays / / 0 Comments Watch in Couch Mode

Galois Tech Talks

Galois Video Plus

This channel contains video from the tech talks presented by galois.com

Galois has been holding weekly technical seminars since 2006 on topics from functional programming, formal methods, compiler and language design, to cryptography, and operating


+ More

This channel contains video from the tech talks presented by galois.com

Galois has been holding weekly technical seminars since 2006 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.

Each week new tech talks are published at galois.com/blog/category/techtalks/ and you can find out about upcoming talks on twitter.com/galoisinc

Browse This Channel

Shout Box

Channels are a simple, beautiful way to showcase and watch videos. Browse more Channels. Channels