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

Добрый день, уважаемое хабрасообщество!

В конце ноября 2013 года мы с коллегой устроили встречу, на которой провели сеанс «интенсивного введения Scala в мозг добровольцев».

Выкладываю на суд общественности наше творчество и краткое описание «эксперимента».

На Хабре много статей по монады с примерами для Haskell (http://habrahabr.ru/post/183150, http://habrahabr.ru/post/127556), но не так много статей, которые описывают, что такое монады с примерами на Scala. По сколько большинство разработчиков на Scala пришли из мира объектно ориентированного программирования, то для них, по началу, сложно понять что такое монады и для чего они нужны, эта статья как раз для таких разработчиков. В этой статье я хочу показать, что это такое и навести примеры использования монады Option, в следующих статьях будут описаны монады Try и Future.

В этой статье мы попытаемся рассмотреть всё разнообразие Алгебраических Типов Данных.

Надо сказать, задача это достаточно неподъёмная, и понять человеку, если он ранее с Алгебраическими Типами не имел дело — не очень просто.
АТД были впервые использованы в языке Hope, но основную популярность они приобрели благодаря языкам ML, такими как Standart ML, OCaml, F#, и языку Haskell.
Ныне АТД в той или иной мере поддерживаются в значительно большем количестве языков: Scala, Rust, Nemerle, Racket,…
АТД — это универсальный тип данных. С помощью него можно представить большинство типов данных.
АТД называются алгебраическими, потому что их можно представить как некую алгебраическую композицию типов его составляющих. Это знание даёт своё преимущество: понимая свойства алгебраической композиции, можно посчитать какой тип необходим для построения тех или иных данных.
Будем рассматривать типы на основе языка Haskell, однако подобного с лёгкими изменениями можно добиться в других языках с поддержкой АТД.

Признаюсь. Я не очень любил курс структур данных и алгоритмов в университете. Все эти стеки, очереди, кучи, деревья, графы (будь они не ладны) и прочие “остроумные” названия непонятных и сложных структур данных ни как не хотели закрепляться в моей голове. Как истинный “прагматик”, я уже на втором — третьем курсе свято верил в стандартную библиотеку классов и молился на дарованные нам (простым смертным) коллекции и контейнеры, бережно реализованные отцами и благородными донами CS. Казалось, все что можно было придумать — уже давно придумано и реализовано.

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

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

Всем программистам рано или поздно приходится передавать данные. Ни для кого не секрет, что библиотек сериализации в Java существует примерно >9000, а в C++ они вроде и есть, а вроде их и нет. К счастью для большинства, несколько лет назад появился Google Protobuf, который принёс достаточно удобный способ определять структуры данных и быстро завоевал всенародную любовь. Это была фактически первая, доступная широким массам библиотека, позволяющая гонять по сети готовые структуры данных, не связываясь при этом с чем-то вроде XML. На дворе был 2008 год.

Вернёмся немного назад. В 2006 году простой индийский программист (как бы подозрительно это ни звучало!) Анил Мадхавапедди, один из самых известных сейчас в мире OCaml-разработчиков и автор свежевышедшей книги Real World OCaml, защищал в Кембридже кандидатскую диссертацию. Именно о ней я сегодня вам и расскажу.

Анил сразу пошёл дальше, чем Google. Он сразу подумал, для чего люди обычно пересылают по сети какие-то формализованные структуры данных? Чтобы реализовать какой-то протокол. А что такое протокол? Это какой-то конечный автомат. А где мы можем взять хороший пример сложного, хорошо спроектированного и проверенного временем протокола? Да прямо в обычном сетевом стеке! Итак, были взяты набор сетевых структур данных и протоколов: Ethernet frame, IPv4, ICMP, TCP, UDP, SSH, DNS и DHCP и постановка задачи: большая часть этих протоколов (особенно SSH и DNS) реализуются, что называется «руками», а хочется, чтобы не было типичных для C переполнений буфера, все переходы совершались автоматически, это всё можно было верифицировать, и чтобы работало быстро, а не как обычно.

Поскольку никто не будет читать диссертацию, сразу скажу: это более чем удалось. По результатам работы были написаны референсные реализации DNS и SSH-сервера и произведено сравнение с BIND и OpenSSH. OCaml-реализации давали по сравнению с традиционными прирост производительности от незначительного, до почти двухкратного. Кроме того была найдена ошибка в RFC на SSH (рабочая группа была уведомлена и RFC исправлен). О том, что было сделано, и как с этим жить, читайте под катом.

Добрый день, сегодня хотелось бы рассказать, как наша команда работает с базами данных. У нас в компании в основном используется Oracle и в нашей команде много людей, кто умеет хорошо его готовить. Нам изначально хотелось получить полный доступ к его возможностям: иерархическим запросам, аналитическим функциям, передаче объектов и коллекций, как параметров запросов, и, может быть, если не будет другого способа — хинтам. Модель у нас не очень сложная, поэтому сознательно отказались от ORM.

В качестве основы взяли Apache DbUtils и сделали для него простую обёртку на Scala. Ниже я расскажу, как возможности Scala, особенно её последней версии 2.10, помогли упростить работу с базой данных.

А пытливых читателей, кто дочитает до конца, ждёт сюрприз.

Привет Habr! Сегодня мы поговорим о полиморфизме функций, операторах и карринге. Напоминаю, что лекции рассчитаны на новичков, а конспект предпологает сжатую форму изложения. Если все еще интересно…

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

Этот факт находит отражение и в изменении учебных курсов. Сассман, автор SICP, самого известного курса по программирование, сказал: " инженерное дело в середине 90-ых, а уж тем более в 2000-ых сильно отличается от инженерного дела 80-ых. В 80-ых хорошие программисты проводили много времени в размышлениях, а потом писали немного кода, который работал. Код работал близко к «железу», даже Scheme — все было прозрачно на всех стадиях. Как с резистором, достаточно посмотреть на цветную маркировку, чтобы узнать номинальную мощность, допустимые отклонения, сопротивление и V=IR — это все, что нужно знать. 6.001 был задуман как курс для обучения инженеров тому, как из маленьких кубиков, в которых они досконально разбираются, посредством простых техник составлять сложные конструкции, которые делают то, что от них хотят. Но программирование сейчас далеко не то же самое. Теперь вы ковыряетесь в непонятной или несуществующей документацией для софта, даже неизвестно, кем написанного. Вы должны досконально исследовать библиотеки, чтобы узнать, как они работают, пробовать разные исходные данные и смотреть, как реагирует код. Это в корне иная работа, и для нее требуется иной курс обучения."

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

Привет Habr! Сегодня я достал свои старые конспекты по курсу «Haskell как первый язык программирования» Сергея Михайловича Абрамова и попробую максимально доходчиво и с примерами рассказать об этом замечательном языке тем, кто с ним еще не знаком. Рассказ ориентирован на неподготовленного читателя. Так что, даже если вы впервые услышали слово Haskell…

Это достаточно вольный перевод статьи. Дело в том, что несмотря на конструкции в одну строчку, материал сложен для понимания.
Беря во внимание то, что в комментариях Прелюдия или как полюбить Haskell просили, чтобы код был понятный, я внёс достаточно ремарок, и, надеюсь, код будет понятен и тем, кто далёк от Хаскеля.

Давайте начнём с самого трудного — с самого заголовка: многим непонятны все его слова.
Хаскель — это чистый и ленивый функциональный язык.
Лёб — это немецкий математик, о котором мы поговорим чуть позже.
Ну, и наконец, самое интересное — странные петли.

Странные петли — это запутанные категории, когда двигаясь вверх или вниз в иерархической системе, находишь то же самое, откуда начал движение.
Зачастую такие петли содержат само-референтные ссылки.
Например, подобной странной петлёй обладает рекурсивные акронимы: «PHP — PHP: Hypertext Preprocessor».
Ну, и на сегодняшний день наиболее загадочным словом, содержащим странные петли, является понятие «я».

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

Немецкий математик Лёб мигрировал в 39-м году ХХ-го столетия в Великобританию. Лёб, в частности, развивал математическую логику и миру прежде всего известен Теоремой Лёба. Это теорема развивала труды Гёделя о неполноте математики. Теорема Лёба о взаимосвязи между доказуемостью утверждения и самим утверждением, она гласит, что

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

Всю эту сложность высказывания можно записать символически:


Можно ли такую функцию написать на Хаскеле?! Можно! И всего в одну строчку!

Добрый дня, уважаемые хабровчане. Всегда трудно начинать. Трудно начать писать статью, трудно начать отношения с человеком. Очень трудно, бывает, начать изучать новый язык программирования, особенно, если этот язык рушит все представления и устои, которые у вас были, если он противоречит привычной картине мира и пытается сломать вам мозг. Пример такого языка — Haskell.

J – самый ненормальный и самый эффективный язык из известных мне языков. Он позволяет быстро разрабатывать, а также вызывать ненормативную лексику у людей, незнакомых с ним и смотрящих на код.

J слишком необычный. И сложный для изучения. У людей, сталкивающихся с J не хватает мотивации, чтобы его изучить. Синтаксис непривычный.
В этом посте я хотел помочь вам заглянуть дальше, что будет, если вы его изучите и чем он интересен. По своему опыту знаю, что преимущества этого языка сразу не очевидны. В посте я не собираюсь останавливаться на разборе конструкций. Только в обзоре. Предлагаю просто окунуться в примеры, попробовать ощутить мощь языка. Узнать, чем прекрасен язык, без изучения. Писать статьи, обучающие программированию на нем – дело сложное и думаю, не нужное. Он не так прост, чтобы это сделать кратко, а с обучающими материалами на официальном сайте нет никаких проблем. Главное – желание. Им и займемся.

Так уж завелось на хабре, что на каждую холиварную статью «Pro» всегда найдётся статья «Contra».
Я тоже решил не оставлять в одиночестве пост «Что не так с ООП и ФП».



Прямо противоречить написанному смысла не имеет, там ведь описан «вкус», а, как известно, на вкус и цвет… каждый любит свой ЯП.
Нет никакой проблемы с ООП и ФП. Чистота функций — это всего лишь инструмент, равно как и «всё является объектом».
Критика права лишь в одном — в борьбе за миллиметры хорошо видны яркие прорехи, а в любых вырожденных методах недостатки ярко проявляются.
Другое дело, что любые невырожденные методы так же имеют недостатки, только их больше, зато они не так легко заметны.
Любители С++ гнобят полное ООП, Javа гнобит Си++ за неполное ООП, Haskell гнобит другие ФП за грязные функции, остальные ФП гнобят Haskell за излишне чистые функции.
Всё имеет свою оборотную сторону медали.
Тогда почему досталось всё объектам и функциям, а не массивам и указателям?!

Я не понимаю причины существования бесконечных споров вокруг Объектно-ориентированного (ООП) и Функционального (ФП) программирования. Кажется, что такого рода вещи находятся за пределами человеческого понимая, и о них можно спорить бесконечно. Много лет занимаясь исследованием языков программирования, я увидел четкий ответ, и зачастую я нахожу бессмысленным обсуждение этих вопросов.

Если кратко, то как ООП, так и ФП неэффективны, если доходить в их использовании до крайности. Крайностью в ООП считается идея о том что “все что угодно является объектом” (чистое ОП). Крайностью для ФП можно рассматривать чистые функциональные языки программирования.

Известно, что задача определения того, истинна ли некоторая функция Integer -> Bool хотя бы для одного числа вычислительно неразрешима. Однако, нечто, на первый взгляд кажущееся как раз таким оракулом (а именно, функцией (Integer -> Bool) -> Maybe Integer) будет описано в этой статье.

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

data Nat = Zero | Succ Nat deriving (Eq, Ord, Show)

Другими словами, натуральное число — это либо ноль, либо некоторое натуральное число, увеличенное на единицу (Succ от слова successor).

Также, для удобства, определим основные операции (сложение, умножение, конвертация из Integer) над числами в таком представлении:

instance Num Nat where
    Zero + y = y
    Succ x + y = Succ (x + y)

    Zero * y = Zero
    Succ x * y = y + (x * y)

    fromInteger 0 = Zero
    fromInteger n = Succ (fromInteger (n-1))

Статья устарела, актуальную информацию ищите на сайте Warp9'а



Существует множество реактивных и около-реактивных библиотек для создания графического интерфейса на js: Angular, Knockout, React, RxJS… Спрашивается, зачем писать еще одну. Оказывается, во всех них, помимо фатального недостатка, есть еще несколько.

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

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

Теория «Черного лебедя»

Автор теории Нассим Николас Талеб, описавший ее своей книге «Чёрный лебедь. Под знаком непредсказуемости». Теория рассматривает труднопрогнозируемые и редкие события, которые несут за собой значительные последствия. Процессы реального мира не возможно описать с точки зрение одной лишь математики, и в доказательство этому рассмотрим один простой пример.

Часто, при создании достаточно сложных приложений на JavaScript наступает тот момент, когда становиться совершенно непонятно почему приложение перестало работать как надо, или наоборот вдруг заработало. Cвязей между элементами приложения становится так много, что уследить за ними даже с хорошими дебаггером очень трудно. И вот диллема: с одной стороны есть хорошо известная методика создания приложений на JS, столь привычная и глубоко описанная, что недостатков мы уже как бы и не замечаем. С другой стороны есть масса библиотек предлагающих нам перейти на другую сторону попробовать что-то новое. К таким библиотекам относиться и Bacon.js, предоставляя реализацию FRP на JavaScript.

Предыдущая статья цикла Язык программирования J. Взгляд любителя. Часть 3. Массивы

1. Коробки

Мы уже столкнулись с тем, что существительное в J — это массив. Даже над одиночными константными значениями допустимы векторные операции. В совокупности все это составляет удобную векторную гомогенную среду программирования.

Однако, очевидно, что у массивов есть и свои ограничения. В связи с тем, что в J по умолчанию только прямоугольные массивы, то и нет возможности стандартными средствами создавать т.н. ступенчатые (jagged) массивы. Кроме того, для списков, состоящих из разнородных элементов, массивы также не подходят.