Як C ++ може використовувати стиль передачі продовження?

Припустимо, у C ++ ви виконуєте надто багато рекурсивних викликів за рекурсивною функцією та отримуєте помилку переповнення стека.

Як би ви переписали це в стилі передачі продовження, щоб уникнути переповнення стек?

Мені важко зобразити це на C ++.

9
Ви не збираєтеся отримувати нічого, окрім абстрактних відповідей для такого абстрактного питання. Можливо, ви повинні опублікувати приклад функції, яка викликає переповнення стека, тоді ви отримаєте конкретні відповіді на те, як це виправити. (І особисто, я спробую переписати функцію, щоб використовувати акумулятор, перш ніж переписати його, щоб використовувати продовження ...)
додано Автор ildjarn, джерело
@ highwind7777: Яку абстрактну відповідь ви очікуєте? "Використовувати функціональний функтор"? Це видається надто високим, щоб бути корисним, але важко думати про щось більш конкретне, без більш детального питання ... Що стосується використання акумулятора, ні, ви можете прикріпити рекурсію, якщо ваш компілятор підтримує TCO.
додано Автор ildjarn, джерело
Ви прийшли в потрібне місце.
додано Автор Eddy Pronk, джерело
@ildjarn, дякую за повідомлення. Я насправді шукаю абстрактну відповідь. Якщо я використовую акумулятор, чи не перезаписати його як нормальну ітерацію в C ++?
додано Автор achow, джерело

1 Відповіді

Ну, це досить відкрите питання, але Ерік Ліппер написав (а два насправді) досить довгі серії про саме цю тему . Не зовсім правильна мова, але вона повинна бути досить корисною і дати загальну ідею.

Хоча реалізація CPS в C ++ здається схоже на велику роботу, щоб просто виправити єдину рекурсивну функцію, коли ви можете просто використовувати який-небудь алгоритм, щоб зробити функцію ітеративною з чергою (ви як і раніше використовуєте в основному таку ж кількість даних, але купа далека менш обмежений)

4
додано
@ EricLippert Ви маєте рацію, я вважаю, що це C + + 11 лямбда, але, очевидно, не кожен (навіть навіть близько до більшості) має компілятор, який підтримує лямбда. Без цього вона стає набагато складнішою (використовуйте класи та імовірно передавайте їх?). До речі, дякую за ваші чудові статті - без тебе я б навіть не знав, що таке CPS :)
додано Автор Voo, джерело
@ highwind7777 Покажчики функцій не дуже корисні, якщо ви хочете застосувати закриття. Немає ідеї, як це робить прискорення, але вам потрібно десь зберігати, а не лише покажчик на виконуваний код.
додано Автор Voo, джерело
@Воу: Навіть без C + + 11 lambdas є бібліотеки C ++ 03, які обробляють це тривіально. Див., Наприклад Boost.Phoenix .
додано Автор ildjarn, джерело
Я мав виразну перевагу написання обох цих серій у контексті мов, які мають лексичні закриття, як функцію вбудованої мови. Переписування коду C ++ на закриття, безумовно, є цілком досяжним, але це буде трохи біль.
додано Автор Eric Lippert, джерело
@ highwind7777: Є кілька різних способів, як це зробити. Проблема ускладнюється значною мірою в C ++ через брак автоматичного збирання сміття; точно знаючи, що час закриття може бути складним. Я ніколи не намагався зробити таку річ, і сподіватися, що ніколи не доведеться!
додано Автор Eric Lippert, джерело
Дякую за посилання. @ EricLippert Перезаписуючи код C ++ в закриває, ви маєте на увазі ручне збереження замкнених (обмежених) змінних, передаючи їх у ланцюжок дзвінків?
додано Автор achow, джерело
@Воу, я думаю, що це буде стиль роботи Java у стилі. У C ++ ви можете отримати більш елегантну реалізацію закриття, використовуючи покажчики функцій.
додано Автор achow, джерело
IT KPI C/С++ новым годом
IT KPI C/С++ новым годом
747 учасників

Чат обсуждения С/С++. - Вопросы "напишите за меня лабу" - это оффтоп. - Оффтоп, флуд, оскорбления и вбросы здесь не приняты. - За нарушение - предупреждение или mute на неделю. - За спам и рекламу - ban. Все чаты IT KPI: https://t.me/itkpi/1147