Как стать автором
Обновить

Практическое функциональное программирование

Время на прочтение 8 мин
Количество просмотров 7.3K
Всего голосов 17: ↑14 и ↓3 +11
Комментарии 30

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

Очень странная история, и это в 1977 году! А в 71-ом там же был Маккарти, цитирую энциклопедию:


Джон Маккарти — американский информатик, автор термина «искусственный интеллект» (1956), изобретатель языка Лисп (1958), основоположник функционального программирования, лауреат премии Тьюринга (1971) за огромный вклад в область исследований искусственного интеллекта.

Похоже, любители монад, приватизируют функциональный подход, а у него длинная история,… может Хаскелу нужна отдельная категория: "языки категорий", "категорианство", "категориальное программирование"?

Lisp — не функциональный язык программирования. Во всех смыслах этого слова.

Конечно, Лисп развивался и в него встроили все, он "мульти". Его основы отобразили "функциональное программирование" по мотивам формализмов Черча, а это лямбды, функции, функторы, замыкания и тд. Удивлен сложившейся однобокостью, как будто теория категорий и вывод типов основы функциональщины, в Лиспе уже все основы были и в Эрланге они же...

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

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

Лисп ровесник Фортрана, но суть у них разная, Фортран — машина Тьюринга, с инструкциями и данными на бесконечной ленте, а Лисп использует абстракции Черча, на которых он желал построить основы всего математики. Лисп демонстрирует принцип "единства представления" — вычисления и данные имеют одинаковую форму записи: символы и списки.
Ленивость — о том, что функции могут не "вычислять" возвращаемый результат, а возвращать функцию, которая "потом вычислит" результат. Такое и в современном С++ можно, странно, а где статьи про библиотеки с "революционными ленивыми" списками для С++25 ))
А замечание мое такое — когда декларативность, в частности функциональное представление, преподносят демонстрацией Хаскела, то только отпугивают и запутывают заинтересовавшихся, а его мощь "категориальности", контроля типов или ленивости можно бы называть отдельным определением, для ясности. А функциональщина без лишних "заморочек" присутствует в Эрланге.

Лисп демонстрирует принцип «единства представления» — вычисления и данные имеют одинаковую форму записи: символы и списки.
Это, может быть, и было первоначальной идеей, но современный диалекты — имеют весьма нетривиальный синтаксис. Всех эти quotes, pseudoquotes и прочее.

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

А замечание мое такое — когда декларативность, в частности функциональное представление, преподносят демонстрацией Хаскела, то только отпугивают и запутывают заинтересовавшихся, а его мощь «категориальности», контроля типов или ленивости можно бы называть отдельным определением, для ясности.
Ну это всё равно как отделить BASIC (оригинальный, не Visual Basic) с его двухбуквенными глобальными переменными отдельно, а все остальные языки — отдельно. Можно, да… но зачем?

Только про ясность, про восприятие, если язык следует Тьюрингу, то в нем инструкции и лента память, а если Черчу, то композиция функций, рекурсия…
Повторяюсь, наблюдаю за новостями и удивляюсь, как-то часто Хаскел фигурирует как "функциональный", а не "статически типизированный ленивый функциональный язык". В статье https://habr.com/ru/post/505928/ вижу это:


… Лямбда исчисление имеет к ФП такое отношение, как Теория Категорий, т.е. никакое. Просто люди, привнесшие эту концепцию в ФП, были прожжёнными математиками, и дали ей такое название.

это статья "Почему функциональное программирование такое сложное"…


И автор этой заметки не упоминает о старейшем языке, который ровня Фортрану, а зачем то, рядом с функциональный указывает Хаскел… и монады во втором предложении!?.. о-о-о простите за резкость…

И автор этой заметки не упоминает о старейшем языке, который ровня Фортрану, а зачем то, рядом с функциональный указывает Хаскел… и монады во втором предложении!?.. простите за резкость…
Может быть потому что сегодня, когда учат императивному программированию, тоже учат не Фортрану, даже не Коболу или Ассемблеру, но скорее какому-нибудь Питону? И про объекты рассказывают может и не во-втором предложении, но довольно скоро?

