Каким должен быть язык программирования? Анализ и критика Описание языка Компилятор
Отечественные разработки Cтатьи на компьютерные темы Компьютерный юмор Новости и прочее

Функциональное программирование

Введение

Введение

Представляю вниманию заинтересованных читателей несколько статей на тему функционального программирования. Они, наверное, имеют своей целью способствовать не столько образованию читателей, сколько самообразованию писателя :) Есть отличный способ что-то изучить или понять — рассказать об этом другому.

Это будут записки в жанре «мысли вслух». Если получится излагать просто, значит тема понята. Ведь простота — это косвенный признак понимания. Постараюсь здесь поднять и, по мере своих способностей, осветить те вопросы из функциональной парадигмы, которые умалчиваются, не афишируются или недостаточно чётко и ясно описаны в популярной прессе. Попытаемся побороться с недосказанностью и двусмысленностью.

Функциональное программирование — это мир чистых (в математическом смысле) функций, которые выдают один и тот же результат при одних и тех аргументах. Эти функции можно выполнять в любом порядке или вообще не выполнять, их можно выполнять параллельно на множестве процессоров. Эта парадигма программирования избегает изменяемых состояний. Она обладает целым рядом положительных черт. Оптимисты увидят в ней «серебряную пулю», пессимисты напомнят, что таких пуль было уже немало и серебро в них оказалось поддельным. А реалисты попытаются извлечь из него преимущества, взять из него всё выгодное. Объединить всё лучшее из разных миров: из функциональной, императивной и других парадигм.

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

Сильные стороны функционального программирования

Чем меньше число состояний, в которых может оказаться программа, тем она проще. А функциональное программирование как раз и направлено на программирование без состояний. Одинаковость результата для одинаковых входных параметров — тоже замечательное свойство. Как следствие, такие функции легко тестировать и отлаживать. Ещё одно следствие — возможность распараллеливания вычислений.

Последнее актуально, потому что микроэлектроника постепенно заходит в теоретический тупик: нельзя сделать логический вентиль микросхемы размерами меньше, чем атом. Рост тактовой частоты тоже имеет теоретический предел. И выход видится в увеличении числа процессоров, одновременно выполняющих вычисления. А чистые функции, у которых всегда однозначное соответствие между входными параметрами и результатом, отлично подходят для распараллеливания.

Ещё одно преимущество функционального программирования — оно наилучшим образом подходит для доказательного программирования. Императивные программы слишком сложны для этого. В них имеется множество состояний. В императивных же языках результат функций часто зависит не только от входных аргументов. С чистыми функциями всё проще.

Недостатки ФП и их причины

Никлаус Вирт:

Постулирование модели вычислений без состояний поверх машины, наиболее значительной характеристикой которой является состояние, кажется, по крайней мере, странной идеей. Между моделью и машиной существует широкая пропасть, возведение моста через которую обходится дорого. Это невозможно исправить с помощью какой-либо аппаратной поддержки: идея остается плохой и на практике.

  • Невысокая скорость работы программ, написанных на языках ФП.
  • Сложность языков, высокий порог вхождения, оторванность от знакомой парадигмы, непривычность синтаксиса. Чем выше порог вхождения, тем меньше программистов могут или желают его преодолеть.
  • Плохая совместимость с другими языками, сложность или невозможность создания смешанных программ, например Haskell и C++ (см. «Почему никто не использует функциональные языки»).
  • Неразвитость экосистемы: отсутствие хорошей литературы, распространённых библиотек, фреймворков, малочисленное сообщество разработчиков, небольшие возможности для взаимопомощи и консультаций. Невкусность мёда не может объясняться его неизвестностью широким массам.

А теперь поподробнее.

Низкая производительность

Филип Уодлер, один из создателей Haskell, считает, что низкая эффективность уже не может быть причиной неиспользования языков ФП. Он пишет, что

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

Португальские исследователи не разделяют его оптимизм. Они взяли 27 языков программирования и сравнили их эффективность. Ниже приведена выжимка из полученных результатов.

Язык программирования Место/ Рейтинг Время Место/ Рейтинг Память Место/ Рейтинг Энергия
C 1 1.00 3 1.17 1 1.00
Rust 2 1.04 7 1.54 2 1.03
C++ 3 1.56 5 1.34 3 1.34
Java 5 1.89 22 6.01 5 1.98
Go 7 2.83 2 1.05 14 3.23
Pascal 8 3.02 1 1.00 6 2.14
OCaml 9 3.09 13 2.82 9 2.40
Haskell 12 3.55 9 2.45 12 3.10
Python 26 71.90 12 2.80 26 75.88

