One benefit that functional programmers gain from this restriction is that all data structures are automatically persistent, meaning that updating a data structure does not destroy the existing version, but rather creates a new version that coexists with all previous versions. Persistence has many applications beyond functional programming, including text editing, revision control, transaction processing, discrete event simulation, and computational geometry.
A longstanding problem in the design of persistent data structures is how to make an amortized data structure persistent. The problem is that the ability to access previous versions of a data structure destroys most amortized bounds. I will show how lazy evaluation can sometimes be used to solve this problem, and describe a novel method for analyzing amortized data structures based on lazy evaluation.
Biography
Chris Okasaki grew up in Southern California, receiving his BS in
Mathematics from Harvey Mudd College in 1989. He quickly fled the oppressive
heat for the three rivers and occasional blizzard of Pittsburgh, where
he received his PhD in Computer Science from Carnegie Mellon University
in December 1996. He is currently a living example of the wonders of the
Internet, living in Pittsburgh but telecommuting to Boston, where he consults
for a small start-up company.