Dustin Getz on 5 Oct 2011 16:41:26 -0700


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: More Zipper Articles


i also stumbled across the below. haven't read it yet, but looks really good.

http://www.cs.tufts.edu/~nr/pubs/zipcfg.pdf
An Applicative Control-Flow Graph
Based on Huet’s Zipper
Norman Ramsey and Jo˜ao Dias

Abstract
We are using ML to build a compiler that does low-level optimization. To support
optimizations in classic imperative style, we built a control-?ow graph using mutable
pointers and other mutable state in the nodes. This decision proved unfortunate:
the mutable ?ow graph was big and complex, and it led to many bugs. We have
replaced it by a smaller, simpler, applicative ?ow graph based on Huet’s (1997)
zipper. The new ?ow graph is a success; this paper presents its design and shows
how it leads to a gratifyingly simple implementation of the data?ow framework
developed by Lerner, Grove, and Chambers (2002).


On Wed, Oct 5, 2011 at 7:18 PM, Lalish-Menagh, Trevor <trev@trevmex.com> wrote:
http://en.wikipedia.org/wiki/Zipper_(data_structure)
http://en.wikipedia.org/wiki/Gap_buffer - This is what the zipper is
based off of.

What Constant time is:
http://en.wikipedia.org/wiki/Time_complexity#Constant_time

Yours,
Trevor
--
Trevor Lalish-Menagh
trev@trevmex.com
484.868.6150 (mobile)
trevmex (AIM)