有什么配置语言是图灵完备的吗?

2020-04-17 10:43:30 +08:00
 vevlins

重点是配置语言,类似于 json 、yaml 这种类型。

6425 次点击
所在节点    程序员
37 条回复
learningman
2020-04-17 12:31:58 +08:00
@gkiwi 可以写自己的编译器
DGideas
2020-04-17 13:04:53 +08:00
@learningman 不准确,这叫自举( BootStrap )
SoloCompany
2020-04-17 13:39:21 +08:00
kotlin dsl
js
mightofcode
2020-04-17 15:16:17 +08:00
图灵完备的不适合做配置语言
TangMonk
2020-04-17 15:16:55 +08:00
ruby 的 dsl 算么
purensong
2020-04-17 15:21:23 +08:00
图灵完备是相对不完备而言的,图灵完备是一切可计算问题都能计算,允许无限制循环等,而不完备是限制循环等。相比较而言图灵完备语言是灵活的,但安全性要比不完备的低一些
DGideas
2020-04-17 15:25:14 +08:00
@ConradG 这样确实实现了图灵机的状态转移表,但是并没有循环控制流的概念

可以用其他语言的实现读取 JSON 和 YAML 文件,但 JSON 和 YAML 等配置文件 *本身* 并不图灵完备。
ipwx
2020-04-17 15:26:42 +08:00
Python (狗头
shawndev
2020-04-17 16:05:34 +08:00
ruby, groovy?
ConradG
2020-04-17 16:36:43 +08:00
@DGideas 抖机灵的回答被认真了([:doge]保命)
不过较真一下,如果已经有了“状态转移表”,那么“循环控制流”是不必要的。
xcstream
2020-04-17 16:56:22 +08:00
有 for 循环的基本可以
hst001
2020-04-17 17:00:28 +08:00
Believer
2020-04-17 21:20:02 +08:00
emacs-lisp
secondwtq
2020-04-17 21:58:22 +08:00
这个问题很有意思,因为我前两个月看到了 #18 提到的 Dhall 的作者的一篇博客:
http://www.haskellforall.com/2020/01/why-dhall-advertises-absence-of-turing.html

可能是作者说话太客气了,我没太看懂他究竟要表达什么意思。他列了两点“为什么‘配置语言’应该是非图灵完全的“的原因:第一点是非图灵完全”imply“了一些安全特性,第二点是很多人认为配置语言就应该是非图灵完全的。
虽然尽管我仔细阅读之后认为作者的意思是“非图灵安全对于配置语言是可欲的”(尤其考虑到作者自己就是一个非图灵安全的配置语言的作者之后),我反而认为这篇文章恰好能完美地说明“为什么非图灵完全的配置语言是个骗局”——因为作者列举的这两点理由就挺萌的没有一点是和“非图灵完全”这一特性有直接关系的!

我先亮我的屁股:我个人支持配置语言图灵完全,支持配置语言越做越复杂(或者至少是比现在主流的更加复杂),甚至支持直接使用合适的通用编程语言作为配置语言来使用。这和我的背景,以及由此产生的对软件可定制性的追求有关,见 https://www.v2ex.com/t/647806#r_8619946 https://v2ex.com/t/627912#r_8326554 等回复

然后把文章作者的事实陈述掺上我自己的价值判断炒两下:
“图灵完全”之所以在配置语言上成了个问题,主要是因为有那么一拨人更看重配置语言的“安全”“稳定”和“可控”,偏偏又是这么一拨人中有那么一部分人,根本对“图灵完全”是什么林檎东西都没有概念,然后用“非图灵完全”当作“简单”“安全”的 umbrella term (这要部分归功于 PL 教育的失败和应用的落后),然后搞得很多人都开始 dssq (毕竟大多数人是不会思考的),就成了现在这个德行。

在这篇文章中,作者以 Ackermann Function 举例,说明了“非图灵完全”的特性并不能帮你控制程序的运行时间和资源占用(或者说是个“理论意义”和“实际意义”的问题,再往下就要扯到 王垠 vs. 赵海平 了 ...),然后说“非图灵完全”一般 imply 了几个其他的特性所以大家喜欢——虽然这些特性在图灵完全的语言中也都可以实现。后面实际是把类似的东西又重复了一遍,只不过更强调大家喜欢的是“图灵完全”这个词的色彩而不是这个特性本身——换句话说就是“一群没开化只会跟风的猴子”。然后在评论中作者又把非图灵完全可能带来的静态分析方面的好处给 invalidate 了。总结:非图灵完全的配置语言是个骗局 Q.E.D.

哦对了在这个 Reddit thread 里面 https://old.reddit.com/r/programming/comments/f0odmw/why_dhall_advertises_the_absence_of,作者( u/Tekmo )有部分解释了他的动机:"not to defend improper use of terminology" ... "problem with imprecise terminology" ... "it is that misuse of the term 'Turing complete' is an unfortunate reality that I have to deal with when promoting the language" (Dhall)

然后回到楼主的问题,楼主重点强调了“配置语言”,但是回复已经很明显了——所谓的“配置语言”和其他语言之间并不存在明显的分界线——INI 可能是最简单的,再往上是 JSON,还有 UNIX 一些软件的 config,然后 YAML,XML,Lua,LISP,Python 。这个列表里面,如 #4 所引用的,"Data Description Language" 和图灵完备的编程语言之间形成了一条明显的分界线(虽然这和“图灵完备”并没有什么林檎关系,只是能用的编程语言一般都是图灵完备的),但是如果把 Dhall 这种加进去,就成了一个连续的光谱了。所以不如就把这个滑坡放在那不管,转而尝试区分“适合用于配置的语言”和“不适合用于配置的语言”——当然这个依然是非常主观的 ...

另一方面,可以从语言的设计目的来区分,但是十分不幸的是,常用的“配置语言” JSON 和 XML 都不是专门为了“配置”设计的,YAML 更像但是我不熟悉不太好说,这些只是在相关场景下最常被使用而已(或者说没有更好的替代品 ...),只有 Dhall 旗帜鲜明地打出了“configuration language” ...

我的结论是,楼主的“配置语言”这个概念,也是个骗局。图灵完全的语言一大堆,看谁顺眼爱用啥用啥


更有意义的讨论方向也许是,“图灵完全的配置语言”(或者说图灵完全的,你主观认为适合用于配置的语言)“应该”是什么样子。比如限制或禁止副作用,允许对递归做出限制等等。
当然我更倾向于把这些做成一个通用编程语言的库 ...
DGideas
2020-04-17 22:34:23 +08:00
@ConradG 哈哈哈,你说得对,转移表就能实现循环逻辑了!
encro
2020-04-18 09:32:37 +08:00
配置语言我认为需要具备 2 个特点:
1,容易被其他语言解析;
2,容易学习,从来没学个这个配置的人,看一眼想当然能明白一部分,稍微看下文档就能掌握大部分。

以上,要求配置语言必须简单。
这也是 ini, toml, xml, json, yaml 能流行的原因。


nginx 的配置文件大概能符合楼主要求?
具备变量和条件控制,好像没有循环?
vevlins
2020-04-18 13:00:08 +08:00
补充一下背景,我是一个前端工程师,经常维护一些逻辑非常复杂的表单,尝试过抽组件,也了解过 json-schema 配置表单,但根本无法覆盖复杂的逻辑。比如一个表单中会有验证,会有联动,会有远程校验,还会在联动后更改验证规则。所以我从 json-schema 的角度出发,想问问有没有其他图灵完备的配置语言可能实现复杂表单的配置。

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

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

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

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

© 2021 V2EX