Оценка короткого замыкания

Укороченная оценка , минимальная оценка или оценка Маккарти (по имени Джона Маккарти ) — это семантика некоторых логических операторов в некоторых языках программирования , в которых второй аргумент выполняется или оценивается только в том случае, если первого аргумента недостаточно для определения значения выражение: когда первый аргумент AND функция оценивается как false, общее значение должно быть false; и когда первый аргумент OR функция оценивается как true, общее значение должно быть true.

В языках программирования с отложенным вычислением ( Lisp , Perl , Haskell ) обычные логические операторы являются коротким замыканием. В других ( Ada , Java , Delphi ) доступны как сокращенные, так и стандартные логические операторы. Для некоторых логических операций, таких как исключающее или (XOR), невозможно выполнить короткое замыкание, поскольку для определения результата всегда необходимы оба операнда.

Операторы короткого замыкания, по сути, являются управляющими структурами, а не простыми арифметическими операторами, поскольку они не являются строгими . В императивного языка терминах (особенно C и C++ ), где важны побочные эффекты, операторы короткого замыкания вводят точку последовательности : они полностью оценивают первый аргумент, включая любые побочные эффекты , перед (необязательно) обработкой второго аргумента. АЛГОЛ 68 использовал процедуры для создания пользовательских операторов и процедур короткого замыкания.

Использование операторов короткого замыкания подвергалось критике как проблематичное:

Условные связки — « cand » и « cor » для краткости —… менее невинны, чем могут показаться на первый взгляд. Например, cor не распределяет по cand : сравните
(A и B) и C с и (A и C) и (B C );
в случае ¬A ∧ C второе выражение требует определения B, а первое — нет. Поскольку условные связки таким образом усложняют формальные рассуждения о программах, их лучше избегать.
- Эдсгер В. Дейкстра ^{[ 1 ]}

Определение

В любом языке программирования, реализующем сокращенную оценку, выражение x and y эквивалентно условному выражению if x then y else x, и выражение x or y эквивалентно if x then x else y. В любом случае x оценивается только один раз.

Приведенное выше обобщенное определение подходит для свободно типизированных языков, которые имеют более двух значений истинности. True и False, где операторы сокращения могут возвращать последнее вычисленное подвыражение. В таблице ниже это называется «последним значением». Для строго типизированного языка выражение упрощается до if x then y else false и if x then true else y соответственно для логического случая.

Приоритет

Хотя AND имеет приоритет над OR во многих языках это не универсальное свойство сокращенной оценки. Примером того, как два оператора имеют одинаковый приоритет и левоассоциативны друг с другом, является оболочки POSIX . синтаксис списка команд ^{[ 2 ]}^: §2.9.3

Следующий простой оценщик слева направо обеспечивает приоритет AND над OR по continue:

function short-circuit-eval (operators, values)
    let result := True
    for each (op, val) in (operators, values):
        if op = "AND" && result = False
            continue
        else if op = "OR" && result = True
            return result
        else
            result := val
    return result

Формализация

Логика короткого замыкания, с побочными эффектами или без них, была формализована на основе условного выражения Хоара . В результате операторы без короткого замыкания могут быть определены на основе упрощенной логики, чтобы иметь одинаковую последовательность вычислений. ^{[ 3 ]}

Поддержка распространенных языков программирования и сценариев.

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

Примеры:

В JavaScript каждое из следующих трех выражений оценивается как false:
(true & true) === (true && true),
(false | false) === (false || false),
(1 & 2) === (1 && 2).
В PHP каждое из следующих трех выражений имеет значение false:
(true & true) === (true && true),
(0 | 0) === (0 || 0),
(1 & 2) === (1 && 2).

