Subject: Recursion in Lambda Calculus

From: Shlomi Fish <[email-masked]>
Date: Sat, 18 May 2002 21:32:19 +0300 (IDT)

I found this recipe for doing recursion in Lambda Calculus by browsing the
SICP exercises. I am giving the functions here using define, but
converting them to lambdas is quite trivial:

(define (myfactorial n)
    (define (bootstrap fact)
        (fact fact n)
    )
    (define (fact ft k)
        (if (= k 1)
            1
            (* k (ft ft (- k 1)))
        )
    )
    (bootstrap fact)
)

ft is the callback that fact uses to call back to itself. bootstrap is a
function that accepts fact as argument and makes sure ft is fact too in
all the subsequent calls of fact.

Kool or what?

Regards,

	Shlomi Fish

----------------------------------------------------------------------
Shlomi Fish        [email-masked]
Home Page:         http://t2.technion.ac.il/~shlomif/
Home E-mail:       [email-masked]

"Let's suppose you have a table with 2^n cups..."
"Wait a second - is n a natural number?"

---

From: Omer Musaev <[email-masked]>
Date: Sun, 19 May 2002 13:54:23 +0300

> -----Original Message-----
> From: Shlomi Fish [mailto:[email-masked]]
> Sent: Saturday, May 18, 2002 8:32 PM
> To: Hackers-IL
> Subject: [hackers-il] Recursion in Lambda Calculus
> 
> 
> 

I suggest you to pay a bit of attention to following little piece of code:

(define (Y f) ((lambda (p) (f (lambda (x) ((p p) x))))
               (lambda (p) (f (lambda (x) ((p p) x))))))

(define (pf-fact factorial)
  (lambda (n)
    (if (zero? n) 1
        (* n (factorial (sub1 n))))))

(define (my-fact1 n)
  ((Y pf-fact) n)))

Which is generalisation on technique you had shown.

> ------------------------ Yahoo! Groups Sponsor 
> ---------------------~-->
> Take the Yahoo! Groups survey for a chance to win $1,000.
> Your opinion is very important to us!
> http://us.click.yahoo.com/NOFBfD/uAJEAA/Ey.GAA/saFolB/TM
> --------------------------------------------------------------
> -------~->
> 
> To unsubscribe from this group, send an email to:
> [email-masked]
> 
>  
> 
> Your use of Yahoo! Groups is subject to 
> http://docs.yahoo.com/info/terms/ 
> 
>