Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Стратегии оценки

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

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

На практике многие современные языки программирования, такие как C # и Java, сошлись на стратегии оценки вызова по значению / вызову по ссылке для вызовов функций. [ требуется пояснение ] Некоторые языки, особенно языки нижнего уровня, такие как C ++ , сочетают в себе несколько понятий передачи параметров. Исторически вызов по значению и вызов по имени восходят к Алголу 60 , который был разработан в конце 1950-х годов. Вызов по ссылке используется PL / I и некоторыми системами Fortran . [2] Чисто функциональные языки, такие как Haskell , а также не чисто функциональные языки, такие как R , используют вызов по необходимости.

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

Строгая оценка [ править ]

Основная статья: Жажда оценки

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

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

Заявочный порядок [ править ]

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

Вызов по значению [ править ]

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

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

Неявные ограничения [ править ]

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

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

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

Звоните по ссылке [ править ]

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

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

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

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

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

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

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

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

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

void  изменить ( int  p ,  int *  q ,  int *  r )  {  p  =  27 ;  // передается по значению: изменяется только локальный параметр  * q  =  27 ;  // передается по значению или ссылке, проверяем сайт вызова, чтобы определить, какой  * r  =  27 ;  // передается по значению или ссылке, проверяем сайт вызова, чтобы определить, какой }Int  Основной ()  {  INT  = 1 ; int b = 1 ; int x = 1 ; int * c = & x ; изменить ( a , & b , c ); // a передается по значению, b передается по ссылке путем создания указателя (вызов по значению), // c - указатель, переданный по значению // b и x изменяются return 0 ; }

Звоните, поделившись [ редактировать ]

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

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

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

def  f ( a_list ):  a_list . добавить ( 1 )m  =  [] f ( m ) print ( m )

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

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

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

def  f ( a_list ):  a_list  =  [ 1 ]m  =  [] f ( m ) print ( m )

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

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

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

Вызов путем копирования-восстановления [ править ]

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

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

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

Частичная оценка [ править ]

Основная статья: Частичная оценка

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

Нестрогие оценки [ править ]

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

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

Нормальный порядок [ править ]

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

Звоните по имени [ править ]

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

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

Раннее использование было АЛГОЛ 60 . Сегодняшние языки .NET могут имитировать вызов по имени с использованием делегатов или Expression<T>параметров. Последнее приводит к тому, что функции передается абстрактное синтаксическое дерево . Eiffel предоставляет агентов, которые представляют собой операцию, которая может быть оценена при необходимости. Seed7 предоставляет вызов по имени с параметрами функции. Программы на Java могут выполнять аналогичные ленивые вычисления с использованием лямбда-выражений и java.util.function.Supplier<T>интерфейса.

Звоните по необходимости [ редактировать ]

Основная статья: Ленивая оценка

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

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

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

Ленивая оценка - наиболее распространенная реализация семантики вызова по необходимости, но существуют такие варианты, как оптимистическая оценка . Языки .NET реализуют вызов по необходимости, используя тип Lazy<T>.

Вызов с помощью расширения макроса [ править ]

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

Недетерминированные стратегии [ править ]

Полное β-редукция [ править ]

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

Звонок будущим [ править ]

См. Также: Фьючерсы и обещания

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

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

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

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

Оптимистическая оценка [ править ]

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

См. Также [ править ]

  • Бета нормальная форма
  • Сравнение языков программирования
  • оценка
  • Лямбда-исчисление
  • Стоимость вызова по нажатию
  • Параметр (информатика)

Ссылки [ править ]

  1. ^ Дэниел П. Фридман; Митчелл Уэнд (2008). Основы языков программирования (третье изд.). Кембридж, Массачусетс: MIT Press . ISBN 978-0262062794.
  2. ^ Некоторые системы Fortran используют вызов путем копирования-восстановления.
  3. ^ "Аппликативное сокращение порядка" . Энциклопедия2.thefreedictionary.com . Проверено 19 ноября 2019 .
  4. ^ "Java - это передача по значению, черт возьми!" . Проверено 24 декабря 2016 .
  5. ^ Лисков, Барбара; Аткинсон, Расс; Блум, Тоби; Мосс, Элиот; Шафферт, Крейг; Шайфлер, Крейг; Снайдер, Алан (октябрь 1979 г.). «Справочное руководство CLU» (PDF) . Лаборатория компьютерных наук . Массачусетский Институт Технологий. Архивировано из оригинального (PDF) 22 сентября 2006 года . Проверено 19 мая 2011 .
  6. ^ Лунд, Фредрик. «Звонок по объекту» . effbot.org . Проверено 19 мая 2011 .
  7. ^ "Java - это передача по значению, черт возьми!" . Проверено 24 декабря 2016 .
  8. ^ Справочное руководство CLU (1974) , стр. 14-15.
  9. ^ Примечание: на языке CLU «переменная» соответствует «идентификатору» и «указателю» в современном стандартном использовании, а не общему / обычному значению переменной .
  10. ^ «CA1021: Избегайте параметров» . Microsoft.
  11. ^ «RPC: Версия 2 спецификации протокола удаленного вызова процедур» . tools.ietf.org . IETF . Проверено 7 апреля 2018 года .
  12. ^ "Нормальный порядок понижения" . Энциклопедия2.thefreedictionary.com . Проверено 19 ноября 2019 .
  13. ^ Энналс, Роберт; Джонс, Саймон Пейтон (август 2003 г.). «Оптимистическая оценка: стратегия быстрой оценки для нестрогих программ» .


Дальнейшее чтение [ править ]

  • Абельсон, Гарольд ; Суссман, Джеральд Джей (1996). Структура и интерпретация компьютерных программ (второе изд.). Кембридж, Массачусетс: MIT Press. ISBN 978-0-262-01153-2.
  • Бейкер-Финч, Клем; Царь, Давид; Холл, Джон; Триндер, Фил (1999-03-10). «Операционная семантика для параллельного вызова по необходимости» (ps) . Отчет об исследовании . Факультет математики и вычислительной техники, Открытый университет. 99 (1).
  • Энналс, Роберт; Пейтон Джонс, Саймон (2003). Оптимистическая оценка: стратегия быстрой оценки для нестрогих программ (PDF) . Международная конференция по функциональному программированию. ACM Press.
  • Людешер, Бертрам (2001-01-24). «Конспект лекций CSE 130» . CSE 130: Языки программирования: принципы и парадигмы .
  • Пирс, Бенджамин С. (2002). Типы и языки программирования . MIT Press . ISBN 0-262-16209-1.
  • Сестофт, Питер (2002). Могенсен, Т; Шмидт, Д; Садборо, штат Айленд (ред.). Демонстрация сокращения лямбда-исчисления (PDF) . Суть вычисления: сложность, анализ, трансформация. Очерки, посвященные Нилу Д. Джонсу . Конспект лекций по информатике. 2566 . Springer-Verlag. С. 420–435. ISBN 3-540-00326-6.
  • «Вызов по значению и вызов по ссылке в программировании на языке C» . Вызов по значению и вызова по ссылке в C Programming объяснил . Архивировано из оригинала на 2013-01-21.