Tripod-语言参考规范(草案)

2019-06-08 10:22:56 +08:00
 Qiaogui

我曾在 V2EX 发过一个要开发一门编程语言的帖子,这是最新的进展。 Github: https://github.com/QiaoguiDai/Tripod 原贴: https://www.v2ex.com/t/561958

3938 次点击
所在节点    程序员
59 条回复
FrankHB
2019-06-11 18:43:09 +08:00
@Qiaogui 1.没什么好偷懒的地方,自由存储区(比如操作系统提供的堆)上分配逻辑上 LIFO 的活动记录帧来当作传统的栈。SML/NJ 就是这样做的。
好处是其实不止能实现能避免 stack overflow UB 的栈,first-class continuation 和 PTC 都会省事。
坏处是被当前流行给 ALGOL 开洞的体系结构歧视,即便不考虑碎片问题,不同时实现 GC 就会有 overhead (不过老实说,故意回避 GC 对实现水平要求远远更高)。某些 ISA 上可能还会有标准 calling convention 兼容性的问题。
FrankHB
2019-06-11 18:43:35 +08:00
2.一般意义上就是闭包。用 GC 偷懒回避 funarg problem,或者用 C++这种允许 UB 而不依赖 GC 的设计。
Pascal 的解是半吊子,回避了 upwards funarg problem 却也无法支持 first-class function,不推荐。
FrankHB
2019-06-11 18:45:43 +08:00
3.4 ……其实我建议还是先写( AST )解释器。
架空 bytecode 摊子太大效果好不到哪去,而当前实用 native 编译器不得不依赖太多跟后端 py 的特性,太糟心了,而且要通用根本就不是几人年能做到让一般人满意的。
(仅从这个意义上,我就不看好单枪匹马头铁直接设计出来的所谓“编译型”语言。等整出能用的早凉了。)
FrankHB
2019-06-11 18:46:06 +08:00
LLVM 的主要问题是你别想省事地在上面实现和 C/C++差太多的语言。也没什么能方便部署的公共运行时,JIT 也很叒鸡的样子。
JVM 的一个问题是……残……比如 Clojure 被迫 X 了 TCO。另一个问题是 bytecode 设计还是挺感人的,实用慎重( Dalvik 表示情绪稳定)。好的地方是现在有 Graal,别的地方没类似的备胎好用,但考虑要求糊感人的 Java ……还是忘了吧。
CLR 中规中矩一点,不过也不指望比 JVM 好哪去(有的部件性能也不咋地)。
魔改个 lua 什么的还可能有点实用性。习作的话,你要有信心你的语言足够像 C/C++,那用 LLVM 无妨。否则注意了解功能限制,剩下的就是哪个看着顺眼用哪个。
我是没排除 C/C++烂的东西以后还能有这个信心,所以就不折腾了。以后有空了移植个 nanopass 类似物。
但是后端坑太大了,我不觉得要验证语言的设计需要做到这个地步。
FrankHB
2019-06-11 18:46:18 +08:00
5.可以。
(就我要的东西,大不了做个到 Chez 甚至 Racket 的 transpiler,不是 CPU 密集基本不会比 native 烂哪去……)
Qiaogui
2019-06-11 18:50:44 +08:00
@FrankHB 谢谢
Em5O7B1JGfjQnBry
2019-06-11 20:22:53 +08:00
@FrankHB 你写的好多- -'''

1. 工程上的工作量的问题,说实话就是成本的(时间、金钱、人等)问题,有没有效果这点是很难讨论的,因为工程上大家很少评估你一个程序 bug 少,往往评估的是性能、feature 等等,总而言之,质量这件事情在工程上真的很不好量化,所以真正用 FV(formal verification)的地方都来自于学院派或有一定底气的公司。

用 FV 从领域上来讲,更容易区分,用 FV 的都是质量和成本真正可以讨论的领域,比如部分硬件和嵌入式系统,这些系统一出现 bug 的后果就是灾难的,所以在这些领域 FV 会比其他地方常见,还有分布式和并发系统,这是因为时序太复杂了,普通的测试一般搞不定,所以有时候也可以看到 FV 的影子,比如 Lamport 的 TLA+( lamport 的很多 paper 都会有相应 TLA+代码,遇到不理解的问题,直接看代码简直太舒服了)

2. CompCert 这个工程我觉得还是有意义的,整个系统用上 FV 真是很少,但是有些库比如一些高并发、分布式核心逻辑(一致性协议、多阶段提交等)等等用 C 写完后,编译给 Coq 做证明是非常有意义的,不然真是很难写对。。。

3. 用户这件事情,我觉得看做什么,普通的用户当然不行,但是对于开发者,把 formal spec 已良好的方式展示给用户这点太重要了,比如你要写某语言的静态分析,严格的 BNF 和 Type Rules 等等真的太重要了,写各种系统写扩展(比如写 Mysql 分布式中间件)没有 Formal spec,简直了。。。我觉得这就是业界应该改进的地方。

4. 我觉得整个系统用 FV 这种场景用 Coq 这样来做定理证明还是很难的,但是 Model Checking 是有意义的,一方面 check 整个系统的逻辑,一方面可以把 formal spec 当文档,比各种瞎糊的人肉文档靠谱太多了。

5. 可以扩展和派生这点,也不难吧,Coq 这样的定理证明器,直接看 Theorem(Type)就很清晰了,扩展就是直接加新的 Theorem 就好了。Model Checking 如 TLA+基于集合论虽然口味奇特,但是也是有可扩展 module。Spec 一般都是期望行为,具体的只要可以能被证明是符合需求的,那就没问题,随便改。

其他,关于 FV 方向性的探索方向一直都有,比如 Coq 本身不是通用语言也可以作为 Source 直接编译到通用语言啊,比如把 Coq 代码编译到 Haskell/Rust/ML,这都是可以的尝试,在比如 Idris 本身就是通用语言,因为支持 DT(dependent type)也可以做定理证明,抛开这些 refinement type 这些年也挺不错的吧,不用堆 proof,还有 Model checking 就更简单了,堆机器跑就好了,也不用费心思写 proof。
FrankHB
2019-06-11 23:31:41 +08:00
@svenFeng 0.因为这站还动不动什么验证手机号风评在外,直接写完懒得精简了(否则也不会有那么低级的 typo )。

1.评估是软件工程(SE)的难题,说白了是 PL 圈外部的事情,PL 圈的立场无视这个倒正常。以 paper 为目的的 PL 圈确实不够格。LZ 不算这个圈子,无所谓 PL 圈规矩,不过至少仍然受到 SE 不可抗力的制约,所以需要惦记。
关于 FV 基本同你的意见。显然 LZ 的东西不算适合 FV 的了。

2.CompCert 当然很有意义,不过对做软件的多数人来说,影响主要就是更了解类似 C 这样的语言和实现方式有多么恶心无能,而不是对具体项目能用得上——特别考虑到有需求不得不用 C 的,往往还会用到 CompCert 不支持的特性。
C 的一些困难实际上是原则性和系统性的。类似之前提过的依赖问题,实际上 C 程序内部就很明显:当运行时调用了一个看不见定义的函数,一旦其中不能排除 UB,一样凉凉。
当然,严格来讲这不是 C 的问题,因为看不清的定义完全可以是其它语言写的,而需要允许这种写法一定程度上是不可抗力。
这种片面要求链接兼容性是工程语言和 SE 的传统问题,不能也不该指望 FV 解决。但是,如果 FV 工具受到限制的现状能推进重视这类工程问题,即便不 FV,也算间接起到了正面的作用。

3.因为强调“通用”,用户就非常不特定了,即便不需要提供同等支持。较真的话,作为最终用户的非专业开发者写配置文件应该也能用得上这样的语言。( LZ 的设计没法做到达到这个目的的程度另说。)
另一方面,专业的开发者要是缺乏相关背景,对 formal method 的理解普遍是片面的,能理解 BNF 的大部分都不怎么能想象到如何 formalize semantic rules,更别提使用了。
这个我认为也没法指望靠 PL 业界拉动,CS 基础教育说到底是另一个距离差得太远的行业。(至少比物理学拉动数学困难。)
然后,业界的编码水准恐怕很成问题。
这至少带来两个推广问题:
a)不和非 PL 出身的职业用户共享工作习惯,准确理解 /想象用户需求困难,不混 paper 就找不到符合实际的方向,或者脑补容易做的需求过日子,于是越来越容易脱离工业界。
b)当 formal spec 越来越像样——接近被 FV 的代码,flavor 被传到到 spec 上,SE 的各种客观混账限制生效,维护成本和扩展的机会成本越来越没法忍受,更没机会推广给用户,自然内卷小圈子玩了。

4.有充足理由负担成本敢上 model checking 这样手法的个别项目,使用 formal method 和不使用相比,往往是有容易理解的意义的。
但是非特定项目的整体来讲,就很捉急了。

5.关键不是做不到可扩展,而是去扩展时需要靠人完成的工作量。
……以及机会成本和沉没成本。
一旦加上“通用”的需求,这类问题会很容易到处都是。
靠设计个别可扩展 feature 来解决是不现实的,搞不好费了多项式时间去设计实现组合 features,还解决不了线性规模的普遍问题。

其它……我提过比 type 更严重的问题是 phasing。所有你提到的这些语言都逃不出 static 这个圈圈。
加上通用目的的魔咒,static languages 可能是整个没有未来的。搞 formal methods 和 type system 的大部分人大概都还没 smoothness 这类关于抽象能力的概念(明明一定程度上这个是更欠 formalize 的……)。
Em5O7B1JGfjQnBry
2019-06-12 00:25:38 +08:00
@FrankHB 我倒不觉得 static 有啥问题,从代码角度上来说,定理证明作用之一就是顺带提供一个精妙的手段去完成 statically analyse 的工具,要求 total function 也理所当然,从这个角度上来讲,这不是 bug,是 feature😏(逃
FrankHB
2019-06-12 00:40:39 +08:00
@svenFeng 当要把一长坨 spec 当代码来维护的时候,就会容易发现一些尴尬的问题,比如缺少 ad-hoc 的特例规则就没法 late binding,需要单独的 reflection 并且要有很多幺蛾子才能实现对,static 和不 static 的类似废话不得不重复,pattern sublanguage 之类的马甲越来越多并且设计上难以去重……所有这类关于可修改性的问题根本都来源于不切实际的 static phasing 的设计。这根本上就是需求理解偏差:通用意义上真正需要的只是保证有限的局部依赖来确定语言的解释的局部有序关系——例如根据某一类特定的计算决定另一类的求值结果,而不是非得具体到预设一坨全局特性集合然后映射到不相交集合甚至干脆直接分层映射到一坨序数上去。后者本质上是一种对实现细节的抽象泄露,一定程度违反了最小特权原则。
FrankHB
2019-06-12 00:43:09 +08:00
@svenFeng 换句话说,没很具体的问题域,一般本来就根本不应该存在全局意义上的 static 不 static,非得预设 static 和不 static 两类性质已经一定程度放弃了能做的不少必要的事情了,有这种 feature 就通用不到哪去。
FrankHB
2019-06-12 00:53:13 +08:00
@svenFeng 关于定理证明你说得没错,因为定理证明本来就是一个相当 specific 的 domain。
问题在于,从 DSL 里 extract 出 general-purpose language 的做法,比反过来用 general-purpose language 去 derive 不同 DSL 的做法凭空多出不可忽视的工作量,却没有多少现实收益。
后者的做法先不算 derive (因为习惯上只有反过来接着 extract ),在这个 domain 里也就 ML 勉强能算。但是 ML 的问题嘛上面说过了,再加自身扩展起来也很疼,改 spec 不容易,加新 feature 照样得考虑大坨具体 feature 之间的关系,跟真实的 general-purpose 差远了……
Em5O7B1JGfjQnBry
2019-06-12 01:37:14 +08:00
@FrankHB

我没明白什么是 phasing - -'''

