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

Важно: в данной статье предполагается, что читатель знаком с основами Haskell. Если это не так, то я советую сначала прочитать пару статей для новичков (их можно найти в том числе и на Хабре).

Введение

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

Да и простого любопытствующего обывателя, не отягощённого подробностями органической химии, подобные вопросы не обходят стороной.

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



Такой предельно упрощённой и наглядной моделью могут оказаться «Живые графы» — конечные автоматы на графе, каждый узел которого содержит некое исполняющее устройство (автомат) с конечным числом состояний и с набором примитивных правил, управляющих созданием или изменением новых связей между узлами.

Есть хорошая статья Питера Норвига, в которой он рассказывает как написать спеллчекер в 20 строк кода. В этой статье он показывает как поисковые системы могут исправлять ошибки в запросах. И делает это довольно элегантно. Однако, у его подхода есть два серьезных недостатка. Во-первых, исправление более трех ошибок требует больших ресурсов. А гугл, кстати, неплохо справляется и с четырьмя ошибками. Во-вторых, нет возможности проверки связного текста.



Итак, хочется исправить эти проблемы. А именно, написать корректор коротких фраз или запросов, который:

• умел бы выявлять три (и более) ошибки в запросе;
• умел бы проверять «разорванные» или «слипшиеся» фразы, например expertsexchange — experts_exchange, ma na ger — manager
• не требовал много кода для реализации
• мог бы достраиваться до исправления ошибок на других языках и других типов" ошибок

Остальное — под катом.

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

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


Посмотреть можно здесь:
часть1
video.yandex.ru/users/ya-events/view/129
часть2
video.yandex.ru/users/ya-events/view/128

[FF D8]

Вам когда-нибудь хотелось узнать как устроен jpg-файл? Сейчас разберемся! Прогревайте ваш любимый компилятор и hex-редактор, будем декодировать это:

Специально взял рисунок поменьше. Это знакомый, но сильно пережатый favicon Гугла:

Последующее описание упрощено, и приведенная информация не полная, но зато потом будет легко понять спецификацию.

Даже не зная, как происходит кодирование, мы уже можем кое-что извлечь из файла.

[FF D8] — маркер начала. Он всегда находится в начале всех jpg-файлов.

Следом идут байты [FF FE]. Это маркер, означающий начало секции с комментарием. Следующие 2 байта [00 04] — длина секции (включая эти 2 байта). Значит в следующих двух [3A 29] — сам комментарий. Это коды символов ":" и ")", т.е. обычного смайлика. Вы можете увидеть его в первой строке правой части hex-редактора.

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

Предупреждение: Описанное в статье несколько устарело, т.к. я забросил винды в эпоху Windows 2003.

Каждый раз, когда меня знакомые спрашивают: «какой антивирус лучше?», я могу сказать только одно: «антивирус — как придворный шаман. Бывают лучше, бывают хуже, но определить, кто лучше камлает, не получится». Антивирус не гарантирует защиту от вирусов, более того, у него есть полное моральное право пропустить новую заразу и начать её детектить дня через 2-3 после «инцидента». Т.е. как основное средство защиты он годится не очень.

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

Теория

Любой уважающий себя вирус, оказавшись запущенным, тем или иным методом стремится в системе закрепиться, т.е. создаёт исполняемый файл или библиотеку, которая прописывается тем или иным образом в запуск. «Авто» запуск или в форме «дополнения» к другим исполняемым файлам (debugger, hander, плагин, и т.д.) — не важно. Важно: существует барьер под названием «запуск кода». Даже старые-добрые вирусы, дописывающие себя в исполняемые файлы, всё равно должны иметь возможность писать в файлы, которые предполагается запускать.

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

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

В Windows существует технология — политика ограниченного запуска приложений. Её можно активировать в режиме «запрещать всё, что не разрешено». Если поставить запрет полный — для всех, включая администраторов, все файлы, включая библиотеки, то мы получим точную гарантию того, что посторонний (не входящий в список разрешённых) файл не будет запущен. По-крайней мере я пока не слышал, чтобы в этой технологии были дыры. Обращаю внимание, нужно запрещать и библиотеки тоже, потому что печально известный конфикер запускается с флешек именно с помощью запуска библиотеки обманом rundll32.

Однако, запреты и разрешения не будут иметь смысла, если не сформулировать правила, которые запретят запуск «чужаков».

Модель безопасности

Перед тем, как описать подробно конфигурацию, сформулирую теоретические принципы её организации:

1. То, куда пользователь может писать закрыто для запуска.
2. То, что пользователь может запускать, закрыто для записи.

Доброго времени суток.
В этой статье я хочу сделать обзор одного из главных нововведений в Visual Studio 2010, а именно — функционального языка программирования F#.

