Обновить
137.29

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

Извращения с кодом

Сначала показывать
Период
Уровень сложности

Как писать квайны

Время на прочтение4 мин
Охват и читатели42K
Введение

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

Однако, на самом деле, написать квайн на каком-либо языке не так сложно, как кажется. Сейчас я расскажу, как сделать это на различных языках программирования. Более того, мы не будем использовать «хаки» интерпретеруемых языков вроде операции вывода исходного кода и функций типа eval и напишем квайны на интерпретируемых и компилируемых языках.
Читать дальше →

Поиск гамильтонова пути с помощью мембранной системы за полиномиальное время

Время на прочтение9 мин
Охват и читатели6.3K
Составление алгоритмов в рамках той или иной классической алгоритмической модели (машины Тьюринга и Поста, нормальные алгоритмы Маркова, счетчиковые машины Минского и т.д.) смело можно относить к ненормальному программированию в силу исключительной минимальности выразительных средств этих моделей. Не исключением из данного правила является и такая относительно новая алгоритмическая модель, как мембранные системы или P-системы, придуманная румынским ученым Георгием Пауном чуть более десяти лет назад. Целью этого нововведения было исследование вычислительных возможностей клеткоподобных структур (имеются в виду биологические клетки), а вообще вся эта деятельность была инспирирована знаменитым опытом Адлемана по решению задачи о поиске Гамильтонова пути с помощью ДНК-вычислений. Как это ни странно, но данный топик посвящен как раз решению (к сожалению, виртуальному) той же самой задачи, но уже с помощью простейшей мембранной системы. Итак, под катом читатель найдет 1) краткое описание того, что такое мембранные системы; 2) как «программировать» такое «железо»; 3) мембранный алгоритм решения задачи о гамильтоновом пути, обладающий полиномиальным временем выполнения.
Читать дальше →

Чем изучение Haskell/Python вредит программисту

Время на прочтение5 мин
Охват и читатели28K
От переводчика:

На этот перевод меня толкнула очередная ситуация «мозгового ступора» при написании банального кода на C++/C#: я часами смотрел на уродливый код, но не мог сделать его по-настоящему лучше; мне пришлось просто принять то, что уродливым его видел только я один, и это была моя проблема, а не проблема в коде или языке. Я вспомнил те времена, когда такого со мной не было — а заодно вспомнил и эту старую статью, автор которой пострадал так же, как и я, при этом хорошо написав об этом.


Я обнаружил, что изучение Python и Haskell не улучшило меня как программиста на других языках (что противоречит тому, что иногда пишут об этом). В частности, Haskell — являясь настолько непохожим на императивные языки — по идее, должен был дать мне просветление в программировании, которое помогало бы мне даже без использования какого-либо языка вообще. Мой текущий опыт не совсем соответствует этому, и вот, почему:
Читать дальше →

Не дадим Windows Phone умереть! Как я написал свои клиенты VK, YouTube для Nokia Lumia? Сам себе экосистема ч.2

Уровень сложностиСредний
Время на прочтение16 мин
Охват и читатели31K
image

Windows Phone… услышав название этой мобильной системы, поневоле начинаешь с теплотой вспоминать своего недавнего, такого необычного мобильного друга, как будто прошло всего пару месяцев с момента смены смартфона на iPhone/Android. А ведь с момента фактической смерти Windows Phone прошло уже почти 10 лет! Увы, время вспять уже не повернуть, а мобильное подразделение Nokia не спасти, однако при наличии навыков разработки мобильных приложений, большом энтузиазме и фанатизме, есть шанс вернуть жизнь своему старому другу! Недавно я снова загорелся диким энтузиазмом и смог вернуть жизнь старенькой «люмии», написав собственные клиенты нужных мне сервисов с нуля — и готов поделиться этим с вами во всех подробностях!

Сегодня вы узнаете о моей мотивации привносить жизнь старым смартфонам, о тонкостях разработки мобильных приложений, чем Windiows Phone был на голову выше Android в техническом плане и о том, почему провал Windows Phone — одна из самых больших потерь мобильного рынка. Интересно? Тогда добро пожаловать в статью!
Читать дальше →

Ферритовый ROM для самых маленьких

Время на прочтение7 мин
Охват и читатели14K

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

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

Итак, мы рассмотрим память на ферритовых кольцах, причем, даже не RAM, а ROM.

Читать далее

Живое видео и цифровой звук на 8-битной игровой приставке

Время на прочтение14 мин
Охват и читатели13K