Монады имеют примерно такое же отношение к ФП, как объекты к императивному: да, можно без них, вообще всё можно… но зачем?

Сегодня Haskell, так получилось, считается «основным» языком ФП… хотя формально Lisp популярнее. Но он, видимо, не считается модным.

А кроме того, есть проблема: этих Lisp'ов — как грязи, сотни, если не тысячи, диалектов. Часто несовместимых. Все вместе — они популярнее Haskell. Но вот каждый конкретный…

А Haskell, сегодня, де-факто один GHC. Это упрощает первоначальное обучение.

Хотя да, он сложнее, чем Lisp, конечно…

Ой, спасибо, интересная параллель получилась, объекты: монады ))
Объектам как структурам данных нормально быть в императивном, это же развитие Вирта — "Алгоритмы+Структуры данных=....".
Да и Питон демонстрирует функциональные элементы, по-моему, нормально, а вот с классами там странности...

Ой, спасибо, интересная параллель получилась, объекты: монады ))
Именно параллель. Это сущности сильно разной природы, но одного «ментального поля», в некотором роде.

В императивных языках — всё, вот совсем всё, без ислючения всё, можно реализовать без всяких объектов и интерфейсов. Чисто на массивах и простых переменных.

Однако они, тем не менее, вводятся — для удобства. Чтобы в их терминах структурировать код программы.

В функциональных языках — всё, вот совсем всё, без ислючения всё, можно реализовать без всяких монад и аппликативов. Чисто на функциях и их композиции.

Однако они, тем не менее, вводятся — для удобства. Чтобы в их терминах структурировать код программы.

То, что в Haskell, без монад, невозможно ничего ни ввести, не вывести — имеет ту же природу, по которой в java константы E и PI, внезапно, объединены в классе java.lang.Math. Почему так? Ну потому что если их языка изгнать «свободные» переменные и функции, то куда-то же их нужно засунуть… В Java без работы с классами вы даже «hello, world» не напишите…

А если мы говорим, что в языке нельзя создать функцию с сайд-эффектами, то вам нужна хоть одна сущность в которой эти сайд-эффекты можно сконцентрировать. Потому что иначе ваша программа не может ничего изменить в окружающем мире — что как-то несколько… грустно. Ну вот в Haskell — их собрали в монаду IO. Которая передаётся в main — ну и дальше уже расходится по программе.
Однако они, тем не менее, вводятся — для удобства. Чтобы в их терминах структурировать код программы.

… и в 70-х по структурному программированию, предлагалось соблюдать модулям метрику, требование высокая связность, и такой пример называют логическая связность (это Паскалем/Ада/Модула, по памяти))):


module math;
interface:
var: state:.....
function eps():type;
function pi():type;
declaration:
var X....
.

https://ru.wikipedia.org/wiki/Связность_(программирование)


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

Все же, никакие классы, не устранят проблемы группировки функций в модуль, той самой высокой цельности модулей, вот так писать можно(С++/Ява ))):


public class programm{
  ... state;
  public: 
  void draw(io.screen);  
  sometype load_from_http(string);
}

А факты про main(IO) из Хаскел, очень подходят к определению "низкое сцепление" модулей, а именно один ее положительный вид: "сцепление по данным":


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

такие абстракции Хаскела не странны, это соображения из структурного подхода, а "точку входа" в программу настроит и установит окружение/операционная_система/интерпретатор.
Еще в С было, функция printf() использует файл con для вывода, а его можно передавать в программу (чем не ИО):


program >output.txt

Помню, забавная идея из языка CLIPS https://en.wikipedia.org/wiki/CLIPS, и это называли продукционным подходом к вычислениям(и сейчас существуют языки CHR), там правило выполнялось(файер), когда глобальное состояние фактов совпадет с указанным предусловием, а после выполнения правила и изменения глобального состояния будет файер у другого правила… А начинают с единого первого факта (initial-state), плюс синтаксис там лисп-овский. Порядок обхода правил, настраивался снаружи, это опция интерпретатора, текст программы этого не учитывает, система переберет правила "вширину", "вглубину", "приоритетно" или еще как, это не формулировки решаемой задачи, это механизмы "решателя" формулировок. Вот так будет машина Тьюринга:


