;;   S combinator is all you need! Provided that you also have a K combinator.

;; Raymond Smullian's book I mentioned:
;;    https://en.wikipedia.org/wiki/To_Mock_a_Mockingbird
;;    https://www.angelfire.com/tx4/cus/combinator/birds.html -- the birds
;;       Look for our friends K, I, KI, M, etc.
;;       More in https://dkeenan.com/Lambda/index.htm 

;;
;;   S is λx. λy. λz. x z (y z)   or "λλλ 3 1 (2 1)" in deBruijn's index notation
;;                                     https://en.wikipedia.org/wiki/De_Bruijn_index
;;---- We can check our combinator calculations with eLisp's lambdas (up to a point) 

(setq K (lambda (x) (lambda (y) x)))
(closure (t) (x) #'(lambda (y) x))

(setq KI (lambda (x) (lambda (y) y)))
(closure (t) (x) #'(lambda (y) y))


(funcall (funcall K 'A) 'B)
A

(funcall (funcall KI 'A) 'B)
B

(setq S (lambda (x)
	  (lambda (y)
	    (lambda (z) (funcall (funcall x z) (funcall y z))))))
(closure (t) (x) #'(lambda (y) #'(lambda (z) (funcall ... ...))))



;;   S K K -> I , so we can make I from S and K

(funcall S K)
(closure ((x closure (t) (x) #'(lambda ... x))) (y) #'(lambda (z) (funcall (funcall x z) (funcall y z))))

(print (funcall S K))

(closure ((x closure (t) (x) #'(lambda (y) x))) (y) #'(lambda (z) (funcall (funcall x z) (funcall y z))))



;; S K K  indeed looks like I:
(funcall (funcall (funcall S K) K) 'x)
x


;; KI K -> I :
;;
;; (λxy.y) (λx'y'.x') -> \y.y == I   (in fact, KI A = I for any A)

;;  S K -> KI :

;;          S             K
;;  (λxyz. x z (y z)) (λx'y'.x') -> λyz. ((λx'y'.x') z) (y z) -> λyz. z  == KI    
;;                                          λy'.z         

;; Alas, more complex combinators as eLisp lambdas run into trouble:
;;
;; (funcall (funcall (funcall S K) 'A) 'B)  --- errors out because of eager applicative evaluation of (y z),
;;                                              "Debugger entered--Lisp error: (void-function A)"
;;  Note: S has actual function applications, unlike K and KI !!

(funcall (funcall S K) 'A)
(closure ((y . A) (x closure (t) (x) #'(lambda ... x))) (z) (funcall (funcall x z) (funcall y z)))

   
(funcall (funcall (funcall S K) 'A) 'B)
;;                 ^^^^^^^^^^^----------- KI 

;; succeeds, but the next level fails 
(closure ((y . A) (x closure (t) (x) #'...) t) (z) (funcall (funcall x z) (funcall y z)))

;; We can assign a function value to A and then it will work:
(setf (symbol-function 'A) (lambda (x) "FOO")) 
(closure (t) (x) "FOO")

(funcall #'A 'x)
"FOO"

(funcall (funcall (funcall S K) 'A) 'B)
B
   ; it works now! at some point (A B) is called and makes "FOO", which gets discarded
B

;; we can also just pass in a lambda function:
(setq AA (lambda (x) "BAR"))
(closure (t) (x) "BAR")

(funcall AA 'x)
"BAR"

;; this works 
(funcall (funcall (funcall S K) (lambda (z) "BAZ")) 'B)
B

;; to see that lambda actually gets called:
(funcall (funcall (funcall S K) (lambda (z) (error "Don't compute me"))) 'B)