Грядет переезд

08.05.2014

Я все придумал, и скоро будет абсолютно новый чумовой сайт.

I’m back

23.04.2014

Привет, я вернулся!

И прежде чем начать жечь, хочу поделиться вот какой думкой. Надоел мне WordPress до смерти, хочется чего-то современного, Jekyll-образного, например, Middleman. Но есть одна беда: невозможно безболезненно перенести старый сайт на новую платформу. Все импортеры, которые я смотрел, переносят только текст, без разметки, без картинок и прочего. А терять контент за 3 года жалко.

Вот сижу думаю, как быть.

Рекламная пауза

14.01.2014

В связи с грядущим юбилеем завел свой список желаний.

Про код

24.12.2013

В отрочестве слово «код» у меня ассоциировалось исключительно с машинным кодом и ассемблером. Поэтому, читая переводные книги по C, я неизменно впадал в ступор от фраз типа «три страницы зубодробительного кода» или «много кодировать вручную». Какой же это код, если это – программа на C?

Со временем пообвыкся, и сейчас слово код никаких ассоциаций кроме «исходный код программы» не вызывает.

Выходные с Тео

15.12.2013

На фото: Кирилл, Тео, ваш покорный слуга и Хеннинг в секретной комнате с прекрасным виски. Огромное спасибо всем организатором #ruBSD и особенно Антону @toxo4ka.

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

Кастомизация икеевского шкафа

09.12.2013

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

1-IMAG1224

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

Это я к чему. Если ваша любимая мебель из Икеи куда-то не помещается, это еще не повод бросать ее и бежать к проходимцам из «Мебели на заказ». С помощью пилы и дрели стандартная икеевская мебель легко превращается в изящное кастомное решение.

Отличный канал на YouTube

06.12.2013

Я думаю, если бы Грегори Хаус был не врачом, а столяром, он выглядел бы примерно как Steve Ramsey.

Wooden cheese board. Kick off the holidays with this simple cutting board project.

Мой новый проект: tintun.es

29.11.2013

Когда я сижу за фортепиано, мне постоянно приходят в голову маленькие музыкальные темки. Долгое время я не знал, что с ними делать: выкинуть жалко, а довести до полноценного произведения не хватает ни таланта, ни фантазии, ни усидчивости. И вот наконец я придумал, куда их девать – раздать друзьям и знакомым на рингтоны. А для удобства сделал специальный сайт: http://tintun.es.

Enjoy!

Theo в Москве!

22.11.2013

Наш дорогой Яндекс проведет BSD-конференцию в Москве 14 декабря. Вход бесплатный, но количество мест ограничено. В числе прочего будет выступление Theo de Raadt.

По этому поводу скатаюсь в Москву, пропущу пару пива с Theo :)

Атчет што случаеца

23.10.2013

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

В первую очередь купил то, о чем давно мечтал – студийный микрофон.

1-IMAG1030

Это Rode NT1-A, конденсаторный микрофон с мембраной 1″. В комплекте «паук» и поп-фильтр, стоечку докупил отдельно. Как мне кажется, прекрасный выбор для домашней студии. Записей пока нет, но скоро будут.

Далее прикупил еще одну вещь, которую давно хотел – гравер.

dremel

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

Кстати о бритвах. Она таки приехала и она прекрасна.

1-IMAG1035

Для заточки кухонных и прочих ножей купил у китайцев на Aliexpress реплику американской точилки Edge Pro Apex.

1-Снимок экрана 2013-10-23 в 13.15.09

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

1-IMAG1041

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

У тех же китайцев взял карманный «микроскоп».

Снимок экрана 2013-10-23 в 13.29.35

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

Еще меня время от времени накрывает, и хочется вернуться в детство. В частности вспоминается, какие прекрасные книги были в то время. Особенно запомнились две: «Скифы в остроконечных шапках» и «Рожденный из камня». Первая, как ни странно, переиздавалась, и ее можно купить. А вот вторая канула в Лету и доступна только в виде букинистики. По счастью, на Озоне нашелся один экземпляр, и я его купил.

1001013500

Сказка по мотивам нартского эпоса. Книга, я так понимаю, б/у, но состояние отличное. Так что можете считать теперь меня хипстером букинистом.