Рассматривать синтаксис и потенциал F# мы будем на примере создания своего собственного интерпретатора для придуманного нами языка программирования (Ведь рассказвать о чем-то всегда интереснее на примерах).

Проблема

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

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

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

Хочется поделиться с хабросооществом информацией о том как я собирал домашний сервер.



Из софта на домашнем сервере будет «крутиться» следующий набор:

• torrent клиент с web-мордой
• DHCP — раздаем ip адреса и сетевые настройки
• TFTP — для сетевой загрузки
• OpenVPN — для хождения в сеть с нетбука из недоверенных сетей
• FTP/Samba/NFS — сетевые шары для доступа с домашних машин
• Radius — для WPA2 авторизации
• DigiTemp — мониторинг домашней температуры

Когда в коде фигурирует пара вызовов BeginXxx()/EndXxx(), это приемлимо. Но что если алгоритм требует несколько таких вызовов подряд, то количество методов (или анонимных делегатов) преумножится и код станет менее читабельным. К счастью, эта проблема решена как в F# так и в C#.

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

Усложнённый вариант задачки про эльфийских зэков. Решение предыдущей задачки умещается в пять строчек комментария. Теперь вот придумали вариант посложнее.
1-го сентября 100 бессмертных эльфийских магаданских зэков (далее — эльфов) постоили на торжественную линейку и предложили им ускорить процесс своего освобождения.
Каждый день одного из них будут отводить в одиночную камеру для воспитательных работ. В камере есть абсолютно чистый стол, неспособный запачкаться и без тайников (впрочем, неважно), к тому же его периодически будут менять (впрочем, неважно).
На столе стоит настольная лампа. Каждый день эльф с охранником заходят в комнату, эльф садится, включает лампу, рисует, либо читает книгу, либо думает, либо делает что-либо еще (неважно). Далее по протоколу эльф обязан выключить лампу (должен, но иногда этого может не делать) и уйти с охраной. Охранник иногда проверяет и, если эльф не выключил лампу, он делает это за него (потому что был както в магаданской тюрьме инцидент). Охранник неаккуратный, ленивый, но иногда лампу он выключает (пусть и редко). Также иногда в тюрьме бывают перебои с электричеством, и в этот день никого в комнату не водят. В таких случаях лампочку переводят в положение «выключено». Эльфов выбирают абсолютно случайно. Каждый день водят не более одного.
У каждого заключенного тюремщик будет спрашивать: «А все ли твои товарищи тут были хотя бы раз?». Если он ответит «не знаю» («нет»), то игра продолжается. Если он ответит «да», и это неправда — высшая мера наказания для всех. Если каждый из сотни эльфов сказал «да», и это всегда была правда, всех всех выпускают на волю в тундру.
Примечание. Если эльф сказал «да», и это правда, его, как остальных, продолжают водить в эту камеру на общих правах.
Заключенные сидят в одиночных камерах и могут договориться только один раз — 1-го сентября на обеде после торжественной линейки. После этого они сидят в «одиночках» без окон, совсем не видят друг друга и лампочки.
Определить стратегию (не обязательно оптимальную — её я сам не знаю) поведения каждого заключенного с тем, чтобы их выпустили пораньше.

Задача, подобная этой на использование совместных ресурсов:
1-го сентября 100 бессмертных эльфийских воркутинских зэков постоили на торжественную линейку и предложили им ускорить процесс своего освобождения. Итак, в тюрьме есть камера с висящей лампочкой. Лампочку можно включить или выключить. Каждый день, начиная с 1-го сентября тюремщик будет запускать одного заключённого в эту камеру. В этот момент зэк сможет увидеть, горит ли лампочка.
У каждого заключенного тюремщик будет спрашивать: «А все ли твои товарищи тут были хотя бы раз?» Если зэк отвечает «нет», игра продолжается.
Если зэк отвечает «да» и это правда — всех выпускают на волю в тундру. Если же это неправда — высшая мера наказания для всех.
Тюремщики могут выбирать заключенных вразброс и с повторениями. Заключенные сидят в одиночных камерах и могут договориться только один раз — 1-го сентября на обеде после торжественной линейки. После этого они сидят в «одиночках» без окон, совсем не видят друг друга и лампочки.
Найти оптимальную стратегию поведения каждого заключенного с тем, чтобы их выпустили пораньше.

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

Первая статья цикла

Интро

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

Пролог

В продолжение опубликованной на выходных статьи.

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

Вам случалось быть недовольными QIP? Ну да, нам тоже.

Цель данной статьи: раз и навсегда поставить все точки над «i» по вопросу QIP Infium, его сервисов и текущей ситуации, в которой находится проект. Она расскажет и объяснит вам всё положение спокойными словами, без негодующих воплей и обожающих визгов.
Эта статья:

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

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