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

Укороченная оценка , минимальная оценка или оценка Маккарти (по имени Джона Маккарти ) — это семантика некоторых логических операторов в некоторых языках программирования , в которых второй аргумент выполняется или оценивается только в том случае, если первого аргумента недостаточно для определения значения выражение: когда первый аргумент 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:

функция  короткого замыкания-eval (  операторы  ,  значения  ) 
      пусть   результат  := True 
      для каждого  (  op  ,  val  ) в (  операторах  ,  значениях  ): 
          если   op  = "И" &&  результат  = False 
              продолжить 
         еще, если   op  = "ИЛИ" &&  результат  = True 
              вернуть   результат 
         else 
             result  :=  val 
     вернуть   результат

Формализация [ править ]

Логика короткого замыкания, с побочными эффектами или без них, была формализована на основе условного выражения Хоара . В результате операторы без короткого замыкания могут быть определены на основе упрощенной логики, чтобы иметь одинаковую последовательность вычислений. ^[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 :

целое   число   =   0  ; 
  if   (  denom   !=   0   &&   num   /   denom  ) 
 { 
     ...   // гарантирует, что вычисление числа/денома никогда не приведет к ошибке деления на ноль 
 }

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

интервал   а   =   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 вполне возможен с p == NULL 
 } 

 bool   is_first_char_valid_alpha  (  const   char   *  p  ) 
 { 
     return   p   !=   NULL   &&   isalpha  (  p  [  0  ]);    // 1) нет ненужного выполнения isalpha() с p == NULL, 2) нет риска SEGFAULT 
 }

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

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

Идиомы Perl :

какое-то_состояние   или   умри  ;       # Прервать выполнение, если some_condition ложно 
 some_condition   и   умереть  ;      # Прерываем выполнение, если some_condition истинно

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

modprobe   -q   some_module   &&   echo   «некоторый_модуль установлен»   ||    эхо   «некоторый_модуль не установлен»

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

Возможные проблемы [ править ]

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

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

if   (  выражениеA   &&   myfunc  (  b  ))   { 
     do_something  (); 
  }

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

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

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

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

Примером компилятора, который не может оптимизироваться для такого случая, является машина Java виртуальная Hotspot (VM) по состоянию на 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]