OberonCore
https://forum.oberoncore.ru/

Еще раз о выходе из середины цикла
https://forum.oberoncore.ru/viewtopic.php?f=82&t=1500
Страница 1 из 7

Автор:  Валерий Лаптев [ Понедельник, 27 Апрель, 2009 12:23 ]
Заголовок сообщения:  Еще раз о выходе из середины цикла

Тут где-то долго спорили о легитимности выхода из середины цикла.
Добавлю свои 5 копеек.
Я для книжки по системному программированию склепал несколько абстрактных машин.
В одной из них по аналогии с БЭСМ-6 система команд является одноадресной.
И по 2 команды в машинном слове размещается.
Основной цикл процессора (С++):
Код:
while (true)
{   RM = mem[RA];         // выбрать слово
    RA = (RA + 1) % N;         // изменение адреса - по модулю 1024
    RC = RM.cmd.first;         // выбрать команду first
    run();               // выполнить команду
    if (Error || stop) break;           // если команда stop или ошибка
    RC = RM.cmd.second;      // выбрать команду second
    run();               // выполнить команду
    if (Error || stop) break;           // если команда stop или ошибка
}

Небольшие пояснения.
Процессор выбирает слово с 2 командами в регистр RM
из регистра RM команда попадает в регистр команд.
В функции run анализируется код операции и команда исполняется.
Если это команда Stop или при выполнении были ошибки (Error = true), то процессор останавливается

С чисто программистской точки зрения - очень простой цикл, который можно написать, не очень заморачиваясь об инвариантах. Выход из середины смотрится нормально и естественно.
Если же писать условие окончания-продолжения в условии цикла, то вторая команда выполняется всегда.
А вот такой вариант:
Код:
while (!Error & !stop)
{   RM = mem[RA];         // выбрать слово
    RA = (RA + 1) % N;         // изменение адреса - по модулю 1024
    RC = RM.cmd.first;         // выбрать команду first
    run();               // выполнить команду
    if (Error || stop) break;           // если команда stop или ошибка
    RC = RM.cmd.second;      // выбрать команду second
    run();               // выполнить команду
}

мне нравится ГОРАЗДО меньше, поскольку условия выхода разные и еще в разных местах находятся.
Жаль, конечно, что в С++ нет цикла loop - он здесь бы очень подошел.
Выскажетесь, пожалуйста, по поводу приемлемости-неприемлемости такого рода циклов в обучении.
Еще хотелось бы об инварианте такого цикла что-нить увидеть.
Если кто предложит более подходящий вариант - возьму на вооружение.

Автор:  Илья Ермаков [ Понедельник, 27 Апрель, 2009 13:12 ]
Заголовок сообщения:  Re: Еще раз о выходе из середины цикла

Навскидку.

Цикл имеет смысл покомандной обработки. Т.е. взять команду - что-то сделать - если не стоп, то будет следующая команда...
В этом смысле то, что команды лежат по две в одном слове, является деталью, не относящейся к семантике цикла. И я бы скрыл это под какой-то процедурой типа GetLexem в сканерах, которая каждый нечётный вызов считывает новое слово, а каждый чётный - только берёт его вторую часть.

И будет цикл такого вида (схематично, я, конечно, каких-то тонкостей могу и не учитывать):

Код:
error = 0;
GetCommand;
WHILE (cmd # stop) & (error = 0) DO
  Execute;
  GetCommand
END


Неформальный инвариант: (cmd - очередная команда, подлежащая обработке OR cmd = stop) & (error - результат последнего Execute)

Но вообще-то тут компоненты условия зависят от разных действий, и свести в такой простой WHILE можно только потому, что действия независимы. Иначе потребовалось бы ставить IF на GetCommand, или действительно удобнее LOOP-EXIT, про что Ткачёв и упоминал (когда перед каждым условием выхода надо какое-то действие по его вычислению сделать).

Автор:  Евгений Темиргалеев [ Понедельник, 27 Апрель, 2009 13:13 ]
Заголовок сообщения:  Re: Еще раз о выходе из середины цикла

Код:
int state = 0;
while (state != 2)
{
  switch (state)
  {
  case 0:
    RM = mem[RA];         // выбрать слово
    RA = (RA + 1) % N;         // изменение адреса - по модулю 1024
    RC = RM.cmd.first;         // выбрать команду first
    run();               // выполнить команду
    if (Error || stop) state = 2;           // если команда stop или ошибка
    else state = 1;
    break;
  case 1:
    RC = RM.cmd.second;      // выбрать команду second
    run();               // выполнить команду
    if (Error || stop) state = 2;           // если команда stop или ошибка
    else state = 0;
  }
}

Автор:  Сергей Губанов [ Понедельник, 27 Апрель, 2009 13:46 ]
Заголовок сообщения:  Re: Еще раз о выходе из середины цикла

Код:
do
{
   RM = mem[RA];
   RA = (RA + 1) % N;
   RC = RM.cmd.first;
   run();
   if (!(Error || stop))
   {
      RC = RM.cmd.second;
      run();
   }
}
while (!(Error || stop));

Автор:  Евгений Темиргалеев [ Понедельник, 27 Апрель, 2009 14:35 ]
Заголовок сообщения:  Re: Еще раз о выходе из середины цикла

Код:
/* Инвариант:  процессор работает */
stop = false;
while (!stop)

    RM = mem[RA];
    RA = (RA + 1) % N;
    RC = RM.cmd.first;
    run(); if (Error) stop = true; // ошибка -> останов
    if (!stop)
    {
      RC = RM.cmd.second;
      run(); if (Error) stop = true; // ошибка -> останов
    }
}

Автор:  Илья Ермаков [ Понедельник, 27 Апрель, 2009 14:53 ]
Заголовок сообщения:  Re: Еще раз о выходе из середины цикла

Во, только хотел сказать, что задачку хорошо рассмотреть автоматно, как уже опередили :)

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

Пример, как это записывается с циклом Дейкстры:

Код:
GetCommand(cmd); (* ASSERT(cmd # empty) *)
WHILE (cmd # empty) & (cmd # stop) DO
  Execute(cmd, error); cmd := empty
ELSIF (cmd = empty) & (error = no_error) DO
  GetCommand(cmd)
END


Цикл находится либо в состоянии, когда команда выбрана, но не выполнена (cmd # empty); либо в состоянии, когда команда выполнена, и нужно выбирать следующую (cmd = empty). В первом случае условие продолжения - cmd # stop, во втором - error = no_error.

(Заметим, что тут оказалась не нужна противоестественная инициализация переменной error до цикла; как и полагается по её смыслу - до первого Execute она имеет право быть неопределённой).

Автор:  Валерий Лаптев [ Понедельник, 27 Апрель, 2009 17:37 ]
Заголовок сообщения:  Re: Еще раз о выходе из середины цикла

Накидали... :)
1. Второй вариант Евгения мне тоже в голову приходил. Естественно выполнять вторую команду только в случае отсутствия проблем с первой. Но как-то внешне нарушается равноправность двух шагов.
2. Вариант с do while мне почему-то по жизни просто не нравится из-за самого оператора цикла. Фиг знает посчему предпочитаю while в начале (еще один интересный психологический вопрос... :)) ). Поэтому и в голову варианты с do while приходят в последнюю очередь
3. Первый вариант Евгения с состояниями мне в голову не приходил, но чисто внешне кажется несколько длинноватым.
4. Последний вариант Ильи Ермакова - это же БЛЕСК!!!!
Не даром в Питоне есть ветка else у цикла while. Надо в учебном языке тоже такое сделать.
Спасибо!

Автор:  Сергей Губанов [ Понедельник, 27 Апрель, 2009 17:51 ]
Заголовок сообщения:  Re: Еще раз о выходе из середины цикла

Вот это ничего себе до чего доизвращались-то!

Здесь нет ни "автоматов" ни "дейкстры", здесь проще.

Здесь обычный REPEAT-UNTIL внутрь которого вложен IF-THEN-END.
Код:
REPEAT
  *
  IF * THEN * END
UNTIL *
То что условия в IF и в UNTIL одинаковые -- случайность, нет причины чего-то там заумное изобретать.

Автор:  Илья Ермаков [ Понедельник, 27 Апрель, 2009 21:28 ]
Заголовок сообщения:  Re: Еще раз о выходе из середины цикла

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

Автор:  Евгений Темиргалеев [ Вторник, 28 Апрель, 2009 00:52 ]
Заголовок сообщения:  Re: Еще раз о выходе из середины цикла

Автоматом в тех же терминах - для сравнения с циклом Дейкстры:
Код:
state := get;
WHILE state # halt DO
  CASE state OF
  | get: GetCommand(cmd); IF cmd # stop THEN state := exec ELSE state := halt END
  | exec: Execute(cmd, error); IF error = no_error THEN state := get ELSE state := halt END
  END
END
Похоже, цикл Дейкстры рулит :)...

