Вопрос по GOTO: это известно, что есть теоремы о полноте

структурного программирования по отношению к GOTO (прыжки только внутри функции).

a) Кто-нибудь делал ли преобразование лапши из GOTO в структурное программирование автоматически?

б) Не можете ли напомнить литературу по этим теоремам? У меня была одна статья, я её потерял.

Соответственно, правильно ли я понимаю, что есть оптимальный алгоритм?

Нет. Есть алгоритм, которым доказывали возможность такого преобразования, но он генерит очень неэффективный код. Там по сути превращают код в стейтмашину, где каждый стейт — это кусок кода, начинающийся с определённой метки, а находится всё это в большом свиче в цикле. Тогда goto заменяется на изменение идентификатора стейта на нужный, и прыжок в начало цикла. В эмскриптере это улучшали эвристиками, алгоритм назвали relooper, он есть в пейпере по эмскриптену. В ллвм в бэкенде васма используется чуть улучшенный алгоритм, stackifier. Он вообще для reducible графа потока исполнения генерит код без диспатча свичами, но тоже полностью без них не справляется

Странно. Мне казалось, что эффективность кода как раз должна быть абсолютно одинакова, что в случае циклов, что в случае goto. В этом же теорема об эквивалентности и заключается.

Совсем не в этом же. Она про то, что существует структурная программа, которая вычисляет то же самое. Про эффективность ни слова

Что-то мне вспоминается, что лапша goto иногда приводит к несводимым циклам, которые стандартными средствами языка в виде циклов, if-else и break-continue никак не получить. Точно ли задача преобразования goto в структурное программирование всегда решаема?

Я просто даже не понимаю, где там потерять эффективность. У вас есть ссылки на теорему об эквивалентности? Кроме того, у wasm нет break/continue/return. А они вроде бы как очень важны.

Да, причём тривиально: while (!exit) {switch(state) { … }}

А, видимо там реально много дублирования кода.

Вместо простого прыжка сделать запись в переменную, прыжок, чтение из переменной, проверку значения, и ещё прыжок — это бесплатное изменение?

Не, дублирования там как раз нет

Не, зачем.

Ну и у wasm есть break/continue/return, если что

Ааа, спасибо. Ну для каких-то ситуаций бесплатное.

Наивная реализация ни для каких не бесплатная

Ну вот интересно, что же именно там небесплатно для нас, какие именно вещи небесплатны. Вот про перевычисление переменной, например, мне было совсем не очевидно.

Оптимизации: существуют.

Два прыжка вместо одного хотя бы

Плюс ещё зависимость по данным между итерациями цикла, так как там постоянно read+write в одну переменную.

Зачем-то relooper, а затем и stackifier придумали же. У них вполне заметный эффект на производительность

Никакой теоремы об эквивалентности я лично не видел. По сути, есть теорема о refinement, но там происходит чуть не экспоненциальное раздувание кода, как выше описали.

Экспоненциальное — это если именно эквивалентный код с точки зрения выполнения прыжков хочется получить

Ну из совершенно простого соображения: пусть каждая строчка программы чего-то пишет на экран, получается, что если мы хотим заменить goto на структурное программирование с теми же вычислительными возможностями, мы можем раздувать код, несколько его замедлить, но и всё.

Как бы да, если не смотреть насколько раздувать и замедлять, то разницы нет. 🤷‍♀️

И тут уже, замечу, зависит от ситуации: для нас раздувание недопустимо, а замедление без изменения сложности, вполне.

"Имя, сестра, имя!" А вы не можете дать хотя бы на это ссылку? Кто писал, когда?

Очень давно... 😅 Сейчас поищу...

Спасибо огромное!

https://en.wikipedia.org/wiki/Structured_program_theorem

Блин,а это не растет из древнего пранка от Вирта, который вольно интерпретировал слова Дейкстры и кликбейтнул сообщество заголовком "GoTo больше не нужен"?😅😅

Спасибо огромное!