Ненормальное программирование *

Писать Нормальные Алгоритмы Маркова, это безумно интересно и забавно. Интересно ли узнать о том, как мы делали лучшую в мире IDE для Нормальных Алгоритмов Маркова?

Мэтт Паркер, отметившийся в проектах Numberphile и Standup Maths, в компании с командой Domino Computer Builders построили, наверное, самый медленный компьютер в мире из костей домино.


Немного деталей под катом.

Я расскажу вам о том, как можно создать компьютер (точнее, пока только его часть) на электромагнитных реле своими руками.

На Хабре недавно проскочила ещё одна статья про вычисления на шаблонах C++ от HurrTheDurr. В комментариях к ней лично я увидел вызов:

> С каждым новым релизом количество способов нетривиально вывихнуть себе мозг при помощи С++ продолжает увеличиваться)
> > Особенно, если не менять подход к реализации игрового поля и продолжать пытаться все вычисления выполнять не над константами, а над типами.

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

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

#include <iostream>

#include <LC/kernel.h>
#include <LC/church_numerals.h>

int main()
{
    // Представление натуральных чисел в виде лямбда-абстракций
    typedef ChurchEncode<2> Two;    // 2 = λfx.f (f x)
    typedef ChurchEncode<3> Three;  // 3 = λfx.f (f (f x))

    // * = λab.λf.a (b f)
    typedef Lambda<'a', Lambda<'b', Lambda<'f',
                Apply<Var<'a'>, Apply<Var<'b'>, Var<'f'> > >
        > > > Multiply;

    // Вычисление (* 2 3)
    typedef Eval<Apply<Apply<Multiply, Two>, Three>> Output;

    // Переход обратно от лямбда-абстракций к натуральным числам
    typedef ChurchDecode<Output> Result;

    std::cout << Result::value;
}

А на выходе получать такое:

ilammy@ferocity ~ $ gcc cpp.cpp
ilammy@ferocity ~ $ ./a.out
6

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

Под катом находится очередное прокомментированное конструктивное доказательство Тьюринг-полноты шаблонов C++ в виде compile-time интерпретатора бестипового лямбда-исчисления (плюс печеньки в виде макросов и рекурсии).

Статья не о том, чем заняться, пока собирается проект.

Фраза «Шаблоны — полноценный, тьюринг-полный, язык» часто воспринимается с недоверием. Это же просто обобщающая возможность современных языков программирования, откуда там вычислительные возможности? Так думал и я. Теперь хочу переубедить остальных, попутно объясняя принципы работы шаблонов для начинающих, вроде меня.

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

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

Привет, недавно мне совершенно случайно попалась в руки такая железка:


Ну железка и железка, подумал я… На плате присутствует микроконтроллер РВЕ035, расширитель IO m5l8243p, ИР12 между РФ5 и контроллером и там еще где-то ЛН1 в стороне болтается. Мне сразу понравилась хорошая раритетная ПЗУ на 2Кб РФ5 в панельке в золоте. Думаю, сниму ее, а остальное смело в утиль, бо вся плата залита лаком по самое небалуйся..А потом все-таки стало интересно, а что это такое вообще?

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

Вчера компания Apple выпустила обновление безопасности iOS 7.0.6 для iPhone 4 и более поздних моделей, iPod touch 5-го поколения и iPad 2+. Одновременно выпущен аналогичный патч 6.1.6 для iPhone 3GS и iPod touch 4-го поколения.

Обновление закрывает уязвимость CVE-2014-1266, которая позволяет злоумышленнику из «привилегированной позиции в сети» перехватывать и модифицировать пакеты в сессиях, защищённых SSL/TLS. Речь идёт о MiTM-атаке с подменой трафика.

В лаконичном пояснении Apple говорит, что при установке защищённого соединения по SSL/TLS система не способна определить аутентичность соединения. Проблему решили путём «добавления недостающих этапов валидации».

После продолжительного обсуждения объявлены победители конкурса Grand C++ Error Explosion Competition. Награды должны были объявить в двух номинациях. Участники первой соревновались по максимальному количеству ошибок на минимальный объём кода. Вторая номинация — творческая, там важно не количество и размер, а качество и красота глюков.

В итоге, абсолютным победителем назван программист Эд Хэнвей (Ed Hanway), приславший такую программу.