Булевы операторы на разных языках
Язык	Нетерпеливые операторы	Операторы короткого замыкания	Тип результата
Расширенное программирование бизнес-приложений ( ABAP )	никто	`and`, `or`	логическое значение ^{[ а ]}
Есть	`and`, `or`	`and then`, `or else`	логическое значение
АЛГОЛ 68	и, &, ∧ ; или, ∨	andf , orf (оба определяются пользователем)	логическое значение
АПЛ	`∧`, `∨`, `⍲` (нэнд), `⍱` (ни) и т. д.	`:AndIf`, `:OrIf`	логическое значение ^{[ а ]}
авк	никто	`&&`, `\|\|`	логическое значение
Баш	никто	`&&`, `\|\|`	логическое значение
C , Цель-C	`&`, `\|`^{[ б ]}	`&&`, `\|\|`, `?`^{[ 5 ]}	интервал ( `&`, `\|`, `&&`, `\|\|`), opnd-зависимый ( `?`)
С++ ^{[ с ]}	никто	`&&`, `\|\|`, `?`^{[ 6 ]}	Логическое значение ( `&&`, `\|\|`), opnd-зависимый ( `?`)
С#	`&`, `\|`	`&&`, `\|\|`, `?`, `??`	Логическое значение ( `&&`, `\|\|`), opnd-зависимый ( `?`, `??`)
Язык разметки ColdFusion (CFML)	никто	`AND`, `OR`, `&&`, `\|\|`	логическое значение
Д ^{[ д ]}	`&`, `\|`	`&&`, `\|\|`, `?`	Логическое значение ( `&&`, `\|\|`), opnd-зависимый ( `?`)
Эйфелева	`and`, `or`	`and then`, `or else`	логическое значение
Эрланг	`and`, `or`	`andalso`, `orelse`	логическое значение
Фортран ^{[ и ]}	`.and.`, `.or.`	`.and.`, `.or.`	логическое значение
Го , Хаскелл , OCaml	никто	`&&`, `\|\|`	логическое значение
Java , MATLAB , R , Swift	`&`, `\|`	`&&`, `\|\|`	логическое значение
JavaScript	никто	`&&`, `&&=`, `\|\|`, `\|\|=`	Последнее значение
Юлия	никто	`&&`, `\|\|`	Последнее значение
Лассо	никто	`and`, `or`, `&&`, `\|\|`	Последнее значение
Котлин	`and`, `or`	`&&`, `\|\|`	логическое значение
Лисп , Луа , Схема	никто	`and`, `or`	Последнее значение
Свинка (М)	`&`, `!`	никто	Числовой
Модуль-2	никто	`AND`, `OR`	логическое значение
Оберон	никто	`&`, `OR`	логическое значение
OCaml	`land`, `lor`^{[ 7 ]}	`&&`, `\|\|`	логическое значение
Паскаль	`and`, `or`^{[ ж ]}^{[ г ]}	`and_then`, `or_else`^{[ г ]}	логическое значение
Перл	`&`, `\|`	`&&`, `and`, `\|\|`, `or`	Последнее значение
PHP	никто	`&&`, `and`, `\|\|`, `or`	логическое значение
Оболочка POSIX (список команд)	никто	`&&`, `\|\|`	Последнее значение (выход)
PowerShell Язык сценариев	никто	`-and`, `-or`	логическое значение
Питон	`&`, `\|`	`and`, `or`	Последнее значение
Руби	`&`, `\|`	`&&`, `and`, `\|\|`, `or`^{[ 8 ]}	Последнее значение
Ржавчина	`&`, `\|`	`&&`, `\|\|`^{[ 9 ]}	логическое значение
Смолток	`&`, `\|`	`and:`, `or:`^{[ ч ]}	логическое значение
Стандартный ML	Unknown	`andalso`, `orelse`	логическое значение
ТТЦН-3	никто	`and`, `or`^{[ 10 ]}	логическое значение
Beckhoff TwinCAT® ( IEC 61131-3 ) ^{[ я ]}	`AND`, `OR`	`AND_THEN`, ^{[ 11 ]} `OR_ELSE`^{[ 12 ]}	логическое значение
Визуальный Бейсик .NET	`And`, `Or`	`AndAlso`, `OrElse`	логическое значение
Visual Basic , Visual Basic для приложений (VBA)	`And`, `Or`	`Select Case`^{[ Дж ]}	Числовой
Вольфрам Язык	`And @@ {...}`, `Or @@ {...}`	`And`, `Or`, `&&`, `\|\|`	логическое значение
ЗТТ	`&`, `\|`	никто	логическое значение

^ Перейти обратно: ^а ^б ABAP и APL не имеют отдельного логического типа.
^ Побитовые операторы ведут себя как логические операторы, когда оба аргумента имеют тип bool или брать только значения 0 или 1. ^{[ 4 ]}
^ При перегрузке операторы && и || хотят и могут вернуть любой тип.
^ Это применимо только к выражениям, оцениваемым во время выполнения, static if и static assert. Выражения в статических инициализаторах или константах манифеста используют нетерпеливую оценку.
^ Операторы Фортрана не являются ни короткими замыканиями, ни нетерпеливыми: спецификация языка позволяет компилятору выбирать метод оптимизации.
^ ISO/IEC 10206:1990 Extended Pascal допускает, но не требует короткого замыкания.
^ Перейти обратно: ^а ^б Delphi и Free Pascal по умолчанию используют оценку короткого замыкания. Это может быть изменено опциями компилятора , но, похоже, не используется широко.
^ Smalltalk использует семантику короткого замыкания, пока аргумент and: представляет собой блок (например, false and: [Transcript show: 'Wont see me']).
^ Норма IEC 61131-3 фактически не определяет, AND и OR используйте короткую оценку, и она не определяет операторы AND_THEN и OR_ELSE. Записи в таблице показывают, как это работает для Beckhoff TwinCAT®.
^ Языки BASIC , которые поддерживали операторы CASE, делали это с помощью системы условного вычисления, а не с помощью таблиц переходов, ограниченных фиксированными метками.

