Copyless 流式字符串转导器

Copyless 规则把每段已经积累的文本当成线性资源：一轮中可以移动、连接或丢弃，但不能同时送往两个去处。新读到的字符是常量，可以分别追加到多个寄存器；被禁止的是复制整个历史片段。

因此寄存器内容可以任意长，模型并非常数内存的实际流算法。它保存的是固定数量的无界字符串，只是这些字符串的“血统”不会分叉。固定寄存器数和每步有限常量共同推出输出长度对输入长度的线性上界。

该限制是可静态检查的：扫描每个更新表，计数右式中的变量出现次数即可。无需分析输入或求不动点，因而适合作为语言设计和验证系统中的语法纪律。

更细地看，每轮更新都诱导一张“旧寄存器到新寄存器”的变量流图。Copyless 要求每个旧变量的出度至多为一；一个新变量仍可接收若干不同旧变量并按指定次序连接。随着输入推进，历史片段可以汇合，却不会分叉成越来越多副本，这正是线性长度界背后的机制，而非单纯的实现建议。

反转可由一个寄存器完成。令 $X$ 初值为 $\epsilon$，每读当前字符 $a$ 同步更新

终态输出 $X$。输入 cab 时，轨迹为

最终正是 cab 的反转。旧 $X$ 每步只出现一次，所以完全 copyless；在左侧追加当前常量并不算“复制寄存器”。

模型甚至能输出两份输入：用 $X:=Xa$、$Y:=Ya$ 同时把当前字符常量写入两个寄存器，终态输出 $XY$。旧 $X,Y$ 各用一次，故仍合法。由此可见 copyless 不表示每个输入位置只能贡献一个输出字符；固定寄存器数允许固定倍数复制。

相反，单寄存器更新 $X:=XXa$ 非法，因为旧 $X$ 出现两次，并产生 $2^n-1$ 长输出。函数 $w\mapsto w^{|w|}$ 也不能靠“再加几个寄存器”实现：所需副本数随输入增长，而机器的寄存器数固定。若把终态表达式写作 $XX$，同样在最后一步违反 copyless。

需要注意，copyless 是逐条转移的联合条件，不是分别检查每个赋值。例如 $X:=X$ 与 $Y:=X$ 单看各自都只写一次 $X$，合在同一轮却把旧 $X$ 分到两个新寄存器，仍然违法。审计更新表时必须跨所有右式累计变量次数。

Copyless SST 单向读输入，却可通过“向寄存器左端或右端追加”模拟双向读头最终会以何种顺序输出各片段。反过来，确定 2DFT 可用 crossing sequence 追踪每个输入边界的有限穿越方式，从而模拟寄存器片段的组合。两向构造给出 regular function 等价定理。

该类对函数复合封闭，但直接把一台 SST 的寄存器表达式代入另一台，可能迅速增大控制状态和更新式；保持 copyless 需要结构化地追踪变量流，而非文本式反复展开。表达能力闭包不等于构造没有指数代价。

在流式数据清洗、字段重排和程序验证中，copyless 纪律提供两项可用保证：输出大小线性受控，变量来源可追踪。若需求确实包含指数展开，应改用一般 SST 并显式评估输出成本，而不是悄悄放宽一条赋值。