Does anyone know how to implement the Y-combinator in Scheme, specifically with lazy evaluation and additional argument? It's my understanding that Scheme (promise?) (delay) and (force) provide lazy evaluation support.
It's my understanding the Y-combinator with application is as follows, however will not work in Scheme due to applicative order evaluation by default.
((lambda (f)
((lambda (x) (f (x x)))
(lambda (x) (f (x x)))))
(lambda (r) (r)))
This is a suggested solution (the Z-combinator), however it uses another lambda function with arguments as the solution:
;; Z-combinator
(define Z
(lambda (f)
((lambda (g) (f (g g)))
(lambda (g) (f (lambda args (apply (g g)
args)))))))
;Value: z
((Z (lambda (r)
(lambda (x)
(if (< x 2)
1
(* x (r (- x 1))))))) 5)
;Value: 120
;; end Z-combinator
Update based on solutions
The Y-combinator is as follows:
;; Y-combinator
(define Y
(lambda (f)
((lambda (x) (f (delay (x x))))
(lambda (x) (f (delay (x x)))))))
;Value: y
;; end Y-combinator
;; Non tail recursive
((Y (lambda (r)
(lambda (x)
(if (< x 2)
1
(* x ((force r) (- x 1)))))))
5)
;Value: 120
;; Tail - recursive
((Y (lambda (r)
(lambda (x acc)
(if (< x 2)
acc
((force r) (- x 1) (* x acc))))))
5 1)
;Value: 120
Appreciate your guidance!
Yes, with strict evaluation the self application (x x) causes an infinite loop to occur. If you delay this, you can use the y-combinator as long as you also 'force' that delayed object at its use site:
(define (test)
(((lambda (f)
((lambda (x) (f (delay (x x))))
(lambda (x) (f (delay (x x))))))
(lambda (r)
(lambda (x)
(if (< x 2)
1
(* x ((force r) (- x 1)))))))
5))
The normal way to make a variation of the y-combinator that works in a strict setting is to eta-expand the self application, which is another way to delay it but doesn't require an explicit application of force. Instead the forcing is done by function application.