Реализация конечного цикла без проверки условия выхода?

Question

[cicatrix]

Добрый день. Вопрос чисто академический, но не даёт мне покоя.
Наткнулся на спор по поводу того, возможно ли реализовать конечный цикл так, чтобы в скомпилированном коде не было ни одной проверки условия.
Вроде как, по итогу родился следующий пример (С++). Примерно, как это работает, я понял, однако много непонятного.
Кто-нибудь может объяснить, что именно происходит в этой строчке:

void (*ptr)(int) =(void (*)(int)) ((int)CycleIteration + (arg / N) * ((int)CycleEnd - (int)CycleIteration));

Весь пример:

#include <stdio.h>
#include <stdlib.h>
int N = 0;
void CycleEnd(int arg)
{
    printf("cycle is finished, N = %d ", arg);
}
void CycleIteration(int arg)
{
    printf("%d\n", arg);
    void (*ptr)(int) =(void (*)(int)) ((int)CycleIteration + (arg / N) * ((int)CycleEnd - (int)CycleIteration));
    ptr(arg + 1); 
}

void cycleBegin(int iteratorStartValue, int iteratorEndValue)
{
    N = iteratorEndValue - 1;
    CycleIteration(iteratorStartValue);
}

int main()
{
    cycleBegin(0, 100);
}

Comments

[Roman]

только нужно

((long)CycleIteration + (arg / N) * ((long)CycleEnd - (long)CycleIteration));

иначе получается сужающее преобразование.

Answer 1

[Adamos]

Главная фишка - в том. что arg / N == 0 до тех пор, пока arg < N.
Функция-итератор вызывает функцию ptr по адресу.
Адрес вычисляется по формуле "адрес функции-итератора плюс то самое выражение arg / N, умноженное на разницу адресов функции-итератора и функции-конца цикла.
Вместо банального сравнения используется математическое выражение, вот и вся хитрость.
И да, Antony прав - это не чистый цикл, а просто извращенная рекурсия.

P.S. Кстати, можно превратить это извращение и в цикл - создаем вектор адресов функций, заполняем его нужным количеством адресов функции, изменяющей переменную цикла, а в конец добавляем адрес завершающей функции. Проходим по нему, ничего не проверяя... зато без рекурсии ;))
P.P.S. Хотя вектор здесь тоже не нужен. Просто массив из двух значений и индексом - то самое выражение.

Comments

[cicatrix]

Да, сам подумал про массив с указателями. И проще будет.

Answer 2

[Antony]

Нет не возможно. У вас в любом случае будет условие. Чисто логически чтобы цикл кончился он должен кончится по какой-то причине, в отсутствии причины он не кончится.

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

p.s.

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

p.p.s.
А вообще не занимайтесь ерундой.

По воводу того, как оно работает:
Смотрим этот кусок кода:
(arg / N) * ((int)CycleEnd - (int)CycleIteration)
Вы вычитаете разницу между адресами функций CycleIteration и CycleEnd (я так понимаю, там должно получится -1 * sizeof(void*). Затем вы это умножаете (arg / N) (вы делите целое число на целое число, емнип оно округляется в меньшую сторону, а не по правилам математики). Кроме последней итерации (когда arg = N) у вас будет результат ноль. Т.е. вы от указателя CycleIteration отнимаете 0 и присваиваете это ptr.
Фактически (кроме последней итерации) ptr указатель на функцию CycleIteration (вы ее вызываете рекурсивно).
Когда arg == N вы умножаете ваш -1 * (sizeof(void*)) на 1 и таким образом вы присваиваете ptr значение CycleIteration - 1*sizeof(void*) т.е. на CycleEnd.

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

Comments

[cicatrix]

Однако формально, этот пример соответствует определению цикла:
Цикл — разновидность управляющей конструкции в высокоуровневых языках программирования, предназначенная для организации многократного исполнения набора инструкций. Также циклом может называться любая многократно исполняемая последовательность инструкций, организованная любым способом

Я компилировал и запускал приведённый пример. Цикл конечный, выход происходит, исключений не возникает.

[Antony]

cicatrix, это у вас на 100 исключений не возникает. попробуйте его до INT_MAX погонять. Стандартного размера стэка, если я не ошибся, должно не хватить.

Answer 3

[Евгений Шатунов]

Если коротко, то в этом коде происходит дичь. :)
Этот код нельзя компилировать, он в общем случае рванет.

Опираться будем на (arg / N). Что это означает? Это означает просто целочисленное деление.
Единица в результате этой операции получится только если arg будет эквивалентен N.

Теперь обратим внимание на (int)CycleIteration. Опустим момент что писавший это человек любит "острые ощущения". Обратим внимание только на то, что тут адрес глобальной функции переводится в число.

Далее обратим наше внимание на ((int)CycleEnd - (int)CycleIteration)). Тип int тут не спроста. Функции CycleEnd и CycleIteration могут быть расположены в произвольных местах бинарного образа. Тут определяется буквальное расстояние между двумя функциями в образе. И это расстояние может быть как положительным, так и отрицательным.

А теперь собираем все вместе. Мы определяем расстояние между функциями итерации и конца и переключаемся с итерации на конец только тогда, когда счетчик итераций достигает лимита.
ptr будет принимать значение CycleIteration до тех пор, пока arg < N, а когда arg == N, ptr принимает значение CycleEnd.

Comments

[cicatrix]

То, что дичь, это понятно. Код был написан на спор как раз для иллюстрации "конечного цикла без единой проверки условий". Мне просто хотелось разобраться, как это работает.

[Adamos]

cicatrix, если хочется разобраться - велкам в ассемблер. Там такие игрища вполне могут быть рабочими решениями. В Крестах - однозначный изврат.

Answer 4

[Rsa97]

(arg / N) - целочисленное деление при arg < N даёт 0, при arg == N даёт 1.

((int)CycleEnd - (int)CycleIteration)) - смещение между адресами функций CycleEnd и CycleIteration

Пока arg < N, (arg / N) * ((int)CycleEnd - (int)CycleIteration)) даёт 0 и в ptr записывается адрес функции CycleIteration.

Как только arg == N, (arg / N) * ((int)CycleEnd - (int)CycleIteration)) даёт нужное смещение и в ptr записывается адрес функции CycleEnd.

Затем вызывается функция по адресу ptr.

Answer 5

[Павел Язовских]

Было же недавно что-то такое на Хабре. Цикл от 100 до 0 с выводом значений но без условных операторов. В комментариях там несколько вариантов было. Мне больше всего понравилась реализация с выделением через размещающий new[] и статическую переменную в классе в этом комментарии.