1 Тема від ch0r_t Востаннє редагувалося ch0r_t (11.11.2020 01:22:06)

  • ch0r_t
  • Ibi nullus timet mortem.
  • Поза форумом
  • Дата реєстрації: 04.11.2020
  • Повідомлень: 1 944
    • Репутація: 1203

Тема: Безпечні потенц. Нескінчені псевдо-Рекурсії. Теоретичне розсудження.

Тортурований своїм безсонням, мене знайшла і захопила ця ідея, (ймовірно через ослаблену свідомість).
-що можливо імплементувати потенційно безкінечну (псевдо-)рекурсивну функцію в С++.

Проблема:
0. Пам'ять є ресурсом, не нескінченним, - значить рекурсії довго не тривати. Але розгалужені рекурсії можуть бути елегантним і зручним рішенням.

Вірогідне рішення/підхід:
0. "Забстрактувати" функцію як "кадр даних" - представити об'єкт який утримуватиме всі її значення(перемінні), і як наслідок можливі її стани. Теж саме до "позиції" потоку її виконання на випадок коли вона мусить мати чисельні гілки умовних переходів.
1. Провадити об'єкту що утримуватиме "кадри функцій" ряд методів для генерації і запису ідентифікатору(нумерування просто кажучи) функції що звертатиметься для "самозбереження" до нього і якщо вона утримує данні що вже повторювалися -  або вся цілком є еквівалентна тій що вже колись виконувалась, - то ці данні або її саму очевидно - можна заштовхати в хеш-мапу. (звідси потенційно безкінечне виконання, коли багато кадрів - генерованих є рівнозначними.)
2. При власне описанні функції натикати досточорта (технічний термін) кодованих goto і міток, на кожен крок. Повертатись з їх допомогою, через якийсь посередник ймовірно, на початок(чи назад при згортанні на бажану позицію посередником) поки задачу не розв'язано (або не закінчилась пам'ять). Вуаля.

Подякували: P.Y.1

2 Відповідь від Arete

  • Arete
  • Arete
  • Replace Team
  • Поза форумом
  • Звідки: Київ
  • Дата реєстрації: 19.07.2014
  • Повідомлень: 390
    • Репутація: 419

Re: Безпечні потенц. Нескінчені псевдо-Рекурсії. Теоретичне розсудження.

Короутіни підходять на роль потенційно безкінечної функції, виконання якої можна призупиняти, а потім відновлювати.
Coroutines

Функція iota з прикладу безкінечно повертає наступний int. На co_yield виконання зупиняється і повертається значення n, а при наступному виклику iota виконання відновлюється.

generator<int> iota(int n = 0) {
  while(true)
    co_yield n++;
}

Як мінімум в python і java, короутіни давно імплементовані, а в С++ вони тільки-тільки з'являються, можливо ще й не затверджені в стандарті.

Подякували: leofun01, ch0r_t2

3 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 602
    • Репутація: 13310

Re: Безпечні потенц. Нескінчені псевдо-Рекурсії. Теоретичне розсудження.

Лишається питання глобальних змінних. Їх теж зі стековими кадрами зберігати? Чи використовувати чисті функції? Але тоді повторення кадру означає нескінчену рекурсію.
goto лише вбивають оптимізації. Власне, і функції, і структурне програмування придумали, щоб взяти goto під контроль.
Ну і про хвостову рекурсію, сподіваюся, ви в курсі?

Подякували: FakiNyan, ch0r_t2

koala вебсайт

4 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 602
    • Репутація: 13310

Re: Безпечні потенц. Нескінчені псевдо-Рекурсії. Теоретичне розсудження.

Та й узагалі - стискання пам'яті (це те, що ви, фактично, намагаєтеся робити гешем) це окрема цікава тема. В Linux це вміє робити прямо ядро (zswap).

Подякували: ch0r_t1

koala вебсайт

5 Відповідь від ch0r_t

  • ch0r_t
  • Ibi nullus timet mortem.
  • Поза форумом
  • Дата реєстрації: 04.11.2020
  • Повідомлень: 1 944
    • Репутація: 1203

Re: Безпечні потенц. Нескінчені псевдо-Рекурсії. Теоретичне розсудження.

Яких тільки химер мозок не нагенерує піся 70 годин без сну, тепер видається ця ідея доволі дурна коли не сказати ідіотична.

goto лише вбивають оптимізації. Власне, і функції, і структурне програмування придумали, щоб взяти goto під контроль.

Так, так я читав той класичний папір. https://homepages.cwi.nl/~storm/teachin … stra68.pdf

6 Відповідь від P.Y. Востаннє редагувалося P.Y. (14.11.2020 13:43:24)

  • P.Y.
  • P.Y.
  • Replace Team
  • На форумі
  • Дата реєстрації: 19.02.2013
  • Повідомлень: 7 625
    • Репутація: 4966

Re: Безпечні потенц. Нескінчені псевдо-Рекурсії. Теоретичне розсудження.

Цікаво, чи можливий у C або C++ перехід (goto) на довільно задану адресу пам'яті (аналог асемблерного jmp зі змінною) та отримання такої адреси з імені мітки? Десь колись у якійсь книжці бачив сішний код з такими діями, але не впевнений, чи це був реальний код, а не псевдокод для пояснення внутрішньої механіки якихось алгоритмічних конструкцій.
Якщо така можливість є, з нею можна заімплементити будь-які варіації на тему переходів/повернень/викликів, не вдаючись до асемблерних вставок. Втім, якщо, наприклад, нам потрібен аналог ON змінна GOTO список_міток, для його реалізації достатньо й switch-case з переходами звідти.

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

Подякували: ch0r_t1

7 Відповідь від ReAl Востаннє редагувалося ReAl (15.11.2020 12:24:13)

  • ReAl
  • ReAl
  • Видатний діяч Броунівського Руху
  • Поза форумом
  • Звідки: Бровари
  • Дата реєстрації: 27.04.2016
  • Повідомлень: 1 472
    • Репутація: 1855

Re: Безпечні потенц. Нескінчені псевдо-Рекурсії. Теоретичне розсудження.

P.Y. написав:

Цікаво, чи можливий у C або C++ перехід (goto) на довільно задану адресу пам'яті (аналог асемблерного jmp зі змінною) та отримання такої адреси з імені мітки?

Є як розширення в gcc.
void *ptr = &&label; щоб взяти адресу мітки
goto *ptr; щоб перейти по адресі

Найвідоміше використання з тих, що я знаю — один з варіантів втілення protothreads від Adam Dunkels, що знімає обмеження на використання switch.
Власне, protothreads це те, про що я хотів написати ще на початку цієї теми, а зараз так вже зовсім туди пішло :-)

Якось так
https://ideone.com/rEAHNt

#include <stdio.h>
 
void foo(int i)
{
    static const void *sw[] = { &&lab_0, &&lab_1, &&lab_2 };
 
    if (i < 0 || i >= sizeof(sw)/sizeof(*sw)) {
        printf("out of range\n");
        return;
    }
 
    goto *sw[i];
 
lab_0:
    printf("lab_0\n");
    return;
 
lab_1:
    printf("lab_1\n");
    return;
 
lab_2:
    printf("lab_2\n");
    return;
 
}
 
int main(void) {
    for (int i = -1; i < 4; ++i)
        foo(i);
    return 0;
}
Подякували: ch0r_t, leofun01, P.Y.3

8 Відповідь від ReAl

  • ReAl
  • ReAl
  • Видатний діяч Броунівського Руху
  • Поза форумом
  • Звідки: Бровари
  • Дата реєстрації: 27.04.2016
  • Повідомлень: 1 472
    • Репутація: 1855

Re: Безпечні потенц. Нескінчені псевдо-Рекурсії. Теоретичне розсудження.

p.s. щось я не помічав, щоб goto вбивав оптимізацію. Щонайменше, це залежить від компілятора (gcc і асемблерну вставку може викинути, якщо вона не позначена як volatile і йому здається, що вона нічого не робить).
Компілятору все одно, буде написано switch чи отаку конструкцію. Ба більше — часто switch з мітками підряд він всередині як отаку конструкцію і робить.

Подякували: leofun01, ch0r_t2

9 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 602
    • Репутація: 13310

Re: Безпечні потенц. Нескінчені псевдо-Рекурсії. Теоретичне розсудження.

Ні, культурно розставлені goto, звісно, нічого не зіпсують.
Але ж не всі goto розставлені культурно, у цьому ж і проблема.

koala вебсайт