Re: Parallel CPS? (was Re: [Caml-list] stack overflow)

[Mike Lin <mikelin@MIT.EDU>]

>
>>> I've learned this style in Scheme. Yet I feel paralyzed when trying 
>>> to
>>> write in it to build trees. The type declaration may make my point
>>> clearer. --8<--
>>> type  dtree = Dnode of dnode | Dtree of (dnode * int * dtree list)
>>> --8<--
>>> The problems are that unless the next call returns, the tree is not
>>> complete yet and it may have several calls on itself.
>

> What if the continuation is not sequential, but parallel? If the tree 
> is
> uniformly binary branching, I guess it would be easier.

> Thanks for other listers as well. The major problem is what if the
> continuation is not singular (sequential) but parallel?

I'm not exactly sure what you mean by 'parallel' here. The observation 
I'll make is that I'm assuming you're not designing your code to only 
work on SMP or distributed machines, so that there must exist an 
equivalent sequential control structure for it.

I'll describe a problem which I hope is related to yours.

Say we had code structured like:

type  tree =
	  Leaf of int
	| Tree of tree * tree (* left and right branches *)

let build_tree (data:some_type) =
	Tree(build_left_subtree data, build_right_subtree data)

...and we wanted to CPS it. So assume we are given:

build_left_subtree' : some_type -> (Tree->unit) -> unit
build_right_subtree' : some_type -> (Tree->unit) -> unit

So sometimes people get confuzled because they have to issue a 
tail-call to build_left_subtree to be good CPSers, but they still need 
additional information to finish constructing the tree.

The solution is to use an intermediate closure as follows:

let build_tree' (data:some_type) (kont:(Tree->unit)) =
	build_left_subtree data
		(fun (left:tree) ->
			build_right_subtree data
				(fun (right:tree) ->
					kont (left,right)))

Again, I hope I understood your problem correctly.

By the way, if there's anyone reading who understands the workings of 
the compiler better than I do. In the above example, left (the argument 
to the first closure) should get stack-allocated since it is an 
argument. Thereafter, we issue a tail-call with a downward funarg that 
references that argument. On the one hand, you want to blow away the 
activation record and allocate the closure on the heap in order to be a 
constant-stack-space tail call. On the other hand, you want to allocate 
the closure on the stack, since it's a downward funarg and you don't 
want to go digging around for memory in the heap. Which does the 
compiler do? I hope the former, or else there's a big problem with my 
technique...

-Mike


--
Mike Lin
mikelin@mit.edu

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners