用 C# 类型系统做了个 Brainfuck 编译器

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

• 请不要在回答技术问题时复制粘贴 AI 生成的内容

最近花了点时间做了个 Brainfuck 编译器，编译后的程序用 C# 的类型来表达。

比如这是一个编译出来的 Hello World 的 Brainfuck 程序：

AddData<Int<Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex8>,Loop<AddPointer<Int<Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex1>, AddData<Int<Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex4>, Loop<AddPointer<Int<Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex1>, AddData<Int<Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex2>, AddPointer<Int<Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex1>, AddData<Int<Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex3>, AddPointer<Int<Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex1>, AddData<Int<Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex3>, AddPointer<Int<Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex1>, AddData<Int<Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex1>, AddPointer<Int<HexF, HexF, HexF, HexF, HexF, HexF, HexF, HexC>, AddData<Int<HexF, HexF, HexF, HexF, HexF, HexF, HexF, HexF>, Stop>>>>>>>>>>, AddPointer<Int<Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex1>, AddData<Int<Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex1>, AddPointer<Int<Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex1>, AddData<Int<Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex1>, AddPointer<Int<Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex1>, AddData<Int<HexF, HexF, HexF, HexF, HexF, HexF, HexF, HexF>, AddPointer<Int<Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex2>, AddData<Int<Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex1>, Loop<AddPointer<Int<HexF, HexF, HexF, HexF, HexF, HexF, HexF, HexF>, Stop>, AddPointer<Int<HexF, HexF, HexF, HexF, HexF, HexF, HexF, HexF>, AddData<Int<HexF, HexF, HexF, HexF, HexF, HexF, HexF, HexF>, Stop>>>>>>>>>>>>>>, AddPointer<Int<Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex2>, OutputData<AddPointer<Int<Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex1>, AddData<Int<HexF, HexF, HexF, HexF, HexF, HexF, HexF, HexD>, OutputData<AddData<Int<Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex7>, OutputData<OutputData<AddData<Int<Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex3>, OutputData<AddPointer<Int<Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex2>, OutputData<AddPointer<Int<HexF, HexF, HexF, HexF, HexF, HexF, HexF, HexF>, AddData<Int<HexF, HexF, HexF, HexF, HexF, HexF, HexF, HexF>, OutputData<AddPointer<Int<HexF, HexF, HexF, HexF, HexF, HexF, HexF, HexF>, OutputData<AddData<Int<Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex3>, OutputData<AddData<Int<HexF, HexF, HexF, HexF, HexF, HexF, HexF, HexA>, OutputData<AddData<Int<HexF, HexF, HexF, HexF, HexF, HexF, HexF, Hex8>, OutputData<AddPointer<Int<Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex2>, AddData<Int<Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex1>, OutputData<AddPointer<Int<Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex1>, AddData<Int<Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex2>, OutputData<Stop>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

然后可以直接运行这个程序输出 Hello World!：

<前面那一大串类型>.Run(0, stackalloc byte[16], Console.OpenStandardInput(), Console.OpenStandardOutput());

性能出乎意料的不错，尤其是经过 NativeAOT 编译出独立可执行文件后，跑 Mandelbrot 甚至超过了先把 Brainfuck 代码翻译到 C 后再用 clang -O3 -march=native 编译出来的程序的性能。

项目	执行时间（毫秒）	排名	比例
C 解释器	4874.6587	5	5.59
GCC	901.0225	3	1.03
Clang	881.7177	2	1.01
.NET JIT	925.1596	4	1.06
.NET AOT	872.2287	1	1.00

项目地址： https://github.com/hez2010/Brainfly

一些介绍： https://zhuanlan.zhihu.com/p/20878662768

欢迎点 star ！

brainfuck

编译器

4 条回复

w568w

6 天前

有点意思。C# 的类型系统有解析层数限制吗？至少 TypeScript 中，这样的奇巧淫技是玩不了的：

https://github.com/microsoft/TypeScript/issues/34933#issuecomment-552500444

hez2010

6 天前 via Android

@w568w 目前来看似乎是没有限制的，Mandelbrot 套出了总共 16 万多个字符长度的类型名都能正常解析和运行。

WorseIsBetter

5 天前

可惜 C# 的类型系统不支持像 TypeScript 和 C++ 那样直接操作 string literal ，还得需要一个额外的编译器来将 Brainfuck 代码编译成那一坨「中间表示」。

（翻了一下楼主历史发言，原来楼主曾经在 .NET 社区提过相关 proposal 甚至还给出了参考实现，哈哈失敬失敬）

WorseIsBetter

5 天前

@w568w #1

我之前在用 TypeScript 的类型系统实现 Unlambda 解释器的时候也发现了这个问题。跑个简单的字符串翻转都会超过限制，几乎完全不可用。

当时看到有人提了个 patch 来放宽这个限制，但并没有被官方接受： https://github.com/microsoft/TypeScript/pull/29602

没办法最后只能在 README 里让用户手动魔改 tsc/tsserver 代码（