отличия аппликативного порядка/вызова по значению и нормального порядка/вызова по имени

Задний план

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

Спутанность сознания

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

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

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

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

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

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

Вопрос

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

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


evaluation operator-precedence programming-languages scheme sicp
person Archimedes520    schedule 23.10.2014    source источник

Ответы (1)


arrow_upward
6
arrow_downward

Аппликативный порядок (без учета порядка оценки, который в схеме не определен) будет эквивалентен 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.

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

В этой же статье говорится о call-by-value

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

И прикладной порядок:

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

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

person Rptx    schedule 23.10.2014