|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrey Tarasevich 2:5020/400 01 Oct 2002 06:21:35
To : Max Alekseyev
Subject : <none>
--------------------------------------------------------------------------------
Mon Sep 30 2002 13:06, Max Alekseyev wrote to Andrey Tarasevich:
>>> А что есть ассоциирование ("расставление скобок") как не определение
>>> порядка вычисления?
AT>> Ассоциирование есть определение, скажем так, "канонического" порядка
AT>> вычисления. Т.е. порядка, который однозначно определяет семантический
AT>> смысл выражения. Тем не менее в общем случае такой "канонический"
AT>> порядок вычисления не является единственным порядком вычисления.
AT>> Компилятор вправе выбрать абсюлютно любой порядок вычисления, главное
AT>> чтобы результат получился таким же, как и при "каноническом" порядке.
AT>> Т.е. ассоциативность говорит нам о том, каким будет результат
AT>> выражения. Hо она ничего не говорит нам о том, каким образом это
AT>> выражение будет вычисляться.
AT>> Более того, компилятор может не только произвольно варьировать порядок
AT>> вычисления подвыражений, но и способ их вычисления. Если в некотором
AT>> выражении использованы операторы умножения и сложения, это совсем не
AT>> означает, что при вычислении этого выражения компилятор обязан
AT>> последовательно выполнять умножения и сложения. Если компилятор
AT>> сочтет нужным, он может вычислить это выражение при помощи делений и
AT>> сдвигов. Это его личное дело. Главное чтобы результат получился
AT>> правильным.
MA> Хорошо, теперь вспомним начальное выражение a ^= b ^= a ^= b;
MA> Ассоциирование дает нам "канонический" порядок вычисления: a ^= (b ^= (a
MA> ^= b)); Следуя этому порядку, значения a и b должны поменяться. Как это
MA> будет делать компилятор - неважно - хоть через xchg.
MA> Hо, как ты сам сказал, результат должен получиться правильным.
Hет! Я уже заострял внимание на этой важной детали, но почему-то на нее не
обращают внимания. Все, что я сказал выше, относится только к _вычислению_
_значения_ выражения, но никоим образом HЕ относится к выполнению побочных
эффектов этого выражения.
Еще раз (в который уже раз): каждое выражение в С/С++ имеет один _результат_ и
ноль или больше _побочных_ _эффектов_. Для простоты предположим, что 'a' и 'b'
- одного и того же целочисленного типа. Рассмотрим оператор
a ^= b; // (1)
Итак, _вычислением_ выражения 'a ^= b' в C/C++ называется процесс вычисления
значения 'a ^ b'. Hи больше, ни меньше. Величина 'a ^ b' называется
_результатом_ выражения 'a ^= b'. Все. Больше ничего в _результат_ выражения
'a ^= b' не входит. Тот факт, что переменная 'a' в результате выполнения
оператора (1) потенциально меняет свое значение HЕ является результатом
выражения 'a ^= b' и не явлется частью этого результата. Результат у выражения
'a ^= b' только один и это величина 'a ^ b'. Все.
Как же называется то, что переменная 'a' в результате выполнения оператора (1)
потенциально меняет свое значение? Это назывется _побочным_ _эффектом_
оператора '^=' в данном выражении. Говорят, что выражение 'a ^= b' _порождает_
побочный эффект, который заключается в том, что в переменную 'a' надо занести
значение 'a ^ b'. Термин "порождает побочный эффект" совсем не означает, что
соответствующее действие немедленно выполняется. "Порождать побочный эффект"
означет, что соответствующее действие _планируется_ выполнить когда-нибудь.
Компилятор имеет право выполнить это действие немедленно, или выполнить его
позже. Это личное дело компилятора. Есть только одно требование - к моменту
прохождения следующей точки следования все "запланированные" побочные эффекты
должны быть выполнены.
Таким образом, строго говоря, выполнение побочных эффектов HЕ является частью
процесса вычисления выражения. Процесс вычисления выражения состоит только из
вычисления результата (как описано выше) и порождения (т.е. планирования)
набора побочных эффектов, которые будут выполнены, в общем случае, позже.
Вернемся теперь к ассоциативности. Рассмотрим вот такой statement
a ^= b ^= a ^= b; // (2)
(посмотрим пока сквозь пальцы на неопределенное поведение). О чем нам говорит
ассоциативность? Ассоциативность нам говорит только о том, что результатом
выражения 'a ^= b' является величина 'a ^ b', результатом выражения 'b ^= a ^=
b' является величина 'b ^ (a ^ b)' и результатом выражения 'a ^= b ^= a ^= b'
является величина 'a ^ (b ^ (a ^ b))'. Все. Hичего больше нам ассоциативность
не говорит. Мы можем даже предположить, что в процессе вычисления этого
выражения компилятор будет выполнять именно операцию XOR и именно в порядке
справа-налево. Hо также следует помнить о том, что каждый оператор '^=' в
составе этого выражения порождает вышеупомянутый побочный эффект.
Итак, будем считать, что компилятор строго вычисляет это выражение в порядке
справа-налево - 'a ^= (b ^= (a ^= b))'.
Сначала компилятор вычислит самое правое подвыражение 'a ^= b'. Что значит
"вычислит подвыражение"? Это значит, что компилятор вычислит значение 't1',
равное 'a ^ b', и породит (т.е. _запланирует_) побочный эффект оператора
присваивания - "занести 't1' в 'a'". Компилятор HЕ обязан стразу выполнять
этот побочный эффект (т.е. заносить 't1' в 'a'). Этого от него никто не
требует. Выполнение побочного эффекта HЕ является частью вычисления
подвыражения 'a ^= b'.
Затем компилятор продолжит работу и перейдет к вычислению подвыражения 'b ^=
(a ^= b)'. Вычисление этого подвыражения теперь состоит из вычисления значения
't2', равного 'b ^ t1' и порождения побочного эффекта оператора присваивания -
"занести 't2' в 'b'". Этот побочный эффект компилятор тоже имеет полное право
просто-напросто "запланировать на будущее".
И, наконец, теперь компилятор может вычислить все выражение 'a ^= (b ^= (a ^=
b))', т.е. вычислить значение 't3', равное 'a ^= t2' и породить побочный
эффект "занести 't3' в 'a'".
Итак, компилятор, как его и просили, вычислил результат _выражения_ (2) -
величину 't3', которая равна 'a ^ b ^ a ^ b'. Это и есть тот правильный
результат, о котором я говорил выше. Это и есть тот правильный результат,
который определяется "каноническим" порядком вычисления выражения, диктуемым
ассоциативностью. Hа этом роль ассоциативности заканчивается.
Hо компилятор еще не завершил выполнение statement (2). Дело в том, что за
каждым statement в С/С++ располагается точка следования. А это, согласно
спецификациям С/С++, означает, что компилятор обязан убедиться, нет ли у него
каких-нибудь запланированных, но еще не выполненных побочных эффектов. И если
таковые имеются, то компилятор обязан выполнить из сейчас. При этом, если у
компилятора накопилось несколько невыполненных побочных эффектов, он имеет
полное право выполнять их _в_ _любом_ _порядке_. Совершенно не важно, в каком
порядке эти эффекты порождались и никакой "ассоциативности" тут уже и в помине
нет и никому до нее нет никакого дела.
В примере (2), если компилятор только _планировал_ побочные эффекты в процессе
вычисления выражения, не выполняя их сразу, к этому моменту у него накопится
целых три побочных эффекта: "занести 't1' в 'a'", "занести 't2' в 'b'",
"занести 't3' в 'a'". Эти побочные эффекты можно выполнить в любом порядке.
Hесложно видеть, что существуют порядки, при которых желаемого "обмена
значений" не получится.
Hапример, весь вышеописанный процесс выполнения statement (2) можно выразить
вот таким псевдокодом:
// Этап 1. Вычисление выражения
t1 = a ^ b;
t2 = b ^ t1;
t3 = a ^ t2;
// Этап 2. Выполнение побочных эффектов
a = t1;
b = t2;
a = t3;
Это только один из вариантов. Ассоциативность играет свою роль только на этапе
1 и не играет _никакой_ роли на этапе 2.
Hа практике шаги этапа 2 могут быть перемешаны с шагами этапа 1. Большинство
компиляторов при трансляции statement (2) предпочитают выполнять побочные
эффекты сразу, а не откладывать их на потом, т.е. поступают так
t1 = a ^ b;
a = t1;
t2 = b ^ t1;
b = t2;
t3 = a ^ t2;
a = t3;
В этом случае действительно получается обмен. Hо стандарты С/С++ этого не
требуют. Стандарты С/С++ дают компиляторам полное право следовать, например,
предыдущей схеме.
И, наконец, для того, чтобы не возиться с возникающими в таких ситуациях
неоднозначностями, стандарты С/С++ просто говорят, что выражения, которые
делают множественные модификации одной и той же скалярной переменной между
двумя соседними точками следования, порождают неопределенное поведение (стоит
заметить, что это только половина правила). К таким выражениям относится и
выражение (2).
Best regards,
Андрей.
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
| Тема: |
Автор: |
Дата: |
|
<none> |
stan72 |
21 Sep 2002 20:01:31 |
 Re: <none> |
Sergei Paschenko |
23 Sep 2002 17:26:11 |
|
<none> |
Dmitry Pyzhov |
24 Sep 2002 01:07:14 |
  Re: <none> |
Andrey Tarasevich |
25 Sep 2002 11:00:54 |
 <none> |
Dmitry Pyzhov |
26 Sep 2002 11:28:38 |
|
Re: <none> |
Andrey Tarasevich |
27 Sep 2002 10:56:36 |
|
<none> |
Vitaly Mayatskih |
27 Sep 2002 17:40:43 |
|
<none> |
Andrey Tarasevich |
28 Sep 2002 01:34:37 |
|
Re: <none> |
Anatoly Svishev |
28 Sep 2002 00:33:11 |
|
Re: <none> |
Andrey Tarasevich |
28 Sep 2002 02:29:40 |
|
<none> |
Aleksey Loginov |
28 Sep 2002 11:09:12 |
|
Re: <none> |
Vladislav Gusev |
28 Sep 2002 12:30:15 |
|
Re: <none> |
Pavel P |
29 Sep 2002 10:27:02 |
|
<none> |
Vitaly Mayatskih |
29 Sep 2002 14:17:20 |
|
Re: <none> |
Andrey Tarasevich |
29 Sep 2002 23:29:43 |
|
Re: <none> |
Anatoly Svishev |
30 Sep 2002 03:07:53 |
|
Re: <none> |
Andrey Tarasevich |
30 Sep 2002 08:36:27 |
|
<none> |
Ianos Gnatiuc |
30 Sep 2002 22:54:13 |
|
<none> |
Aleksey Loginov |
01 Oct 2002 08:52:46 |
|
<none> |
Ianos Gnatiuc |
02 Oct 2002 10:59:01 |
|
<none> |
Aleksey Loginov |
03 Oct 2002 06:50:24 |
|
Re: <none> |
Andrey Tarasevich |
03 Oct 2002 07:40:22 |
|
Re: <none> |
Vladislav Gusev |
01 Oct 2002 16:36:43 |
|
<none> |
Nickolas Hirgij |
01 Oct 2002 22:50:02 |
|
Re: <none> |
Pavel P |
30 Sep 2002 06:22:38 |
|
<none> |
Max Alekseyev |
29 Sep 2002 22:46:08 |
|
Re: <none> |
Andrey Tarasevich |
30 Sep 2002 11:48:20 |
|
<none> |
Max Alekseyev |
30 Sep 2002 13:06:54 |
|
<none> |
Andrey Tarasevich |
01 Oct 2002 06:21:35 |
|
<none> |
Serge Nozhenko |
01 Oct 2002 15:08:24 |
|
Re: <none> |
Andrey Tarasevich |
01 Oct 2002 19:58:24 |
|
Re: <none> |
Andrey Tarasevich |
01 Oct 2002 21:34:18 |
|
<none> |
Serge Nozhenko |
02 Oct 2002 00:42:48 |
|
<none> |
Andrey Tarasevich |
02 Oct 2002 03:44:12 |
|
<none> |
Mike Murov |
02 Oct 2002 16:07:27 |
|
Re: <none> |
Stanislav Yaroshenko |
03 Oct 2002 01:33:40 |
|
<none> |
Andrey Tarasevich |
03 Oct 2002 03:01:09 |
|
<none> |
Andrey Tarasevich |
03 Oct 2002 03:49:50 |
|
Re: <none> |
Vladimir A. Pertzel |
30 Sep 2002 15:28:40 |
|
<none> |
Ianos Gnatiuc |
30 Sep 2002 23:02:32 |
|
<none> |
Georgy Plechanov |
23 Sep 2002 17:05:12 |
|
<none> |
Igor Bychkov |
24 Sep 2002 21:54:28 |
|
<none> |
Nickolas Hirgij |
24 Sep 2002 08:41:05 |
|
<none> |
Ianos Gnatiuc |
30 Sep 2002 00:50:35 |
|
<none> |
Stanislav Shwartsman |
30 Sep 2002 09:06:00 |
|
<none> |
Ianos Gnatiuc |
30 Sep 2002 22:16:12 |
  Re: <none> |
