ぱーふぇくとYコンビネータ

slisp/slisp-ycc.el at master · sodeyama/slisp · GitHub

sLispのベータ変換にバグがあり

(defun Y (f)
  ((lambda (x)
     (f (x x)))
   (lambda (x)
     (f (x x)))))

(print ((Y 
         (lambda (f)
           (lambda (n)
             (if (= n 0)
                 1
               (* n (f (- n 1))))))) 8))

みたいなコードをsLispで評価出来なかったんですが、修正しました。
ベータ変換時に、変換するkeyがlambdaとletで束縛されている変数と一致する場合はlambdaやletのS式内部を変換してはいけないんですが、ここを変換してしまっていて無限ループに陥ってました。

この修正で以下のように完全に関数名が消えた階乗の再帰が書けます

(print 
 (((lambda (f)
     ((lambda (x)
        (f (x x)))
      (lambda (x)
        (f (x x)))))
   (lambda (f)
     (lambda (n)
       (if (= n 0)
           1
         (* n (f (- n 1))))))) 8))

なかなか美しいですね。

Yコンビネータと同じ効力を持つZコンビネータも評価出来ます。

(defun Z (y)
  ((lambda (x)
     (lambda (m)
       ((y (x x)) m)))
   (lambda (x)
     (lambda (m)
       ((y (x x)) m)))))
(defun fact0 (f)
  (lambda (n)
    (if (= n 0)
        1
      (* n (f (- n 1))))))
(print ((Z fact0) 8))

elispのfuncallのウザさは異常だよねって人はsLispを改造して使ってみてはいかがか