From Lutz Strassburger:
I’d like to announce a talk by Daniel Seidel (University of Bonn, Germany) on
“Free Theorems in Languages with Real-World Programming Features”
The talk takes place this Thursday 20/09 at 13:30 in the Prefab meeting room.
Abstract: Free theorems, type-based assertions about functions, have become a prominent reasoning tool in functional programming languages. For example, they are employed to validate program transformations. But their correct application requires a lot of care. Restrictions arise due to features present in a real-world programming language, but not in the language free theorems were originally investigated in.
We give a short introduction to the theory of free theorems and consider restrictions that arise due to general recursion and forced strict evaluation, as present in the functional programming language Haskell.
In particular, we consider a counterexample generator that tells if and why restrictions on a certain free theorem arise due to general recursion. If a restriction is necessary, the generator, that relies on a proof search algorithm for intutionistic logic and a refined type system for our language, provides a counterexample to the unrestricted free theorem. Thus, we may on the one hand boost the understanding of restrictions and on the other hand hint to cases where restrictions are superfluous.
Concerning restrictions that arise due to forced strict evaluation, we present a refined type system that allows to localize the impact of forced strict evaluation. Refined typing results in stronger free theorems and therefore raises the value of the theorems.
As formal ground for our investigations, we employ different lambda calculi equipped with a denotational semantics.
