stringtranslate.com

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

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

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

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

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

Условные связки — « cand » и « cor » для краткости — ... менее невинны, чем могут показаться на первый взгляд. Например, cor не распространяется на cand : сравните

(A канд B) кор С с (A кор С) канд (B кор С) ;

в случае ¬A ∧ C второе выражение требует определения B, первое — нет. Поскольку условные связки таким образом усложняют формальные рассуждения о программах, их лучше избегать.

—  Эдсгер В. Дейкстра [1]

Определение

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

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

Приоритет

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

Следующий простой вычислитель слева направо обеспечивает приоритет ANDнад ORa continue:

функция short-circuit-eval ( операторы , значения ) let  result  := True for each ( op , val ) in ( операторы , значения ): if  op = "AND" && result = False continue  else if  op = "OR" && result = True return  result  else  result  := val  return  result

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

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

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

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

Примеры:

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

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

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

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

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

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

int a = 0 ; если ( a != 0 && myfunc ( b )) { do_something (); }

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

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

Оба варианта проиллюстрированы в следующем фрагменте кода на языке 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 or die ; # Прервать выполнение, если some_condition ложно some_condition и die ; # Прервать выполнение, если some_condition истинно

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

modprobe  -q  some_module && echo "some_module установлен" || echo "some_module не установлен"

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

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

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

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

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

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

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

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

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

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

Смотрите также

Ссылки

  1. ↑ Эдсгер В. Дейкстра «О несколько разочаровывающей переписке», EWD1009-0, 25 мая 1987 г., полный текст
  2. ^ "Язык команд оболочки". pubs.opengroup.org .
  3. ^ Бергстра, Ян А.; Понсе, А.; Штаудт, DJC (2010). «Логика короткого замыкания». arXiv : 1010.3674 [cs.LO].
  4. ^ Стандарт ISO/IEC 9899, ​​разделы 6.2.5, 6.3.1.2, 6.5 и 7.16.
  5. ^ Стандарт ISO/IEC 9899, ​​раздел 6.5.13
  6. ^ Проект стандарта ISO/IEC IS 14882.
  7. ^ "OCaml - язык OCaml".
  8. ^ "operators - Документация по Ruby 3.3". docs.ruby-lang.org . Получено 2024-04-02 .
  9. ^ "std::ops - Rust". doc.rust-lang.org . Получено 12.02.2019 .
  10. ^ ETSI ES 201 873-1 V4.10.1, раздел 7.1.4
  11. ^ "Beckhoff Information System - English". infosys.beckhoff.com . Получено 2021-08-16 .
  12. ^ "Beckhoff Information System - English". infosys.beckhoff.com . Получено 2021-08-16 .
  13. ^ "Что означает || в bash?". stackexchange.com . Получено 09.01.2019 .
  14. ^ "Referential Transparency, Definiteness and Unfoldability" (PDF) . Itu.dk . Получено 24.08.2013 .
  15. ^ Вассерман, Луис (11 июля 2012 г.). «Java: В каких случаях лучше использовать безусловное И (& вместо &&)». Stack Overflow .