V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
vevlins
V2EX  ›  程序员

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

  •  
  •   vevlins · 2020-04-17 10:43:30 +08:00 · 6375 次点击
    这是一个创建于 1668 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    37 条回复    2020-04-18 13:00:08 +08:00
    aliipay
        1
    aliipay  
       2020-04-17 10:48:55 +08:00
    lua [:doge]
    murmur
        2
    murmur  
       2020-04-17 10:49:47 +08:00
    gradle 算么
    runze
        3
    runze  
       2020-04-17 10:52:43 +08:00
    jsonnet 、xml(xslt)
    或者你可以用图灵完备的语言来当作配置,比如 js 、lua
    DGideas
        4
    DGideas  
       2020-04-17 10:58:00 +08:00   ❤️ 5
    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
        5
    DGideas  
       2020-04-17 10:58:23 +08:00
    不过可以考虑一下 Makefile
    wangyzj
        6
    wangyzj  
       2020-04-17 11:01:56 +08:00
    图灵完备
    新知识
    gkiwi
        7
    gkiwi  
       2020-04-17 11:05:45 +08:00
    求个图灵完备的一句话清晰解释,总感觉印象模糊。
    cmdOptionKana
        8
    cmdOptionKana  
       2020-04-17 11:06:47 +08:00   ❤️ 1
    我猜你想要的不是配置语言,而是插件语言,比如用于 vim 的 vimscript, 用于 emacs 的 elisp 等。
    cmdOptionKana
        9
    cmdOptionKana  
       2020-04-17 11:08:54 +08:00
    一般有这种需求的,lua 是一个很好的选择,因为它容易内嵌,体积小。
    Cbdy
        10
    Cbdy  
       2020-04-17 11:17:15 +08:00 via Android
    groogy
    hahaayaoyaoyao
        11
    hahaayaoyaoyao  
       2020-04-17 11:22:01 +08:00
    @gkiwi 我的理解是自我无性生殖
    fanhed
        12
    fanhed  
       2020-04-17 11:28:09 +08:00
    我觉得楼主的需求还是用一个预处理来解决吧, 预处理生成配置文件, 然后再被读入
    ConradG
        13
    ConradG  
       2020-04-17 11:31:56 +08:00
    Json 和 Yaml 就是图灵完备的啊,你把每一项看成一个状态,每个子项看成下一个状态不就行了[:doge]
    InkStone
        14
    InkStone  
       2020-04-17 11:33:37 +08:00
    @gkiwi 不那么精确地讲,能模拟 brainfuck 的语言就是图灵完备的。
    otakustay
        15
    otakustay  
       2020-04-17 11:36:58 +08:00   ❤️ 1
    我感觉 CSS 快要图灵完备了呢
    DGideas
        16
    DGideas  
       2020-04-17 11:49:20 +08:00   ❤️ 4
    @gkiwi 我们称某编程语言是图灵完备的,旨在表示它能完成等价于通用图灵机的工作,即考虑以下四点:
    (a). 具有能够等价于移动图灵机纸带的能力:比如编程语言提供的重复控制流,如 while 、if ... goto 等。
    (b). 具有能够等价于读写图灵机纸带内容的能力:拥有变量机制,能够读写(任意的)变量,拥有能够“引用”其他变量的能力(比如引用或指针)。
    (c). 具有模仿有限状态机的能力:能够表示有限个状态以及在这些状态之间的转移和动作等行为。
    (d). 具有停机状态:程序应当能在有限步骤后结束运行。

    本回答参考了 user3067516 在 Software Engineering Stack Exchange 上的回答: https://softwareengineering.stackexchange.com/a/305248/363321
    btnokami
        17
    btnokami  
       2020-04-17 11:56:33 +08:00
    groovy 。。。
    krjt
        18
    krjt  
       2020-04-17 11:58:09 +08:00   ❤️ 1
    感觉最接近的可能是 Dhall: https://dhall-lang.org/
    虽然不是 Turing-complete 但是足够 programmable 。
    ljwrer
        19
    ljwrer  
       2020-04-17 11:58:10 +08:00
    sass
    gaoryrt
        20
    gaoryrt  
       2020-04-17 12:25:44 +08:00
    然后应该有人来科普一下哥德尔不完备定理
    learningman
        21
    learningman  
       2020-04-17 12:31:58 +08:00
    @gkiwi 可以写自己的编译器
    DGideas
        22
    DGideas  
       2020-04-17 13:04:53 +08:00
    @learningman 不准确,这叫自举( BootStrap )
    SoloCompany
        23
    SoloCompany  
       2020-04-17 13:39:21 +08:00 via iPhone
    kotlin dsl
    js
    mightofcode
        24
    mightofcode  
       2020-04-17 15:16:17 +08:00
    图灵完备的不适合做配置语言
    TangMonk
        25
    TangMonk  
       2020-04-17 15:16:55 +08:00
    ruby 的 dsl 算么
    purensong
        26
    purensong  
       2020-04-17 15:21:23 +08:00
    图灵完备是相对不完备而言的,图灵完备是一切可计算问题都能计算,允许无限制循环等,而不完备是限制循环等。相比较而言图灵完备语言是灵活的,但安全性要比不完备的低一些
    DGideas
        27
    DGideas  
       2020-04-17 15:25:14 +08:00
    @ConradG 这样确实实现了图灵机的状态转移表,但是并没有循环控制流的概念

    可以用其他语言的实现读取 JSON 和 YAML 文件,但 JSON 和 YAML 等配置文件 *本身* 并不图灵完备。
    ipwx
        28
    ipwx  
       2020-04-17 15:26:42 +08:00
    Python (狗头
    shawndev
        29
    shawndev  
       2020-04-17 16:05:34 +08:00
    ruby, groovy?
    ConradG
        30
    ConradG  
       2020-04-17 16:36:43 +08:00
    @DGideas 抖机灵的回答被认真了([:doge]保命)
    不过较真一下,如果已经有了“状态转移表”,那么“循环控制流”是不必要的。
    xcstream
        31
    xcstream  
       2020-04-17 16:56:22 +08:00
    有 for 循环的基本可以
    hst001
        32
    hst001  
       2020-04-17 17:00:28 +08:00
    Believer
        33
    Believer  
       2020-04-17 21:20:02 +08:00
    emacs-lisp
    secondwtq
        34
    secondwtq  
       2020-04-17 21:58:22 +08:00   ❤️ 3
    这个问题很有意思,因为我前两个月看到了 #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
        35
    DGideas  
       2020-04-17 22:34:23 +08:00
    @ConradG 哈哈哈,你说得对,转移表就能实现循环逻辑了!
    encro
        36
    encro  
       2020-04-18 09:32:37 +08:00
    配置语言我认为需要具备 2 个特点:
    1,容易被其他语言解析;
    2,容易学习,从来没学个这个配置的人,看一眼想当然能明白一部分,稍微看下文档就能掌握大部分。

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


    nginx 的配置文件大概能符合楼主要求?
    具备变量和条件控制,好像没有循环?
    vevlins
        37
    vevlins  
    OP
       2020-04-18 13:00:08 +08:00
    补充一下背景,我是一个前端工程师,经常维护一些逻辑非常复杂的表单,尝试过抽组件,也了解过 json-schema 配置表单,但根本无法覆盖复杂的逻辑。比如一个表单中会有验证,会有联动,会有远程校验,还会在联动后更改验证规则。所以我从 json-schema 的角度出发,想问问有没有其他图灵完备的配置语言可能实现复杂表单的配置。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2629 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 05:29 · PVG 13:29 · LAX 21:29 · JFK 00:29
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.