Это, действительно, было бы очень полезно и для практики и для участия в холиварах с пруфами :)
Вопрос не по теме. Присмотрел для перевода материал по freer monad, но сижу, чешу в затылке, как корректно перевести на русский freer: "ёщё более свободные", "освобождённые"… есть ли устоявшийся термин?
Так вышло, но детерминистическая генерация псевдо-случайных чисел тоже функциональна по своей природе. Недетерминизм возникает лишь на входе в цепочку генератора, а это может быть точкой входа в функциональную программу.
Для RosettaCode я писал "Змейку" на Haskell. И там генерация случайного расположения "еды" для змеи вся прячется в одной полиморфной функции в рамках MonadRandom, так как будто бы генератор у нас есть и он возьмёт затравку, когда понадобится, но нам пока не важно откуда. При этом код выглядит так, будто бы в мире змейки уже существуют все будущие координаты в которых еда "случайно" появится (как в беременной самке тли хранятся уже беременные самки и т.д.), это следствие ленивости.
Когда же, наконец, мы в точке входа в программу (функция main) инициализируем змейкин мир, тогда в качестве экземпляра MonadRandom оказывается IO (без неё-то всё равно никак) и вот ни пользователь, ни змейка уже "не знают" где появится очередной фрукт.
Это может показаться трюкачеством, но по-существу вся программа говорит только о том, что делать змейке, получившей сигнал от пользователя или при встрече с едой, и не более. Откуда возьмутся еда и сигналы пользователя, змейке знать не обязательно, об этом заботится только функция main, которая отправляет её в "реальный мир", либо в его детерминистическую эмуляцию (монаду ST) для отладки.
Этот пример не призван показать превосходство ФП перед императивным программированием. Он про то, что многие как кажется чисто императивные задачи гладко ложатся на функциональную парадигму, не требуя лишних шаманств и костылей (если не считать костылями то, что не понимаешь с первого раза).
Боюсь, что разочарую вас. Я имел в виду принципиальную возможность двигаться в этом направлении, если оставаться в рамках ФП. Пока же выкладки приходится делать "на бумажке". Но! Это возможно сделать. Я игрался с формальной верификацией некоего подмножества Java (практически, процедурным подмножеством, не выходящем за пределы Оберона) через триады Хоара. Очень быстро система неравенств становится неподъёмной, по моим ощущениям, экспоненциально. Инварианты циклов приходится писать самому, а это искусство и шаманство. После этого, возвращаясь к типам и индукции в ФП, с доказуемыми свойствами алгебраических структур, понимаешь, какой это кайф: надеть, наконец лыжи после того, как брел по пояс в мокром снегу. Но и лыжи пока приходится переставлять самому. Впрочем, пока ждем завтипов в Хаскеле, можно упражняться, отрабатывая технику на том что есть. Понятно же, что для того, чтобы написать грамотную рабочую спецификацию для автоматического верификатора, потребуется нехилая квалификация программиста. Но пока, насколько я вижу, именно ФП ведёт нас к возможности по-настоящему взлететь.
Запросто! Это как в задаче интегрирования. Есть алгебраический подход, а есть геометрический, есть спектральный, а есть аналитический по теореме Коши, наконец, можно численно, но и там, можно Симпсоном, можно Гауссом. Когда как удобнее. Полезно владеть всем.
Это не переменные, поскольку они не могут измениться, оставаясь в рамках процесса, описываемого функцией. Изменения происходят только на входе-выходе. Одно из отличий, в частности, состоит в том, что, в функциональном коде нет понятия времени и изменение наших "переменных" происходит одновременно: a,b = b,a+b, эквивалентное последовательности присвоений с буфером с = b; b = a+b; a = c.
Это не лучше и не хуже нормальных переменных, просто если проще описать вычислительный процесс итеративным, ФП этому не сильно помешает.
А вот тут в дело вступает то обстоятельство, что задача трансляции (компиляции) по природе своей функциональна. Объектный код полностью определяется исходным кодом и текущим окружением (входными параметрами). На этом стоит вся система сборки дистрибутивов типа configure >> make. Так что если абстракция функциональности и теряется на каком-то уровне, то это происходит всегда одинаково и решение можно, в конце концов, верифицировать, добившись герметичности абстракции на верхнем уровне. GHC это уже умеет. То есть, нас, действительно могут не сильно интересовать детали реализации, покуда компилятор не нарушает некоторых нужных нам законов и инвариантов.
Самое главное — эти проверки и доказательства возможны, причём уже сейчас, так что глупо этим не пользоваться и спорить. Что подтверждает тезис, обозначенный в названии статьи.
Функциональному подходу нет необходимости заполнять всё вокруг. Оно тяготеет к маленьким самодостаточным ортогональным блокам и если в императивной архитектуре такие блоки использовать, то они не помешают. В Фотране (куда уж императивнее!) с 80-х годов есть модификатор pure, указывающий и программисту и компилятору, что определяемая функция чистая, что позволяет им делать определённые выводы как о коде функции, так и о коде, ее использующем.
Операционную систему не сделать чистой по определению, но с некоторыми задачами ФП справляется отлично. Например, на моём ноутбуке, а также на домашнем и на рабочем десктопах стоит NixOS (Linux-дистрибутив построенный вокруг функционального ленивого (а значит, чистого) пакетного менеджера Nix), c оконным менеджером XMonad. И мне нужна их декларативность при настройке и переносе решений с машины на машину. Но это не позволяет мне говорить, что ФП решает все проблемы. Но оно очень неплохо встраивается в императивные решения, поскольку предлагает… чистые функции :)
Ну, и во многих областях это оправдано. Так появилась поддержка длинных целых и рациональных чисел с одной стороны, и всё более мощные символьные движки в повседневных задачах. Так что не зря упирались теоретики!
Про вилку и ложку — это хорошо! А ведь есть ещё палочки и ножи всякие… Споры о том "что круче" парадоксальны в своей бесполезности. Ответ очевиден — лучше научиться владеть всеми приборами, и это не мешает иметь среди всех приборов любимый.
Например, я люблю считать на логарифмической линейке, хотя каждый день ею, конечно, не пользуюсь, для этого есть калькулятор. Но опыт работы с линейкой даёт зримое представление о преобразованиях, соответствующих вычислениям. Движения ползунка и бегунка превращают вычисления в буквальную манипуляцию: в преобразования руками, от которых приходит интуитивное геометрическое представление о поле чисел, имеющее под собой глубокое теоретико-групповое основание. Ответ не берётся из ниоткуда, а возникает в контексте масштаба и своеобразного "ландшафта" вычислений, так что проверка его правильности начинает согласовываться с интуицией. Это как знание города помогает понять, как тебя везёт таксист.
Подобные опыт и интуицию даёт работа в Лиспе и Хаскеле. С ними программа на JS или C# превращается не просто в набор рецептов, инструкций, а в те или иные вычислительные схемы или математические структуры с присущими им свойствами.
Но, полагаю, даже если жаркие дискуссии на темы "нужна ли программистам математика", "что круче: ФП или ООП" и т.п. постепенно отомрут, на смену им придёт что-то вроде: "кто круче, как программист: ИИ, корректно выполняющий ТЗ, или человек с его творчеством?". Мы уже видим начало этой эпохи, споря можно ли доверять машине управлять автомобилем на дороге.
Думаю, для простоты примера. Регулярки, действительно знакомы всем, а контекстно-свободные грамматики, тем кто уже хоть немного знаком с теорией языков. К тому же, кроме злополучного many, в определениях примеров выражений не используется рекурсия материнского языка (Haskell), а именно она позволяет расширить регулярную грамматику до КС. Возможно, автор хотел показать, что хоть мы и создали EDSL, наследующий полноту по Тьюрингу от вмещающего языка, он сам по себе уже обладает вычислительной мощностью НКА. Впрочем, это уже мои домыслы :) но меня привлекла именно минимальность исходных посылок: создали элементарный тип, ввели его в свободную структуру и рраз! имеем конструктор, потом определили аглебру и рраз! готов простой исполнитель.
Да, пример, что надо! Ничего не знаю об этой библиотеке, но код смог прочесть сразу. Отличное сочетание моноидов и аппликациий! В этой связи люблю вспоминать моноидально-аппликативный fizzbuzz:
fizzbuzz = max <$> "fizz" `when` (`divisibleBy` 3)
<> "buzz" `when` (`divisibleBy` 5)
<> "quux" `when` (`divisibleBy` 7)
<*> show
where
when x p y = if p y then x else mempty
divisibleBy x n = x `mod` n == 0
Думаю, вполне правильно. Для управления состояниями строгие и императивные языки в монадах не нуждаются. Но монады и в этих языках позволяют организовывать поток вычислений с весьма изощрённой логикой. Когда-то я определил для себя, что монады позволяют мне перегрузить операторы := и ; определив в них свою семантику. Это случилось во времена Лиспа — не чистого и строгого языка.
Здесь mkComps выполняет всю работу чистым образом, "производя" данные, а в main они превращается в вывод на печать. Благодаря параметрическому полиморфизму функция printf может возвращать как "чистую" строку, так и побочное действие. А благодаря ленивости языка никакого списка в памяти при этом не создаётся, хотя выглядит он подозрительно. На моём ноутбуке откомпилированный бинарник отправил в /dev/null 10000*10000 записей за 10 секунд.
Абсолютно согласен. Мне хотелось показать, что ничего "магического", "неправильного" или чуждого идее ФП в функциях типа getLine нет. И вообще, разницу между императивным и функциональным подходом хотелось бы демистифицировать. Можно писать чистые функции на С, и даже выгоды от этого получать (в FORTRAN есть ключевое слово pure, помогающее компилятору трансляции чистых функций), но это акт доброй воли. Можно в Haskell запихать всё в IO, но компилятор из помощника превратится в послушного толмача. А можно балдеть от оптимизаций gcc и ghc, подавая им правильно приготовленные программы, расширяя горизонты. Кайф!
Это, действительно, было бы очень полезно и для практики и для участия в холиварах с пруфами :)
Вопрос не по теме. Присмотрел для перевода материал по freer monad, но сижу, чешу в затылке, как корректно перевести на русский freer: "ёщё более свободные", "освобождённые"… есть ли устоявшийся термин?
О, знаменитая статья. Но время идёт и приведённое в ней решение уже выглядит переусложнённым. Но это очень, очень полезная статья!
Так вышло, но детерминистическая генерация псевдо-случайных чисел тоже функциональна по своей природе. Недетерминизм возникает лишь на входе в цепочку генератора, а это может быть точкой входа в функциональную программу.
Для RosettaCode я писал "Змейку" на Haskell. И там генерация случайного расположения "еды" для змеи вся прячется в одной полиморфной функции в рамках
MonadRandom, так как будто бы генератор у нас есть и он возьмёт затравку, когда понадобится, но нам пока не важно откуда. При этом код выглядит так, будто бы в мире змейки уже существуют все будущие координаты в которых еда "случайно" появится (как в беременной самке тли хранятся уже беременные самки и т.д.), это следствие ленивости.Когда же, наконец, мы в точке входа в программу (функция
main) инициализируем змейкин мир, тогда в качестве экземпляраMonadRandomоказываетсяIO(без неё-то всё равно никак) и вот ни пользователь, ни змейка уже "не знают" где появится очередной фрукт.Это может показаться трюкачеством, но по-существу вся программа говорит только о том, что делать змейке, получившей сигнал от пользователя или при встрече с едой, и не более. Откуда возьмутся еда и сигналы пользователя, змейке знать не обязательно, об этом заботится только функция
main, которая отправляет её в "реальный мир", либо в его детерминистическую эмуляцию (монаду ST) для отладки.Этот пример не призван показать превосходство ФП перед императивным программированием. Он про то, что многие как кажется чисто императивные задачи гладко ложатся на функциональную парадигму, не требуя лишних шаманств и костылей (если не считать костылями то, что не понимаешь с первого раза).
Боюсь, что разочарую вас. Я имел в виду принципиальную возможность двигаться в этом направлении, если оставаться в рамках ФП. Пока же выкладки приходится делать "на бумажке". Но! Это возможно сделать. Я игрался с формальной верификацией некоего подмножества Java (практически, процедурным подмножеством, не выходящем за пределы Оберона) через триады Хоара. Очень быстро система неравенств становится неподъёмной, по моим ощущениям, экспоненциально. Инварианты циклов приходится писать самому, а это искусство и шаманство. После этого, возвращаясь к типам и индукции в ФП, с доказуемыми свойствами алгебраических структур, понимаешь, какой это кайф: надеть, наконец лыжи после того, как брел по пояс в мокром снегу. Но и лыжи пока приходится переставлять самому. Впрочем, пока ждем завтипов в Хаскеле, можно упражняться, отрабатывая технику на том что есть. Понятно же, что для того, чтобы написать грамотную рабочую спецификацию для автоматического верификатора, потребуется нехилая квалификация программиста. Но пока, насколько я вижу, именно ФП ведёт нас к возможности по-настоящему взлететь.
Запросто! Это как в задаче интегрирования. Есть алгебраический подход, а есть геометрический, есть спектральный, а есть аналитический по теореме Коши, наконец, можно численно, но и там, можно Симпсоном, можно Гауссом. Когда как удобнее. Полезно владеть всем.
Это не переменные, поскольку они не могут измениться, оставаясь в рамках процесса, описываемого функцией. Изменения происходят только на входе-выходе. Одно из отличий, в частности, состоит в том, что, в функциональном коде нет понятия времени и изменение наших "переменных" происходит одновременно:
a,b = b,a+b, эквивалентное последовательности присвоений с буферомс = b; b = a+b; a = c.Это не лучше и не хуже нормальных переменных, просто если проще описать вычислительный процесс итеративным, ФП этому не сильно помешает.
А вот тут в дело вступает то обстоятельство, что задача трансляции (компиляции) по природе своей функциональна. Объектный код полностью определяется исходным кодом и текущим окружением (входными параметрами). На этом стоит вся система сборки дистрибутивов типа configure >> make. Так что если абстракция функциональности и теряется на каком-то уровне, то это происходит всегда одинаково и решение можно, в конце концов, верифицировать, добившись герметичности абстракции на верхнем уровне. GHC это уже умеет. То есть, нас, действительно могут не сильно интересовать детали реализации, покуда компилятор не нарушает некоторых нужных нам законов и инвариантов.
Боже упаси! Рекурсивная функция не обязательно реализует рекурсивный процесс. если хочется организовать итерацию с "переменными"
aиb:что эквивалентно псевдокоду:
Но в функциональном решении пропустить инициализацию "переменных" нельзя никак.
Самое главное — эти проверки и доказательства возможны, причём уже сейчас, так что глупо этим не пользоваться и спорить. Что подтверждает тезис, обозначенный в названии статьи.
Функциональному подходу нет необходимости заполнять всё вокруг. Оно тяготеет к маленьким самодостаточным ортогональным блокам и если в императивной архитектуре такие блоки использовать, то они не помешают. В Фотране (куда уж императивнее!) с 80-х годов есть модификатор
pure, указывающий и программисту и компилятору, что определяемая функция чистая, что позволяет им делать определённые выводы как о коде функции, так и о коде, ее использующем.Операционную систему не сделать чистой по определению, но с некоторыми задачами ФП справляется отлично. Например, на моём ноутбуке, а также на домашнем и на рабочем десктопах стоит NixOS (Linux-дистрибутив построенный вокруг функционального ленивого (а значит, чистого) пакетного менеджера Nix), c оконным менеджером XMonad. И мне нужна их декларативность при настройке и переносе решений с машины на машину. Но это не позволяет мне говорить, что ФП решает все проблемы. Но оно очень неплохо встраивается в императивные решения, поскольку предлагает… чистые функции :)
Ну, и во многих областях это оправдано. Так появилась поддержка длинных целых и рациональных чисел с одной стороны, и всё более мощные символьные движки в повседневных задачах. Так что не зря упирались теоретики!
Про вилку и ложку — это хорошо! А ведь есть ещё палочки и ножи всякие… Споры о том "что круче" парадоксальны в своей бесполезности. Ответ очевиден — лучше научиться владеть всеми приборами, и это не мешает иметь среди всех приборов любимый.
Например, я люблю считать на логарифмической линейке, хотя каждый день ею, конечно, не пользуюсь, для этого есть калькулятор. Но опыт работы с линейкой даёт зримое представление о преобразованиях, соответствующих вычислениям. Движения ползунка и бегунка превращают вычисления в буквальную манипуляцию: в преобразования руками, от которых приходит интуитивное геометрическое представление о поле чисел, имеющее под собой глубокое теоретико-групповое основание. Ответ не берётся из ниоткуда, а возникает в контексте масштаба и своеобразного "ландшафта" вычислений, так что проверка его правильности начинает согласовываться с интуицией. Это как знание города помогает понять, как тебя везёт таксист.
Подобные опыт и интуицию даёт работа в Лиспе и Хаскеле. С ними программа на JS или C# превращается не просто в набор рецептов, инструкций, а в те или иные вычислительные схемы или математические структуры с присущими им свойствами.
Но, полагаю, даже если жаркие дискуссии на темы "нужна ли программистам математика", "что круче: ФП или ООП" и т.п. постепенно отомрут, на смену им придёт что-то вроде: "кто круче, как программист: ИИ, корректно выполняющий ТЗ, или человек с его творчеством?". Мы уже видим начало этой эпохи, споря можно ли доверять машине управлять автомобилем на дороге.
Думаю, для простоты примера. Регулярки, действительно знакомы всем, а контекстно-свободные грамматики, тем кто уже хоть немного знаком с теорией языков. К тому же, кроме злополучного
many, в определениях примеров выражений не используется рекурсия материнского языка (Haskell), а именно она позволяет расширить регулярную грамматику до КС. Возможно, автор хотел показать, что хоть мы и создали EDSL, наследующий полноту по Тьюрингу от вмещающего языка, он сам по себе уже обладает вычислительной мощностью НКА. Впрочем, это уже мои домыслы :) но меня привлекла именно минимальность исходных посылок: создали элементарный тип, ввели его в свободную структуру и рраз! имеем конструктор, потом определили аглебру и рраз! готов простой исполнитель.Да, пример, что надо! Ничего не знаю об этой библиотеке, но код смог прочесть сразу. Отличное сочетание моноидов и аппликациий! В этой связи люблю вспоминать моноидально-аппликативный fizzbuzz:
Примером декомпозиции в Haskell может быть реализация игры "Змейка" на RosettaCode: http://rosettacode.org/wiki/Snake#Haskell
Думаю, вполне правильно. Для управления состояниями строгие и императивные языки в монадах не нуждаются. Но монады и в этих языках позволяют организовывать поток вычислений с весьма изощрённой логикой. Когда-то я определил для себя, что монады позволяют мне перегрузить операторы
:=и;определив в них свою семантику. Это случилось во времена Лиспа — не чистого и строгого языка.Хороший пример, спасибо!
Идиоматичное решение здесь может быть таким: создадим чистую полиморфную функцию, которая соответствует вложенному циклу:
где
compare :: Ord a => a -> a -> Ordering— это чистая библиотечная функция, соответствующая вашей.Эту функцию можно вызвать в чистом контексте:
или в IO
это был вывод в консоль.
Здесь
mkCompsвыполняет всю работу чистым образом, "производя" данные, а вmainони превращается в вывод на печать. Благодаря параметрическому полиморфизму функцияprintfможет возвращать как "чистую" строку, так и побочное действие. А благодаря ленивости языка никакого списка в памяти при этом не создаётся, хотя выглядит он подозрительно. На моём ноутбуке откомпилированный бинарник отправил в/dev/null10000*10000 записей за 10 секунд.Впрочем, это я дразнюсь. Получается не всегда, если залезаешь в незнакомую область ничерта непонятно. Но если надо, то можно, и это круто!
Представляете, а ведь мы так говорим не чтобы запутать, а наоборот, чтобы разобраться :) и ведь получается!
Абсолютно согласен. Мне хотелось показать, что ничего "магического", "неправильного" или чуждого идее ФП в функциях типа getLine нет. И вообще, разницу между императивным и функциональным подходом хотелось бы демистифицировать. Можно писать чистые функции на С, и даже выгоды от этого получать (в FORTRAN есть ключевое слово pure, помогающее компилятору трансляции чистых функций), но это акт доброй воли. Можно в Haskell запихать всё в IO, но компилятор из помощника превратится в послушного толмача. А можно балдеть от оптимизаций gcc и ghc, подавая им правильно приготовленные программы, расширяя горизонты. Кайф!