Programming Languages Lunch - "Functional programming with structured graphs," Bruno C. d. S. Oliveira/The University of Hong Kong

Contact Name: 
John Thywissen
GDC 6.302
Oct 7, 2013 12:00pm - 1:30pm


This talk presents a new functional programming model for graph structures called structured graphs. Structured graphs extend conventional algebraic datatypes with explicit definition and manipulation of cycles and/or sharing, and offer a practical and convenient way to program graphs in functional programming languages like Haskell. The representation of sharing and cycles (edges) employs recursive binders and uses an encoding inspired by parametric higher-order abstract syntax. Unlike traditional approaches based on mutable references or node/edge lists, well-formedness of the graph structure is ensured statically and reasoning can be done with standard functional programming techniques. Since the binding structure is generic, we can define many useful generic combinators for manipulating structured graphs. We give applications and show how to reason about structured graphs.


Bruno C. d. S. Oliveira is an Assistant Professor in the Department of Computer Science at The University of Hong Kong.  His interests are centered around programming languages and methodologies. His existing research is mainly focused on lightweight generic programming techniques and the essence of (OO-style) design patterns. More generally, Dr. Oliveira is interested in the design of programming languages, functional programming, object-oriented programming, design patterns, aspect-oriented programming and concurrency.  He is a member of the IFIP Working Group 2.1 (Algorithmic Languages and Calculi), a steering committee member of the Workshop on Generic Programming and a steering committee member of the Haskell Symposium. He has a DPhil (PhD) from Oxford University.