trampolines via SMLofNJ.Cont.isolate

Dave Herman <[email protected]> Thu, 29 Mar 2007 01:07:54 -0400
Newsgroups gmane.comp.lang.sml.smlnj
Message-ID <[email protected]>
If I understand SMLofNJ.Cont.isolate correctly, then I think it should 
be possible to use it to implement a trampoline, without having to 
explicitly save a top-level continuation from a program's main function.

I built a little example to test it out, and I've included the code 
below. But when I view the memory usage in Windows, both the 
tail-recursive and the trampolined versions of this function seem to use 
up a tiny bit more memory (~10 - 20K) every time I call them. (The 
naively recursive version, unsurprisingly, gobbles up around 10MB.) Is 
that to be expected, that an iterative function like this would still 
use up a little bit of space?

I am not totally sure if I understood the documentation for isolate, but 
it sounds like it produces an 'a cont purely from the function argument, 
i.e., it does not capture any of the current continuation; so it should 
exhibit iterative space usage to keep throwing to an isolated 
continuation, right?

Thanks,
Dave

(* VERSION 1: NAIVELY RECURSIVE *)

fun stack () =
     let fun f n = if n = 0 then 0 else 1 + (f(n-1)) in
         f 1000000
     end

(* VERSION 2: TAIL-RECURSIVE *)

fun tail () =
     let fun f n a = if n = 0 then a else f (n-1) (a+1) in
         f 1000000 0
     end

(* VERSION 3: TRAMPOLINED *)

open SMLofNJ.Cont;

fun dummy () = ()

val halt = ref (isolate dummy)

fun start thunk =
(
     (callcc (fn k => ((halt := k); thunk ())));
     !n
)

val n = ref 0

fun loop () =
     if (!n) = 1000000 then
         throw (!halt) ()
     else
     (
         n := (!n) + 1;
         throw (isolate (fn () => loop ())) ()
     )

fun trampoline () = ((n := 0); start loop)


-------------------------------------------------------------------------
Take Surveys. Earn Cash. Influence the Future of IT
Join SourceForge.net's Techsay panel and you'll get the chance to share your
opinions on IT & business topics through brief surveys-and earn cash
http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV