OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Воскресенье, 08 Декабрь, 2019 13:01

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 122 ]  На страницу 1, 2, 3, 4, 5 ... 7  След.
Автор Сообщение
СообщениеДобавлено: Понедельник, 27 Апрель, 2009 12:23 

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 3124
Откуда: Астрахань
Тут где-то долго спорили о легитимности выхода из середины цикла.
Добавлю свои 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 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9162
Откуда: Россия, Орёл
Навскидку.

Цикл имеет смысл покомандной обработки. Т.е. взять команду - что-то сделать - если не стоп, то будет следующая команда...
В этом смысле то, что команды лежат по две в одном слове, является деталью, не относящейся к семантике цикла. И я бы скрыл это под какой-то процедурой типа 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 
Модератор
Аватара пользователя

Зарегистрирован: Среда, 16 Ноябрь, 2005 00:53
Сообщения: 4539
Откуда: Россия, Орёл
Код:
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 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Код:
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 
Модератор
Аватара пользователя

Зарегистрирован: Среда, 16 Ноябрь, 2005 00:53
Сообщения: 4539
Откуда: Россия, Орёл
Код:
/* Инвариант:  процессор работает */
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 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9162
Откуда: Россия, Орёл
Во, только хотел сказать, что задачку хорошо рассмотреть автоматно, как уже опередили :)

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

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

Код:
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 

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 27 Апрель, 2009 17:51 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Вот это ничего себе до чего доизвращались-то!

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

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 27 Апрель, 2009 21:28 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9162
Откуда: Россия, Орёл
Нет, вроде не случайность! Это достаточно типовой случай. Здесь явно цикл Дейкстры - когда шаг цикла и условия остановки неоднородны...


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 28 Апрель, 2009 00:52 
Модератор
Аватара пользователя

Зарегистрирован: Среда, 16 Ноябрь, 2005 00:53
Сообщения: 4539
Откуда: Россия, Орёл
Автоматом в тех же терминах - для сравнения с циклом Дейкстры:
Код:
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 04:52 

Зарегистрирован: Суббота, 26 Ноябрь, 2005 18:38
Сообщения: 1857
Валерий Лаптев писал(а):
Тут где-то долго спорили о легитимности выхода из середины цикла.


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

Код:
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. Глобальные переменные давить.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 28 Апрель, 2009 07:19 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 531
Откуда: Москва
Илья Ермаков был близок к решению, но не решился сделать последний шаг.
Не знаю, какой синтаксис использовать, буду использовать псевдокод, там можно всё.

Код:
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 
Модератор
Аватара пользователя

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 28 Апрель, 2009 10:44 

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 3124
Откуда: Астрахань
Евгений Темиргалеев писал(а):
Автоматом в тех же терминах - для сравнения с циклом Дейкстры:
Код:
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 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Илья Ермаков писал(а):
Здесь явно цикл Дейкстры - когда шаг цикла и условия остановки неоднородны...
Нет!

Цикл Дейкстры есть обобщение цикла 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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 28 Апрель, 2009 12:52 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8209
Откуда: Троицк, Москва
Сергей Губанов писал(а):
Каноническое использование цикла Дейкстры есть линейный поиск элемента в многомерном массиве/списке.
Вынужден не согласиться. Это вырожденный пример, на каноничность не тянет.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 28 Апрель, 2009 15:42 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 531
Откуда: Москва
Евгений Темиргалеев писал(а):
У Вас, имхо, тот же автомат, только закодирован не по стандартному шаблону... И не определено значение охраны цикла в первый раз.

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 28 Апрель, 2009 15:49 

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 3124
Откуда: Астрахань
Изменяет функция run.
Считайте, что эти переменные - локальные в модуле.
Переменная RA получает значение 1 перед первым шагом цикла.
Тоже локальна в модуле


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 28 Апрель, 2009 16:17 

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


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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 28 Апрель, 2009 19:32 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9162
Откуда: Россия, Орёл
Здесь нет ошибок. Ошибка исполнения пользовательской программы - нормальная ситуация для интерпретатора.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 122 ]  На страницу 1, 2, 3, 4, 5 ... 7  След.

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 0


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2005-2019, участники конференции «OberonCore», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Без разрешения участников и ссылки на конференцию «OberonCore» любое воспроизведение и/или копирование высказываний полностью и/или по частям запрещено.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB