Управляйте складским краном с помощью кода и переставляйте цветные ящики при лимите команд, настолько жёстком, что без рекурсии не обойтись.
Составьте программу из команд крана (движение влево и вправо, захват, сброс и условия по цвету), чтобы переставить ящики из контейнеров в целевую стопку. Лимит команд намеренно жёсткий, поэтому вы будете опираться на команду Call, которая перезапускает всю программу с начала; невыполненное условие становится базовым случаем, который останавливает рекурсию. В игре десять уровней, созданных вручную, — от одного красного ящика до башни из шести ящиков, и восемь из них невозможно решить без Call.
Башня из трёх: три красных ящика стоят в контейнере 1 и должны оказаться в контейнере 2, а использовать можно только шесть команд. Если расписать всё подряд, каждому ящику нужны Grab, Right, Drop и Left — одиннадцать команд на три ящика, даже если убрать последний Left. Шести не хватит.
Поэтому напишите одну ходку и дайте ей повторяться: Grab, If-held red, Right, Drop, Left, Call. Это шесть команд. Кран захватывает ящик, проверяет, что держит красный, переносит его, ставит, возвращается и снова вызывает всю программу. На четвёртом вызове контейнер 1 пуст, Grab ничего не поднимает, проверка If-held red не проходит, и программа останавливается. Эта невыполненная проверка и есть базовый случай.
Замените If-held red на If-held blue, и те же шесть команд пройдут уровень с четырьмя ящиками и башню из шести, потому что процедура никогда не считает ящики: она работает, пока они не кончатся. В этом и смысл рекурсии: программа описывает один шаг и правило остановки, а сколько раз она выполнится, решают входные данные.
Claw Compiler учит рекурсии с помощью крана, переставляющего ящики, и строгого лимита ходов, делая сложную идею наглядной.
Команды крана — двигаться влево и вправо, хватать, опускать и условия по цвету — это минимальный язык ассемблера с приделанным физическим телом.
Обучение программированию через маленького робота в маленьком мире восходит к роботу Карелу — языку для начинающих, который Ричард Паттис представил в книге 1981 года и использовал в своих курсах в Стэнфорде. Игры подхватили идею: Lightbot учит циклам и процедурам, заставляя программировать робота в лабиринте, а ближайший предок игры Claw Compiler — Cargo-Bot, головоломка 2012 года для iPad, в которой вы учите робота переставлять ящики. Студия Two Lives Left сделала её вместе с Руем Вианой на основе его прототипа в своём приложении для программирования на iPad Codea и представила как первую игру, полностью запрограммированную на iPad.
Задача — переставить ящики из контейнеров в целевую стопку — это сортировка, выполняемая машиной, которая может держать ровно одну вещь за раз. Ограничение одним захватом — урок само по себе. Это то же ограничение, что налагает регистр, и именно поэтому настоящей сортировке нужно место, куда что-то положить, — обнаружить, что вам нужен запасной контейнер, значит открыть идею временного хранения.
Поскольку Call всегда стоит последней командой, каждая программа здесь хвостово-рекурсивна: вызов самой себя — последнее, что она делает. Многие реализации языков превращают хвостовой вызов в простой переход к началу, поэтому одну и ту же программу можно прочитать и как рекурсию, и как цикл. Понять, что это одна идея, — значит во многом понять рекурсию.
Claw Compiler — оригинальная бесплатная браузерная игра, созданная для PlayPendium: язык крана из семи команд, десять уровней, лимиты которых делают рекурсию необходимой, а не факультативной, общий ежедневный уровень и режим тренировки, в котором выпадают остальные.