Russian Lambda Planet

23 сентября 2016

darkus

Сентябрьский конкурс по ФП: систематизация знаний

Ура! Конкурс по функциональному программированию запущен. Сегодня задача связана с построением систем знаний по лекарственным средствам. Это не только увлекательно, но и полезно. Я бы сказал, что душеспасительно. Так что принимайте участие. Подарки будут. Возможно, не только от меня.

Адрес конкурса: http://haskell98.blogspot.ru/2016/09/blog-post.html

23 сентября 2016, 07:35

22 сентября 2016

Фонд Поддержки Функционального Программирования

Сентябрьский конкурс по ФП: систематизация знаний

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

Вот здесь вы найдёте список ссылок. По каждой ссылке имеется описание одного лекарственного средства. Например, вот описание Кофеина. Необходимо:

1. Скачать все описания.

2. Распарсить их таким образом, чтобы на выходе с парсера для каждого описания был список пар вида (ключ, значение), где ключом выступают заголовки разделов в описании (или, что то же, ссылки в содержании), а значениями выступают тексты после соответствующего заголовка и до следующего. Кстати, из заголовков необходимо удалять наименование вещества.

3. Объединить все распарсенные описания в огромную таблицу (матрицу), строками в которой являются ключи, а столбцами — наименования лекарственных средств. В ячейках матрицы, для которых не нашлось пары в описаниях, необходимо ставить прочерк «—». После формирования матрицу необходимо записать в формате CSV и кодировке UTF-8 без BOM в файл, который и прислать в качестве результата конкурса.

Дерзайте. Вопросы задавайте в комментариях. Победителя определим по полноте представленного файла. И победитель получит в качестве приза мою книгу про квантовые вычисления с автографом. Ну и ещё что-нибудь придумаем для победителя и всех участников.

написал Dark Magus (noreply@blogger.com) 22 сентября 2016, 23:11

21 сентября 2016

Adept

ICFPC-2016: afterparty

Организаторы выложили результаты

Моя скромная команда сползла с 19-го места на 22-е (все равно, я считаю, офигенно для этого подхода к решению).

Первое место, как и в прошлом году, взяли Unagi и вот тут можно посмотреть, как работает их солвер.

Lightning round полностью вручную взял jabber.ru, как уже было, кажется, в 2007-м году.

21 сентября 2016, 21:17

20 сентября 2016

Scala@livejournal.com

К предыдущему

Вот скажем, у нас есть QueryParams (что-то вроде Map[String, String]), из которого нужно создать инстанс класса Employee(name: String, age: Int).

Иными словами, имеются функции QueryParams => Try[String] и QueryParams => Try[Int], а из них нужно построить функцию QueryParams => Try[Employee].

Если немного обобщить, то выходит, что у нас есть разные функции вида fа: QueryParams => Try[A], fb: QueryParams => Try[B], и fc: QueryParams => Try[C], а в результате нужно получить fabc: QueryParams => Try[ABC], где ABC это произведение типов A, B, и C.

Предположим теперь, что мы хотим аккумулировать ошибки валидации. Тогда удобнее заменить Try на scalaz.\/ и получится что-то вроде:
import scalaz._
type Result[T] = Exception\/T 
val fa: QueryParams => Result[A] = ...
val fb: QueryParams => Result[B] = ...
val fc: QueryParams => Result[C] = ...

case class ABC(a: A, b: B, c: B)

type ResultNel[T] = NonEmptyList[Throwable]\/ABC

val fabc: QueryParams => ResultNel[ABC] = qp => {
  val va = fa(qp).validation.toValidationNel
  val vb = fb(qp).validation.toValidationNel
  val vc = fc(qp).validation.toValidationNel
  ((va |@| vb |@| vc)(ABC)).disjunction 
}
Теперь вопросы:

Можно ли сделать то же самое попроще ? (Я понимаю, что с Result из ScalaKittens можно избежать преобразований \/ в Validation и обратно, но хотелось бы использовать только "стандартные" средства).

Так и придётся расписывать вручную для всех конкретных типов A, B, C, и ABC или можно как-нибудь избавиться от boilerplate ?

написал Michael 20 сентября 2016, 18:43

17 сентября 2016

Максим Сохацкий

STREAMS: gen_server will be recorded, stay tuned.

Решил я все-таки написать уничтожитель SSD дисков свою библиотеку аппенд бинари логов. Одна есть неплохая в составе hanoidb, а вторая неплохая в составе rafter имплементации которая включена в cr. В мире сишечки есть eblob в организации reverbrain, которая юзается в Coub, Sputnik и других яндексах. Что хочется от этой библиотеки?

1. Максимум в два раза падение по сравнению с физической на блочном устройстве. Да, конечно хочется интеловские SSD SDK для прямого управления контроллером посекторным, но это будет работать только на линуксе.

2. Простая и понятная привязка к эрланг процессу, т.е. мы стримим все эффекты эрланг процесса. Сколько эфектов навешано на процесс, столько и цепочек. Каждая цепочка отдельный файл. Т.е. N очередей ограничено (например N=500, для сервисов кольца [vnode] ). Это не должно скейлиться на миллионы. Кстати для кольца должна быть отдельная библиотека synrc/ring (вакантное название, желательно из трех букв), которая по заданному имени и степени двойки генерирует совместимые наборы vnode в хеш-кольце и стартует для них по одному gen_server. Эти сервера тоже персистентные, как и цепочки master_node серверов. Т.е. DHT — это просто pub sub такой (пока на эрланг ремоутинге, его обещали в R20 починить и заскейлить до 100 нод лохобаны эриксоновские), где все всё пишут и могут работать в зависимости от CAP конфигурации по разных протоколах-алгоритмах. Алгоритмы эти не влияют никак на библиотеку кольца. В идеале конечно было бы на каждую vnode свой SSD диск. Также vnode могут выступать и в виде виртуальных машин которые уже держат по отдельному процессу для каждого пользователя. Но это хай-энд, незнаю или кто-то уговорит меня такое сделать. Как алоцировать vnode — это отдельный вопрос к трактовкам цепочных схем хранения. Тут тоже могут быть свои протоколы.

3. Эта библиотека должна стать системообразующей наравне с новым gen_server+streams — это как пи и сигма (одно работает, второе пишет), поэтому примитивы должны быть хорошо проработаны чтобы составить основу для EXE примитива персистентного процесса. Это персистентные видимые и индексируемые эффекты процесса. Т.е. — это как примитивная сущность виртуальной машины рассматривается, а не как прикладная библиотека. По крайней мере должно так быть.

Я собрал PoC:
>  boot:test(boot:start(1)).
flush: {{<<99,97,108,1,2,3,4,5,6,7,8,1,1,1,1,1>>},
        {ecirca,#Ref<0.0.3.168>,<<>>,<0.196.0>,medium}}
2000100 messages sent in 2s with 847824 m/s rate
Disk write performance: 170 MB/s
ok

Если склеивать сообщения таким образом (буферезировать):
append(Circ,Record) -> <<(term_to_binary(Record))/binary, Circ>> .

То процесс вообще виснет. Если склеивать с помощью листов:
append(Circ,Record) -> [term_to_binary(Record)|Circ].

То упираемся в фольклерные эрланговые 50MB/s. Но если взять библиотеку si14 ecirca:
append(Circ,Record) -> ecirca:push_list(Circ, binary_to_list(term_to_binary(Record))).

То мы уже можем достигать 250МБ/s — это половина линейной сторости моего SSD. С учетом на виртуальную машину и операционную систему (в два раза !!!!). А вы говорите зачем юникернелы.



Есть еще идея писать выровненные данные по колонкам. Но тогда без компрессии. Но зато с мнгновенными операциями get/put, так как оффсет высчитывается по номеру сообщения.

Заметьте, что хотя эрланговый процесс через себя пропускает миллион сообщений, будучи склеинные в цепочки (cons) эти сообщения могут записываться при максимальном рейте 50MB/s. Вот такой эрланговый лимит. Так что либо ecirca либо emmap. Я выбрал ecirca так как она менее системнозависима, ecirca работает только с BIF эрланговыми, а emmap с API ОС.

P.S. Писал я все это на конференции http://OSDN.org.ua, которая сегодня была. Там Влад опять рассказывал про zalora/upcast который оказывается сменили на terraform.

17 сентября 2016, 17:32

13 сентября 2016

12 сентября 2016

11 сентября 2016

Anton Salikhmetov

Token-passing Optimal Reduction with Embedded Read-back

http://dx.doi.org/10.4204/EPTCS.225.7

Token-passing Optimal Reduction with Embedded Read-back
Anton Salikhmetov

We introduce a new interaction net implementation of optimal reduction for the pure untyped lambda calculus. Unlike others, our implementation allows to reach normal form regardless of the interaction net reduction strategy using the approach of so-called token-passing nets and a non-deterministic extension for interaction nets. Another new feature is the read-back mechanism implemented without leaving the formalism of interaction nets.

In Andrea Corradini and Hans Zantema: Proceedings 9th International Workshop on Computing with Terms and Graphs (TERMGRAPH 2016), Eindhoven, The Netherlands, April 8, 2016, Electronic Proceedings in Theoretical Computer Science 225, pp. 45–54.
Published: 10th September 2016.

comment count unavailable comments

11 сентября 2016, 07:02

08 сентября 2016

Максим Сохацкий

Новый сезон канала HBO

В связи с тем, что последний математик в Groupoid Infinity не выдержал и сошел с ума бросив работу над проектом, я, в индуктивно-индуктивной обсессивно-компульсивной попытке спасти проект, решил привести другого математика в проект. А именно себя.

С этого момента деканат прикладной математики КПИ величает вашего покорного слугу-грфомана аспирантом (теперь я официально ебанат). В этом году сдают экзамены как на кандидатский (англ., специальность, у меня обе А, готовился чесно, ебанул 50 страниц матфизики вплоть до ядер интегральных операторов и функциональных пространств L2), ну и как всегда на ПМ только дневная форма обучения. Так как это последний год (мне 35) когда я могу поступить в аспирантуру (да да, сейчас КПИ дает PhD дипломы, а не галимого к.ф-м.н). Придется теперь срать тут и везде про рекурсоры и индукции в промышленных масштабах всея ЖЖ и на нескольких языках, чтобы до Андрея Байера слух дошел. Ну и на пары ходить, лекции читать, телочек в КПИ крутезных просто дофига, и все стартапы мутят и матан шарят. Ах Ах Ах.

С кодировками (хотябы CiC, не говоря уже про HIT и QIT) пока не понятно, что буду делать, буду делать pivot наверное. Возьму для начала ебану экстракт Lean, а потом плавно перейду к модифицированому тайпчекеру с Self типами уважаемых Пенг Фу и Аарона Стампа. Если найду хрошего категорщика может продолжу проект о суперкомпактном чистейшем как слеза PTS ядре. Времени дают 3 года.

Мне уже на кафедре посоветовали двух бодхисаттв. Первый бодхисаттва — правая рука Лямбдагарбхи — Любашенко Владимир (Институт Математики НАН Украины), а второй бодхисаттва — Лялецкий Александр (и его сын) из Института Глушкова (тот который придумал кибернетику в СССР Украине). Вот видео Любашенко из цикла лекций про Теорию Гомотопий https://www.youtube.com/watch?v=h2eU6OxHr3c Лялецкий по слухам тоже прувер пишет.

Поэтому, троли — расчехляйте ваши клавиатуры, контентом мы вас завалим сполна. Благо лямбда термы в нашей PTS действительного большого размера.

08 сентября 2016, 19:38

Евгений Охотников

[prog.flame] Давно что-то не писал про ООП vs ФП, надо исправиться... ;)

Довелось опять пересечься с приверженцами функционального подхода к программированию (для которых отстой все -- начиная от ООП и заканчивая исключениями). Поймал себя на давно забытом ощущении: у функциональщиков большинство примеров сильно оторванны от прикладных целей. Во времена, когда ООП завоевывало себе место под Солнцем апологеты ООП расказывали о достоинствах ООП на простых и понятных примерах. Вот, типа, вам нужны средства для рисования кругов, квадратов, треугольников и т.д. Или вот вам нужны средства для показа менюшек и диалогов. И эти примеры нормально заходили, т.к. без ООП все это приходилось делать на процедурных языках вроде C или Pascal. Это было сложно, плохо расширяемо, трудоемко в поддержке и т.д. Тогда как с ООП все оказывалось ощутимо проще. Ну, если хотите, не проще, а управляемее. Появлялась более удобная структура в коде, больше устойчивости (т.е. правки в одной части вовсе не обязательно сказывались в остальных частях), расширяемость улучшалась и т.д.

Понятно, что ООП -- это никакая не серебрянная пуля. И даже на заре проникновения ООП в мейнстрим (по крайней мере в наших Палестинах) было очевидно, что на ряде задач выигрыш от ООП может быть только если задача объемная и предполагает развитие в течении длительного времени. Помнится, некоторые аппологеты, вроде Гради Буча, даже предупреждали, что с ООП придется потратить гораздо больше сил и времени по сравнению с процедурным подходом на начальном этапе разработки. Т.е. на C или на Pascal-е вы бы уже могли написать худо-бедно работающий прототип, а на C++, Eiffel или SmallTalk еще бы только-только завершали фазу ОО-анализа и, возможно, фазу ОО-проектирования. И, скорее всего, не написали бы еще никакого кода.

Тем не менее, при всех своих проблемах ООП всегда (по крайней мере так было в начале 90-х) крутился вокруг практических вещей. Вот здесь у нас будет класс Строка. Ok, понятно что это и зачем. Вот здесь -- класс Файл. Снова Ok, снова понятно что и зачем. Вот здесь -- класс COM-порт. И снова Ok, снова все понятно. Аналогично с классами Меню, Диалог, Конфиг, Таймер, Нить и т.д. И вот уже из понятных частей собирается GUI-приложение для работы с неким внешним устройством через COM-порт.

Поэтому ООП было более-менее просто объяснять людям. Мол, смотри, у тебя будет COM-порт. Мы сейчас точно не знаем, что именно будет у него внутри, но более-менее понимаем, как с ним работать. Поэтому давай сделаем набросок класса COM-порт с несколькими очевидными публичными методами и пойдем дальше... На какой-то N-ой итерации мы возвращаемся к нашему классу и уточняем еще чуть больше. А потом еще и еще раз.

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

Тогда как с ФП лично мне таких объяснений, которые бы отталкивались от практики, особо не попадается. Если говорить совсем грубо, то получается что-то вроде:

-- Вот смотри, у нас есть функция f a b -> c...
-- А что это за функция? Для чего она?
-- Это не важно. У нас просто есть функция f a b -> c. У нее два аргумента. Но, на самом деле, ее можно представить как последовательность функций с одним аргументом f a -> b -> c...
-- И что?
-- И мы может делать каррирование, когда мы из f a b -> c, получаем g b -> c с зафиксированным значением аргумента a. А все месте нам это дает возможность композиции функций!
-- Композиции функций для чего?
-- Для чего угодно. Вот смотри, допустим, нам нужно применить к данным функции x, y и z...
-- К каким именно данным и что именно делают функции x, y и z?
-- Это не важно, важно то, что через композицию мы можем сделать так, что разультат x идет в y, а разультат y идет в z. Мы просто описываем композицию функций декларативно в коде и все.
-- Что все? Какие у нас данные? Как именно мы их обрабатываем? Зачем мы это делаем?
-- Это не важно, я тебе принцип объясняю.

Вот, скажем, как вам такая статья на Хабре: Монады и do-нотация в C++? Но не просто как статья, как демонстрация принципа, на котором можно связать в цепочку последовательность операций. Например, B*x + C, где B и C -- это матрицы, а операции умножения и сложения могут завершаться неудачно.

Собственно, сей пост не является попыткой бросить камень в само ФП. Как по мне, так изрядная часть фишек ФП оказалась в императивном мире давным давно (например, если посмотреть на языки SmallTalk и Ruby, в которых блоки кода есть ни что иное, как лямбды, а изрядная часть методов в стандартной библиотеке базируется на использовании функций высших порядков). И использовалась программистами задолго до возникновения хайпа вокруг ФП, причем многие до сих пор не подозревают об этом, дергая Enumerable#map. Ну и вообще, очень многие вещи из ФП вполне себе просты и понятны, если их объяснять без чрезмерного использования математических формул :)

Речь о том, что рекламе ФП и раньше недоставало приземленности. И сейчас ничего особо не изменилось, как по мне. Поэтому если человек не фанат изучения новых парадигм и языков, и его не прет от реализации моноидов на шаблонах C++, он не тащится от того, насколько генерики+трейты в Rust-е удобнее генериков в Java, а ему тупо нужно взять набор байтиков отсюда и переложить их вот туда, то осознать полезность фишек ФП ему сейчас ничуть не проще, чем 10 лет назад. Имхо, конечно.

PS. Кстати говоря, ничуть не удивлюсь, если для современной молодежи, которая начала учиться программировать сейчас или даже лет пять назад, ситуация видится прямо противоположной. Вероятно, для нонишних новичков в программировании базисом, с которого они стартуют, являются такие вещи, как функции высших порядков, алгоритмы вроде foldr/foldl/zip, алгебраические типы данных и т.д. А вовсе не правила структурного и модульного программирования, с осознания важности которых довелось начинать моему поколению.

написал Yauheni Akhotnikau (noreply@blogger.com) 08 сентября 2016, 11:36

04 сентября 2016

ru_scheme

Просуммировать по длине вектора, новичковое

Есть кто живой? Спасите-помогите-мы-сами-не-местные.
Записываю музыку в lilypond-е, который написан на scheme guile
Хочу (и не могу сказать :) ) написать функцию, которой передавать вектор из скольких-то N чисел, не знаю из скольки (каждый раз сколько понадобится), а она бы склеивала столько N раз строку из заготовок. Термин "хвостовая рекурсия" уже паники не вызывает )

