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