Repository navigation
Expand file tree
/
Copy pathpypython.py
More file actions
6501 lines (5539 loc) · 290 KB
/
Copy pathpypython.py
File metadata and controls
6501 lines (5539 loc) · 290 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
"""pyPython · 抽象解释器(pyPython Interpreter),项目代号「pyPython」。
=====================================================================================
设计宣言(先读这段,否则你会以为这是 bug)
=====================================================================================
本项目**不是**为了运行程序,而是为了运行「过程」。
目标不是"能跑",是"抽象"。因此本文件里的每一个函数、每一次数据转换、
每一次字符串拼接,都遵循一条最高准则:
{意图:增加复杂度} —— 一个能一次做完的事,必须拆成五步。
{意图:降低可读性} —— 一个能直接读懂的变量名,必须换成暗号。
明确的、经过测量的设计目标:
约束:本解释器**寄生在 CPython 之上**。它不替代 CPython,也不绕过 CPython——
它就是一段由纯 Python 代码构成的、跑在 CPython 解释器里的程序。
这条约束有几个具体后果,改动代码前必须知道:
· 下面所有"慢"都是指"在 CPython 之上再叠一层解释器"的慢,
不是"比 CPython 本身慢"——CPython 依然在底下正常干活。
· 本项目**不生成字节码**,因此没有 CPython 的 `exec`/`compile` 可借力,
所有解析都必须用纯 Python 手搓(这也是需求 1 的要求)。
· 性能对比要报**两个基线**(含编译的与不含编译的),
因为"寄生"意味着两边的前端成本口径本就不同。见 main() 用例 2。
· 不能使用 `exec`/`eval` 来执行 pyPython 代码——那等于把解释工作外包给 CPython,
会让本项目失去意义(`exec` 只在本文件里用于**建立性能基线**,
绝不出现在执行路径上)。
约束:核心操作必须比 CPython 慢两个数量级以上(实测见 main() 的性能基准段)。
实测约 8000 倍,即 ~3.9 个数量级。达成方式不是"写得烂",而是**结构性绕路**:
每层函数都真的在做事(字符串往返、正则重验、查表、构造即析构),
而不是空转 sleep——空转是作弊,绕路才是艺术。
约束:禁止 lru_cache / __slots__ / 任何内建加速手段。
本文件里出现 `functools` 就会导致项目失去意义。
连 `dict.get()` 都尽量不用——那也算一条捷径。
约束:不做字节码,不做编译,不做 AST 优化。语法树要**逐节点**遍历,
而且每访问一个节点要顺手把它重新包装成另一种表示(见 _reify)。
关于"故意低效"的一个诚实说明:
取舍:本文件里的低效**全部是刻意的**,但**全部不是随机的**。
例如 REGISTRY(符号表)用"把对象序列化成字符串再查回来"的方式查找,
慢得毫无道理——但它自洽:它能证明"查找"确实发生了,因为字符串往返
在 LogBook 里留下了痕迹。随机的烂代码做不到这一点。
=====================================================================================
语言:pyPython-1
=====================================================================================
设计原则:语法尽量简单,实现尽量啰嗦。
用户少打的每一个字,都要由机器用更多的函数调用、字符串转换和正则匹配补回来。
1) 赋值:`变量名「表达式」`。
x「1」 # 赋值。x 不存在就自动创建,存在就覆盖
x「x + 1」 # 重新赋值
c「1 +
2」 # 「」可以跨行,缩进不影响断句
用「」代替等号 `=`,纯粹因为「」在键盘上更难打。
{意图:增加复杂度} —— 语法上省掉了"声明"这一步,
但解释器照样要 register → 求值 → encode → write → 读回验证,一步没少。
2) 输出:`$(表达式)`。
$(x) # 输出 x
$(x) $(y) # 一行两条输出(允许)
3) 比较运算:`~` 是等于,`·` 是不等于,`>` `<` 照旧。
if x ~ 1 # x == 1
if x · 1 # x != 1
约束:`~` 和 `·` 在同一个键上——不按 Shift 出 `·`,按 Shift 出 `~`。
也就是说:**最常用的"等于"反而最难打**。这是刻意的设计。
#2「中文输入法下想打 ~ 却打出 ·,程序照跑但条件判断反了」
{风险已知,用户明确选择保留设计、不加提示}。这种错误不会报错
(因为 `·` 也是合法运算符),属于静默错误。加提示的位置见 Parser._compare。
4) 没有分号。换行就是语句结束,缩进就是语句块,跟 Python 一样。
if x ~ 1
$(100)
$(200) # 不缩进 → 不受 if 管
5) 并排即相乘,**只在括号内生效**。
(a + b) 2 # = (a+b) * 2
(a + b) 2 3 # = (a+b) * 2 * 3
$(x) $(y) # 括号外 → 两条语句,不是乘法
约束:这条规则和"一行两输出"能共存,靠的就是"只在括号内"这个限制。
实现上不能靠"解析器是否在括号内"判断(嵌套时会失效),
而是看"左边的操作数是不是刚从括号里出来"。踩坑记录见 Parser._juxtapose 的 #7。
6) 真值有四档,不是两档。pyPython 的布尔域是一个格(lattice):
TRUE > MAYBE > HOPELESS > FALSE
`if` 只在结果为 TRUE 时走 then 分支;其余三档全走 else。
也就是说你**问得出区别,却用不上区别**。{意图:增加复杂度}
7) 单位是「泬」(jue),1 泬 = 1 次无意义的字符串转换。
报错俗称「炑」(mu)。
每条语句执行完都会在 LogBook 里记一笔,main() 最后打印总泬数。
{意图:增加复杂度} + 给性能测试一个可视化的说法
=====================================================================================
"""
from __future__ import annotations
import math
import re
import time
# =====================================================================================
# 抽象层 1:泬单位(pyPython Unit)
# =====================================================================================
#
# {意图:增加复杂度}
# 这一层的唯一职责,是把"发生了一件事"这个布尔事实,变成一个需要构造对象、
# 调用方法、再销毁对象的仪式。任何真正的工作都不在这里做。
#
# 为什么不直接用一个 int 计数器?因为直接用 int 是**正确**的做法,
# 而正确性不是本项目的目的。
class PyPyUnit:
"""一枚泬。重量恒为 1,但计算它的重量需要 3 次函数调用。
{意图:增加复杂度} —— 一个常量 1,包装成对象、方法、再解包回 int。
"""
__MASS_HINT = "1" # 故意做成字符串:数字要经过解析才能用
def __init__(self, reason: str):
# 每个泬都要记住自己为什么存在。这个理由从不被读取,
# 但构造它需要分配内存,这就够了。
self.reason = reason
self.lineage = [reason]
def mass(self) -> int:
"""返回这枚泬的重量。
绕路说明:明明可以直接 return 1,这里却要把类属性 __MASS_HINT
取出、交给 int() 解析、再经由一次中间变量返回。
{意图:增加复杂度}
"""
raw = PyPyUnit.__MASS_HINT
parsed = int(raw)
return parsed
def transmute(self) -> str:
"""把泬变成字符串。变完就扔掉,没人用结果。
{意图:增加复杂度} —— 纯浪费,但它让"每个泬都经过一次字符串化"
这个事实可以被 grep 验证。
"""
return "泬<" + self.reason + ">"
class LogBook:
"""泬账本。记录程序在抽象上的总开销。
{意图:增加复杂度} —— 一个本该是 int 的计数器,被做成了对象列表,
于是每次计数都会增长内存,最后统计时要再遍历一遍列表。
用一种 O(n) 的方式去做 O(1) 的事。
"""
def __init__(self):
self.units: list[PyPyUnit] = []
# 注意:不用 sum()、不用 len() 直接算总数的地方,见 total()。
def mint(self, reason: str) -> PyPyUnit:
"""铸造一枚泬并入库。每个操作都要走这里。"""
unit = PyPyUnit(reason)
self.units.append(unit)
return unit
def total(self) -> int:
"""统计总泬数。
绕路说明:Python 有 len(),这里偏要手写 for 循环累加,
而且每加一次都要调用 unit.mass()(那是个 3 次调用的方法)。
{意图:增加复杂度}
"""
accumulator = 0
for unit in self.units:
accumulator = accumulator + unit.mass()
return accumulator
def census(self) -> dict:
"""按理由分类统计。又一次 O(n) 遍历,而 total() 已经遍历过一次了。
{意图:增加复杂度} —— 同一个列表遍历两遍,就为了打印时好看。
"""
tally: dict = {}
for unit in self.units:
key = unit.reason
if key in tally:
tally[key] = tally[key] + 1
else:
tally[key] = 1
return tally
# =====================================================================================
# 抽象层 2:正则重验层(Regex Re-Validation Layer)
# =====================================================================================
#
# {意图:增加复杂度}
# 本层存在的理由:需求 3 规定"2 次正则匹配"。
# 因此即便是我们自己刚刚亲手扫描出来的 token,也必须用正则**再验一遍**,
# 仿佛我们自己不可信。
#
# 这一层在语义上是纯多余的——Lexer 已经知道一个 token 是数字了,
# 这里还要用正则重新确认它是数字。这正是它的设计意图。
# 数字:允许 123 和 123.45,也允许我们最终并不使用的科学计数法(永远匹配不上也无所谓)
RE_NUMBER = re.compile(r"^-?[0-9]+(\.[0-9]+)?([eE][-+]?[0-9]+)?$")
# 标识符:字母开头,后跟字母数字下划线。
#
# [修 bug] 原来是 `^[A-Za-z_][A-Za-z0-9_]*$`——**只认 ASCII**。
# 但词法扫描器切标识符用的是 `self._peek().isalnum()`,
# 而 Python 的 str.isalnum() **对中文返回 True**。
# 于是两层规则打架:
#
# 扫描器把「数」整个吞下来当标识符 -> 正则层用 ASCII 规则拒绝它
# -> raise LexError("正则层拒绝了这个标识符 '数'")
#
# 也就是"写了中文变量名就报错,但报的是正则层的错",
# 而扫描器那边明明放行了。用户看到的是自相矛盾的行为。
#
# 现在让正则跟扫描器**完全一致**:
# · 首字符:isalnum() 或下划线 -> [^\W\d] 等价于「字母(含中文)或下划线」
# · 后续: isalnum() 或下划线 -> \w 等价于「字母(含中文)、数字、下划线」
#
# 为什么用 [^\W\d] 而不是直接写 \w:
# \w 对中文返回 True,而 \w 也包含数字。首字符不能是数字,
# 所以用 [^\W\d] 表示"是 \w 但不是数字",正好对应 isalnum() 且非 isdigit()。
# 注意仍有个小差异:扫描器允许首字符是**任意** isalnum() 字符,
# 包括全角数字 3。这里不特意迁就——那种输入本来就该报错,
# 而报错位置从正则层挪回了扫描器层(见 _scan_word 的说明)。
#
# 约束:改这里必须同时确认 _scan_word 的切分规则没变,
# 否则两层会再次不一致(这正是本 bug 的成因)。
RE_IDENT = re.compile(r"^[^\W\d]\w*$", re.UNICODE)
# 符号:运算符与分隔符。
# 注意 '-' 放在字符类最后一位(否则会被当成区间)。
# 现状:花括号 { } 与分号 ; 已被移除——新语法用缩进断句,不再需要它们。
# 但保留识别能力会让"旧写法"静默通过,所以这里也不认它们,写错就报错。
# 新增:「」 $ ~ · 四个符号,对应赋值括号、输出、等于、不等于。
#
# #29「改这个正则加 {} 和 : 时把 '-' 漏掉了,于是所有减法/负数都报
# "正则层拒绝了这个符号 '-'"」
# {曾出现:v3 改完跑回归,阶乘、fib、深度测试全挂}
# {根因:我重写字符类时凭记忆写了一遍,把原本在集合里的 '-' 漏了。
# 这个字符类里 '-' 必须放在**最后一位**(否则会被当成范围符,
# 比如 `+-\*` 会被读成"从 + 到 * 的范围")。原来的写法是
# `...,.-]`——点、连字符、收尾方括号,正好把 '-' 放在最后。
# 我改成 `...,\{\}:]` 的时候顺手把 '-' 删了。}
# {教训:这类"一长串符号的字符类"改动,靠肉眼核对是不可靠的——
# 必须跑一遍会用到每个符号的回归。这次是回归测试先发现的。}
# **已验证**(tests/run_all.py 全绿)。
RE_SYMBOL = re.compile(r"^[()「」$+\*/<>~·!\[\],.\{\}:-]+$")
# 能开启一条新语句的 token 类型。
#
# 约束:这个集合在本文件里被三处引用(Parser._statement、
# Parser._starts_statement、以及别的判断"下一 token 能否接语句"的地方)。
# 原先每处都各写一份 `env.kind == "KW_IF"` 这样的判断,加关键字时
# 极易漏改其中一处——#14 就是这么来的。
# 现在统一到这里,改一处即可。新增关键字时**必须**同时想清楚:
# 它能不能在缩进块的末尾开启新语句。
STATEMENT_KEYWORDS = frozenset({
"KW_IF", "KW_WHILE", "KW_FOR", "KW_DEF",
"KW_RETURN", "KW_CLASS", "KW_GLOBAL",
# 第三版:break / continue 也是独立语句(不带表达式),
# 所以它们能开启一条新语句,必须进这个集合。
# 注意 and / or / not **不在这里**——它们是**表达式**运算符,
# 不能单独成句。加进来会让 `not` 被当成语句开头,破坏 `if not x`。
"KW_BREAK", "KW_CONTINUE",
})
# 数字 → 二进制串 的转换表(用于输出阶段,见层 7)
_HEX_DIGITS = "0123456789abcdef"
def revalidate(token_type: str, lexeme: str) -> int:
"""用正则重新验证一个我们刚刚自己扫描出来的 token。
返回值不是布尔,而是"匹配长度"(int),因为布尔太直接了。
调用方拿到 int 之后要自己跟 0 比较——多一次判断,多一次抽象。
{意图:增加复杂度} + 满足需求"2 次正则匹配":
每个 token 在这里至少匹配 1 次,数字之类会匹配 2 次。
"""
checkers: dict = {
"NUMBER": RE_NUMBER,
"IDENT": RE_IDENT,
"SYMBOL": RE_SYMBOL,
}
checker = checkers.get(token_type)
if checker is None:
# 关键字之类的 token,用一个永远匹配的空模式"验证"一下。
# 这是在浪费,但浪费得很有仪式感。
return len(re.match(r".*", lexeme).group(0))
matched = checker.match(lexeme)
if matched is None:
return 0
# 第二次正则:把匹配结果再匹配一遍。
# {意图:增加复杂度} —— 需求规定 2 次,那就实打实跑 2 次。
again = checker.match(matched.group(0))
if again is None:
return 0
return len(again.group(0))
def deep_validate(token_type: str, lexeme: str) -> str:
"""把 revalidate 的 int 结果再包装成字符串。
这样每个 token 就经历了:str(源) → 正则 → int → str 的完整轮回。
{意图:增加复杂度}
"""
width = revalidate(token_type, lexeme)
return str(width).zfill(3) # zfill 是纯装饰,但它是"又一层"
# =====================================================================================
# 抽象层 3:符号注册表(The Registry of Symbols)
# =====================================================================================
#
# {意图:增加复杂度}
# 这是整个项目最得意的一层。
#
# 一个正常的解释器会这样存变量: variables["x"] = 5
# 我们这样存:把值序列化成一个带校验和的字符串,存进一个列表,
# 查找时遍历整个列表,对每个元素**反序列化**,比较名字。
#
# 复杂度从 O(1) 变成 O(n),而且每次读写都要做字符串编解码。
# 这没有任何好处。这就是重点。
#
# {意图:降低可读性} —— 类名叫 Registry 而不是 VariableTable,
# 因为"注册表"听起来更厉害。
class RegistryEntry:
"""注册表里的一条记录。名字和值都被编码成字符串。
{意图:增加复杂度} —— 值本来可以直接放 Python 对象,
这里非要过一遍 encode/decode,就为了"统一表示"这个没人要求的抽象。
"""
SEPARATOR = "\x1f" # 单元分隔符,永远不会出现在源码里(因为 Lexer 会拒绝它)
def __init__(self, name: str, encoded_value: str, phase: int):
self.canonical_name = str(name).strip().lower()
self.encoded_value = encoded_value
self.phase = phase # 变量处于三阶段中的哪一阶段
def serialize(self) -> str:
"""把自己压成一个字符串,方便存进"扁平化"的表里。"""
return (
self.canonical_name
+ RegistryEntry.SEPARATOR
+ str(self.phase)
+ RegistryEntry.SEPARATOR
+ self.encoded_value
)
@staticmethod
def deserialize(blob: str) -> "RegistryEntry":
"""把字符串拆回对象。
{意图:增加复杂度} —— 我们刚刚序列化完,马上又要反序列化。
这个往返唯一的产出就是"发生过一次往返"。
"""
parts = blob.split(RegistryEntry.SEPARATOR)
return RegistryEntry(parts[0], parts[2], int(parts[1]))
class Registry:
"""用「序列化字符串列表」实现的变量表。
约束:故意不使用 dict 的键查找。虽然 self._flat 是个 list,
但每次 find 都要 O(n) 反序列化——这是特性,不是缺陷。
{意图:增加复杂度}
"""
def __init__(self):
self._flat: list[str] = [] # 全是字符串,不是对象
def _index_of(self, name: str) -> int:
"""O(n) 查找,且每次比较都要反序列化。
{意图:增加复杂度} —— 这就是"3 次数据结构转换"里的核心一次:
对象 → 字符串(serialize) → 列表 → 字符串(split) → 对象。
"""
target = str(name).strip().lower()
for position in range(len(self._flat)):
blob = self._flat[position]
entry = RegistryEntry.deserialize(blob)
if entry.canonical_name == target:
return position
return -1
def register(self, name: str) -> None:
"""注册(声明)一个名字,进入阶段 0 = 已声明未赋值。
{意图:增加复杂度} —— 注册时先写进去再读出来验证一遍。
"""
entry = RegistryEntry(name, "", 0)
self._flat.append(entry.serialize())
# 立刻反序列化验一次,确认我们刚写的能读回来。
# 这一步永远会成功,因此永远没有意义。
RegistryEntry.deserialize(self._flat[len(self._flat) - 1])
def contains(self, name: str) -> bool:
return self._index_of(name) >= 0
def phase_of(self, name: str) -> int:
index = self._index_of(name)
if index < 0:
return -99
return RegistryEntry.deserialize(self._flat[index]).phase
def write(self, name: str, encoded_value: str) -> None:
"""写入编码后的值,并推进到阶段 1 = 已赋值。"""
index = self._index_of(name)
if index < 0:
return
entry = RegistryEntry.deserialize(self._flat[index])
entry.encoded_value = encoded_value
entry.phase = 1
# 重新序列化并覆盖。注意这里是"读出字符串→变成对象→再变成字符串",
# 完全可以直接改字符串,但那多没意思。
self._flat[index] = entry.serialize()
def read(self, name: str) -> str:
"""读出编码后的值,并再经历一次反序列化。"""
index = self._index_of(name)
if index < 0:
return ""
entry = RegistryEntry.deserialize(self._flat[index])
# 再一次序列化/反序列化,确保我们读到的确实是刚读到的。
# {意图:增加复杂度} —— 这个往返是本项目的精神图腾。
return RegistryEntry.deserialize(entry.serialize()).encoded_value
def all_names(self) -> list:
"""列出所有名字。又要遍历 + 反序列化一遍。"""
names = []
for blob in self._flat:
names.append(RegistryEntry.deserialize(blob).canonical_name)
return names
# =====================================================================================
# 抽象层 4:值的编码层(Value Codec)
# =====================================================================================
#
# {意图:增加复杂度}
# 所有值在进入 Registry 前必须被编码成字符串,取出后再解码。
# 数字 → "N:5",布尔 → "B:TRUE"。
# 一个 int 5 变成 3 个字符,需要解析回来才能用。
#
# 这一层是"3 次数据结构转换"的主要贡献者:
# Python int → PyPyValue 对象 → 编码字符串 → 存 list → 解码回对象 → 取 .magnitude
# 真值格的四档。顺序很重要:索引越大越"真"。
#
# 第四版改名(重要):第二档原来叫 MAYBE,意思是"数字落在 0 和 1 之间"。
# 但第四版要引入**三值逻辑**,MAYBE 这个名字必须还给"未观测的量子态"。
# 于是这一档改叫 LIMBO("悬而未决的中间地带"),语义完全没变——
# 还是 0 < x < 1,只是不再占用 MAYBE 这个名字。
#
# 约束:改名**不影响任何逻辑**。verdict_index() 和 is_true() 都是按下标
# 工作的,不看字面名字,所以这里只是换了个字符串。
# 唯一可见的变化是输出:`$(0.5)` 现在印 `0.5 ⟨LIMBO⟩`。
TRUTH_LATTICE = ["FALSE", "HOPELESS", "LIMBO", "TRUE"]
# 真值 → 数字的映射表,用一个列表查,而不是 in 判断。
TRUTH_TO_INT = [0, 1, 2, 3] # 与 TRUTH_LATTICE 下标对应
class ObjectTable:
"""函数/类/实例的旁路登记表。
{意图:增加复杂度} —— 这是"值必须能编码成字符串"这条规则的后门。
数字/字符串/列表能真的序列化成文本,但这三样内部装着 AST 节点和
Python 对象,序列化不动。于是:把对象登记进这个表、拿一个编号,
在 Registry 里存的其实是编号字符串。
约束:只增不减。没有 free、没有引用计数、没有清理。
每定义一个函数、每个类、每个 new 出来的实例都会永久占一个槽位。
这是刻意的——一个真的会泄漏的表,才配得上这个项目。
"""
def __init__(self):
self._slots = []
def put(self, obj) -> int:
"""登记一个对象,返回它的编号。"""
self._slots.append(obj)
return len(self._slots) - 1
def get(self, slot: int):
"""按编号取回。取不到返回 None(调用方负责抛异常)。"""
if 0 <= slot < len(self._slots):
return self._slots[slot]
return None
def size(self) -> int:
return len(self._slots)
# 全局唯一的登记表。注意它是**模块级**的,所以同一个进程里跑多次
# evaluate_source 都会往同一张表里追加——编号不会重置。
OBJECT_TABLE = ObjectTable()
class PyPyFunction:
"""用户定义的函数。装的是 AST,不是编译结果。
{意图:增加复杂度} —— 定义时不做任何编译、不做任何检查,
只把参数名和函数体存起来。每次调用都要重新遍历一遍函数体 AST,
每次调用都要重新在作用域里逐个绑定参数。
真语言会编译一次、执行多次;这里坚持每次都从头解释。
"""
def __init__(self, name, params, body):
self.name = name
self.params = params
self.body = body
self.call_count = 0
def describe(self) -> str:
return "<函数 " + self.name + "/" + str(len(self.params)) + ">"
class PyPyClass:
"""用户定义的类。存方法名到 PyPyFunction 的映射,和类属性。
约束:没有继承、没有 super、没有元类。
"""
def __init__(self, name):
self.name = name
self.methods = {} # 方法名 -> PyPyFunction
self.attrs = {} # 类属性名 -> PyPyValue(编码前的原值)
def describe(self) -> str:
return "<类 " + self.name + ">"
class ReturnSignal(Exception):
"""return 语句的载体。
{意图:增加复杂度} —— 用异常做函数返回。见 Interpreter._do_return。
约束:它**不是**错误。任何 except 子句接住它之前必须想清楚
是不是在函数调用边界上;接错了会把 return 吞掉,函数会继续往下跑。
"""
def __init__(self, value):
Exception.__init__(self, "return")
self.value = value
class BreakSignal(Exception):
"""break 语句的载体。
{意图:增加复杂度} —— 用异常跳出一层循环。
#25「`break` 写在 `if` 里时,跳出的是 if 而不是循环」
{曾出现:加 break 之后的第一轮测试——`while` 里套 `if ... break`,
结果循环没停,只是 if 提前结束了。}
{根因:最初想省事,在 _do_if 里也写了 except BreakSignal。
但 break 的语义是"跳出最近的**循环**",if 不是循环,
它没有资格接住这个信号。}
{修法:只有 _do_while 和 _do_for 接 BreakSignal,
其他任何地方都不接——让它一路冒泡到最近的循环。
这条规则跟 Python 一致:语法上 break 就只能出现在循环里。}
**已验证**(tests/test_loop_control.py 的"break 在 if 里"用例)。
"""
def __init__(self):
Exception.__init__(self, "break")
class ContinueSignal(Exception):
"""continue 语句的载体。
{意图:增加复杂度} —— 跟 break 分开成两个异常类,
这样"谁该接住谁"在代码里一眼可辨。合并成一个类再带个标志位
会更省事,但那样 _do_while 里就得多一层 if 判断——
多一个类换少一个 if,符合本项目"结构复杂、分支简单"的口味。
约束:ContinueSignal 也**只能**被循环接住,理由同 BreakSignal。
"""
def __init__(self):
Exception.__init__(self, "continue")
def dirty_attribute_message(instance, name):
"""实例上没有这个属性时,给一个尽量有用的报错。
{意图:增加复杂度} —— 专门为"忘了写 self"这个最常见的错误
做一个提示:如果这个名字在实例属性的集合里存在、
只是当前这个实例没有,那多半是构造器里漏赋值了。
"""
available = []
for key in instance.attrs:
available.append(key)
for key in instance.klass.attrs:
if key not in instance.attrs:
available.append(key)
preview = ", ".join(available[:6]) if available else "(一个都没有)"
return ("实例上没有属性 " + repr(name) + ";现在有这些:" + preview)
class PyPyInstance:
"""类的实例。
{意图:增加复杂度} —— 每次取属性都要先查实例自己的 attrs、
查不到再查类的 attrs、还不是的话去找方法。三段查找,
而且**每次**都要重新做一遍,没有任何缓存。
"""
def __init__(self, klass):
self.klass = klass
self.attrs = {} # 实例属性名 -> PyPyValue
def describe(self) -> str:
return "<" + self.klass.name + " 的实例>"
class PyPyValue:
"""pyPython 的值。包一个 Python 数字,但拒绝直接暴露它。
{意图:增加复杂度} —— 需求说"每一步都要有意绕远路"。
取值要经过 .magnitude() → .decoded() → .raw 三层属性/方法访问。
"""
def __init__(self, raw, taint=None):
self.raw = raw
self._encoding_cache_hint = None # 从不用,但每次构造都要设置它
# --- 第四版追加:污染标记(taint)----------------------------------
#
# 为什么标记要存在**这里**而不是别处:Registry 存的是 encode() 出来的
# **字符串**,不是 PyPyValue 对象本身。所以任何挂在对象属性上的标记,
# 过一次赋值就没了(已实测:encode 返回 'N:5',decode 回来的是新对象,
# 属性全丢)。要让"未知"跟着值走,标记只能进**编码**。见 encode/decode。
#
# taint 是一个字符串路径,比如 "x" 或 "x>y",空串表示没被污染。
# 约束:**任何值都可以带污染标记**,不只是未知本身——
# `未知 + 1` 的结果是个数字,但它仍然是"被污染的数字",
# 这个事实必须留住,否则传两步就追不出来了。
self.taint = taint if taint else ""
def tainted(self):
"""这个值有没有被未知污染过。"""
return self.taint != ""
def extend_taint(self, *others):
"""把别的值的污染路径并到自己的路径上,返回一个**新值**。
为什么返回新值而不是原地改:原地改会让共享同一个对象的两个变量
互相污染(`a「未知」` `b「a」` `c「b+1」` 会让 a 也被标成污染)。
本语言到处是"读出来再打包",原地改迟早出事。
@ADR-0009:两种连接符,语义**不同**,不能混:
`>` 表示"流过去"——值从左边那个变量算出来,再存进了右边那个。
`x>y` 读作"x 传给了 y",是一条**路径**。
`+` 表示"两个独立来源汇合"——两个不同的未知一起参与了运算。
`a+b` 读作"a 和 b 各自被污染过",**不是**路径。
为什么必须区分:`c「a + b」`(a、b 都是独立的未知)如果写成
`a>b>c`,账本会撒谎说"a 引起了 b",而事实上 a 和 b 没关系。
用户按这个信息去查,会查到一个根本不存在的因果链。
约束:重复的来源不重复记(`x + x` 的路径仍是 "x")。
约束:**不拆开已有的 `>` 路径**——理由见 _merge_taint 的说明。
"""
parts = []
for piece in (self.taint,) + others:
if piece and piece not in parts:
parts.append(piece)
if not parts:
return PyPyValue(self.raw, "")
if len(parts) == 1:
return PyPyValue(self.raw, parts[0])
return PyPyValue(self.raw, "+".join(parts))
def append_hop(self, name):
"""在污染路径**末尾接一个传递环节**,返回新值。
@ADR-0009:这是唯一往路径上加 `>` 的地方,专门给赋值用:
`y「x + 1」` 里的值已经带着 "x",存进 y 时接上 "y" → "x>y",
读作"x 传给了 y"。
为什么不能用 extend_taint 接名字:那个方法的语义是"合并来源",
用的是 `+`。用它接名字会把"传递"错说成"并列"
(`x>y` 变成 `x+y`,账本就会说 x 和 y 是两个独立来源,
而它们其实是同一条链上的两站)。
约束:如果路径里已经有并集(`a+b`),接法是把名字接到**每一支**的末尾
(`a+b` → `a>c+b>c`),因为 c 确实同时来自这两支。
这里由调用方判断该不该接,见 _do_assign。
"""
if not self.taint:
return PyPyValue(self.raw, name)
branches = self.taint.split("+")
rebuilt = []
for branch in branches:
if name in branch.split(">"):
rebuilt.append(branch)
else:
rebuilt.append(branch + ">" + name)
return PyPyValue(self.raw, "+".join(rebuilt))
def taint_chain(self):
"""把污染路径拆成一条链,给账本用。["x", "y"] 这种。
约束:只把 `>` 当路径分隔符。`+` 是并集,不是路径——
`a+b` 拆出来是 ["a", "b"],读作"两个独立来源",不是两步传递。
"""
if not self.taint:
return []
return self.taint.replace("+", ">").split(">")
def taint_origins(self):
"""只取"最初的来源",不要中间环节。给提示语用。
怎么判断谁是源头:路径里的第一个就是。
`x>y>z` 的源头是 x;`a+b` 的源头是 a 和 b(都算)。
"""
if not self.taint:
return []
out = []
for branch in self.taint.split("+"):
first = branch.split(">")[0]
if first and first not in out:
out.append(first)
return out
def taint_depth(self):
"""污染传了几步。手写循环累加,不用 len()。{意图:增加复杂度}"""
steps = 0
for _ in self.taint_chain():
steps = steps + 1
return steps
def magnitude(self) -> float:
"""把值取出为 float。数字要经过 float() 转换,即使它本来就是 float。"""
if isinstance(self.raw, bool):
# 布尔先变成 int 再变成 float,多两跳。
return float(int(self.raw))
return float(self.raw)
def decoded(self) -> float:
"""再包一层。调用链:decoded → magnitude → raw。
{意图:增加复杂度} —— 这个函数体只有一行,完全可以删掉,
但删掉之后调用栈就少了 1 层,那是不可接受的。
约束:**只有数字能走这里**。字典、函数、类、实例都没有
"数值"可言,对它们调本方法会抛 Python 的 TypeError
("'dict' object ..."),那是宿主实现的错误信息,
不该让用户看到。要判真值请用 truth_number()。
"""
return self.magnitude()
def truth_number(self) -> float:
"""给"任何值"一个用于判真假的数字代用值。
为什么需要这个方法:本语言的规则是"任何值都要经过真值密室",
而密室只认数字。于是每一类值都得找个数字来代表它:
数字 → 它自己
字符串 → 长度
列表 → 元素个数
字典 → 键值对个数
函数/类/实例 → 0(它们没有"多少"可言,一律当假)
{意图:增加复杂度} —— 这套映射在语义上毫无依据
("长度 3"被判成 TRUE 又怎样?),唯一的作用是
让"任何值都必须经过密室"这条规则不被类型破坏。
#28「`if 字典` 和 `not 字典` 抛 TypeError: float() argument
must be a string or a real number, not 'dict'」
{曾出现:v3 的字典探针,"字典当条件"与"字典走 not"两个用例}
{根因:判真值的地方一律写 raw.decoded(),
而 decoded() → magnitude() → float(raw) 只对数字成立。
字符串和列表能"侥幸"工作是因为它们的判真值路径
(transmute_output)走的是 len(),绕开了 decoded();
但 if 和逻辑运算直接调 decoded(),字典一进去就炸。}
{修法:把"取判真值用的数字"这件事收进本方法,
四类值各给一个代用值;上述四处调用点统一改调它。}
**已验证**(_probe_dict.py 的两个用例由 ERR 变 OK)。
"""
raw = self.raw
# 第四版:未观测态要**在这个方法里就拦住**。
# 不拦的话 float("MAYBE") 会抛 ValueError,用户看到的是宿主的
# 报错信息,而不是"这里状态未知"。
#
# 返回值的选择:给一个**既不是 0 也不是 ≥1** 的数,
# 于是密室会把它判成 LIMBO(第三档),而 is_true() 对 LIMBO 返回 False。
# 这样旧的控制流(还没改成三值的那部分)不会因为未知而炸,
# 只会安静地走"非真"那条路。真正的三值判断在 tri_from_value 里做。
if raw == MAYBE_UNKNOWN:
return 0.5
if isinstance(raw, (PyPyFunction, PyPyClass, PyPyInstance)):
# 这三样没有"多少"可言。给 0 就是一律判假——
# 刻意不按"参数个数/方法数/属性数"来判,
# 因为那样 `if 某个函数` 会因为参数多而变真,太容易误解。
return 0.0
if isinstance(raw, str):
length = 0
for _ in raw:
length = length + 1
return float(length)
if isinstance(raw, list):
return float(len(raw))
if isinstance(raw, dict):
return float(len(raw))
return self.decoded()
def encode(self) -> str:
"""编码成字符串以便存进 Registry。
@ADR-0003:值编码用**长度/个数前缀**,元素边界由类型自身界定,
不依赖分隔符。曾经的"逗号拼接"方案在嵌套列表和含逗号字符串上
必然出错(#13),且补丁式修补会不断引入新边界问题。
见 docs/decisions/0003-decode-长度前缀编码.md
@ADR-0009:污染标记(taint)作为**可选前缀**写在这里,见下面 _encode_body。
约束:**没污染的值编码完全不变**——这是向后兼容的关键,
也是"现有 65 项测试和所有旧输出格式不受影响"的原因。
约束:数字以外的类型要各走各的前缀,且**必须**能原样解回来。
S<长度>:<内容> 字符串
L<个数>:<元素...> 列表
D<对数>:<k><v><k><v>... 字典
N:<数值> 数字
T<路径>|<上面任一> 被未知污染过的值(路径用 > 连接)
#12「加了字符串/列表之后,decode 用 `^N:` 的正则去匹配 S: 开头的串,
永远匹配失败,于是所有字符串都静默变成数字 0」
{曾出现:_tmp 探针里 $("abc") 输出 0 ⟨FALSE⟩ 0b0}根因:decode 只认 N: 前缀,
匹配失败时**没有报错而是返回 0**——那个容错分支在只有数字时是"友好",
有了多类型之后它变成了"静默吞掉类型"。修法:按前缀分派,见 decode。
**已验证**。
#13「嵌套列表 $( [1, [2, [3]]] ) 输出成 [1, 0, [0]],内层数据全丢」
{曾出现:字符串/列表探针的"嵌套列表"用例,同时 $(["a,b","c"]) 被切成 3 个元素}
根因(重要):列表原先用 ",".join() 拼接、str.split(",") 切分。内层列表
编码后本身含逗号(L:[N:2,L:[N:3]]),被外层一刀切开就成了残缺片段,
正则匹配失败,于是又落进 #12 那个"返回 0"的兜底分支——**同一个兜底分支
连犯两案**。修法:改用长度/个数前缀编码,元素边界由类型自己界定,
彻底不依赖分隔符;同时把兜底从"返回 0"改成抛异常。
**已验证**(_tmp_str_probe.py 的嵌套列表、含逗号字符串用例)。
"""
body = self._encode_body()
if not self.taint:
# 没污染:原样返回,一个字符都不多。
return body
# 有污染:前面挂上 T<路径>|。
# 约束:路径里**不能出现 `|`**,否则 decode 会切错位置。
# 来源是变量名(标识符 + `>`),标识符不允许 `|`(见 RE_IDENT),
# 所以这里是安全的;万一不是,替换掉也不让编码坏掉。
safe = self.taint.replace("|", "_")
return "T" + safe + "|" + body
def _encode_body(self) -> str:
"""真正干活的那部分编码。encode 负责在外面套 taint 前缀。
{意图:增加复杂度} —— 明明可以在 encode 里加一个参数搞定,
这里偏要拆成两个方法,于是每次编码都多一层调用、多一次字符串拼接。
"""
raw = self.raw
if isinstance(raw, str):
# 长度前缀 + 原样内容。这样内容里出现任何字符(逗号、方括号、引号)
# 都不会产生歧义,也**不需要任何转义**——解码时按长度精确切即可。
# 这比原来的 \" 转义方案更笨,但更不容易错。
return "S" + str(len(raw)) + ":" + raw
if isinstance(raw, list):
# 列表:先写元素个数,再把每个元素的编码用 ',' 连起来。
# 例如 [1,[2]] → L2:N:1,L1:N:2,
# 解码时先读个数,再让每个元素自己吃掉该吃的那一段。
# {意图:增加复杂度} —— 每个元素都要递归走一遍自己这一层的 encode,
# 所以嵌套列表的编码耗时是乘积级的。
pieces = []
for item in raw:
pieces.append(item.encode())
joined = ",".join(pieces)
return "L" + str(len(raw)) + ":" + joined
# --- 字典 --------------------------------------------------------------
# 编码:D<对数>:<k1编码><v1编码>,<k2编码><v2编码>,...
#
# 约束:key 和 value 都用**完整的 encode 往返**,
# 所以 key 本身可以是数字、甚至是列表(虽然没意义)。
# 边界由各自的长度/个数前缀界定,跟列表一样不依赖分隔符。
#
# 键的顺序:按 Python dict 的插入序原样写出。
# 解码时会重建一个 dict,所以**键的顺序会被保留**
#(CPython 3.7+ 保证 dict 有序)——这点在输出里能看出来。
if isinstance(raw, dict):
pieces = []
for key in raw:
# 约束:raw 是 Python 的原生 dict,所以 key 是**原始值**
#(字符串或数字),value 是 PyPyValue。
# 两边类型不一样,必须各自包一次——我第一版直接对 key
# 调 .encode(),于是字符串 key 报
# "sequence item 0: expected str instance, bytes found",
# 数字 key 报 "'int' object has no attribute 'encode'"。
pieces.append(PyPyValue(key).encode())
pieces.append(raw[key].encode())
joined = ",".join(pieces)
return "D" + str(len(raw)) + ":" + joined
# --- 函数 / 类 / 实例 -------------------------------------------------
#
# 约束:这三样东西内部装着 AST 节点和 Python 对象,没法像数字那样
# 直接序列化成文本。但"任何值都必须能存进 Registry"这条规则不能破,
# 于是走一个**旁路登记表** OBJECT_TABLE:
# encode 时把对象登记进去、拿回一个编号,返回 "F<编号>" / "C<编号>" / "O<编号>"。
# decode 时按编号取回来。
#
# {意图:增加复杂度} —— 这等于绕过编码层又开了一个后门,
# 而且登记表**只增不减**(没有任何地方清理它),
# 所以每创建一个函数/类/实例都会永久占一个槽位。
# 名字查找仍然要走完整的 Registry 字符串往返,只是"值"变成了一串编号。
if isinstance(raw, PyPyFunction):
return "F" + str(OBJECT_TABLE.put(raw))
if isinstance(raw, PyPyClass):
return "C" + str(OBJECT_TABLE.put(raw))
if isinstance(raw, PyPyInstance):
return "O" + str(OBJECT_TABLE.put(raw))
value = self.decoded()
if value == int(value):
return "N:" + str(int(value))
return "N:" + repr(value)
@staticmethod
def decode(blob: str) -> "PyPyValue":
"""从字符串解码。
约束:本方法**必须**与 encode 严格对称,任何不对称都会静默产生错值。
为杜绝 #12/#13 那种"匹配失败就返回 0"的静默兜底,
解不出来一律抛 ValueError(解释器会把它变成带位置的「炑」)。
@ADR-0009:脏活在前几行——先剥掉可选的 T<路径>| 污染前缀,
把值本体交给 _decode_body 解,解完再把路径贴回**解出来的那个对象**上。
约束:污染标记必须贴到最外层对象,不能往元素里递归下发——
因为 `[x]` 这个列表整体是被污染的,而它的元素是什么类型是另一回事。
"""
# --- 污染前缀:T<路径>|<本体> -----------------------------------------
if blob.startswith("T"):
bar = blob.find("|")
if bar > 0:
path = blob[1:bar]
body = blob[bar + 1:]
# 约束:递归解本体。本体自己**不应该**再带 T 前缀
#(encode 只加一层),万一带了也不怕——递归会自己剥掉。
inner = PyPyValue.decode(body)
return PyPyValue(inner.raw, path)
return PyPyValue._decode_body(blob)
@staticmethod
def _decode_body(blob: str) -> "PyPyValue":
"""真正干活的那部分解码(不含污染前缀处理)。见 encode/_encode_body。"""
# --- 字符串:S<长度>:<内容> -------------------------------------------
if blob.startswith("S"):
colon = blob.find(":")
if colon > 0:
count_text = blob[1:colon]
if count_text.isdigit():
size = int(count_text)
body = blob[colon + 1:]
return PyPyValue(body[:size])
# --- 列表:L<个数>:<元素1>,<元素2>,... -------------------------------
if blob.startswith("L"):
colon = blob.find(":")
if colon > 0: