Y combinator in elisp

Question

We can define a recursive function, factorial as an example, by YCombinator as follows

;;; elisp
;;; This code works. Thanks to
;;; https://www.diegoberrocal.com/blog/2015/10/12/y-combinator-in-emacs-lisp/ 

(setq lexical-binding t)  ;;; lexical == static ??

(defun YCombinator (f)
  (funcall #'(lambda (x) (funcall f
                            #'(lambda (y) (funcall (funcall x x) y))))

           #'(lambda (x) (funcall f
                            #'(lambda (y) (funcall (funcall x x) y))))
  )
)

(setq meta-factorial
      #'(lambda (f) #'(lambda (n) (if (eq n 0) 1 (* n (funcall f (1- n)))))))

(funcall (YCombinator meta-factorial) 4) ;; ===> 24

I have learned what a Y combinator is, and knew how it is defined in a mathematical way.

Y: f -> ( (x -> f(x x)) (x -> f(x x)) )

But I found it hard to implement. In particular, my definition of YCombinator, which seems more closer to the mathematical definition, fails to define factorial.

;; this code fails!

(defun YCombinator (f)
  (funcall #'(lambda (x) (funcall f
                            #'(funcall x x)))

           #'(lambda (x) (funcall f
                            #'(funcall x x)))
  )
)

Questions

1. Why is this the case? Did I miss something?
2. Why do we need to set lexical-binding to t?
3. Is there a lambda-expression to (e)lisp translator?

Answer 1

You say you understand this definition:

Y: f -> ( (x -> f(x x)) (x -> f(x x)) )

You can eta-expand the x xs in that to get this:

Y: f -> ( (x -> f(y -> x x y)) (x -> f(y -> x x y)) )

And you should see that this is the same as the working one. Thus, in a pure math lambda-calculus world, your definition and the working one are the same. This leads to the conclusion that yours didn't work because Lisp doesn't live in a pure math lambda-calculus world. This is indeed the case, and the specific difference is that Lisp is strict, which causes it to evaluate the x xs too early, and thus infinitely recurse without ever getting anywhere. Wrapping them in a mathematically unnecessary lambda works around the strictness. As a final note, had you tried to implement this in a lazy language, you wouldn't need that workaround. For example, here's a transliteration of your code into Lazy Racket, which works fine without it:

#lang lazy
(define (YCombinator f) ((lambda (x) (f (x x))) (lambda (x) (f (x x)))))
(define meta-factorial (lambda (f) (lambda (n) (if (= n 0) 1 (* n (f (- n 1)))))))
((YCombinator meta-factorial) 4)

As for why your code uses lexical binding, the simple answer is that that's how lambda calculus works, and trying to get it to work with dynamic binding would significantly complicate everything for no benefit.