Подскажите, как узнать число элементов в векторе (или листе, если вектора не окажется в доступных из lilypond'а типах)
Спасибо!

написал bashusha 04 сентября 2016, 12:42

31 августа 2016

caml_programmer

Haskell, Erlang update

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

А вот компиляция Erlang очень существенно повлияла на его
производительность, почти в 3 раза. Судя по strace, он
какое-то время инициализируется, а потом довольно шустро
работает, не исключаю, что в случае сервиса - догонит
haskell и rust.

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



О, день знаний, всех короче с праздником!

31 августа 2016, 21:40

30 августа 2016

caml_programmer

Erlang update

Erlang вариант переписали, стало гораздо лучше - 6.415 секунд.



https://github.com/DMSOFTWARE/cats/pull/2

30 августа 2016, 19:20

29 августа 2016

caml_programmer

Haskell update

Отлично, размер буфера haskell-варианту зачинили.
теперь он с результатом 2.019 вплотную догнал rust и python,
но до тройки go, c++, c - немного не дотянул.



https://github.com/DMSOFTWARE/cats/pull/1

29 августа 2016, 19:06

archimag

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

Недавно со мной связался Иван, который ищет человека себе в команду и он полагает, что интересный ему человек может быть среди лисперов. Я предложил опубликовать объявление в моём блоге, что бы он попал в Russian Lambda Planet (а также в планету на lisper.ru) и таким образом попытаться зацепить целевую аудиторию. Ниже его текст.

##############################################################

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

Мы начали применять сверточные нейронные сети ("компьютерное зрение 2.0") раньше, чем об этом появилась первая русскоязычная статья в интернете. За последние пару лет у нас были заказы такого плана: видеоконтроль нештатных ситуаций на конвейере, распознавание блюд китайской кухни по фото со смартфона, поиск ключевых точек на лице в реальном времени, есть заказчик, с которым мы работаем по теме process mining (анализ процессов по журналу событий), кластеризации и прогнозированию процессов и прочим связанными вещами, были работы по распознаванию речи, ну и много всякой мелочевки типа "классифицировать картинки."

В качестве дополнительного понта могу указать, что на upwork-аккаунте имеем 5 звезд и job success rate 95%.

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

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

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

Из минусов: отсутствие трудоустройства по ТК, отсутствие стабильности - бывает все заказчики дружно просыпаются и случается аврал, а бывает (хотя и нечасто) целый месяц нет работы.

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

Для прототипирования и обучения прогнозирующих моделей мы используем питон, в основном из-за обилия специализированных библиотек. Заказчиков разворачивать у себя питонье окружение обычно не устраивает, поэтому готовое решение обычно переписываем на Си. Это доставляет кучу боли, поэтому мы сейчас обдумываем разные варианты, на какой платформе выкатывать готовые решения. Пока склоняемся к common lisp, который был бы идеальным вариантом, если бы имел нормальный биндинг к OpenCV.

По любым вопросам пишите на hohlovivan@gmail.com

##############################################################

29 августа 2016, 08:49

28 августа 2016

Scala@livejournal.com

Создание с валидацией

Допустим, у меня есть case class Employee(name: String, age: Int), где 10 < age < 120. Тогда, чтобы не создавать невалидные инстансы, я могу добавить case class Age(value: Int) и переписать Employee как case class Employee(name: String, age: Age), а для создания валидных инстансов Age можно добавить object Age { def apply(age: Int): Try[Age] = ... }.

Но и тогда сожалению остаётся возможность создания невалидного инстанса: val a = new Age(-10). Очевидно, нужно сделать конструктор case class Age приватным, но тогда object Age не сможет его вызвать.

На stackoverflow советуют сделать что-то навроде такого:
sealed trait Age { val value }
object Age {
  def apply(age: Int): Try[Age] = ... // if age within the range return a new instance of AgeImpl otherwise fail 
  private case class AgeImpl(value: Int) extends Age 
}
и для Employee тогда:
object Employee {
  def apply(name: String, age: Int): Try[Employee] = Age(age) map (Employee(name, _))
}
По-моему, как-то громоздко :( А можно то же самое попроще написать ?

написал Michael 28 августа 2016, 16:29

ruhaskell.org

Возможности и проблемы FFI в Haskell

Возможности и проблемы FFI в Haskell и примеры его использования.

написал Денис Шевченко 28 августа 2016, 00:00

27 августа 2016

swizard

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

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

Давайте, например, посмотрим на такие платформы: 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, я бы не писал этот текст, а вместо этого сделал бы что-нибудь полезное.

27 августа 2016, 03:19

nponeccop

Когда GHC FFI недостаточно быстр - лепим примопсы

Чувак дабы избавиться от оверхеда говномаршаллинга при FFI, генерит как я понял из Ragel Си, из сей - LLVM assembly, а оный ассемблер хачит седом, дабы получился примопс непосредственно с коллинг конвеншеном STG:

http://breaks.for.alienz.org/blog/2012/05/23/ffi-vs-primops/
http://breaks.for.alienz.org/blog/2012/02/09/parsing-market-data-feeds-with-ragel/

27 августа 2016, 02:29

caml_programmer

Заколхозил тест ввода/вывода для всех языков программирования

Вот такая ситуация пока получается.



https://github.com/dmsoftware/cats

Haskell и SBCL рисовать не стал, они оба где-то 2m50s отрабатывают,
и масштаб графика сильно портят. Ну Haskell там монады из себя
высасывает, а SBCL-то что капризничает?

Erlang - надо доработать, чтобы тест корректно завершался,
а то кажись там halt не срабатывает, что-то с этим надо
сделать. Но он тоже довольно задумчивый, наверное сопоставим
с Haskell и SBCL.

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

До APL-подобных языков я почти добрался, не знаю, есть ли
там ввод/вывод, но посмотрим.

27 августа 2016, 00:47

24 августа 2016

rssh

SE-2016 и Objective-C++

Занимаюсь сейчас подготовкой к выступлению на SE-2016 https://se2016.inhacking.com/ - буду рассказывать о эволюции языков программирования и современном ландшафте области [Киев, 3 сентября]. Давно хотел куда-то вставить о Objective-C++ , думал в этом выступлении, но получается и так слишком много материала, непонятно удастся ли включить и эту тему(?). Напишу пока в ЖЖ. Objective-C++ это первый язык, который возник "случайно", "сам по себе".

Сам Objective-C - это препроцессор над C, который написан Smalltalk. Его автор (Brad-Cox [блог: http://bradjcox.blogspot.it/ ; вот еще интервью с ним: http://www.mactech.com/articles/mactech/Vol.25/25.07/2507RoadtoCode-BradCoxInterview/index.html ] перетащил из Smalltalk OO-часть, что-бы можно было писать "как на Smalltalk" без медленного интерпретатора и сбора мусора, но с OO-dispath. Далее, компилятор внизу (gnu gcc или clang) может понимать как C, так и С++, следовательно если через препроцессор прогнать C++ класс, то С++ классы останутся классами, а Objective-C конструкции преобразуются в наборы вызовов C-функций. Некоторые разработчики обнаружили, что довольно удобно UI объекты представлять как Objective-C интерфейсы, а внутренние "не-UI" логику - C++ классами. Apple, следуюя запросам community, добавил поддержку Objective-C++ в XCode (вот архив документации: http://web.archive.org/web/20101203170217/http://developer.apple.com/library/mac/#/web/20101204020949/http://developer.apple.com/library/mac/documentation/Cocoa/Conceptual/ObjectiveC/Articles/ocCPlusPlus.html ). Потом они устыдились, доку снесли но поддержку де-факто оставили (XCode понимает расширение .mm ) . Некоторые примеры использования Objective-C++ с современным C++ можно посмотреть в презентации Peter Stainberger-а на AltConf-2015 https://realm.io/news/altconf-peter-steinberger-objective-c++-what-could-possibly-go-wrong/ Вот такая beautiful madness.

24 августа 2016, 12:28

22 августа 2016

Максим Сохацкий

Respect Proper Proof of Setoid Cat

Нас спрашивают, как выглядит код на EXE. Здесь записана модель Категории, на языке, у которого нет встроеного равенства (кроме definitional конечно):

define Respect (A,B: Type) (C: A → Type) (D: B → Type) (R: A → B → Prop)
       (Ro: ∀ (x: A) (y: B) → C x → D y → Prop) : 
       (∀ (x: A) → C x) → (∀ (x: B) → D x) → Prop :=
       λ (f g: Type → Type) → (∀ (x y) → R x y) → Ro x y (f x) (g y).

record Proper (A: Type) (R: A → A → Prop) (m: A): Prop :=
       (Proof: R m m)
       
record Setoid: Type :=
       (Carrier: Type)
       (Equ: Carrier → Carrier → Prop)
       (Refl: ∀ (e0: Carrier) → Equ e0 e0)
       (Trans: ∀ (e1,e2,e3: Carrier) → Equ e1 e2 → Equ e2 e3 → Equ e1 e3)
       (Sym: ∀ (e1 e2: Carrier) → Equ e1 e2 → Equ e2 e1)

record Cat: Type :=
       (Ob: Type)
       (Hom: ∀ (dom,cod: Ob) → Setoid)
       (Id: ∀ (x: Ob) → Hom x x)
       (Comp: ∀ (x,y,z: Ob) → Hom x y → Hom y z → Hom x z)
       (Dom1◦: ∀ (x,y: Ob) (f: Hom x y) → (Hom.Equ x y (Comp x x y id f) f)) 
       (Cod1◦: ∀ (x,y: Ob) (f: Hom x y) → (Hom.Equ x y (Comp x y y f id) f)) 
       (Subst◦: ∀ (x,y,z: Ob) → Proper (Respect Equ (Respect Equ Equ)) (Comp x y z))
       (Assoc◦: ∀ (x,y,z,w: Ob) (f: Hom x y) (g: Hom y z) (h: Hom z w)
                → (Hom.Equ x w (Comp x y w f (Comp y z w g h)) 
                               (Comp x z w (Comp x y z f g) h)))


zeit_raffer переписал Subst◦ без Proper/Respect:

       (Subst◦: ∀ (x,y,z: Ob) (f1,f2: Hom x y) (Hom.Equ x y f1 f2) 
                              (g1,g2: Hom y z) (Hom.Equ y z g1 g2) 
             → (Hom.Equ x z (Comp x y z f1 g1) (Comp x y z f2 g2))) 


Вроде компактнее уже нельзя. Не нашел ни одной библиотеки на Agda на github, где по компакности хоть кто-то приблизился бы. Достигнут новый золотой стандарт лямбда-йобства!

22 августа 2016, 11:47

Благословение от Хенка получено

Henk Barendrecht wrote:

Dear Maxim,

1. Great that you have reached a point in your software
development where you need automated verification
via formalization. Indeed you have my blessings.
My co-author and former colleague Freek Wiedijk
will almost for sure be interested in your project.
He is not happy with the existing provers and has
reimplemented automath.

...


Работаем дальше!

22 августа 2016, 10:04

Identity Types in EXE





____________________
[1] E.Bishop Foundations of Constructive Analysis 1967
[2] T.Streicher, M.Hofmann The groupoid interpretation of type theory 1996
[3] G.Barthe, V.Capretta Setoids in type theory 2003
[4] M.Sozeau, N.Tabareau Internalizing Intensional Type Theory 2013
[5] V.Voevodsky Identity types in the C-systems defined by a universe category 2015
[6] D.Selsam and L.de Moura Congruence Closure in Intensional Type Theory 2016

22 августа 2016, 10:04

Американская и Британская школы Лямбды

Выражаю почтение и склоняюсь перед де Брейном,
отцом всех пруверов,
создателем AUTOMATH


Сейчас я объясню мотивацию синтаксиса OM/EXE. Навскидку есть несколько синтаксисов для лямбды:

    λ x . B x            — нетипизированная классика
    λ x : A , B x        — в научных статьях
    λ (x: A) → B x       — современный синтаксис Morte/Om
    λ (x: A) , B x       — Lean
    (x: A) B x           — LISP синтаксис
    [x: A] B(x)          — AUTOMATH
    fun (x: A) => B x    — языки программирования и французкая школа
    fun (X) -> B(X)      — Erlang


Классика используется студентами, которые решают домашки, на википедии, и в HOL/Isabelle. Второй синтаксис используется в самых крутых статьях по лямбда исчислению, его использует например Страйхер, третий используется тоже часто в статьях, например Пфенинг. LISP синтаксис заюзал в своей работе по индуктивных семейставах Дыбьер. Но все это вариации AUTOMATH, где есть [], что есть там и квантор и лямбда. Есть еще логический синтаксис правил вывода, который заюзал МакБрайд в Эпиграмме, но это уже через чур. Синтаксис, который используется в современных языках программирования, тоже приведен, тут по столько по скольку, так как статьи на нем писать неудобно. Мы выбрали в качестве синтаксиса лямбда исчисления в OM тот, где есть и скобочки и стрелочки. Нормальные формы лямбд мы выстраиваем вертикально так как это делал Дыбьер, чтобы видеть паттерн и глубину терма.

То как выглядят индуктивные типы условно можно разделить на британскую школу LCF/ML/HOL/Hope/Miranda/Haskell/Agda/Idris и американскую LISP/ACL2/NuPRL/Lean/EXE школу. Это помогает понять почему мы выбрали скобочки и тут. Синтаксисом OM/EXE мы хотим показать приемственность к другой, не-британской школе. Как мы определяем List и как это делают британцы:

    data List (A: *): * :=
         (Nil: List A) 
         (Cons: A → List A → List A)

    data List (A : Set) : Set where
         []  : List A
         _∷_ : (x : A) (xs : List A) → List A


Тут сразу несколько моментов, мы хотим, в базовой поставке EXE, без notation, парсер должен быть минималистичный, мы всячески избегаем 2D синтаксиса ориентированного на \n и \r и обрамляем все скобочками, как это происходит в лиспах и Lean. Благодаря чему параметры индуктивных конструкторов напоминают множественные параметры наших лямбд \ (B: *) (x: A) -> B x.

Т.е. OM/EXE классифицируется исключительно, как синтаксис американской школы, с еще большим уклоном в LISP, чем калифорнийская Annah/Morte. Этот синтаксис создан для того, чтобы статьи выглядели красиво и читались ревьюверами мгновенно (кроме этого еще код нужно компактный писать, чем не все типовые теоретики могут похвастаться даже в своих Agda репозиториях).

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

Кроме того мы проводим эксперименты над людьми. Мы заставили Пашу целое лето писать на голом ОМ синтаксисе, и Паша с вами поделился своими откровениями на эту тему. После компактификации кода, остается по одному квантору на теорему, а все остальное превращается в скобочки.

22 августа 2016, 10:03

Собеседование в Групоид Инфинити

Как-то тут зашла речь, что якобы мы в Групоид Инфинити пиздаболы, и кодировки наши не кодировки, и веры в нас нет никакой. На что у меня сразу появилось отдельное, не связанное с этим, ответное предложение — составить тестовое задание на вход в команду:

Итак, как вы знаете мы работаем в чистейшем как слеза CoC, с бесконечными наобором аксиом для вселенных. Разные конфигурации у нас возможны, предикативные, импредикативные, внизу одна импредикативная для Prop как у всех и.д. Комулятивные эмулируются, так что для простоты они не нужны.

Так вот для статьи я начал выписывать семантику. Ну ее еще Мартин Леф выписал в 1972 для Пи типов, т.е. наш ОМ. А потом уже идет семантика EXE.

В EXE дальше идет у нас равенство с J элиминатором. В 1988 году была записана семантика для теории категорий (наша рабочая теория) в теории типов Мартина Лефа. Потом была записана семантика для Well Founded Trees, которые полиномиальные функторы, они же индуктивные типы в общем случае, ну а дальше идут высшие индуктивные типы. Как выписать Type Inference Judgment Rules для скажем Транкейшина или Гомотопической Сферы — тривиальная задача, которую может выполнить даже такой дибил как я. А в команду мы возьмем того, кто выпишет правила вывода для высших индуктивных типов в общем случае (HIT-form, HIT-intro, HIT-elim, HIT-comp).

Ждем ваших писем! :-)

22 августа 2016, 09:56

14 августа 2016

Максим Сохацкий

Наноядра чистый изумруд

В Твиттере пошла волна репостов про https://github.com/littlekernel/lk Но среди молодняка мало кто знает, что автор этого ядра Тревис Гейзельбрехт был со-автором ядра операционной системы BeOS, а также автором NewOS, которое фактически в неизменном виде стало основой HaikuOS. Теперь Google начало пилить Фуксию, ОС основанную на LK. Все-таки BeOS выстрелил! Also если кто незнает из NewOS известный ебанат Дима Завалишин понадергивал кусков и всем говорит что заебашил PhantomOS с нуля.

Я когда-то дико упарывался по BeOS, Haiku и даже ебашил там на С++ чаты и KHTML портировал с KJS. Но теперь у меня смешанные чувства: с одной стороны я рад, что правительство Гугла дало добро на закапывание Линукса, с другой я уже перерос это байтойобство. Только лямбдочку хардварную верифицировнную мне подавай. К старости говорят все капризными становятся как дети.

Таки дела, пацаны.

14 августа 2016, 21:25

Scala@livejournal.com

Вопрос про трейты

Я не очень понимаю трейты, но иногда приходится с ними иметь дело. В основном из-за legacy. И вот возник такой вопрос:

Допустим, у нас есть trait A и trait A1 extends A. Можно ли как-то сделать так, чтобы трейт A1 нельзя было подмешать к трейтам, которые не extends А ?

P.S. Очевидно, trait A1 extends A {this: A => } не работает.

написал Michael 14 августа 2016, 18:52

Максим Сохацкий

Порядок редукций и Элиминатор Bool

Поднял из анналов, старый тред akuklev, nponeccop и udpn про if и "заходить в две ветки"

http://udpn.livejournal.com/78084.html

Напомнимаю, что мы все у себя давно померяли, для нормализации/ненормализации, eager/lazy вариантов:

http://maxim.livejournal.com/471966.html

Наткнулся на фразу

> В extensional ITT существуют сетоиды, но это жалкая замена левой руки.

Интересно что имелось ввиду? Что круто писать на J элиминаторе все, как на предыдущих слайдах? :-)

14 августа 2016, 00:01

13 августа 2016

Scala@livejournal.com

Библиотека для HttpClient

По-моему, библиотека для написания http client-а должна быть такой:
  • классы Request, Response, а также служебные Url, Entity, и т.д. это просто контейнеры для данных (как POJO или DTO на Джаве). Без всякой связи с собственно работой по сети.

  • Синтаксическй сахар для создания всех этих Request'ов, типа:
    get("myhost") / "foo" / "bar" withQuery("qp" -> "xxx")
  • Служебные функции для преобразования Request в Kleisli:
    Request => HttpConnection => Try[Response]
    Request => HttpConnection => Future[Response]
    и т.д.
  • Благодаря implicit class эти функции можно вызывать как методы Request'а:
    val req = get("a/b/c")
    val sync  : HttpClient => Try[Response]    = req.sync[HttpClient]
    val async : HttpClient => Future[Response] = req.async[HttpClient] 
    
Тут важно, что я могу единообразно использовать самые разные библиотеки, которые занимаются собственно работой по сети. В том числе Apache HttpClient, Async HttpClient, Netty, Finagle, и даже наши собственные библиотеки на джаве.

Как вам такой подход ?

написал Michael 13 августа 2016, 18:06

12 августа 2016

Теория категорий

MONADS NEED NOT BE ENDOFUNCTORS

We will elsewhere comment on the relation of our relative monads to the recent gen- eralization of monads by Spivey [31] that was also motivated by programming examples: he fixes a functor K ∈ C → J (notice the direction) to then look for monad-like structures with an underlying functor J → C. With Paul Levy we have checked that a fair amount of monad theory transfers to his generalized monads, but they are not monoids in [J, C] unless K has a left adjoint, in which case they are equivalent to relative monads. Sam Staton has considered an enriched variant of relative monads.

http://jmchapman.github.io/papers/relmon-lmcs.pdf

написал Namdak Tonpa 12 августа 2016, 18:57

Максим Сохацкий

MONADS NEED NOT BE ENDOFUNCTORS

We will elsewhere comment on the relation of our relative monads to the recent gen- eralization of monads by Spivey [31] that was also motivated by programming examples: he fixes a functor K ∈ C → J (notice the direction) to then look for monad-like structures with an underlying functor J → C. With Paul Levy we have checked that a fair amount of monad theory transfers to his generalized monads, but they are not monoids in [J, C] unless K has a left adjoint, in which case they are equivalent to relative monads. Sam Staton has considered an enriched variant of relative monads.

http://jmchapman.github.io/papers/relmon-lmcs.pdf

Кто еще раз пизданет что Монада — это моноид в категории эндофункторов, сразу с вертушки :-)

12 августа 2016, 18:56

Scala@livejournal.com

ru_scala @ 2016-08-12T20:43:00

Ещё одна версия "игры жизнь". На этот раз добавлен zipWith (по совету sassa_nf, за что ему огромное спасибо). К сожалению этот вариант длиннее изначального за счёт всех этих операций сдвига. Теперь было бы интересно написать визуализацию на scala.js.
object MatrixConway {

  type Board = Vector[Vector[Int]]

  def tick(board: Board): Board = {

    val cell: (Int, Int) => Int = {
      case (c, 2) => c
      case (_, 3) => 1
      case _ => 0
    }

    val shifts: Seq[Board => Board] = {

      def shiftL[T](ts: Vector[T], pad: T): Vector[T] = (ts drop 1) :+ pad
      def shiftR[T](ts: Vector[T], pad: T): Vector[T] = pad +: (ts dropRight 1)

      val shiftW = { b: Board => b map (shiftL(_, 0)) }
      val shiftE = { b: Board => b map (shiftR(_, 0)) }

      val zeros = Vector.fill(board.length)(0)
      val shiftN = { b: Board => shiftL(b, zeros) }
      val shiftS = { b: Board => shiftR(b, zeros) }

      val shiftNW = shiftN andThen shiftW
      val shiftSE = shiftS andThen shiftE
      val shiftNE = shiftN andThen shiftE
      val shiftSW = shiftS andThen shiftW

      Seq(shiftW, shiftE, shiftN, shiftS, shiftNW, shiftSE, shiftNE, shiftSW)
    }

    def zipWith[A](f: (A, A) => A): (Vector[A], Vector[A]) => Vector[A] = (_, _).zipped map f
    val zipBoardWith: ((Int, Int) => Int) => ((Board, Board) => Board) = f => zipWith(zipWith(f))

    val neighbors: Board => Board = b => shifts map (_.apply(b)) reduce zipBoardWith(_ + _)

    zipBoardWith(cell)(board, neighbors(board))
  }
}

написал Michael 12 августа 2016, 17:59

10 августа 2016

caml_programmer

Чистые функции против сайдэффектов.

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

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

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

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

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

В общем, неоднозначно можно сказать что ничерта не понятно
как всё устроено.

10 августа 2016, 21:53

Scala@livejournal.com

ru_scala @ 2016-08-10T18:25:00

Ещё одна имплементация "игры жизнь" по подсказке sassa_nf, за что ему большое спасибо. Мне очень понравилась идея использовать операции с матрицами вместо манипуляций с индексами (только, к сожалению, не могу объяснить почему).

Код, по-моему, выглядит вполне читаемым, но не очень компактным и явно длиннее чем в предыдущейм примере
Как обычно, буду рад любым предложениям и исправлениям.
object MatrixConway {

  type Board = Vector[Vector[Int]]

  def tick(board: Board): Board = {

    val cell: (Int, Int) => Int = {
      case (_, n) if n < 2 || n > 3 => 0
      case (c, 2) => c
      case (_, 3) => 1
    }

    def shiftL[T](ts: Vector[T], pad: T): Vector[T] = (ts drop 1) :+ pad
    def shiftR[T](ts: Vector[T], pad: T): Vector[T] = pad +: (ts dropRight 1)

    val shiftW: Board => Board = _ map (shiftL(_, 0))
    val shiftE: Board => Board = _ map (shiftR(_, 0))

    val zeros = Vector.fill(board.length)(0)
    val shiftN: Board => Board = shiftL(_, zeros)
    val shiftS: Board => Board = shiftR(_, zeros)

    val shiftNW: Board => Board = shiftN andThen shiftW
    val shiftSE: Board => Board = shiftS andThen shiftE
    val shiftNE: Board => Board = shiftN andThen shiftE
    val shiftSW: Board => Board = shiftS andThen shiftW

    val shifts = Seq[Board => Board](shiftW, shiftE, shiftN, shiftS, shiftNW, shiftSE, shiftNE, shiftSW)

    val addUp: (Board, Board) => Board = (b1, b2) => (b1, b2).zipped map ((v1, v2) => (v1, v2).zipped map (_ + _))
    val neighbors: Board => Board = b => shifts map (_.apply(b)) reduce addUp

    (board, neighbors(board)).zipped map ((v1, v2) => (v1, v2).zipped map ((c, ns) => cell(c, ns)))
  }
}

написал Michael 10 августа 2016, 16:41

Dee Mon journal

Bashkortostan ftw

As you surely know, Bashkortostan is the world leader in technology,
computer science and algebraic topology. With this submission, we expect to
cement the positions of our motherland in the exciting new field of
computational geometry. Don't worry: resistance is very obviously futile.

From young age, our children are trained in the art of convex decomposition
of polyhedra, computing barycenters of weighted point sets, and triangulated
surface mesh skeletonization; hoping, that one day they'd be tasked with a
crucially important problem of...

https://github.com/cakeplus/icfp-2016-wild-bashkort-mages
Самый суперский отчет (точнее, readme к исходникам) с нынешнего ICFPC. Почитайте целиком, не пожалеете.

В этом году контест был очень классным, и очень суровым.

10 августа 2016, 05:42

09 августа 2016

Adept

ICFPC-2016: день первый

(Это первая часть рассказа, а вот вторая и третья)

В этом году ICFPC был про оригами.

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

Вот на картинке контур закрашен красным, а линии скелета выделены:


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

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



Если вы развернете ваше оригами, то обнаружите, что лист расчерчен складками на многоугольники. Вам надо пронумеровать все вершины, указать их координаты и то, к какому многоугольнику относится та или иная точка, а затем показать, в какое место оригами (в какие координаты) в конце концов будет перенесена каждая точка:


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

Был интерактивный leaderboard.

По истечении 24 часов открывалась возможность засылать свои задачки и решать чужие. Авторы задач получали (5000-размер задачи)/молодцов очков, что по первым прикидкам было чуть больше, чем дофига (если твою задачу никто не решил).

День первый

В моей временной зоне все начиналось в час ночи. Собрав волю в кулак, я пошел спать до того, как было опубликовано задание, и на следующий день проснулся аж в 10:00 и засел читать условие. Первые впечатления были смешанные. Ура, в этом году без навязшего в зубах AI. Ура, leaderboard. Ура, не надо готовить свой код для исполнения на сервере организаторов. Ура, просто засылаем решение в каком-то простом формате, а решать можно на чем угодно и как угодно.

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


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

REST API, говорите? С примерами на curl? Замечательно, заворачиваем все в bash, суем в нужные места "sleep 0.5", чтобы сервер не ругался на слишком много запросов (еще 0.5 секунд добавляют тормоза баша), и скрипт для выкачивания задач готов.

Это задало определенный тон на все соревнование -- больше, больше шелла и скриптов. Я колебался, что именно брать для рисования задач -- cairo2 или ocaml'овский graphics, и в результате выбрал gnuplot + все тот же bash.

Для lightning round организаторы дали 100 задач, сложность которых росла очень медленно. Квадратик. Квадратик, сдвинутый из начала координат. Повернутый квадратик. Чуть меньший квадратик. В 12:00 я заслал первое (идеальное) решение для тупого квадратика и был доволен собой. И тут внезапно (зацените всю красоту гнуплота, кстати - на статической картинке этого не видно, но можно было щелкать мышкой и включать-выключать видимость контура и скелета по отдельности):



Или вот:


Это нифига не очевидно с первого взгляда, но такую фигуру нельзя сложить без так называемого inside reverse fold. Это мне очень вовремя объяснила жена, у которой с оригами не в пример лучше моего. То есть, нужно сделать несколько сгибов, а потом один из них вот этак вытащить наружу (или наборот - заправить внутрь под уже сложенные слои бумаги).

Я понял, что я вообще не понимаю, как это можно 1)распознать по описанию задачи 2)запрограммировать. Но унывать нельзя, надо что-то делать. И я сделал програмку, которая распознает задачи, являющиеся переносом-повотором квадрата 1х1 и решает их. Чисто чтобы отладить парсер заданий, принтер решений, работу с числами (которые были в виде натуральных дробей -- привет, Num) и все такое прочее. "Такое прочее" заняло у меня порядочно времени (как всегда бывает), и этот игрушечный солвер был у меня готов только к 15:00.

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

