Bored-Again Shell

#lang racket

;; This defines an n-argument version of the Y combinator. A use case is
;; implementing mutually recursive functions. The intended usage is:

;;   ((y* (lambda (f1 f2 ... fn) (lambda <body of f1>))
;;        (lambda (f1 f2 ... fn) (lambda <body of f2>))
;;        ...
;;        (lambda (f1 f2 ... fn) (lambda <body of fn>)))
;;    (lambda (f1 f2 ... fn) <use of f1 to fn>))

;; Implementation:

(define u (lambda (f) (f f)))           ;trusty old Mockingbird
(define y*
  (lambda fs
    (u (lambda (this)
         (lambda (receiver)
           (apply receiver
                  (map (lambda (f)
                         (lambda args
                           (apply ((u this) f) args)))
                       fs)))))))

;; An application: mutually recursive odd?/even? predicates

((y* (lambda (oddp evenp) (lambda (n) (if (zero? n) #f (evenp (sub1 n)))))
     (lambda (oddp evenp) (lambda (n) (if (zero? n) #t (oddp (sub1 n))))))
 (lambda (oddp evenp)
   (list (oddp 5) (oddp 6) (evenp 7) (evenp 8))))

;; produces '(#t #f #f #t)

PRINT THIS POST WORDS: Notes: 6 View comments 3/31/11 — 12:28am Short URL: http://tmblr.co/ZNAuby3xy-sn Filed under: #scheme #lisp #code #lambda

uros posted this