Вызов по необходимости в схеме

ProgramBox

Вызов по необходимости в схеме

Post author:admin
Запись опубликована:21 декабря, 2022
Post category:Вопросы по программированию

#parameters #scheme #parameter-passing #anonymous-recursion #call-by-need

#параметры #схема #передача параметров #анонимный-рекурсия #вызов по необходимости

Вопрос:

У меня есть этот код, который знает, что параметры передаются с помощью вызова по необходимости:

 (define fact-2
  (let ((foo (lambda (n f)
               (if (zero? n)
                   1
                   (f n f)))))
    (lambda (n)
      (let ((res 1))
        (foo n (begin 
                 (set! res (* res n)) 
                 (set! n (- n 1)) 
                 foo)) 
        res))))

Я чувствую, что мне чего-то не хватает, но при вызове по необходимости foo с помощью этого объекта as f он будет вычисляться f один раз, а затем никогда не будет обновляться res и n . Это правильно? Я что-то упускаю?

Спасибо.

1. После первого вызова foo foo вызывает себя в бесконечном цикле. Поскольку foo это просто вызов самого себя, числовой аргумент n никогда не уменьшается, поэтому никогда не достигает нуля для завершения цикла.

2. Ну, основываясь на моем учителе, вы ошибаетесь, он каким-то образом должен продолжать обновлять n в (begin … ) но я не понимаю, почему, поскольку при вызове по необходимости это должно быть сделано один раз

3. Вы можете легко показать это, добавив небольшой вывод. Добавьте строку, подобную (display "Enter foo: n: ")(display n)(newline) первой строке foo . Затем вызовите (fact-2 5) . Вы увидите бесконечный поток выходных данных, где foo вызывается с аргументом 4.

4. @clartaq — вызов по необходимости — это модель ленивой оценки, и Scheme охотно оценивает аргументы в вызовах функций. Вы не можете просто запустить этот код в Scheme REPL, чтобы рассуждать о его поведении в модели call by need .

Ответ №1:

Вы правы. Только при вызове по имени begin выражение будет оцениваться при каждом вызове f (за исключением самого первого раза) — чтобы выяснить, что именно мы вызываем, только если вызов f действительно выполнен.

При вызове по значению begin выражение будет вычисляться только один раз, перед самым первым вызовом foo .

При вызове по необходимости он может оцениваться не более одного раза, когда и если в конце самого первого вызова foo возникает необходимость повторного вызова f .

Давайте посмотрим, как версия вызова по имени может быть смоделирована в обычной схеме вызова по значению:

 (define fact2
  (let ((foo (lambda (n f)
               (if (zero? (n))       ;; (n)   NB
                   1
                   ((f) n f)))))     ;; (f)   NB
    (lambda (n)
      (let ((res 1))
        (foo (lambda () n)           ;; (lambda () ...)    NB
             (lambda ()              ;; (lambda () ...)    NB
               (begin 
                 (set! res (* res n)) 
                 (set! n (- n 1)) 
                 foo))) 
        res))))

Вызов (fact2 5) приводит 120 к Racket.

Для семантики вызова по значению ваш код не нуждается в изменениях (для интерпретации в обычной схеме вызова по значению) и, конечно, будет зацикливаться на (fact-2 5) вызове (и действительно делает это в Racket).

И в соответствии с семантикой вызова по необходимости тело каждого лямбда-выражения (из двух новых лямбда-оболочек) будет оцениваться только при первом вызове, после чего оно сохранит вычисленное значение, а затем вернет его; и для всех последующих вызовов сохраненное значение будет немедленно возвращено,без оценки тела. Таким образом set! , формы будут оцениваться не более одного раза, и код с примером тестового вызова (fact-2 5) снова будет зацикливаться.

1. Не могли бы вы объяснить еще немного? Я вижу только fact-2 вызов foo с аргументами n и foo . И foo только вызовы foo с аргументами n и foo . Нигде не foo уменьшается n . И я не вижу никакой настройки запоминания или другой механики для настройки лени.

2. @clartaq объясните конкретно, что? в моем ответе есть три утверждения. вы спрашиваете о вызове по необходимости? какой именно, конкретно, ваш вопрос, пожалуйста?

3. Да, о «вызове по необходимости» (или любом другом соглашении о передаче параметров). Я просто не понимаю, как любой вызов fact-2 может быть успешным, если нет видимого способа прекратить foo рекурсию. В противном случае я повторю вопрос операционной системы. «Я что-то упускаю?» Спасибо за настойчивость.

4. @clartaq я отредактировал ответ. 🙂 при вызове по значению код операции не нуждается в изменениях и, конечно, будет зацикливаться для (fact-2 5) вызова.

5. @adabsurdum «… и произойдет непрерывный цикл «. да, это все. я имел в виду, что нам пришлось внести некоторые изменения, чтобы представить интерпретацию вызова по имени кода OP, чтобы представить его кодом, который будет выполняться внутри системы вызовов по значению Racket; поэтому нет необходимости в каких-либо изменениях для представления его вызова по значениюинтерпретация, поскольку Racket — это уже то.