Общее использование

Как избежать нежелательных побочных эффектов второго аргумента

Обычный пример использования языка на основе C :

int denom = 0;
if (denom != 0 && num / denom)
{
    ... // ensures that calculating num/denom never results in divide-by-zero error   
}

Рассмотрим следующий пример:

int a = 0;
if (a != 0 && myfunc(b))
{
    do_something();
}

В этом примере короткая оценка гарантирует, что myfunc(b) никогда не вызывается. Это потому, что a != 0 оценивается как ложь . Эта функция позволяет реализовать две полезные программные конструкции.

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

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

bool is_first_char_valid_alpha_unsafe(const char *p)
{
    return isalpha(p[0]); // SEGFAULT highly possible with p == NULL
}

bool is_first_char_valid_alpha(const char *p)
{
    return p != NULL && isalpha(p[0]); // 1) no unneeded isalpha() execution with p == NULL, 2) no SEGFAULT risk
}

Идиоматическая условная конструкция

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

Идиомы Perl :

some_condition or die;    # Abort execution if some_condition is false
some_condition and die;   # Abort execution if some_condition is true

оболочки POSIX : Идиомы ^{[ 13 ]}

modprobe -q some_module && echo "some_module installed" || echo "some_module not installed"

Эта идиома предполагает, что echo не может потерпеть неудачу.

Возможные проблемы

Непроверенное второе условие приводит к невыполненному побочному эффекту.

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

if (expressionA && myfunc(b)) {
    do_something();
}

если myfunc(b) предполагается выполнить некоторую необходимую операцию независимо от того, do_something() выполняется, например, выделение системных ресурсов, и expressionA оценивается как ложное, тогда myfunc(b) не будет выполняться, что может вызвать проблемы. Чтобы избежать этой проблемы, в некоторых языках программирования, таких как Java , есть два оператора: один использует минимальные вычисления, а другой нет.

Проблемы с невыполненными операторами побочных эффектов можно легко решить, используя правильный стиль программирования, т. е. не используя побочные эффекты в логических операторах, поскольку использование значений с побочными эффектами в оценках обычно делает код непрозрачным и подверженным ошибкам. ^{[ 14 ]}

Снижение эффективности из-за ограничений оптимизации.

Короткое замыкание может привести к ошибкам в прогнозировании ветвлений на современных центральных процессорах (ЦП) и резко снизить производительность. Ярким примером является высокооптимизированный луч с кодом пересечения прямоугольника, выровненного по оси, в трассировке лучей . ^{[ нужны разъяснения ]} Некоторые компиляторы могут обнаруживать такие случаи и создавать более быстрый код, но семантика языка программирования может ограничивать такую оптимизацию. ^{[ нужна ссылка ]}

Примером компилятора, который не может оптимизироваться для такого случая, является VM ( виртуальная машина Java Hotspot ) по состоянию на 2012 год. ^{[ 15 ]}

См. также

Неважный термин

Ссылки

↑ Эдсгер В. Дейкстра «О несколько разочаровывающей переписке», EWD1009-0, 25 мая 1987 г., полный текст
^ «Язык команд оболочки» . pubs.opengroup.org .
^ Бергстра, Ян А.; Понсе, А.; Штаудт, DJC (2010). «Логика короткого замыкания». arXiv : 1010.3674 [ cs.LO ].
^ Стандарт ISO/IEC 9899, разделы 6.2.5, 6.3.1.2, 6.5 и 7.16.
^ Стандарт ISO/IEC 9899, раздел 6.5.13.
^ Проект ISO/IEC IS 14882.
^ «OCaml — язык OCaml» .
^ "операторы — Документация для Ruby 3.3" . docs.ruby-lang.org . Проверено 2 апреля 2024 г.
^ "std::ops - Rust" . doc.rust-lang.org . Проверено 12 февраля 2019 г.
^ ETSI ES 201 873-1 V4.10.1, раздел 7.1.4
^ «Информационная система Beckhoff — английский» . infosys.beckhoff.com . Проверено 16 августа 2021 г.
^ «Информационная система Beckhoff — английский» . infosys.beckhoff.com . Проверено 16 августа 2021 г.
^ «Что означает || в bash?» . stackexchange.com . Проверено 9 января 2019 г.
^ «Ссылочная прозрачность, определенность и раскрываемость» (PDF) . Itu.dk. Проверено 24 августа 2013 г.
^ Вассерман, Луи (11 июля 2012 г.). «Java: В каких случаях лучше использовать безусловное И (& вместо &&)» . Переполнение стека .