Дальше я понял, что раз "лыжи не едут", то надо делать хоть что-то. Этим хоть чем-то оказалась идея, которая пришла в голову, думаю, всем без исключения - можно в качестве решения отсылать листик 1х1 без всяких сгибов, заботливо положеный поверх требуемого оригами. Это давало какие-то небольшие очки, но все-таки лучше, чем ничего. Опять же, можно написать еще скриптов - чтобы решать все задачи, засылать все решения и т.п.

К 18:00 я накрыл квадратиками все задачи и неожиданно поднялся на 18 место. Приободренный, я подумал, что я могу пойти на один шаг дальше -- если оригами меньше квадрата 1х1, то я могу положить оригами в угол моего листа, загнуть правый и верхний края, и результат будет лучше (т.к. получившийся квадратик с подгибами будет "более похож" на результат). Прелесть в то, что структура такого решения всегда одна и та же -- лист бумаги будет разделен сгибами на четыре прямоугольника, номера точек и номера вершин прямоугольников всегда одни и те же, отличаются только их координаты (в зависимости от того, насколько сильно подогнут листик). Но координаты-то как раз посчитать легко. А все остальное можно захардкодить.

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

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

К 23:00 у меня появилось первое приближение к коду, который загибает уголок у листа бумаги (это я так думал, на самом деле там не работало примерно ничего, но я об этом узнаю только завтра). После полуночи закончился lightning (я был где-то на 18-м месте), организаторы опубликовали первую любовно сделанную моей женой задачу, на нее никто в течении часа не позарился, и я получил где-то 4000 очков и взлетел до 13 места. Окрыленный этим результатом, я пошел спать.

Хронология взлетов и падений:


Продолжение.

09 августа 2016, 22:58

ICFPC-2016: день третий

Предыдущие части : день первый, день второй.

На третий день (традиционно, в 10:00) я обнаружил, что сполз до 42 места (из около 200 активных участников). Какое-то время ушло на вытягивание новых задач и разглядывание того, как другие участники решают мои задачи. В 11:00 я вернулся к написанию солвера.

На третий день количество написанного кода превысило критический порог и наконец-то ПОПЁРЛО.

К 12:00 я сделал вычисление выпуклой оболочки (convex hull) и стал писать солвер, который заворачивает любое оригами как подарок -- кладет сверху лист бумаги и подгибает все края по граням выпуклой оболочки, пока бумага не перестанет торчать за пределы нужного контура.

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

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

Где-то в 13:00 я начал первые пробные запуски нового солвера, и на удивление он почти сразу же заработал. Единственной найденной проблемой было то, что я сдвигал оригами к (0,0), потом оборачивал вокруг него бумагу, а потом двигал результат обратно в то место, где он должен быть по условию задачи. И вот это последнее движение могло превратить все мои координаты в ужасные громадные дроби, что приводило к превышению лимита в 5000 байт.

К 14:00 я закончил допиливать скрипты для проверки решений, и поставил решение задач и их отправку на поток, а сам принялся разглядывать неидеально решенные задачи.

С ключом -debug солвер мог сохранять на диск картинки до и после каждого сгибания. Вот как это выглядит (линии тонкие, рекомендую фуллскрин):


Очень быстро я понял, что в отдельные моменты хочется сказать "да где ты загибаешь! Ты не вот там загибай, ты вот тут загибай!". К этому моменту (15:30) жена прошерстила статистику по имеющимся задачам и моим решениям, и сказала мне, что есть довольно много задач, которые по сути являются выпуклой оболочкой, которую потом перегнули еще раз или два. И если бы мой солвер мог сделать еще и это ...

Как именно вычислить такие задачи и сделать дополнительный шаг или два я в тот момент сообразить не мог. Зато я вспомнил ICFPC 2007, на котором jabber.ru решил все задачи вручную (написав для этого подходящие инструменты).

К 16:00 я залили все решения, которые только мог произвести и скакнул с 52 места на 20-е. Дальше имеющийся солвер меня поднять не мог.

И я стал писать интерактивный солвер на базе имеющегося у меня кода. Тут я впервые пожалел о том, что выбранный мной подход к визуализации позволяет мне только сохранять .png. Поколебавшись между "переписать все с нуля" и "оставить как есть и что-то придумать" я решил оставить все, как есть.
В результате интерактивная решалка после каждого шага сохраняла /tmp/interactive.png, а я запускал программу для просмотра картинок, которая раз в пол-секунды ее перерисовывала.

На картинке я рисовал исходный лист бумаги и точки "скелета" на нем, а рядом - текущий вид оригами и, опять-таки, точки скелета. Управлялся процесс интерактивной сборки через простой командный интерфейс. Программа имела/умела:
  • ввод через readline с историей и поиском
  • неограниченное undo (undo)
  • сгибание через произвольные координаты (fc x,y x2,y2)
  • сгибание через линию, проходящую через а произвольные точки (fp точка1 точка2)
  • смещение бумаги на произвольный вектор (mv dx,dy)
  • совмещение точек на оригами и скелете (mp paper_point skeleton_point)
  • показать координаты точек скелета (skeleton)
  • показать размер решения (size)
  • и самая киллер-фича: многократно сгибать бумагу по двум указанным линиям, пока есть, что сгибать. В результате она свернется в полоску, края которой совпадают с этими линиями (strip line1_point1 line1_point2 line2_point1 line2_point2)

Последняя команда была добавлена из-за того, что было очень много задач вида "полоска, согнутая 1-3 раза".

В 18:30 интерактивная решалка заработала. Этого набора команд оказалось достаточно, чтобы решить любую задачу, которая моя "бумага" в принципе могла позволить решить.

Вот как это выглядит:


С 19:00 до 21:00 я допиливал фичи в интерактивный решатель, делал новые задачи и вручную решал имеющиеся. Жена постоянно подбрасывала мне информацию о том, какие задачки выглядят решаемыми (глядя в статистику и картинки). Первым делом я старался решать задачи, которые присутствовали в N копиях, чтобы получить побольше очков.

Очень скоро стали понятны ограничения моего кода. Самым серьезным оказалось то, что сгиб по линии сгибал всё оригами целиком, тогда как для некоторых задач надо было согнуть только его часть. Кроме того, я не мог сделать нетривиальные сгибы с вытаскиванием или засовыванием углов (тот самый inside reverse fold, который я разглядывал в первый день).

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

Жена решила мне вручную какое-то невообразимое количество задач (что-то около 30), которые были моему коду не по зубам.

Где-то к 22:00 я написал код, который вытягивал из snapshot-а информацию о задачах, которые идеально решило меньше трех человек. Я просматривал их картинки и пытался решить их вручную, и решил что-то около десятка.

Две задачи требовали ручного сдвига бумаги "на чуть-чуть", я пытался высчитать правильное значение, но не смог, и в результате решил их с resemblance=0.99999999999. Обидно :)

Остаток времени ушел на то, чтобы еще раз прогнать солвер по всем задачам, убедиться, что все решения отправлены, еще раз посчитать статистику и решить максимальное количество задач вручную. Последнюю задачу я решил за 15 секунд до конца и отправить уже не успел :)

Хронология последнего дня (время в часах от начала ICFPC):


Исходники (там вместе с задачками, картинками и всеми снепшотами, около 100М):
https://bitbucket.org/dastapov/icfpc2016/

Статистика:
  • Идеально решенных задач: 1120
  • С подобием от 0.5 до 1.0: 2125
  • С подобием меньше 0.5: 236

По своим задачам точную статистику я не вел, но помню, что были какие-то, решенные всего 2-3 участниками.

Надеюсь, что с 19-го я поднимусь хотя быть на 18-е место :)

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

Выводы:
  • Жена, увлекавшаяся оригами - страшная сила
  • Без команды вполне себе ничего
  • Гулять - хорошо :)
  • Если что-то приуныл - пиши скрипты, разглядывай картинки, что-то делай. Мысль придет
  • После ежедневного ocaml на работе я даже и не думал писать на haskell -- уже не ориентируюсь в современных библиотеках, а тратить время на разбирательство неохота.
  • Это, конечно, не 2006 год, но тоже неплохо.


EOF

(первая часть, вторая часть)

09 августа 2016, 22:56

ICFPC-2016: день второй

(предыдущая часть, следующая часть)

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

Так как решение состоит из точек (заданных координатами на начальном листике), полигонов (заданых порядковыми номерами точек) и финальной формы оригами (заданной конечными координатами точек), то я подумал, что моя модель бумаги будет состоять из:
  • текущего положения точек (список координат)
  • полигонов (заданых списками номеров точек)
  • какой-то истории сгибов

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

Наутро второго дня (в 10:00) я перечитал написаный код и понял, что дела не будет. Во-первых, полигоны в виде списка точек неудобны, так как постоянно нужна "предыдущая точка" или "следующая точка". То есть, удобнее будет задавать полигоны отрезками.

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

В-третьих, моя реализация имела ошибку, и уверенно работала только в том случае, если в результате сгиба поворачивался только один "уголок" бумаги с одной вершиной.

В-четвертых, я так и не придумал, как хранить историю сгибов, и как "разгибать" бумагу назад, чтобы получить решение.

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

В общем и целом выходило так, что моя "бумага" ни на что не годилась.


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

К 12:00 я понял, что нужно расставить приоритеты. Я выкачал новую порцию задачек, сгенерировал для них картинки, сделал сводную статистику моих решений и их успешности и сел вместе с женой над ними медитировать. Выводов намечалось два: нужно делать свои задачи, они дают очки (и много). Но одними задачами выехать не получится - ты можешь размещать не более одной задачи в час, всего 46 штук. А твои конкуренты, которых 100-200 команд, могут за это время разместить до 8000 задач. То есть, все-таки нужен решатель. Более умный, чем "накрываем листиком, подворачиваем края".

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

Первым делом жена сделала мне вручную описание задачки-"змеи". Вот она:


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

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

Тут на меня нашло какое-то затмение и я почему-то подумал, что надо найти реализацию синуса-косинуса через, например, continued fractions, и все замечательно получится. Такая библиотека была найдена, но (как можно было бы и догадаться) чуда не произошло. "Polygon #0 is not mapped congruently", все в сад, повторять школьную математику. Можно было бы взять значение синуса равным какому-то произвольному числу, и вычислить, какое при этом будет значение косинуса, но там же \sqrt{1-cos^2{\alpha}}, а корень квадратный у нас - что? Правильно, такая же фигня, как и с синусом и косинусом.

Идея перебрать натуральные дроби из какого-то диапазона, удовлетворяющие a^2+b^2=c^2, и положить синус равным a/c, а косинус - b/c мне тогда в голову не пришла. В результате змея так и осталась неповернутой.

На неравный бой с тригонометрией у меня ушел битый час. Потом я еще какое-то время почитал всякие статьи, некоторые из них были довольно любопытными. В частности, из "Folding Flat Silhouettes and Wrapping Polyhedral Packages: New Results in Computational Origami" я узнал, что можно сложить оригами в виде любого плоского многогранника - хоть и невыпуклого, хоть бы и с дырками. Доказательство было конструктивным, но вот беда - подразумевало неограниченное количество бумаги. Кому лень читать статью - идея была в том, чтобы сложить узкую полоску, а потом "змейкой" замостить полигон, и напоследок завернуть под него выступающие части "змейки". Даже если бы я и умудрился сложить из квадрата очень узкую и очень длинную полоску, у меня было всего 5000 байт на решение, а такое количество точек и ребер туда бы не влезло.

В процессе всего этого я периодически вяло выкачивал новые задания и решал их, постепенно сползая к 30-му месту.

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

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

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

С этой новой идеей я за время где-то с 17:00 до 22:00 написал новую модель бумаги и процедуру ее сгибания вдоль произвольной линии, заданной двумя точками A и B. При этом линия считалась идущей из A в B, и все, что лежало справа от нее, перегибалось налево. Кроме того я реализовал "отладочный вывод", заключавшийся в том, что после каждого сгибания модель бумаги сохраняла на диск .png с изображением "разогнутого" и текущего состояний. Мой ocaml был собран без graphics, интерфейс cairo2 был большим и мне незнакомым, поэтому я нашел векторыне библиотеки Vg и Gg и использовал их (потеряв, наверное, на этом сколько-то времени). Зато -- и это оказался большой плюс -- Vg/Gg позволяли рисовать в произвольных координатах и сами транслировали нарисованное в рамки картинки.

Естественно, ничего не заработало с первого раза. Линии, пересекающие полигоны точно в вершине, или сопадающие с одной из сторон, или параллельные осям координат все потребовали каких-то тестов и фиксов.

Только к часу ночи я написал программу, которая читала из файла список отрезков, последовательно сгибала бумагу по каждому из них, и записывала получившееся решение в файл. В четыре руки с женой мы сделали несколько задач "посложнее" (как мне тогда казалось) и отправились спать.

Хронология второго дня выглядит так (время в часах от начала ICFPC):


(предыдущая часть, следующая часть)

09 августа 2016, 22:56

08 августа 2016

beroal

придумайте какую-нибудь теорию

Задача из учебника по физике: «Запишите уравнение Менделеева—Клапейрона. Придумайте задачу на его применение и решите её». По мотивам я придумал свою: «Изучите теорию категорий. Научите теории категорий других. Придумайте ещё какую-нибудь теорию».

08 августа 2016, 19:14

Максим Сохацкий

Про линзы в Хаскеле

http://andrej.com/

Edward Kmett explained to me once (at about three times the speed I could follow) how lenses are just a bunch of category theory. That’s the sort of thing that this broken Hask non-category is good for.

08 августа 2016, 16:44

Крипто-ебанаты. Выпуск #1

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

Вот одна криптовалюта https://www.ethereum.org, которая разрабатывается в том числе и математиками, была хакнута и из нее вывели 50 лимонов, потом начали транзакцию отменять, делать форк, и сейчас наверно оно уже мертвое. Все репозитории Эфира на гитхабе на JavaScript. Читать тут: http://www.coindesk.com/understanding-dao-hack-journalists/

Вот недавний инцидент с биткоин биржей Bitfinex:
http://www.ft.com/cms/s/0/1ea8baf8-5a11-11e6-8d05-4eaa66292c32.html#axzz4GkdJQNtk И вообще если вы начнете искать и погуглите вы охуеете сколько там дыр и утечек. Пока биткоин был маргинальной валютой, никому это не было интересно, но сейчас, все измненится и ваши биткоины потекут.

Если вы видете, что кто-то у вас рядом создает/запускает blockchain криптовалюты/торговые/аукционные/голосовательные площадки, и там используются криптоалгоритмы не прочеканые на (F*/Agda/Coq/EXE), рано или поздно этой хуйне придет пиздец. Не спасет и Хаскель.

Тот, кто первый построит прочеканную VM, компактное ядро прувера, прочеканый гипервизор, тот и срубит весь куш. И я не говорю про хуйню типа CompCert/VST которая линкуется башем с говнокодом. Я говорю про единую вычислительную среду LING/Erlang/EXE!

Очень интересно увидеть какую-то дыру в непрочеканном кванторами Хаскель коде. Пишите нам и держите нас в курсе.

08 августа 2016, 15:24

Elm support in mad

Наш агент, который делает поддержку Elm в `mad` сообщает:

> втыкал в елм малеха на выходных, сыроватая хуйня конечно
> н2о скрипты не переписать на этой штуке
> даже вебсокеты умеют только в текст и то прикручены нативной жс либой
> вроде для юайчика нормально написали все, но эта нативная срань конечно фейспалмище
> у тебя такой хуйни не было

> вообщем ищут себя походу еще пацаны, половину модулей нужно подправлять в жаваскрипте
> конечно, но нада добить конечно конектор к н2о, может кто возмется эту хуйню дальше развивать

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

08 августа 2016, 11:06

07 августа 2016

Dee Mon journal

срыв покровов

http://math.andrej.com/2016/08/06/hask-is-not-a-category/
И в конце отличный анекдот про "let’s just pretend".

07 августа 2016, 06:16

05 августа 2016

nponeccop

GHC DLL for Windows

Внезапно кто-то чинит баг, поломавшийся в незапамятные времена (в районе GHC 7.6)

https://ghc.haskell.org/trac/ghc/ticket/5987

05 августа 2016, 20:34

"Turtle//BAZON Group"

Лидерборд апдейт

Сейчас 8:48. Какие-то бомжи на первом месте в лидерборде.


написал turtle (noreply@blogger.com) 05 августа 2016, 08:49

04 августа 2016

"Turtle//BAZON Group"

ICFPC-2016, меньше 12 часов до старта

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

1.upto(99){|_|puts'FizzBuzz '[o=_**4%-15,o+13]||_}
Это на руби. Выводит следующую последовательность:
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
16
17
Fizz
19
Buzz
Fizz
22
23
Fizz
Buzz
26
Fizz
28
29
FizzBuzz
31
32
Fizz
34
Buzz
Fizz
37
38
Fizz
Buzz
41
Fizz
43
44
FizzBuzz
46
47
Fizz
49
Buzz
Fizz
52
53
Fizz
Buzz
56
Fizz
58
59
FizzBuzz
61
62
Fizz
64
Buzz
Fizz
67
68
Fizz
Buzz
71
Fizz
73
74
FizzBuzz
76
77
Fizz
79
Buzz
Fizz
82
83
Fizz
Buzz
86
Fizz
88
89
FizzBuzz
91
92
Fizz
94
Buzz
Fizz
97
98
Fizz
=> 1
 Смысл в том, что выводятся числа от 1 до 99 и там, где число делится на 3, пишут Fizz, где на 5, пишут Buzz, а где и на 3, и на 5 - FizzBuzz. В общем, такая шляпа широко используется в качестве тестового задания и даже приводят почему именно оно так хорошо раскрывает потенциал программиста. Правда, я не понял. :) Точнее, задача позволит отсеить откровенного непрограммиста.

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

Далее что мы имеем? Имеем некий запрос - Закидывание забутонами. Забутон это такой стул без ног. Которым кидают в сумоиста, который по рангу сильнее, но проиграл. Такие вот японские забавы. У моря живут, помидоров и яиц дефицит.

И третий пост - "Check or Fold?" Термины check и fold относятся к покеру. Check - пропуск хода, fold - сброс карт. 

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

И да, самый главый момент. В этом году наша команда выступает на хаскеле. Я его всю неделю учил. Не скажу, что понравился, но и не скажу, что прям сильно не понравился. Ясно, что в ICFPC и иже с  ним далеко не язык определяет победу. Так что начало в 03 утра по Мск. Ждём. :)

написал turtle (noreply@blogger.com) 04 августа 2016, 14:48