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

Стратегия вычисления (англ. 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 вычисляет аргументы слева направо в редуцируемых выражениях.

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

Для рассмотрения примера вычислений аппликативным порядком определим несколько функций:

$square(x)=x\cdot x$

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

$f(x)=sum\_of\_squares(x+1,x\cdot 2)$

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

$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)

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

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

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

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

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

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

Вызов по ссылке (call-by-reference)

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

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

Эта стратегия используется в языках Python, Iota, Java (для ссылок на объекты), Ruby, JavaScript, Scheme, Ocaml, AppleScript, и многих других. Однако, терминология в сообществах разных языков различается. Например, в сообществе Python используется термин «вызов по соиспользованию»; в сообществах Java и Visual Basic ту же семантику часто описывают как «вызов по значению, где „значением“ является ссылка на объект»; в сообществе Ruby говорят, что 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)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вызов по имени (call-by-name)

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

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

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

Вызов по необходимости (call-by-need)

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

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

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

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

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

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

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

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

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

Вызов по преднамеченности (call by future)

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

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

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

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

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

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

См. также

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

Ссылки

• Харольд Абельсон, Джеральд Джей Сассман, Джули Сассман — Структура и интерпретация компьютерных программ
• 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