My First Type Theory

Who knew? Add eyeballs and rhymes, and type theory becomes cute! An introductory video by Arved Friedemann.

PhD position in Certifying Compilation of Smart Contracts

Wouter Swierstra at Utrecht and my IOHK colleague Manuel Chakravarty are looking for someone to undertake a PhD to build a certifying compiler for our smart contract language, Plutus.

This project aims to develop a certifying compiler for Plutus Tx, a subset of the purely functional language Haskell that is used to implement smart contracts for the Cardano blockchain. The Plutus smart contract framework is being developed by IOHK for Cardano and the present project is a joint effort of IOHK and Utrecht University. The Plutus Tx compiler is based on the GHC Haskell compiler and adds a translation step from GHC Core to a minimal lambda calculus. Programmes in this lambda calculus are executed during transaction validation in a sandboxed execution environment in a manner that is crucial to the security of the blockchain. The aim of this project is to formalise the semantics of the languages involved in a proof assistant such as Coq, to reason about the transformation and optimisation steps that the compiler performs, and finally, to generate a proof object certifying the correctness of the generated code together with that code.

Papers We Love Remote Meetup: John Reynolds, Definitional Interpreters for Higher-Order Languages

I will reprise my June presentation to Papers We Love London at Papers We Love Remote Meetup 2, today at 7pm UK time, with the subject John Reynolds, Definitional Interpreters for Higher-Order Languages. Learn the origins of denotational semantics and continuations. Additional citations here. See you there!

Propositions as Types generalised: The Rosetta Stone

From Physics,Topology, Logic and Computation: A Rosetta Stone by John C. Baez and Mike Stay, courtesy of @CompSciFact, @sigfpe, and @notjfmc.

Papers We Love: John Reynolds, Definitional Interpreters for Higher-Order Programming Languages

I've added online links to the relevant papers (not behind paywalls), copied here.

Papers we love: John Reynolds, Definitional Interpreters for Higher-Order Programming Languages

7 June 2016, Skills Matter, London.
Certain papers change your life. McCarthy's 'Recursive Functions of Symbolic Expressions and their Computation by Machine (Part I)' (1960) changed mine, and so did Landin's 'The Next 700 Programming Languages' (1966). And I remember the moment, halfway through my graduate career, when Guy Steele handed me Reynolds's 'Definitional Interpreters for Higher-Order Programming Languages' (1972).
It is now common to explicate the structure of a programming language by presenting an interpreter for that language. If the language interpreted is the same as the language doing the interpreting, the interpreter is called meta-circular.
Interpreters may be written at differing levels of detail, to explicate different implementation strategies. For instance, the interpreter may be written in a continuation-passing style; or some of the higher-order functions may be represented explicitly using data-structures, via defunctionalisation.
More elaborate interpreters may be derived from simpler versions, thus providing a methodology for discovering an implementation strategy and showing it correct. Each of these techniques has become a mainstay of the study of programming languages, and all of them were introduced in this single paper by Reynolds.

Related material

• John Reynolds, Definitional Interpreters for Higher-Order Programming Languages, 1972.
• John Reynolds, Definitional Interpreters for Higher-Order Programming Languages, 1998.
• John Reynolds, Definitional Interpreters Revisited, 1998.
• John Reynolds, The Discoveries of Continuations, 1993.
• John McCarthy, Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I, 1960.
• John McCarthy, Towards a Mathematical Science of Computation, 1962.
• Peter Landin, The Next 700 Programming Languages, 1966.
• Gordon Plotkin, Call-by-value, Call-by-name, and the Lambda Calculus, 1975.
• Robin Milner, A Theory of Type Polymorphism in Programming, 1978.
• Fermin Reig, ed, Reminiscences of Influential Papers, SIGPLAN Notices, 38(12):9—10, December 2003.

Papers We Love: John Reynolds, Definitional Interpreters for Higher Order Languages

I will be speaking on John Reynolds paper, Definitional Interpreters for Higher Order Languages, at Papers We Love, London, 6:30pm Tuesday 7 June; details here.

A brief bibliography on parametricity

Henry Story asked HoTT Cafe about parametricity, prompting creation of a handy, short bibliography including Hermida, Reddy, and Robinson; Ahmed; Dreyer; Milewski (artist of the elegant diagram above); and Shulman.

Idioms are oblivious, arrows are meticulous, monads are promiscuous

Jeremy Yallop spotted a recent comment on Haskell by Albert Y. C. Lai on a paper we coauthored with Sam Lindley, Idioms are oblivious, arrows are meticulous, monads are promiscuous.  Cheers!

I much recommend this paper. Underrated, underknown, pinpointing, unifying.

Two tributes to Kohei

Two tributes to Kohei Honda, from the session in his honour at ETAPS 2013.

Mustard Watches

Another paper by J.-Y. Girard that I will recommend to my students. Reveals deep insight into the techniques used by theoreticians—the payoff is in the final line.  Via Franck FS and Conor McBride.