В 2016 году американский музыкант Sergio Elisondo опубликовал музыкальный альбом инструментальных кавер-версий A Winner Is You (отсылка к древнему мему, происходящему из классической игры Pro Wrestling), в котором он в одиночку исполнял музыку из популярных игр для восьмибитной приставки NES на настоящих музыкальных инструментах. Необычным дополнением к этому релизу стала его версия в виде картриджа для игровой приставки NES, запускаемая на ней и воспроизводящая музыку из альбома в виде полноценного аудио, а не типичного для этой приставки довольно примитивного синтезированного звука. Я занимался разработкой программной части этого не вполне обычного проекта.

Дальше больше

Как сегодня создаются 64k intro: погружение в Immersion

Время на прочтение14 мин
Охват и читатели26K
image


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


Работа над проектом заняла лучшие свободные часы последних двух лет жизни. Всё это началось во время проведения Revision 2015, большого мероприятия, устраиваемого каждый год в Германии во время пасхальных каникул. Мы вдвоём болтали по дороге из отеля в место проведения мероприятия. Предыдущим вечером уровень конкуренции в области 64kB intro оказался высоким. Очень высоким. Опытная и хорошо известная венгерская группа Conspiracy наконец вернулась с серьёзной, потрясающей работой. Наш лучший враг Approximate идеально успел по времени с завершением цикла выпуска и показал значительные улучшения в сторителлинге. Продуктивная группа Mercury обрела собственный зрелый стиль дизайна в интро, которое не оставляло сомнений в своей победе.

Компьютеры Советской России с троичной сбалансированной системой счисления

Время на прочтение7 мин
Охват и читатели61K

компьютер сетунь


"Возможно, самая красивая система счисления — это сбалансированная троичная" — Дональд Е. Кнут, Искусство программирования, Издание 2.

Многие знают, что компьютеры хранят данные и работают с ними с помощью двоичной системы счисления. Одно из главных объяснений этому можно найти в схеме современных компьютеров, которые состоят из миллиардов простых и массово производимых транзисторов и конденсаторов, которые могут вместе представлять два состояния: высокое напряжение (1) и низкое напряжение (0).


Такая конструкция сегодня настолько распространена, что трудно себе представить, как компьютеры могут работать иначе. Но, в Советской России 50-х годов они работали иначе. Если вы вдруг не слышали про такое, загуглите "Сетунь" — сбалансированный трехкомпонентный компьютер, разработанный в 1958 году небольшой группой во главе с Брусенцовым, в МГУ.


Перед тем, как говорить о Брусенцове и Сетуни, давайте я немного объясню вам троичную сбалансированную систему счисления.


Сбалансированная троичность


Тернарная или троичная — это система счисления, в которой есть три вероятных значения: 0, 1 и 2. В её сбалансированной версии существуют три вероятности -1, 0 и +1, часто упрощённые до -, 0 и + соответственно.

Читать дальше →

Qemu.js с поддержкой JIT: фарш всё же можно провернуть назад

Время на прочтение18 мин
Охват и читатели12K

Несколько лет назад Фабрис Беллар написал jslinux — эмулятор ПК, написанный на JavaScript. После этого был ещё как минимум Virtual x86. Но все они, насколько мне известно, являлись интерпретаторами, в то время как написанный значительно раньше тем же Фабрисом Белларом Qemu, да и, наверное, любой уважающий себя современный эмулятор, использует JIT-компиляцию гостевого кода в код хостовой системы. Мне показалось, что самое время реализовать обратную задачу по отношению к той, которую решают браузеры: JIT-компиляцию машинного кода в JavaScript, для чего логичнее всего виделось портировать Qemu. Казалось бы, почему именно Qemu, есть же более простые и user-friendly эмуляторы — тот же VirtualBox, например — поставил и работает. Но у Qemu есть несколько интересных особенностей


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

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


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

Читать дальше →

Реактивное программирование в табличном процессоре

Время на прочтение20 мин
Охват и читатели38K


Табличный процессор (речь идет о MS Excel или LibreOffice Calc) — это довольно занятный и универсальный инструмент. Мне часто приходилось (и приходится) пользоваться его широкими возможностями: автоматизированные отчеты, проверка гипотез, прототипирование алгоритмов. Например, я использовал его для решения задач проекта Эйлер, быстрой проверки алгоритмов, реализовал парсер одного прикладного протокола (по работе надо было). Мне нравится наглядность, которую можно добиться в табличном процессоре, а еще мне нравится нестандартное применение всего, чего только возможно. На Хабре уже появлялись интересные статьи на тему нестандартного применения Excel:
«Assembler в 30 строк на Excel»
Чем заняться айтишнику в армии или как я на VBA игры писал
«RPG-игра в рабочей книге Excel»

