Эта статья — перевод спецификации, посвященной описанию минимальной реализации типов-значений в Java, которую с нетерпением ждут уже несколько лет. Добро пожаловать в MVT!

Замечания к переводу

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

Периодически на хабре можно встретить статьи о том, какие невероятные вещи можно сделать на шаблонах C++: конечные автоматы, лямбда-исчисление, машина Тьюринга и многое другое.

Параметризованные типы в Java традиционно считаются лишь пародией на шаблоны C++ (несмотря на то, что их даже сравнивать как-то некорректно), и причины этого несложно понять. Тем не менее не всё так плохо, и компилятор Java можно заставить производить во время проверки типов любые вычисления, лишь бы хватило оперативной памяти. Конкретный способ это сделать был описан в ноябре 2016-го года в этой прекрасной публикации. Его я и хотел бы объяснить.

Для затравки приведу следующий код. Корректен ли он? Предлагаю скомпилировать и проверить, угадали ли вы результат.

class Sample {

    interface BadList<T> extends List<List<? super BadList<? super T>>> {}

    public static void main(String[] args) {
        BadList<? super String> badList = null;
        List<? super BadList<? super String>> list = badList;
    }
}

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

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

После прочтения Dive into Python или подобной ей и ознакомления с документацией возникает вопрос, а что читать дальше? Можно обратиться к списку книг на python.org. Там есть раздел Advanced Books, но в нем всего лишь 6 книг (седьмая не выходила), и только одну я бы назвал по-настоящему стоящей.

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

Ниже собраны сложные материлы про Питон, его устройство и возможности. Все на английском (грех, не знать технический английский). Про Dive into Python я слукавил. Большинство приведенных материалов требуют хорошее знание Питона и наличие опыта программирования на нем.

UPD от 2017-03-04: кто-то выполнил английский перевод. Обсуждение на Hacker News.

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

Костыли в UNIX начали возникать ещё с момента появления UNIX, а это было ещё раньше появления не только Windows, но даже вроде бы Microsoft DOS (вроде бы, мне лень проверять, проверяйте сами). Если лень читать, хотя бы просмотрите все пункты, что-нибудь интересное найдёте. Это далеко не полный список, это просто те косяки, который я захотел упомянуть.

Создатели шаблонов в C++ заложили основу целого направления для исследований и разработки: оказалось, что язык шаблонов C++ обладает полнотой по Тьюрингу, то есть метапрограммы (программы, предназначенные для работы на этапе компиляции) C++ в состоянии вычислить всё вычислимое. На практике мощь шаблонов чаще всего применяется при описании обобщенных структур данных и алгоритмов: STL (Standard Template Library) тому живой пример.

Однако, с приходом C++11 с его variadic-шаблонами, библиотекой type_traits, кортежами и constexpr'ами метапрограммирование стало более удобным и наглядным, открыв дорогу к реализации многих идей, которые раньше можно было воплотить только с помощью расширений конкретного компилятора или сложных многоэтажных макросов.

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

Определение 1. Однородный контейнер – это такой контейнер, в котором хранятся объекты строго одного типа.

Определение 2. Неоднородный контейнер — это такой контейнер, в котором могут храниться объекты разного типа.

Определение 3. Статический контейнер — это контейнер, состав которого полностью определяется на этапе компиляции.

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

Определение 4. Динамический контейнер — это контейнер, состав которого частично или полностью определяется на этапе выполнения.

По такой классификации, очевидно, существуют четыре вида контейнеров:

1. Статические однородные

   
   
   Сможете придумать пример?

   Обычный массив — int[n].

   
   

2. Статические неоднородные

   
   
   Примеры?

   Наиболее яркий пример такого контейнера — это кортеж. В языке C++ он реализуется классом std::tuple<...>.

   
   

3. Динамические однородные

   
   
   Догадались?

   Правильно, std::vector<int>.

   
   

4. Динамические неоднородные

   
   

   Вот об этом виде контейнеров и пойдёт речь в данной статье.

   
   

Примечание от переводчика:

Этот пост был написан и опубликован на Medium разработчиком приложений Адрианом Космачевским из Швейцарии. Кроме подготовки перевода его публикации, я также пригласил и самого автора, Адриана ( akosma ), на Хабр, для того, чтобы он смог лично ответить на любые вопросы участников сообщества, если таковые возникнут. Думаю, для общего удобства при общении в комментариях с ним стоит использовать английский (и, при желании, дублировать на русском).

