一种无需变量名的汇编语言，程序可被有限自动机识别
The IsalProgram Programming Language
- 用固定指令集生成程序，语法无限制，所有字符串都合法
- 虚拟机仅用循环双向链表和三个数据指针，通过双代码指针控制流程
- 适合神经程序合成，支持基于编辑距离的程序空间探索
我们提出IsalProgram（指令集与编程语言），一种新型类汇编编程语言，具备三个理论特性：（1）在形式语言理论中为正则语言，其程序可由有限自动机接受；（2）指令字母表上的任意有限字符串均为语法合法程序；（3）不显式使用内存地址或变量名（绝对或相对）。程序是来自固定指令集的有限标记序列，运行于仅以循环双向链表（CDLL）作为数据结构的虚拟机上，由三个数据指针导航，控制流由两个代码指针管理。我们给出语言及其虚拟机的完整形式定义，证明其正则性，并展示其表达能力。进一步讨论了其作为神经程序合成目标语言的潜力，其程序空间可通过莱文斯坦编辑距离进行度量探索，以及在此框架内分析可计算性与复杂性的方向。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。