Простое введение в завтипы

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

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

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

К счастью, есть неплохая статья 2009 года с введением в зависимые типы на примере языка Agda. В ней авторы демонстрируют несколько примеров того, как языки с завтипами могут статически решать проблемы, которые раньше разрешались только на стадии исполнения.

#literature

nanochess и bootOS

Иногда люди создают программы исключительно ради искусства.

К примеру, проект nanochess не имеет никакой практической пользы, кроме удовольствия от низкоуровневого программирования. Ну и конечно, обучения. В рамках этого проекта был разработан десяток простых игр, написанных на ассемблере для Intel 8088. Каждая из них умещается в один сектор дискеты, 512 байт. А еще автор проекта, Оскар Толедо (Oscar Toledo), опубликовал несколько книг с комментариями к исходному коду игр, объяснив, как они работают.

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

#digest

Монадные трансформеры Haskell

В нашем недавнем посте мы вспоминали Haskell с присущими ему концепциями, заимствованными из теории категорий. Вспоминали и монадные трансформеры.

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

#literature

Использование model finding при разработке компилятора

Chapel — язык программирования, созданный для упрощения параллельных вычислений.
Компилятор этого языка, Dyno, использует нетривиальную логику для разрешения имен: например для того, чтобы понять, что требуется вызывать — метод с именем foo или одноименную функцию.

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

Один из авторов рассказал в своем блоге, как решил использовать известный model finder Alloy 6 для моделирования возможных состояний и поиска контрпримера. Простая модель на Alloy позволила доказать, что исходный алгоритм был неверным, и существовали примеры программ, в которых происходило неверное разрешение имен.

Хороший аргумент за использование формальных методов. Особенно столь легковесных и простых в применении.

#digest

Введение в формальную верификацию программ

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

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

#literature

Избавление от зависимости

Давненько не было у нас внутренних кеков :)

#fun

Введение в системное программирование под Plan 9

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

Возможно, кто-то заинтересуется немного необычной альтернативой подобного курса, которая изложена в бесплатно распространяемой книге «Introduction to Operating Systems Abstractions Using Plan 9 from Bell Labs». Автор книги, Франсиско Бальестерос (Francisco J Ballesteros), рассказывает о типовых системных абстракциях, доступных в Plan 9, и показывает, как ими можно воспользоваться на практике.

#literature

xv6 на Rust

Многие, конечно, уже слышали про xv6 — маленькую операционную систему, разработанную в качестве методического пособия для курса MIT 6.828.

Эта игрушечная, но вполне полноценная Unix-система хорошо описана в этой книге Расса Кокса, Франса Каашоека и Роберта Морриса (Russ Cox, Frans Kaashoek, Robert Morris). На наш взгляд, это издание, дополненное кодом самой ОС, — лучшее введение в архитектуру операционных систем из доступных сегодня.

xv6 всегда привлекала внимание исследователей и хобби-разработчиков благодаря подробному описанию, простой реализации, ортогональному набору возможностей и способности работать на современном железе. Например, авторы xv6 не так давно перенесли ее на RISC-V и решили использовать эту архитектуру в качестве базовой для курса. Так что система адаптируется к «модным трендам» в мире системного программирования.

А что там насчет безопасных языков программирования, например Rust? Ведь RISC-V + Rust было бы мегакомбо, не так ли?! Что же, сразу два проекта на Github занимаются переписыванием xv6 на Rust: octox и rxv6.

Приятного погружения!

#literature

A Tiny Linux-compatible Kernel

Большинство курсов по разработке ОС фокусируются или на ядре Linux, что может быть слишком для непосвященных студентов, или на примитивных учебных ОС, которые совсем далеки по сложности от своих старших собратьев. Кажется, нужно что-то среднее — например, система, достаточно продвинутая, чтобы запускать бинарники из GNU/Linux.

Сказано — сделано, и Владислав Вальчев (Vladislav Valtchev) создал проект Tilck, цель которого — разработать минималистичное ядро ОС, совместимое с Linux на бинарном уровне. Так, чтобы можно было брать программы, собранные для этого популярного ядра, и запускать в учебной ОС.

Пожелаем автору удачи в его проекте, а сами го ковыряться в исходном коде!

#digest

Floppy Bird

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

Что же, вот еще один шедевр низкоуровневого программирования: игра, работающая без операционной системы, Floppy Bird. По названию вы, наверное, уже догадались, что она копирует механику знаменитой Flappy Bird с мобильных устройств. Игра написана на ассемблере x86, и работает в реальном режиме, используя сервисы BIOS.

#fun

Технология аппаратной виртуализации

Гипервизорами с поддержкой Intel VMX или AMD-V уже никого не удивить. Даже если вы не используете в своей работе виртуальные машины, они незаметно присутствуют в вашей повседневной жизни. Например, Windows 10 использует Hyper-V для создания защищённого компартмента, внутри которого исполняются важные для системы функции.

Но как работают расширения виртуализации в вашем процессоре, и просто ли написать свой гипервизор?

Можно обратиться к официальной документации Intel или AMD, погрузиться в исходный код KVM, Xen или ACRN, чтобы разобраться в вопросе досконально. Но можно удовлетворить свой технический интерес и более простым образом, обратившись к хорошему туториалу, где автор уже все разжевал для читателя.

Такой материал мы сегодня и посоветуем: серию уроков по разработке гипервизора для Intel от Ryanfam.

Несмотря на то, что Intel неоднократно расширял возможности аппаратной виртуализации новыми фичами, основы не изменились, и туториал вряд ли серьезно устареет со временем.

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

#digest

Изучаем ассемблер ARMv8 на примерах

Если вы спросите у системного программиста, хорошо знакомого с ARM-платформой, что бы вам почитать, чтобы освоить 64-битный ассемблер ARMv8, то он, вероятно, ответит, что нужно читать ARMARM (ARM Architecture Reference Manual). Это действительно всеобъемлющий документ, позволяющий глубоко познакомиться с платформой.

Но если вас интересует только практическое введение в ассемблер для этой архитектуры, советуем обратиться к статье "A Guide to ARM64 / AArch64 Assembly on Linux with Shellcodes and Cryptography". Это очень удачное и понятное введение, снабженное неплохой практической частью, где авторы реализуют различные криптографические алгоритмы непосредственно на языке ассемблера.

#literature

Наглядная демонстрация алгоритма сжатия JPEG

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

Статья Омара Шехаты (Omar Shehata) на сайте Parametric Press наглядно демонстрирует работу алгоритма сжатия изображений, используемого для формата JPEG.

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

Подобного явно не хватает во многих ВУЗах на занятиях алгоритмами и структурами данных, правда? 😁

#digest

Легковесные формальные методы для верификации примитивов синхронизации

Мало кто не слышал про такие проекты, как seL4 или CompCert, потратившие невероятное количество сил на формальную верификацию микроядра операционной системы и компилятора языка Cи соответственно.

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

Сегодня мы хотели бы поделиться ссылкой на страницу, на которой Расс Кокс (Russ Cox) собрал всю историческую информацию про верификацию примитивов синхронизации в ядре Plan 9.

Применение Spin/Promela помогло найти реальные проблемы в реализации рандеву, что использовалась в системе, ну и, конечно, исправить ее.

Обратите внимание, насколько просты модели на этом языке. При помощи Spin/Promela можно верифицировать сетевые протоколы, примитивы синхронизации и параллельные алгоритмы.

Инструмент за долгие годы существования стал стабильным и быстрым, его отлично документировали. Почему бы не попробовать его в своих задачах?

#lilerature

Макро-RISC-V

RISC-V любят за открытость спецификаций: например, многие ресечеры в академической среде выбирают именно эту архитектуру в качестве основы для своих работ. Даже всем известный учебный проект операционной системы xv6, как мы уже видели, переехал на RISC-V, оставив позади легаси платформы x86.


Вендоры железа не отстают, и уже можно встретить достаточно производительные платы на базе этой архитектуры. Дрю ДеВолт (Drew DeVault) даже пробовал одну из таких железок в качестве десктопа, и оно было почти юзабельно.


Но и хобби-проекты часто выбирают эту открытую архитектуру за основу. Так в рамках проекта Pinapple One Филип Скандера (Filip Szkandera) разработал макропроцессор с архитектурой RV32I на простой дискретной логике. То есть это полноценный 32-битный процессор, правда собранный на нескольких логических микросхемах, и работающий с очень низкой частотой — порядка половины мегагерца.


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


#digest

Низкоуровневый бутстрап языков программирования

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

Но как быть с доверием к компилятору? Кен Томпсон в статье "Reflections on Trusting Trust" упоминал, что компилятор, которому мы доверяем, может быть "зараженным" и продуцировать зараженный код. Есть ли способ получить доверенный компилятор сразу?

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

Примерно так устроен проект Картика Агарама (Kartik Agaram) Mu. В рамках этого проекта автор разработал несколько языков программирования, каждый из которых может исполняться на платформе x86 и собирать компилятор языка более высокого уровня, пока не получится компилятор ЯВУ наподобие C.

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

Не менее интересны и проекты, пытающиеся создать минимальный интерпретатор языка Forth.

StoneKnifeForth представляет собой примитивный Forth, все слова которого записываются одним ASCII символом. Компилятор для такого языка написать несложно даже без ассемблера под рукой. Для упрощения бутстрапа автор использует примитивный интерпретатор, разработанный на языке Python. Первая рабочая копия компилятора, полученная благодаря бутстрапу, уже является исполняемым файлом ELF и позволяет расширять набор конструкций языка привычными словами Forth.

Не менее интересен проект PlanckForth, реализацию которого скрупулезно написали в машинных кодах (уж точно никто кроме авторов не оставит закладки). Файл с HEX-дампом достаточно пропустить через утилиту xxd и на выходе получится исполняемый файл компилятора минималистичного Forth. Этот примитивный язык может быть расширен уже своими внутренними средствами до приемлемого уровня, позволяющего написать что-то более сложное.

#digest

Microsoft ♥ Open Source and Rust

То, что Microsoft много вкладывается в Open Source, уже ни для кого не секрет: компания выложила в свободный доступ множество своих продуктов, регулярно контрибьютит в исходный код ядра Linux и вообще всячески поддерживает независимых разработчиков.

С недавних пор компания также активно вкладывается в развитие Rust на своей платформе, так как хорошо понимает выгоды от перевода своих системных компонентов на memory- и type-safe язык.

Ну а совсем недавно Microsoft анонсировала следующий шаг — публикацию инструментария для разработки драйверов Windows на Rust. Теперь WDM/WDF-интерфейсы, привычные для системного разработчика, доступны хоть и в ржавом, но безопасном и современном языке! 🙂

#digest

Еще один lowtech шифр

Мы уже описывали один занятный криптографический алгоритм, который можно применять без использования компьютера, он назывался ElsieFour(LC4). Напомним, что относительно других «ручных» шифров, этот предоставлял довольно серьезные гарантии.

Сегодня мы хотели бы упомянуть другой практичный ручной потоковый шифр, который использует колоду карт — Solitaire cypher. Если следовать некоторым ограничениям на переиспользование ключей и длину сообщений, то можно добиться вполне приличных гарантий и от столь простой lowtech системы шифрования.

#digest

Исходный код Elite с комментариями

Elite — известная серия космических симуляторов с открытым миром, которая зародилась в далеких 80-х. Творение Дэвида Брэбена и Яна Белла стало мегапопулярным, поскольку в те годы игра позволяла путешествовать по трехмерному, хотя и довольно примитивному, случайно сгенерированному миру, сражаться с космическими пиратами, торговать, пристыковываться к заправочным станциям, апгрейдить корабль на заработанные кредиты. И все это на домашних восьмибитных компьютерах вроде BBC Micro!

Была реализация Elite и для Nintendo Entertainment System, известной в СНГ в основном благодаря китайским клонам этой приставки. Мы не встречали ее на китайских пиратских картриджах, но у обеспеченных обладателей настоящей Nintendo такую игру можно было встретить.

Как же разработчики уместили столь продвинутые игровые механики в программе для такой примитивной игровой системы?
Естественно, чтение исходников столь продвинутого проекта может натолкнуть на интересные мысли, научить оптимизировать код, выжимать из примитивного железа все возможное. И сегодня это возможно, конечно, если вы не боитесь ассемблера MOS 6502.

Исходный код, выложенный на Github, прокомментирован невероятно подробно — уверены, что опытному программисту будет легко справиться с чтением, даже если вы плохо знакомы с архитектурой NES. А туториал для освоения ассемблера 6502 мы уже рекомендовали ранее.

Приятного погружения!

#digest

Кажется, вы больше не должны давать тестовые задания кандидатам на дом

Наткнулись на интересную статью, где через призму AI рассматриваются тестовые задания, которые компании нынче дают кандидатам.

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

#digest

Бесплатные книги по архитектуре программных систем

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

В первую очередь, это два тома книги «The Architecture of Open Source Applications», где описываются красивые архитектурные решения, найденные в известном открытом ПО, например в LLVM, Sendmail, PyPy, Git и других.

Еще одна книга из серии посвящается вопросам производительности программных систем. В ней на примерах известных open source программ разбираются хорошие практики, которые могут помочь и в ваших собственных проектах.

Отличное дополнение к уже названным книгам — брошюра «500 Lines or Less», демонстрирующая компактные реализации решений для нетривиальных задач: создание MVP программы трехмерного моделирования, объектной модели, табличного редактора, или интерпретатора байт-кода Python.

#literature