#include ".//.//.//.//jeh.cpp"
#include "jeh.cpp"
`

Речь у нас пойдёт о поэзии. Минимализм языка программирования Forth и красота образов демосцены подтолкнули программиста Брэда Нельсона к идее Forth Haiku. Подражая японским хайку, Брэд писал свои первые программы из трёх строк, состояли они из пяти, семи, и снова пяти слов. Но в отличии от традиционного японского жанра, поэзия на языке Forth порождала картины не в воображении читателя, а зримо, на экране компьютера. Эта затея могла бы остаться причудой одинокого фаната компьютерного ретро (Forth прочно ассоциируется со старыми добрыми семидесятыми), если бы Брэд не воплотил её на самой что ни на есть современной платформе (WebGL) и не сделал бы онлайн-редактор общедоступным.

Вот пример кода Forth Haiku и изображение, которое этот код создаёт: «Light Drop» by Brad Nelson.

: iii x y z*
Sin ; x 5 * x y
- iii exp y iii

Впереди нас ждут немало удивительных (в том числе и «живых») картин, но сперва — немного теории.

Прислал мне тут один программист смешную круглую программку на языке C, там был #define определяющий подчерк, а потом из подчерков и минусов был нарисован круг:

            _-_-_-_
       _-_-_-_-_-_-_-_-_
    _-_-_-_-_-_-_-_-_-_-_-_
  _-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
  _-_-_-_-_-_-_-_-_-_-_-_-_-_
    _-_-_-_-_-_-_-_-_-_-_-_
        _-_-_-_-_-_-_-_
            _-_-_-_

При вычислении этого выражения получалось число π. Ну на самом деле, там чего-то съехало и вместо π получалось 0.250, но не в этом дело.

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

В прошлом году были популярны темы, как написать программу за 30 строк кода. Все примеры были сделаны на JavaScript. Для запуска таких программ требуется не только веб страница, но и браузер, разные библиотеки, ядро ОС. На самом деле работают не 30 строк кода, а десятки, сотни мегабайты программного кода, находящиеся в памяти компьютера.
А можно ли написать не полностью бесполезную программу за 30 строк ассемблера, без лишних библиотек и мегабайт ОС?
В этой статье я опишу, как можно сделать крестики-нолики за 30 строк ассемблера. UPD Теперь всего за 20 строк. UPD2 И 18 или 16 строк без единого условного ветвления.

Опубликован исходный код программ-победителей 22-го конкурса программ с обфусцированным кодом на C. Участвовать в конкурсе могут готовые программы размером меньше 4096 байт, при этом количество значимых символов, без учёта пробелов, знаков табуляции и знаков; ( ), не должно превышать 2048. Впрочем, в этом году многие участники воспользовались эксплоитом для бага в модуле вычисления размера программы, так что в 2013 году на конкурс были представлены, пожалуй, самые продвинутые программы за все годы проведения соревнований.

Например, вызывает искреннее восхищение эмулятор 8086-компьютера размером 4043 байта (исходный код) с полным набором инструкций 8086/186, который поддерживает флоппи-диски и HDD и PC-спикер.

Всем программистам рано или поздно приходится передавать данные. Ни для кого не секрет, что библиотек сериализации в Java существует примерно >9000, а в C++ они вроде и есть, а вроде их и нет. К счастью для большинства, несколько лет назад появился Google Protobuf, который принёс достаточно удобный способ определять структуры данных и быстро завоевал всенародную любовь. Это была фактически первая, доступная широким массам библиотека, позволяющая гонять по сети готовые структуры данных, не связываясь при этом с чем-то вроде XML. На дворе был 2008 год.

Вернёмся немного назад. В 2006 году простой индийский программист (как бы подозрительно это ни звучало!) Анил Мадхавапедди, один из самых известных сейчас в мире OCaml-разработчиков и автор свежевышедшей книги Real World OCaml, защищал в Кембридже кандидатскую диссертацию. Именно о ней я сегодня вам и расскажу.

Анил сразу пошёл дальше, чем Google. Он сразу подумал, для чего люди обычно пересылают по сети какие-то формализованные структуры данных? Чтобы реализовать какой-то протокол. А что такое протокол? Это какой-то конечный автомат. А где мы можем взять хороший пример сложного, хорошо спроектированного и проверенного временем протокола? Да прямо в обычном сетевом стеке! Итак, были взяты набор сетевых структур данных и протоколов: Ethernet frame, IPv4, ICMP, TCP, UDP, SSH, DNS и DHCP и постановка задачи: большая часть этих протоколов (особенно SSH и DNS) реализуются, что называется «руками», а хочется, чтобы не было типичных для C переполнений буфера, все переходы совершались автоматически, это всё можно было верифицировать, и чтобы работало быстро, а не как обычно.

Поскольку никто не будет читать диссертацию, сразу скажу: это более чем удалось. По результатам работы были написаны референсные реализации DNS и SSH-сервера и произведено сравнение с BIND и OpenSSH. OCaml-реализации давали по сравнению с традиционными прирост производительности от незначительного, до почти двухкратного. Кроме того была найдена ошибка в RFC на SSH (рабочая группа была уведомлена и RFC исправлен). О том, что было сделано, и как с этим жить, читайте под катом.

Приукрасим забытое старое

Для начала — небольшая картинка в качестве эпиграфа. Продолжение — под катом.

Как-то так вышло, что завелся у меня Windows 8 планшет. Не очень удачная модель — громоздкий как помощник, слабоватый как рабочая станция, но зато с стилусом, а самое важное, с 32-битной Win32 системой. Имея некое количество старых игр с распродаж GOG и Steam, я планировал как-нибудь засесть с этой таблеткой и переиграть все, что можно и нельзя. Но вот как-то не хватало времени и настроения, да еще и пробные запуски показали, что играть надо с мышью — курсор от тач-скрина убегал неизвестно куда, да и правый клик долгим нажатием был бы откровенно неудобным. Планшет пылился пол-года в углу до недавней раздачи Fallout от GOG и эта раздача подтолкнула меня к действию. Начинался вечер пятницы, планшет обзавелся USB мышью, а я устроился поудобнее на диване и начал по списку с самого верха — с Arcanum.
Через пол-часа создания персонажа (а ведь это дело очень важное и ответственное!) левая рука с трудом держала устройство, а запястье правой подозрительно начало тянуть, намекая о туннельном синдроме и прочих радостях неудобного хвата. Вспомнив нехорошим словом разработчиков некой эргономичной складывающейся мыши, я полез искать драйвера, патчи или еще хоть что-то, чтобы играть с тачскрина или хотя бы стилуса.
Патчей не нашлось. Единственный похожий драйвер был платным и без пробного режима. Вот в этот момент в голову и пришла идиотская (это я теперь понимаю!) мысль — «там ведь наверняка приходит какой-то WM_TOUCH и неправильно преобразуется в WM_MOUSEMOVE»… Забегая вперед, Арканум теперь у меня полностью управляется с тачскрина, правда, выходные закончились и больше хочется спать, чем играть.

Это достаточно вольный перевод статьи. Дело в том, что несмотря на конструкции в одну строчку, материал сложен для понимания.
Беря во внимание то, что в комментариях Прелюдия или как полюбить Haskell просили, чтобы код был понятный, я внёс достаточно ремарок, и, надеюсь, код будет понятен и тем, кто далёк от Хаскеля.

Давайте начнём с самого трудного — с самого заголовка: многим непонятны все его слова.
Хаскель — это чистый и ленивый функциональный язык.
Лёб — это немецкий математик, о котором мы поговорим чуть позже.
Ну, и наконец, самое интересное — странные петли.

Странные петли — это запутанные категории, когда двигаясь вверх или вниз в иерархической системе, находишь то же самое, откуда начал движение.
Зачастую такие петли содержат само-референтные ссылки.
Например, подобной странной петлёй обладает рекурсивные акронимы: «PHP — PHP: Hypertext Preprocessor».
Ну, и на сегодняшний день наиболее загадочным словом, содержащим странные петли, является понятие «я».

Странные петли будоражат людей своей красотой. И очень приятно, когда находишь их в самых неожиданных местах. Очень интересные функции со странными петлями можно написать на Хаскеле.

Немецкий математик Лёб мигрировал в 39-м году ХХ-го столетия в Великобританию. Лёб, в частности, развивал математическую логику и миру прежде всего известен Теоремой Лёба. Это теорема развивала труды Гёделя о неполноте математики. Теорема Лёба о взаимосвязи между доказуемостью утверждения и самим утверждением, она гласит, что

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

Всю эту сложность высказывания можно записать символически:


Можно ли такую функцию написать на Хаскеле?! Можно! И всего в одну строчку!

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

Ущербный — имеющий изъян, неполноценный. Вредный, недостаточный.

Наследование

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

J – самый ненормальный и самый эффективный язык из известных мне языков. Он позволяет быстро разрабатывать, а также вызывать ненормативную лексику у людей, незнакомых с ним и смотрящих на код.

J слишком необычный. И сложный для изучения. У людей, сталкивающихся с J не хватает мотивации, чтобы его изучить. Синтаксис непривычный.
В этом посте я хотел помочь вам заглянуть дальше, что будет, если вы его изучите и чем он интересен. По своему опыту знаю, что преимущества этого языка сразу не очевидны. В посте я не собираюсь останавливаться на разборе конструкций. Только в обзоре. Предлагаю просто окунуться в примеры, попробовать ощутить мощь языка. Узнать, чем прекрасен язык, без изучения. Писать статьи, обучающие программированию на нем – дело сложное и думаю, не нужное. Он не так прост, чтобы это сделать кратко, а с обучающими материалами на официальном сайте нет никаких проблем. Главное – желание. Им и займемся.