[abap-apl-4] Перейти обратно: ^а ^б ABAP и APL не имеют отдельного логического типа.

[bitwise_c-6] Побитовые операторы ведут себя как логические операторы, когда оба аргумента имеют тип bool или брать только значения 0 или 1. ^{[ 4 ]}

[cpp-8] При перегрузке операторы && и || хотят и могут вернуть любой тип.

[d-10] Это применимо только к выражениям, оцениваемым во время выполнения, static if и static assert. Выражения в статических инициализаторах или константах манифеста используют нетерпеливую оценку.

[fortran-11] Операторы Фортрана не являются ни короткими замыканиями, ни нетерпеливыми: спецификация языка позволяет компилятору выбирать метод оптимизации.

[pascal-1-13] ISO/IEC 10206:1990 Extended Pascal допускает, но не требует короткого замыкания.

[delphi-14] Перейти обратно: ^а ^б Delphi и Free Pascal по умолчанию используют оценку короткого замыкания. Это может быть изменено опциями компилятора , но, похоже, не используется широко.

[smalltalk-17] Smalltalk использует семантику короткого замыкания, пока аргумент and: представляет собой блок (например, false and: [Transcript show: 'Wont see me']).

[twincat-19] Норма IEC 61131-3 фактически не определяет, AND и OR используйте короткую оценку, и она не определяет операторы AND_THEN и OR_ELSE. Записи в таблице показывают, как это работает для Beckhoff TwinCAT®.

[basic-22] Языки BASIC , которые поддерживали операторы CASE, делали это с помощью системы условного вычисления, а не с помощью таблиц переходов, ограниченных фиксированными метками.

[1] Эдсгер В. Дейкстра «О несколько разочаровывающей переписке», EWD1009-0, 25 мая 1987 г., полный текст

[2] «Язык команд оболочки» . pubs.opengroup.org .

[3] Бергстра, Ян А.; Понсе, А.; Штаудт, DJC (2010). «Логика короткого замыкания». arXiv : 1010.3674 [ cs.LO ].

[5] Стандарт ISO/IEC 9899, разделы 6.2.5, 6.3.1.2, 6.5 и 7.16.

[7] Стандарт ISO/IEC 9899, раздел 6.5.13.

[9] Проект ISO/IEC IS 14882.

[12] «OCaml — язык OCaml» .

[15] "операторы — Документация для Ruby 3.3" . docs.ruby-lang.org . Проверено 2 апреля 2024 г.

[16] "std::ops - Rust" . doc.rust-lang.org . Проверено 12 февраля 2019 г.

[18] ETSI ES 201 873-1 V4.10.1, раздел 7.1.4

[20] «Информационная система Beckhoff — английский» . infosys.beckhoff.com . Проверено 16 августа 2021 г.

[21] «Информационная система Beckhoff — английский» . infosys.beckhoff.com . Проверено 16 августа 2021 г.

[23] «Что означает || в bash?» . stackexchange.com . Проверено 9 января 2019 г.

[24] «Ссылочная прозрачность, определенность и раскрываемость» (PDF) . Itu.dk. Проверено 24 августа 2013 г.

[25] Вассерман, Луи (11 июля 2012 г.). «Java: В каких случаях лучше использовать безусловное И (& вместо &&)» . Переполнение стека .

[ 1 ]

[ 2 ]

[ 3 ]

[ а ]

[ б ]

[ 5 ]

[ с ]

[ 6 ]

[ д ]

[ и ]

[ 7 ]

[ ж ]

[ г ]

[ 8 ]

[ 9 ]

[ ч ]

[ 10 ]

[ я ]

[ 11 ]

[ 12 ]

[ Дж ]

[ 4 ]

[ 13 ]

[ 14 ]

[ 15 ]