IsalProgram 프로그래밍 언어

우리는 세 가지 독특한 이론적 특성을 가진 새로운 어셈블리 스타일 (assembly-like) 프로그래밍 언어인 IsalProgram (Instruction Set and Language for Programming)을 소개합니다: (1) 형식 언어 이론 (formal language theory)의 관점에서 정규 언어 (regular language)이며, 이는 프로그램이 유한 오토마타 (finite automaton)에 의해 수용됨을 의미합니다; (2) 명령어 알파벳 (instruction alphabet) 상의 모든 유한 문자열은 구문론적으로 유효한 (syntactically valid) 프로그램입니다; (3) 절대적 또는 상대적인 메모리 주소 (memory addresses)나 변수 이름 (variable names)을 명시적으로 사용하지 않습니다. 프로그램은 고정된 명령어 세트에서 추출된 토큰들의 유한한 시퀀스이며, 세 개의 데이터 포인터 (data pointers)로 탐색되는 원형 이중 연결 리스트 (circular doubly linked list, CDLL)를 유일한 데이터 구조로 사용하는 가상 머신 (virtual machine)에서 실행됩니다. 제어 흐름 (control flow)은 두 개의 코드 포인터 (code pointers)에 의해 관리됩니다. 우리는 이 언어와 가상 머신에 대한 완전한 형식적 정의 (formal definition)를 제공하고, 그 정규성 (regularity)을 증명하며, 표현력 (expressive power)을 입증합니다. 나아가 우리는 신경망 프로그램 합성 (neural program synthesis)을 위한 타겟 언어로서 IsalProgram의 잠재적 장점, 레벤슈타인 편집 거리 (Levenshtein edit distance)를 통한 메트릭 기반 탐색 (metric-based exploration)에 대한 프로그램 공간의 적합성, 그리고 이 프레임워크 내에서 계산 가능성 (computability) 및 복잡도 (complexity)를 분석하기 위한 방향에 대해 논의합니다.