Grid Programs: 2차원, 변수 없는 계산 모델

우리는 프로그램이 선형적인 문장 시퀀스(linear sequences of statements)가 아닌, 정수 그리드(integer grid) 상의 명령어들의 유한한 2차원 배열인 새로운 계산 모델인 Grid Programs를 소개합니다. 세 가지 속성이 이 모델을 기존의 프레임워크와 근본적으로 구분합니다: (i) 프로그램은 명령어 포인터(instruction pointer)가 네 가지 기본 방향(cardinal directions)으로 이동하는 평면 구조(planar structures)입니다; (ii) 구문 제약(syntax constraints)이 없으므로, 그리드 셀에 명령어를 할당하는 모든 방식이 유효한 프로그램이 됩니다; (iii) 이 모델은 이름이 지정된 변수(named variables)나 명시적인 메모리 주소(explicit memory addresses)를 사용하지 않습니다. 프로그램 상태는 데이터 스택(data stack), 주소 스택(address stack), 그리고 세 개의 이름이 지정된 포인터(named pointers)를 통해 접근되는 원형 이중 연결 리스트(circularly doubly linked list)를 통해 유지됩니다. 제어 흐름(Control flow)은 공간적으로 달성되며, 분기(branching)는 명령어 포인터의 수직 회전(perpendicular turns)으로 인코딩됩니다. 주소 스택은 (셀 행, 셀 열, 방향)의 삼중항(triplets)을 저장하여, 분기(branches), 루프(loops), 함수 호출(function calls) 이후에 위치와 방향을 모두 정밀하게 복구할 수 있게 합니다. 우리는 공식적인 운영 의미론(formal operational semantics)을 제공하고, 산술(arithmetic), 제어 흐름(control flow), 연결 리스트 조작(linked-list manipulation)을 다루는 대표적인 명령어 세트를 제시하며, 절댓값 함수, 팩토리얼 계산, 선형 탐색 알고리즘(linear-search algorithm), 문자열 역순 프로그램, while-loop 합계 계산을 포함한 여러 상세한 예제를 살펴봅니다. 우리는 임의의 레지스터 머신(register machine)을 시뮬레이션함으로써 Grid Programs가 튜링 완전(Turing-complete)함을 입증하며, Befunge 및 Funge-98과 같은 기존의 2차원 언어, Forth 및 PostScript와 같은 스택 기반 언어(stack-based languages), 그리고 데이터 흐름(dataflow) 및 공간 계산(spatial computation) 모델과의 관계를 논의합니다. Grid Programs는 시각적 프로그래밍 환경(visual programming environments), 셀룰러 오토마타(cellular-automaton)에서 영감을 받은 하드웨어, 난독화 저항성 코드(obfuscation-resistant code) 분야에서의 잠재적 응용 가능성과 함께, 계산의 설계 공간을 탐구하기 위한 새로운 관점을 제공합니다.