Бесконечная рекурсия без переполнения стека

l_inc

Да давно уже сделано до нас, гуглить надо уметь:

sml vs c++
http://www.ffconsultancy.com/languages/ray_tracer/comparison_cpp_vs_sml.html

и

ocaml vs c++
http://www.ffconsultancy.com/languages/ray_tracer/comparison.html

те кто не осилит много букв - результат:
+ по скорости одинаково
+ по количеству кода ФЯ зарулили

P.S.

Обе задачи: рейтрейсинг. Очень, надо сказать, трудоёмкая задача.

 

CyberManiac

Хвала тебе и слава - повтори в Win32 приложении и будет полный вин!

 

Беглый взгляд на примеры показывает, что собственно функциональная часть (main) в ФЯ проигрывает "цикличному" варианту и по длине кода и по читабельности - разбор где там хвостовая рекурсия, а где настоящая (и соответсвующее усложнение логики работы) вещь совсем не очевидная, со всеми последствиями о которых я писал выше. Ну а то что интенсивное использование STL в С++ способно изрядно затормозить код, думаю ни для кого не секрет.

 

Y_Mur

> Беглый взгляд на примеры показывает, что собственно функциональная часть (main) в ФЯ проигрывает "цикличному" варианту и по длине кода

Зато вся программа выигрывает. На 25% в SML и на 47% в OCaml.

> и по читабельности...

Вы уже сами сознались, что даже с самим понятием ФЯ впервые встретились в этой теме пару дней назад. Как вы можете судить о ЧИТАЕМОСТИ программ на... на.... на вообще двух разных языках, от ФЯ, в которых и синтаксис то отличается, от того к чему вы привыкли (С++) и даже друг от друга??? Разумеется никак. =)))

> Ну а то что интенсивное использование STL в С++ способно изрядно затормозить код, думаю ни для кого не секрет.

Секрет. Да. Действительно секрет. Ему приходится обучатся пару годиков обучения C++. То что вы их уже преодолели не значит что уберкуча начинающих программистов не шпарят сейчас тысячи строк в секунду по всему миру вида func( std::string val ). И это после года изучения С++. А вы тут пытаетесь за пару дней ЗНАКОМСТВА (даже не обучения!) ФЯ рассуждать о чём-то что там "может затормозить код" и "ухудшить понимание". =)

Мдааааа....

 

Я никогда не утверждал, что "любая семантика не похожая на С++ и асм плоха" Да в ФЯ есть интересные семантические решения (не имеющие прямого отношения к обсуждаемой здесь рекурсии), а если ещё и библиотека стандартных функций хорошо сделана, то это здорово. Гляжу OCaml не стал кидаться в крайности и полностью отказываться от обычных циклов (for) - это тоже хорошо
Я утверждаю, что рекурсия - "инструмент специального назначения" и слепо использовать её как "универсальный инструмент" - самоубийственная нелепость. Ещё большая нелепость, превращать рекурсию в основу семантики языка. (Как верно заметил Виктор Суворов «использовать десант в качестве обычной пехоты подобно использованию в бетоне золотой арматуры – обычная сталь намного дешевле и прочнее»)
Да реализация методов push, top, pop в STL объектах гипернаворочена и замена их на рекурсию, неявно сохраняющую данные в общем стеке, может дать выигрыш в скорости, даже в самом С++, но это весьма опасный приём, чреватый множеством побочных эффектов (частично описанных ранее). Гораздо логичнее и безопаснее использовать для ускорения массивы (если их размер заранее поддаётся вычислению) или «резиновые буферы» (растущие через SEH) и т.п. Кстати в асме (доступном из С) программный стек доступен напрямую и соответвенно проблемы сделать push / pop не прибегая к рекурсии нет

 

Y_Mur

> Я утверждаю, что рекурсия - "инструмент специального назначения" и слепо использовать её как "универсальный инструмент" - самоубийственная нелепость.

А я не спорю. Тем более что в здравом уме даже ФЯ-программисты и не используют. Это та же тема про "if/while/for супротив goto". Хотя goto никто не использует в здравом уме, но работает всё на уровне реализации только через goto (JMP), ибо другого способа передать управление в принципе не существует (CALL лишь шоткат для PUSH IP+CONST_SIZE, JMP ADDR).
Т.е. в принципе, все машины тьюринга эквивалентны, остается лишь радоваться тому, что ФЯ тоже существует.

 

Ну тогда будем считать, что консенсус достигнут
А то у меня из этого топика сложилось впечатление, что замена цикла на рекурсию и есть главная фишка ФЯ.

 

Y_Mur

Если и не главная, то одна из.

 

> На языке OCaml, в частности написан рендеринг формул Википедии, использующих тег <math>, а также популярный файлообменный клиент MLDonkey.

Ну и что? До сих пор - в ФЯ для вас всё говённо? Википедия, откуда сами же цитаты таскаете им пользуется.

 

aa_dav
Да нет. Не всё. Некоторые математические задачки решаются там довольно удобно. Но слишком уж много зависит от компилятора. Да и программист в результате всё равно должен думать не функционально, а о том, как бы из рекурсии цикл сконструировать (перевод в хвостовую рекурсию), который, если верить вики, и то не всегда гарантированно будет организован компилятором.
Но нет... не всё говённо. На существование имеет право.

 

l_inc

> Но нет... не всё говённо. На существование имеет право.

Ах, благородное спасибо, за то, что не зная подхода, не имея опыта в программировании на нём и признавшись таки в этом, вы вынесли сей, довольно мягкий вердикт. =) Спасибо!

 

aa_dav
Как это не имея? Целый прошлый семестр.
Да и что Вы ожидали, задавая этот вопрос? Что я скажу, что все императивные языки - отстой, а функционалые рулят? Я вопрос для того и задал, чтобы либо поднять, либо понизить своё мнение о функциональных языках.

 

И в заключение темы рекурсии в различных языках программирования – макроязык препроцессинга в fasm.
Например, размещение данных в любом месте программы без применения линкера:

Код (Text):

1. .code
2. macro MyData
3.    { szMyString1 db 'hello', 0 }
4. ; здесь дальше код программы
5. macro MyData
6.    { MyData ; объединение новых данных со старыми
7.      szMyString2 db 'Привет', 0 }
8. ; здесь дальше код программы
9. .data
10.   MyData    ; А здесь собранные в кучу данные будут реально располагаться
11. ...

Такая рекурсия тоже не может обеспечить бесконечный цикл и даже цикл вообще, так как на самом деле это не рекурсия – макрос вызывает не самого себя, а «свою предыдущую версию», соответственно более уместна тут аналогия с цепочкой хуков, где каждый обработчик, сделав свою часть работы, передаёт управление дальше по цепочке. Такая форма «псевдорекурсии» не скрывает в себе ни алгоритмических подвохов, ни бесполезного расхода ресурсов типа стека
Хотя и с ней следует быть осторожным – в приведённом примере вся добавляемая в макрос функциональность является полезной, но если переопределить таким образом к примеру команду mov, добавив к ней функциональность реально используемую в ~5÷10% команд mov в программе, то компиляция сильно и бестолково замедлится