#lang racket

; The applicative-order Y combinator
;
; Or how to define a recursive function without giving it a name
; before the definition is complete.
;
; One notion of "definition" is that of an abbreviation.  I.e. a
; a shorthand name for a piece of text.  When used, the name is simply
; expanded into the text it stands for.  Many languages call these
; macros. In general, an abbreviation is not supposed to be
; circular, so that a sequence of substitutions (aka macro expansions)
; always terminates in a constant number of steps.  
;
; If an abbreviation is a term that does not create side effects, then
; abbreviations can be replaced by their values.  For example, a lambda
; term with no free variables can be abbreviated:

(define g  (lambda (x) (+ x 1)))

(g (g 2)) 
; is the same as 
( (lambda (x) (+ x 1)) ((lambda (x) (+ x 1)) 2))

; But a recursive definition is different.  For example
; here is a typical recursive definition of f in terms of itself.  

(define f 
  (lambda (x) 
    (if (> 0 x) x (f (- x 2)))
    )
  )
  
; Simple text substitution is not going to terminate, and furthermore
; we are using f before it is actually defined.  That is, f is a free
; term inside the text that is being used to define f.

; Of course, Scheme is perfectly happy with this:

(f 2)

; and we are now going to explain why.

; Let's change our defintion a bit, so that the identifier f is bound
; inside the defining term:

(lambda (f)
  (lambda (x) 
    (if (> 0 x) x (f (- x 2)))
    )
  )

; so now there are no free variable in the defining term.  
; But this thing we just defined is not f, it is the
; function that builds f when given f!

; (define f-builder
;  (lambda (f)
;    (lambda (x) 
;      (if (> 0 x) x (f (- x 2)))
;      )
;    )
;  )

; The function f is this:  
;    (f-builder f).  
; But we don't have f!  We need to build it.  
; So f is this:
;    (f-builder (f-builder f))
; That is (f-builder (f-builder (f-builder (..... f))))
; Arrg!!!  It doesn't look like we have accomplished anything.

; But in fact we have.  Because now we can defer some of the definition of
; f to run time (evaluation time).  Getting something like this

; (define f
;  (lambda (x) 
;    (if (> 0 x) x ((f-builder ?) (- x 2)))
;    )
;  )

; This new defintion has no free variables (after substituing f-builder)
; except is does have the unknown term ?.  But we only need the value of ?
; when we are in the recursion.  In the base case we never evaluate 
; f-builder.

; In other words, in the construction of f we have two cases driven by the
; input argument:
; The base case can compute the function result directly, without needing
; f and thus does not need to construct f. 
; The recursion needs to construct f prior to recursing, and 
; the recursion might need the builder.
  
; So the builder of f needs to be able to call itself.  
; Since we don't have a defined name for it (that would be cheating), 
; we need to pass it it's own name!
  
; So, now we define a new variant of f-builder, that instead of
; taking f as an argument, takes itself, so that it can build f.  That 
; is (f-builder f-builder) constructs f,
  
; so f-buiilder will look like this:

(lambda (f-builder)
  (lambda (x)
    (if (> 0 x) x ( (f-builder f-builder) (- x 2)) )
    )
  )

; So now we just need to start this process by having the above
; expression call itself.

; But wait, how can you call yourself when you don't have a name?
; This is easily done with this kind of function

  (define call-yourself-with-yourself 
    (lambda (d) (d d)
    ))

; so we get something like this

  ( (lambda (d) (d d))  ; i.e. call yourself with yourself
    
    ; the f-builder that expects itself:
    
    (lambda (f-builder)
      (lambda (x)
        (if (> 0 x) x ( (f-builder f-builder) (- x 2)) )
        )
      )
    )
  
; ok, does this do what we want?

(define f-version-1
  
  ( (lambda (d) (d d))
    
    (lambda (f-builder)
      (lambda (x)
        (if (> 0 x) x 
            ( (f-builder f-builder) (- x 2)) 
        )
      )
    )
))

(f-version-1 -1)
(f-version-1 0)
(f-version-1 2)

; Wow, that actually works without going off the deep end of recursion!
; Why? Note how only in the recursion is f-builder invoked.

; So, now we have a function f-version-1 that is f, but it would be nice if 
; our definition of f actually look like a typical recursive one, rather 
; than the above which constructs f when needed.

; Let us introduce f-def as the term defining f. Then we can write things 
; this way (which is a simple defintion, not recursive):

(define f-def
  (lambda (f) 
    (lambda (x)
      (if (> 0 x) x ( f (- x 2)) )
      )
    )
  )
  
; So we need to pass in the defintion of f, that is, 
;   (f-builder f-builder)
; or (call-yourself-with-yourself f-builder), 
; into f-def so that it can build f


; (define f-version-2
;   ( ; apply the general builder
;    (lambda (function-def)
;      
;      ( (lambda (d) (d d))  ; i.e. call yourself
;        
;        (lambda (function-builder)
;          (begin (print "Invoking function-builder") (newline) )
;          
;          ; this recursion does not terminate when evaluating:  
;          ;    (function-builder function-builder)
;          (function-def (function-builder function-builder) )
;          )
;        )
;      )
;    
;    ; to the defintion of f
;    f-def
;    )
;   )
; 
; (f-version-2 0)
; 


(define f-version-3
  
  ( ; apply the builder 
   (lambda (function-def)
     
     ( (lambda (d) (d d))  ; i.e. call yourself
       
       (lambda (function-builder)
         ; (begin (print "Invoking function-builder") (newline) )
         
         ; delay the evaluation of (function-builder function-builder) until
         ; it is needed.  That is, make it a function, and this is f!
         
         (function-def 
            (lambda (y) ( (function-builder function-builder) y) ) )
         )
       )
     )
   
   ; to the definition
   f-def
   )
  )
   

(map f-version-3 '(0 1 2 3))

; The general builder is completely independent of the definition of f, so we 
; can create the function (combinator) the converts a definition into the 
; actual function

(define Y-comb
  (lambda (function-def)
    
    ( (lambda (d) (d d))  ; i.e. call yourself
      
      (lambda (function-builder)
        
        ; delay the evaluation of (function-builder function-builder) until
        ; it is needed.  That is, make it a function, and this is f!
        
        (function-def 
            (lambda (y) ((function-builder function-builder) y) ) )
        )
      )
    )
  )

(map (Y-comb f-def) '(0 1 2 3))

; Amazing, we can now allow definitions in our restricted subset of Scheme!

( (Y-comb f-def) 3 )

; do not try this at home: (Y-comb Y-comb)