(self self) вызов внутри оператора let на строгом языке

В настоящее время я прохожу эта статья на Y-комбинаторе от Майк Ванье.
По пути получения Y-комбинатора этот код:

(define (part-factorial self)
  (lambda (n)
    (if (= n 0)

      1
      (* n ((self self) (- n 1))))))

((part-factorial part-factorial) 5) ==> 120
(define factorial (part-factorial part-factorial))
(factorial 5) ==> 120

разработан для:

(define (part-factorial self)
  (let ((f (self self)))
    (lambda (n)
      (if (= n 0)
        1
        (* n (f (- n 1)))))))

(define factorial (part-factorial part-factorial))
(factorial 5) ==> 120

После этого в статье говорится:

This will work fine in a lazy language. In a strict language, the (self self) call in the let statement will send us into an infinite loop, because in order to calculate (part-factorial part-factorial) (in the definition of factorial) you will first have to calculate (part-factorial part-factorial) (in the let expression).

а затем читателю предлагается:

For fun: figure out why this wasn't a problem with the previous definition.

Мне кажется, я понял почему, хотя хочу подтвердить, что:

Я правильно понимаю.
Насколько я понимаю, я не упускаю ни одного критического момента.

Я понимаю: в первом фрагменте кода вызов (self self) не приведет к бесконечному циклу, потому что он содержится (завернут) в lambda как функцию part-factorial и, таким образом, оценивается как lambda (n) до тех пор, пока вызов (self self) не будет фактически выполнен, что происходит только для n > 0. Таким образом, после того, как (= n 0) оценивается как #t, нет необходимости вызывать (self self).

lambda scheme lisp let y-combinator

21.03.2018 12:01

Сортировка hashmap по значениям

На Leetcode я решал задачу с хэшмапой и подумал, что мне нужно отсортировать хэшмапу по значениям.

109

Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Да, это правильный ответ. И действительно, этот трюк (обертывание чего-то, что в противном случае рекурсивно повторялось бы в лямбде) имеет решающее значение при определении Y для языков прикладного порядка, о чем, я думаю, говорится в его статье (кстати, хорошая статья).

21.03.2018 12:38

Ответ принят как подходящий

Да, "let-over-lambda" во втором определении

(define (part-factorial self)
  (let ((f (self self)))        ; let above the
    (lambda (n)                    ; lambda
      (if (= n 0)
        1
        (* n (f (- n 1)))))))

вызывает запуск приложения (self self) перед возвратом (lambda (n) ...).

Это предлагает другой способ избежать зацикливания: поместить само проблемное приложение за свой собственныйlambda:

(define (part-factorial self)
  (let ((f (lambda (a) ((self self) a))))
    (lambda (n)
      (if (= n 0)
        1
        (* n (f (- n 1)))))))

и теперь это тоже работает. Он известен как "эта-экспансия" (или «эта-преобразование» в целом, поскольку его двойственное значение - «эта-сокращение»).

Этот - это то, что на самом деле используется в обычном определении "Y-комбинатора аппликативного порядка".

В первом определении приложение (self self) запускается только тогда, когда его результат действительно необходим - но цена для него состоит в том, что нам пришлось написать его в несколько «неестественном» стиле, который в любом случае отличается от того, что мы хотели бы write, т.е. просто используйте f для ссылки на функцию, которая каким-то образом сделана для нас рекурсивной за кулисами.

При явном самоприложении бремя ложится на нас, а мы, люди, как известно, ошибаемся. В конце концов, человеку свойственно ошибаться, а прощать - Божественно; но наши компьютеры еще не на всепрощающей стадии еще совсем.

Итак, это - это то, почему Y. Чтобы позволить нам написать это прямо, без забот, с детализацией и безопасным абстрагированием.

И груз явного самоприложения больше не упоминается.

мудрость небес

— 03.04.2018 18:40

Вы имеете в виду @naomik святотатство. :)

— 03.04.2018 19:48

@naomik, а если серьезно, Y довольно прост (ну, по крайней мере, понятен), если представлять его постепенно, с правильными мотивационными примерами. Меня действительно бесит, несмотря на все бесчисленные представления об этом как о данности, совершенно непонятной, на ровном месте, без каких-либо объяснений. Почему люди это делают? Или мне просто не повезло? :) / вентиляция

— 03.04.2018 20:22

24.03.2018 21:29