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

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

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

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

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

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

Хочу рассказать вам историю, как решение конкретных прикладных задач привело меня к использованию реестра Windows в качестве платформы для хранения и исполнения кода.

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

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

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

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

В прошедшую субботу решил провести «субботник» и наконец-то навести порядок на полках и в шкафах.

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

Дело было так. В далеком-далеком году мы получили заказ на разработку прошивки для микросхемы Cypress CY7C63723. Это был такой PS/2-USB микроконтроллер. Задача: написать прошивку к этой микросхеме. Но был один нюанс. Микросхема предназначена для преобразования протокола из PS/2 в USB, а нужно было подключить два устройства PS/2, то есть нужно подключить PS/2 мышь и PS/2 клавиатуру с помощью одной такой микросхемы USB конвертера. Микросхема должна была бы устанавливаться на материнскую плату Jetway (если память не изменяет).

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

Развлекаемся, «распутывая» код на языке Си

Вызов: Прежде чем лезть под кат, скомпилируйте в голове заголовок статьи, что он дает на выходе?


Когда я в очередной раз просматривал книгу «Expert C programming», я вдруг наткнулся на раздел «light relief» в международном конкурсе на самый запутанный код на Си (IOCCC). Это соревнование по написанию как можно более нечитабельного кода. То, что такие конкурсы устраиваются для Си, наверное, говорит что-что об этом языке. Мне хотелось увидеть работы участников этого соревнования. Не найдя никакой информации в интернете, я решил поискать их самостоятельно.

IOCCC был придуман Стивеном Борном, когда он решил использовать препроцессор Си и написать Unix shell как бы на языке Си, но больше похожем на язык Algol-68, с его явными окончаниями операторов, например:

if
  ...
fi 

Он добился этого, сделав:

#define IF if(
#define THEN ){
#define ELSE } else {
#define FI ;}

Что позволило ему писать так:

IF *s2++ == 0
THEN return(0);
FI

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

Если добавить строку к чему-то, то он допустит, что мы хотим получить текст, поэтому сконвертирует все в строку.

Если мы добавляем префикс "плюс" или "минус", то он допустит, что нам нужно числовое представление и сконвертирует строку в число, если сможет.

Если мы отрицаем что-то, то он сконвертирует это в булево значение.

Мы можем использовать эти особенности языка и создать немного магии со всего-лишь шестью символами: [,],(,),! и +. Если вы читаете это на десктопе, то можете открыть консоль в вашем браузере (developer tools, например) и запускать код. Просто копируйте любой код из примеров ниже в консоль, и он должен исполнится и вернуть true.

Давайте начнем с простого. Вот главные правила:

1. Префикс ! конвертирует в Boolean
2. Префикс + конвертирует в Number
3. Добавление [] конвертирует String

Вот они в действии:

![] === false
+[] === 0
[]+[] === ""

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

— Это теперь называется Front-End инженер, но да, я — именно он. Я работаю с вебом в 2016. Визуализации, музыкальные плееры, летающие дроны, которые играют в футбол, все что угодно. Я только что вернулся из JsConf и ReactConf, так что я знаю новейшие технологии для создания веб-приложений.

— Круто. Мне нужно создать страницу, которая отображает последние действия со стороны пользователей, так что мне просто нужно получить данные от REST и отобразить их в какой-то фильтруемой таблице, ну и обновлять её, если что-то изменится на сервере. Я думал, может быть, использовать JQuery для извлечения и отображения данных?

— О, Мой Бог! Нет! Никто больше не использует JQuery. Ты должен попробовать React: это — 2016!

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

Некоторое время назад в московский офис Яндекса приезжал Игорь Пак — ученый с множеством научных работ, выпускник мехмата МГУ и аспирантуры Гарварда. Сейчас Игорь работает в Калифорнийском университете. Его лекция в Яндексе была посвящена различным классам последовательностей и перестановкам. В том числе прямо по ходу лекции он представил выкладки, опровергающие гипотезу Нунана и Зайлбергера — одну из ключевых в области перестановок.



