;; These examples follow 
;;   https://hbr.github.io/Lambda-Calculus/lambda2/lambda.html and
;;   https://tgdwyer.github.io/lambdacalculus/

;; Key terms: confluent, strongly normalizing, weakly normalizing, divergent.
;;   See also "operational semantics" and "reduction order" in
;;     https://www.cs.jhu.edu/~jason/465/readings/lambdacalc.html
;;   

;; M := \x.(x x)  diverges:

;;   \x.(x x) \x'.(x' x') -> (\x'.x' x')  (\x'.x' x')  

;; U := \x.\f.f (x x f)  diverges, but slightly more usefully:

;; U U -> \f. f (U U f) 

;; U U g -> g (U U g) -> g (g (U U g))

;; The famous Y combinator:
;;        Y = λf. ( λx . f (x x) ) ( λx. f (x x) )

;;  Y g = g (Y g)

;; Examples of using this style of double self-application
;;   to achieve recursion without any global names/labels/bindings:

;; Factorial:

(funcall 
 ((lambda (h) (funcall h h))  ; top self-application
  (lambda (f)
    (lambda (n)
      (if (zerop n)
          1
          (* n (funcall (funcall f f) (1- n)))))))  ; second self-application
 100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

;; List length:

(funcall 
 ((lambda (h)
    (funcall h h))
  (lambda (f)
    (lambda (l)
      (cond
        ((null l) 0 )
        (t (1+
            (funcall (funcall f f)
                     (cdr l))))))))
 '(a b c d e f))
6

;; The general Y combinator for functions of one argument:

(defun Y1 (f)
  (funcall (lambda (x) (funcall x x))
           (lambda (y)
             (lambda (z)  ; this extra lambda requires additional explanation
               (funcall
                (funcall f (funcall y y)) 
                z)))))
Y1

;; Applied to the factorial:

(funcall 
 (Y1 
  (lambda (f)
    (lambda (n)
      (if (zerop n)
          1
          (* n (funcall f (1- n)))))))
 300)

788657867364790503552363213932185062295135977687173263294742533244359449963403342920304284011984623904177212138919638830257642790242637105061926624952829931113462857270763317237396988943922445621451664240254033291864131227428294853277524242407573903240321257405579568660226031904170324062351700858796178922222789623703897374720000000000000000000000000000000000000000000000000

;; ..and to the list length:

(funcall 
 (Y1 
  (lambda (f)
    (lambda (lst)
      (cond ((null lst) 0)
            (t (1+ (funcall f (cdr lst))))))))
 '(a b c d e))
5

;; Y combinator for functions of multiple arguments, needs a few gimmicks:

(defun Y (f)
  (funcall (lambda (x) (funcall x x))
           (lambda (y)
             (funcall f (lambda (&rest args)
                          (apply (funcall y y) args))))))
Y

(funcall 
 (Y
  (lambda (f)
    (lambda (n acc)
      (if (zerop n)
          acc
          (funcall f (1- n) (* n acc))))))
 5 1)
120

;; Different form, with the extra lambda in a different place:

(defun Y2 (f)
  (funcall (lambda (x) (funcall x x))
           (lambda (y)
             (lambda (&rest args)
               (apply
                (funcall f (funcall y y)) 
                args)))))
Y2


(funcall
 (Y2
  (lambda (f)
    (lambda (n acc)
      (if (zerop n)
          acc
          (funcall f (1- n) (* n acc))))))
 100 1)
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

;; With a bit of cheating:

(defun fac (f)
  (lambda (n)
    (if (zerop n)
        1
        (* n (funcall f (1- n))))))

(mapcar (Y #'fac) '(1 2 3 4 5 6 7 8 9 10))
(1 2 6 24 120 720 5040 40320 362880 3628800)

;; No cheating: 

(mapcar (Y (lambda (f)
	     (lambda (n)
	       (if (zerop n)
		   1
		 (* n (funcall f (1- n)))))))
	'(1 2 3 4 5 6 7 8 9 10))
(1 2 6 24 120 720 5040 40320 362880 3628800)