Category: it

satyr

У нас есть Rust, поэтому C++ больше не нужен.

Просто чудесный пост у thesz, наглядно демонстрирующий мой лозунг из сабжа.

Давайте пройдёмся по пунктам:

> Большое неудобство, однако, составляет отсутствие подсказок компилятора в сообщении об ошибке

Rust прекрасно всё подсказывает, вплоть до того, что явно указывает как именно тебе надо исправить код, чтобы всё заработало.

> но сама необходимость думать о том, как правильно создавать объект, отнимает достаточно сил

А в Rust отсутствует возможность "неправильно" создать объект.

> должен ли я бросать исключение

В Rust нет исключений, а есть только один "идеоматический" (как это по-русски — общепринятый?) способ сигнализировать об ошибке: вернуть Result.

> могу ли я оставить объект не полностью или не корректно созданным

В Rust невозможно (без использования unsafe) не полностью инициализировать объект.

Ну и так далее.

На самом деле, в Rust очень многое сделано сразу правильно, по сравнению с C++. Ведь его же создавали люди, которые много программировали на C++ :) В Rust мы не встретим таких понятий, как "правило пяти", "swap", "pimpl", etc, потому что язык уже сделан как нужно.

Кроме того, в Rust используется только один общепринятый стиль написания кода (вспоминаем все эти венгерские нотации, все эти противоречащие друг другу c++ guidelines от гугл, тоёты, микрософта и тд), существует один всемогущий cargo c сайтом crates.io (вспоминаем цмейк, автомейк, сконс и тд), а также rustdoc, rustup, rustfmt, и тд и тп.

Повторюсь (уже в третий раз в этом блоге): нет никаких причин в настоящее время программировать что-то новое на C++, потому что есть Rust. Могут быть причины, чтобы выбрать вместо Rust, там, какой-нибудь Haskell, Scala, Erlang, да даже Common Lisp. Но не может быть никаких причин, чтобы вместо Rust выбрать C++.

satyr

а вот, например, ещё вакансии

Собственно, образовалась ещё вакансия. Нам нужно несколько человек, задач много, они все (как это водится) инновационные и интересные, минимум легаси, максимум r&d, ну и так далее.

Формальное описание таково:


От кандидата требуется:
  • Опыт работы с большими объёмами данных.
  • Знание основных паттернов проектирования систем обмена сообщениями.
  • Опыт сетевого программирования.
  • Навыки работы с linux.
Плюсами будут:
  • Знание теории, связанной с bigdata (статистика, машинное обучение, анализ данных, вероятностные алгоритмы, кластеризация, и т.п.)
  • Знание, или устойчивое желание и возможность освоить:
    • Язык программирования Rust
    • Язык программирования Erlang и платформу OTP
  • Владение функциональной парадигмой программирования.
  • Опыт работы с:
    • RabbitMQ
    • Postgres
    • Apache Cassandra
    • Redis

Работа на полный рабочий день: по желанию либо в офисе (Москва, ул. Верейская), либо удалённо, с регулярным посещением офиса для совещаний. Размер зарплаты обсуждается индивидуально (очевидно, он в прямой зависимости от навыков кандидата), но, в любом случае, сумма должна получиться выше рынка.

Если интересна вакансия, пишите мне на почту (с резюме в аттаче), если знаете кого-то, кому может быть она интересна — рассказывайте! Общие вопросы пишите лучше сюда в комменты, чтобы мне не копипастить по письмам ответы.

satyr

ICFPC 2017: Ticket to Ride на Rust (первая часть)

ICFPC 2017: Ticket to Ride на Rust.

Сетап.

В прошлом году я как-то так и не собрался написать отчёт про ежегодный конкурс, который проходит под эгидой ICFP. Хотя там тоже было интересно: наша команда впервые выступила не на традиционном Common Lisp, а вовсе даже на Haskell. Опыт был достаточно любопытным. Мне скорее понравилось, ребятам скорее нет -- но положенную долю драйва все получили (хотя выступили в тот раз так себе, конечно).

В этот раз решили продолжить с экспериментами, и попробовать в деле Rust. Так как этот язык кроме меня тоже никто не знал, было принято решение основательно подготовится в течении года: совместно порешать предыдущие задания ICFPC, поревьювить разнообразного коду на расте, и тд. Надо же ответственно подходить к делу, сколько можно проигрывать-то всяким бомжам, верно? Итак, внимание вопрос: сколько же раз мы с командой успели таким образом попрактиковаться? Правильно, ноль.

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

  • Пять человек в команде.
  • Из них "на полной ставке" четверо.
  • Программировать на Rust-е умеет один, остальные листали книжку.
Казалось бы, это же верная заявка на победу? Вот и я так думал, поэтому мирозданию пришлось ещё немного подкорректировать расклад:
  • Фёдор по семейным обстоятельствам отказывается от участия.
  • Я ломаю себе правую руку.
Вот теперь ситуация выглядит справедливо, следовательно, можно начинать играть :)

Подготовка.

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

Вот что мне показались полезным по итогам экспериментов:

  • nom -- крутая библиотека zero-cost парсер-комбинаторов.
  • piston -- вообще, это игровой движок, но он сильно модульный, поэтому оттуда легко взять только самоы необходимый минимум для того же визуализатора, без необходимости разбираться в огромном навороченном апи.

Надо сказать, что пистон меня прямо впечатлил: я что-то даже не ожидал, как там легко всё делается: графика (и 2d, и opengl), рисовалки всякие, картинки, шрифты, мышь/клавиатура. Прям даже захотелось какую-нибудь игру напрограммировать =) По-факту визуализатор базового уровня (а что-то большее редко требуется на icfpc) пишется неспешно за 30 минут, а если приложить чуть больше усилий, можно вполне сделать игровой симулятор. Пример такого простенького графического интерфейса для сокобана можно видеть на картинке выше.

Начало конкурса.

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

В этот раз ребята, организовавшие конкурс (University of Edinburgh) осмелели настолько, что по какой-то причине решили захостить сайт с заданием на своей площадке (а не на гитхабе или гугл-доках, как обычно это делалось в последнее время). Разумеется, ровно в 15:00 сайт обвалили, и работягам пришлось ждать минут тридцать, пока орги всё-таки перевезут своё барахло на гитхаб. Но, так или иначе, задание всё же было получено в виде PDF-ки.

Участникам предлагалось сыграть в онлайн-версию "Паровозов": весьма популярной настолки Ticket To Ride. На старте выдаётся карта с набором объектов, малая часть из которых является шахтами, где добывают лямбды, а большая часть является потребителями этих лямбд. Объекты как-то соединены между собой реками, по которым лодочники могут доставлять добытые лямбды из шахт к потребителям.

На картинке объекты 1 и 5 являются рудниками, а все остальные узлы графа -- потребителями. Игроки (лодочники) делают ход по-очереди, либо "захватывая" себе одну какую-то ничейную реку, либо пасуя. Чем дальше по построенному маршруту удалось увезти от шахты ламбды, тем больше очков зарабатывает игрок. Цель игры, соответственно, набрать больше всех очков.

Уметь играть предлагалось в двух режимах:

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

Вообще, конечно, я уже не первый раз наблюдаю в ICFPC эти милые мелочи, типа сериализуемого стейта: видно, что организаторы всячески пытаются подогнать задание под функциональные языки, чтобы на них делать было удобно, а на императивных, напротив, муторно. И, что любопытно, даже несмотря на это побеждают преимущественно всякие c++ и java :)

А для маленьких любителей попрограммировать инфраструктуру была выдана спека на несколько страниц про протокол для онлайн и оффлайн режимов, спецификации для кодировки данных (json), алгоритм для подсчёта очков и обработки таймаутов. В общем, всё как полагается.

Также, в этот раз были обещаны апдейты задания прямо в процессе конкурса (до четырёх раз), и lightning division: отдельное объявление победителей по итогам 24-х часового марафона.

День первый.

Первые пару часов мы традиционно тупим в правила, и пытаемся играть друг с другом в предоставленном организаторами симуляторе, который работает через веб-интерфейс. К 16:23 я коммичу скелет проекта и какие-то базовые структуры данных, а Sectoid начинает настраивать какой-то наколенный CI.

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

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

Далее работы распределяются следующим образом: Игорь начинает программировать сериализацию структур данных в json, я отправиляюсь писать игровой цикл с сопутствующей обвязкой, Sectoid продолжает мучать CI, а Turtle куда-то уходит.

В 17:23 я внезапно делаю игровой цикл с игровым стейтом. Осмотревшись вокруг, я обнаруживаю, что никто ещё не освободился. Поэтому я берусь делать дальше протокол чата с сервером. Ещё через двадцать минут возвращается Turtle и берётся писать подсчёт очков -- как это обычно у нас принято, испортив мастер. Я традиционно прогоняю его в бранч :) Sectoid в это время дорабатывает CI.

Ещё через два часа я делаю реализацию игрового чата с сервером. Причём, в этом виде функции практически без изменений доживают до самого конца конкурса, хотя это изначально планировался как черновой набросок. Так как у меня на текущий момент есть только игровой стейт, а самих клиентов (сетевого и оффлайн) и сериализации пока нет, я делаю вот такую функцию:

pub fn run_online<S, FS, SR, FR, RR, GB>(
    name: &str,
    mut fn_state: S,
    mut send_fn: FS,
    mut recv_fn: FR,
    gs_builder: GB)
    -> Result<(Vec<Score>, GB::GameState), Error<SR, RR, <GB::GameState as GameState>::Error>>
    where FS: FnMut(&mut S, Req, Option<GB::GameState>) -> Result<(), SR>,
          FR: FnMut(&mut S) -> Result<(Rep, Option<GB::GameState>), RR>,
          GB: GameStateBuilder
и аналогичную для run_offline. Конечно, возникает вопрос, почему я не сделал FS и FR трейтами вместо замыканий со стейтом. Ну, так просто получилось меньше церемониального кода с вводом новых типов и описыванием имплементаций, ну и плюс стейта S там в изначальной реализации вообще не было. Соответственно, в реализации клиента нужно было просто вызвать нужный run, передав функции для отсылки и получания сообщений, и всё должно было заработать само.

Дальше я отправляюсь писать всякие тесты для игрового цикла и чата с сервером, в том числе, на основе демонстрационного чата Alice и Bob, который был приведён в конце спеки.

В этом месте мне следует сделать логическое отступление и поразмышлять о тестах в Rust. Дело в том, что на данный момент единственная объективная вещь, из-за которой раст может проигрывать в динамике разработки тому же Common Lisp, Haskell или Erlang -- это отсутствие REPL. Всем, кто уже успел привыкнуть к реплу, должно быть известно, насколько он ускоряет цикл создания нового кода. Особенно роскошен в этом плане CL + Slime, ни один другой репл даже близко к его возможностям даже близко не стоит. И настолько же мучительно потом возвращаться к абстрактному С++ или Java, где ты сначала несколько минут компилируешь программу, чтобы потом две секунды потратить на отлаживание printf-aми -- за это время ты бы успел провести десяток экспериментов в репле, чтобы проверить десяток идей.

Формально, Rust можно было бы причислить как раз к этой категории, если бы не его встроенная поддержка тестов. Эта поддержка на деле получилось насколько удобной, что, по-факту, цикл вида: "написал тест" + "вызвал cargo test" (C-C-t в емаксе) оказывается вполне такой себе заменой репла. Конечно, по интенсивности этот манёвр, всё же, реплу сильно уступает, но надо понимать, что тест-то остаётся "навсегда", в отличие от команды в консоли. Он будет прогоняться каждый раз во время cargo test (и в цикле CI), и, рано или поздно, он потенциально сможет вскрыть какой-нибудь новый недавно спрограммированный баг.

Тем временем Turtle начинает жаловаться в чатик на свой неравный бой с какой-то "арифметикой указателями", и я сразу подозреваю неладное :) Но, так как он упражняется в отдельной ветке, я не придаю его словам значения. Как потом выяснилось, зря.

В девять вечера, когда я возвращаюсь с ужина, обнаруживаю, что Sectoid делает автоматическую сборку сабмишнов, а Игорь доделал сериализацию и десериализацию наших структур данных в json. После небольшого совещания решили, что я попробую быстро спрограммировать сетевой клиент, а Игорь наваяет какой-нибудь базовый солвер, который что-то бы умел захватывать. Без какой-либо специальной стратегии пока, но любой солвер такого плана всяко лучше стратегии постоянного пасования каждый ход :) Игорь решает попробовать захватывать сначала все реки вокруг шахт, и потом все остальные рандомно. Я удаляюсь программировать клиента.

В 21:45 у меня готов клиент, и я обнаруживаю, что на текущий момент у нас уже есть сериализация, протокол, чат, игровой цикл, клиент, и почти готов какой-то солвер. В воздухе отчётливо запахло успешным сабмитом к lightning division :) Я бросаюсь программировать бинари lambda_punter_online и lambda_punter_offline, которые будут точками входа для онлайн и, соответственно, оффлайн реализаций протоколов. Через полчаса Sectoid куда-то убрёл, обещая вернуться в течении двух часов.

В 22:40 у Игоря готов солвер nearest, который столбит ближайшие к руднику реки. В 22:45 я заканчиваю lambda_punter_online который даже, внезапно, заработал с первой попытки! Вот она -- целебная сила написания тестов параллельно с разработкой :) Через веб-интерфейс оргов я даже умудряюсь сыграть со своим ботом. Это, конечно, всего лишь always_pass солвер, который каждый ход пасует, поэтому я разгромил его в пух и прах. В честь этой победы я ухожу дорабатывать lambda_punter_online (и, соответственно, -offline), чтобы можно было выбирать используемый солвер с помощью параметров командной строки.

В 23:17 мне это удаётся, и на карте sample.json я играю с нашим ботом уже вничью! Предлагаю в чате всем присоединиться к тестированию бота:

RUST_LOG=lambda_punter=debug,lambda_punter_online=debug cargo run --release -- --server-port 9002 nearest
В этот момент на связь снова выходит Turtle со своей "адресной арифметикой" в Rust. После краткого допроса выясняется, что он так и не смог освоить теорию про заимствования и владения в языке, и пытается программировать путём буквального следования подсказкам компилятора, который, в свою очередь, тщетно пытается угадать, что его хозяин имеет в виду :) Основная проблема заключается в том, что эти понятия в расте основополагающие, поэтому, судя по всему, особо много полезного кода Turtle'у породить не удастся.

В 23:33 из эфира пропадает Игорь, а я отправляюсь доделывать lambda_punter_offline, чтобы у нас был хотя бы один рабочий сабмит для лайнтнинга. Попутно, правда, пришлось оторваться на чат с Turtle'ом про то, как делать разное на Rust, а потом мне вообще нужно временно удалиться.

Вплоть до 01:30 мы с Turtle'ом усиленно учим Rust в ускоренном темпе, а в 1:40 я заканчиваю первую версию бинаря для оффлайна. Буквально через 10 минут организаторы апдейтят задание: появляются фьючерсы на маршруты. Тем, кто играл в паровозы должна быть понятна аналогия с карточками маршрутов, которые раздаются в начале игры (из которых можно выбрать какие хочешь). В ICFPC смысл точно такой же: на этапе инициализации игрок имеет право объявить несколько (от нуля до количества шахт) маршрутов, которые он обязуется выполнить. Получилось -- зарабатывает большой бонус, не получилось -- получает такой же большой штраф. В принципе, всё понятно :)

Тем временем Sectoid'а всё нет в эфире, и мы с Turtle'ом пытаемся понять, как собрать сабмишн. Формально-то lambda_punter_offline у меня готов, а сабмишна-то у нас нет.

В 02:46 всё-таки появляется Sectoid и обязуется сварить сабмишн. Все уже к этому довольно медленные и тупят (особенно я). Ещё через десять минут организаторы выкладывают программку-адаптер между оффлайн и онлайн режимом, с помощью которой оффлайновый клиент можно проверить прямо на игровых серверах. Программка на окамле, которую (кто бы сомневался) мне на макбуке собрать никак не удаётся.

В этом месте я ещё раз хочу сделать отступление, и отдать должное Rust-у. Я имел дело с очень большим количеством языков и их рантаймов, так вот, ответственно заявляю: почти у всего, что бывает в мире, гарантирован геморрой в плане кроссплатформенности. На чём бы вы не программировали большой проект, например, под линуксом -- будьте уверены, что отнести его мак и запустить его с без специальных плясок с первого раза не удастся (не говоря уж об венде, не к ночи будет упомянута). Неважно, хаскель это, лисп или си (особенно c++). Больше всего шансов в этом плане у джавы (хотя там есть свои приколы) и у эрланга (если не использовать порты). Так вот, проект на Rust соберётся в "чужеродной" среде с практически 100%-тной вероятностью. Особо отметим при этом, что раст -- низкоуровневый язык без рантайма.

Вплоть до трёх ночи я мучаюсь с окамловой сборкой, после чего позорно сдаюсь. Через некоторое время Turtle собирает этот адаптер у себя в виртуалке, а мне любезно даёт туда ssh.

Хоть все уже и тупят просто отчаянно, тем не менее, нам удаётся заметить, что lambda_punter_offline через орговский адаптер lamduct не работает: ошибка в клиенте "Resource temporarily unavailable". Хотя я же проверял руками через stdin/stdout, у меня всё пашет как ожидается. Что может быть увлекательней, чем ремонтировать такого рода баги в половину пятого ночи? :) Я уже было совсем собрался плюнуть и пойти спать.

04:30: пока пойти спать как-то не удалось, поэтому спрограммировал в протоколе поддержку фьючерсов. Вот теперь уже вроде все точно собрались идти спать.

04:40: я неожиданно нагугливаю информацию про "Resource temporarily unavailable" и решаю срочно ремонтировать lambda_punter_offline :) Разумеется, не получается. Хотя суматохи я навёл: Turtle'у надо пересобрать бинарь у себя в виртуалке, а Sectoid'у переварить заново сабмишн.

05:18: внезапно ремонтирую таки. Оказывается, это проблема возникает, когда на том конце пайп установлен в неблокирующий режим. Правда, вместо отремонтированного всплывает другой баг.

05:28: ремонтирую второй баг. Всплывает третий. Меня уже не остановить =)

05:36: ремонтирую третий баг. Всё, наконец заработало! Но, проблема: Sectoid'а нет, сабмишн собрать некому :) К счастью, через пять минут он появляется и сабмишн уходит. Тадам, у нас есть рабочий сабмишн к lightning division. Всё, я ухожу спать.

Продолжение здесь.
satyr

Трамплины и продолжения

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

Давайте, например, посмотрим на такие платформы: Common Lisp/Scheme, Haskell или OCaml. А потом на такие: Java или Javascript. В чём разница? Правильно, в одних есть хвостовая рекурсия, в других нет :)

Ладно, на самом деле, большинству программистов наджави эта рекурсия нафиг не сдалась. Полагаю, что многие и не подозревают даже что это такое, и подобное неведение никак не мешает им вполне комфортно существовать на свете. Но оная проблема встаёт достаточно остро для пользователей более вменяемых языков, которые используют джаву или js в качестве бэкенд-платформы. Например, Clojure для jvm или Elm для javascript. Эти языки предполагают функциональную парадигму программирования, и отсутствие TCO при этом причиняет серьёзные неудобства.

Честно говоря, натолкнувшись на переполнение стека в Elm, я был несколько ошарашен. Ничто не предвещает беды, вокруг тепло и уютно: с одной стороны, у тебя почти хаскель, с другой тебе было обещано отсутствие рантайм-исключений (если ты не выходишь за рамки чистого elm). И тут херак, привет из js:

RangeError: Maximum call stack size exceeded

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

Итак, давайте рассмотрим следующий синтетический пример:


isEven : Int -> Bool
isEven x =
    case abs x of
        0 -> True
        v -> isOdd <| v - 1


isOdd : Int -> Bool
isOdd x =
    case abs x of
        0 -> False
        v -> isEven <| v - 1


isSumEven : Int -> Int -> Bool
isSumEven a b =
    isEven a == isEven b


Я тут попытался смоделировать проблему: у нас есть две взаимно-рекурсивные функции (определяющие, чётное или нечётное число на входе) и одна утилитарная, которая их как-то использует (предсказывает, будет ли сумма двух чисел чётная).

Можно сразу посмотреть в репле, как они (не) работают:


> isEven 2
True : Bool
> isOdd 13
True : Bool
> isSumEven 100 1
False : Bool
> isEven 100000
RangeError: Maximum call stack size exceeded


Как их заставить работать, если платформа не поддерживает TCO? Никак, надо переписывать.

Общепринятая практика использовать в таких случаях технику, которая называется trampolining. Она широко используется, например, в Clojure. Идея там достаточно простая. Мы рефакторим функции, использующие рекурсию таким образом, чтобы:

  1. во всех местах, где производится рекурсивный вызов, вместо этого возвращалось наружу продолжение (достаточно просто обычного замыкания: thunk)
  2. на самом "верхнем" уровне выполняется обычный тупой цикл (trampoline), который последовательно вызывает отрефакторенную функцию до тех пор, пока она возвращает продолжения

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

В Elm, оказывается, есть даже микро-пакетик с трамплинами: elm-lang/trampoline. С его помощью можно переписать вышеприведённые взаимно-рекурсивные функции следующим образом:


import Trampoline exposing (Trampoline, done, jump, evaluate)


isEvenTr : Int -> Trampoline Bool
isEvenTr x =
    case abs x of
        0 -> done True
        v -> jump <| \() -> isOddTr <| v - 1


isOddTr : Int -> Trampoline Bool
isOddTr x =
    case abs x of
        0 -> done False
        v -> jump <| \() -> isEvenTr <| v - 1



В данном случае, всё получается достаточно прямолинейно: когда готов результат, возвращаем его через done, а когда нужно выполнить рекурсивный вызов, оборачиваем его в thunk и возвращаем через jump. Соответственно, в пакете trampoline лежит ещё функция evaluate, которая как раз крутит цикл, вызывая по-очереди все возвращаемые продолжения. Проверяем:


> evaluate <| isEvenTr 2
True : Bool
> evaluate <| isOddTr 13
True : Bool
> evaluate <| isOddTr 100000
False : Bool


Да, в этом варианте всё работает!

Кстати, небольшое отступление. Очевидно, что многим (включая меня) может не понравиться, как выглядит вот этот кусок кода:


jump <| \() -> isOddTr <| v - 1


Лично я его автоматически написал сначала так:


jump <| always <| isOddTr <| v - 1


За что был наказан потерянным часом на отладку. Кто может предположить, в чём кроется засада? :) Для справки: always.

Ладно, возвращаемся к примерам. Как написать трамплин-версию isSumEven? В принципе, можно как-то так:


isSumEvenTr : Int -> Int -> Trampoline Bool
isSumEvenTr a b =
    done <| (evaluate <| isEvenTr a) == (evaluate <| isEvenTr b)


Конкретно для этого синтетического примера, наверно, такой вариант особо ничем не плох. Но всё же: можно ли обойтись только одним evaluate? Очевидно, что можно, если получится каким-то образом "попасть внутрь" типа Trampoline a, чтобы достать значение a или, хотя бы, как-то его преобразовать. Но вот незадача: этот тип не является функтором или монадой, никаких соответствующих комбинаторов для него нет, да и вообще это всё страшные слова, и такой мерзости у нас в эльме не водится! Следовательно, единственный вариант — это честно интерпретировать Trampoline a через evaluate. Или нет?

На самом деле, есть способ "состыковать" несколько Trampoline-ов, чтобы выполнить их в одном цикле-эвалюаторе: опять же, CPS. Но для этого нам опять нужно отрефакторить функции, на этот раз в continuation passing style:


isEvenTrK : Int -> (Bool -> Trampoline Bool) -> Trampoline Bool
isEvenTrK x k =
    case abs x of
        0 -> k True
        v -> jump <| \() -> isOddTrK (v - 1) k


isOddTrK : Int -> (Bool -> Trampoline Bool) -> Trampoline Bool
isOddTrK x k =
    case abs x of
        0 -> k False
        v -> jump <| \() -> isEvenTrK (v - 1) k


isSumEvenTrK : Int -> Int -> (Bool -> Trampoline Bool) -> Trampoline Bool
isSumEvenTrK a b k =
    isEvenTrK a <|
        \resultA ->
            jump <| \() -> isEvenTrK b <|
                \resultB ->
                    k <| resultA == resultB



Главное изменение: функции теперь не возвращают результаты напрямую (логически, они уже ничего не должны возвращать), вместо этого они принимают дополнительные параметр: "продолжение", которому этот результат передаётся. Теперь в isEvenTrK появилась возможность состыковать две "затрамплиненные" функции внутри продолжения, при этом сохранив тип возвращаемого значения Trampoline Bool, который уже скармливается единственному evaluate:


> evaluate <| isSumEvenTrK 100000 1 done
False : Bool
> evaluate <| isSumEvenTrK 100000 100000 done
True : Bool


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

Ну, в целом, как-то так. Далее полагается, чтобы я написал какие-то выводы или подытоги, но какие тут могут быть выводы? Сложно, запутанно. Но это и есть та самая "отложенная сложность", про которую я говорил в начале поста. Был бы в вашем джаваскрипте изначально родной TCO, я бы не писал этот текст, а вместо этого сделал бы что-нибудь полезное.
satyr

Вернуть итератор

А между тем, зацените, в nightly rust научились делать вот так:

#![feature(conservative_impl_trait)]

fn numbers() -> impl Iterator<Item = i32> {
    1 ..
}

Дословно, мы из функции возвращаем некоторый анонимный тип, всё что известно про которого — это то, что он реализует типаж Iterator, ассоциативный тип Item коего установлен в i32.

Выглядит сумбурно, но знающие люди будут со мной солидарны в том, что это единственная вещь, которой не хватало для того, чтобы итераторы было реально удобно использовать. Общеизвестно, что автовывод типов в Rust работает только внутри функции, поэтому нельзя было малой кровью собрать лесенку итераторов и вернуть результат наружу, без обязательного прописывания получившегося типа в сигнатуре. До сих пор в этих случаях людям приходилось использовать либо trait objects:

fn numbers() -> Box<Iterator<Item = i32>> {
    Box::new(1 ..)
}

… что плохо, потому что здесь одна совершенно ненужная аллокация, и итерация через vtable. Либо писать вот так:

fn numbers() -> std::ops::RangeFrom {
    1 ..
}

… что тоже омерзительно, по ряду причин:
  • Надо знать возвращаемый тип, а он может быть сильно составным (и будет, в случае с лесенкой преобразований итератора).
  • Зачастую приходится оборачивать его в newtype, чтобы не экспортировать из модуля кишки (и имплементировать соответствующий Deref).
  • В некоторых случаях тип вообще невозможно прописать руками, например, когда generic биндится замыканием (а тип замыкания нельзя написать руками).

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

Помимо итераторов, данная возможность даст возможность возвращать замыкания перемещением (by move), как-то так:

#![feature(conservative_impl_trait)]

fn adder(a: i32) -> impl Fn(i32) -> i32 {
    move |x| x + a
}

Это ваще космос. По факту можно будет с относительным комфортом писать в функциональном стиле на языке, в котором нет garbage collector (!!), и при этом без сегфолтов и утечек.

Да, и ещё формат ошибок в Rust теперь слизали с Elm, и они теперь выглядят максимально подробно:


Короче, я повторю свою мысль ещё раз: в 2016-м не может быть ни единой причины писать что-то на C++, когда есть Rust. Ну, может, если вы только дорабатываете какой-то уже существующий большой проект. Начинать же сейчас что-то новое на плюсах вообще безумие, никогда так не делайте :)
satyr

Вероятностные алгоритмы.

Введение.

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

Задание было придумано очень крутое. "Очень крутое" -- это, в моём понимании, такое задание, которое:

  1. Имеет практическую ценность.
  2. Не подразумевает одного единственного верного решения, до которого просто нужно додуматься в процессе конкурса.

Полностью условие можно почитать на офсайте, а вкратце оно звучит так:

  • Дан словарь из ~660k записей. Ориентировочно, это английские слова.
  • Надо написать функцию "test(word)", которая возвращает true, если заданное слово входит в словарь, и false, если нет.
  • Суммарный объём программы и файла с данными, которым она может пользоваться, не должен превышать 65536 байт.
  • Побеждает решение, которое даст максимальный процент правильных ответов на большом количестве тестов.

Чтобы было повеселее, в тестах используется специальный генератор слов, которые визуально (и грамматически) очень похожи на нормальные английские, но при этом в словаре их нет, например: "goldrunk". И, напротив, в заданном словаре есть весьма странные записи, в которых распознать английский язык очень сложно, например, "qwertys" или "rRNA".

Согласно комментариям участников в соответствующем треде на хабрахабре, основные идеи (успешных) решений были следующие:

  • Максимальное обрезание словаря, выделение значащих префиксов/суффиксов/нграмм, и последующее запихивание всего этого в фильтр Блума.
  • Машинное обучение. В основном, это разновидности деревьев решений.
  • Решения, воссоздающие словарь из тестовых данных в рантайме.

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

Немного теории.

В статье на русскоязычной википедии говорится, что: "Вероятностный алгоритм — алгоритм, предусматривающий обращение на определённых этапах своей работы к генератору случайных чисел с целью получения экономии во времени работы за счёт замены абсолютной достоверности результата достоверностью с некоторой вероятностью". Это не совсем так -- принципиально, к ГСЧ в вероятностных алгоритмах обращаться необязательно. В англоязычной версии этой статьи есть более корректное определение: "uniformly random bits". Опять же, экономия может достигаться не только во времени работы, а по памяти, например.

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

Соответственно, возможность такого рода компромисса в постановке задачи (значительный выигрыш по ресурсам взамен некоторой допустимой недостоверности ответа) может быть хорошим признаком того, что в решении имеет смысл использовать вероятностный алгоритм. Например, это конкурс про упаковку огромного словаря в 64Kb :)

Самое главное, что здесь нужно запомнить, это фразу: дискретно-равномерное распределение. "Равномерное распределение" на практике должно означать следующее: если случайная величина (ГСЧ, хэш-функция, значение сигнала) генерирует нам какое-то значение из интервала R, нужно, чтобы вероятность получения каждого значения из R была 1/R (или, хотя бы, очень близко к этому). При этом количество таких значений должно быть конечно (дискретно). Визуально, это выглядит следующим образом: допустим, мы взяли поле 10x10 и ткнули в рандомную точку. Получилось, например, как-то так:

А если мы воткнули их несколько тыщ, то должно получиться относительно равномерное покрытие, что-то типа такого:

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

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

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

Немного практики.

Из популярных практических алгоритмов для подобного рода задач я бы хотел отметить, например, такие:

  • Locality-sensitive hashing: подбирает для множества элементов хэш-функцию таким образом, что "схожие" элементы попадают в одну корзину (хеши дают коллизию ожидаемым образом). Таким образом достигается существенное уменьшение размерности данных, и используется, например, в задачах кластеризации.
  • MinHash: ускорение расчёта коэффициента Жаккара для вычисления степени схожести двух множеств. Широко используется, например, для задач выявления нечётких дубликатов среди большого количества документов.
  • Семплирование потока данных. В отличие от простой выборки каждого N-ого элемента из потока, хешируют некоторый составной ключ (например, "пользователь"/"запрос"/"таймстамп"), после чего берут N корзин, и отбрасывают все результаты, не попавшие в одну из них. Это позволяет семплировать поток по сложным условиям, избегая дорогостоящей группировки.
  • Flajolet–Martin algorithm, и его развитие в виде HyperLogLog. Алгоритмы используют достаточно изящный хак для быстрой аппроксимации количества уникальных элементов в заданном множестве. Я реально советую ознакомится с описанием, это, действительно, хитрый трюк :)

Конкурсная задача.

Вернёмся к задаче про словарь. Итак, уже в условии однозначно написано про компромисс "допустимая недостоверность в обмен на ограниченные ресурсы". Следовательно, задачу можно пробовать решать вероятностным алгоритмом.

Самый простой вероятностный алгоритм, который можно придумать, это подбрасывание монетки:

function test(word) {
    return Math.random() < 0.5;
}

Несложно догадаться, что он совершенно бесплатно даёт нам 50% правильных ответов, при этом даже не пользуясь своим аргументом :) Соответственно, это значение будет базисом, с которым можно сравнивать результативность других алгоритмов.

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

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

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

Применив K таких случайных хеш-функций к одному и тому же аргументу (например, слову из словаря) мы получим K результатов, которые будут, опять же, случайно распределены по всему диапазону значений fnv. Я взял 32-х битную версию, соответственно, результаты хеширования будут в диапазоне 0 - 0xffffffff. Дальше надо как-то убедиться, что эти результаты имеют равномерное распределение. Этот факт явно каким-то образом должен доказываться, но я, к сожалению, не математик, поэтому тупо нарисовал график и посмотрел на него глазами. Выглядит как равномерное :) Это свойство в данном случае мне важно для того, чтобы можно было оценить вероятность того, что случайная хэш-функция даст конкретное значение. При равномерном распределении эта вероятность будет 1/R, где R = 232.

Дальше сделаем вот что: возьмём одну такую случайную хеш-функцию H, и прогоним через неё все N слов из словаря. Получим N чисел (хешей слов), которые как-то случайным образом будут раскиданы в интервале от 0 до 232 - 1. Теперь нам надо найти какое-то такое утверждение P, которое бы:

  1. Выполнялось бы для всех полученных чисел.
  2. Не выполнялось для как можно большего количества остальных чисел из [0, 232).

Идея понятна: алгоритм получает слово, считает от него хеш с помощью хеш функции H, проверяет результат на условие P, и, если оно ложно, то это слово точно не из словаря. Если условие истинно, то слово, с какой-то вероятностью, может быть в словаре. С какой? Это зависит от природы утверждения P. Далее нам достаточно провести несколько проб (повторить алгоритм несколько раз для различных хеш-функций), с каждым разом увеличивая вероятность срабатывания P, чтобы достичь удовлетворяющей нас достоверности ответов.

Допустим, к примеру, сложилось такая ситуация, что все хеши слов из словаря оказались чётными. Тогда все нечётные значения из интервала от 0 до 232 означали бы true negative. Вероятность этой ситуации (хеш проверяемого слова оказался нечётным) была бы почти 0.5 -- это очень крутой результат для одной только пробы. Ведь тогда нам для достоверности ответа "слова точно нет в словаре" в 99% достаточно log0.50.01 = ~7 проб, то есть, всего семь рандомных хеш-функций.

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

Конкретно под наш словарь можно попробовать делить всё множество значений хеш-функций не на две корзины (чётные и нечётные числа), а на большее количество: M > 2. Тогда нашей задачей будет подобрать для каждой используемой хеш-функции такое (в идеале, минимальное) количество корзин, чтобы при хешировании всех слов из словаря одна из корзин оказалась пустой.

Если значения хеш-функций имеют равномерное распределение (а они имеют в нашем случае), вероятность попадания хеша в одну из корзин будет равняться 1/M. Каким же должен быть M, чтобы, раскидав по этому такому количеству корзин 660 тысяч хешей, у нас бы осталась одна пустая корзина? Это как-то явно подсчитывается при помощи математики, но (если вы, подобно мне, ничерта не помите из тервера) можно немного схалтурить, и получить нужные цифры при помощи несложного программирования.

Проведём эксперимент: сгенерируем нужное количество 32-х битных случайных чисел, по одному на слово из словаря -- как будто, это результаты хеширования. Программный ГСЧ должен давать равномерное распределение, и хеш-функция тоже даёт равномерное распределение, так что это относительно равноценная замена. Далее тупо брутфорсом попробуем подобрать минимальное количество корзин так, чтобы в одну из них ни одно рандомное число не попало. Вот как это примерно может выглядеть на Common Lisp:

(defun get-minimum-buckets-count (words-count)
  (iter
    ;; generate pseudo hashes
    (with pseudo-hashes =
              (iter (repeat words-count)
                    (collect (random (ash 1 32)) result-type simple-vector)))
    (for buckets-count from 2)
    ;; make buckets with hit counters
    (for buckets-hits =
         (make-array buckets-count
                     :element-type 'fixnum
                     :initial-element 0))
    ;; collect hits
    (iter (for i from 0)
          (for hash in-sequence pseudo-hashes)
          (for bucket = (mod hash buckets-count))
          (incf (elt buckets-hits bucket)))
    ;; check whether an empty bucket exists
    (for empty-bucket = (position 0 buckets-hits))
    (when empty-bucket
      (return-from get-minimum-buckets-count
        (values buckets-count empty-bucket)))))        

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

Запустив эту функцию для 660000 слов, мы (через некоторое время) получим результат для M порядка ~33000. Разумеется, при каждом запуске он будет разный (так как псевдо-хеши генерируются каждый раз случайным образом), но это будут всегда приблизительно одинаковые значения с небольшим разбросом. На практике это означает, что мы можем получить с одной пробы вероятность 0.00003, что слово не входит в заданный словарь: для этого достаточно проверить, что хеш слова попал в пустую корзину. На первый взгляд совсем мизерный шанс, но давайте прикинем, что с этого можно получить.

Итак, мы можем взять одну рандомную хеш функцию H0, словарь, и найти для них два числа: M0 (минимальное количество корзин, раскидывая хеши по которым образуется одна пустая), и B0 (номер пустой корзины). Эти два числа описывают пробу P0, которая даёт шанс в 0.003%, что проверяемое слово точно не принадлежит словарю. Если же мы посчитаем таким же образом P1 для другой функции H1, мы сможем провести две независимые пробы, увеличив вероятность true negative до 0.00006 (вероятность не попасть в пустую корзину для одной пробы равняется 1.0 - 0.00003 = 0.99997, а для двух независимых проб вероятности умножаются). Аналогично, десять подобных проб дадут уже вероятность в 0.03%, сто в 0.3%, а десять тысяч, например, целых 26.1%. Продолжая этот ряд, можно подобрать число 153000 -- именно столько проб нужно выполнить, чтобы с вероятностью 99% определить true negative.

Одна проба однозначно задаётся двумя числами M и B, соответственно, для 150-ти тысяч проб нужно сохранить 300 тысяч чисел. Это явно больше того, что можно запихать в заданные задачей лимиты. Нетрудно прикинуть, что, если мы аллоцируем, ориентировочно 14 бит для M и 15 бит для B, в 64 Kb можно вместить всего порядка 18000 проб. А ведь там ещё должно остаться какое-то место для сценария на js! Соответственно, чуть более реалистичная цифра в 17000 проб даст вероятность определения true negative в ~40%.

Что это означает на практике? Это означает следующие вещи:

  • Если на вход функции test было подано слово из словаря, все пробы будут успешными (хеши не попадут в пустые корзины), и будет возвращена истина. Это true positive.
  • Если на вход функции test было подано слово не из словаря, то:
    1. с вероятностью 40% одна из проб даст неуспех (один из хешей попадёт в пустую корзину), и будет возвращена ложь. Это true negative.
    2. с вероятностью 60% все пробы, всё же, дадут успех, и будет возвращена истина. Это false positive.
  • Ситуация false negative в данной конфигурации невозможна, потому что мы, формируя множество проб, специально так подбирали числа M, чтобы для слов из словаря обязательно оставалась пустая корзина.

Итоговый процент верных ответов зависит от характера тестовых данных: в худшем случае он будет стремиться к 40% (если на вход подаются только слова не из словаря), в лучшем -- к 100% (если на входе только слова из словаря), а в случае половина тех, и половина других, это должно быть значение порядка 70%.

Эту цифру можно чуть-чуть улучшить, параллельно значительно упростив формат сериализованной пробы (что тоже немаловажно, ведь размер js-скрипта тоже имеет значение). Можно подбирать M специальным образом, чтобы пустая корзина оказывалась всегда, например, в нулевой позиции (B == 0, или H % M == 0). В этом случае для записи пробы нам достаточно только одного числа M. Эксперименты показывают, что это получаются значения из диапазона примерно 38000 - 91000: это означает, что соответствующие вероятности для проб будут меньше, но зато для их упаковки теперь достаточно 16 бит, следовательно количество проб можно увеличить до ~32000, и, главное, сильно упростить код для их упаковки/распаковки.

Конечно, полученная цифра в 70% верных ответов выглядит не очень впечатляюще. Но следует отметить две вещи про это решение:

  1. Удивительная простота алгоритма в целом, и элементарная масштабируемость: для достижения нужной точности нужно просто последовательно увеличивать количество проб.
  2. Это абсолютно "чистый" и "честный" результат: на нетронутых оригинальных входных данных, когда словарь взят полностью как есть. Всегда можно приложить некоторые усилия к препроцессингу: порезать слова, оканчивающиеся на "'s", разделить на префиксы/суффиксы, и т.п. Ребята в комментариях к задаче на хабрахабре писали, что они относительно безболезненно уменьшали словарь до 280000 записей. А 280 тысяч хешей в нашем алгоритме уже означают M ~ 13000, что, в свою очередь, даёт вероятность одной пробы 0.0076% и порядка 18000 проб в 64 Kb, выдающих, суммарно, почти 75% true negative! А это уже больше 87% верных ответов для случая 50/50 словарных и не словарных слов.

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

Полностью моё решение, вместе с расчитанными данными, можно взять в этом репо: сами хеши я породил из js (директория generator), а компилятор проб из них сделал на Rust (директория compiler).

satyr

Геймификация скучных процессов

13 апреля я опубликовал пост с текстом интересной, как мне тогда казалось, вакансии, и он провисел неделю. Много ли за эту неделю заинтересовалось ей людей? Нуль!
19 апреля я предложил развлекательную тестовую задачку для потенциальных кандидатов и им сочувствующих, и внезапно за одну такую же неделю мне наприсылали какие-то полчища резюме, что я даже немного впал в ступор :) Честно говоря, начал даже понимать профессиональных эйчаров, это не такая уж и простая работа, оказывается.

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

Задачка для интересу

Чёто вакансия вызвала интерес у удивительно малого количества народу, я даже затрудняюсь объяснить этот феномен :) Все так недолюбливают Эрланг? Но у меня же ещё Elm и Rust, и вообще, потенциально определённая свобода в этом плане. Пишите, когда ещё вам предложат попрограммировать с пользой на чём-то неунылом за деньги :)

Для подогрева интереса к вакансии выкладываю тестовую задачку для потенциальных кандидатов. А то чё я её зря что ли придумывал.
UPD 2016-04-20: добавил "sample_9".
UPD 2016-04-21: пофиксил рефенсные тайминги.

Итак, задачка из трёх частей, в порядке увеличения сложности. Делать надо на эрланге, если умеете эрланг, или на чём угодно, если не умеете. Ориентировочные критерии оценки такие:
  • Если человек сделал первую часть, то хорошо: с ним уже есть о чём говорить.
  • Если получилась вторая — очень хорошо.
  • Если третья — совсем круто!

Общее условие

Дана программа в виде упрощённого S-expression (что это?), например:

sample_1() -> <<"(+ (* 4 4) (* 2 (- 7 5)) 1)">>.

где первый элемент каждого списка — это операция (всего их три вида):
  1. сложение: атом "+"
  2. вычитание: атом "-"
  3. умножение: атом "*"
Все остальные возможные атомы — это целые числа.
Ещё примеры:

sample_2() -> <<"10">>.
sample_3() -> <<"(* 10 (- 0 1))">>.
sample_4() -> <<"(- (+ 10 10) -5 0)">>.
sample_5() -> <<"(+ (- (* (+ (- (* 1))))))">>.
sample_6() -> <<"(* 2 (+ (- 10 9) (- 3 (* 2 1))) (+ (- 10 9) (- 3 (* 2 1))))">>.
sample_7() -> <<"(+ (* 2 1) (+ 8 8) (- (+ 4 3 2 1) (* 3 3) (* 2 2)) (* 5 7))">>.
sample_8() -> <<"(- (+ (+ 3 3) (- 3 3) (+ 3 3) (- 3 3)) (* 2 2))">>.
sample_9() -> <<"(+ (- 6 1) (+ 0 1 1) (- 7 2) (* 3 4 5) (- 3 1) (+ 2) (- 0 10))">>.

Задача 1

Реализуйте функцию-интерпретатор "interpret/1" и вычислите результаты вышеприведённых программ.

Например:
interpret(sample_1()). --> 21
interpret(sample_2()). --> 10
interpret(sample_3()). --> -10
interpret(sample_4()). --> 25
interpret(sample_5()). --> 1
interpret(sample_6()). --> 8
interpret(sample_7()). --> 50
interpret(sample_8()). --> 8
interpret(sample_9()). --> 66

Задача 2

Представим, что все операции в программе имеют константную задержку, которая не зависит от процессора. Например, это некоторого рода длительная сетевая активность.
Итого, реализация каждой из операции теперь должна содержать вызов "timer:sleep(X)":
  • X = 2000 ms для сложения "+"
  • X = 3000 ms для вычитания "-"
  • X = 10000 для умножения "*"

Реализуйте функцию-интерпретатор "interpret_network/1", которая вычисляет результат заданной программы с минимально возможной задержкой.

Например:
interpret_network(sample_1()). --> 21 (delay 15 s)
interpret_network(sample_2()). --> 10 (delay 0 s)
interpret_network(sample_3()). --> -10 (delay 13 s)
interpret_network(sample_4()). --> 25 (delay 5 s)
interpret_network(sample_5()). --> 1 (delay 30 s)
interpret_network(sample_6()). --> 8 (delay 25 s)
interpret_network(sample_7()). --> 50 (delay 15 s)
interpret_network(sample_8()). --> 8 (delay 13 s)
interpret_network(sample_9()). --> 66 (delay 12 s)

Задача 3

Представим, что все операции в программе имеют константную задержку, которая зависит от процессора. Например, это некоторого рода тяжелые вычисления, выедающие 100% ядра процессора.
Наша машина оборудована N физическими ядрами.
Итого, реализация каждой из операции теперь должна содержать вызов "timer:sleep(X)", при этом максимальное количество "одновременно выполняющихся" операций должно быть меньше или равно N:
  • X = 2000 ms для сложения "+"
  • X = 3000 ms для вычитания "-"
  • X = 10000 для умножения "*"

Реализуйте функцию-интерпретатор "interpret_cpu/2", которая, используя процессор максимально оптимальным образом, вычисляет результат заданной программы с минимально возможной задержкой.

