Различия между аппликативным порядком / вызовом по значению и обычным порядком / вызовом по имени

Question

Фон

Я изучаю сикп по онлайн-курсу и меня смущают его лекционные заметки. В примечаниях к лекции аппликативный порядок, по-видимому, равен cbv, а нормальный порядок - cbn.

неразбериха

Но вики указывает, что, кроме порядков оценки (слева направо, справа налево или одновременно), существует разница между аппликативным порядком и cbv:

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

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

А для нормального порядка и cbv я еще больше запутался согласно вики.

В отличие от этого, стратегия вызова по имени не оценивает внутри тела неприменяемой функции.

Я думаю, означает ли это, что нормальный порядок будет оцениваться внутри тела неприменимой функции. Как это могло произойти?

Вопрос

1. Может ли кто-нибудь дать мне более конкретные определения четырех стратегий?
2. Может ли кто-нибудь показать пример для каждой стратегии, используя любой язык программирования.

Большое спасибо?

Answer 1

Аппликативный порядок (без учета порядка оценки, который в схеме не определен) будет эквивалентен cbv. Все аргументы вызова функции полностью оцениваются перед входом в тело функции. Это пример, приведенный в SICP

(define (try a b)
  (if (= a 0) 1 b))

Если вы определяете функцию и вызываете ее с этими аргументами:

(try 0 (/ 1 0))

При использовании аппликативной оценки заказа (по умолчанию в схеме) это приведет к ошибке. Это оценит(/ 1 0) прежде чем войти в тело. При обычной оценке порядка это вернет 1. Аргументы будут переданы без оценки в тело функции и (/ 1 0) никогда не будет оцениваться, потому что (= a 1) верно, избегая ошибки.

В статье, на которую вы ссылаетесь, они говорят о лямбда-исчислении, когда упоминают оценку Аппликативного и Нормального порядка. В этой статье вики это объясняется более понятно, я думаю. Сокращенный означает применение правил сокращения к выражению. (также в ссылке).

α-преобразование: изменение связанных переменных (альфа);

β-редукция: применение функций к своим аргументам (бета);

Нормальный порядок:

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

Вызов по имени

В обычном порядке, но никакие сокращения не выполняются внутри абстракций. Например, λx.(Λx.x)x находится в нормальной форме в соответствии с этой стратегией, хотя и содержит переопределение (λx.x)x.

Нормальная форма - это эквивалентное выражение, которое не может быть уменьшено в дальнейшем в соответствии с правилами, налагаемыми формой.

В той же статье они говорят о колл-по стоимости

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

И Аппликативный порядок:

Самый левый, самый внутренний переопределение всегда уменьшается первым. Интуитивно это означает, что аргументы функции всегда уменьшаются перед самой функцией.

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