这两种双向转换说不上哪个好那个差吧,比如从把 C 编译到中间语言,然后 Coq 写证明,就是写 C 舒服,用写证明蛋疼。

而把 Coq 代码 extract 出 haskell 代码是写证明简单,extract 出来的代码质量可能不可控,写 Coq 代码也是件不怎么爽的事情。

对我个人来说,我基本都不会趋向于这么干。。。我更有可能拿 Coq 来写 high-level model and proof,然后再去写对应的 haskell/rust 代码。
FrankHB
2019-06-12 12:40:00 +08:00
> 我没明白什么是 phasing - -'''

cf. The Definition of Standard ML
Chapter 1, para. 3, 4.

> 这两种双向转换说不上哪个好那个差吧

这显然有问题的。首先转换相比之下是凭空多出来的步骤,如果是兼容历史遗留问题还能理解,对新的项目有什么积极意义?
然后更严重的问题是 spec 本身。
你提的语言里要么默认了,要么明确指出这种和我要求的相反的做法,如 SML 这种为了 formal spec 偷懒,撑死只允许实现混淆 static 和 dynamic phase,而 spec 里是写死了的。但这种 formal spec 的东西其实是没法直接用于不区分 phase 的实现的,实际上变相歧视了更自由的实现(类似 C/C++都明确回避要求编译,但不 AOT 编译实现起来就是吃亏)。
同时,这样 formal spec 更复杂了,而不是标榜的简单了——所谓的简单,是作者自认为的写起来的简单而不是统计写出来东西有多少能客观度量的复杂度的意义上的简单,本质上就是无视元语言的复杂度的鸵鸟政策罢了,就像 AOT 编译把调用编译器的 penalty 无视以后自以为比 JIT 高效一样( AOT 性能的问题还就是 phasing 破事的另一个具体例子)。
你感觉不出这个问题,可能是因为你和大多数用户一样只使用到现有资源的某一小个子集。比如你用 C,不理解 LLVM 和 cfe 的实现以及 ISO C 的 rules 有多蛋疼,也不是不能干活。但对想要把 spec 垂直地复用到实现上游和下游各个层次、去除其中的重复冗余的 hacker 来说,这是显然不够的。
现在的业界被动适应的这个问题并不光彩,大体思路就是算力不够堆机器,人力不够 996。这是不可持续发展的,同时分工过头导致几乎禁绝垂直复用。虽然能多搞点就业多吹 GDP 吧……
Em5O7B1JGfjQnBry
2019-06-12 14:32:55 +08:00
@FrankHB 看了发现这种 phasing 是合理的啊,理论上除了 evaluation phase,其他 phase 都必须是 static,这是期望行为吧(包括 parsing phase ),也就是这是 feature 啊,理论上任何抽象解释都应该停机,不然就谈不上正确性了,不停机的编译器,那不得 gg。
Qiaogui
2019-06-12 15:02:33 +08:00
@FrankHB 大大,昨天我看了您的回复,我自己也想了许久。最终还是决定以第 4 种类似的方法实现,因为我发现如果直接翻译成现成的高级语言是有些不现实的,源语言总是会受到目标语言的制约,导致与语言特性相关的不同的底层实现会变得异常困难,所以我考虑再三,还是决定以一个基于寄存器字节码解释器的形式实现(不用栈式是因为用起来不方便),不过我不想依赖于 JVM 和 DVM,以及 LLVM,我打算自己从头开发字节码,关于这方面,想咨询一下您的看法。您对有关设计字节码的书籍有什么好的推荐吗?
FrankHB
2019-06-12 19:38:28 +08:00
@svenFeng 不合理。
1.你忽略了 phase 可以允许让用户指定的设计。保证停机最终是用户的责任。
另外,做编译器基本上不会是实现语言的直接的目的,所以可以反过来想:“能停机的实现的一部分才叫编译器”。停不下来嘛就凉拌。
2.你忽略了 static 之间也不完全是一回事。
(虽然如果不忽略继续头铁 static 的话可能会进另一个坑,比如 static_assert 大战#ifdef。只是这通常没有 std::integral_constant 和 integral type 没法合并的问题这样恶劣罢了。)
FrankHB
2019-06-12 19:40:21 +08:00
@Qiaogui 坑太大,不太值。
因为需要 trial & error 成本太大,我回避从头开始造字节码的设计,对这方面了解不够 。
Tomotoes
2020-04-29 15:22:17 +08:00
@Qiaogui 现在进展怎么样了?

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/571918

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX