CSS图灵完成?

就我所知,CSS并不是Turing完成的。 但是我对CSS的知识是非常有限的。

  • CSS图灵完成?
  • 现在的草案或委员会是否考虑了可能使图灵完整性的语言特征,如果它不是现在呢?

您可以在CSS3中对规则110进行编码,所以只要您认为合适的伴随HTML文件和用户交互作为CSS的“执行”的一部分就是图灵完成的。 一个很好的实现是可用的,另一个实现包括在这里( JsFiddle版本 ):

<!DOCTYPE html> <html lang="en"> <head> <meta http-equiv="Content-Type" content="text/html; charset=utf-8"> <title>Rule 110</title> <style type="text/css" media="screen"> body { -webkit-animation: bugfix infinite 1s; font-family: "Courier New"; font-size: 28px; } @-webkit-keyframes bugfix { from { padding: 0; } to { padding: 0; } } /* 111 110 101 100 011 010 001 000 0 1 1 0 1 1 1 0 */ body > input { -webkit-appearance: none; display: block; float: left; border-right: 1px solid #ddd; border-bottom: 1px solid #ddd; padding: 5px 12px; margin: 0; } body > input::before { content: "0"; } body > input:nth-of-type(-n+30) { border-top: 1px solid #ddd; } body > input:nth-of-type(30n+1) { border-left: 1px solid #ddd; clear: left; } body > input::before { content: "0"; } body > input:checked::before { content: "1"; } body > input:checked { background: #afa !important; } input:not(:checked) + *+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+ input::before { content: "1"; } input:not(:checked) + *+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+ input { background: #fa0; } input:checked + *+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+ input::before { content: "1"; } input:checked + *+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+ input { background: #fa0; } input:checked + *+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+ input::before { content: "1"; } input:checked + *+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+ input { background: #fa0; } input:checked + input:checked + input:checked + *+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+ input::before { content: "0"; } input:checked + input:checked + input:checked + *+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+ input { background: #fff; } input:not(:checked) + input:not(:checked) + input:not(:checked) + *+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+ input::before { content: "0"; } input:not(:checked) + input:not(:checked) + input:not(:checked) + *+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+ input { background: #fff; } body > input:nth-child(30n) { display: none !important; } body > input:nth-child(30n) + label { display: none !important; } </style> </head> <body> <input type="checkbox" /> <input type="checkbox" /> /* A total of 900 checkboxes required */ <input type="checkbox" /> <input type="checkbox" /> </body> </html> 

图灵完备性的一个方面就是它的停止问题是不可判定的

这意味着没有通用的algorithm来确定一个CSS程序是否会完成运行或永远循环。

但是我们可以推导出这样的CSSalgorithm! 这里是:

  • 如果样式表没有声明任何animation ,则会停止。

  • 如果它有animation,那么:

    • 如果任何animation-iteration-countinfinite ,并且包含的​​select符在HTML中匹配,那么它不会停止。

    • 否则,它将停止。

而已。 由于我们只是表明停止问题是CSS可判定的,因此CSS 不是图灵完成的

(其他人提到IE6,它允许在CSS中embedded任意的JavaScriptexpression式,这显然会增加图灵的完整性,但是这个function是非标准的,没有人正确地使用它)。


丹尼尔·瓦格纳(Daniel Wagner)提出了一个我原来的错误答案。 他指出,虽然我已经介绍了animation ,但引擎的其他部分(如select器匹配布局)也可能导致图灵的完整性。 虽然很难就这些问题进行正式的争论,但我会试图概述为什么图灵完备性不太可能发生。

首先:图灵完整的语言有一些方法可以将数据反馈回自己 ,无论是通过recursion还是循环。 但是CSS语言的devise却反对这种反馈:

  • @media查询只能检查浏览器本身的属性,如视口大小或像素分辨率。 这些属性可以通过用户交互或JavaScript代码(例如,调整浏览器窗口大小)来改变,但不能通过CSS来改变。

  • ::before::after伪元素不被认为是DOM的一部分 ,并且不能以任何其他方式进行匹配。

  • select器组合器只能检查当前元素之上之前的元素,因此不能用于创build依赖性循环。

  • 将鼠标hover在其上时可以将元素移开 ,但只有在移动鼠标时位置才会更新。

这应该足以说服你, select器匹配本身不可能是图灵完整的 。 但是布局呢?

现代的CSS布局algorithm非常复杂,如Flexbox和Gridfunction混淆了水域。 但即使可能触发布局的无限循环,也很难利用它来执行有用的计算。 这是因为CSSselect器只检查DOM的内部结构,而不检查这些元素在屏幕上的布局。 所以使用布局系统的任何图灵完备性certificate都必须依赖布局

最后 – 这也许是最重要的原因 – 浏览器供应商有兴趣让CSS保持完整 。 通过限制语言,供应商可以进行巧妙的优化 ,使networking更快速。 而且,Google专门为整个服务器场寻找Chrome中的错误。 如果有办法用CSS编写无限循环,那么他们可能已经发现它了

根据这篇文章,它不是 。 文章还认为,把它做成一个不是一个好主意。

引用其中一条评论:

所以,我不相信CSS是完整的。 没有能力在CSS中定义一个函数。 为了使系统变成完整的,必须编写一个解释器:一个解释表示程序执行的expression式的函数。 CSS没有可供用户直接访问的variables; 所以你甚至不能模拟代表要在CSS中解释的程序的结构。

图灵完备性不仅关乎“定义function”或“具有ifs / loop / etc”。 例如,Haskell没有“循环”,lambda-calculus没有“ifs”等。

例如,这个网站: http : //experthuman.com/programming-with-nothing 。 作者使用Ruby,并创build一个“FizzBu​​zz”程序只有closures(没有string,数字,或类似的东西)…

有些例子是人们仅仅使用types系统在Scala上计算一些算术函数

所以,是的,在我看来,CSS3 + HTML是turing-complete(即使你不能完全做任何真正的计算,而不会变得疯狂)

这里的基本问题是,任何用HTML + CSS编写的机器都不能计算无限多的步骤(也就是说,除非代码是无限长的,否则不可能有“真正的”recursion)。 而且如果n是有限的,那么这个机器在n步或更less的时候达到configurationH总是可以回答的。

CSS不是一种编程语言,因此图灵完备性的问题是没有意义的。 如果将编程扩展添加到CSS中(例如IE6中的情况),那么这个新的综合是一个完全不同的东西。

CSS只是对风格的描述; 它没有任何逻辑,其结构是平坦的。