Files
dsh 1513111689 synth: measure whether the address-aware metric can shrink a real program
It cannot.  The calculator assembles to 73624 characters in the default flat
metric and 73940 with --synth-chars (identity layout), 316 more.  Three reasons,
now written down in SPEC section 3.7:

* the travel term 2*(hi-lo) is translation invariant, so moving a group of cells
  farther or nearer changes nothing; only a permutation or a spread can, and the
  contiguous identity layout is already the tightest of those;
* the library blocks are expanded at dozens of call sites with different
  addresses, so a single layout line is a guess that the real sites rarely
  match;
* the model still ignores the hop between blocks, and the exact metric tends to
  pick programs with more blocks (six blocks for the adder table against five,
  82 emitted characters against 87 -- five characters, which the other tables
  give back and more).

Cell placement is the lever that works, and it is already spent: the terminal
front end first put its borrowed classifier cells at 52..57 (77164 characters)
and moving them into 20..29 gave 73624, minus 3540.  Five single-cell moves on
the current map were measured too (T and DEPTH to 17, HAVE and CNT to 52, S2
back to 52) and every one is longer: +182, +2900, +92, +134, +3810.  So the map
is a local optimum and the only way down from 73.6k is to drop features.

The experiment left three metric-0 cache entries behind; they were deleted, so
the committed cache still holds only what the flat metric needs.
2026-11-19 14:33:25 +08:00

11 KiB
Raw Permalink Blame History

桌上计算器(RPN)设计与分阶段计划

目标:examples/calc.r8asm —— 一条长驻的纸带,跑了就是一个 RPN 计算器 (3 格栈,S0 是栈顶;有符号数;带行编辑的终端外壳):

> 12 34 + .
0046
> 1 2 + 3 4 * + .
0015
> -5 2 * .
-0010
> 12<退格>3 .
0013
> ,

条件已经齐了:inp 在三份 VM 里都有实现、tape_run/derive 能用 -i 喂输入、例程头部能写 ; in(examples_test 会把那串字符交给 inp)。

1. 命令协议

输入 动作
'0'..'9' 攒进 D 位数字缓冲(遇到终止符一次性 clb_undigits 换成整数,压栈),并原样回显
'*' '+' '-' '/' 弹两个、算、压回;'-' 在栈空时是一元负号(§7)
'.' 另起一行打印栈顶,不动栈(clb_digits_signed + D 个 output),然后补提示符
',' 清栈(内容和深度一起归零)
8(退格) 删掉数字缓冲的最后一位(屏幕上是"空格 + 退格"),攒着的数继续攒(§8)
10(回车) 提交这一行(缓冲里的数压栈),然后打下一行的提示符 > (§8)
其它(空格等) 同回车,但不打提示符 —— 只当数字的终止符
0(EOF) erase 掉循环计数器,主循环结束,纸带自然跑完(收尾打一个换行)

六个命令字符 * + , - . / 正好是 0x2A..0x2F 连续,数字是 0x30..0x39,所以:

t = C - 0x2A                     ; 命令: 0..5  数字: 6..15
数字  <=> C 的 bit4 == 1         ; 一次 ror×4 + biz
命令号 = t                       ; 0=* 1=+ 2=, 3=- 4=. 5=/

2. 内存地图

2. 内存地图

这张表是设计时的草图(stage 1 那会儿的格号)。真的地图在 examples/calc.r8asm 的 .var 段里,比这张表细得多(每个格都有注释:栈、窗口、运算草稿、一次性标志、 带符号数的三格)。两处已经对不上了,照文件走:A/B 现在是栈的 S1/S0, "栈深度标志"是 DEPTH(0..3)。

3. 分阶段计划(每步都能单点验证)

每个驱动都放在 drv/,用 r8forge_derive drv/<名字>.r8asm 0 -i "..." 跑,; out 逐项核对。

  1. drv/calc_lex.r8asm:只做分派。喂 "0 5 9 + - . , *",输出"这是数字(d) / 这是命令(k)"。 验证点:bit4 判断 + t 的取值范围。
  2. drv/calc_num.r8asm:"12"+终止符 → 整数 12(4 位缓冲右移 + clb_undigits)。 验证点:"0" "9" "10" "2047" 四个输入。
  3. drv/calc_disp.r8asm:整数 → > 提示符 + 4 位 ASCII + 换行。
  4. drv/calc_op.r8asm:12 34 + → 46(+ - * / 各一次)。
  5. examples/calc.r8asm:主循环 + EOF 退出 + ; in/; out 头部,进 examples_test。
  6. 有符号数(做完,见 §7):显示换 clb_digits_signed、除法换 clb_divmod_signed、 加一元负号。3 5 - . → -0002、-5 2 * . → -0010、-7 -2 / . → 0003。
  7. RPN 栈(做完,见 §4):3 格栈 + 运算符立刻算 + '.' 真 peek。1 2 + 3 4 * + . → 0015。
  8. 终端外壳(做完,见 §8):回显、退格行编辑、回车提交 + 提示符。见 §8 的三个坑。

4. 栈:3 格,不用指针(做完)

.tp 是汇编期常量、没有间接寻址,所以不要做动态栈指针。实际落地的是 3 个固定格 S0..S2(S0 = 栈顶):

push(新数)  : S2 <- S1 ; S1 <- S0 ; 新数直接 clb_undigits 进 S0
op(a=S1,b=S0): 算进 RES ; 然后 S1 <- S2 ; S2 清掉 ; RES -> S0
'.'         : 只显示 S0(真 peek,"1 2 3 . . ." 连打三次 3)
','         : S0、S1、S2 和 DEPTH 一起清零

挪动的次序不能反(从高往低搬,否则还没搬的源被新值盖掉)。代价:push 2 次 copy (~1k 字符)、一次运算 2 次 copy —— 这也是为什么是 3 格而不是计划里的 16:簿记下来 一格一次 copy(~500 字符),16 格光 push 就要 8k,这条纸带直接冲到 7 万以上。

3 格够算 1 2 + 3 4 * +(最深用到 3);超过了就把最底下那个挤掉,跟老式计算器一样。 深度是要数的(DEPTH:push +1、算一次 -1),一元负号的判据就是 DEPTH == 0。 数深度的减法要挡住下溢(空栈再算一次会绕成全 1,之后的 '-' 就判错了)。

和旧的两寄存器版本(A 累加器 + P 待结算操作数)比,栈买到的是嵌套: 旧版 1 2 + 3 4 * + . 打 0007(第二个运算符把第一个覆盖了),现在打 0015。

5. 步数预算(按 11 位实测的每例代价)

动作 步数
攒一个数(clb_undigits) ≤ 36,481
+/-(clb_add_nc/clb_sub_nc) ~2.5k
*(clb_mul) ≤ 20,300
/(clb_divmod_signed) ≤ 35,202(byte_op_test 全扫的最坏值;无符号版是 31,579)
打印(clb_digits_signed) ≤ 117,606(byte_op_test 2048 个值的最坏值;无符号版 119,431)

一行 12 34 + . 实测 287,589 步(终端外壳之前是 246,142;换栈之前是 280,645)。 回显、退格、提示符每一步都要多走几个格,所以步数大约 +17%。examples_test 的上限是 2000 万步,所以会话控制在十几行以内(或把打印换成"里程表"版本,见下)。

6. 已知的坑(都在库里踩过)

  • 条件体的身体必须回到自己的条件格(净位移 0),否则 .tp 全错位;
  • copy 的缓冲格必须干净(脏了结果是 0);
  • 用 loop/endloop 计数器时,erase 计数器就能提前退出(EOF 就这么退);
  • 库宏每轮都重建 TEN 和轮数计数器 —— 这个终端的常量区(cell 32..43)就是为了把这些 搬到循环外,v2 再让 clb_undigits/clb_digits 支持"外部常量"版本。

7. 有符号数(第 6 步,做完)

约定在 SPEC §5.4、宏在 SPEC §7.10。计算器这边只动三处:

  1. 显示:clb_digits → clb_digits_signed(负数自己打 '-',然后打 |栈顶| 的定宽四位)。

  2. 除法:clb_divmod → clb_divmod_signed(截断、余数随被除数)。加、减、乘不用动, 二补码的模 2^W 运算天然对。

  3. 一元负号:判据是 cell DEPTH(栈深):

    DEPTH == 0(空栈)时字符 45 是一元负号:置 NEG、清 ISCMD(第 3 步据此这一轮 不算);下一个压栈的数在 step 2 里被 clb_neg_ip 取负。DEPTH != 0 时它就是 二元减号。注意 a 弹空了就是 0,0 - 栈顶 正好等于取负 —— 所以栈深只有 1 时 '-' 的两义性没有实际后果。

为什么不用"HAVE == 0 就当作一元负号"(最初的计划就是那样):HAVE 只表示"正在攒 数字",打完运算符之后它也是 0,于是 2 * -5 里的负号会被判成二元减号,结果错。

为什么也不用"上一个字符是运算符"(两寄存器版本就是这么写的):栈机器里 1 2 + - 的 '-' 是二元减法(拿栈顶去减那个"弹空了的 0"),按"上一个是运算符"判会把它 当一元负号、那个负号就被吞掉了。所以判据必须是栈的状态(深度),不是输入的历史。

作废的旧例子:2047 3 / . → 0682 是无符号时代的。有符号之后 2047 的位型是 -1, -1/3 截断成 0,现在打 > 0000;要 341 就写 1023 3 / .。能打的整数范围从 0..2047 变成 -1024..1023。

实测(r8forge_tape_run):3 5 - . → > -0002、-5 2 * . → > -0010、 -7 -2 / . → > 0003、-1024 2 / . → > -0512。纸带 59519 → 62624(两套包装宏

  • 一元负号)→ 64983(再换成 3 格栈,+2.4k)→ 73624(终端外壳,+8.6k,见 §8)。

8. 终端外壳(第 8 步,做完)

目标是把 examples/term.r8asm 那套行编辑接到计算器上:打什么看见什么、能退格、 一行结束有提示符。没有搬 term 的行缓冲:计算器本来就是一格一格吃字符的, 再套一层"先攒一整行、回车才解析"的缓冲既放不下(.tp 是常量地址,回放整行等于 把引擎展开十几遍),也没必要 —— 行编辑在这里就是数字窗口的退格。

实现(都在 examples/calc.r8asm 的主循环里):

  • 回显:读完字符就在数字那一支 / 非数字那一支各打一次 output C(两处,因为 两支的处理顺序不同)。EOF 那支先清 NONDIG,所以 C = 0 不会被回显成 NUL。
  • 退格:判 C - 8 == 0(用 C 的副本 CE,命令分派还要用 C),命中就 打"空格 + 退格"、把窗口整体右移一格、最高位补 '0',然后清 NONDIG —— 这样命令分派那一整段被跳过,攒着的数继续攒。
  • 回车:判 C - 10 == 0(C - 8 再减两次),在回显之后补 > 。
  • '.':先打换行再打结果(以前是同一行前面打 > ),结果后打换行 + 提示符; EOF 收尾再补一个换行。

三个坑(都是先写错再改对的):

  1. 判据格会被别人吃掉。KBS(常量 8)借的是 SC+5,而运算那一步会 %for k 7 { erase SC + k } 整块擦掉 —— 第一版在减法之后才重装常量,于是 12 34 + . 里 + 之后的那一轮拿 0 去减,每个字符都被当成退格。 改成"用之前现装"。KBS 也不能借 R:EOF 那一支每轮都把 R 写成 0/2047。
  2. set_1 只保证最低位是 1,高位残留不管;进位格必须靠 set_1 每轮重置, 不能指望它跨轮是 0。
  3. 提示符的顺序:回车那一支不能直接打 > (那样提示符会跑到上一行末尾), 得等换行回显出去再打;而"回车"这个标志 EH 会被 mul 当草稿格写掉 (EH 借的是 SC+3 = mul 的 S),所以补提示符必须赶在命令分派/运算之前, 放在 NONDIG 块的开头。

代价:64983 → 73624 字符(+8.6k:退格的三次 copy 约 4.4k、判两次减法约 3k、 回显和提示符几百)。这条纸带因此超过了 ROT-8-viz 的旧 INS_SIZE(65536); 现在的虚拟机按纸带长度分配缓冲(16 位版 112802、32 位版 336304 都在那边跑过), 所以只是历史口径作废。想压回去只能砍行编辑:只留回显 + 回车提示符约 +2.5k, 仍然在 65536 之上。

还能不能再压?试过三条路,都不行(数字都是实测):

  • 地址有关口径(r8forge --synth-chars):73940,比 flat 多 316。理由见 SPEC §3.7 —— 那个代价平移不变、库里的块又被几十个调用点共用,一份 layout 猜不准。
  • 单格搬家:把 T 挪到 17、DEPTH 挪到 17、HAVE/CNT 挪到 52、S2 回 52, 五种都更长(+182 / +2900 / +92 / +134 / +3810)。现在这张地图对"单格搬家"是局部最优。
  • 把借来的判据格挤进 20..29(这一步做过,是唯一有效的一次):77164 → 73624, −3.5k。教训是热格必须挨着(clb_sub_nc / clb_nonzero / copy 内部每一位都在走)。