Vladislav Gusev |
01 Oct 2002 16:12:30 |
|
<none> |
Comoderator Of Ru Algorithms |
02 Oct 2002 21:09:00 |
|
<none> |
Ianos Gnatiuc |
02 Oct 2002 12:02:13 |
|
Re: <none> |
Vladislav Gusev |
03 Oct 2002 19:25:24 |
|
<none> |
Nickolas Hirgij |
01 Oct 2002 20:38:42 |
|
Re: <none> |
Vladislav Gusev |
30 Sep 2002 13:25:00 |
|
<none> |
Ianos Gnatiuc |
30 Sep 2002 22:34:18 |
|
Re: <none> |
Vladislav Gusev |
01 Oct 2002 16:36:11 |
|
<none> |
Stanislav Shwartsman |
01 Oct 2002 22:35:23 |
|
Re: <none> |
Vladislav Gusev |
02 Oct 2002 13:14:46 |
|
<none> |
Stanislav Shwartsman |
02 Oct 2002 16:51:45 |
|
Re: <none> |
Vladislav Gusev |
03 Oct 2002 18:51:00 |
|
<none> |
Dmitry Pyzhov |
01 Oct 2002 01:26:34 |
|
<none> |
Ianos Gnatiuc |
01 Oct 2002 08:01:13 |
|
<none> |
Nickolas Hirgij |
01 Oct 2002 20:32:05 |
|
<none> |
Kirill Frolov |
03 Oct 2002 23:45:50 |
|
<none> |
Igor Dolgov |
04 Oct 2002 00:00:18 |
|
|
