Normalisation by Evaluation

538 views · Published 6 September 2016 · 49:54 · Indexed 28 October 2026

Channel: Microsoft Research · 2016 · Science & Technology

Watch on YouTube

Normalisation by Evaluation is a technique to efficiently compute the normal form of, possibly open, lambda terms with respect to beta reduction and rewrite rules. It works by compiling terms into some functional programming language and reading off a term representation from the evaluated program. It has been implemented in the theorem prover Isabelle, and a detailed model has been formally verified. The talk will explain the technique and details of the implementation and verification.

More from this channel