神奇的自产生程序

简介: 最近读到冯·诺依曼的《Theory of Self-Reproducing Automata》的中译本,被自复制自动机理论深深吸引了!

最近读到冯·诺依曼的《Theory of Self-Reproducing Automata》的中译本,被自复制自动机理论深深吸引了!

问题(自产生程序):编写一个程序,不读取任何输入,只把自己的源代码输出。

image.png

这个问题是个非常本质的问题,跟使用什么编程语言无关(不要想到使用反射之类的东西)。

试想,如果要输出自己的源代码,那么,显然,程序中应该有“print ...”语句。但 print 什么出来呢?如果硬要写的话就会变成:

print"print \\"print......\\""

最后是一个无限循环。

一般地,我们知道,如果程序 A 能产生程序 B ,那么 A 必须包含 B 的全部信息,而且应该比 B 的信息还多,因为还要包含额外的打印语句。也就是说,一般情况下,信息是减少的。而这个自产生程序,自己要包含自己的全部信息,从某种程度上已经具有生命的意味了。

下面列出一些自产生程序及其思路。

首先需要注意的是,使用编程语言本身的反射功能或者读取文件等做法都被视为 cheating ,比如这样的 bash 脚本:

#!/bin/sh

cat $0

或者像这样的 javascript :

functiona() { console.log(a.toString(), "a()"); } a()

因为这些程序没有体现出自产生程序的递归和自指特性,或者结果严重依赖于编程语言的具体实现。

不cheating的思路主要有以下几种:


输出源代码在该语言中的转义

Python :

s = "'s = ' + repr(s) + '\\nprint(' + s + ')'"

print('s = ' + repr(s) + '\nprint(' + s + ')')

Lua 5.1 :

s = "string.format('s = %q\\nprint(%s)', s, s)"

print(string.format('s = %q\nprint(%s)', s, s))

另一个 Lua 版:

s = "s = %q\

print(string.format(s, s))"

print(string.format(s, s))

Scala :

defe(s: String) = ("\""+s.replace("\\", "\\\\").replace("\"", "\\\"") +"\"")

vals="\"\"\"def e(s: String) = (\"\\\"\" + s.replace(\"\\\\\", \"\\\\\\\\\").replace(\"\\\"\", \"\\\\\\\"\") + \"\\\"\")\"\"\" + \"\\nval s = \" + e(s) + \"\\nprintln(\" + s + \")\""

println("""def e(s: String) = ("\""+s.replace("\\", "\\\\").replace("\"", "\\\"") +"\"")""" + "\nvals=" + e(s) + "\nprintln(" + s + ")")

用某种方法 encode 源代码,使之不包含引号,然后还原出源代码

Bash :

#!/bin/sh

s='\x22#!/bin/sh\ns=\x27$s\x27\necho $(echo -e $s)\x22'

echo"#!/bin/sh

s='$s'

echo $(echo -e $s)"

Lua 5.2 使用 load():

s = "a,q,b=string.char(39),string.char(34),string.char(92) return a..'s = '..q..a..'..s..'..a..q..b..'nprint('..a..'..load(s)()..'..a..')'..a"

print('s = "'..s..'"\nprint('..load(s)()..')')

Scala :

~~~~ {.hl}

val s = "%22val+s+%3D+%5C%22%22+%2B+s+%2B+%22%5C%22%5Cnprintln%28%22+%2B+java.net.URLDecoder.decode%28s%2C+%22UTF-8%22%29+%2B+%22%29%22"

println("val s = \"" + s + "\"\nprintln(" + java.net.URLDecoder.decode(s, "UTF-8") + ")")

~~~~

使用 eval :在 eval 的字符串中引用自己

-------------------------------------

Lua load() 的另一种用法:

```lua

s = "print(string.format('s = %q load(s)()', s))" load(s)()

js 的 eval()

s="q = String.fromCharCode(34); console.log('s = ' + q + s + q + '; eval(s)')"; eval(s)


使用语言中的更强的转义机制

类似上面的第二种,但不用引号。

Lua 的 long string :

x = [["x = [".."["..x.."]".."]\nprint("..x..")"]]

print("x = [".."["..x.."]".."]\nprint("..x..")")

Scala 的三引号:

val s = """"val s = \"\"\"" + s + "\"\"\"\nprintln(" + s + ")""""

println("val s = \"\"\"" + s + "\"\"\"\nprintln(" + s + ")")

使用 C 的宏

先执行传入的参数,再把参数变成字符串。

gcc :

#definep(a) int main(){a;puts("p("#a")");return 0;}

p(puts("#definep(a) int main(){a;puts(\"p(\"#a\")\");return 0;}"))

至于它们是怎么实现的,就留给读者自己琢磨了。自产生程序也称为 Quine ,可以参考 Quine Page

目录
打赏
0
0
0
0
91
分享
相关文章
人工智能平台PAI产品使用合集之在执行shade打包后遇到“类找不到”的错误,是什么原因
阿里云人工智能平台PAI是一个功能强大、易于使用的AI开发平台,旨在降低AI开发门槛,加速创新,助力企业和开发者高效构建、部署和管理人工智能应用。其中包含了一系列相互协同的产品与服务,共同构成一个完整的人工智能开发与应用生态系统。以下是对PAI产品使用合集的概述,涵盖数据处理、模型开发、训练加速、模型部署及管理等多个环节。
程序命名的原则与重构
命名是对事物本质的一种认知探索,是给读者一份宝贵的承诺。糟糕的命名会像迷雾,引领读者走进深渊;而好的命名会像灯塔,照亮读者前进的路。命名如此美妙,本文将一步步揭开它的神秘面纱!
程序命名的原则与重构
【单点知识】基于实例讲解PyTorch中的ImageFolder类
【单点知识】基于实例讲解PyTorch中的ImageFolder类
224 0
共识协议的技术变迁问题之能不能介绍下Share Log应用场景Pub/Sub
共识协议的技术变迁问题之能不能介绍下Share Log应用场景Pub/Sub
107 3
CocosCreator 面试题(十)Cocos Creator 内存管理
CocosCreator 面试题(十)Cocos Creator 内存管理
480 0
二叉树的创建和遍历
二叉树(Binary tree)是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式,即使是一般的树也能简单地转换为二叉树,而且二叉树的存储结构及其算法都较为简单,因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树,且有左右之分
106 0

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等