Hacker News Digest

Разработка собственной ОС освобождает от ограничений коллективной работы и позволяет экспериментировать с необычными паттернами. Вдохновлённый статьёй LWN «Object-oriented design patterns in the kernel», я реализовал все сервисы ядра через «виртуальные таблицы» (vtables) — структуры с указателями на функции, обеспечивающие полиморфизм на чистом C.

Базовая идея

struct device_ops {
    void (*start)(void);
    void (*stop)(void);
};

struct device {
    const char *name;
    const struct device_ops *ops;
};

Разные устройства регистрируют свои реализации ops, а вызывающий код работает с единым интерфейсом. Таблицу можно менять на лету без изменения клиентов.

Применение в моей ОС

• Сервисы: сетевой менеджер, оконный сервер и др. описываются структурой

struct service_ops { void (*start)(void); void (*stop)(void); void (*restart)(void); };

Позволяет из терминала запускать/останавливать потоки без хардкода.

• Планировщик: интерфейс yield, block, add, next реализуется разными стратегиями (round-robin, SJF, FIFO). Политику можно заменить без пересборки ядра.
• Файлы: как в Unix, «всё есть файл». Сокеты, устройства и обычные файлы предоставляют одинаковые read/write, скрывая сложность реализации.

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

• Обсуждение показывает, что в ядре Linux и других проектах на C давно применяют «объектно-ориентированные» приёмы через структуры с указателями на функции (таблицы виртуальных методов).
• Некоторые считают это удобным и экономным по памяти, другие — источником проблем с читаемостью, отладкой и оптимизацией.
• Упоминаются готовые микро-фреймворки (co2, carbon) и примеры из tmux, где такие паттерны уже используются.
• Спор идёт о необходимости явного параметра this: одни ценят прозрачность, другие — «сахар» неявного this в C++/Java.
• Вопрос «почему бы не перейти на C++/другой язык» сводится к контролю над памятью, отсутствию «магии» и возможности оставаться на C ради производительности и простоты.

Проект «Zoo» — мини-реализации самых влиятельных статических систем типов последних 50 лет. Начнём с простых и дойдём до зависимых типов. Всё пишем на Rust — просто потому что удобно и забавно строить чисто функциональные языки на не-функциональном.

Это не учебник, а выходные развлечение. За теорией и доказательствами смотрите TAPL, ATTAPL, PFPL и оригинальные статьи (ссылки в приложении). Здесь же — грязные детали реализации: структуры данных, AST, логика, всё, что можно осилить за уик-энд.

Код — идиоматичный Rust с полноценным парсером и тестами (lalrpop, logos, ariadne). Примеры урезаны, но понятнее продакшен-реализаций. Парсинг и MLIR считаем решёнными задачами, поэтому не фокусируемся на них.

Четыре «зверька»:

• Algorithm W (775 строк) — классический Hindley–Milner, полиморфный λ-исчисление.
• System F (1090 строк) — второе λ-исчисление, параметрический полиморфизм, Mini-OCaml.
• System F-ω (3196 строк) — высшие рода, паттерн-матчинг, дататипы, Haskell-lite.
• Calculus of Constructions (6000 строк) — иерархия универсумов, индуктивные типы, крошечный Lean.

MIT-лицензия, хобби-проект. Нашли опечатку — присылайте pull-request.

• Пользователи хвалят Elaboration Zoo как полезный ресурс для изучения нормализации по вычислению и вывода неявных переменных.
• Просят аналогичный «зоопарк» для линейных типов и предлагают добавить быстрый вариант Hindley–Milner из OCaml.
• Автору советуют включить тёмную тему для блоков кода и рассмотреть простой однонаправленный type-checker в духе Featherweight Java.
• Уточняют, что присутствие индуктивных типов делает реализацию ближе к CIC, но Lean всё же сильнее за счёт аксиомы выбора.
• Картинки с животными вызывают путаницу; большинство считают их просто AI-орнаментом без смысловой нагрузки.