Personal tools
You are here: Home Events LFCS seminar: Tarmo Uustalu: Dynamic programming and coalgebras with sharing

LFCS seminar: Tarmo Uustalu: Dynamic programming and coalgebras with sharing

— filed under:

What
  • LFCS Seminar
When May 12, 2016
from 04:00 PM to 05:00 PM
Where IF 2.33
Add event to calendar vCal
iCal

Dynamic programming is about recognizing sharing opportunities in recursive call trees of a function. If the pattern of sharing opportunities is known in advance, it can be taken into account so that instead of a tree one builds a dag from the start.

We present a framework for doing so based on coalgebras and comonads, which we demonstrate in action with some classical examples. We use systems of coequations for cooperations to describe sharing opportunity patterns. Further, we use techniques from term rewrite systems, namely Knuth-Bendix completion, to obtain unique normal forms of coterms.

In a Haskell implementation of the framework, we rely on circular programming and zippers implemented generically with derivatives of functors.

This is joint work with Nicolas Wu, University of Bristol.

Document Actions