В этой длинной статье я хочу поделиться своими экспериментами в реактивном программировании с помощью формул табличного процессора. В результате этих экспериментов у меня получился «компьютер» с процессором, памятью, стеком и дисплеем, реализованный внутри LibreOffice Calc при помощи одних только формул (за исключением тактового генератора), который можно программировать на неком подобии ассемблера. Затем, в качестве примера и proof-of-concept, я написал игру «Змейка» и бегущуюползущую строку для этого компьютера.
Читать дальше →

Мультиквайногенератор

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

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

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

Команда разработчиков «научила» квадрокоптер ловить шарики для пинг-понга

Время на прочтение1 мин
Охват и читатели5.1K


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

Читать дальше →

Числовые подписи

Время на прочтение3 мин
Охват и читатели2.4K
Меня всегда завораживала магия программирования — маленькие фокусы, в которых бессмысленный на первый взгляд код делает что-то интересное. Самые известные из них — «подписи», которые выводят на печать короткий текст (обычно имя автора). В прошлый раз я показала несколько таких фокусов, основанных на эзотерических языках программирования, и некоторым читателям они даже пригодились при подготовке новогоднего поздравления :-) Настоящая же магия — это создание таких вещиц на совершенно нормальном языке, который вы используете каждый день, например, на C++ или Java. В этой статье я покажу несколько способов вывести короткий текст с использованием в качестве исходных данных только числовых констант.

Disclaimer: большинство приведенных фокусов основаны на низкоуровневых действиях с памятью, поэтому результаты могут варьироваться в зависимости от архитектуры компьютера и используемого компилятора (я пользуюсь gcc).


C++ спокойно относится к маргинальным манипуляциям с памятью и указателями, поэтому обфускации типа задания строки числом — почти обычное дело :-) Самый простой пример:

Читать дальше →

Ближайшие события

Game++. Dancing with allocators

Уровень сложностиПростой
Время на прочтение34 мин
Охват и читатели6.9K

C и C++ не имеют встроенной сборки мусора, поэтому разработчик сам решает, как и когда выделять и освобождать память. Мы, конечно, можем покивать в сторону STL, сокрытия аллокаций в контейнерах, но от этого они никуда не денутся. Просто если раньше приходилось думать про выделенный кусок памяти, понимать, как он скажется на времени фрейма, помнить, что его надо удалить (а может, не надо и стоит оставить на следующий фрейм), то теперь всё заворачивается в сахарные контейнеры и разработку в стиле STL-blin-vse-sterpit. STL-то может и стерпит, и даже как-то будет ворочаться, однако не стоит полагаться исключительно на системный аллокатор, бездумно вызывая new или malloc для каждого запроса памяти. Вы ведь понимаете, что std::vector посреди цикла или горячей функции — это плохая идея?

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

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

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

Ребята из HFT, Database, Automotive и Embedded-систем наверняка могут рассказать немало интересных историй про оптимизацию new/delete. Давайте я расскажу немного про разные аллокаторы в играх?

Аллокатор аллокатору аллокации аллоцировал

Intel 4004 — процессор, изменивший мир

Время на прочтение9 мин
Охват и читатели37K

50 лет назад, 15 ноября 1971 года компания Intel представила процессор 4004. Трудно переоценить значимость этого события, именно с этой даты началась эра архитектуры x86, которую мы знаем и сегодня.

Поздравляю компанию Intel с этой знаменательной датой!

Далее будет немного истории, много теории, ещё больше практики и оригинальных фот.

Вперёд и с песней..

«Жизнь» на PostgreSQL

Время на прочтение4 мин
Охват и читатели21K
Недавно на Хабре была опубликована статья Морской бой в PostgreSQL. Должен признаться: я обожаю решать на SQL задачи, для SQL не предназначенные. Особенно одним SQL-оператором. И полностью согласен с авторами:

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

И еще. Будем честны: всегда использовать SQL по назначению — тоска зеленая. Вспомните, какие примеры приводятся во всех учебниках, начиная с той самой статьи Кодда? Поставщики да детали, сотрудники да отделы… А где же удовольствие, где же фан? Для меня один из источников вдохновения — сравнение процедурных решений с декларативными.

Я, позвольте, не буду объяснять, что такое Жизнь Джона Конвея. Скажу только, что — оказывается — используя клеточный автомат Жизни, можно построить универсальную машину Тьюринга. Мне кажется, это грандиозный факт.

Так вот, можно ли реализовать игру Жизнь одним оператором SQL?
Конечно можно

Quipu — эзотерический язык программирования на основе узелковой письменности Инков

Время на прочтение6 мин
Охват и читатели31K
Один мой друг, историк по профессии, подкинул мне замечательную идею об использовании древней мнемонической и счетной систем в современной криптографии. В процессе его рассказов об узелковой письменности Инков, я начал соображать, что все новое — хорошо забытое старое и было бы не плохо как-то применить древний опыт в современном мире. Первое, что пришло в голову — криптография. Это самое очевидное — просто сконвертировать узлы с ниток в байты и шифр готов. С одной стороны все казалось понятным, но потом я вспомнил про криптостойкость и другие параметры шифров и понял, что не обладаю достаточным опытом и знаниями в области криптографии, чтобы в одиночку разработать новый шифр.

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

Четвертая версия языка оказалось удачной: я написал факториал, затем генерацию последовательности Фибоначи и дюжину простых примерчиков аля “сумма чисел от 0 до 99”. Язык получился что надо: необычный и в тоже время с простой понятной идеей. Главное — язык может решить любую (ну или почти любую) задачу которую можно выразить в виде вычислимой функции.

А теперь все по-порядку

И целых 20 ядер мало

Уровень сложностиПростой
Время на прочтение27 мин
Охват и читатели14K

Если вы посмотрите на общую раздутость современного софта, загружаемые 100 гигабайтные игры, ежегодную Nvidia X090 дающую +20% год от года, и 20-ядерные процессоры, то со стороны может показаться, что оптимизация производительности неважно чего, будь то игры или другой софт, казалось бы, утратила свою актуальность. В эпоху безнаказанной производительности аппаратной части можно расплескивать хоть половину этой мощи, и пользователь этого даже не заметит. Это все может и верно, если вы не делаете игру. Почему же тогда на этих двадцати ядрах, фризит и тормозит (хорошо что не вылетает часто) игра выпущенная два года назад?

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

При том, что все эти 30 — 60 — 120 — 200 фпс в играх, это чисто маркетинговый показатель, это время с которой движок может создавать фреймы для видеокарты, но движок это не только картинка, есть физика — а она как работала на 30 фпсах 10 лет назад, так и работает. Или звуковая подсистема, так она вообще своей отдельной жизнью живет в своих приоритетных тредах, мы просто кидаем туда меседжи с настройками и номером фрейма, чтобы засинхронизировать это с картинкой. Это сложно, но решаемо, но звук не привязан к картинке.

Налево пойдешь проца не хватит...

Геймдев, про который мы забыли: как работали 2D-игры на кнопочных телефонах нулевых

Уровень сложностиСредний
Время на прочтение11 мин
Охват и читатели21K
image

Друзья! А вы помните, какими были мобильные игры в 2000-х годах? Помните, как разработчики умудрялись уместить целые миры в устройство с небольшим дисплеем, аппаратной клавиатурой, весьма слабым железом и парой сотен килобайт памяти? Но задумывались ли вы, как в своё время работали эти сами игры «под капотом»? В сегодняшней статье-ретроспективе предлагаю вспомнить мобильный геймдев нулевых и узнать, как же работали 2D Java-игры, какие API были доступны и что из себя представлял средний телефон тех лет! Интересно? Тогда добро пожаловать под кат!
Читать дальше →

Копия по мотивам «ячейки звукового синтеза Агат» для IBM PC/XT — «музыкальная ячейка»

Время на прочтение8 мин
Охват и читатели6.5K

ЯЗС - Ячейка Звукового Синтеза - дополнительная плата расширения для компьютера "Агат", нечто вроде примитивной звуковой карты, имеющая пять тональных и два ударных канала. Подробнее про нее можно почитать здесь: http://agatcomp.ru/agat/Hardware/SoundNCL/jzs52.shtml. Когда-то давно мне очень понравилась видео-демонстрация работы ЯЗС, и особенно понравился звук, издаваемый этим устройством. Так, как ПЭВМ Агат у меня нет, и никогда не было, а побаловаться с извлечением звуков и таймером КР580ВИ53 хотелось, появилась мысль повторить устройство, только на более доступную для меня (да наверное, и не только для меня) шину ISA-8 от компьютеров IBM PC - благо на барахолках купить любую плату с ISA шиной пока еще представляется возможным. 

Читать далее

Вклад авторов