"Type-Driven Program Synthesis" by Nadia Polikarpova

A promising approach to improving software quality is to enhance programming languages with declarative constructs, such as logical specifications or examples of desired behavior, and to use program synthesis technology to translate these constructs into efficiently executable code. In order to produce code that provably satisfies a rich specification, the synthesizer needs an advanced program verification mechanism that is sufficiently expressive and fully automatic. In this talk, I will present a program synthesis technique based on refinement type checking: a verification mechanism that supports automatic reasoning about expressive properties through a combination of types and SMT solving.
The talk will present two applications of type-driven synthesis. The first one is a tool called Synquid, which creates recursive functional programs from scratch given a refinement type as input. Synquid is the first synthesizer powerful enough to automatically discover programs that manipulate complex data structures, such as balanced trees and propositional formulas. The second application is a language called Lifty, which uses type-driven synthesis to repair information flow leaks. In Lifty, the programmer specifies expressive information flow policies by annotating the sources of sensitive data with refinement types, and the compiler automatically inserts access checks necessary to enforce these policies across the code.
Nadia Polikarpova

[@timh.6872]

I'm not so sure the "let there be instagram" future is as inconceivable as she thinks. Sure there's the essential complexity of describing what "instagram" is (and is not), but scaling is just an optimization problem.
For example, the (quite impressive) negation normal form function was a specific case of a structure-preserving transformation between two related Initial Algebras (the recursive types and the measure). Functional programs are an initial algebra, C++ programs are an initial algebra, and machine executable programs are an initial algebra. Statically and dynamically linked libraries are a collection of members of an initial algebra. Compilation and optimization is thus a structure-preserving map between initial algrbras that minimizes resource utilization.
Even scarier for the mathematicians in the room, these algebraic refinement types are an initial algebra. Synthesis itself is something of a structure preserving map between initial algebras.
This is good stuff.

[@mariusraducan1348]

Great talk! On a side note, this is probably the most advanced work on General Artificial Intelligence so far."Type-Driven Program Synthesis" is obviously the right path. Let the people from machine learning do they deep neural network stuff, their will never get it :)

[@alonzoc537]

Yeh I am looking at merging this with Optimal Ordered Problem Solver so you could exploit old solutions and do meta-searches. Looks promising

[@cynocephalusw]

Agree. DNA and RNA work with refinement types. Methylation is a „epigenetic“ refinement.

[@TheSunscratch]

Awesome talk!

[@srghma]

generation is very similar to idris 2

[@samhughes1747]

Geez. Just watched this twice, and I'm gonna be recommending the living frick out of this. Even if it's not directly and broadly applicable, it's still a fantastic pattern.

[@alexanderskladovski]

Is Haskell the pinnacle of creation? 😁😁😁

[@malkdk]

13:07 I don’t understand this. Looks to me like you’re comparing a single element of a list (the head) with an entire list. How is that operation defined? I mean, “v” covers several elements in “t”, so how can we compare “v” to “h”? I guess it would make sense to just compare “h” with the head element of “v”, but I’m not sure if that’s how it’s done.

[@LiamGoodacre]

Ignore `t` here, it is irrelevant in thinking about what `v` is.
The refinement `{ v:a | h

[@henrituhola]

Oh. It's a logic programming language that saves the proof.

[@nirgle]

Great talk!