Есть ли у языков функционального программирования больше возможностей для оптимизации времени компиляции?

Я читал книгу «Функциональное программирование для реального мира». Началось со сравнения императивного и функционального языков программирования. И там указывалось, как «значения» и «выражения» в функциональном программировании отличаются от «переменных» и «функций» императивного программирования. Из обсуждения я разработал идею, что -

Функциональные языки программирования имеют больше возможностей для оптимизации времени компиляции, чем их императивные аналоги.

Это правда?

functional-programming compilation Gulshan
источник

Ответы:

Функциональные языки программирования значительно оптимизируют время компиляции. Одной из причин является чистота - параллелизм тривиален, потому что нет государства. Таким образом, компилятор может взять две ветви и выполнить их параллелизацию без изменения поведения программы.

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

Кроме того, все, что не нужно в вычислительном отношении, может быть полностью оптимизировано вне программы.

альтернатива
источник

+1: программирование без побочных эффектов очень, очень легко оптимизировать.

С.Лотт

@mathepic: на самом деле распараллеливание (в Haskell) происходит как во время компиляции, так и во время выполнения. Compile время решает , является ли это стоит создать осколок (поток семена) и время выполнения процессов черепки , как он может, в зависимости от числа потоков , которые вы указали. Если вы укажете только один поток, будут созданы осколки, но они обрабатываются один за другим.

Матье М.

@mathepic: еще одно использование чистоты -> лень и отсутствие вычислений. Если вы можете доказать, что значение не нужно, то полностью удалите вычисления. Если это может быть необходимо, используйте ленивый звук. Если вы знаете, что это будет необходимо, вычислите его прямо перед собой (чтобы избежать накладных расходов). Чистота (просто) потрясающая :)

Матье М.

@Matthieu хорошая точка зрения

альтернатива

@ Масс даже монада IO чиста. Просто результат "запуска" монады ввода / вывода не является.

альтернатива

То, что в принципе есть больше возможностей для оптимизации времени компиляции для функциональных языков, чем для их императивных аналогов, вероятно, верно.

Тем не менее, более интересно то, реализованы ли они в современных компиляторах и насколько важны эти оптимизации на практике (т. Е. Конечная производительность идиоматического кода «реальной жизни») в производственной среде с априорно предсказуемыми настройками компилятора).

напр., представления на Haskell для печально известной игры «Тесты компьютерного языка» (как бы плохо это ни было - но это не так, как сейчас, - что-то значительно лучше) создают впечатление, что значительное количество времени было потрачено на ручная оптимизация, которая столкнулась с утверждением о «возможной оптимизации компилятора из-за insert some property about FP languages here», заставляет думать, что оптимизации (в настоящее время, по крайней мере) скорее теоретическая возможность, чем актуальная реальность.

Я был бы рад, однако, чтобы быть доказанным неправильно в этом пункте.

Александр Баттисти
источник

Причина ручной оптимизации в Haskell больше связана с тем, что некоторые «простые» операции отнимают много времени (с точки зрения сложности) в Haskell. Например, скажем, вы хотите получить последний элемент списка. В Java это довольно простая операция; в Haskell наивный подход требует, чтобы вы обходили весь список, пока не дойдете до конца (из-за ленивого характера списков), что делает его операцией O (n). Это (частично), когда приходят ручные оптимизации.

Mipadi

Я уверен, что есть веские причины для ручной оптимизации Haskell, но они необходимы для «простых» операций, и создается впечатление, что большие возможности для оптимизации кода (в настоящее время) актуальны только в теории.

Александр Баттисти

Это больше разница между оптимизацией алгоритмов и оптимизацией сгенерированного кода. Возьмите пример C: если я пишу алгоритм поиска, я могу написать наивный алгоритм, который просто просматривает список, или я могу использовать бинарный поиск. В обоих случаях компилятор оптимизирует мой код, но он не превратит простой алгоритм поиска в бинарный поиск. Многие ручные оптимизации в коде на Haskell больше связаны с оптимизацией самих алгоритмов, а не сгенерированным кодом.

Mipadi

@mipadi, но кажется, что простая версия алгоритма Haskell не так хороша, как простая версия алгоритмов других языков. (Я подозреваю, что из-за несоответствия между функциональной моделью и компьютерной архитектурой) Даже если она хороша для генерации кода, ее недостаточно для преодоления этой проблемы.

Уинстон Эверт

>> Плохо, как может быть << - Знаете ли вы, плохо это или нет? Что вы вообще имеете в виду, говоря, что это «плохо»? Пожалуйста, будьте конкретны.

igouy

В функциональном стиле поток значений через программу очень и очень заметен (как для компилятора, так и для программиста). Это дает компилятору много возможностей для решения, где хранить значения, как долго их хранить и так далее.

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

Теперь есть две оговорки:

Сообщество языков программирования потратило (впустую?) Много усилий за последние пятьдесят лет на разработку умных способов сделать этот анализ. Существуют хорошо известные приемы, такие как раскраска регистров и т. Д., Которые позволяют выполнять некоторые из более простых случаев большую часть времени; но это приводит к большим, медленным компиляторам и постоянному компромиссу сложности компиляции для качества получаемого кода
В то же время большинство функциональных языков программирования также не являются чисто функциональными; много вещей программ на самом деле нужно делать, как реагировать на I / O являются по своей природе не функциональны, так как ни один компилятор не может быть полностью свободен от этих трюков, и ни один язык не исключает их полностью - даже Haskell, который немного слишком Чисто на мой вкус (ваш пробег может меняться) может только контролировать и блокировать нефункциональные части вашего кода, а не полностью их избегать.

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

jimwise
источник

Все в Haskell является функциональным, просто ваша mainфункция преобразования состояния, а не то, что использует само состояние.

альтернатива

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

Jimwise

@jimwise Ссылочная прозрачность - очень большая разница.

альтернатива

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

Jimwise

@mathepic Да, конечно, вы можете концептуально рассматривать случайность или ввод данных пользователем (или задержку в сети, или нагрузку на систему) как бесконечный поток или функцию от состояния к состоянию, но это не представление, которое поддается полезным рассуждениям о поведении программы Вы или ваш компилятор - Боб Харпер хорошо освещает эту тему в недавнем посте в своем блоге о новой учебной программе CS по функциональному программированию.

Jimwise