• Регулярные выражения: никакой магии

    • Перевод
    image

    Код этого поста, как и сам пост, выложен на github.

    До недавнего времени регулярные выражения казались мне какой-то магией. Я никак не мог понять, как можно определить, соответствует ли строка заданному регулярному выражению. А теперь я это понял! Ниже представлена реализация простого движка регулярных выражений менее чем в 200 строках кода.

    Часть 1: Парсинг


    Спецификация


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

    • . — соответствие любому символу
    • | — соответствие abc или cde
    • + — соответствие одному или более предыдущего паттерна
    • * — соответствие 0 или более предыдущего паттерна
    • ( и ) — для группировки

    Хотя набор опций невелик, с его помощью можно создать интересные regex-ы, например, m (t|n| ) | b позволяющий найти субтитры к Star Wars без субтитров к Star Trek, или (..)* для нахождения множества всех строк чётной длины.

    План атаки


    Мы будем анализировать регулярные выражения в три этапа:

    1. Парсинг (синтаксический анализ) регулярного выражения в синтаксическое дерево
    2. Преобразование синтаксического дерева в конечный автомат
    3. Анализ конечного автомата для нашей строки

    Для анализа регулярных выражений (подробнее об этом ниже) мы будем использовать конечный автомат под названием NFA. На высоком уровне NFA будет представлять наш regex. При получении входных данных мы будем перемещаться в NFA от состояния к состоянию. Если мы придём в точку, из которой невозможно совершить допустимого перехода, то регулярное выражение не соответствует строке.
    Читать дальше →
    • +27
    • 13,8k
    • 4
  • Глобальная теплокарта Strava: теперь в 6 раз горячее

    • Перевод
    Рад объявить о первом крупном обновлении глобальной тепловой карты в Strava Labs c 2015 года. Это обновление включает в себя в шесть раз больше данных, чем раньше —  в сумме 1 миллиард активностей со всей базы Strava по сентябрь 2017 года.

    Наша глобальная теплокарта — самая крупная и подробная, и это самый прекрасный в мире набор данных такого рода. Это прямая визуализация активностей глобальной сети атлетов Strava. Чтобы дать представление о масштабе, то новая теплокарта включает в себя:

    • 1 миллиард активностей
    • 3 триллиона точек долготы/широты
    • 13 триллионов пикселей после растрирования
    • 10 терабайт исходных данных
    • Общая дистанция маршрутов: 27 миллиардов километров
    • Запись общего времени активности: 200 тысяч лет
    • 5% земной суши покрыто тайлами


    Тепловая карта Москвы демонстрирует функцию поворота/наклона в Mapbox GL
    Читать дальше →
  • Dotty – будущее языка Scala

      В конце мая я оказался среди слушателей конференции Scala Days в Копенгагене. Одним из ключевых спикеров был создатель языка Scala Мартин Одерски. Он рассказал о развитии языка и, в частности, о разработке компилятора, названного Dotty. Планируется, что на основе Dotty будет разработан новый компилятор для версии 3.0.

      Мартин не раз выступал на эту тему, и я бы хотел собрать здесь всю актуальную информацию о Dotty – новые ключевые возможности и элементы, удаленные за ненадобностью.


      Мартин Одерски. План развития Scala на ближайшие несколько лет

      Этот пост будет полезен и знатокам, и совсем новичкам, для которых разговор о Dotty я предваряю рассказом об особенностях Scala, а также о том, что лежит в его математической основе.
      Читать дальше →
    • Шесть парадигм программирования, которые изменят ваш взгляд на код

      • Перевод
      Периодически я натыкаюсь на языки программирования, которые настолько самобытны, что меняют моё представление о коде в целом. В этой статье я хотел бы поделиться некоторыми из самых любимых моих находок.

      Здесь вы не найдёте устаревшего посыла «функциональное программирование спасёт мир!»; мой список состоит из куда менее популярных наименований. Готов поспорить, многие из читателей вообще не слышали о большинстве языков и парадигм, о которых пойдёт речь, так что надеюсь, вам будет так же интересно с ними разбираться, как и мне.

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


      Читать дальше →
    • Монадные трансформеры для практикующих программистов

      • Перевод

      Прикладное введение в монадные трансформеры, от проблемы к решению


      Представьте, что вы сидите за рабочим столом, допиваете кофе и готовитесь к написанию кода на Scala. Функциональное программирование оказалось не так страшно, как его малюют, жизнь прекрасна, вы усаживаетесь поудобнее, сосредотачиваетесь и начинаете писать новый функционал, который нужно сдать на этой неделе.


      Всё как обычно: несколько лаконичных однострочных выражений (да, детка, это Scala!), несколько странных ошибок компилятора (о, нет, Scala, нет!), лёгкое сожаление о том, что вы написали такой запутанный код… И вдруг вы сталкиваетесь со странной проблемой: выражение for не компилируется. «Ничего страшного», — думаете вы: «сейчас гляну на StackOverflow», как вы это делаете ежедневно. Как все мы это делаем ежедневно.


      Но сегодня, похоже, неудачный день.


      Читать дальше →
      • +25
      • 8,4k
      • 8
    • Тонкости Scala: изучаем CanBuildFrom

      image


      В стандартной библиотеке Scala методы коллекций (map, flatMap, scan и другие) принимают экземпляр типа CanBuildFrom в качестве неявного параметра. В этой статье мы подробно разберём, для чего нужен этот трейт, как он работает и чем может быть полезен разработчику.


      Читать дальше →
    • Ой, у вас баннер убежал!

      Ну. И что?
      Реклама
    • Возвращаясь к Неразмеченным Конечным Интерпретаторам с Dotty

      Неразмеченные Конечные Интепретаторы (Tagless Final interpreters — прим. пер.) — это альтернативный подход традиционным Алгебраическим Типам Данных (и обобщённым ADT), основанный на реализации паттерна "интерпретатор". Этот текст представляет "неразмеченный конечный" подход в Scala, и демонстрирует каким образом Dotty с его недавно добавленными типами неявных функций делает этот подход ещё более привлекательным. Все примеры кода — это прямое переложение их Haskell версий, представленных в Typed Tagless Final Interpreters: Lecture Notes (раздел 2).


      Паттерн "интерпретатор" в последнее время привлекает всё больше внимания в сообществе Scala. Множество усилий было затрачено на борьбу с наиболее ярким недостатком решений, основанных на ADT/GADT: расширяемость. Для начала можно взглянуть на typeclass Inject из cats как на реализацию идей Data Type à la Carte. Библиотека Freek предоставляет средства для комбинирования более двух алгебр, используя украшения с задействованием аппарата операций на уровне типов. Решение, предложенное в работе Freer Monads, More Extensible Effects также ставит акцент на расширяемости, и вдохновлено набором небольших Scala-библиотек, таких как eff, emm и paperdoll. Неразмеченные конечные интерпретаторы подходят в некотором смысле с противоположной стороны, используя типы классов в своём непосредственном основании вместо более традиционных ADT/GADT. Они также поставляются с большим превосходством в расширяемости "из коробки" без каких-то явных опасностей.


      Читать дальше →
    • Мифы о Spark, или Может ли пользоваться Spark обычный Java-разработчик

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

        Итак, Евгений EvgenyBorisov Борисов о Spark, мифах и немного о том, дествительно ли тексты Pink Floyd адекватнее, чем у Кэти Пэрри.





        Это будет необычный доклад о Spark.

        Обычно много рассказывают про Spark, какой он крутой, показывают код на Scala. Но у меня немного другая цель. Во-первых, я поговорю о том, что такое Spark и зачем он нужен. Но основная цель — показать, что вы, как Java-девелоперы, можете прекрасно им пользоваться. В этом докладе мы развеем несколько мифов о Spark.
        Читать дальше →
        • +26
        • 17,2k
        • 6
      • Советы начинающему скалисту

          Часть 1. Функциональная


          Эта статья (если быть до конца честным — набор заметок) посвящена ошибкам, которые совершают новички, ступая на путь Scala: не только джуниоры, но и умудренные опытом программисты с сединами в бороде. Многие из них до этого всегда работали лишь с императивными языками такими как C, C++ или Java, поэтому идиомы Scala оказываются для них непонятными и, более того, неочевидными. Поэтому я взял на себя смелость предостеречь новообращённых и рассказать им об их типичных ошибках — как совсем невинных, так и тех, что в мире Scala караются смертью.

          Читать дальше →
        • Прекрасное настоящее и светлое будущее Scala

            image

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

            В мае 2016 году на конференции Scala Days в Нью-Йорке Мартином Одерски была представлена презентация, описывающая настоящее и будущее языка Scala.
            Читать дальше →
          Самое читаемое