Автор:  Vlad [ Вторник, 28 Апрель, 2009 04:52 ]
Заголовок сообщения:  Re: Еще раз о выходе из середины цикла

Валерий Лаптев писал(а):
Тут где-то долго спорили о легитимности выхода из середины цикла.


Дейкстра, Дейкстра... Только здесь он тоже нафиг не нужен.

Код:
try
{
    while (true)
    {   
        RM = mem[RA];         // выбрать слово
        RA = (RA + 1) % N;         // изменение адреса - по модулю 1024
        RC = RM.cmd.first;         // выбрать команду first
        run();               // выполнить команду
        RC = RM.cmd.second;      // выбрать команду second
        run();               // выполнить команду
    }
}
catch ( run_exception const& ex )
{
    // если команда stop или ошибка
}


P.S. А еще лучше RM.cmd в run отдавать, и там обрабатывать и первую и вторую команду. Тогда цикл вообще в три строчки будет, нагляднее некуда.
P.S.S. Глобальные переменные давить.

Автор:  Peter Almazov [ Вторник, 28 Апрель, 2009 07:19 ]
Заголовок сообщения:  Re: Еще раз о выходе из середины цикла

Илья Ермаков был близок к решению, но не решился сделать последний шаг.
Не знаю, какой синтаксис использовать, буду использовать псевдокод, там можно всё.

Код:
first = true;
while (НЕ stop И НЕ Error) do
  if first then
    RM = mem[RA];         // выбрать слово
    RA = (RA + 1) % N;      // изменение адреса - по модулю 1024
    RC = RM.cmd.first;      // выбрать команду first
  else
    RC = RM.cmd.second;      // выбрать команду second
  endif;
  run();            // выполнить команду
  first = НЕ first;
end;

Судя по всему, здесь напрашивается цикл с постусловием (повторять до), но я его тоже не люблю.

Автор:  Евгений Темиргалеев [ Вторник, 28 Апрель, 2009 08:40 ]
Заголовок сообщения:  Re: Еще раз о выходе из середины цикла

У Вас, имхо, тот же автомат, только закодирован не по стандартному шаблону... И не определено значение охраны цикла в первый раз.
Цитата:
P.S. А еще лучше RM.cmd в run отдавать, и там обрабатывать и первую и вторую команду. Тогда цикл вообще в три строчки будет, нагляднее некуда.
P.S.S. Глобальные переменные давить.
Идёт речь об учебной имитации работы процессора. Имхо, код должен быть приближен к физич. модели и быть проще.
Vlad писал(а):
Дейкстра, Дейкстра... Только здесь он тоже нафиг не нужен.
По мне, здесь не нужен Vlad с исключениями.

Автор:  Валерий Лаптев [ Вторник, 28 Апрель, 2009 10:44 ]
Заголовок сообщения:  Re: Еще раз о выходе из середины цикла