Например:
interpret_cpu(sample_1(), 2). --> 21 (delay 15 s)
interpret_cpu(sample_2(), 2). --> 10 (delay 0 s)
interpret_cpu(sample_3(), 2). --> -10 (delay 13 s)
interpret_cpu(sample_4(), 2). --> 25 (delay 5 s)
interpret_cpu(sample_5(), 2). --> 1 (delay 30 s)
interpret_cpu(sample_6(), 2). --> 8 (delay 28 s)
interpret_cpu(sample_6(), 3). --> 8 (delay 25 s)
interpret_cpu(sample_7(), 2). --> 50 (delay 26 s)
interpret_cpu(sample_7(), 3). --> 50 (delay 22 s)
interpret_cpu(sample_7(), 4). --> 50 (delay 15 s)
interpret_cpu(sample_8(), 2). --> 8 (delay 15 s)
interpret_cpu(sample_8(), 3). --> 8 (delay 13 s)
interpret_cpu(sample_9(), 2). --> 66 (delay 15 s)


Приглашаю всех желающих порешать, код выкладывайте на какой-нибудь gist и давайте ссылку в комменты. Свой вариант я выложу ближе к концу недели.
satyr

А вот, например, вакансия.

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

От кандидата требуется:
  • Знание, или устойчивое желание и возможность освоить Erlang + OTP.
  • Знание основных паттернов проектирования систем обмена сообщениями.
  • Опыт сетевого программирования.
  • Навыки работы с linux.

Плюсами будут:
  • Опыт проектирования и разработки высоконагруженных сервисов.
  • Опыт работы с большими объёмами данных.
  • Знание функциональной парадигмы программирования.
  • Знание языков (или желание освоить) Elm и Rust.
  • Опыт работы с:
    • RabbitMQ
    • Apache Cassandra
    • Redis
    • cowboy http server
  • Навыки работы с freebsd.

Работа на полный рабочий день: по желанию либо в офисе (Москва, ул. Верейская), либо удалённо, с регулярным посещением офиса для совещаний. Белая зп, 130-250к (вилка большая, крутому и матёрому спецу тоже будем рады).

Если интересна вакансия, пишите мне на почту (с резюме в аттаче), если знаете кого-то, кому может быть она интересна — рассказывайте! Общие вопросы пишите лучше сюда в комменты, чтобы мне не копипастить по письмам ответы.
satyr

Ещё об обработке ошибок в Rust

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

Давайте рассмотрим процесс на простом примере: допустим, бинарю на вход подаётся (или не подаётся) параметр такого вида:

~ $ ./a.out --sample 2,3,4.5,6.0,7

Соответственно, если всё хорошо, в программе мы хотим получить какой-то вектор действительных чисел.

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

Итак, getopts вернул нам Option<String>, как нам получить из него Vec<f64>? Очевидно, что можно гопническим методом:

fn parse_sample_v0(param: Option<String>) -> Option<Vec<f64>> {
    param.map(|values| values.split(',').map(|v| v.parse().unwrap()).collect())
}

Понятно, что программа вылетит в panic на unwrap, если на вход подать мусор. Но есть множество случаев, когда это вполне допустимо (тем более, при панике будет какая-никакая диагностика, из которой можно понять причину проблемы). Удобно при прототипировании, или при разработке небольших утилит.

Однако, такой подход уже недопустим когда надо сделать библиотеку, или в других случаях, когда нельзя валить программу. Какая тогда должна быть правильная сигнатура? Вероятно, какая-то такая:

#[derive(Debug)]
enum ParamError {
    SampleValue(String, ParseFloatError),
}

fn parse_sample_v1(param: Option<String>) -> Result<Option<Vec<f64>>, ParamError> {

Тоесть результат выполнения функции может быть один из следующих вариантов:
  • Успех: результата нет (параметр не был задан).
  • Успех: результат Vec<f64> есть (параметр задан).
  • Ошибка: параметр задан, но не может быть распаршен.
    • В этом случае надо пробросить наверх информацию о том, какое именно число в векторе не распарсилось, и ошибку из метора parse.

Реализация функции с такой сигнатурой "в лоб" приводит к достаточно развесистому дереву условий:

fn parse_sample_v1(param: Option<String>) -> Result<Option<Vec<f64>>, ParamError> {
    if let Some(values) = param {
        let mut result = Vec::new();
        for value in values.split(',') {
            match value.parse() {
                Ok(v) => 
                    result.push(v),
                Err(e) =>
                    return Err(ParamError::SampleValue(value.to_owned(), e)),
            }
        }
        Ok(Some(result))
    } else {
        Ok(None)
    }
}

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

Воспользуемся реализацией FromIterator для Result, и всяким около-монадическим добром типа Result::map:

fn parse_sample_v2(param: Option<String>) -> Result<Option<Vec<f64>>, ParamError> {
    param.map(|value| value.split(',')
              .map(|value| value.parse().map_err(|e| ParamError::SampleValue(value.to_owned(), e)))
              .collect::<Result<_, _>>())
        .map(|r| r.map(|values| Some(values)))
        .unwrap_or(Ok(None))
}

Как переписать ещё короче, я не знаю.

И, хотя код здесь сократился в три раза, всё равно получается плохо. Потому что, по-сути, в этом сниппете из пяти строк кода, значимых реально две. А последние три суть церемониальный код, не делающий ничего, кроме переоборачивания типов в другие типы. Причём, с высокой долей вероятности, весь этот код будет тупо выкинут транслятором при инлайнинге, и весь его смысл чисто формальный: преобразовать один ADT в другой, путём приписывания пары конструкторов. Я, конечно, не уверен, но у меня есть смутное ощущение, что компилятор в силах с этим справиться сам :)

Как здесь сделать правильно — я не знаю. Без поддежки HKT в языке не хватает абстракции, чтобы сделать "красивые" монады, а без них непонятно как правильно реализовать сахар типа do. В языке существует ещё механизм из синергии макроса try! с трейтом-преобразователем From, для конвертации одних типов ошибок в другие. Но он реально упрощает только случаи с "плоским" кодом (в пределах одной функции с явными циклами), но как только у нас появляются замыкания (цепи итераторов или модификация внутри деревьев Option/Result), вариант с try! уже не помогает.

Просто я к чему: люди уже сильно избалованы подходом, когда можно тупо писать happy path, и вообще класть болт на обработку ошибок. Но для этого нужны исключения, а для них нужен рантайм и сборщик мусора, от чего в Rust как раз пытаются уйти. Я не знаю, правильно ли будет активно перенимать опыт из хаскеля (насколько я знаю, там аккуратно обрабатывать ошибки тоже не очень любят ;)) — не факт, что для нефункционального языка это получится удобно. Скорее всего, нужно просто брать текущую систему, и специальными расширениями в самом языке уменьшать количество церемониального кода, которое требуется сейчас для корректной обработки ошибок. Например, внести какую-нибудь волшебную директиву "удовлетворить компилятор", которая сама преобразует заданный тип в такой, который нужен согласно сигнатуре :)