[Alice-users] Re: CTM Chapter 7

[Andreas Rossberg]

Chris Rathman wrote:
> 
> One example that should have translated was the Declarative version of 
> the Flavius Josephus problem - Section 7.8.3.  I got the class based 
> version to work in Alice, but the declarative version relies on Oz's 
> procedural (as opposed to functional) nature.  The correct solution 
> would involve threading the promise list through the function calls and 
> fulfilling the head of the list as necessary, with a new promise in the 
> tail.  Unfortunately, I couldn't quite lock in on the proper threading 
> of the promise.  Any help on this particular example would be most 
> appreciated.

Here is a solution. It's almost identical to the Oz solution. Instead of 
threading promises like you suggest I just spawn a new thread for each 
recursion of victim.

Cheers,

   - Andreas

-------------8<--------------------

fun pipe(xs, l, h, f) = if l <= h then pipe(f(xs, l), l+1, h, f) else xs

fun josephus(n, k) =
     let
	val last = promise()
	fun victim(nil, i) = nil
	  | victim((x,s)::xr, i) =
	    if s = 1 then (fulfill(last, i); nil)
	    else if x mod k = 0 then (x+1,s-1)::xr
	    else (x+1,s)::(spawn victim(xr, i))
	val zs = promise()
     in
	fulfill(zs, pipe((1,n)::future(zs), 1, n,
			 fn(is, i) => spawn victim(is, i)));
	future last
     end