• Учим поросёнка на моноидах верить в себя и летать

    • Tutorial

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



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

    Читать дальше →
  • Стековая машина на моноидах

    • Tutorial

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


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


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

    Читать дальше →
  • Данные высокого рода

      Да-да, вам не привиделось и вы не ослышались — именно высокого рода. Род (kind) — это термин теории типов, означающий по сути тип типа [данных].

      Но вначале немного лирики.

      На Хабре вышло несколько статей, где подробно описывался метод валидации данных в функциональных языках.

      Эта статься — мои пять копеек в этот хайп. Мы рассмотрим валидацию данных в Хаскеле.

      Валидация типом


      Ранее было рассмотрен пример методики валидации при помощи валидации типом:

      type EmailContactInfo  = String
      type PostalContactInfo = String
      
      data ContactInfo = EmailOnly EmailContactInfo | 
                         PostOnly PostalContactInfo | 
                         EmailAndPost (EmailContactInfo, PostalContactInfo)
      
      data Person = Person 
        { pName :: String,
        , pContactInfo :: ContactInfo,
        }

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

      Валидация данными высокого рода




      В этой статье мы посмотрим иной метод валидации — при помощи данных высокого рода.

      Пусть у нас есть тип данных:

      data Person = Person
        { pName :: String
        , pAge  :: Int
        }

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

      Тут можно и поэтому данный метод широко используется среди авторов библиотек на Хаскеле.
      Читать дальше →
      • +16
      • 2,9k
      • 7
    • Как сделать ещё больше некорректных состояний ещё более невыразимыми

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

        Читать дальше →
      • Великая сила newtypes

          НовыйТип (newtype) — это специализированное объявление типа данных. Такое, что содержит лишь один конструктор и поле.

          newtype Foo a = Bar a
          newtype Id = MkId Word
          


          Типичные вопросы новичка


          В чём же отличие от data типа данных?

          data Foo a = Bar a
          data Id = MkId Word
          

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

          Да это ничего не значит для меня… Буду использовать data
          Не, ну в конце-концов, всегда можно включить расширение -funpack-strict-fields :) для строгих(не ленивых) полей или указать прямо

          data Id = MkId !Word
          

          Всё же сила newtype не ограничивается лишь эффективностью вычислений. Они значительно сильнее!
          Читать дальше →
          • +13
          • 2,7k
          • 2
        • ТРИЗ, Haskell и функциональное мышление

            При слове ТРИЗ, часто вспоминают тезис "идеальная система — та, которой нет (а ее функция при этом выполняется)". Как хороший админ, который не появляется в офисе, а все при этом исправно работает.


            Функция и система — критически важные понятия в ТРИЗ, говорят даже о функциональном стиле мышления. Правда при этих словах лично у меня сразу возникает ассоциация с функциональными языками программирования.


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


            Читать дальше →
          • Cofree Will Tear Us Apart

            Всем привет.


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

            Читать дальше →
          • Software Transactional Memory на Free-монадах

              Осознав, что я давно не писал на Хабр ничего полезного о ФП и Haskell, и что имеется вполне отличный повод для технической статьи, — решил тряхнуть стариной. Речь в статье пойдет о Software Trasactional Memory (STM), которую мне удалось реализовать на Free-монадах при участии ADTs (Algebraic Data Types) и MVars (конкурентные мутабельные переменные). И, в общем-то, Proof of Concept оказался крайне простым, в сравнении с «настоящим» STM. Давайте это обсудим.

              Software Transactional Memory

              Читать дальше →
            • Пишем небесных пчелок на Cloud Haskell

              • Tutorial

              Привет, Хабр!

              Прошло всего лишь каких-то 11577635 секунд с конца осенней школы GoTo в ИТМО. Неделя направления Распределённых систем началась с прототипирования распределённой системы на Cloud Haskell. Мы начали бодро и потому быстро выяснили, что существующую документацию без PhD понять сложновато — и решили написать методичку.

              Под катом введение в p2p cloud haskell, немножко функционального стека прототипирования РС, мотивация и «но зачем».
              Читать дальше →
              • +26
              • 4,8k
              • 3
            • Haskell. Задача о мудрецах и колпаках

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

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

                Как он об этом догадался?
                Существует определенная последовательность рассуждений, которая привела нашего мудреца к верному ответу. Мы попытаемся смоделировать эти рассуждения.
                Читать дальше →

              Самое читаемое