В чем разница между do и do * в Лиспе?

Question

Я работаю над этими двумя функциями, которые отличаются только тем, как ret и curr присваивают свои значения во время выполнения l oop. В первой функции ret и curr связаны параллельно ; во второй функции они привязаны последовательно.

параллельные привязки

(defun maxpower (base maximum)
    "returns base ^ k such that it is <= maximum"
    (do ((ret 1 curr)               ; parallel
         (curr base (* base curr))) ; binding
        ((> curr maximum) ret)))

последовательные привязки

(defun maxpower* (base maximum)
    "returns base ^ k such that it is <= maximum"
    (do* ((ret 1 curr)                ; sequential
          (curr base (* base curr)))  ; binding
         ((> curr maximum) ret)))

Вопрос: является ли 1-я функция неправильной ^(*) , потому что curr обновляется и оценивается одновременно (параллельно)?

IOW: если я изменю порядок привязок, не должно быть разницы в параллельной версии? Как Лисп принимает решение о распараллеливании привязок ?

В моих тестах обе функции возвращают одно и то же значение, как есть.

^{(*) : Я из C фона; Я бы сказал, что первая функция вызывает неопределенное поведение.}

Answer 1

Вероятно, лучше сначала посмотреть на let против let*. Если вы это понимаете, то из этого следует do по сравнению с do*, за исключением дополнительного рассмотрения пошаговых форм.

Common Lisp - это строго оцениваемый язык. И в let, и в let* переменные init-forms вычисляются слева направо. Разница в объеме и привязке. Под let все формы init оцениваются в области, в которой ни одна из переменных не видна, тогда как под let* формы оцениваются в среде, в которой все предыдущие переменные видимый. Во-вторых, поскольку под let* предыдущие переменные видны, их значения также устанавливаются.

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

(let ((x y)
      (y x))
   ...)

Сначала вычисляются инициализирующие выражения y и x в указанном порядке, а затем новые значения x и y привязываются к полученным значениям, что делает это возможным.

С другой стороны:

(let* ((a 1)
       (b (+ a 2)))

Здесь вычисляется 1 и связывается a. Этот a затем становится видимым для выражения (+ a 2), значение которого вычисляется и связывается с b.

Теперь, с do / do*. Эти макросы перед первой итерацией выполняют привязку переменных точно так же, как let / let*. При связывании переменных разница между do и do* точно такая же, как между let и let*.

Макросы do / do* также имеют ступенчатые формы, которые дают следующее значение для соответствующих им итерационных переменных. Все эти пошаговые формы входят в область видимости всех переменных, независимо от того, является ли макрооператор do или do*. Независимо от того, используете ли вы do или do*, вы можете ссылаться на любую переменную в любой пошаговой форме. Разница в том, когда происходит задание. Под do все формы шагов оцениваются сверху вниз, а затем их соответствующим переменным присваиваются новые значения для следующей итерации. Под do* поведение будет «назначать как вы go». При оценке каждой ступенчатой ​​формы присваивается соответствующая переменная. Следовательно, в do, когда ступенчатая форма ссылается на любую переменную, она обращается к ее значению из предыдущей итерации. В do*, если ступенчатая форма ссылается на лексически более раннюю переменную, она получает новое значение. Если он ссылается на лексически более позднюю переменную, он все еще видит старое значение из предыдущей итерации.

Мы должны подчеркнуть, что, хотя let и do имеют некоторое «параллельное» поведение, в некотором смысле, параллельной оценки нет. Все видимые эффекты выполняются слева направо. Кажется, что параллельно происходит то, что переменные возникают или им присваиваются новые значения в новой итерации. Но это только параллель в том смысле, что программа не может наблюдать промежуточный прогресс. Например, передача аргументов функции в функцию также «параллельна»; программа не отслеживает состояние, в котором вызов функции частично выполняется, и передана только половина аргументов.

Answer 2

В случае maxpower неверно, что «curr обновляется и оценивается одновременно ». Все формы шагов в do оцениваются перед выполнением любого назначения. Для do Hyperspe c говорит, что « присвоение значений vars выполняется параллельно, как если бы psetq, а для psetq он говорит, что » сначала оцениваются все формы, и только затем переменные устанавливаются в результирующие значения. "

В опубликованном коде оба определения должны давать одинаковые результаты, потому что ступенчатые формы оцениваются перед любым задания выполнены. Но если бы порядок привязок был изменен на обратный, все было бы иначе:

(defun maxpower (base maximum)
  (do ((curr base (* base curr))
       (ret 1 curr))
      ((> curr maximum) ret)))

(defun maxpower* (base maximum)
  (do* ((curr base (* base curr))
        (ret 1 curr))
       ((> curr maximum) ret)))

Теперь для первой функции (* base curr) и curr оцениваются одновременно, а значения curr и ret обновляются параллельно. Но для второй функции вычисляется (* base curr), и результат присваивается curr, а , затем curr оценивается и присваивается ret.

Для этих новых Вы можете видеть, что результаты различаются, тогда как в исходных определениях обе функции возвращали бы 4 для (maxpower 2 5) и (maxpower* 2 5):

CL-USER> (maxpower 2 5)
4
CL-USER> (maxpower* 2 5)
8