A Crash into FP through ATS: | ||
---|---|---|
Prev |
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] //
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:
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] //
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: