Функциональное программирование
ВведениеПредставляю вниманию заинтересованных читателей несколько статей на тему функционального программирования. Они, наверное, имеют своей целью способствовать не столько образованию читателей, сколько самообразованию писателя :) Есть отличный способ что-то изучить или понять — рассказать об этом другому. Это будут записки в жанре «мысли вслух». Если получится излагать просто, значит тема понята. Ведь простота — это косвенный признак понимания. Постараюсь здесь поднять и, по мере своих способностей, осветить те вопросы из функциональной парадигмы, которые умалчиваются, не афишируются или недостаточно чётко и ясно описаны в популярной прессе. Попытаемся побороться с недосказанностью и двусмысленностью. Функциональное программирование — это мир чистых (в математическом смысле) функций, которые выдают один и тот же результат при одних и тех аргументах. Эти функции можно выполнять в любом порядке или вообще не выполнять, их можно выполнять параллельно на множестве процессоров. Эта парадигма программирования избегает изменяемых состояний. Она обладает целым рядом положительных черт. Оптимисты увидят в ней «серебряную пулю», пессимисты напомнят, что таких пуль было уже немало и серебро в них оказалось поддельным. А реалисты попытаются извлечь из него преимущества, взять из него всё выгодное. Объединить всё лучшее из разных миров: из функциональной, императивной и других парадигм. Так же прошу читателей иметь в виду, что говоря о функциональном программировании, «по умолчанию» буду иметь в виду язык Haskell. Хотя некоторые его черты можно встретить и в других языках ФП. Сильные стороны функционального программированияЧем меньше число состояний, в которых может оказаться программа, тем она проще. А функциональное программирование как раз и направлено на программирование без состояний. Одинаковость результата для одинаковых входных параметров — тоже замечательное свойство. Как следствие, такие функции легко тестировать и отлаживать. Ещё одно следствие — возможность распараллеливания вычислений. Последнее актуально, потому что микроэлектроника постепенно заходит в теоретический тупик: нельзя сделать логический вентиль микросхемы размерами меньше, чем атом. Рост тактовой частоты тоже имеет теоретический предел. И выход видится в увеличении числа процессоров, одновременно выполняющих вычисления. А чистые функции, у которых всегда однозначное соответствие между входными параметрами и результатом, отлично подходят для распараллеливания. Ещё одно преимущество функционального программирования — оно наилучшим образом подходит для доказательного программирования. Императивные программы слишком сложны для этого. В них имеется множество состояний. В императивных же языках результат функций часто зависит не только от входных аргументов. С чистыми функциями всё проще. Недостатки ФП и их причиныНиклаус Вирт: Постулирование модели вычислений без состояний поверх машины, наиболее значительной характеристикой которой является состояние, кажется, по крайней мере, странной идеей. Между моделью и машиной существует широкая пропасть, возведение моста через которую обходится дорого. Это невозможно исправить с помощью какой-либо аппаратной поддержки: идея остается плохой и на практике.
А теперь поподробнее. Низкая производительностьФилип Уодлер, один из создателей Haskell, считает, что низкая эффективность уже не может быть причиной неиспользования языков ФП. Он пишет, что в наши дни эффективность функциональных языков часто соперничает с С... [она] может быть ... ниже С... Но как грубое приближение в пределах множителя двух от С она кажется справедливой. Португальские исследователи не разделяют его оптимизм. Они взяли 27 языков программирования и сравнили их эффективность. Ниже приведена выжимка из полученных результатов.
Здесь видна цена моста над пропастью, о которых говорил Вирт. Усреднённые данные тестов говорят о том, что Haskell проигрывает в эффективности C от 2.45 до 3.55 раз. Эти цифры опровергают Уодлера. Почему Haskell так проигрывает C? Они же «одного поля ягоды» — статически типизированные компилируемые языки.
Однако, надо заметить, что разница между Haskell и C не такая уж и катастрофичная. Но это в тестах португальцев. Легко подобрать такой тест, в котором Haskell будет хуже на несколько порядков. Результаты же Python в приведённой выше таблице на порядок хуже Haskell. Но и это не катастрофа, раз Python так популярен. Просто Haskell отпадает, как инструмент системного программирования и в задачах, где скорость и эффективность критична. Ну и вряд ли стоит использовать Haskell в задачах, приводящим к постоянному копированию больших объёмов данных. Для остальных применений некоторая его неторопливость большим препятствием не будет. Хотя опять-таки важно учитывать класс задач. Ведь нельзя утверждать, что соотношение эффективности Haskell и Си стабильно и равно, допустим, трём. Отнюдь. Надо обращать внимание на класс задач, где проигрыш Haskell особенно велик.
Ниши и области оправданного применения ФПНадо признать, что многие программисты признают ограниченность сфер применения функционального программирования вообще и Хаскелла в частности. Встречались такие признания: «Использовать Хаскелл как числодробилку — не лучшая идея». Или: «Зачем применять Хаскелл там, где много мутабельных данных? Вы сами должны понимать, что Хаскелл не для этого».
Функциональное программирование делает упор на иммутабельность данных. Это не всегда находит понимание у программистов-практиков. «Разве есть такой такие классы задач, в которых обеспечивается неизменность данных?! Какую задачу не возьми, везде объекты меняются с течением времени!». Но если не горячиться, то такие классы задач найти можно. Вот что приходит на ум:
Наверняка это далеко не полный перечень. Есть немало задач, которым присуща иммутабельность. Опубликовано: 2022.03.16, последняя правка: 2022.06.07 20:25
Отзывы
Использование функциональной парадигмы даёт некоторые преимущества, например, повышение надёжности ПО. Чем больше функциональщины, тем меньше места алгоритмам.
Использование же функциональной парадигмы даёт некоторые преимущества, например, повышение надёжности ПО. Есть такая разновидность веры. Но подтверждается ли она практикой?Чем больше функциональщины, тем меньше места алгоритмам. А это уже просто неправда. Понятие алгоритма верно как для императивной, так и для любой другой парадигмы, в том числе и функциональной.
Есть такая разновидность веры. Но подтверждается ли она практикой? Функциональное программирование стимулирует написание кода, не имеющего состояния. Уменьшение числа состояний в программе уменьшает её сложность, улучшает возможности её отладки. Применение чистых функций делает возможным некоторые виды оптимизаций. Это не обязательно воспринимать на веру, это имеет рациональные доказательства.Насчёт «веры» и её разновидностей. Хорошо бы, чтобы программисты не становились сектантами, обращёнными в какую-то «веру», и слышали аргументы извне. Чтобы не было сект Форта, «Дракона», Оберона. Чтобы не делали из того же Оберона культ, где «Отче наш» — «Арифметика синтаксиса», где поют осанну «O santa simplicitas». Надеюсь, функциональное программирование тоже не станет культом. Тем более, что Haskell и прочие — гибридные языки (а не чисто функциональные, чтобы там не рекламировали!), раз без императивщины не могут обойтись. Понятие алгоритма верно как для императивной, так и для любой другой парадигмы, в том числе и функциональной. map() и reduce() во многих языках применяет к элементам контейнера какую-то функцию. В императивных же языках это делается в цикле. Цикл — это последовательность операторов, которая имеет ветвления, это можно наблюдать на блок-схемах. map() и reduce() на блок-схеме — это прямоугольники один под другим, не имеющие ветвлений. Таким образом, эти элементы функционального программирования делают блок-схему одномерной. Блок-схема деградирует вплоть до вырожденного состояния — без единого ветвления, с единственным маршрутом. Формально это можно продолжать называть алгоритмом и блок-схемой, а по факту такая блок-схема никому не нужна. Тот же SELECT в SQL — какие ветки в блок-схеме он образует?А вот как реализованы map(), reduce() и SELECT — это уже детали. Возможно, «под капотом» — это циклический последовательный процесс, а может и параллельный — раскиданный на разные процессоры.
Функциональное программирование стимулирует написание кода, не имеющего состояния. Уменьшение числа состояний в программе уменьшает её сложность Это утверждение было бы верно, если бы состояние было бы единственным аргументом некой функции сложности, но это не так. Естественно, меня интересуют не подобные логически некорректные рассуждения, а в первую очередь, практические сравнения. Наподобие «использовали функциональное программирование -> написали программу в R раз быстрей при прочих равных».Формально это можно продолжать называть алгоритмом и блок-схемой Каким образом вы свалили в одну кучу алгоритм и блок-схему? Понятие «алгоритм» не привязано ни к императивному программированию, ни к блок-схемам. Вы давали совет Попову: «Поинтересуйтесь на досуге». Это был хороший совет.Надеюсь, функциональное программирование тоже не станет культом. Если Вы на это только надеетесь, то у меня есть плохие новости.
Это утверждение было бы верно, если бы состояние было бы единственным аргументом некой функции сложности, но это не так. Если представить программу в виде ориентирированного графа, то вершины этого графа — это состояния, а рёбра — функции перехода из одного состояния в другое. Между сложностью программы и размером этого графа есть не прямая, но тесная связь. Любой инженер, изучавший теорию надёжности систем, скажет Вам, что при одинаковой надёжности элементов система с меньшим количеством элементов надёжнее.использовали функциональное программирование -> написали программу в R раз быстрей при прочих равных Я говорил не о скорости, а о надёжности. Но поскольку я и мои коллеги не могут подкрепить или опровергнуть утверждение о надёжности цифрами (впрочем, как и Вы), то остаётся дождаться, что кто-то когда-то соберёт статистику.Каким образом вы свалили в одну кучу алгоритм и блок-схему? Там не куча, а некоторая взаимосвязь. Алгоритм [существующий в голове] не подразумевает существование [нарисованной] блок-схемы. А вот [нарисованная] блок-схема подразумевает существование алгоритма [в голове]. А ещё алгоритм можно изобразить ориентированным графом, для этого пригодятся Р-схемы — изобретение Вельбицкого, советского программиста из Киева. Представьте себе такой граф алгоритма, где начальную вершину и конечную соединяет один-единственный маршрут. Простая схема, от которой легко добиться надёжности. Функциональное программирование местами помогает с одномаршрутными графами.«Поинтересуйтесь на досуге». Это был хороший совет. Ну хоть одна хорошая оценка. Кстати, Вы интересовались оптимизациями, в которых помогают чистые функции? Об этом говорилось чуть выше. Представьте себе такое: Вы описали в программе функцию, а потом вызвали с входными параметрами, и все параметры — константы. Вопрос: «Вы можете выполнить эту функцию на этапе компиляции, подставив константы? Чтобы вызов функции заменить другой константой — результатом работы этой функции?». Примерно так: вместо sin(π/6) подставить ½. Ответ очевиден: «Нет, потому что функция может оказаться недетерминированной или производящей побочный эффект. Такие функции нельзя выполнять на этапе компиляции». Тогда следующий вопрос: «А если эта функция гарантированно чистая?». Ответ: «Тогда можно».Языки типа Си или Оберона не могут гарантировать чистоту функции. А вот язык D может, там есть для этого ключевое слово «pure». А в Haskell функции и так по умолчанию чистые. А может ли Оберон обзавестись ключевым словом «pure»? Нет, там взят курс на максимально компактный язык, на минимальное количество правил в языке. А зря, ведь чистые функции имеют и другие замечательные свойства, о которых Вы, думаю, уже читали. Если Вы на это только надеетесь, то у меня есть плохие новости. Ничего страшного. Достаточно просто иметь холодную голову и оставаться прагматиком.
Любой инженер, изучавший теорию надёжности систем, скажет Вам Любой человек, знакомый с многопараметрическими зависимостями Вам скажет, что оценивать функцию по одному параметру некорректно. То есть Вы можете предполагать об уменьшении одного из параметров и не замечать увеличение другого. Всё ещё сложней, когда речь идёт о сложно формализуемой функции, такой как надёжность. Также любой человек, знакомый с понятием алгоритмической полноты Вам скажет, что о программе на алгоритмически полном языке вообще сложно утверждать о наличии или отсутствии чего либо. Более того, на самом базовом уровне функциональная и императивные парадигмы — это вопрос интерпретации.Я говорил не о скорости, а о надёжности. Пожалуйста, используйте логику. Высокая надёжность доступна на любом языке. Для того же печально известного Си наработаны на практике(!) методы получения программ высокой надёжности. Вопрос лишь в ресурсах, которые нужно потратить для достижения этого уровня. Поэтому бессмысленно говорить о достижении надёжности благодаря выбору языка, а имеет смысл говорить о достижении той же самой надёжности за меньшее время, или о достижении большей надёжности за тоже самое время.Там не куча, а некоторая взаимосвязь. Это опять не то. Я веду речь о том, что Вы ошибочно противопоставляете код в функциональной парадигме алгоритмам. В то время, как алгоритм не привязан к понятию императивной парадигмы, и алгоритм в функциональной символике всё равно будет алгоритмом.Ну хоть одна хорошая оценка. Совет был хорошим, но он не будет таким до конца, если не будет пропущен через себя.Кстати, Вы интересовались оптимизациями, в которых помогают чистые функции Напомните, пожалуйста, где я интересовался.Ничего страшного. Достаточно просто иметь холодную голову и оставаться прагматиком. Недостаточно думать о том, что голова холодная.
Вы ошибочно противопоставляете код в функциональной парадигме алгоритмам Всё правильно, f(g(h(x))) — это алгоритм. y=h(x); z=g(y); w=f(z) — это тоже алгоритм. Я так выше и написал:Формально это можно продолжать называть алгоритмом Пусть даже и вырожденный до графа, между начальной и конечной вершинами которого — единственный маршрут. Даже попробую угадать: Вам наверняка нравится рисовать блок-схемы для f(g(h(x))).Напомните, где интересовался Вы, цитируя, забыли поставить знак вопроса: не «Вы интересовались», а «Вы интересовались?». Т.е. это не утверждение, а вопрос. Просто выше рекомендовал Вам поинтересоваться, а потом уточнил, знакомились ли Вы с рекомендованным. Но Вы, видимо, не хотели поднимать тему чистых функций. Где выгода от функционального программирования видна, но признавать этого Вам не хочется. Наверно потому, что тут поспорить не получается.А насчёт надёжности — тут можно и поспорить. Ведь объективных, общепризнанных результатов исследований на эту тему не существует. Давайте закруглимся с бесполезным спором и не будем отнимать время друг у друга.
Ну да, если система уменьшила число размерностей с n до n-1 Про размерности- это метафора, а не суть. Поэтому ирония неуместна.Формально это можно продолжать называть алгоритмом Круг замкнулся, Вы снова противопоставляете их. В том то и дело, что не формально, а фактически. Не привязано понятие алгоритма ни к блок-схемам, ни к графам. Вы так и не воспользовались собственным советом.Даже попробую угадать: Вам наверняка нравится рисовать блок-схемы для f(g(h(x))) Снова юмор. Я никогда не рисую блок-схем, даже в голове. Алгоритм — он алгоритм хоть на Java, хоть на Haskell.это не утверждение, а вопрос. Просто выше рекомендовал Вам поинтересоваться Спасибо за рекомендацию. Я знаком с чистыми функциями и использую их на практике даже в Си. Я много ещё с чем знаком, но ещё больше с чем не знаком, конечно. Пожалуйста, не делайте рекомендаций на основании Ваших предположений, о незнании собеседника. Похоже, что из моего сомнения об априорном или основанном на метафорах повышении надёжности от использования функционального программирования, Вы сделали вывод, что я вообще отрицаю пользу вещей, которые ассоциируют с функциональной парадигмой. Хотя мне известно, что начиная с Фортрана, большинство «императивных» языков содержат в себе элементы функциональной парадигмы.Давайте закруглимся с бесполезным спором и не будем отнимать время друг у друга. Каждому — своё. Я спорю ради установления истины. Думаю, Вы тоже. Жаль, что насчёт моих мотивов Вы делаете неуместные предположения. Я указал на фактическую ошибку. В ошибках нет ничего предосудительного, и исправление их — это не желание бесмыссленно поспорить или посамоутверждаться, а желание улучшить интересный ресурс. Если не находиться в плену бессмысленных иллюзий и оставлять голову действительно холодной, то будет больше шансов, что из этого получится что-то хорошее.
ирония неуместна... Круг замкнулся А что уместно, когда замкнулся круг? Именно ирония уместнее всего!не формально, а фактически Когда Вы потратили последний рубль, то фактически у Вас нет денег. А формально они есть, только их количество равно нулю. Когда алгоритм можно представить маршрутом без ветвлений, то формально алгоритм есть и могут существовать его изобразительные инкарнации в виде блок-схемы или ориентированного графа. А по факту эти материальные воплощения алгоритма никому не нужны.Не привязано понятие алгоритма ни к блок-схемам, ни к графам Бог никак не привязана к иконам. Но иконы с изображением бога к нему всё-таки привязаны. Икона — это материальное воплощение наших мыслей о вечном. А блок-схема — это воплощение мыслей об алгоритме.Алгоритм — он алгоритм хоть на Java, хоть на Haskell О! Если я Вас правильно понял, то Вы придерживаетесь мысли, что алгоритм — он и в Африке алгоритм, един и одинаков? Хоть он на Java, хоть на Haskell, хоть на ассемблере реализованный? Хоть для 8-битных процессоров, хоть для 64-битных? Что для процессоров с аппаратной реализацией плавающей арифметики, хоть для платформ с отсутствием оной? Что для современных процессоров, что для процессоров IBM/360, где отсутствовала аппаратная поддержка стека? Что при выполнении оператора «SELECT» в SQL, что при выполнении аналогичной задачи на ассемблере?Я спорю ради установления истины Ну если Вы так любите истину, то почему не признали, что чистые функции делают возможными оптимизации, которые невозможны в языках без этих функций?А вообще-то все религиозные войны имели своей целью оказать помощь в установлении истины. Давайте просто пожмём друг другу руки и разойдёмся. не желание бесмыссленно поспорить или посамоутверждаться, а желание улучшить интересный ресурс Спасибо, что Вы заставили меня пошерстить Интернет в поисках определения алгоритма. Правда, разноголосица там не меньше, чем у нас с Вами. Спасибо, что подтолкнули изложить то, что давно сидело в голове (пример с синусом).
О! Если я Вас правильно понял, то Вы придерживаетесь мысли, что алгоритм — он и в Африке алгоритм, един и одинаков? Хоть он на Java, хоть на Haskell, хоть на ассемблере реализованный? Нет. Понятие «алгоритм» одинаково для всех языков в соответствии со смыслом слова «понятие». Конкретный же алгоритм привязан к языку исполнителя и потому не может быть абсолютно одинаковым для исполнителей с языками, не содержащих достаточного общего подмножества. При этом могут быть эквивалентные алгоритмы и возможен перевод алгоритма на языке одного исполнителя в эквивалентный алгоритм на языке другого исполнителя.Ну если Вы так любите истину, то почему не признали, что чистые функции делают возможными оптимизации, которые невозможны в языках без этих функций? Не в полной мере понимаю, о чём Вы. Конкретно я применяю чистые функции в Си для оптимизаций. Примеры Вы можете найти в документации gcc и в трансляторе, ссылку на который я приводил.А вообще-то все религиозные войны имели своей целью оказать помощь в установлении истины. Давайте просто пожмём друг другу руки и разойдёмся. Не хочется ввязываться в дискуссию ещё и по этому вопросу, но насколько я могу судить, в религиозных войнах основой служили экономические противоречия. Религия в них была обслуживающим персоналом, и без неё бы тоже обошлись, если бы её не было.В любом случае, жму руку.
чистые функции делают возможными оптимизации, которые невозможны в языках без этих функций Они возможны, просто алгоритмы для получения аналогичного конечного результата оптимизации требуются другие. Будь иначе — языки не были бы полными в принципе. В этом смысле ФП — это не автоматизированная, а ручная оптимизация.
Comdiv Не в полной мере понимаю, о чём Вы. Конкретно я применяю чистые функции в Си для оптимизаций. Теперь представим, что Вы написали определение функции «fun(int, int)», а потом вызвали её с константными аргументами: «fun(2, 10)». Вопрос: мы можем вычислить эту функцию прямо во время компиляции? Допустим, у нас есть встроенный в компилятор интерпретатор. Он может вычислить константное выражение и вместо него в выходной код подставить одну-единственную константу? Нет, потому что «fun(int, int)» может оказаться «грязной». Если у вас в языке нет чистых функций, то и гарантий чистоты тоже нет. Почему? Потому чистоту функций нельзя определить по косвенным признакам. Даже если мы выясним чистоту вложенных функций, то не может вычислить чистоту функций, переданных по указателю. Указатель делает функции анонимками, надевшими маски на бале-маскараде. Явное же определение чистоты функции (хоть с помощью ключевого слова, хоть по умолчанию) распространяется и на указатели на функции. Поэтому если чистота «fun(int, int)» гарантируется средствами языка, то и в исполняемом коде вызов «fun(2, 10)» можно заменить на константу. А вот ещё одно применение чистым функциям. В языке D применяется контрактное программирование, когда на входе в функцию проверяются входные параметры, и на выходе тоже. Цель ясна — надёжность программы, ловля багов. Но потом, когда программа отлажена, качество её отменно, то проверку контрактов можно отменить (для повышения скорости работы) опцией при компиляции. Но — при условии, что проверка контрактов делается чистыми функциями. Потому взять и отключить функции с побочными эффектами — это нарушить логику программы.
Вы написали определение функции «fun(int, int)», а потом вызвали её с константными аргументами: «fun(2, 10)». Вопрос: мы можем вычислить эту функцию прямо во время компиляции? ... Нет, потому что «fun(int, int)» может оказаться «грязной» Поэкспериментируйте с gcc, почитайте документацию по опциям и атрибутам. Возможно, результат Вас удивит. Если будет интересно, можете ещё поэкспериментировать с суперкомпилятором Java, который, правда так и остался на уровне прототипа. Да и это уже совсем другая история.
почитайте Почитаю. Неплохо б сразу ссылку на документацию. А что, в C++ чистые функции появились?
Потому чистоту функций нельзя определить по косвенным признакам Можно. Даже с передачей указателей вычисление чистоты или нечистоты функции во многих случаях допустимо. Утверждение о невозможности просто абсурдно. Если в стандарте конретного языка и в реализации его компилятора этого нет, это никоим образом не значит, что этого принципиально нельзя сделать в таких случаях. Вот эта функция, например, чистая:int f(int a,int b){return a+b;}и если в ней заменить передачу значений ссылками или указателями с последующим разыменованием вручную — функция останется чистой. У Вас, скорее всего, путаница между фактической чистотой функции и передачей информации о чистоте через синтаксис в целях упрощения алгоритмов.А что, в C++ чистые функции появились? У Вас не отделено понятие чистоты функции от средств их поддержки. Представьте, что можно написать комплиятор, который вообще не оптимизирует даже 2+2. Меняется ли синтаксис языка? Нет. Меняется ли семантика? Что вообще говорит стандарт языка про оптимизации? А он может что-то говорит, а может — не говорить. Зависит ли от этого возможность оптимизации 2+2? Нет, если язык говорит, что эти константы нельзя менять во время работы программы.
У Вас, скорее всего, путаница между фактической чистотой функции и передачей информации о чистоте через синтаксис в целях упрощения алгоритмов. Да, я имею в виду чистоту, закреплённую через синтаксис и гарантированную синтаксисом. В противном случае эту чистоту приходится определять.
Применение чистых функций делает возможным некоторые виды оптимизаций. Это не обязательно воспринимать на веру, это имеет рациональные доказательства. Рекомендую статью 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) {Эта функция чистая? Чистая, если g(x) чистая и никогда не возвращает число 32. Но вот определить, возвращает ли функция g(x) число 32 — в общем случае алгоритмически неразрешимая задача.Но никто не мешает разрабатывать алгоритмы приближённой разметки чистых функций, имеющие разную степень точности. Вообще, если в теории задача алгоритмически неразрешима, на практике это означает, что задачу можно решить приближённо разными способами. Эти способы будут отличаться по точности, сложности реализации, скорости работы и т.д.
Про исследования побочного эффекта в суперкомпиляции я ничего не знаю А для Java http://supercompilers.ru/ не считается? Правда, в ограниченном виде, но чем не исследование?Ну и на базовом уровне чистота функции — это вопрос трактовки, любой императивный язык можно формализовать как 100% чистый функциональный язык. В этом смысле ограничение на чистоту функций не является ни необходимым, ни достаточным.
Теория суперкомпиляции описана только для чистых функциональных программ. Про исследования побочного эффекта в суперкомпиляции я ничего не знаю. А для Java http://supercompilers.ru/ не считается? Правда, в ограниченном виде, но чем не исследование? Суперкомпилятор для Java я внимательно не изучал, поэтому не знаю детали его работы.В принципе, если метод на Java выполняет (прямо или косвенно) присваивания только локальным переменным (и не вызывает нечистых методов), то его можно преобразовать в один или несколько чистых методов — методов, в тексте которых нет оператора присваивания. Модификацию состояния можно имитировать при помощи уникальных типов: Тип, гарантирующий уникальность. Кстати, к этой статье приложил руку Автор сайта. Как осуществляется поддержка нечистых функций в суперкомпиляторе Java — понятия не имею. Однако, не исключаю, что никак. Ну и на базовом уровне чистота функции — это вопрос трактовки, любой императивный язык можно формализовать как 100% чистый функциональный язык. Не очень понял. Раскройте мысль, пожалуйста.
чистота функции — это вопрос трактовки Т.е. всё зависит от трактовки, кто как её понимает? Как у юристов: «Там где есть два юриста, там существуют три мнения».любой императивный язык можно формализовать как 100% чистый функциональный язык. Не могли бы подробнее изложить свои мысли? Вас можно понять так, что исходник на Си, к примеру, можно по определённому алгоритму переписать на Хаскелле. Я, допустим, могу написать на Си обработчик прерываний и поместить адрес этой функции по абсолютному адресу. Но как такое написать на Хаскелле?В этом смысле ограничение на чистоту функций не является ни необходимым, ни достаточным. В языке D есть функции с ключевым словом pure, которое запрещает внутри этой функции грязные функции, что гарантирует чистоту функции. И это всё зря? Это не является достаточным для чистоты функции? И что ещё необходимо, помимо чистоты вызываемых функций?уникальных типов «Уникальный тип» — это калька с английского, передающая смысл не точно. Перед тем, как определиться с «типом, гарантирующим уникальность», я советовался. В частности, небезысвестный Роман Душкин согласился именно с такой формулировкой, как наиболее полно описывающей суть термина.
Раскройте мысль, пожалуйста. А что раскрывать, если Вы и так всё знаете? Если бы Вам пришлось доказывать полноту по Тьюрингу чистого функционального языка, как бы Вы это сделали? Что бы это Вам сказало об императивной машине Тьюринга с функциональной точки зрения?Если удобней размышлять о типах, гарантирующих уникальность, то представьте себе состояние императивного вычислителя как переменную с гарантированной уникальностью, а машинные инструкции — функциями, оперирующими переменными такого типа. Получается?
Стихи от Лидии Васильевны Городней о функциональном программировании В компьютере всё — данные Символьные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
Парадигма — это Задачи и приоритеты, Языки и системы, Примеры программ и схемы Такой реализации понятий, Что стиль мышления понятен. Парадигмы возникают, Когда чего-то не хватает. Сначала были просто вычисления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 Логическое программирование Написать автору можно на электронную почту |
2018/12/01 09:12, Автор сайта