코드로 창고 크레인을 움직여, 재귀가 꼭 필요할 만큼 빠듯한 명령 수 제한 안에서 색깔 상자를 다시 쌓으세요.
크레인 명령(왼쪽·오른쪽 이동, 잡기, 놓기, 색 조건)으로 프로그램을 만들어 칸에 담긴 상자들을 목표 더미로 재배열합니다. 명령 수 제한이 일부러 빠듯하게 되어 있으므로, 프로그램 전체를 처음부터 다시 실행하는 Call 명령에 기대게 됩니다. 실패한 조건은 재귀를 멈추는 기본 사례가 됩니다. 직접 설계한 레벨은 10개로, 빨간 상자 하나부터 상자 여섯 개짜리 탑까지 있으며, 그중 8개는 Call 없이는 풀 수 없습니다.
Tower of Three(세 상자 탑): 빨간 상자 세 개가 1번 칸에 있고 이를 2번 칸으로 옮겨야 하는데, 쓸 수 있는 명령은 여섯 개뿐입니다. 하나하나 풀어 쓰면 상자마다 Grab, Right, Drop, Left가 필요하므로, 마지막 Left를 빼더라도 상자 세 개에 명령 열한 개가 듭니다. 여섯 개로는 부족합니다.
그러니 한 번 오가는 동작만 쓰고 그것을 반복하게 합니다: Grab, If-held 빨강, Right, Drop, Left, Call. 명령 여섯 개입니다. 크레인은 상자를 잡고, 빨간색을 들고 있는지 확인하고, 옮겨서 내려놓고, 돌아와서 프로그램 전체를 다시 호출합니다. 네 번째 호출에서는 1번 칸이 비어 있으므로 Grab은 아무것도 잡지 못하고, If-held 빨강 검사가 실패해 프로그램이 멈춥니다. 이 실패하는 검사가 바로 기본 사례입니다.
If-held 빨강을 If-held 파랑으로 바꾸면 같은 명령 여섯 개로 상자 네 개짜리 레벨과 여섯 개짜리 탑도 풀립니다. 이 루틴은 상자를 세지 않고, 하나도 남지 않을 때까지 계속할 뿐이기 때문입니다. 이것이 재귀의 핵심입니다. 프로그램은 한 단계와 멈추는 규칙을 기술하고, 몇 번 실행될지는 입력이 정합니다.
Claw Compiler는 상자 쌓기 크레인과 엄격한 이동 예산을 통해 재귀를 가르치며 어려운 아이디어를 구체화합니다.
왼쪽과 오른쪽 이동, 잡기, 놓기, 그리고 색에 대한 조건으로 이루어진 크레인 명령은 물리적인 몸이 붙은 최소한의 어셈블리어다.
작은 세계 속 작은 로봇으로 프로그래밍을 가르치는 방식은 카렐 더 로봇으로 거슬러 올라간다. 리처드 패티스가 1981년 책에서 소개하고 스탠퍼드 대학교 강의에서 사용한 초보자용 언어다. 게임들도 이 발상을 이어받았다. Lightbot은 미로 속 로봇을 프로그래밍하게 하여 반복문과 프로시저를 가르치며, Claw Compiler의 가장 가까운 조상은 로봇에게 상자 옮기는 법을 가르치는 2012년 아이패드 퍼즐 Cargo-Bot이다. Two Lives Left는 Rui Viana가 자사의 아이패드 코딩 앱 Codea로 만든 프로토타입을 바탕으로 그와 함께 이 게임을 만들었고, 아이패드에서 완전히 프로그래밍된 최초의 게임이라고 홍보했다.
상자 칸들을 목표 더미로 재배열하는 과제는 한 번에 정확히 하나만 들 수 있는 기계가 하는 정렬이다. 집게가 하나뿐이라는 한계는 그 자체로 하나의 교훈이다. 레지스터가 부과하는 것과 같은 제약이며, 실제 정렬에 물건을 내려놓을 곳이 필요한 이유다. 여분의 칸이 필요하다는 것을 발견하는 것은 임시 저장이라는 개념을 발견하는 것이다.
Call은 항상 마지막 명령이므로 여기서 만드는 모든 프로그램은 꼬리 재귀다. 자기 호출이 프로그램이 마지막으로 하는 일이라는 뜻이다. 많은 언어 구현은 꼬리 호출을 맨 위로 되돌아가는 단순한 점프로 바꾸는데, 그래서 같은 프로그램을 재귀로도 반복문으로도 읽을 수 있다. 둘이 같은 개념이라는 것을 알아보는 것이 재귀를 이해하는 일의 큰 부분이다.
Claw Compiler는 PlayPendium을 위해 만든 독창적인 무료 브라우저 게임입니다. 명령 일곱 개로 이루어진 크레인 언어, 제한 때문에 재귀가 선택이 아닌 필수가 되는 10개의 레벨, 모두가 함께 푸는 일일 레벨, 그리고 나머지 레벨을 내주는 연습 모드를 갖추고 있습니다.