代码之家 › 专栏 › 技术社区 › DVK

Language features helpful for writing quines (self-printing programs)?

quine language-design programming-languages

2

DVK · 技术社区 · 14 年前

好吧,对于那些从未遇到过这个词的人来说, quine 是一个“自我复制”的计算机程序。更具体地说,一个在执行时生成自己的源代码的副本作为它的唯一输出。

当然,奎因可以用许多编程语言(但不是全部)来开发;但是有些语言显然比其他语言更适合生成奎因(为了清楚地理解一些主观的听起来“更适合”,请看 Haskell example vs. C example in the Wiki page -我在下面给出了更客观的定义)。

我的问题是, 从编程语言的角度来看,什么语言特性(理论设计特性或语法糖)使语言更适合/有助于编写奎因 ?

我对“更合适”的定义是“奎因更容易写”和“更短/更可读/更模糊”。但是,欢迎您添加更多至少在一定程度上客观的标准。

请注意,这个问题明确地排除了退化的情况,比如设计用来包含“print-a-quine”原语的语言。

3 回复 | 直到 14 年前

1

3

Gabriel Å Äerbák 14 年前

我不完全确定,所以如果你们中有人更了解我,请纠正我。我同意其他两个答案,进一步解释,奎因是:

γ-G

其中Y是 Y fixed-point combinator (或任何其他固定点组合器),这意味着 lambda calculus :

y g= g(y g)

现在,很明显,我们需要代码是数据,而g是一个将打印其参数的函数。

综上所述,我们需要构建这样一个奎因函数、打印函数、定点组合器和按名称调用的评估策略。

满足这一条件的最小语言是来自 Iota and Jot 家庭。

2

3

jer 14 年前

像这样的语言 Io Programming Language 还有一些允许将代码视为数据。在树遍历系统中,这通常允许语言实现者将抽象语法树作为第一类公民公开。在IO的情况下,这就是它所做的。AST是面向对象的,围绕消息对象建模,并创建一个特殊的sentinel来表示当前正在执行的消息;这个sentinel被调用 thisMessage . 此消息 是一个完整的消息,与其他任何消息一样,并响应 print 消息,将其打印到屏幕上。因此,我能用任何语言制作出的最短的奎因来自IO,看起来如下:

thisMessage print

不管怎样,我只是忍不住和你分享这个话题。以上当然可以使写奎因容易,但不这样做当然不排除容易创造奎因。

3

2

Tomas Petricek 14 年前

我不确定这是否是一个实用的答案,但有一些有用的理论 可计算性理论 . 尤其是固定点和 Kleene's recursion theorem 可以用来写奎因。显然,这个理论可以用来写Lisp中的奎因(如维基百科页面所示)。