Abstract

The log­ic un­der­ly­ing the Lean programming language and theorem prover does not know re­cur­sive func­tions, yet Lean users can de­fine func­tions re­cur­sive­ly. In this ses­sion we’ll get to look at how Lean trans­lates the user’s spec­i­fi­ca­tion into some­thing that the log­ic un­der­stands, whether by struc­tur­al re­cur­sion, well-found­ed re­cur­sion or the brand-new par­tial fix­point strat­e­gy. We’ll also see how this af­fects com­piled code (name­ly not at all), and the dif­fer­ence be­tween par­tial and un­safe.

This ses­sion will like­ly con­tain high amounts of im­pro­vised live-cod­ing and ben­e­fit great­ly from your ques­tions, sug­ges­tions and dis­cus­sions.

Joachim Breitner @nomeata

Ever since Joachim has found beauty and elegance in Functional Programming, he’s been working with and on functional programming languages, in particular Haskell.

He’s also always been fascinated by Interactive Theorem Proving and his academic persona used Isabelle and Coq for formalize mathematics and verify programs.

These two interests find their natural synthesis in the Lean programming language, and Joachim joined the Lean FRO to work on the Lean compiler itself.

Besides such serious nerdery, you’ll find Joachim dancing Swing and Tango (in particular when traveling to conferences, so talk to him if you want to join), paragliding and unapologetically making bad puns.