Стратегия оценки - Evaluation strategy

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

Чтобы проиллюстрировать, приложение-функция может оценить аргумент перед оценкой тела функции и передать возможность найти текущее значение аргумента и изменить его с помощью назначение.^[1] Понятие стратегия сокращения в лямбда-исчисление похоже, но отличается.

На практике многие современные языки программирования, такие как C # и Java, сошлись на стратегии оценки вызова по значению / вызову по ссылке для вызовов функций.^{[требуется разъяснение ]} Некоторые языки, особенно языки нижнего уровня Такие как C ++, объедините несколько понятий передачи параметров. Исторически сложилось так, что вызов по значению и вызов по имени относятся к АЛГОЛ 60, который был разработан в конце 1950-х годов. Звонок по ссылке используется PL / I и немного Фортран системы.^[2] Чисто функциональные языки вроде Haskell, а также не чисто функциональные языки, такие как р, используйте вызов по необходимости.

Стратегия оценки определяется определением языка программирования и не является функцией какой-либо конкретной реализации.

Строгая оценка

При строгой оценке аргументы функция всегда полностью оцениваются перед применением функции.

Под Церковная кодировка, жадная оценка из операторы соответствует строгой оценке функций; по этой причине строгую оценку иногда называют «нетерпеливой». Большинство существующих языков программирования используют строгое вычисление функций.

Заявочный порядок

Оценка аппликативного порядка - это стратегия оценки, в которой выражение оценивается путем многократного вычисления его крайнего левого угла. сокровенный приводимое выражение. Это означает, что аргументы функции оцениваются до применения функции.^[3]

Звоните по цене

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

Вызов по значению - это не отдельная стратегия оценки, а скорее семейство стратегий оценки, в которых аргумент функции оценивается перед передачей в функцию. Хотя многие языки программирования (например, Common Lisp, Эйфель и Java), которые используют вызов по значению, оценивают аргументы функции слева направо, некоторые оценивают функции и их аргументы справа налево, а другие (например, Scheme, OCaml и C) не указывают порядок.

Неявные ограничения

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

Причина передачи ссылки часто заключается в том, что язык технически не обеспечивает представление значений сложных данных, а вместо этого представляет их как структуру данных, сохраняя при этом некоторое подобие внешнего вида значений в исходном коде. Часто трудно предсказать, где именно проходит граница между правильными значениями и маскирующимися под них структурами данных. В C, массив (из которых строки являются частными случаями) является структура данных но имя массива рассматривается как (имеет как значение) ссылку на первый элемент массива, а структура Имя переменной относится к значению, даже если оно имеет поля, являющиеся векторами. В Клен, вектор - это частный случай таблицы и, следовательно, структуры данных, но список (который отображается и может быть проиндексирован точно так же) является значением. В Tcl, значения являются «двухпортовыми», так что представление значения используется на уровне сценария, а сам язык управляет соответствующей структурой данных, если таковая требуется. Изменения, внесенные через структуру данных, отражаются обратно в представление значения и наоборот.

Описание «вызов по значению, где значение является ссылкой» является общим (но не следует понимать как вызов по ссылке); другой термин позвонить, поделившись. Таким образом, поведение вызова по значению Java или Visual Basic и вызываем по значению C или Паскаль существенно различаются: в C или Pascal вызов функции с большой структурой в качестве аргумента приведет к копированию всей структуры (кроме случаев, когда она на самом деле является ссылкой на структуру), что потенциально может вызвать серьезное снижение производительности и мутации структуры. невидимы для вызывающего абонента. Однако в Java или Visual Basic копируется только ссылка на структуру, что происходит быстро и изменения структуры видны вызывающему.

Звоните по ссылке

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

Обычно это означает, что функция может изменять (т. Е. назначить на ) переменная, используемая в качестве аргумента - то, что будет видно вызывающему. Таким образом, вызов по ссылке может использоваться для обеспечения дополнительного канала связи между вызываемой функцией и вызывающей функцией. Язык вызова по ссылке затрудняет программисту отслеживание эффектов вызова функции и может вносить небольшие ошибки. Простой лакмусовой бумажкой для определения того, поддерживает ли язык семантику вызова по ссылке, является возможность написать традиционный своп (а, б) функции на языке.^[4]

Многие языки поддерживают вызов по ссылке в той или иной форме, но немногие используют ее по умолчанию. FORTRAN II является ранним примером языка вызова по ссылке. Несколько языков, например C ++, PHP, Visual Basic .NET, C # и REALbasic, по умолчанию вызывается по значению, но предлагается специальный синтаксис для параметров вызова по ссылке. C ++ дополнительно предлагает вызов по ссылке на const.

Вызов по ссылке можно смоделировать на языках, которые используют вызов по значению и точно не поддерживают вызов по ссылке, используя Рекомендации (объекты, которые относятся к другим объектам), например указатели (объекты, представляющие адреса памяти других объектов). Такие языки как C, ML и Ржавчина используйте эту технику. Это не отдельная стратегия оценки - язык вызывает по значению, - но иногда ее называют «вызов по адресу» или «передача по адресу». В ML ссылки тип- и безопасный для памяти, похожий на Rust.