Евгений Темиргалеев писал(а):
Автоматом в тех же терминах - для сравнения с циклом Дейкстры:
Код:
state := get;
WHILE state # halt DO
  CASE state OF
  | get: GetCommand(cmd); IF cmd # stop THEN state := exec ELSE state := halt END
  | exec: Execute(cmd, error); IF error = no_error THEN state := get ELSE state := halt END
  END
END
Похоже, цикл Дейкстры рулит :)...

О!!!! Это мне тоже нравится!

Автор:  Сергей Губанов [ Вторник, 28 Апрель, 2009 12:40 ]
Заголовок сообщения:  Re: Еще раз о выходе из середины цикла

Илья Ермаков писал(а):
Здесь явно цикл Дейкстры - когда шаг цикла и условия остановки неоднородны...
Нет!

Цикл Дейкстры есть обобщение цикла WHILE.

Каноническое использование цикла WHILE есть линейный поиск элемента в одномерном массиве/списке.

Каноническое использование цикла Дейкстры есть линейный поиск элемента в многомерном массиве/списке.

Пример линейного поиска элемента b в трехмерном массиве a: ARRAY N, N, N OF INTEGER:
Код:
i := 0; j := 0; k := 0;
WHILE (i < N) & (j < N) & (k < N) & ~(a[i, j, k] = b) DO
  INC(i)
ELSIF i = N DO
  i := 0; INC(j)
ELSIF j = N DO
  j := 0; INC(k)
END;
IF k < N THEN
  элемент b найден
ELSE
  элемент b не найден
END

Автор:  Info21 [ Вторник, 28 Апрель, 2009 12:52 ]
Заголовок сообщения:  Re: Еще раз о выходе из середины цикла

Сергей Губанов писал(а):
Каноническое использование цикла Дейкстры есть линейный поиск элемента в многомерном массиве/списке.
Вынужден не согласиться. Это вырожденный пример, на каноничность не тянет.

Автор:  Peter Almazov [ Вторник, 28 Апрель, 2009 15:42 ]
Заголовок сообщения:  Re: Еще раз о выходе из середины цикла

Евгений Темиргалеев писал(а):
У Вас, имхо, тот же автомат, только закодирован не по стандартному шаблону... И не определено значение охраны цикла в первый раз.

Значение охраны, да, неопределено. Надо бы определить. Просто исходный текст такой: Error и stop - глобальные переменные, неизвестно как они инициализируются и кто их изменяет. Там и переменная RA не инициализирована.
Что касается автомата, то он тут не причем, хотя можете его разглядеть при желании.
Всё дело в том, что никто не сформулировал инвариант цикла. В моём решении он такой (неформально, естественно): есть указатель на команду, который задан переменными RA и first. Инвариант: команды от начала последовательности до указателя выполнены.

Автор:  Валерий Лаптев [ Вторник, 28 Апрель, 2009 15:49 ]
Заголовок сообщения:  Re: Еще раз о выходе из середины цикла

Изменяет функция run.
Считайте, что эти переменные - локальные в модуле.
Переменная RA получает значение 1 перед первым шагом цикла.
Тоже локальна в модуле

Автор:  Vlad [ Вторник, 28 Апрель, 2009 16:17 ]
Заголовок сообщения:  Re: Еще раз о выходе из середины цикла

Евгений Темиргалеев писал(а):
Идёт речь об учебной имитации работы процессора. Имхо, код должен быть приближен к физич. модели и быть проще.


Ну тогда может проще схему нарисовать а-ля Дракон или псевдокод (в учебных примерах обработку ошибок обычно опускают)?

Автор:  Илья Ермаков [ Вторник, 28 Апрель, 2009 19:32 ]
Заголовок сообщения:  Re: Еще раз о выходе из середины цикла

Здесь нет ошибок. Ошибка исполнения пользовательской программы - нормальная ситуация для интерпретатора.

Страница 1 из 7 Часовой пояс: UTC + 3 часа
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/