Y Combinator in Emacs Lisp

emacs-lisp-y-combinator.el

;; Based on https://rosettacode.org/wiki/Y_combinator#Common_Lisp

;; Y combinator in Emacs Lisp

(require 'cl-lib)

(defun Y (f)
  ((lambda (x) (funcall x x))
   (lambda (y) (funcall f (lambda (&rest args)
                        (apply (funcall y y) args))))))
                        
(defun fac (f)
  (lambda (n)
    (if (zerop n)
        1
      (* n (funcall f (1- n))))))

(defun fib (f)
  (lambda (n)
    (cl-case n
      (0 0)
      (1 1)
      (otherwise (+ (funcall f (- n 1))
		    (funcall f (- n 2)))))))
		    
(funcall (Y 'fac) 10) ; => 3628800
(funcall (Y 'fib) 10) ; => 55

Hey, I think this implementation of Y can be made slightly simpler yet. Here's my take:

(setq lexical-binding t)

(cl-defun Y (proc)
  (lambda (&rest arg)
    (apply proc proc arg)))

Lexical binding needs to be enabled for that to work, otherwise Emacs will complain about the value of proc (dynamic scope can be confusing). Below are two test scenarios: head- and tail-recursive implementations of factorial:

(cl-defun factorial-y-combinator (n)
  (funcall
   (Y (lambda (f n)
	(if (zerop n)
	    1
	  (* n (funcall f f (1- n))))))
   n))

(cl-defun tail-factorial-y-combinator (n)
  (funcall
   (Y (lambda (f n acc)
	(if (zerop n)
	    acc
	  (funcall f f (1- n) (* n acc)))))
   n 1))