Y-комбинатор в схеме, использующий ленивую оценку? - PullRequest
Новая
       58

Y-комбинатор в схеме, использующий ленивую оценку?

1 голос
/ 04 мая 2019

Кто-нибудь знает, как реализовать Y-комбинатор в Scheme, особенно с ленивой оценкой и дополнительным аргументом? Насколько я понимаю, схема (обещание?) (Задержка) и (сила) обеспечивают ленивую поддержку оценки.

Насколько я понимаю, Y-комбинатор с приложением выглядит следующим образом, однако не будет работать в схеме из-за аппликативной оценки заказа по умолчанию. 

((lambda (f)
   ((lambda (x) (f (x x)))
    (lambda (x) (f (x x)))))
 (lambda (r) (r)))

Это предлагаемое решение (Z-комбинатор), однако оно использует другую лямбда-функцию с аргументами в качестве решения: 

;; 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

Обновление на основе решений

Y-комбинатор выглядит следующим образом: 

;; 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

Ценю ваше руководство!

Ответы [ 2 ]

1 голос
/ 05 мая 2019

Обычный Y комбинатор порядка, здесь вычисляется (ack 3 6) в Lazy Racket: 

#lang lazy

(define Y
  (lambda (f)
    ((lambda (g) (g g))
     (lambda (g) (f (g g))))))

((Y (lambda (ackermann)
      (lambda (m n)
        (cond
        ((= m 0) (+ n 1))
        ((= n 0) (ackermann (- m 1) 1))
        (else (ackermann (- m 1) (ackermann m (- n 1))))))))
 3
 6) ; ==> 509

Схема не является ленивым языком, как Lazy Racket, поэтому Y должен немного отличаться.Теперь он называется комбинатором Z: 

#!r6rs
(import (rnrs base))

(define Z
  (lambda (f)
    ((lambda (g)
       (f (g g)))
     (lambda (g)
       (f (lambda args (apply (g g) args)))))))

((Z (lambda (ackermann)
      (lambda (m n)
        (cond
        ((= m 0) (+ n 1))
        ((= n 0) (ackermann (- m 1) 1))
        (else (ackermann (- m 1) (ackermann m (- n 1))))))))
 3
 6) ; ==> 509

Использование delay и force на самом деле не делает его лучше: 

#!r6rs
(import (rnrs base)
        (rnrs r5rs))

(define DY
  (lambda (f)
    ((lambda (g) (g g))
     (lambda (g) (f (delay (g g)))))))


((DY (lambda (d-ackermann)
      (lambda (m n)
        (cond
          ((= m 0) (+ n 1))
          ((= n 0) ((force d-ackermann) (- m 1) 1))
          (else ((force d-ackermann) (- m 1) ((force d-ackermann) m (- n 1))))))))
 3
 6) ; ==> 509

Обычно Y и Z позволяютмы называем нашу рекурсивную процедуру, но в этой последней мы получаем обещание, которое нам необходимо решить, и, таким образом, мы пропускаем детали реализации, и ее становится все труднее использовать.Обычно при использовании обещаний мы хотим избежать ненужного выполнения, но тогда вызов должен вернуть обещание.

1 голос
/ 04 мая 2019

Да, при строгой оценке самоприменение (x x) вызывает бесконечный цикл. Если вы откладываете это, вы можете использовать y-комбинатор, если вы также «принудительно» принудительно отложите объект на его сайте: 

(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))

Обычный способ сделать вариант y-комбинатора, работающего в строгих условиях, - это расширить само приложение, что является еще одним способом отложить его, но не требует явного применения силы. Вместо этого форсирование выполняется приложением функции.

...