Loading ...
Sorry, an error occurred while loading the content.

RE: [hackers-il] Recursion in Lambda Calculus

Expand Messages
  • Omer Musaev
    ... 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
    Message 1 of 2 , May 19, 2002
    • 0 Attachment
      > -----Original Message-----
      > From: Shlomi Fish [mailto:shlomif@...]
      > Sent: Saturday, May 18, 2002 8:32 PM
      > To: Hackers-IL
      > Subject: [hackers-il] Recursion in Lambda Calculus
      >
      >
      >
      > 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?

      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.

      >
      > Regards,
      >
      > Shlomi Fish
      >
      >
      > ----------------------------------------------------------------------
      > Shlomi Fish shlomif@...
      > Home Page: http://t2.technion.ac.il/~shlomif/
      > Home E-mail: shlomif@...
      >
      > "Let's suppose you have a table with 2^n cups..."
      > "Wait a second - is n a natural number?"
      >
      >
      > ------------------------ 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:
      > hackers-il-unsubscribe@egroups.com
      >
      >
      >
      > Your use of Yahoo! Groups is subject to
      > http://docs.yahoo.com/info/terms/
      >
      >
    Your message has been successfully submitted and would be delivered to recipients shortly.