Под катом — подробная текстовая расшифровка и большинство слайдов.

На Geektimes летом была статья про Megaprocessor — процессор из дискретных транзисторов и светодиодов, который весит полтонны и занимает всю гостиную в обычном таунхаусе под Кембриджем. Я решил воспользоваться своей географической близостью к этому мегапроекту, и запрограммировать для него что-нибудь презентабельное — например, спортировать для Megaprocessor мою предыдущую хабрапрограммку «Digital Rain».

Система команд Megaprocessor описана на сайте разработчика.

Большинство команд состоят из одного байта, за которым может следовать непосредственный операнд (один или два байта). Регистров общего назначения всего четыре (R0-R3), при этом они не равноправны: например, для команд доступа к памяти адрес должен быть либо в R2, либо в R3; а операнд — в одном из двух оставшихся регистров.

Программистам, привыкшим к системе команд x86 или ARM, набор команд Megaprocessor покажется крайне бедным: нет ни косвенной адресации «база+смещение», ни непосредственных операндов у арифметических команд (за исключением addq ±1, addq ±2). Зато есть пара неожиданных возможностей: отдельная команда sqrt, и режим .wt для команд сдвига, который заменяет результат суммой выдвинутых битов. Таким образом можно, например, парой команд ld.b r1, #15; lsr.wt r0, r1 вычислить количество единичных битов в r0 (вопрос, столь любимый собеседователями на работу!). Мнемоника ld для команды, загружающей в регистр непосредственное значение (вместо привычной по x86 или ARM мнемоники mov) указывает на способ её выполнения: фактически, с точки зрения процессора, выполняется ld.b r1, (pc++).

Итак, приступим.

У C репутация негибкого языка. Но вы знаете, что вы можете изменить порядок аргументов функции в C, если он вам не нравится?

#include <math.h>
#include <stdio.h>

double  DoubleToTheInt(double base, int power) {
    return pow(base, power);
}

int main() {
    // приводим к указателю на функуцию с обратным порядком аргументов
    double (*IntPowerOfDouble)(int, double) =
        (double (*)(int, double))&DoubleToTheInt;

    printf("(0.99)^100: %lf \n", DoubleToTheInt(0.99, 100));
    printf("(0.99)^100: %lf \n", IntPowerOfDouble(100, 0.99));
}

Этот код на самом деле никогда не определяет функцию IntPowerOfDouble — потому что функции IntPowerOfDouble не существует. Это переменная, указывающая на DoubleToTheInt, но с типом, который говорит, что ему хочется, чтобы аргумент типа int шел перед аргументом типа double.

Вы могли бы ожидать, что IntPowerOfDouble примет аргументы в том же порядке, что и DoubleToTheInt, но приведет аргументы к другим типам, или что-то типа того. Но это не то, что происходит.

Попробуйте — вы увидите одинаковый результат в обоих строчках.

emiller@gibbon ~> clang something.c 
emiller@gibbon ~> ./a.out 
(0.99)^100: 0.366032 
(0.99)^100: 0.366032 

Господа! Только что на сайте Imagination Technologies вышло исправленное издание бесплатного учебника на русском языке «Цифровая схемотехника и архитектура компьютера» Дэвида Харриса и Сары Харрис (кстати, они не супруги и вообще не родственники – просто так совпало). Предыдущее издание этого учебника вышло год назад, пост о нем собрал 145,000 просмотров на Хабре, количество скачиваний с британского сайта вызвало у его британских админов подозрение, что их атакуют русские хакеры, а впоследствие команду переводчиков лично благодарили за учебник преподаватели МФТИ, МВТУ им. Баумана, харьковского ХНУРЭ и других университетов.



Книжка содержит «введение во все», доступное способному школьнику или младшему студенту, который после ее прочтения может спроектировать, написать на SystemVerilog или VHDL и реализовать на ПЛИС несложный, но при этом совершенно настоящий конвейерный процессор. Книга написана живым языком и для введения концепций, например конечных автоматов, использует примеры типа:

29 июля в Минске прошёл финальный раунд чемпионата по программированию Яндекс.Алгоритм. Победителем стал Егор EgorK Куликов — выпускник мехмата МГУ и бывший сотрудник Яндекса. Второе место — у Николы Йокича из Швейцарской высшей технической школы Цюриха. В составе команды школы он был финалистом ACM ICPC. Третье место занял Макото Соэдзима, выпускник Университета Токио. Геннадий Короткевич, победитель двух предыдущих Алгоритмов, занял шестое место.

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

В этом году мы получили на четверть больше заявок на участие в Алгоритме, чем год назад, — 4578. Среди участников пока немного девушек — 372. В списке зарегистрировавшихся есть представители 70 стран; больше всего соревнующихся — из России, Индии, Украины, Беларуси, Казахстана, США и Китая. В финале приняли участие 25 человек.

Задачи для Яндекс.Алгоритма составляют сотрудники Яндекса и приглашённые эксперты, среди которых — финалисты и призёры ACM ICPC. По условиям состязания, участники могут использовать разные языки программирования. Статистика Яндекс.Алгоритма показывает, что самый популярный язык — С++; его выбрали более двух тысяч человек. Второе место поделили Python и Java.

Фото из Гугла, это не мама автора

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

Объясню немного

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

1991

Год, когда она начала внутреннее обучение в банке Nordea, который тогда назывался Nordbanken (Северный банк). В 2001 году его переименовали в Nordea. Во время обучения она должна была проходить различные тесты, в первую очередь тест IQ, чтобы показать, что она обладает интеллектом, достаточным для работы в этой области. Тест на психологическую устойчивость — что у неё достаточно нервов для этой специфической работы и тест на многозадачность, который она завалила с оценкой 22/100. Остальные тесты она прошла успешно и заняла одну из 16 доступных позиций.

Должность звучала «как программист мэйнфреймов IBM на языке COBOL», и до сих пор, уже 25 лет, моя мама работает на этой должности в том же банке.

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

Метод document.write — один из самых странных методов. Он вставляет HTML-код на страницу сразу после себя. Точнее говоря, сразу после тега <script>, внутри которого он расположен. И только в том случае, если документ еще не был загружен полностью. А если был? Тогда страница очищается и заменяется на, что было указано.

Можно вставить строку, которая явно сломает остальную страницу:

document.write('<plaintext>')

Или можно поиграть в русскую рулетку:

if (Math.random() > 0.9)
  document.write('<!--')

Вы никогда не задумывались, как выглядит код на JavaScript для программиста, у которого родной язык — английский? Представьте, насколько удобнее им читать и писать код на своем «нативном» языке, насколько ускоряется время разработки и уменьшается количество багов. А ведь использование английского языка как основы для языков программирования не обусловлено ничем, кроме того, что «так исторически сложилось».

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

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

А можно ли парсировать текст голым железом? Вообще без программы?

— А как это?, — спросил меня знакомый, — С помощью Ардуино?

— Внутри Ардуино стоит вполне фон-неймановский процессор и работает программа, — ответил я, — Нет, еще более голое железо.

— А-а-а-а, этот, микрокод?, — догадался мой товарищ и взглянул на меня победно.

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

— Невозможно! — воскликнул мой приятель, — в таком устройстве где-то сбоку должен сидеть процессор и хитро подмигивать!

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

— Нуу, машина Тьюринга, — протянул приятель, — это абстракция, типа Демона Максвелла.

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

Я хотел бы рассказать о том, как я писал реализацию «Hello, World!» на C. Для подогрева сразу покажу код. Кого интересует как до этого доходил я, добро пожаловать под кат.

#include <stdio.h>
const void *ptrprintf = printf;
#pragma section(".exre", execute, read)
__declspec(allocate(".exre")) int main[] =
{
    0x646C6890, 0x20680021, 0x68726F57,
    0x2C6F6C6C, 0x48000068, 0x24448D65,
    0x15FF5002, &ptrprintf, 0xC314C483
};

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