Подобный эффект достигается за счет позвонить, поделившись (передача объекта, который затем может быть изменен), используется в таких языках, как Java, Python и Рубин.

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

Ниже приведен пример, демонстрирующий вызов по ссылке в Язык программирования E:

def modify (var p, & q) {p: = 27 # передается по значению: изменяется только локальный параметр q: = 27 # передается по ссылке: изменена используемая в вызове переменная}? var a: = 1 # значение: 1? var b: = 2 # значение: 2? изменить (a, & b)? a # значение: 1? b # значение: 27

Ниже приведен пример вызова по адресу, который имитирует вызов по ссылке в C:

пустота модифицировать(int п, int* q, int* р) {    п = 27; // передается по значению: изменяется только локальный параметр    *q = 27; // передается по значению или ссылке, проверяем сайт вызова, чтобы определить, какой    *р = 27; // передается по значению или ссылке, проверяем сайт вызова, чтобы определить, какой}int главный() {    int а = 1;    int б = 1;    int Икс = 1;    int* c = &Икс;    модифицировать(а, &б, c); // a передается по значению, b передается по ссылке путем создания указателя (вызов по значению),                    // c - указатель, переданный по значению                    // b и x изменены    возвращаться 0;}

Звоните, поделившись

Вызов посредством совместного использования (также известный как "вызов посредством совместного использования объекта" или "вызов посредством совместного использования объекта") - это стратегия оценки, впервые отмеченная Барбара Лисков в 1974 г. для CLU язык.^[5] Он используется такими языками, как Python,^[6] Ява (для объектных ссылок), Рубин, JavaScript, Схема, OCaml, AppleScript, и много других. Однако термин «вызов путем совместного использования» не является общепринятым; терминология в разных источниках противоречива. Например, в сообществе Java говорят, что Java - это вызов по значению.^[7] Вызов путем совместного использования подразумевает, что значения в языке основаны на объектах, а не на примитивные типы, т.е. что все значения "в штучной упаковке ". Поскольку они заключены в коробку, можно сказать, что они передаются по копии ссылки (где примитивы упаковываются перед передачей и распаковываются в вызываемой функции).

Семантика вызова путем совместного использования отличается от вызова по ссылке: «В частности, это не вызов по значению, потому что изменения аргументов, выполняемые вызываемой подпрограммой, будут видны вызывающему. И это не вызов по ссылке, потому что доступ не предоставляется переменные вызывающего, но только для определенных объектов ".^[8] Так, например, если переменная была передана, невозможно смоделировать присвоение этой переменной в области действия вызываемого.^[9] Однако, поскольку функция имеет доступ к тому же объекту, что и вызывающая сторона (копия не создается), изменения этих объектов, если объекты изменчивый, внутри функции видны вызывающему, что может отличаться от вызова по семантике значения. Мутации изменяемого объекта внутри функции видны вызывающему, потому что объект не копируется и не клонируется - он является общим.

Например, в Python списки изменяемы, поэтому:

def ж(список):    список.добавить(1)м = []ж(м)Распечатать(м)

выходы [1] поскольку добавить Метод изменяет объект, для которого он вызывается.

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

Сравните приведенную выше мутацию Python с приведенным ниже кодом, который связывает формальный аргумент с новым объектом:

def ж(список):    список = [1]м = []ж(м)Распечатать(м)

выходы [], потому что заявление список = [1] переназначает новый список переменной, а не месту, на которое она ссылается.

За неизменяемые объекты, нет реальной разницы между вызовом по совместному использованию и вызовом по значению, за исключением случаев, когда идентичность объекта видна на языке. Использование call путем совместного использования с изменяемыми объектами является альтернативой параметры ввода / вывода: параметр не назначается (аргумент не перезаписывается и идентичность объекта не изменяется), но объект (аргумент) изменяется.^[10]

Хотя этот термин широко используется в сообществе Python, идентичная семантика в других языках, таких как Java и Visual Basic, часто описывается как вызов по значению, где подразумевается, что значение является ссылкой на объект.^{[нужна цитата ]}

Вызов по копированию-восстановлению

Вызов путем копирования-восстановления - также известный как «копирование-вход-копирование-выход», «вызов по результату значения», «вызов по возврату значения» (как это обозначено в Фортран community) - это особый случай вызова по ссылке, когда предоставленная ссылка уникальна для вызывающего. Этот вариант привлек внимание в многопроцессорность контексты и Удаленный вызов процедур:^[11] если параметр вызова функции - это ссылка, которая может быть доступна другому потоку выполнения, его содержимое может быть скопировано в новую ссылку, которой нет; когда вызов функции возвращается, обновленное содержимое этой новой ссылки копируется обратно в исходную ссылку («восстанавливается»).

Семантика вызова путем копирования-восстановления также отличается от семантики вызова по ссылке, где два или более аргумента функции псевдоним друг друга (т. е. указывают на одну и ту же переменную в среде вызывающего). При обращении по ссылке, письмо одному повлияет на другое; вызов методом копирования-восстановления позволяет избежать этого, предоставляя функции отдельные копии, но оставляет результат в среде вызывающего неопределенный в зависимости от того, какой из аргументов с псевдонимом копируется первым - будут ли копии создаваться слева направо как при входе, так и при возврате?

Когда ссылка передается вызываемому объекту неинициализированным, эту стратегию оценки можно назвать «вызов по результату».

Частичная оценка

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

Нестрогая оценка

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

Под Церковная кодировка, ленивая оценка операторов отображается в нестрогое вычисление функций; по этой причине нестрогие оценки часто называют «ленивыми». Булевы выражения во многих языках используют форму нестрогого вычисления, называемую оценка короткого замыкания, где оценка возвращается, как только может быть определено, что результатом будет однозначное логическое значение - например, в дизъюнктивном выражении (ИЛИ), где истинный встречается, или в конъюнктивном выражении (И), где ложный встречается и т. д. Условные выражения также обычно используют ленивое вычисление, при котором вычисление возвращается, как только в результате возникает однозначная ветвь.

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

Вычисление в нормальном порядке - это стратегия оценки, при которой выражение оценивается путем многократного вычисления его самого левого края. крайний приводимое выражение. Это означает, что аргументы функции не оцениваются до применения функции.^[12]

Звоните по имени

Вызов по имени - это стратегия оценки, при которой аргументы функции не оцениваются перед вызовом функции - скорее, они подставляются непосредственно в тело функции (используя замена с избеганием захвата ), а затем оставлено для оценки всякий раз, когда они появляются в функции. Если аргумент не используется в теле функции, он никогда не вычисляется; если он используется несколько раз, он пересматривается каждый раз, когда появляется. (Видеть Устройство Дженсена.)

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

Раннее использование было АЛГОЛ 60. Сегодняшний .NET языки может имитировать вызов по имени с помощью делегатов или Выражение параметры. Последнее приводит к абстрактное синтаксическое дерево передается функции. Эйфель предоставляет агентов, которые представляют операцию, которая должна быть оценена при необходимости. Семя7 обеспечивает вызов по имени с параметрами функции. Ява программы могут выполнять аналогичную ленивую оценку, используя лямбда-выражения и java.util.function.Supplier интерфейс.

Звоните по необходимости

Звонок по нужде - это памятный вариант вызова по имени, где, если аргумент функции оценивается, это значение сохраняется для последующего использования. Если аргумент чистый (т.е. без побочных эффектов), это дает те же результаты, что и вызов по имени, экономя затраты на пересчет аргумента.

Haskell - хорошо известный язык, в котором используется оценка по запросу. Поскольку оценка выражений может происходить произвольно далеко в вычислении, Haskell поддерживает только побочные эффекты (например, мутация ) с помощью монады. Это исключает любое неожиданное поведение переменных, значения которых изменяются до их отложенной оценки.

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

Ленивая оценка является наиболее распространенной реализацией семантики вызова по необходимости, но такие варианты, как оптимистическая оценка существовать. .NET языки реализовать вызов по необходимости, используя тип Ленивый .

Вызов по раскрытию макроса

Вызов по макросу подобен вызову по имени, но использует текстовую замену, а не захват, что позволяет избежать замены. Но подстановка макросов может вызвать ошибки, в результате захват переменных, что приводит к нежелательному поведению. Гигиенические макросы избежать этой проблемы, проверив и заменив затененные переменные это не параметры.

Недетерминированные стратегии

Полное β-восстановление

Под "полным β-редукция ", любое приложение функции может быть сокращено (путем подстановки аргумента функции в функцию с помощью подстановки без захвата) в любое время. Это может быть выполнено даже в теле непримененной функции.

Звонок будущим

"Звонок будущим", также известный как "параллельный звонок по имени", одновременный стратегия оценки, в которой ценность будущее выражение вычисляется одновременно с потоком остальной части программы с обещаниями, также известными как фьючерсы. Когда требуется значение обещания, основная программа блокируется до тех пор, пока обещание не получит значение (обещание или одно из обещаний завершает вычисление, если оно еще не было выполнено к тому времени).

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

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

Если реализовано с сопрограмма, как в .NET асинхронный / ожидание при создании future-объекта вызывается сопрограмма (асинхронная функция), которая может уступить место вызывающей стороне и, в свою очередь, возвращаться обратно, когда используется значение, при совместной работе в многозадачном режиме.

Оптимистическая оценка

Оптимистическая оценка - это еще один вариант вызова, когда аргумент функции частично оценивается в течение некоторого времени (которое может быть скорректировано при время выполнения ). По истечении этого времени оценка прерывается, и функция применяется с использованием вызова по необходимости.^[13] Такой подход позволяет избежать некоторых затрат времени выполнения стратегии вызова по необходимости, сохраняя при этом желаемые характеристики завершения.