Ycombinator3

Ycombinator3.rkt

#lang racket

(define identity (lambda (x) x))

(define (part-factorial0 self n)
  (if (= n 0)
      1
      (* n (self self (- n 1)))))  ;; note the extra "self" here the same as below

(part-factorial0 part-factorial0 5)


;; let remove the n

(define (part-factorial1 self)
  (lambda (n)
    (if (= n 0)
        1
        (* n ((self self) (- n 1))))))

((part-factorial1 part-factorial1) 5) ;; 120


(define (part-factorial2-wrong self)
  (let ((f (self self))) ;; this way halt so we need remove it
    (lambda (n)
      (if (= n 0)
          1
          (* n (f (- n 1)))))))


;;((part-factorial2-wrong part-factorial2) 5) ;; 120

;It turns out that any let expression can be converted into an equivalent
; lambda expression using this equation:
;
;  (let ((x <expr1>)) <expr2>)
;  ==> ((lambda (x) <expr2>) <expr1>)

(define (part-factorial3-wrong self)
  ((lambda (f)
     (lambda (n)
       (if (= n 0)
           1
           (* n (f (- n 1))))))
   (self self))) ;; wrong too

;;((part-factorial3 part-factorial3) 5) ;; 120
;; we need make (self self) not to run directoty
;; make 

(define almost-factorial
    (lambda (f)
      (lambda (n)
        (if (= n 0)
            1
            (* n (f (- n 1)))))))

;; rewrite part-factorial3-wrong
(define (part-factorial self)
    (almost-factorial
      (self self)))

;; ((part-factorial part-factorial) 5) failed

;; let move self into lambda (the almost-factorial)
;; (define factorial-wrong (part-factorial part-factorial))  ;; run forever

;; let make part-factorial more special

;;(define factorial-wrong2
;;    (let ((part-factorial-local (lambda (self) 
;;               (almost-factorial (self self))))) ;; like redefine the part-factorial-local (a repeat define like part-factorial above)
;;      (part-factorial-local part-factorial-local)))  ;; but string rong

;; and we again see let

;  (let ((x <expr1>)) <expr2>)
;  ==> ((lambda (x) <expr2>) <expr1>)
;(define factorial-wrong3
  ;;;                                  expr2                                   expr1
;  ((lambda (part-factorial-local) (part-factorial-local part-factorial-local)) (lambda (self) (almost-factorial (self self))) ))


;; make the name shot to x
;(define factorial-wrong4
  ;;;                                  expr2                                   expr1
;  ((lambda (x) (x x)) (lambda (x) (almost-factorial (x x))) ))

;; short the almoast-factorial to f
(define (make-recursive f)
    ((lambda (x) (x x))
     (lambda (x) (f (x x)))))

;; (define factorial (make-recursive almost-factorial)) still wrong agin
;;

;; remove f and name it y
(define Y0 
    (lambda (f)
      ((lambda (x) (x x))
       
       (lambda (x) (f (x x)))  )))

;Note that we can apply the inner lambda expression to its argument to get an equivalent version of Y: only simple  use

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

;; remove f

(define (Y2 f)
      ((lambda (x) (f (x x))) (lambda (x) (f (x x)))))  

;; now you can see 
;; In Ycombinator2.rkt
;;(define (Y f) (f (Y f)))  it is the same there (we know Y can't work becuase we are eval args at the passing func)

;  (Y f)
;  = ((lambda (x) (f (x x))) (lambda (x) (f (x x))))

;Now apply the first lambda expression to its argument, which is the second lambda expression, to get this:
;  (Y f)
;  = (f ((lambda (x) (f (x x))) (lambda (x) (f (x x)))))
;  = (f (Y f))
;; we see it is the same in In Ycombinator2.rkt Y


;; So we just make part-factorial2 work like Ycombinator2.rkt 's warp it into lambda
;; It is the same Y-Strict in  Ycombinator2.rkt
(define (part-factorial2 self)
    (let ((f (lambda (y) ((self self) y))))
      (lambda (n)
        (if (= n 0)
            1
            (* n (f (- n 1)))))))

((part-factorial2 part-factorial2) 5) ;;  120

;; then we can continue the infer

;  (let ((x <expr1>)) <expr2>)
;  ==> ((lambda (x) <expr2>) <expr1>)

(define (part-factorial3 self)
  ((lambda (f)
     (lambda (n)
       (if (= n 0)
           1
           (* n (f (- n 1))))))
   (lambda (y) ((self self) y)) )) ;; wrong too

((part-factorial3 part-factorial3) 5) ;;  120


;(define factorial-wrong (make-recursive almost-factorial)) ;;still wrong agin

((part-factorial3 part-factorial3) 5) ;;  120

;; use almost-factorial

(define (part-factorial4 self)
  ( almost-factorial (lambda (y) ((self self) y)) )) ;; wrong too

((part-factorial4 part-factorial4) 5)


;; let remove self 
(define part-factorial5 (part-factorial4 part-factorial4))  ;; run forever
(part-factorial5 5)


;; let move part-factorial4 's define  into part-factorial5 to make part-factorial6
(define part-factorial6
    (let ((part-factorial4-local (lambda (self) 
               (almost-factorial  (lambda (y) ((self self) y)) )))) 
      (part-factorial4-local part-factorial4-local)))  ;; but string rong

(part-factorial6 5)


;; make the name shot to x
(define part-factorial7
    (let ((x (lambda (x) 
               (almost-factorial  (lambda (y) ((x x) y)) )))) 
      (x x)))  ;; but string rong

(part-factorial7 5)


;  (let ((x <expr1>)) <expr2>)
;  ==> ((lambda (x) <expr2>) <expr1>)

(define part-factorial8
  ((lambda (x) (x x))
   (lambda (x) (almost-factorial  (lambda (y) ((x x) y)) ))))

(part-factorial8 5)

; short the almoast-factorial to f
(define (make-recursive-lazy f)
 ((lambda (x) (x x))
   (lambda (x) (f  (lambda (t) ((x x) t)) ))))

(define factorial9 (make-recursive-lazy almost-factorial))

(factorial9 5)

;; remove f make it to Y and 
(define Y0-lazy
    (lambda (f)
      ((lambda (x) (x x))
       
       (lambda (x) (f (lambda (t) ((x x) t))))  )))

(define factorial10 (Y0-lazy almost-factorial))
(factorial10 5)


;Note that we can apply the inner lambda expression to its argument to get an equivalent version of Y: only simple  use

(define Y-lazy 
    (lambda (f)
      ((lambda (x) (f (lambda (t) ((x x) t))))
       (lambda (x) (f (lambda (t) ((x x) t)))))  ))

(define factorial11 (Y0-lazy almost-factorial))
(factorial11 5)

; now you can see 
;; In Ycombinator2.rkt
;;(define Y-lambda (lambda (f) (f (Y-lambda f))))  it is the same there (we know Y can't work becuase we are eval args at the passing func)

;; how to prove Y-lazy it is sme like Y-lmabda

;  (Y-lazy f)
;  = ((lambda (x) (f (lambda (t) ((x x) t)))) (lambda (x) (f (lambda (t) ((x x) t)))))

;Now apply the first lambda expression to its argument, which is the second lambda expression, to get this:
;  (Y-lazy f)
;  = (f ((lambda (x) (f (lambda (t) ((x x) t)))) (lambda (x) (f (lambda (t) ((x x) t))))))
;  = (f (Y-lazy f))
;; we see it is the same in In Ycombinator2.rkt Y