Стратегия вычислений - NiNa.Az

Стратегия вычисления (англ. evaluation strategy) — правила семантики языка программирования, определяющие, когда следует вычислять аргументы функции (метода, операции, отношения), и какие значения следует передавать. Например, стратегия «вызов при упоминании и передача по ссылке» (call-by-worth/pass-by-reference) диктует, что аргументы должны быть вычислены перед выполнением тела вызываемой функции, и что ей должны быть предоставлены две возможности в отношении каждого аргумента: чтение текущего значения и его изменение посредством операции присваивания. На эту стратегию похожа ^[англ.] в лямбда-исчислении, но есть отличия.

На практике модель вычисления многих практически используемых языков (Java, C#) сводится к стратегии вызова при упоминании и передачи по ссылке. Некоторые более старые языки, в особенности небезопасные, такие как C++, сочетают несколько разных моделей вызова. Исторически вызов по значению➤ и вызов по имени➤ восходят к Алголу-60, созданному в конце 1950-х годов. Только чистые функциональные языки, такие как Clean и Haskell, систематически используют вызов по необходимости➤.

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

Строгие вычисления

Запрос «Строгие вычисления» перенаправляется сюда. На эту тему нужно создать отдельную статью.

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

В нотации Чёрча энергичные вычисления (eager evaluation) операторов соответствуют строгим вычислениям для функций, и по этой причине строгие вычисления временами называются «энергичными». Большинство существующих языков используют строгие вычисления для функций.

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

Аппликативный порядок вычислений (англ. applicative order; также «вычисления слева направо, изнутри наружу» — leftmost innermost) означает стратегию вычислений, при которой обход снизу вверх по AST вычисляет аргументы слева направо в редуцируемых выражениях.

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

Стандартная демонстрация аппликативного порядка использует три функции:

${\displaystyle square(x)=x\cdot x}$,

${\displaystyle sum\_of\_squares(x,y)=square(x)+square(y)}$,

${\displaystyle f(x)=sum\_of\_squares(x+1,x\cdot 2)}$;

при вычислении значения ${\displaystyle f(5)}$ получается следующий набор подстановок:

${\displaystyle f(5)=sum\_of\_squares(5+1,5\cdot 2)=square(6)+square(10)=((6\cdot 6)+(10\cdot 10))=36+100=136}$.

Вызов по значению

Вызов по значению (англ. call-by-value) является наиболее широко распространённой стратегией вычислений, она применена в самых разных языках — от Си до Scheme. При вызове по значению, выражение-аргумент вычисляется, и полученное значение ^[англ.] с соответствующим формальным параметром функции (обычно посредством копирования этого значения в новую область памяти). При этом, если язык разрешает функциям присваивать значения своим параметрам, то изменения будут касаться лишь этих локальных копий, но видимые в месте вызова функции значения останутся неизменными по возвращении.

При этом вызов по значению — целое семейство отличающихся моделей вызова, в которых аргументы вычисляются до передачи телу функции. Большинство языков (Common Lisp, Eiffel, Java), использующие вызов по значению, вычисляют аргументы функций слева направо, но некоторые вычисляют их справа налево, а некоторые (Scheme, OCaml, Си) не определяют порядок вычисления.

Скрытые ограничения

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

Причина использования вызов по ссылке обычно состоит в том, что язык технически не предоставляет возможности оперировать сложными данными как единым значением — он представляет их как структуру данных, хотя в исходном коде заставляет их выглядеть весьма похоже на значение. Определить точное место проведения грани между полноценным значением и маскирующейся под него структурой данных бывает весьма тяжело. В Си вектор (то есть одномерный массив, частным случаем которого является и символьная строка) представляет собой структуру данных и поэтому рассматривается как ссылка на область памяти; однако структура является значением, даже если её поля являются векторами. В Maple вектор является частным случаем таблицы, и следовательно, структурой данных; однако, список (который строится и индексируется точно таким же образом) является значением. В Tcl значения трактуются двояко: представление в виде значения используется на уровне сценария, а сам язык управляет соответствующей структурой данных по мере необходимости. Изменения, производимые над структурой данных, отражаются на значении, и наоборот.

Объяснение, что язык «передаёт параметры по значению, где значением является ссылка», встречается весьма часто (но его не следует отождествлять с вызовом по ссылке); иначе это называется вызовом по соиспользованию. Из-за этого вызов по значению в языках Java и Visual Basic ведёт себя существенно иначе, нежели вызов по значению в языках Си и Паскаль. В Си или Паскале при передаче массивной структуры данных в функцию вся структура будет скопирована (если только аргумент не является в действительности ссылкой на структуру данных), что потенциально существенно снизит быстродействие; при этом изменения состояния структуры не будут видны в вызывающем контексте. В Java и Visual Basic копируется всегда лишь ссылка на структуру, что выполняется быстро, и изменение структуры будет видно в месте вызова.

Вызов по ссылке

При вызове по ссылке (англ. call-by-reference; или передаче по ссылке — pass-by-reference) функция неявно получает ссылку на переменную, использованную в качестве аргумента, вместо копии её значения.

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

Многие языки поддерживают вызов по ссылке в той или иной форме, но лишь немногие используют его по умолчанию — например Perl. Ряд языков, например, C++, PHP, Visual Basic .NET, C# и REALbasic, по умолчанию используют вызов по значению, но предоставляют специальный синтаксис для вызова по ссылке. C++ дополнительно представляет уникальную стратегию «вызов по ссылке на константу».

Системы типов некоторых языков, использующих вызов по значению и непосредственно не поддерживающих вызов по ссылке, предоставляют возможность явно определять ссылки (объекты, ссылающиеся на другие объекты), в частности, указатели (объекты, представляющие собой адреса других объектов в памяти ЭВМ). Их использование позволяет симулировать вызов по ссылке внутри семантики вызова по значению. Такое решение применяется, например, в языках Си и ML. Оно не является самостоятельной стратегией вычисления — язык по-прежнему вызывает по значению — но иногда его называют «вызовом по адресу» (call-by-address) или «передачей по адресу» (pass-by-address). В небезопасных языках, например в Си или C++, оно может приводить к ошибкам доступа к памяти, таким как разыменование нулевого указателя, соответственно, к затруднению понимания программы и первоначального изучения языка. В ML ссылки безопасны по типам и по доступу к памяти.

Близкий эффект также обеспечивает стратегия вызова по соиспользованию➤, применяемая в таких языках как Java, Python, Ruby.

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

Следующий пример демонстрирует симуляцию вызова по ссылке в языке E:

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

Следующий пример демонстрирует симуляцию вызова по ссылке в языке Си — переменные целого типа и указатели передаются по значению, но так как указатель содержит адрес внешней переменной, её значение изменится:

void Modify( int p, int * q, int * o )  {  // все параметры переданы по значению  p = 27; // изменяется только локальное значение  *q = 27; // изменяется внешняя переменная, на которую указывает q  *o = 27; // изменяется внешняя переменная, на которую указывает o } int main() {  int a = 1;  int b = 1;  int x = 1;  int * c = &x;  Modify( a, &b, c ); // 1-й параметр - значение переменной a  // 2-й параметр - адрес переменной b  // 3-й параметр - значение переменной c, являющееся адресом переменной x  // b и x изменяются  return(0); } 

Вызов по соиспользованию

Вызов по соиспользованию (вызов с разделением ресурсов — англ. call-by-sharing; вызов по объекту — call-by-object; вызов с разделяемым объектом — call-by-object-sharing) подразумевает, что значения в языке основаны на объектах, а не на примитивных типах, то есть «» («упакованы», англ. boxed). При вызове по соиспользованию функция получает копию ссылки на объект. Сам объект не копируется — он оказывается соиспользуемым или разделяемым. Как следствие, присваивание аргументу в теле функции не имеет эффекта в вызывающем её контексте, но присваивание компонентам этого аргумента — имеет.

Вызов по соиспользованию впервые реализован в языке Клу в 1974 году под руководством Барбары Лисков.

Эта стратегия используется в языках Python, ^[англ.], Java (для ссылок на объекты), Ruby, JavaScript, Scheme, Ocaml, AppleScript, и многих других. Однако, терминология в сообществах разных языков различается. Например, в сообществе Python используется термин «вызов по соиспользованию»; в сообществах Java и Visual Basic ту же семантику часто описывают как вызов по значению, где значением является ссылка на объект; в сообществе Ruby говорят, что язык «использует вызов по ссылке» — несмотря на то, что семантика вызова в этих языках идентична.

Для неизменяемых объектов нет разницы между вызовом по соиспользованию и вызовом по значению, за исключением идентичности этих объектов. Применение вызова по соиспользованию является альтернативой применения входных и выходных параметров — изменение параметра здесь не означает присваивание параметру; параметр не перезаписывается, а изменяет состояние, сохраняя свою идентичность.

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

def f(l): l.append(1) m = [] f(m) print m 

— напечатает «[1]», так как аргумент «l» был изменён.

Разницу между изменением и присваиванием демонстрирует следующий пример. Такой код:

def f(l): l += [1] m = [] f(m) print m 

— напечатает «[1]», так как оператор «l += [1]» ведёт себя как «l.extend([1])»; но похожий код:

def f(l): l = l + [1] m = [] f(m) print m 

— напечатает"[]", так как оператор «l = l + [1]» создаёт новую локальную переменную, вместо того, чтобы изменять аргумент.

Наглядно семантику обёрнутых (boxed) значений и вызова по соиспользованию демонстрирует поведение следующей программы:

x = [[]] * 4 x[0].append('a') x[1].append('b') x[2].append('c') print(x) >>[['a', 'b', 'c'], ['a', 'b', 'c'], ['a', 'b', 'c'], ['a', 'b', 'c']] 

Оператор «x = [[]] * 4» создаёт пустой список (назовём его «l»), а затем новый список (^[англ.] «x») из четырёх элементов, каждый из которых является ссылкой на «l», то есть «x = [ l, l, l, l ]». Последующие обращения к разным элементам списка «x» изменяют объект «l». То же происходит и при печати списка «x»: поскольку он состоит из четырёх ссылок на «l», то и состав «l» распечатывается четыре раза.

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

Вызов по копированию — восстановлению (англ. call-by-copy-restore; копируй-на-входе копируй-на-выходе — copy-in copy-out; вызов по значению в результате, call-by-value-result; вызов по значению при возврате — call-by-value-return) — особый случай вызова по ссылке➤, в котором предоставляемая ссылка является уникальной для вызывающего контекста. Этот вариант интересен в контексте многопроцессорных систем и удалённого вызова процедур: если параметром функции является ссылка, которая может быть доступна для другого исполняемого процесса, то её содержимое может быть скопировано в новую ссылку, которая уже будет недоступна; при возвращении из функции изменённое содержимое этой новой ссылки будет скопировано в исходную ссылку («восстановлено»).

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

Если ссылка передаётся неинициализированной, такая стратегия вычисления может называться вызов по результату (англ. call-by-result).

Частичные вычисления

Основная статья: Частичные вычисления

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

Нестрогие вычисления

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

Нестрогое вычисление функций соответствует ленивому вычислению операторов в нотации Чёрча, и поэтому нестрогие вычисления часто называются «ленивыми».

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

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

Нормальным порядком вычислений (англ. normal order; также «вычислениями слева направо, снаружи внутрь», leftmost outermost) называют стратегию вычислений, при которой охватывающее выражение полностью редуцируется, применяя функции до вычисления аргументов.

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

Например, значение ${\displaystyle f(5)}$ для функции ${\displaystyle f}$, используемой в стандартной демонстрации аппликативного порядка➤, при вычислении нормальным порядком даст следующий набор подстановок:

${\displaystyle f(5)=sum\_of\_squares(5+1,5\cdot 2)}$

${\displaystyle =square(5+1)+square(5\cdot 2)}$

${\displaystyle =((5+1)\cdot (5+1))+((5\cdot 2)\cdot (5\cdot 2))}$

${\displaystyle =(6\cdot 6)+(10\cdot 10)=36+100=136}$

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

В стратегии вызова по имени (англ. call-by-name аргументы не вычисляются перед вызовом функции. Вместо этого они подставляются непосредственно в тело функции (используя ^[англ.]), и далее вычисляются по месту требования. Если аргумент не используется в теле функции, он вообще не вычисляется; если он используется несколько раз, он повторно вычисляется при каждом вхождении (трюк Йенсена).

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

Впервые вызов по имени был применён в Алголе-60. .NET-языки могут симулировать вызов по имени, используя делегаты или Expression<T>-параметры. В последнем случае функция получает AST. В языке Eiffel реализованы агенты, представляющие собой операции, выполняемые по требованию.

Вызов по необходимости

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

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

Наиболее распространённой реализацией семантики вызова по необходимости являются ленивые вычисления, хотя встречаются и другие варианты — например оптимистичные вычисления.

Haskell — наиболее известный язык, использующий вызов по необходимости. R также использует своего рода вызов по необходимости. .NET-языки могут симулировать вызов по необходимости, используя тип Lazy<T>.

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

Вызов по макрораскрытию (англ. call-by-macro-expansion) похож на вызов по имени, но использует текстовую подстановку вместо подстановки без захвата. При неосторожном использовании, подстановка макроопределения может привести к захвату переменной и нежелательному поведению программы. ^[англ.] устраняют эту проблему, проверяя и при необходимости подменяя затеняемые переменные, не являющиеся параметрами.

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

Полная β-редукция

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

Вызов по преднамеченности

Основная статья: Преднамеченности и обещания

Вызов по преднамеченности (англ. call by future), или параллельный вызов по имени (parallel call-by-name) — это параллельная стратегия вычисления: значения преднамеченных выражений (future expressions) вычисляются параллельно с течением остальной программы. В местах, где требуется значение преднамеченности, основная программа блокируется до завершения вычисления, если оно ещё не было завершено к этому моменту.

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

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

Оптимистичные вычисления

Оптимистичные вычисления (англ. Optimistic evaluation) — это другой вариант вызова по необходимости, при котором аргумент функции частично вычисляется за некоторый отведённый промежуток времени (который можно настраивать во время исполнения программы), после чего вычисления прерываются и функция применяется с использованием вызова по необходимости. Такой подход снижает временны́е задержки, присущие ленивым вычислениям, обеспечивая те же характеристики продукта.

См. также

• ^[англ.]
• Лямбда-исчисление
• Параметр (программирование)
• ^[англ.]

Примечания

1. Essentials of Programming Languages by Daniel P. Friedman and Mitchell Wand, MIT Press 1989—2006
2. Lambda Calculus  (неопр.). Cs.uiowa.edu. Дата обращения: 29 мая 2014. Архивировано из оригинала 14 декабря 2010 года.
3. applicative order reduction definition of applicative order reduction in the Free Online Encyclopedia  (неопр.). Encyclopedia2.thefreedictionary.com.
4. Harold Abelson and Gerald Jay Sussman with Julie Sussman. 1.1.5 The Substitution Model for Procedure Application // Structure and Interpretation of Computer Programs. — second edition. — Cambridge, Massachusetts, London, England: The MIT Press, 1996.
5. Barbara Liskov, Russ Atkinson, Toby Bloom, Eliot Moss, Craig Schaffert, Craig Scheifler, Alan Snyder. CLU Reference Manual (англ.). Laboratory for Computer Science. Massachusetts Institute of Technology (1979). Дата обращения: 29 мая 2014. Архивировано из оригинала 22 сентября 2006 года.
6. Fredrik Lundh. Call By Object (англ.). effbot.org. Дата обращения: 29 мая 2014. Архивировано из оригинала 23 ноября 2019 года.
7. Iota Language Definition  (неопр.). CS 412/413 Introduction to Compilers. Cornell University (2001). Дата обращения: 29 мая 2014. Архивировано 23 сентября 2015 года.
8. CA1021: Avoid out parameters  (неопр.). Дата обращения: 29 мая 2014. Архивировано 5 октября 2013 года.
9. В отличие от Си, в Python записи «l += x» и «l = l + x» не являются эквивалентными — первое семантически является изменением, а не присваиванием. Более того, «l += x» не является синтаксическим эквивалентом «l.extend(x)» из-за правил разрешения видимости: «l += x» требует, чтобы «l» был в локальной области, тогда как «l.extend(x)» ищет также и в охватывающих.

Ссылки

• Харольд Абельсон, Джеральд Джей Сассман, Джули Сассман — Структура и интерпретация компьютерных программ
• Clem Baker-Finch, David King, Jon Hall, Phil Trinder. An Operational Semantics for Parallel Call-by-Need // Research report. — Faculty of Mathematics & Computing, The Open University, 1999-03-10. — Вып. 1, № 99.
• Robert Ennals, Simon Peyton Jones. Optimistic Evaluation: a fast evaluation strategy for non-strict programs. — ACM Press, 2003. — Вып. International Conference on Functional Programming.
• Bertram Ludäscher. CSE 130 lecture notes (англ.). CSE 130: Programming Languages: Principles & Paradigms (24 января 2001).
• Benjamin C. Pierce. Types and Programming Languages. — MIT Press, 2002. — ISBN 978-0-262-16209-8.
• Peter Sestoft. The essence of computation : complexity, analysis, trnasformation : essays dedicated to Neil D. Jones. — Springer-Verlag, 2002. — С. 420—435 "Demonstrating Lambda Calculus Reduction". — ISBN 3-540-00326-6. Архивная копия от 21 июня 2006 на Wayback Machine