Lift-Reduce

The OCaml library to normalize-by-evaluation MapReduce loop bodies to
uncover the uniformity of their processing and speed up the loops

Joint work with Chung-chieh Shan.


	Step-wise expository development of the library

lifted_once.ml		Lifting single loops ranging over a fixed
			domain of individuals
lifted_nested.ml	Generalizing to nested loops, revealing the
			metacircularity of reify

delimcc_simple.ml	Emulating the polymorphic shift/reset using multiple 
			prompts and unsafe unions.
delimcc_simple.mli	This emulation is used only in the expository code,
			to get the prompts out of the way.


	The complete library
lifted_nested_mp.ml	Parameterizing over the type of the loop domain,
			optimizing reification of deeply nested loops

lifted.ml		A different approach, closer to that of HANSEI.
			It seems to make it easier to add further constraints
			and generalize to loops over subsets.


	Looping over all subsets of the domain

lifted_tuples.ml	Converting a nested loop to a flat loop over individuals;
			Converting the loop over all subsets to a loop
			over individuals. Explaining the conversions.

lifted_full.ml		Extending lifted.ml to loops over subsets; adding
			additional constraints: membership and cardinality.

check.hs		Verifying the results of test examples

Makefile	How to build it all

July 2009.