(defrule step0 (state 0)=>
  (retract (state 0) 
  (some code)
  (assert (state 1))
)
(defrule step1 (state 1)=>
  (retract (state 1) 
  (other code)
  (assert (state 2))
)
.....
(defrule main (initial-fact)=>(assert (state 0)))

Мне как раз показалось, что обсуждения в статье "Почему функциональное программирование такое сложное" и отражают, что основы Хаскел не сколько функциональность, а только детали теории категорий, которая пугающе все абстрагировала…
Лисповская однородность представления позволяла генерировать программу, а потом ее выполнять, чем не ленивость или отложенность выполненя, в список собранные символы запустятся на самом верхнем уровне, пусть так:


(defun main (x y)
  (cons + (list x y))
)
(prog 
   (eval (main 1 2))
) 
основы Хаскел не сколько функциональность, а только детали теории категорий, которая пугающе все абстрагировала…
Не более погающе, чем public static void main(String[] args).

Или вы думаете человека, который первый раз за компьютер сел такое нагромождение непонятных слов не пугает? Пугает конечно. Сам много раз видел.

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

Вот и вся разница.

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

Но если у вас язык, изначально, «неленив», то вы не будете изображать ленивость вручную в каждой строчке.

Ну вот возьмите классическую программку из учебника:
main = do 
       inh <- openFile "input.txt" ReadMode
       outh <- openFile "output.txt" WriteMode
       inpStr <- hGetContents inh
       let result = processData inpStr
       hPutStr outh result
       hClose inh
       hClose outh

processData :: String -> String
processData = map toUpper
Обратите внимание — processData это совершенно обычная, вот тривиальная просто, функция, которая берёт буковки из списка, делает для каждой из них toUpper и возвращает кладёт в другой список.

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

А в Lisp, в этом месте, возникают потоки. И вам приходится придумывать как делить работу на части — причём не в реализации hGetContents, а реализации функции, которая работает с данными.

И всё: иллюзия «чистого», «функционального» мира — рассыпалась в прах.

Можно ли на Lisp писать чисто функциально? Да не вопрос — это можно хоть в машинных кодах делать! Вопрос в том — насколько это удобно.

Так вот «идеоматически правильные» программы на Haskell — как правило — функциональны. «Идеоматически правильные» программы на Lisp — нет. Потому что вам нужно возиться с потоками и со всеми вот этим прочим — в достаточно большой части вашей программы. Фактически везде, где вы не можете быть уверены, что работаете с «небольшими объектами». Которые можете «позволить себе» копировать, условно говоря.

Спасибо, попробую пояснить рассуждения. Функциональное программирование, введенное Маккарти в работе над Лиспом, основано на лямбда-исчислении Черча, абстракции на которой можно строить математическую базу вычислимости как комбинации функций.
Теория категорий занимает место у основ математики, ей можно выражать и вычислимость и лямбда-исчисление, видимо, и логику предикатов — ее мощные абстракции, позволяют складывать программы от типов и описаний зависимостей между ними. Это не комбинирование функций, тут конструирование из особых функциональных объектов, которые можно вычислять, это же не чистота функций, это отсутствие средства конструировать такие объекты. Хаскел называть императивным не начинают, а механизмы линзирования встроили.


И, да, это только "название", это путаница из-за отнесения конструкций из объектов к функциональной парадигме, почему такой стиль не может иметь отдельного термина?


Бэкус из текущей истории, в упомянутой своей статье, размышляет и о Лиспе, и о его чистоте, а еще классифицирует несколько "стилей" функционального программирования: комбинации функций без использования переменных, алгебраическое ФП как у Черча, какие-то формальные ФП и "applicative state transition systems"…


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

Теорию множеств не используют при обучении арифметики или геометрии, а сейчас теория категории стала базой и для множеств, как же так? Почему Хаскелу не стать машинным языком, лисп-процессоры уже бывали)))

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

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

Почему Хаскелу не стать машинным языком, лисп-процессоры уже бывали)))
Для начала ему бы было неплохо стать хотя бы популярным языком, тогда и в железе чего-нибудь можно сделать…
Однако благодаря ленивости — вы можете использовать эту функцию для любого потока данных — в частности для обработки файлов терабайтного размера.
Тут мы очень полагаемся на внутренности hGetContents, где может быть и попытка прочитать целиком, и куча лишних IO операций типа побайтового чтения. Надо ли так делать?

Попробую пояснить, это же демонстрация "ленивости" строка "inpStr <- hGetContents inh" показала, что inpStr это не сами данные, а механизм/"функция обратного вызова"/поток, который предоставит порции данных потом...

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

Ого, это было обсуждение формы записи программ, а такой вопрос из сферы вычислительной сложности… Я не припоминаю средств, может профилирование, для определения "оптимальности" вычислений функции…

Понятно дело, если перестает устраивать скорость выполнения, то профилирование. Просто с декларативным или логическим программированием это тот момент, когда очень легко может оказаться, что код разматывается во что-то, не приспособленное к имеющимся входным данным, и тут уже становится важно «как». Я на это напрыгивал и в прологе, и в sql, и с сишными макросами.
Для hGetContents мы должны верить, что для текущего размера файла будет выбран оптимальный способ чтения.
Нет, не должны. Этим заведует объект, который вы передаёте в hGetContents.

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

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

Соответственно вопрос «как и насколько кастомизируются IO функции» — он вообще неважен. Если они недостаточно хорошо кастомизируются для ваших нужд (например вы хотите использовать не буфер, а mmap) то вы просто-напросто создаёте ещё один генератор — который можно использовать с любой «чистой» функцией так же, как hGetContents.

В случае же с языками типа Lisp или Python — вы должны создавать и использовать (там где это нужно и полезно) генераторы явно. Вот через все эти yield и прочее.

Это, в принципе, работает, но, в некотором смысле, «переворачивает» подход…
Надо ли так делать?
Знаете — это вопрос очень философский. Где-то совсем рядом со смыслом жизни.

Двавайте я ещё раз напомню: это — пример из учебника. Глава 7я, посвящённая вводу-выводу, даже не какое-то там приложение «для особо крутых».

Так что в каком-то глубоко философском смысле, может быть, вам так делать и не нужно — но тогда вам и писать на Haskell, скорее всего, не очень нужно.

Ибо там такие вещи — как раз составляют основу языка. И да, hGetContents ровно-таки и предназначен для того, чтобы его вот именно так и использовали.
Хотя да, он сложнее, чем Lisp, конечно…

Возражаю, Haskell проще, чем Lisp.

О, если сложностью называть количество исходных абстракций, то надо сосчитать где их меньше…
Не проверил, но популярность Common лиспа точно все еще высока, поэтому и вспоминаю про него, раз тут возникает Фортран, да, ладно…
Преимущества Хаскел не могу отрицать, выражаю только недовольство его "ярлыком", странное ощущение складывается, а не какой-то ли тут план, не направленное ли переиначивание взглядов…
Доступный Эрланг без Фейсбука растерял популярность, чем плохо на нем демонстрировать подходы? Ага, это все про модность.

Маленькое замечание: в русскоязычной литературе фамилию создателя языка Фортран принято писать "Бэкус", а не "Бакус".

Как-то пропущен момент с оригинальным duplicate. Судя по всему синатура была String duplicate(String message). Как оно скомпилировалось если новая firstWord стала возвращать Optional? Или Optional какой-то магический дженерик, при виде которого в качестве параметра, компилятор декорирует функцию проверкой на empty? Почему бы тогда не декорировать так проверкой на null?

Написано же:


firstWord(input).map(this::duplicate)

Упустил как-то при чтении с телефона… Спасибо

Суровым императивщикам порекомендую книгу Ивана Чукича, которая вышла недавно: Функциональное программирование на С++.
Более понятного для императивщика изложения я нигде не читал.
И там есть все: и чистые функции, и каррирование, и ленивые вычисления, и монады.
Написана блестяще!
Зарегистрируйтесь на Хабре , чтобы оставить комментарий