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

[vevlins]

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

[aliipay]

lua [:doge]

[murmur]

gradle 算么

[runze]

jsonnet 、xml(xslt)
或者你可以用图灵完备的语言来当作配置，比如 js 、lua

[DGideas]

The notion of Turing completeness does not apply to languages such as XML, HTML, JSON, YAML and S-expressions, because they are typically used to represent structured data, not describe computation. These are sometimes referred to as markup languages, or more properly as "container languages" or "data description languages".

[DGideas]

不过可以考虑一下 Makefile

[wangyzj]

图灵完备
新知识

[gkiwi]

求个图灵完备的一句话清晰解释，总感觉印象模糊。

[cmdOptionKana]

我猜你想要的不是配置语言，而是插件语言，比如用于 vim 的 vimscript, 用于 emacs 的 elisp 等。

[cmdOptionKana]

一般有这种需求的，lua 是一个很好的选择，因为它容易内嵌，体积小。

[Cbdy]

groogy

[hahaayaoyaoyao]

@gkiwi 我的理解是自我无性生殖

[fanhed]

我觉得楼主的需求还是用一个预处理来解决吧, 预处理生成配置文件, 然后再被读入

[ConradG]

Json 和 Yaml 就是图灵完备的啊，你把每一项看成一个状态，每个子项看成下一个状态不就行了[:doge]

[InkStone]

@gkiwi 不那么精确地讲，能模拟 brainfuck 的语言就是图灵完备的。

[otakustay]

我感觉 CSS 快要图灵完备了呢

[DGideas]

@gkiwi 我们称某编程语言是图灵完备的，旨在表示它能完成等价于通用图灵机的工作，即考虑以下四点：
(a). 具有能够等价于移动图灵机纸带的能力：比如编程语言提供的重复控制流，如 while 、if ... goto 等。
(b). 具有能够等价于读写图灵机纸带内容的能力：拥有变量机制，能够读写（任意的）变量，拥有能够“引用”其他变量的能力（比如引用或指针）。
(c). 具有模仿有限状态机的能力：能够表示有限个状态以及在这些状态之间的转移和动作等行为。
(d). 具有停机状态：程序应当能在有限步骤后结束运行。

本回答参考了 user3067516 在 Software Engineering Stack Exchange 上的回答： https://softwareengineering.stackexchange.com/a/305248/363321

[btnokami]

groovy 。。。

[krjt]

感觉最接近的可能是 Dhall： https://dhall-lang.org/
虽然不是 Turing-complete 但是足够 programmable 。

[ljwrer]

sass

[gaoryrt]

然后应该有人来科普一下哥德尔不完备定理

[learningman]

@gkiwi 可以写自己的编译器

[DGideas]

@learningman 不准确，这叫自举（ BootStrap ）

[SoloCompany]

kotlin dsl
js

[mightofcode]

图灵完备的不适合做配置语言

[TangMonk]

ruby 的 dsl 算么

[purensong]

图灵完备是相对不完备而言的，图灵完备是一切可计算问题都能计算，允许无限制循环等，而不完备是限制循环等。相比较而言图灵完备语言是灵活的，但安全性要比不完备的低一些

[DGideas]

@ConradG 这样确实实现了图灵机的状态转移表，但是并没有循环控制流的概念

可以用其他语言的实现读取 JSON 和 YAML 文件，但 JSON 和 YAML 等配置文件 *本身* 并不图灵完备。

[ipwx]

Python （狗头

[shawndev]

ruby, groovy?

[ConradG]

@DGideas 抖机灵的回答被认真了（[:doge]保命）
不过较真一下，如果已经有了“状态转移表”，那么“循环控制流”是不必要的。

[xcstream]

有 for 循环的基本可以

[hst001]

lisp

参考这篇博客 https://blog.codingnow.com/2017/07/paradox_data_format.html

[Believer]

emacs-lisp

[secondwtq]

这个问题很有意思，因为我前两个月看到了 #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]

@ConradG 哈哈哈，你说得对，转移表就能实现循环逻辑了！

[encro]

配置语言我认为需要具备 2 个特点：
1，容易被其他语言解析；
2，容易学习，从来没学个这个配置的人，看一眼想当然能明白一部分，稍微看下文档就能掌握大部分。

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


nginx 的配置文件大概能符合楼主要求？
具备变量和条件控制，好像没有循环？

[vevlins]

补充一下背景，我是一个前端工程师，经常维护一些逻辑非常复杂的表单，尝试过抽组件，也了解过 json-schema 配置表单，但根本无法覆盖复杂的逻辑。比如一个表单中会有验证，会有联动，会有远程校验，还会在联动后更改验证规则。所以我从 json-schema 的角度出发，想问问有没有其他图灵完备的配置语言可能实现复杂表单的配置。