youmuliu/stgsharp

Fork 0

Files

T

Youmu Liu 0356f5aff8 mat task adapts L4

2026-06-09 18:13:36 +08:00

12 KiB

Raw Permalink Blame History

NGRA 作为计算语言：设计讨论笔记（草案）

本文是一次理论讨论的结论沉淀，不是规范。主业仍是「通用序列模式分析器」（用于解释/编译器前端、日志分析）。「把 NGRA 扩展成通用语言」是副产品，优先级靠后。但其中若干结论会反过来影响主业的语法设计，已在文末标出。

0. 一句话总览

NGRA 在理论上可以是图灵完备的通用语言，但它的最优生态位不是通用语言，而是可嵌入宿主的、面向任意可分类线性序列的改写/分析处理器（awk 之于文本，NGRA 之于任意序列）。作为语言时，它是胶水语言 / 教学语言，不适合做大型通用系统。

1. 计算能力：图灵完备，但靠「写回反馈回路」而非随机访问

「正则 + 序列改写」这条路在理论上图灵完备（参照 Markov 算法、Thue、sed、XSLT）。
决定生死的不是「能不能随机读写」，而是有没有「写回 → 重新匹配」的反馈回路：
- 单向「输入序列 → 输出序列」= 有界转换器（transducer），不图灵完备。对应 scanning。
- 存在「工作序列可读可写、写完再进入下一轮匹配直到不动点」= Markov/Post 改写系统，图灵完备。对应 stepping + Feed/Step/Flush。
「不能随机读写」不影响图灵完备性（图灵机本身只有单向带），只影响渐进复杂度与人体工程学：模拟随机访问/堆是 O(n) 扫描重写，写算法反人类。
结论：NGRA 的弱点不是「能不能算」，而是「算法类、随机访问类负载写起来难受」。

2. 计算模型：reduction（收敛），不是 evaluation（求值）

数学/逻辑是标准库问题，不是语言核心问题：给基本型提供 Add 等方法 + 算符重载即可。
算符重载 = 一条改写规则；return = 把匹配到的 redex 就地替换成结果。
- 局部运算（a+b、向量相加）写起来很干净：消费 N 个元素 → 吐回 1 个元素。
别扭之处不在单步，而在嵌套与组合：
1. 中间结果是「显式存在于序列里的真实元素」，会污染序列，需打 tag/island 隔离；
2. 求值顺序要靠规则匹配优先级 + 边界自己控制（等于手写优先级/结合性）；
3. 没有「可反复引用的变量」——值在序列里只有一份，用一次即被消耗，复用需显式拷贝（线性/一次性，类似 linear logic）。
一句话：NGRA 的「算」是 reduce to normal form，不是 evaluate。
- 能自然表达成「局部模式 → 局部替换 → 整体收敛」的计算，写起来甚至比命令式干净。
- 依赖「可变变量多次读写 / 深层嵌套 / 随机寻址结构」的计算会持续别扭，且是结构性的。

3. 双空间模型（影响主业）

NGRA 有两个语义空间，必须分开：

空间	单元	受谁影响	用途
类型/布局空间	恒为字节	与 `#input` 无关	类型声明、字段偏移、size
算术/解析空间	由 `#input` 决定（string/byte/bit/event…）	`#input`	提取函数、表达式计算

<_:12> 中的 12 永远是字节。
#input 只管算术/解析空间可用哪些内联函数，不影响类型定义。
代价：位域（sub-byte 字段）不在类型声明层，只能在解析层用 #input bit + Bit(n) 处理。

4. 类型系统：定长闭包 + 被动布局

4.1 类型声明 = `reinterpret_cast`，不是匹配

类型声明不匹配/不判定任何东西，它只贡献两样：size(T) 和「字段 → 偏移」表。
「读一段字节并视作 T」永远成立（零成本重解释），成员访问 = base + 常量偏移 读一个寄存器基本型。
推论：裸 union 在类型空间没有「消歧」问题——读哪个视图由访问方决定，无 tag、纯偏移（与 C union 同）。

4.2 struct = 乘积类型（天作之合）

顺序拼接 <a:int><b:int> 在序列上就是连接 = 乘积，本身就是 struct。
优势：字节布局显式无歧义（默认 packed，无隐式 padding）；ABI padding 需显式写 <_:N>；字节序需显式声明。
bitfield：在类型空间表达不了（见 §3），归解析层。

4.3 union / overlay = 和类型（`|`）

类型空间的 |：作用域 = 当前 () 层，向前向后直到 | 或 (/)；中间连续字段按 struct 排列。
规则要点：
- | 是 flat n-ary sum（可交换、可结合，扁平候选集）；
- 禁止空分支（尾随 | 静默变可选是隐形 bug）；
- 分支不等长时：size = max(分支)，开头对齐（同 C union），短分支尾部隐含 padding；
- 读 union 时游标恒前进 max 字节（由类型 size 决定，不由匹配到的分支决定）——这是静态偏移得以保住的关键。
赠品：overlay / FieldOffset = |（同基址重叠）+ <_:N>（精确偏移），不需要负游标或绝对偏移锚点：

define Overlay =
      <x:int32> <y:int32>      # x@0, y@4
    | <_:4> <z:float32>;       # z@4，与 y 同址重叠

「裸 union 读消歧」在类型空间是伪问题：| 默认产出多视图和类型（multi-view sum），所有成立视图同时有效；需要「排他单一分支」时用判别字段（tagged），判定逻辑属于使用方/规则空间，不进类型声明。

4.4 `<_:N>` 与 `int[0]`（一对对偶）

<_:N>：匿名、占 N 字节、不产字段的纯偏移推进（padding）。只前进，保持游标单调。
- 单位：字节（见 §3）；读 = skip 不校验；写 = 填零；参与 span/diagnostics 但不进 AST（复用 <r"..."> 哲学）。
int[0]：具名、占 0 字节、产一个零元素字段的偏移锚点。
- 其「值」= 长度 0 的空序列视图（不是 null、不是 0，避免与缺失字段 / 具体 0 值撞语义）；
- 与 int[n] 在 n=0 处语义连续；越界访问（buf[0]）= 诊断错误（不学 C 的 UB）。

4.5 定长闭包是地基（影响主业）

类型必须声明为确定性长度：允许 int[0]，禁止 int[]。
int[] 的毒性是传染：一个变长字段令外层 size 与后续偏移全部变运行期值，沿嵌套向外塌方。
禁 int[] = 斩断传染链，保住整棵类型树的定长闭包。
「全定长」是 §3、§4 一切结论（静态偏移、reinterpret、overlay 的 max 常量）的公共前提/地基，不是「模仿 C99」。
变长被驱逐到规则/解析空间（<byte>{@count=$len} 这类带求值的顺序读取），绝不回流进 define。两个空间之间这道墙就是靠「禁 int[]」砌起来的。

5. 变长数据 / 字符串：靠 slice（fat pointer）

「定长不兼容字符串」不是缺陷，是缺了 C 早有的间接层：char* + len = fat pointer / slice。
解法不是放松定长闭包，而是新增一个定长的序列引用类型：

define Slice = <ptr: offset> <len: int32>;   # 自身定长！只存「从哪开始、多长」

slice 把变长内容留在纸带 / 规则空间，类型空间只持有定长把手 → 地基不动，字符串进来。
slice 就是正则捕获组的推广（捕获组 = 输入串上的 (start,len)，slice = 纸带上的 (ptr,len)）。
ptr 就是纸带指针本身（现成的），不引入 arena / trust domain（见 §7）。

6. 函数与调用约定（通用语言化部分，可挂起）

工作在纸带上的语言不能用传统 return，模型如下：

默认 = 纯 reducer：调用点 p 记下，函数跑完游标复位回 p，结果落在终止时游标位置；调用区间 <f args> 被结果替换（消费 redex，不堆垃圾）。
不复位模式 = consumer / 流推进：游标停在 p'，返回锚点 = 终止时游标位置（复位与否只决定该游标在哪）。
insert vs overwrite 是正交轴：
- overwrite 不改长度，O(1)，不漂移偏移（对静态布局友好）；
- insert 撑开纸带，O(尾部长度)，且令后续纸带绝对位置漂移；
- reduction 真正要的是「替换 redex」（insert/overwrite 的统一）。
静态偏移在 insert 下存活的前提：偏移常量只在类型对象内部成立；纸带绝对位置是易失的、不可长期持有（只能持有「相对游标」或「对象基址内偏移」）。
双纸带：公共纸带 + 函数私有纸带（随函数销毁）= 双带图灵机 = 天然栈帧，配复位 → 干净递归。
emit = 序列语言版 return：把私有纸带上的值显式拷贝到公共纸带的返回锚点；可多次调用 → 能返回整个序列（比传统 return 强）；定长返回类型下 emit 累计须正好凑满 size(T)。
传参双通道：
- 标量 / 捕获 $name / @count 走上下文通道（VM 绑定，不占纸带寻址）；
- 序列 / 大对象 copy 到私有纸带 0x00 起，函数读完游标前移。
悬垂引用对策：slice 只能指向公共纸带，私有纸带数据要外传必须 emit 拷贝。 → 「匹配字符串后要序列拷贝」是显式、必然、无悬垂的操作（诚实，且与「越界判错」的安全取向一致）。

7. 内存模型与自我定位

不引入 arena / trust domain：这是唯一不背离「源自正则」的选择。
- 正则捕获组从无「所有权 / 回收」概念；arena 会引入正则世界里不存在的问题。
由此，NGRA 只有两种内存：纸带（线性、易失） 与 类型对象（定长、内联）。
缺的是第三种：生命周期独立于控制流的、可长期持有的动态堆对象。
- 准确说法：NGRA 没有「独立生命周期堆对象」这个概念本身（而非「有但不安全」）。
- 这让它结构上是流处理器，而非系统构建器 → 注定是胶水 / 教学语言。
生态位（体面且有独占性，与 awk/jq/sed/XSLT 同列，但更泛化）：

可嵌入宿主语言的、面向任意可分类线性序列的改写/分析处理器生成框架。
「教学语言」是真资产：NGRA 把纸带、栈帧、fat pointer、求值收敛、内存布局全暴露成第一类语法—— 「不适合生产」与「适合教学」是同一个原因：没有隐藏的魔法。

8. 对主业（序列分析器）的直接影响 —— 现在就要认的三条

双空间分离（§3）：定义 .ngra 类型语法前，先认「类型空间字节寻址 / 算术空间随 #input」这条线。
定长闭包 + 变长隔离进规则空间（§4.5）：直接决定 define 与规则体的语法边界，是主业地基。
{...} 记号超载问题：当前 {...} 同时承担
- 属性谓词 <Token>{value="if"}、
- 泛型参数 Array{T:int}、
- 计数约束 <int>{?=8}。三者挤在同一对花括号里，词法上几乎无法区分。建议早定方案，例如：
- 计数沿用 @count：<int>{@count=8}；
- 泛型改用尖/方括号：Array<T:int> 或 Array[T:int]。

其余偏计算的（§6 的 emit、双纸带、reduction、算符重载、数学库）属于语言化，可等主业稳定后再展开。

9. 主业 vs 语言化：清单

属于主业、现在就该落地：

token/序列提取（Regex/Byte/Bit/Char + Regex(expr, group) 消费但不产出）
<...> 规则调用、<r"..."> 胶水、捕获 (?<name>:...) / $name
岛屿分层压缩 + scanning/stepping 双模式
定长类型声明（struct / overlay-union / <_:N> / int[0]）——二进制日志、协议解析刚需
slice 作为「匹配结果的引用」——捕获组的自然形态

属于语言化、可挂起：

函数 / emit / 双纸带调用约定 / reduction 求值
算符重载、数学标准库、写回反馈回路

12 KiB Raw Permalink Blame History Unescape Escape