Цикл for реализован иначе, чем в других языках? - PullRequest
13 голосов
/ 23 октября 2008

Я прочитал следующее в обзоре Кнута «Искусство компьютерного программирования»:

«Сама« практичность »означает, что потенциальный мажор CS должен изучить ошибки Кернигана при проектировании C, в частности печально известный факт, что цикл for повторно оценивает условие for, которое дублирует время и не соответствует поведению большинство других языков, которые реализуют цикл for. "

(http://www.amazon.com/review/R9OVJAJQCP78N/ref=cm_cr_pr_viewpnt#R9OVJAJQCP78N)

О чем говорит этот парень? Как вы могли бы реализовать цикл for, который не был просто синтаксическим сахаром для цикла while?

Ответы [ 11 ]

29 голосов
/ 23 октября 2008

Учтите это:

for i:=0 to 100 do { ... }

В этом случае мы могли бы заменить окончательное значение 100 на вызов функции:

for i:=0 to final_value() do { ... }

... и функция final_value будет вызвана только один раз.

В С, однако:

for (int i=0; i<final_value(); ++i) // ...

... * final_value -функция будет вызываться для каждой итерации в цикле, что делает хорошей практикой быть более подробным:

int end = final_value();
for (int i=0; i<end; ++i) // ...
5 голосов
/ 23 октября 2008

Если все, что вам нужно, это простой счетный цикл, тогда

for (i=0; i<100; i++) dostuff();

будет хорошо, и компилятор может оптимизировать его.

Если вы используете функцию в части continue для оператора for, например

for (i=0; i<strlen(s); i++) dostuff();

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

Если возвращаемое значение функции не изменится во время итерации, извлеките его из цикла:

slen = strlen(s);
for (i=0; i<slen; i++) dostuff();

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

for (isread(fd, &buffer, ISFIRST);
     isstat(fd) >= 0;
     isread(fd, &buffer, ISNEXT)
{
  dostuff(buffer);
}

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

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

Последний пример можно было бы выразить как цикл while:

isread(fd, &buffer, ISFIRST);
while (isstat(fd) >= 0)
{
  dostuff(buffer);
  isread(fd, &buffer, ISNEXT);
}

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

Я пишу функции более низкого уровня, чтобы их можно было использовать для таких циклов. Он объединяет все элементы цикла while, чтобы вам было легче его понять.

4 голосов
/ 23 октября 2008

Вероятно, он ссылается на циклы типа for i:=0 to N и циклы for-each, которые перебирают элементы набора. Я подозреваю, что все языки, которые имеют цикл for в стиле C, на самом деле получили его от C.

3 голосов
/ 23 октября 2008

У Магнуса все правильно, но следует также отметить, что в большинстве языков (до-C) условным является критерий end (то есть «остановка, когда я равен 100»). В C (и в большинстве языков после C) это критерий continue (т. Е. «Продолжить, пока я меньше 100»).

2 голосов
/ 23 октября 2008

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

q := 10;
for i in 1..q loop
    q := 20;
    --// Do some stuff
end loop;

Этот цикл будет повторяться ровно 10 раз, потому что q было 10, когда цикл начался. Однако, если я напишу, казалось бы, эквивалентный цикл в C:

q = 10;
for (int i=0;i<q;i++) {
   q = 20;
   // Do some stuff
}

Затем цикл повторяется 20 раз, потому что q было изменено на 20 к тому времени, когда я стал достаточно большим, чтобы он имел значение.

Конечно, путь С более гибкий. Однако это имеет немало негативных последствий. Очевидным является то, что программа должна тратить усилия на перепроверку состояния цикла каждый цикл. Хороший оптимизатор может быть достаточно умен, чтобы обойти проблему в таких простых случаях, как этот, но что произойдет, если «q» является глобальным и «делать что-то» включает вызов процедуры (и, следовательно, теоретически может изменить q)?

Жесткий факт заключается в том, что мы просто знаем way о цикле Ada больше, чем о цикле C. Это означает, что с таким же уровнем интеллекта и усилий в оптимизаторе, Ada может выполнять работу по оптимизации намного лучше. Например, компилятор Ada знает, что он может заменить весь цикл на 10 копий содержимого, независимо от того, что это за содержимое. Оптимизатору С придется проверять и анализировать содержимое.

На самом деле это всего лишь один из многих способов, когда дизайн синтаксиса Си мешает компилятору.

2 голосов
/ 23 октября 2008

На x86 цикл может быть выполнен на уровне сборки без создания цикла while. Инструкция loop уменьшает значение регистра ecx и переходит к операнду, если ecx больше 0, иначе ничего не делает. Это классика для цикла.

mov ecx, 0x00000010h
loop_start:
;loop body
loop loop_start
;end of loop
2 голосов
/ 23 октября 2008

По сути, цикл C (и Java, JavaScript и множество языков, производных от C) for действительно является синтаксическим сахаром для цикла while:

for (int i = 0; i < max; i++) { DoStuff(); }

, что является очень актуальной идиомой, строго эквивалентно:

int i = 0; while (i < max) { DoStuff(); i++; }

(Разбирая проблемы с областями видимости, которые в любом случае менялись между версиями C.)

Условие остановки оценивается на каждой итерации. В некоторых случаях это может быть интересно, но это может быть ловушкой: я видел i < strlen(longConstantString) в источнике, который является основным способом замедления программы, потому что strlen - дорогостоящая функция в C.
Каким-то образом цикл for в основном предназначен для запуска заранее определенного количества раз, но вы все равно можете использовать break для досрочного завершения, поэтому динамическая оценка термина остановки скорее раздражает, чем полезна: если вам действительно нужен динамический оценка, вы используете while () {} (или do {} while ()).

На некоторых других языках, таких как Lua, условие остановки вычисляется только один раз, в цикле init. Это помогает прогнозировать поведение цикла и часто более производительно.

2 голосов
/ 23 октября 2008

Развернуть цикл возможно? Если вы знаете, сколько раз будет выполняться цикл for, вы можете буквально скопировать и вставить содержимое цикла. Большинство циклов while будут основаны на некотором условии, которое не является простым подсчетом от 0 до N, поэтому не сможет использовать эту оптимизацию.

Возьмите этот пример

int x;
for (x = 10; x != 0; --x)
{
    printf ("Hello\n");
}

Я знаю, что вы обычно делаете x = 0; x <= 10; ++x, но все будет раскрыто в сборке.

некоторые псевдо-сборки:

mov 10, eax
loop:
print "hello"
dec eax
jne loop

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

Если бы мы развернули его, мы могли бы просто поставить

print "hello"
print "hello"
print "hello"
print "hello"
print "hello"
print "hello"
print "hello"
print "hello"
print "hello"
print "hello"

Нам не нужны никакие другие инструкции, так что это быстрее. Это всего лишь простой пример - я постараюсь найти лучший!

1 голос
/ 24 октября 2008

Сама «практичность» означает, что потенциальный мажор CS должен изучить ошибки Кернигана при проектировании C, в частности, печально известный факт, что цикл for многократно оценивает условие for, которое дублирует while и не соответствует поведению большинства другие языки, которые реализуют цикл for.

Muaahahahaa!

Мне нравятся основные (каламбурные) утверждения рецензента:

  • ошибки Кернигана
  • печально известный факт
  • не соответствует поведению большинства других языков

Для меня это пахнет кем-то, кому никогда не удавалось овладеть основными чертами / философией Си.

Введение

Поскольку я еще изучал физику в университете, я обнаружил, что C (т.е. языки, подобные C) должны были стать моим языком выбора, когда я обнаружил C для loop.

Так что, очевидно, неудача в стиле - это успех в стиле другого. На этом субъективная часть этого обсуждения закончится.

Возможно, Керниган должен был называться цикл?

Шучу? Возможно, нет.

Автор обзора, по-видимому, решил, что каждая языковая конструкция должна иметь одинаковое поведение в разных языках. Поэтому переименование для в loop уменьшило бы его / ее дискомфорт.

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

Действительно ли C нужен?

Цитируя автора обзора, он / она делает следующие утверждения о для и при :

  • для - для постоянных циклов, от начала до конца
  • , в то время как - для циклов, оценивающих условие на каждой итерации

Наличие ортогональных элементов - хорошая вещь, когда вы можете комбинировать их. Но на всех известных мне языках невозможно объединить для и , а вместе.

Пример: что, если для языка рецензента вам нужен цикл, идущий от начала до конца (например, для ), но при этом все равно можно выполнять оценку на каждой итерации цикла (например, while ): вам может понадобиться найти в подмножестве контейнера (не во всем контейнере) значение, соответствующее некоторому тесту с состоянием?

На C-подобном языке вы используете для . На идеальном языке рецензента вы просто взламываете некрасивый код, плача, потому что у вас нет цикла for_ while (или цикла C for ).

Заключение

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

Цитата Бьярн Страуструп:

Существует только два вида языков: те, на которые жалуются люди, и те, которые никто не использует.

Итак, в целом комментарий рецензента следует рассматривать как похвалу.

^ _ ^

1 голос
/ 23 октября 2008

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

...