Author: Gerd Isenberg
Date: 01:52:55 08/01/03
Go up one level in this thread
On July 31, 2003 at 18:56:14, Dan Andersson wrote:
Thanks Dan,
quite interesting, about "Continuation Passing Style transformation" i have to
think about a while...
Regards,
Gerd
> Here's a factorial function in FP pseudocode using pattern matching:
> factorial 0 = 1
> factorial x = x * factorial (x - 1)
> Loops are replaced by recursion. To reduce time complexity in programs you can
>use the nifty Continuation Passing Style transformation. Here is a CPS form
>factorial:
> factorial' 0 s = s
> factorial' x s = factorial' (x - 1) (s * x)
> factorial x = factorial' x 1
>
>MvH Dan Andersson
Ok lets try 4!
factorial 4 = 4 * factorial 3
= 4*3 * factorial 2
= 4*3*2 * factorial 1
= 4*3*2*1 * factorial 0
= 4*3*2*1 * 1
CPS form
factorial 4 = factorial' 4 1
= factorial' 3 ( 1 * 4)
= factorial' 2 ( 4 * 3)
= factorial' 1 (12 * 2)
= factorial' 0 (24 * 1)
= 24
hmm...
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.