Здесь видна цена моста над пропастью, о которых говорил Вирт. Усреднённые данные тестов говорят о том, что Haskell проигрывает в эффективности C от 2.45 до 3.55 раз. Эти цифры опровергают Уодлера. Почему Haskell так проигрывает C? Они же «одного поля ягоды» — статически типизированные компилируемые языки.

  • Вызов функции, адрес которой возвращается из другой функции, не даёт процессору предсказать переход и загрузить конвейер предварительными вычислениями. Код на обычных же языках программирования позволяет процессору заниматься этим. Такова цена, которую приходится платить за то, что функции являются объектами первого класса.

  • Все функции в Haskell — каррированные. Там, где в императивных ЯП можно вызвать одну функцию с n аргументами, в Haskell делается n вызовов функций с одним аргументом. Это опять дополнительные расходы.

  • Классикой структур данных является список, который исключает доступ к произвольному элементу за один шаг. Поиск в списках медленный.

  • Куда меньшая, чем обычно, доля функций, возвращающих значение, которое можно поместить в регистр процессора. И большая доля функций, возвращающих кортеж или иных значений, которые в регистр не помещаются. К примеру, все монадические функции возвращают кортеж. Это ведёт к тому, что для возвращения значений постоянно задействуется «куча». Когда её эксплуатируют и в хвост, и в гриву, то скорость программ падает, потребности в памяти растут.

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

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

Для остальных применений некоторая его неторопливость большим препятствием не будет. Хотя опять-таки важно учитывать класс задач. Ведь нельзя утверждать, что соотношение эффективности Haskell и Си стабильно и равно, допустим, трём. Отнюдь. Надо обращать внимание на класс задач, где проигрыш Haskell особенно велик.

Ниши и области оправданного применения ФП

Надо признать, что многие программисты признают ограниченность сфер применения функционального программирования вообще и Хаскелла в частности. Встречались такие признания: «Использовать Хаскелл как числодробилку — не лучшая идея». Или: «Зачем применять Хаскелл там, где много мутабельных данных? Вы сами должны понимать, что Хаскелл не для этого».

Сквозь игольное ушко иммутабельности
Сквозь игольное ушко иммутабельности

Функциональное программирование делает упор на иммутабельность данных. Это не всегда находит понимание у программистов-практиков. «Разве есть такой такие классы задач, в которых обеспечивается неизменность данных?! Какую задачу не возьми, везде объекты меняются с течением времени!». Но если не горячиться, то такие классы задач найти можно. Вот что приходит на ум:

  • Построение отчётов в различных информационных системах. То есть надо произвести анализ, опираясь на уже свершившиеся факты, которые с некоторых пор неизменны. «Какая выручка была у нашей компании в марте месяце? А прибыль? Какие товары самые продаваемые? А если сравнить с прошлым годом?» — эти вопросы задаются уже в апреле, когда данные за март стали неизменны.
  • Браузер, получив ответ от сервера, имеет этот ответ в виде неизменного набора данных. Эти данные иммутабельны!
  • Текст программы, прочитанный компилятором, можно считать неизменным.
  • Языки макросов.

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

Опубликовано: 2022.03.16, последняя правка: 2022.06.07    20:25

ОценитеОценки посетителей
   ▌ 0
   ██████████████████████████████████████████ 2 (100%)
   ▌ 0
   ▌ 0

Отзывы

     2018/12/01 09:12, Автор сайта          # 

Перенесено отсюда.

Использование функциональной парадигмы даёт некоторые преимущества, например, повышение надёжности ПО. Чем больше функциональщины, тем меньше места алгоритмам.

     2018/12/02 00:21, Comdiv          # 

Использование же функциональной парадигмы даёт некоторые преимущества, например, повышение надёжности ПО.

Есть такая разновидность веры. Но подтверждается ли она практикой?

Чем больше функциональщины, тем меньше места алгоритмам.

А это уже просто неправда. Понятие алгоритма верно как для императивной, так и для любой другой парадигмы, в том числе и функциональной.

     2018/12/03 13:02, Автор сайта          # 

Есть такая разновидность веры. Но подтверждается ли она практикой?

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

Насчёт «веры» и её разновидностей. Хорошо бы, чтобы программисты не становились сектантами, обращёнными в какую-то «веру», и слышали аргументы извне. Чтобы не было сект Форта, «Дракона», Оберона. Чтобы не делали из того же Оберона культ, где «Отче наш» — «Арифметика синтаксиса», где поют осанну «O santa simplicitas». Надеюсь, функциональное программирование тоже не станет культом. Тем более, что Haskell и прочие — гибридные языки (а не чисто функциональные, чтобы там не рекламировали!), раз без императивщины не могут обойтись.

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

map() и reduce() во многих языках применяет к элементам контейнера какую-то функцию. В императивных же языках это делается в цикле. Цикл — это последовательность операторов, которая имеет ветвления, это можно наблюдать на блок-схемах. map() и reduce() на блок-схеме — это прямоугольники один под другим, не имеющие ветвлений. Таким образом, эти элементы функционального программирования делают блок-схему одномерной. Блок-схема деградирует вплоть до вырожденного состояния — без единого ветвления, с единственным маршрутом. Формально это можно продолжать называть алгоритмом и блок-схемой, а по факту такая блок-схема никому не нужна. Тот же SELECT в SQL — какие ветки в блок-схеме он образует?

А вот как реализованы map(), reduce() и SELECT — это уже детали. Возможно, «под капотом» — это циклический последовательный процесс, а может и параллельный — раскиданный на разные процессоры.

     2018/12/03 17:52, Comdiv          # 

Функциональное программирование стимулирует написание кода, не имеющего состояния. Уменьшение числа состояний в программе уменьшает её сложность

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

Формально это можно продолжать называть алгоритмом и блок-схемой

Каким образом вы свалили в одну кучу алгоритм и блок-схему? Понятие «алгоритм» не привязано ни к императивному программированию, ни к блок-схемам. Вы давали совет Попову: «Поинтересуйтесь на досуге». Это был хороший совет.

Надеюсь, функциональное программирование тоже не станет культом.

Если Вы на это только надеетесь, то у меня есть плохие новости.

     2018/12/04 13:22, Автор сайта          # 

Это утверждение было бы верно, если бы состояние было бы единственным аргументом некой функции сложности, но это не так.

Если представить программу в виде ориентирированного графа, то вершины этого графа — это состояния, а рёбра — функции перехода из одного состояния в другое. Между сложностью программы и размером этого графа есть не прямая, но тесная связь. Любой инженер, изучавший теорию надёжности систем, скажет Вам, что при одинаковой надёжности элементов система с меньшим количеством элементов надёжнее.

использовали функциональное программирование -> написали программу в R раз быстрей при прочих равных

Я говорил не о скорости, а о надёжности. Но поскольку я и мои коллеги не могут подкрепить или опровергнуть утверждение о надёжности цифрами (впрочем, как и Вы), то остаётся дождаться, что кто-то когда-то соберёт статистику.

Каким образом вы свалили в одну кучу алгоритм и блок-схему?

Там не куча, а некоторая взаимосвязь. Алгоритм [существующий в голове] не подразумевает существование [нарисованной] блок-схемы. А вот [нарисованная] блок-схема подразумевает существование алгоритма [в голове]. А ещё алгоритм можно изобразить ориентированным графом, для этого пригодятся Р-схемы — изобретение Вельбицкого, советского программиста из Киева. Представьте себе такой граф алгоритма, где начальную вершину и конечную соединяет один-единственный маршрут. Простая схема, от которой легко добиться надёжности. Функциональное программирование местами помогает с одномаршрутными графами.

«Поинтересуйтесь на досуге». Это был хороший совет.

Ну хоть одна хорошая оценка. Кстати, Вы интересовались оптимизациями, в которых помогают чистые функции? Об этом говорилось чуть выше. Представьте себе такое: Вы описали в программе функцию, а потом вызвали с входными параметрами, и все параметры — константы. Вопрос: «Вы можете выполнить эту функцию на этапе компиляции, подставив константы? Чтобы вызов функции заменить другой константой — результатом работы этой функции?». Примерно так: вместо sin(π/6) подставить ½. Ответ очевиден: «Нет, потому что функция может оказаться недетерминированной или производящей побочный эффект. Такие функции нельзя выполнять на этапе компиляции». Тогда следующий вопрос: «А если эта функция гарантированно чистая?». Ответ: «Тогда можно».

Языки типа Си или Оберона не могут гарантировать чистоту функции. А вот язык D может, там есть для этого ключевое слово «pure». А в Haskell функции и так по умолчанию чистые. А может ли Оберон обзавестись ключевым словом «pure»? Нет, там взят курс на максимально компактный язык, на минимальное количество правил в языке. А зря, ведь чистые функции имеют и другие замечательные свойства, о которых Вы, думаю, уже читали.

Если Вы на это только надеетесь, то у меня есть плохие новости.

Ничего страшного. Достаточно просто иметь холодную голову и оставаться прагматиком.

     2018/12/06 00:14, Comdiv          # 

Любой инженер, изучавший теорию надёжности систем, скажет Вам

Любой человек, знакомый с многопараметрическими зависимостями Вам скажет, что оценивать функцию по одному параметру некорректно. То есть Вы можете предполагать об уменьшении одного из параметров и не замечать увеличение другого. Всё ещё сложней, когда речь идёт о сложно формализуемой функции, такой как надёжность. Также любой человек, знакомый с понятием алгоритмической полноты Вам скажет, что о программе на алгоритмически полном языке вообще сложно утверждать о наличии или отсутствии чего либо. Более того, на самом базовом уровне функциональная и императивные парадигмы — это вопрос интерпретации.

Я говорил не о скорости, а о надёжности.

Пожалуйста, используйте логику. Высокая надёжность доступна на любом языке. Для того же печально известного Си наработаны на практике(!) методы получения программ высокой надёжности. Вопрос лишь в ресурсах, которые нужно потратить для достижения этого уровня. Поэтому бессмысленно говорить о достижении надёжности благодаря выбору языка, а имеет смысл говорить о достижении той же самой надёжности за меньшее время, или о достижении большей надёжности за тоже самое время.

Там не куча, а некоторая взаимосвязь.

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

Ну хоть одна хорошая оценка.

Совет был хорошим, но он не будет таким до конца, если не будет пропущен через себя.

Кстати, Вы интересовались оптимизациями, в которых помогают чистые функции

Напомните, пожалуйста, где я интересовался.

Ничего страшного. Достаточно просто иметь холодную голову и оставаться прагматиком.

Недостаточно думать о том, что голова холодная.

     2018/12/06 14:20, Автор сайта          # 

Ну да, если система уменьшила число размерностей с n до n-1, то это не означает увеличения простоты и увеличения надёжности. Если в программе уменьшается логическая сложность, уменьшается количество точек принятия решений, то это её никак не упрощает. И на надёжности не сказывается. Надёжность, если разобраться, — сущность эфемерная. Продолжать дискуссию, думаю, неуместно.

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

Всё правильно, f(g(h(x))) — это алгоритм. y=h(x); z=g(y); w=f(z) — это тоже алгоритм. Я так выше и написал:

Формально это можно продолжать называть алгоритмом

Пусть даже и вырожденный до графа, между начальной и конечной вершинами которого — единственный маршрут. Даже попробую угадать: Вам наверняка нравится рисовать блок-схемы для f(g(h(x))).

Напомните, где интересовался

Вы, цитируя, забыли поставить знак вопроса: не «Вы интересовались», а «Вы интересовались?». Т.е. это не утверждение, а вопрос. Просто выше рекомендовал Вам поинтересоваться, а потом уточнил, знакомились ли Вы с рекомендованным. Но Вы, видимо, не хотели поднимать тему чистых функций. Где выгода от функционального программирования видна, но признавать этого Вам не хочется. Наверно потому, что тут поспорить не получается.

А насчёт надёжности — тут можно и поспорить. Ведь объективных, общепризнанных результатов исследований на эту тему не существует.

Давайте закруглимся с бесполезным спором и не будем отнимать время друг у друга.

     2018/12/06 16:16, Comdiv          # 

Ну да, если система уменьшила число размерностей с n до n-1

Про размерности- это метафора, а не суть. Поэтому ирония неуместна.

Формально это можно продолжать называть алгоритмом

Круг замкнулся, Вы снова противопоставляете их. В том то и дело, что не формально, а фактически. Не привязано понятие алгоритма ни к блок-схемам, ни к графам. Вы так и не воспользовались собственным советом.

Даже попробую угадать: Вам наверняка нравится рисовать блок-схемы для f(g(h(x)))

Снова юмор. Я никогда не рисую блок-схем, даже в голове. Алгоритм — он алгоритм хоть на Java, хоть на Haskell.

это не утверждение, а вопрос. Просто выше рекомендовал Вам поинтересоваться

Спасибо за рекомендацию. Я знаком с чистыми функциями и использую их на практике даже в Си. Я много ещё с чем знаком, но ещё больше с чем не знаком, конечно. Пожалуйста, не делайте рекомендаций на основании Ваших предположений, о незнании собеседника. Похоже, что из моего сомнения об априорном или основанном на метафорах повышении надёжности от использования функционального программирования, Вы сделали вывод, что я вообще отрицаю пользу вещей, которые ассоциируют с функциональной парадигмой. Хотя мне известно, что начиная с Фортрана, большинство «императивных» языков содержат в себе элементы функциональной парадигмы.

Давайте закруглимся с бесполезным спором и не будем отнимать время друг у друга.

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

     2018/12/06 18:21, Автор сайта          # 

ирония неуместна... Круг замкнулся

А что уместно, когда замкнулся круг? Именно ирония уместнее всего!

не формально, а фактически

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

Не привязано понятие алгоритма ни к блок-схемам, ни к графам

Бог никак не привязана к иконам. Но иконы с изображением бога к нему всё-таки привязаны. Икона — это материальное воплощение наших мыслей о вечном. А блок-схема — это воплощение мыслей об алгоритме.

Алгоритм — он алгоритм хоть на Java, хоть на Haskell

О! Если я Вас правильно понял, то Вы придерживаетесь мысли, что алгоритм — он и в Африке алгоритм, един и одинаков? Хоть он на Java, хоть на Haskell, хоть на ассемблере реализованный? Хоть для 8-битных процессоров, хоть для 64-битных? Что для процессоров с аппаратной реализацией плавающей арифметики, хоть для платформ с отсутствием оной? Что для современных процессоров, что для процессоров IBM/360, где отсутствовала аппаратная поддержка стека? Что при выполнении оператора «SELECT» в SQL, что при выполнении аналогичной задачи на ассемблере?

Я спорю ради установления истины

Ну если Вы так любите истину, то почему не признали, что чистые функции делают возможными оптимизации, которые невозможны в языках без этих функций?

А вообще-то все религиозные войны имели своей целью оказать помощь в установлении истины. Давайте просто пожмём друг другу руки и разойдёмся.

не желание бесмыссленно поспорить или посамоутверждаться, а желание улучшить интересный ресурс

Спасибо, что Вы заставили меня пошерстить Интернет в поисках определения алгоритма. Правда, разноголосица там не меньше, чем у нас с Вами. Спасибо, что подтолкнули изложить то, что давно сидело в голове (пример с синусом).

     2018/12/06 19:47, Comdiv          # 

О! Если я Вас правильно понял, то Вы придерживаетесь мысли, что алгоритм — он и в Африке алгоритм, един и одинаков? Хоть он на Java, хоть на Haskell, хоть на ассемблере реализованный?

Нет. Понятие «алгоритм» одинаково для всех языков в соответствии со смыслом слова «понятие». Конкретный же алгоритм привязан к языку исполнителя и потому не может быть абсолютно одинаковым для исполнителей с языками, не содержащих достаточного общего подмножества. При этом могут быть эквивалентные алгоритмы и возможен перевод алгоритма на языке одного исполнителя в эквивалентный алгоритм на языке другого исполнителя.

Ну если Вы так любите истину, то почему не признали, что чистые функции делают возможными оптимизации, которые невозможны в языках без этих функций?

Не в полной мере понимаю, о чём Вы. Конкретно я применяю чистые функции в Си для оптимизаций. Примеры Вы можете найти в документации gcc и в трансляторе, ссылку на который я приводил.

А вообще-то все религиозные войны имели своей целью оказать помощь в установлении истины. Давайте просто пожмём друг другу руки и разойдёмся.

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

В любом случае, жму руку.

     2018/12/06 20:29, MihalNik          # 

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

Они возможны, просто алгоритмы для получения аналогичного конечного результата оптимизации требуются другие. Будь иначе — языки не были бы полными в принципе. В этом смысле ФП — это не автоматизированная, а ручная оптимизация.

     2018/12/07 23:59, Автор сайта          # 

Comdiv Не в полной мере понимаю, о чём Вы. Конкретно я применяю чистые функции в Си для оптимизаций.
MihalNik Они возможны, просто алгоритмы для получения аналогичного конечного результата оптимизации требуются другие.

Я понял, что плохо изложил свою идею. Многие компиляторы, встретив в тесте программы «2+2», выполняют это сложение прямо во время компиляции — с помощью встроенного интерпретатора, как правило. Почему это возможно? Потому что для типа данных «целые числа» операция сложения — это чистая функция. Она детерминирована, не имеет побочных эффектов.

Теперь представим, что Вы написали определение функции «fun(int, int)», а потом вызвали её с константными аргументами: «fun(2, 10)». Вопрос: мы можем вычислить эту функцию прямо во время компиляции? Допустим, у нас есть встроенный в компилятор интерпретатор. Он может вычислить константное выражение и вместо него в выходной код подставить одну-единственную константу? Нет, потому что «fun(int, int)» может оказаться «грязной». Если у вас в языке нет чистых функций, то и гарантий чистоты тоже нет. Почему?

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

Явное же определение чистоты функции (хоть с помощью ключевого слова, хоть по умолчанию) распространяется и на указатели на функции. Поэтому если чистота «fun(int, int)» гарантируется средствами языка, то и в исполняемом коде вызов «fun(2, 10)» можно заменить на константу.

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

     2018/12/08 02:40, Comdiv          # 

Вы написали определение функции «fun(int, int)», а потом вызвали её с константными аргументами: «fun(2, 10)». Вопрос: мы можем вычислить эту функцию прямо во время компиляции? ... Нет, потому что «fun(int, int)» может оказаться «грязной»

Поэкспериментируйте с gcc, почитайте документацию по опциям и атрибутам. Возможно, результат Вас удивит. Если будет интересно, можете ещё поэкспериментировать с суперкомпилятором Java, который, правда так и остался на уровне прототипа. Да и это уже совсем другая история.

     2018/12/08 12:49, Автор сайта          # 

почитайте

Почитаю. Неплохо б сразу ссылку на документацию. А что, в C++ чистые функции появились?

     2018/12/08 14:56, MihalNik          # 

Потому чистоту функций нельзя определить по косвенным признакам

Можно. Даже с передачей указателей вычисление чистоты или нечистоты функции во многих случаях допустимо. Утверждение о невозможности просто абсурдно. Если в стандарте конретного языка и в реализации его компилятора этого нет, это никоим образом не значит, что этого принципиально нельзя сделать в таких случаях. Вот эта функция, например, чистая:
int f(int a,int b){return a+b;}
и если в ней заменить передачу значений ссылками или указателями с последующим разыменованием вручную — функция останется чистой. У Вас, скорее всего, путаница между фактической чистотой функции и передачей информации о чистоте через синтаксис в целях упрощения алгоритмов.

А что, в C++ чистые функции появились?

У Вас не отделено понятие чистоты функции от средств их поддержки. Представьте, что можно написать комплиятор, который вообще не оптимизирует даже 2+2. Меняется ли синтаксис языка? Нет. Меняется ли семантика? Что вообще говорит стандарт языка про оптимизации? А он может что-то говорит, а может — не говорить. Зависит ли от этого возможность оптимизации 2+2? Нет, если язык говорит, что эти константы нельзя менять во время работы программы.

     2018/12/08 18:24, Автор сайта          # 

Да, мне надо было быть точнее в формулировках. В общем случае чистоту функции нельзя определить. А в частных случаях — пожалуйста. Тот же «2+2».

У Вас, скорее всего, путаница между фактической чистотой функции и передачей информации о чистоте через синтаксис в целях упрощения алгоритмов.

Да, я имею в виду чистоту, закреплённую через синтаксис и гарантированную синтаксисом. В противном случае эту чистоту приходится определять.

     2019/10/02 15:09, Александр Коновалов aka Маздайщик          # 

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

Рекомендую статью Burstall R.M., Darlington John «A Transformation System for Developing Recursive Programs» (1977). Она правда на английском, но, я думаю, по силам среднему программисту. Описанная в ней мощная система преобразований программ применима только к чистым функциям. Ссылка:

https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.19.4684&rep=rep1&type=pdf

Если представить программу в виде ориентирированного графа, то вершины этого графа — это состояния, а рёбра — функции перехода из одного состояния в другое.

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

И таки можно для функциональной программы построить конечный граф, узлами которого будут стеки, а рёбрами — переходы. А потом по этому графу (забыв об исходной программе) можно выписать новую программу. И она будет, как правило, оптимальнее исходной. Этот подход к преобразованию программ открыт Валентином Фёдоровичем Турчиным и называется суперкомпиляцией.

Теория суперкомпиляции описана только для чистых функциональных программ. Про исследования побочного эффекта в суперкомпиляции я ничего не знаю. Однако, суперкомпилятор SCP4 может преобразовывать программы с «нечистыми» функциями, но детали его работы я пока не знаю.

Да, мне надо было быть точнее в формулировках. В общем случае чистоту функции нельзя определить.

Пример:
int f(const char *data) {
int res = g(data) + 10;
if (res == 32) {
puts("Hello!");
}
return res;
}
Эта функция чистая? Чистая, если g(x) чистая и никогда не возвращает число 32. Но вот определить, возвращает ли функция g(x) число 32 — в общем случае алгоритмически неразрешимая задача.

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

     2019/10/05 18:10, Comdiv          # 

Про исследования побочного эффекта в суперкомпиляции я ничего не знаю

А для Java http://supercompilers.ru/ не считается? Правда, в ограниченном виде, но чем не исследование?
Ну и на базовом уровне чистота функции — это вопрос трактовки, любой императивный язык можно формализовать как 100% чистый функциональный язык. В этом смысле ограничение на чистоту функций не является ни необходимым, ни достаточным.

     2019/10/06 19:32, Александр Коновалов aka Маздайщик          # 

Теория суперкомпиляции описана только для чистых функциональных программ. Про исследования побочного эффекта в суперкомпиляции я ничего не знаю.

А для Java http://supercompilers.ru/ не считается? Правда, в ограниченном виде, но чем не исследование?

Суперкомпилятор для Java я внимательно не изучал, поэтому не знаю детали его работы.

В принципе, если метод на Java выполняет (прямо или косвенно) присваивания только локальным переменным (и не вызывает нечистых методов), то его можно преобразовать в один или несколько чистых методов — методов, в тексте которых нет оператора присваивания. Модификацию состояния можно имитировать при помощи уникальных типов: Тип, гарантирующий уникальность.

Кстати, к этой статье приложил руку Автор сайта.

Как осуществляется поддержка нечистых функций в суперкомпиляторе Java — понятия не имею. Однако, не исключаю, что никак.

Ну и на базовом уровне чистота функции — это вопрос трактовки, любой императивный язык можно формализовать как 100% чистый функциональный язык.

Не очень понял. Раскройте мысль, пожалуйста.

     2019/10/07 14:17, Автор сайта          # 

чистота функции — это вопрос трактовки

Т.е. всё зависит от трактовки, кто как её понимает? Как у юристов: «Там где есть два юриста, там существуют три мнения».

любой императивный язык можно формализовать как 100% чистый функциональный язык.

Не могли бы подробнее изложить свои мысли? Вас можно понять так, что исходник на Си, к примеру, можно по определённому алгоритму переписать на Хаскелле. Я, допустим, могу написать на Си обработчик прерываний и поместить адрес этой функции по абсолютному адресу. Но как такое написать на Хаскелле?

В этом смысле ограничение на чистоту функций не является ни необходимым, ни достаточным.

В языке D есть функции с ключевым словом pure, которое запрещает внутри этой функции грязные функции, что гарантирует чистоту функции. И это всё зря? Это не является достаточным для чистоты функции? И что ещё необходимо, помимо чистоты вызываемых функций?

уникальных типов

«Уникальный тип» — это калька с английского, передающая смысл не точно. Перед тем, как определиться с «типом, гарантирующим уникальность», я советовался. В частности, небезысвестный Роман Душкин согласился именно с такой формулировкой, как наиболее полно описывающей суть термина.

     2019/10/08 01:30, Comdiv          # 

Раскройте мысль, пожалуйста.

А что раскрывать, если Вы и так всё знаете? Если бы Вам пришлось доказывать полноту по Тьюрингу чистого функционального языка, как бы Вы это сделали? Что бы это Вам сказало об императивной машине Тьюринга с функциональной точки зрения?

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

     2023/07/28 23:44, Автор сайта          # 

Стихи от Лидии Васильевны Городней о функциональном программировании

Основы:
            В компьютере всё — данные
            Символьные1, первозданные2.
            И нет нужды в различении —
            Функция или значение3.
            В определение функции
            Может включаться рекурсия4.
            Все параметры можно связать,
            Их в любом порядке вычислять5.

Спешки нет границы задавать,
Автомат их может изменять6.
Лишь бы данные все сохранить
И всегда к ним доступ получить7.
Формируя функций ряд,
Удобен чистый результат.

Компромиссы:
            Где данных тип играет роль,
            Всё берём мы под контроль8.
            Чтоб рекурсию смягчить,
            Можем циклы применить9.
            Раз все данные хранятся,
            Может к ним и возвращаться10.

Всё что сложно вычислять,
Можно хранить, не повторять11.
Ввод и вывод при отладке
Могут не портить функций гладких12.
Пространства-времени учёт
Конечность счёту придаёт13.

Следствия:
            Нам подвластны все программы
            От маленьких до сложных самых14.
            Можно взять любую часть,
            Её отдельно вычислять15,
            Любую логику вживить,
            Корректность свойств определить16.

У нас в руках процессов вечность17
И представлений бесконечность18.
Чтоб упростить процессов нить,
Можем унарность применить19

Параллелизм:
            Чтобы дубли не плодить,
            Ленивость можно применить20.
            К параллелизму чтоб добраться,
            Берём пространство итераций.
            Но остаётся местом узким
            Распределение нагрузки21,

Распараллеливать при том
Даётся нам с большим трудом22.
Разберёмся мы не скоро
С идентичностью повторов23.
Оптимизаторам нужны
Многоконтактные узлы24.


1 Выбираются на усмотрение программиста
2 Определяются по традициям из разных сфер — числа, строки и т.п.
3 Универсальность
4 Самоопределение
5 Независимость параметров
6 Сборшик мусора
7 Неизменяемость данных
8 Статический анализ
9 Оптимизация рекурсивных определений
10 Обратимость действий
11 Мемоизация
12 Псевдо-функции
13 Учёт прогноза требуемых ресурсов
14 Метапрограммирование
15 Факторизация, декомпозиция, частичность
16 Верификация
17 Непрерывность процессов
18 Неограниченные структуры данных
19 Сведение функций к унарной форме
20 Ленивые, отложенные, опережающие действия
21 Поддержана в языке mpC
22 Ограниченность результатов автоматизации
23 Суперкомпьютеры, распределённые системы и многопроцессорные комплексы
24 Поддержаны в языке Sisal

     2023/07/30 12:18, Автор сайта          # 

Ещё стихи от Лидии Васильевны:

Парадигма — это
Задачи и приоритеты,
Языки и системы,
Примеры программ и схемы

Такой реализации понятий,
Что стиль мышления понятен.
Парадигмы возникают,
Когда чего-то не хватает.

        Сначала были просто вычисления1
        И память для храненья результатов2.
        Потом пришли программы управления3
        И индексы как к векторам прилада4.

        Библиотеки и системы
        Нам дарят силу подпрограмм5.
        Интерпретатор и транслятор
        Дают дорогу языкам6!

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

А это значит можно параллельно
Отдельные потоки запускать8.
И множества или пространства
В создании процессов применять9.

        Мир задач весьма широк
        Включаем обработку строк10
        И вариантов перебор11,
        Чтоб новизне открыть простор.

        Наконец, пришлось понять —
        Нельзя с нуля всё создавать.
        Чтоб не решать задачи в лоб,
        Появляется ООП.

Парадигм на свете много,
Каждая — своя дорога.
Дороги умеют сливаться,
Сужаться и расширяться.

По дорогам идут языки,
Программы вокруг порождая.
Работоспособность программ
Роль парадигм подтверждает.

1 Арифмометр
2 Калькулятор
3 Компьютер
4 Императивное программирование
5 Fortran
6 БНФ — 99 Синтаксически управляемые обработчики данных
7 Функциональное программирование — Lisp
8 Функциональное программирование — APL
9 Setl, Planner
10 Snobol
11 Логическое программирование

Добавить свой отзыв

Написать автору можно на электронную почту
mail(аt)compiler.su

Авторизация

Регистрация

Выслать пароль

Карта сайта


Содержание

Каким должен быть язык программирования?

Анализ и критика

●  Устарел ли текст как форма представления программы

●  Русский язык и программирование

●  Многоязыковое программирование

Синтаксис языков программирования

Синтаксический сахар

●  Некоторые «вкусности» Алгол-68

●  «Двухмерный» синтаксис Python

●  Почему языки с синтаксисом Си популярнее языков с синтаксисом Паскаля?

●  Должна ли программа быть удобочитаемой?

●  Стиль языка программирования

●  Тексто-графическое представление программы

●●  Разделители

●●  Строки программы

●●  Слева направо или справа налево?

●  Комментарии

●●  Длинные комментарии

●●  Короткие комментарии

●●  Комментарии автоматической генерации документации

●●  Нерабочий код

●●  Помеченные комментарии

●  Нужны ли беззнаковые целые?

●  Шестнадцатиричные и двоичные константы

●  Условные операторы

●  Переключатель

●  Циклы

●●  Продолжение цикла и выход из него

●  Некошерный «goto»

●  Изменение приоритетов операций

●  Операции присвоения и проверки на равенство. Возможно ли одинаковое обозначение?

●  Так ли нужны операции «&&», «||» и «^^»?

●  Постфиксные инкремент и декремент

●  Почему в PHP для конкатенации строк используется «.»?

●  Указатели и ссылки в C++

●●  О неправомерном доступе к памяти через указатели

●  Обработка ошибок

●  Функциональное программирование

●●  Нечистые действия в чистых функциях

●●  О чистоте и нечистоте функций и языков

●●  Макросы — это чистые функции, исполняемые во время компиляции

●●  Хаскелл, детище британских учёных

●●  Измеряем замедление при вызове функций высших порядков

●●  C vs Haskell: сравнение скорости на простом примере

●●  Уникальность имён функций: за и против

●●  Каррирование: для чего и как

●●  О тестах, доказывающих отсутствие ошибок

●  Надёжные программы из ненадёжных компонентов

●●  О многократном резервировании функций

●  Использование памяти

●  Почему динамическое распределение памяти — это плохо

●  Как обеспечить возврат функциями объектов переменной длины?

●●  Типы переменного размера (dynamically sized types, DST) в языке Rust

●●  Массивы переменной длины в C/C++

●●  Размещение объектов в стеке, традиционный подход

●●  Размещение объектов переменной длины с использованием множества стеков

●●  Размещение объектов переменной длины с использованием двух стеков

●●  Реализация двухстековой модели размещения данных

●●  Двухстековая модель: тесты на скорость

●●  Изменение длины объекта в стеке во время исполнения

●●  Размещение объектов переменной длины с использованием одного стека

●  Можно ли забыть о «куче», если объекты переменной длины хранить в стеке

●  Безопасность и размещение объектов переменной длины в стеке

●  Массивы, структуры, типы, классы переменной длины

●  О хранении данных в стеке, вместо заключения

●  Реализация параметрического полиморфизма

Описание языка

Компилятор

Отечественные разработки

Cтатьи на компьютерные темы

Компьютерный юмор

Новости и прочее




Последние отзывы

2024/02/24 18:10 ••• Бурановский дедушка
ЕС ЭВМ — это измена, трусость и обман?

2024/02/22 15:57 ••• Автор сайта
Русский язык и программирование

2024/02/22 14:55 ••• veector
О неправомерном доступе к памяти через указатели

2024/02/19 17:58 ••• Сорок Сороков
О русском языке в программировании

2024/02/16 16:33 ••• Клихальт
Избранные компьютерные анекдоты

2024/02/15 12:55 ••• Деньги на WWWетер
«Двухмерный» синтаксис Python

2024/02/10 22:40 ••• Автор сайта
Все языки эквивалентны. Но некоторые из них эквивалентнее других

2024/01/30 23:27 ••• Сорок сороков
О превращении кибернетики в шаманство

2024/01/23 12:04 ••• Неслучайный читатель
О многократном резервировании функций

2024/01/16 17:11 ••• Автор сайта
Некоторые «вкусности» Алгол-68

2024/01/06 16:54 ••• Ильдар
Новости и прочее

2023/12/21 18:26 ••• Автор сайта
Надёжные программы из ненадёжных компонентов

2023/12/20 18:45 ••• Автор сайта
О чистоте и нечистоте функций и языков