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

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

Привет, Хабр! Представляю вашему вниманию перевод статьи Substitution Processes (1962 год) авторства Эдсгера Дейкстры. Разделение на параграфы не оригинальное.

Введение

Машина определяет (по самой своей структуре) язык, а именно: свой язык ввода — и напротив, семантическое определение языка задаёт машину, способную понимать его. Другими словами, машина и язык — это две стороны одной и той же медали. Я собираюсь описать такую медаль. Я оставляю на вас решение того, какой же из этих двух аспектов предмета моего разговора, на ваш взгляд, самый важный, так как сам считаю этот выбор довольно смешным. Язык, наброски которого я собираюсь вам предоставить, является непозволительно трудным для человека, а машина, которую я собираюсь описать, является порочно неэффективной.

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

Кейт Холман и Зак Барт — разработчики из игровой студии Zachtronics. Если вы любите запутанные технические статьи о создании игр для 25-летних компьютеров, возможно, вам понравятся наши игры-головоломки: SpaceChem, Infinifactory, TIS-100 и SHENZHEN I/O!

Приступаем

Смогут ли два программиста, привыкшие к созданию игр для современных компьютеров с гигабайтами ОЗУ и полноцветными HD-дисплеями, портировать свои игры под MS-DOS? Никто из нас не имел опыта разработки на таком старом оборудовании, но работа в искусственно ограниченных системах — основа дизайна игр Zachtronics, поэтому мы были обязаны попробовать!

Проект начался с того, что Зак создал макет SHENZHEN SOLITAIRE, мини-игры в пасьянс из нашей игры SHENZHEN I/O (также продаваемой как отдельная игра). Вот как пасьянс мог выглядеть на экране 256-цветного VGA-дисплея:



Похоже на игры, которые можно было увидеть на экранах PC начала 90-х! Теперь осталось только написать код, правда?

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

---

Совсем немного истории

Головоломка «Instant Insanity» (Мгновенное Безумие), возможно, одна из самых востребованных для иллюстрации применимости теории графов в решении задач подобного ей типа.

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

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

Infinifactory

В этой статье мы поговорим о «магической» константе 0x5f3759df, лежащей в основе элегантного алгоритмического трюка для быстрого вычисления обратного квадратного корня.

Вот полная реализация этого алгоритма:

float FastInvSqrt(float x) {
  float xhalf = 0.5f * x;
  int i = *(int*)&x;  // представим биты float в виде целого числа
  i = 0x5f3759df - (i >> 1);  // какого черта здесь происходит ?
  x = *(float*)&i;
  x = x*(1.5f-(xhalf*x*x));
  return x;
}

Этот код вычисляет некоторое (достаточно неплохое) приближение для формулы



Сегодня данная реализация уже хорошо известна, и стала она такой после появления в коде игры Quake III Arena в 2005 году. Её создание когда-то приписывали Джону Кармаку, но выяснилось, что корни уходят намного дальше – к Ardent Computer, где в середине 80-ых её написал Грег Уолш. Конкретно та версия кода, которая показана выше (с забавными комментариями), действительно из кода Quake.
В этой статье мы попробуем разобраться с данным хаком, математически вывести эту самую константу и попробовать обобщить данный метод для вычисления произвольных степеней от -1 до 1.

Да, понадобится немного математики, но школьного курса будет более, чем достаточно.

Пост ностальгии по игрушкам, которые мы сами для себя писали в детстве.
Лазая по просторам App Store ища очередную игрушку для своего айпада, наткнулся на старинную игрушку “Братья Пилоты”. Сразу купил, поставил и прошёл на одном дыхании (уже наверное в 3 раз). Но более всего задержался на эпизоде с холодильником. Уж больно меня прёт эта головоломка.



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

Подняв старые бекапы я нашёл исходную игру. Запустил её в dosbox и пропал для внешнего мира на пару часов.

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

— Что, даже на том нечитаемом эзотерическом языке, где есть всего пара команд, которые едва-едва симулируют машину Тьюринга?
— Да, этот язык называется brainfuck. Я знаю brainfuck.

И это был не трюк — мы проверили. Я называл известный мне язык программирования, он тратил пару минут в Интернете на то, чтобы освежить свои знания по нему — и был способен писать на этом языке работающие алгоритмы. Я никак не мог понять этого. Ему, как и мне, было тогда около 18 лет — как он мог в этом возрасте знать все эти языки?


Интерпретатор brainfuck, написанный на brainfuck

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

Сегодня я советую своим студентам «постараться изучить все языки программирования». Подумайте сами — ведь эта идея лучше, чем все вот эти «В этом году я выучу Go! Ой, нет, теперь говорят что в моде Rust — выучу лучше Rust! Или Swift ...». Просто выучите все — не ошибётесь. А эта статья, возможно, вам в этом немного поможет.

Upd. 9.7.2017: обновлён раздел про vim. Спасибо вимерам за ценные дополнения.

Вступительное слово

Зачем нужна ещё одна, 1001я публикация на эту тему? Статей про vim и nano написано огромное количество, но как правило они касаются только одного из редакторов, либо представляют из себя общий обзор. Чтобы в одной были сжато описаны оба редактора, но при этом без углубления в дебри приведены все основные клавиши управления для полноценной работы, я не не нашёл. Поэтому, почитав найденные материалы, я начал их конспектировать, так и родилась эта статья.


Любой текстовый редактор можно освоить «методом тыка». Но только не vim.
Чем nano лучше vim?
Из nano можно выйти без reset'а! (с) Интернет


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

Введение в интро

Демосцена — это о создании классных штук, которые работают в реальном времени (как бы «крутятся в вашем компьютере»). Их называют демки. Некоторые из них по-настоящему маленькие, скажем, 64k или меньше — такие называются интро. Название происходит от рекламирования или представления взломанных программ (crack intro). Итак, интро — это просто маленькая демка.

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

Бинарник под Windows: guberniya_final.zip (61.8 kB) (немного ломается на картах AMD)

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

Чтение на английском может быть полезно как в изучении иностранного языка, так и в пополнении профессиональных знаний. Мы задались вопросом, какие новостные порталы, блоги и прочие Интернет-ресурсы на английском языке имеют четкую IT-направленность и наиболее интересны разработчикам, админам, тестировщикам, веб-дизайнерам и людям других технических специальностей в России?

Чтобы создать ТОП полезных англоязычных IT-ресурсов, мы решили воспользоваться статистикой Хабрахабра. Наряду с авторскими публикациями, здесь публикуются и переводы интересных материалов. Такие посты отмечены тегом «Перевод» и содержат ссылку на оригинал.

Всего за последние полгода на Хабре было около 1000 переводных статей. Мы посчитали для каждого источника переводов средний рейтинг публикации, среднее число просмотров и количество добавлений в Избранное. Затем были удалены сайты со средним рейтингом публикаций менее 16 и числом просмотров менее 4000. Полученные сайты мы отсортировали по числу переводов на Хабре из этого источника, так как, возможно, это характеризует ресурс как часто обновляемый и «объёмный».

Собрав и проанализировав таким образом данные о публикациях, мы получили наш ТОП100 компьютерных сайтов на английском, который мы надеемся будет полезен и вам.

«Когда я задался целью получить действительно случайное число, то не нашел для этого ничего лучшего, чем обычная игральная кость» — писал в 1890 году Фрэнсис Гальтон в журнале Nature. «После того, как кости встряхивают и бросают в корзинку, они ударяются друг о друга и о стенки корзинки столь непредсказуемым образом, что даже после легкого броска становится совершенно невозможным предопределить его результат».


(Игральные кости времён Римской Империи)

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

После интересной обратной разработки игрового движка Comprehend (см. Recomprehend) я подбирал новый проект для реверс-инжиниринга игры под DOS. За долгие годы разные люди реверсировали множество старых популярных игр и опубликовали для них спецификации и инструменты. Например, на сайте shikadi.net есть куча информации об играх, в которые я играл в детстве.

Я обнаружил, что для реверс-инжиниринга игры The Lost Vikings компании Blizzard (тогда она называлась Silicon and Synapse), похоже, не предпринималось никаких серьёзных попыток. Игра была выпущена в 1993 году, на закате эры DOS, и очень нравилась мне в юности. The Lost Vikings — это головоломка-платформер, в которой игрок управляет тремя викингами, каждый из которых имеет собственные умения. Викингам нужно объединить свои силы для решения загадок и прохождения уровней с различной тематикой: космический корабль, доисторический мир, Древний Египет. На изображении ниже показан первый уровень игры (источник: Strategy Wiki):



Казалось, что эту игру разобрать будет довольно просто. Уровни основаны на тайловых картах и содержат простые загадки: кнопки, включающие и отключающие объекты, передвижные ящики и поднимающий предметы кран. И на самом деле, бóльшая часть проекта по обратной разработке была достаточно прямолинейной. У игры есть один пакетный файл данных, содержащий сжатые блоки файлов. Блоки кодируют различные ресурсы игры, такие как спрайты, карты, звуки и т.д. Я написал несколько утилит, которые можно использовать для просмотра ресурсов игры: The Lost Vikings Tools.

Мы в Alconost продолжаем переводить советы опытного консультанта Джоша Барнса о выходе на азиатские рынки. Мы уже публиковали его выводы о Южной Корее и Японии. Сегодня речь пойдет о еще двух весьма перспективных рынках.

Если вы хотите воспользоваться потенциалом растущих азиатских рынков и локализовать для этого мобильную игру, возможно, следует подумать о Тайване и Гонконге. Несмотря на меньшую численность населения, это — крупные рынки (только на Тайване в 2015 году мобильные игры заработали 400 млн долл. США) с большой распространенностью смартфонов (73,4% — в Тайване, 69,8% — в Гонконге). Неплохой и средний годовой доход от игр на одного пользователя: на Тайване он составляет $116,60, рынок Гонконга мало в чём уступает. По словам Карстена Ламмерта (Carsten Lammert), занимающегося привлечением клиентов в компании Gamania, пользователей на тайваньском рынке намного больше, однако в Гонконге их легче удержать, поэтому здесь и средний доход на одного пользователя раза в 1,5–2 выше. Это говорит о том, что в каждом из этих случаев следует разрабатывать отдельную маркетинговую стратегию.

Обсудим, что же еще нужно знать об этих рынках.

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

Bash-скрипты: начало
Bash-скрипты, часть 2: циклы
Bash-скрипты, часть 3: параметры и ключи командной строки
Bash-скрипты, часть 4: ввод и вывод
Bash-скрипты, часть 5: сигналы, фоновые задачи, управление сценариями
Bash-скрипты, часть 6: функции и разработка библиотек
Bash-скрипты, часть 7: sed и обработка текстов
Bash-скрипты, часть 8: язык обработки данных awk
Bash-скрипты, часть 9: регулярные выражения
Bash-скрипты, часть 10: практические примеры
Bash-скрипты, часть 11: expect и автоматизация интерактивных утилит

Сегодня поговорим о bash-скриптах. Это — сценарии командной строки, написанные для оболочки bash. Существуют и другие оболочки, например — zsh, tcsh, ksh, но мы сосредоточимся на bash. Этот материал предназначен для всех желающих, единственное условие — умение работать в командной строке Linux.

Речь пойдёт о программах и библиотеках для UNIX-подобных систем, распространяемых в виде исходного кода (в том числе в виде тарболлов), написанных обычно на C и C++ (хотя этот же порядок работы может применяться к софту на любом языке). Многие вещи в этой статье написаны применительно конкретно к GNU/Linux, хотя многое из статьи может быть обобщено и на другие UNIX-подобные ОС.

Под словом «пакет» я понимаю в этой статье пакет с исходными текстами, причём не пакет конкретного дистрибутива GNU/Linux, а просто пакет, исходящий от оригинальных авторов софта (UPD от 2017-02-09: кроме тех случаев, где из контекста ясно, что слово «пакет» употреблено в другом смысле).

В этой статье я разберу следующие вопросы:

• Вот скачал программу или библиотеку. Как её собрать и установить? Как воспользоваться библиотекой?
• Что такое префикс (prefix) установки? В чём разница между сборкой и установкой? Куда обычно устанавливают программы?

Я разберу только совсем базовые вещи. Те, которые типичные участники сообщества свободного ПО, программирующие на C и C++ под UNIX-подобные системы, обычно уже знают. Как создавать тарболлы (на примере «голого» make) и как устанавливать чужие тарболлы. Advanced советы по созданию «хороших» пакетов я не дам. «Продвинутые» вещи читайте в документации систем сборки, в замечательной статье «Upstream guide» от Debian (в её конце есть ещё куча ссылок о создании «хороших» пакетов). Многое в этой статье можно было сделать по-другому, моя цель: дать хотя бы один способ, не пытаться объять необъятное.

Предисловие

→ Первая часть

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

В этой части мы поговорим о том, что же такое случайная и псевдослучайная генерации, какие алгоритмы могут дать нам равновероятно ничем не похожие друг на друга лабиринты и в чем их минусы. Героями нашего сегодняшнего приключения станут алгоритм Уилсона и алгоритм Олдоса-Бродера для создания случайного остовного дерева (Uniform Spanning Tree). ОСТОРОЖНО ТРАФИК.

Сегодня в блоге программы «Менеджмент игровых интернет-проектов», мы подготовили и перевели для вас статью, написанную главным редактором Kill Screen Заком Баджором про искусственный интеллект на примере игры The Suspect и фильма “Она”.

Уже в течение трёх лет я веду блог разработки моего нового roguelike-проекта. Истории игры в нём уделено довольно мало обсуждений, что отражает её малую информативную роль и важность в процессе разработки альфа-версии. На самом деле за посредственной и избитой научно-фантастической историей 7DRL, изложенной в версии для гейм-джема, последовал перезапуск проекта в 2013 году, и первое растягивание сроков разработки произошло только из-за воплощения уникальной детализированной истории. Всё, происходившее позже, тем или иным образом служит для поддержки нарратива.

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