Кратчайшее расстояние между двумя точками – прямая. Скорейший способ освоить язык программирования или фреймворк – создать работающий проект. Доцент Университета Теннесси Остин Хенли собрал в своём блоге идеи подходящих проектов, которые он советует студентам и профессиональными разработчиками:
- Текстовый редактор.
- Двумерная игра.
- Компилятор.
- Маленькая операционная система.
- Электронная таблица (задача со «звёздочкой»).
- Эмулятор консоли видеоигры (тоже трудно).
Пост получил 300 откликов на Hacker News и 100 комментариев на Reddit. Хенли дополнил подборку идеями из комментариев. Они перечислены в конце публикации.
Текстовый редактор
Мы используем текстовые редакторы ежедневно, но как они работают? Забудем на время о навороченных функциях. Как вывести окно с текстовым полем? Как создать мигающий текстовый курсор? Чтобы он перемещался и выделял текст. Чтобы вставлял и удалял новые символы. Без готовых текстовых компонентов, где всё придумано другими разработчиками.
Память. Как сохранить текстовый документ в памяти? Первая мысль – использовать массив. Но у массива ужасная производительность. Если только пользователь не робот, добавляющий текст лишь в конец документа. Изучите другие структуры данных и решите, какая подойдёт лучше.
Поведение курсора. Пусть маркер курсора мигает в середине текстового поля. Если нажать клавишу со стрелкой вверх ↑, куда он переместится? В тот же столбец символов? Не обязательно: если строка короткая, нужно поставить курсор в конец строки. Но как только встречается строка подлиннее, маркер должен возвратиться к исходному столбцу. Иначе при движении вверх указатель будет смещаться к левому краю.
В коммерческих редакторах курсор «помнит» исходное положение по горизонтали, и как только это возможно, возвращается на ближайшую позицию. Такие детали не замечаешь, пока не берёшься за дело.
Расширяем набор функций. И вот мы печатаем и удаляем в редакторе текст, выделяем строки и слова, курсор мигает и носится по экрану. Что ещё попробовать? Две задачи: 1) отмена и повтор действий, 2) перенос слов по слогам.
Как вести запись действий с минимальными затрами памяти? Сразу и не додумаешься. Хенли описал как шел к решению. Сначала пытался хранить состояния в массиве, затем попробовал шаблон проектирования Хранитель (англ. Memento). Наконец, остановился на Команде (англ. Command).
В каких темах вы разберётесь:
- Структуры данных для хранения текста: массив, rope, буферное окно, piece table.
- Поведение и реализация текстового курсора.
- Паттерны проектирования для undo/redo.
Для дальнейшего чтения:
- Соображения о структуре данных для текстового редактора (англ.).
- Пошаговая разработка текстового редактора на C++ (англ.).
Космические захватчики
Чтобы создать даже примитивную игру, нужно выбрать структуру данных и шаблон проектирования. Не увязая в игровом дизайне, реализуйте от начала и до конца двумерную игру. Например, клонируйте Space Invaders (рус. Космические захватчики). Лучше взять библиотеку 2D-графики: SDL для С, PyGame для Python или SFML для Java, C#, Go. Иначе мощный игровой движок скроет всё интересное.
Игровой цикл. Игра – это цикл с условиями. В программе непрерывно происходят три действия: отрисовка, получение данных от пользователя, обработка игровой логики. Пользователь нажимает на клавиши и щёлкает мышью. Логика игры определяет, как новые данные изменят поведение объектов. Персонажи перемещаются на экране – пользователь нажимает другие кнопки.
Отрисовка. Научитесь рисовать движение персонажей. Чтобы создать эффект движения объектов, изображения на экране должны быстро сменять друг друга.
Игрок атакует. Как считать однократный и двойной щелчок? Если пользователь зажал клавишу со стрелкой, должен ли объект ускорить движение? Как часто проверяется пользовательский ввод?
Логика игры. Поведения персонажей описывается логикой игры. Как динамически обновлять количество врагов? Подойдёт фабричный метод. Когда и как меняются позиции пуль? Как узнать, что враг повержен? Когда игра заканчивается?
А ещё? Готова основа игры – добавьте меню и титульный экран. Убедитесь, что игра с одинаковой скоростью работает на разных компьютерах. Создайте врагов поинтереснее с помощью искусственного интеллекта. Добавьте шейдерные эффекты, звук и многопользовательский онлайн-режим.
Для дальнейшего чтения:
Больше идей – в теге Разработка игр.
Компилятор для Tiny BASIC
Напишите свой компилятор простого языка, например, Tiny BASIC. Пусть компилятор транслирует его в симпатичный вам язык. Например, напишите на Python компилятор Tiny BASIC, который выводит код C#. Не нужно создавать сборку. Тем более если вам это неинтересно. Сосредоточьтесь на трансляции.
Порядок действий. Создавайте компилятор в том же порядке, в котором он будет работать с исходным кодом. Каждый этап подразумевает собственный инструмент и свой набор алгоритмов.
1. На стадии лексического анализа токенизатор группирует элементы исходной последовательности по заранее известным категориям.
2. Парсер приводит последовательность токенов в структурированный формат.
3. На этапе семантического анализа программа проверяет, что код имеет смысл и соблюдены правила языка. Если всё в порядке, создаётся промежуточное представление.
4. Генератор кода из промежуточного представления порождает код на целевом языке.
Как улучшить? Чтобы улучшить компилятор, между пунктами 3 и 4 нужно добавить этап оптимизации. Нужно исключить излишние конструкции и упростить код с сохранением его смысла. Как только сделаете базовый компилятор, научите программу работать со стандартной библиотекой. И пусть компилятор не только находит ошибки в случае неверного кода, но и выводит содержательные сообщения.
В каких темах вы разберётесь:
- Лексический анализ.
- Синтаксический анализ (парсинг).
- Метод рекурсивного спуска.
- Абстрактное синтаксическое дерево.
- Семантический анализ.
- Оптимизирующий компилятор.
- Кодогенерация.
Для дальнейшего чтения:
- Электронный учебник «Давайте построим компилятор» (англ.).
- Электронное пособие по созданию интерпретаторов (англ.).
- Репозиторий интерпретатора BASIC, написаного на C#.
- 6 книг по компиляторам.
Маленькая операционная система
Алгоритмы и структуры данных операционных систем кажутся абстрактными и бесполезными только в пределах учебной аудитории. Создав операционную систему, вы уверенно освоите на практике всё, что происходит внутри. Особенно приятно запускать собственные программы в операционной системе, которую вы сами создали с чистого листа.
Вот краткий список тем, в которых вы разберётесь:
- Кросс-компиляция
- Загрузчик операционной системы
- Прерывания BIOS
- Режимы работы процессора
- Управление памятью и подкачка страниц
- Планирование, например, алгоритм Round-robin
- Файловые системы (например, FAT)
Для дальнейшего чтения:
- Как работают операционные системы
- Вики-ресурс OSDev.org
- Создание операционной системы с использованием Rust (англ.)
Электронная таблица
Задача создания приложения для электронных таблиц сочетает элементы двух описанных выше проектов: текстового редактора и компилятора.
Текстовый редактор. Количество информации в ячейках может быть различным. При выделении отдельной ячейки представление информации должно учитывать не только ее содержимое, но и ссылки, подсвечивать функции и операторы.
Компилятор. Ячейка электронной таблицы может содержать функции, переменные, ссылки на другие ячейки, константы и операторы. При этом функции могут действовать в отношении вектора или двумерного массива значений. В общем случае каждая ячейка – то же, что маленькая программа. Поэтому нужен компактный компилятор, который будет проводить все необходимые преобразования и проверки, выдавая конечные значения.
Для реализации собственных электронных таблиц вам могут пригодиться эти статьи:
- Рик Лэмерс рассказывает, как соединил электронные таблицы и Python для целей Data Science (англ.).
- Ориентированный ациклический граф.
- Реактивное программирование.
Эмулятор консоли видеоигры
Продолжим идею проекта с двумерными играми. Где мы могли встречать такие игры кроме автоматов? На игровых консолях. Особый фан представляет написание эмулятора консоли, которая умеет запускать игры, придуманные другими разработчиками. Такой проект объединяет в себе создание компилятора и операционной системы.
Эмулятор – виртуальная машина, которая притворяется, что функционирует так же, как аппаратные компоненты игровой консоли. Поэтому он может запускать игры, предназначенные для приставки.
CHIP-8. Хенли рекомендует начать с эмуляции CHIP-8. Это простая виртуальная консоль, для которой легко найти примеры эмуляции. Потом можно перейти к эмуляции реальных консолей, как Dendy или Sega. В них придётся учитывать особенности конкретного оборудования.
PICO-8. Раз уж эмулятор – это виртуальная машина, то необязательно, чтобы консоль существовала в действительности. Полторы тысячи игр написано под 15-долларовый эмулятор PICO-8. Попробуйте создать свободную версию эмулятора и посмотреть, как запустятся виртуальные картриджи. Если у вас есть дети, написание кода игр к таким эмуляторам –возможность заинтересовать их программированием.
Примеры эмуляции для разных языков и консолей:
- Написание эмулятора Chip-8
- Эмулятор Chip-8 на JavaScript
- Как эмулировать Game Boy
- Исходный код PyBoy
Заключение
Пользователи HackerNews, Reddit, Twitter и другие прислали Остину Хенли следующие идеи проектов:
- Система управления базами данных (11 cхем баз данных)
- Трассировщик лучей.
- Растровый графический редактор в духе MS Paint.
- Редактор векторной графики.
- Декодер изображений.
- Веб-приложение онлайн-чата.
- Калькулятор числа пи с заданным числом знаков.
- Утилиты командной строки (например, grep).
- FTP-клиент и сервер.
Идеи других проектов, предложенных или реализованных в статьях Библиотеки программиста, найдутся по тегу Проекты.
Комментарии