Также продолжаю безуспешно бороться с собственной тупостью: изучаю Haskell по книге «Learn You a Haskell for Great Good!», параллельно пытаюсь научиться кодить на Python на работе. Очень помогает, что в Питоне есть много из Хаскеля. Прям ввожу в гугл «python qualified import» и узнаю, как это устроено в питоне.

Пока все, следите за новостями.

P.S. В заголовке – «Цветы для Элджернона», если кто вдруг не узнал.

Лоджия на сдачу

08.10.2013

10-IMAG0955

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

Прочитать остальную часть записи »

Ванная с бамбуком

02.10.2013

01-Ремонт1

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

Прочитать остальную часть записи »

,

Новая тема: опасные бритвы

23.09.2013

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

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

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

razor1

razor2

Сделана в Германии, в легендарном городе Золингере, в первой половине прошлого века. Сохранилась даже оригинальная коробочка.

Заплатил я, правда, слегка больше, чем рассчитывал – 30 долларов. Кто-то еще уж очень настойчиво бился за нее. Однако ж, я посмотрел на соседние похожие лоты, они тоже ушли за 30 с небольшим. Но случается купить и за $15-20.

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

Загадка

23.09.2013

Перед домом на асфальте обнаружил вот такие следы:

1-IMAG0896

2-IMAG0897

Как думаете, от чего они?

Инструмент для ремонта

11.09.2013

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

Прочитать остальную часть записи »

Рыба/ Я вернулся

10.09.2013

Уха из свежевыловленного судака была отменна!

Отпуск!

22.08.2013

Привет!

Я собираюсь немного отдохнуть. Меня ждет традиционное житье на острове в Астраханской области, рыбалка и все такое прочее. Как вернусь, начнем наконец-то новый сезон на Непорядке. Будем говорить об игре в бридж и гольф, о политике и о галстуках. Stay, как говорится, tuned!

Кухня-лофт

19.08.2013

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

Прочитать остальную часть записи »

ЭВМ/ Синтез функций на ICFPC 2013

15.08.2013

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

В этом году соревнования проводили Microsoft Research. Накануне они объявили, что нам стоит освежить свои знания в области program synthesis (синтез программ). Понятно, что никаких знаний по этой теме у нас не было, поэтому освежать было нечего. Однако я вяло поковырял Интернет и убедился, что на русском языке нет вообще ничего по данному вопросу, а на английском кроме коротенькой статьи в Википедии все ссылки ведут на работы Microsoft Research. Кто бы сомневался, ага. Я пролистал пару их статей, понял, что ничего не понятно, и с легким сердцем лег спать.

Задание

Есть набор программ (около полутора тысяч штук), которые нужно отгадать. Программа – это функция вида

f(x) = ((~(x + 1) & 1) << 1) ^ 1

Все операции побитовые, аргумент и результат – 64-битные беззнаковые целые. Программа задается в стандартной для функциональных языков нотации:

(lambda x (xor (shl1 (and (not (plus x 1)) 1)) 1))

Помимо битовых операторов есть две константы – 0 и 1, тернарный оператор сравнения if0 и хитрый оператор fold, который тоже хорошо знаком функциональным программистам (в некоторых языках он называется reduce и идет в паре с оператором map, MapReduce! :) Для каждого байта из первого аргумента fold вычисляет функцию lambda(x, y), переданную в качестве третьего аргумента, при этом x – это текущий байт, а y – текущее значение аккумулятора. Результат итерации снова записывается в аккумулятор. Начальное значение аккумулятора задает второй аргумент fold. Подробное описание задания можно прочитать на страничке соревнований.

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

После того, как мы попросили значения функции, начинает тикать таймер. Если в течение 5 минут мы не угадали программу, они «сгорает», и больше угадывать ее нельзя. Для тренировки можно попросить специальные тренировочные программы, которые не «сгорают».

Brute force

Фактически, задача состоит в следующем: подобрать такую комбинацию из заданных операторов, которая дает правильный результат для определенных значений. Легко сообразить, что комбинаторная сложность перебора быстро улетает в небеса по мере роста размера угадываемой программы. По условиям соревнований максимально возможный размер программы в предлагаемом наборе равен 30, что лежит далеко за пределами возможностей тупого перебора.

Забегая вперед, скажу, что не существует также простого и элегантного решения этой задачи, потому что она является NP-полной. Поэтому тут нужен не тупой, а «умный» перебор. Соответственно, чей перебор будет умнее, тот и победил.

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

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

К исходу первых 24 часов у нас был готов тупой брутфорсер, который успешно решал задачи длиной до 9. Мы прорешали им сколько смогли, чтобы заявиться в Lightning Division. Это отдельное соревнование для тех, кто успел хоть что-то сделать за первые сутки. После чего с чистой совестью легли спать.

Soft force и SMT-solver

На следующий день ребята пытались оптимизировать перебор, отсекать бесполезные ветки поиска, ускорять эвалюатор. Я читал майкрософтовские статейки в поисках идей. Идей было несколько.

Наша задача эквивалента задаче SAT: доказательству того, что для заданной булевой формулы можно подобрать такой набор операндов, что формула будет истинной. Задача SAT NP-полная. Для решения задач, сводимых к SAT, используют специальные программы: SAT-solvers. В нашем случае требуется не просто SAT, а более общий SMT-solver, который умеет решать задачи для разных логических формул, не только булевых. Чтобы воспользоваться готовым SMT-солвером, нужно описать нашу задачу на его языке, что не так просто.

По наводке из статей я скачал бесплатный SMT-солвер Yices и немного поигрался с ним. Когда я попросил его найти функцию, которая при x1 дает y1, а при x2 дает y2, он ничтоже сумняшеся выдал примерно такое:

if x == x1:
    return y1
elif x == x2
    return x2

Что ж, логично. Теперь ему нужно объяснить, что можно использовать только те операторы, которые заданы, при этом длина программы должна быть такая-то и, возможно, еще какие-то дополнительные ограничения. После этого он должен начать неистово синтезировать нужные нам функции.

Затем я обнаружил более удобный солвер Z3 от Microsoft Research (хе-хе), который, к тому же, имел биндинги для Python. Немного поковырявшись с ним я отвлекся на побочную идею из все тех же статей о подготовке шаблонов, на базе которых SMT-солвер будет искать функцию.

Я начал писать штуку, которая сначала берет набор операторов, из которых должна состоять угадываемая функция, и генерирует все возможные функции из них. Затем она добавляет один оператор из первоначального набора и генерирует все функции для нового набора, в котором один из операторов повторяется дважды, и так далее, пока не достигнет заданной длины функции. Так вот, оказалось, что для угадывания функции длиной, скажем, 10, достаточно сгенерировать функцию длиной 5!

Как так? А вот так. Если посмотреть глазами на тренировочные функции, то в них полно конструкций типа (shl1(shr1 x)), а то и вовсе (or 0 0). То есть угадываемые функции скорее всего сгенерированы случайно и могут быть подвергнуты серьезному упрощению. То есть размер угадываемой программы нужно трактовать не как ее точный размер, а как максимальный. К слову, мы тоже написали мини-сервер, который генерировал случайные функции, для тренировки.

Я рассказал ребятам о своих изысканиях, и Саша вызвался обучить Z3 решать нашу задачу. Мне тоже страшно хотелось поковыряться с SMT-солвером, но, подчиняясь командной игре, я вернулся к своему генератору последовательных решений.

В итоге мой генератор довольно уверенно решал все до размера 15, а иногда удавалось решить и что-то из района 20-25. Все зависит от того, как сильно может быть упрощена неизвестная функция. Саша наконец добил Z3 и синтезировал программы размером 20-25, хотя  и не всегда успешно. Надо сказать, что SMT-солвер ожидаемо не стал серебрянной пулей, NP он и в Африке NP. Именно поэтому половина статей посвящена эффективному поиску решений с помощью SMT. Леша мучал перспективную в общем-то идею предгенерации наборов функций, но как-то не довел ее до победного конца.

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

Результаты

В Lightning Division мы набрали 176 очков, это примерно 60-65 место из 150. В основном зачете мы набрали 569 очков, что соответствует 124 месту из 275. Для людей далеких от функционального программирования, математических проблем и командных соревнований это наверное неплохо. В следующем году постараемся снова сделать правильные выводы и выступить еще лучше.

ЭВМ/ Real-Time MapReduce

14.08.2013

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