Керуйте складським краном за допомогою коду й переставляйте кольорові ящики за ліміту команд, настільки жорсткого, що без рекурсії не обійтися.
Складіть програму з команд крана (рух ліворуч і праворуч, захоплення, скидання та умови за кольором), щоб переставити ящики з контейнерів у цільовий стос. Ліміт команд навмисно жорсткий, тож ви спиратиметеся на команду 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: мова крана із семи команд, десять рівнів, ліміти яких роблять рекурсію необхідною, а не факультативною, спільний щоденний рівень і режим тренування, що видає інші рівні.