Chapter 20. Example: A Bit More of Animation

With continuation, we can readily insert break points into the execution of a program so as to support some interactive form of program execution (e.g., animation).

Hanoi Towers is a puzzle that is often chosen to illustrate recursion and exponentiation. Given three poles: Pole 1, Pole 2 and Pole 3, there are 64 disks of distinct sizes stacked on Pole 1 such that no disk is stacked on one of a lesser size, and both Pole 2 and Pole 3 are empty. The player is asked to finish the task of moving all the disks from Pole 1 to Pole 2 (while using Pole 3 as a spare): Only one disk can be moved from one pole to another one at any time and no disk is ever allowed to be stacked on another one of a lesser size during the entire process of disk-moving.

With recursion, it is quite straightforward for one to infer that 264-1 moves are needed in order to accomplish the aforementioned task. For instance, the following code shows how this task can be done:

// extern fun move(src: pole, dst: pole): void // extern fun nmove(n: int, src: pole, dst: pole, tmp: pole): void // (* ****** ****** *) // implement nmove ( n , src, dst, tmp) = if (n > 0) then ( nmove(n-1, src, tmp, dst); move(src, dst); nmove(n-1, tmp, dst, src); ) // end of [if] // end of [nmove] //

Given two poles src and dst, the function move, which is not implemented here, moves the top disk at pole src and stack it on the top of the disks at pole dst. Given a natural number n and three poles src, dst, and tmp, the function nmove moves the top n disks at pole src and stack them on the top of the disks at pole dst while using pole tmp as the spare. Assume that n is greater than 0. In order to move the top n disks from pole src to pole dst, nmove first moves the top n-1 disks from pole src to pole tmp and then calls move to move 1 disk from pole src to pole dist and then move the top n-1 disks from pole tmp to pole dst. Note that nmove eventually makes 2n-1 calls to move for each given natural number n.

Suppose that we want to animate the process of disk-moving incurred by calling nmove. A very natural approach that we can take is to first translate nmove (implemented in the direct-style) into the following k_nmove implemented in the CPS-style:

// typedef cont() = cfun(void) // extern fun k_move(src: pole, dst: pole, k: cont()): void // extern fun k_nmove(n: int, src: pole, dst: pole, tmp: pole, k: cont()): void // (* ****** ****** *) // implement k_nmove ( n , src, dst, tmp , k0 ) = if (n > 0) then ( k_nmove ( n-1, src, tmp, dst , lam() => k_move(src, dst, lam() => k_nmove(n-1, tmp, dst, src, k0))) ) else k0((*void*)) // end of [if] // end of [k_nmove] //

Usually, the function k_move is expected to be implemented in the follow way:

// implement k_move (src, dst, k0) = let val () = move(src, dst) in k0() end // end of [k_move] //

After calling move to create some effects, k_move calls the passed continuation immediately to initiate the work to be continued. For the sake of animation, the function k_move can be implemented as follows:

// implement k_move (src, dst, k0) = let val () = move(src, dst) in save_cont(k0) end // end of [k_move] //

where the function save_cont stores a given continuation somewhere so that it can be fetched and then called at a chosen point in future.

Please see on-line a demo that animates the process of disk-moving involved in solving the puzzle of Hanoi Towers, where the animation is achieved by a controlled way of evaluating the continuation saved by each call to k_move. Also please refer to HanoiTowers.dats for various implementation details.

Please find on-line the entirety of the code used in this chapter. The mentioned URL link(s) can be found as follows: