The IsalProgram Programming Language
This work presents a new programming language with theoretical properties that may benefit neural program synthesis, but it is an incremental contribution without empirical validation.
The paper introduces IsalProgram, a novel assembly-like programming language that is regular, has no memory addresses, and uses a circular doubly linked list as its sole data structure. It proves the language's regularity and discusses its potential for neural program synthesis and metric-based exploration.
We introduce IsalProgram (Instruction Set and Language for Programming), a novel assembly-like programming language with three distinctive theoretical properties: (1) it is a regular language in the sense of formal language theory, meaning its programs are accepted by a finite automaton; (2) every finite string over the instruction alphabet is a syntactically valid program; and (3) it makes no explicit use of memory addresses or variable names, absolute or relative. Programs are finite sequences of tokens drawn from a fixed instruction set, and are executed on a virtual machine whose sole data structure is a circular doubly linked list (CDLL) navigated by three data pointers, with control flow governed by two code pointers. We give a complete formal definition of the language and its virtual machine, prove its regularity, and demonstrate its expressive power. We further discuss IsalProgram's potential advantages as a target language for neural program synthesis, the amenability of its program space to metric-based exploration via the Levenshtein edit distance, and directions for analyzing computability and complexity within this framework.