---

Привет всем, я — сорокадвухлетний программист-самоучка, а это моя история.

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



Эти размышления привели меня туда, откуда все начиналось.

Я дебютировал в роли разработчика программного обеспечения в 10 часов утра 6 октября 1997 года, в городе Оливос, к северу от Буэнос-Айреса, в Аргентине. Был понедельник. Не так давно я праздновал свой 24-й день рождения.

Мир в 1997 году

Тогда он был немного другим. На веб-сайтах не было предупреждений об использовании cookie. Новаторскими в сети были сайты вида Excite.com, а моим любимым поисковиком был AltaVista.

Мой электронный ящик имел вид kosmacze@sc2a.unige.ch и был расположен на личном веб-сайте, который размещался по адресу http://sc2a.unige.ch/~kosmacze. Тогда мы еще оплакивали принцессу Диану, а Стив Джобс только-только вернулся на роль CEO и убедил Microsoft «вбросить» в Apple Computer 150 миллионов долларов. Digital Equipment Corporation подала в суд на Dell, останки Че Гевары вернули на Кубу, только начался четвертый (!) сезон «Друзей». Был убит Джанни Версаче, скончались Мать Тереза, Рой Лихтенштейн и Жанна Кальман. Люди зависали за Final Fantasy 7 на PlayStation, будто бы были наркоманами, Би-Би-2 начал вещание телепузиков, а Кэмерон только собирался показать миру свой «Титаник».

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

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

Как известно, в современных архитектурах x86(_64) и ARM виртуальная память процесса линейна и непрерывна, ибо, к счастью, прошли времена char near* и int huge*. Виртуальная память поделена на страницы, типичный размер которых 4 KiB, и по умолчанию они не отображены на физическую память (mapping), так что работать с ними не получится. Чтобы посмотреть текущие отображённые интервалы адресов у процесса, в Linux смотрим /proc/<pid>/maps, в OS X vmmap <pid>. У каждого интервала адресов есть три вида защиты: от исполнения, от записи и от чтения. Как видно, самый первый интервал, начинающийся с load address (соответствующий сегменту .text у ELF в Linux, __TEXT у Mach-O в OS X), доступен на чтение и исполнение — очень логично. Ещё можно увидеть, что стек по сути ничем не отличается от других интервалов, и можно быстро вычислить его размер, вычтя из конечного адреса начальный. Отображение страниц выполняется с помощью mmap/munmap, а защита меняется с помощью mprotect. Ещё существуют brk/sbrk, deprecated древние пережитки прошлого, которые изменяют размер одного-единственного интервала «данных» и в современных системах эмулируются mmap’ом.

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

• оптимально управляет уже выделенной памятью;
• значительно уменьшает количество обращений к ядру (ведь mmap / sbrk — это syscall);
• вообще абстрагирует программиста от виртуальной памяти, так что многие пользуются malloc’ом, вообще не подозревая о существовании страниц, таблиц трансляции и т. п.

Довольно теории! Будем щупать malloc на практике. Проведём три эксперимента. Работа будет возможна на POSIX-совместимых операционках, в частности была проверена работа на Linux и на OS X.

Предисловие

Для того чтобы установить на свой компьютер Linux и начать его использовать для конкретных задач существует масса способов. Выбор дистрибутивов чрезвычайно широк, на любой вкус и цвет — и «для домохозяек» и для продвинутых пользвателей, допускающие любой уровень кастомизации, в том числе и сборку из исходников под конкретное железо. Установка системы в принципе доступна любому, мало-мальски грамотному пользователю ПК. И, если не погружаться в популярные по сей дей холивары на тему «Linux vs Другая ОС», то и спользование данной системы не требует знаний, которые были обязательными для новоиспеченного линуксоида скажем десять лет назад. С моей, глубоко субъективной точки зрения, за более чем десять лет, которые я наблюдаю за развитием этой системы, линукс стал более дружественен к новичкам и избавился от многих проблем, присущих ему в прошлом. И это хорошо.

Пингвины ручной сборки...


На Хабре уже мелькала пара статей на тему LFS, например эта, или вот эта. Комментарии к последней наводят на закономерную мысль — если набор возможностей для установки Linux и его изучения и так исчерпывающе широк, зачем нужен LFS?

Не буду витеивато излагать истории о том «как космические корабли бороздят… и когда Земля была огненным шаром...». Я отвечу на поставленный вопрос исходя из своей позиции — я собираю LFS потому, что мне просто интересно это сделать. Я вижу в этом процессе хорошую возможность заглянуть «под капот» системы. Допускаю, что этот путь сложно назвать оптимальным. Тем не менее, данная статья, и последующие за ней будут посвящены процессу ручной сборки Linux-системы. Данные статьи не будут переводом документации по сборке — в этом нет особой нужды. Акценты будут расставлены на специфике и ньюансах процесса, с которыми пришлось столкнуться автору лично. Будем считать этот цикл чем-то вроде дневника неофита.

Реляционные базы данных (РБД) используются повсюду. Они бывают самых разных видов, от маленьких и полезных SQLite до мощных Teradata. Но в то же время существует очень немного статей, объясняющих принцип действия и устройство реляционных баз данных. Да и те, что есть — довольно поверхностные, без особых подробностей. Зато по более «модным» направлениям (большие данные, NoSQL или JS) написано гораздо больше статей, причём куда более глубоких. Вероятно, такая ситуация сложилась из-за того, что реляционные БД — вещь «старая» и слишком скучная, чтобы разбирать её вне университетских программ, исследовательских работ и книг.

На самом деле, мало кто действительно понимает, как работают реляционные БД. А многие разработчики очень не любят, когда они чего-то не понимают. Если реляционные БД используют порядка 40 лет, значит тому есть причина. РБД — штука очень интересная, поскольку в ее основе лежат полезные и широко используемые понятия. Если вы хотели бы разобраться в том, как работают РБД, то эта статья для вас.

Программисты часто сталкиваются с проблемами чтения математических нотаций, когда пытаются разобраться с теоретическими основами какого-либо языка программирования. Также с ними толкнулся и я в своих теоретических изысканиях. К счастью, мне очень помогла замечательная статья Джереми Сиека (Jeremy Siek), чьим переводом я хочу с вами поделиться. Надеюсь она поможет многим программистам-«не математикам».

nxweb – это новый встраиваемый высокопроизводительный веб-сервер для приложений на Си. По функциональности это фреймворк для написания обработчиков HTTP запросов. Аналоги: G-WAN/libevent/Mongoose, Apache/mod_<ваш любимый язык>, Tomcat, Node.js. Разработчик – Ярослав Ставничий. Меня проект заинтересовал прежде всего тем, что он представляет реальную альтернативу существующим решениям, каждое из которых обладает своими недостатками. Выбор – это хорошо. Возможно, и вам понравится сочетание особенностей, плюсов и минусов этого сервера.

Под катом подробная информация о проекте из интервью с разработчиком.

Суффиксное дерево – мощная структура, позволяющая неожиданно эффективно решать мириады сложных поисковых задач на неструктурированных массивах данных. К сожалению, известные алгоритмы построения суффиксного дерева (главным образом алгоритм, предложенный Эско Укконеном (Esko Ukkonen)) достаточно сложны для понимания и трудоёмки в реализации. Лишь относительно недавно, в 2011 году, стараниями Дэни Бреслауэра (Dany Breslauer) и Джузеппе Италиано (Giuseppe Italiano) был придуман сравнительно несложный метод построения, который фактически является упрощённым вариантом алгоритма Питера Вейнера (Peter Weiner) – человека, придумавшего суффиксные деревья в 1973 году. Если вы не знаете, что такое суффиксное дерево или всегда его боялись, то это ваш шанс изучить его и заодно овладеть относительно простым способом построения.

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

1. Разберемся, что такое контекстное меню и зачем оно нужно.
2. Реализуем свое контекстное меню, используя JS и CSS.
3. Затронем недостатки и ограничения используемого подхода, чтобы знать, какие проблемы могут нас предостерегать при выкатывании всего этого в продакшн.

Привет, Хабр!

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

Часто первое знакомство с линейной алгеброй выглядит как-то так:



Не очень вдохновляет, правда? Сразу возникает два вопроса: откуда это все взялось и зачем оно нужно.

Начнем с практики

Когда я занимался вычислительной гидродинамикой (CFD), один из коллег говорил: «Мы не решаем уравнения Навье-Стокса. Мы обращаем матрицы.» И действительно, линейная алгебра — «рабочая лошадка» вычислительной математики:

Наверняка вам известно, что планеты движутся вокруг солнца по эллиптическим орбитам. Но почему? На самом деле, они двигаются по окружностям в четырёхмерном пространстве. А если спроецировать эти окружности на трёхмерное пространство, они превращаются в эллипсы.



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

Что же это за 4-е измерение? Оно похоже на время, но это не совсем время. Это такое особенное время, которое течёт со скоростью, обратно пропорциональной расстоянию между планетой и солнцем. И относительно этого времени планета двигается с постоянной скоростью по кругу в 4 измерениях. А в обычном времени его тень в трёх измерениях двигается быстрее, когда она находится ближе к солнцу.

Тим Петерс разработал гибридный алгоритм сортировки Timsort в 2002 году. Алгоритм представляет собой искусную комбинацию идей сортировки слиянием и сортировки вставками и заточен на эффективную работу с реальными данными. Впервые Timsort был разработан для Python, но затем Джошуа Блох (создатель коллекций Java, именно он, кстати, отметил, что большинство алгоритмов двоичного поиска содержит ошибку) портировал его на Java (методы java.util.Collections.sort и java.util.Arrays.sort). Сегодня Timsort является стандартным алгоритмом сортировки в Android SDK, Oracle JDK и OpenJDK. Учитывая популярность этих платформ, можно сделать вывод, что счёт компьютеров, облачных сервисов и мобильных устройств, использующих Timsort для сортировки, идёт на миллиарды.

Но вернёмся в 2015-й год. После того как мы успешно верифицировали Java-реализации сортировки подсчётом и поразрядной сортировки (J. Autom. Reasoning 53(2), 129-139) нашим инструментом формальной верификации под названием KeY, мы искали новый объект для изучения. Timsort казался подходящей кандидатурой, потому что он довольно сложный и широко используется. К сожалению, мы не смогли доказать его корректность. Причина этого при детальном рассмотрении оказалась проста: в реализации Timsort есть баг. Наши теоретические исследования указали нам, где искать ошибку (любопытно, что ошибка была уже в питоновской реализации). В данной статье рассказывается, как мы этого добились.

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

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



Так и в ситуации с консолями MMC. Вы создаёте для себя «пульт управления» и при определённых ситуациях нажимаете на нужные «кнопки».
Публикация рассчитана на системных администраторов, желающих познакомиться с методом создания консолей управления Windows, путём использования mmc.exe.

В этом посте я постараюсь окончательно разобрать такие тонкие понятия в C и C++, как указатели, ссылки и массивы. В частности, я отвечу на вопрос, так являются массивы C указателями или нет.

Обозначения и предположения

• Я буду предполагать, что читатель понимает, что, например, в C++ есть ссылки, а в C — нет, поэтому я не буду постоянно напоминать, о каком именно языке (C/C++ или именно C++) я сейчас говорю, читатель поймёт это из контекста;
• Также, я предполагаю, что читатель уже знает C и C++ на базовом уровне и знает, к примеру, синтаксис объявления ссылки. В этом посте я буду заниматься именно дотошным разбором мелочей;
• Буду обозначать типы так, как выглядело бы объявление переменной TYPE соответствующего типа. Например, тип «массив длины 2 int'ов» я буду обозначать как int TYPE[2];
• Я буду предполагать, что мы в основном имеем дело с обычными типами данных, такими как int TYPE, int *TYPE и т. д., для которых операции =, &, * и другие не переопределены и обозначают обычные вещи;
• «Объект» всегда будет означать «всё, что не ссылка», а не «экземпляр класса»;
• Везде, за исключением специально оговоренных случаев, подразумеваются C89 и C++98.

Указатели и ссылки

Указатели. Что такое указатели, я рассказывать не буду. :) Будем считать, что вы это знаете. Напомню лишь следующие вещи (все примеры кода предполагаются находящимися внутри какой-нибудь функции, например, main):

int x;
int *y = &x; // От любой переменной можно взять адрес при помощи операции взятия адреса "&". Эта операция возвращает указатель
int z = *y; // Указатель можно разыменовать при помощи операции разыменовывания "*". Это операция возвращает тот объект, на который указывает указатель