Question

这都是相当深奥的问题，因此在试图理解它们之前，我们先回顾一下计算领域的一些基本事实。其中一些事实很明显，而有一些没那么明显，但它们都是思考计算机的能力和限制的前提条件。

8.1.1　能执行算法的通用系统

通常说来，使用像图灵机、lambda 演算和部分递归函数这样的通用系统我们能干什么呢？

如果我们能恰当理解这些系统的能力，那就可以考察一下它们的限制。 计算机的实际目的就是执行算法。算法是一个指令列表，指令描述把一个输入值转成一个输出值的过程，但必须满足某些条件。

· 有限
指令的数量是有限的。

· 简单
指令要足够简单，一个人用一支笔和一张纸就能计算出结果。

· 终止
对于任何输入，一个遵守指令执行的人都会在有限步骤内终止。

· 正确
对于任何输入，一个遵守指令的人都将得到正确的答案。

例如，一个已知最古老的算法是欧几里得算法，这要追溯到公元前 300 年。它以两个正整数为参数，返回能恰好整除它们的最大整数——也就是它们的最大公约数。下面是它的指令。

1.给定两个数 x 和 y。

2.判断 x和 y 哪个数更大。

3.从大的数中减去小的数。（如果 x 更大，就从 x 中减去y，并把这个新值赋给x；反之亦然。）

4.重复步骤 2 和步骤 3，直到 x 和y 相等为止。

5.x 和 y 相等的时候，它们的值就是原来两个值的最大公约数。

我们很愿意承认这是一个算法，因为它看起来能满足基本的条件。它只包含有限的几条指令，而且都足够简单，对整个问题没有特别理解的人也可以使用铅笔和纸算出结果。再稍微思考一下，我们可以看出对于任意的输入它都一定能在有限步骤内结束：每重复一次步骤 3，两个数中的一个就会变小一些，因此它们最终一定会到达同样的值 1 并让算法结束。这个算法是否总是能给出正确的答案不是那么明显，但一些代数学的基础就足以证明所得到的结果必定是原始数字的最大公约数了。

1x 和 y 最小值可以是 1。

所以欧几里得算法确实是一个算法。但像任何算法一样，它只是表示为人类可读语言和符号的思想的集合。如果想要用它做一些有用的事情（或许我们想要探索它的数学性质，或者设计一台自动执行它的机器），我们就需要把算法转换成一个更严格的、歧义更少的形式，这才适合数学分析和机械执行。

我们已经有了一个计算模型用来做这件事情：可以尝试把欧几里得算法写成一台图灵机的规则手册，或者一个 lambda 演算的表达式，或者一个部分递归函数定义，但所有这些都涉及内部的处理以及其他一些枯燥的细节。我们暂时先把它转换成没有限制的 Ruby：2

2Ruby 已经内建了欧几里得算法 #Integer#gcd，但这不是重点。

def euclid(x, y)
  until x == y
    if x > y
      x = x - y
    else
      y = y - x
    end
  end

  x
end

本质上这个 #euclid 方法与欧几里得算法的自然语言描述版本有着同样的指令，但这次它们是用含义严格的定义方式（根据 Ruby 的操作语义）写的，因此可以由一台机器解释：

>> euclid(18, 12)
=> 6
>> euclid(867, 5309)
=> 1

在这个特定的情况下，很容易把一个非形式化的、人类可读的算法描述转换成对一台机器来说没有歧义的指令。拥有机器可读形式的欧几里得算法非常方便；现在我们无需手工劳动就可以快速可靠地反复执行这个算法了。

很明显我们还可以用与 6.1.7 节类似的技术把这个算法用 lambda 演算来实现，或者从 7.2 节的操作来构建一个部分递归函数，或者像 5.1.2 节那样通过简单算术运算实现一个图灵机的规则集合。

这提出了一个重要的问题：任何算法都能转换成适合一台机器执行的指令吗？表面上看，这个问题似乎不值一提——如何把欧几里得算法转换成一个程序相当明显。而作为程序员，我们有天然的倾向会把两者看成可互换的——但在一个计算系统中，一个算法抽象的、直觉的思想与具体的、逻辑上的实现是存在实质差别的。是否存在一个算法，它大、复杂而且不同寻常以致于其本质无法被一个没有思想的机械过程捕捉呢？

最终可能没有严谨的答案，因为这个问题是哲学层面的而非科学层面的。一个算法的指令一定要“简单”而且“不精巧”，以便它“能由一个人计算”，但这些对人类的直觉和能力来说都是不严密的，这并不是能用来证实或者推翻一个假设的数学化断言。

不管怎样，我们都可以通过提出大量算法并观察我们选择的计算系统（图灵机、lambda 演算、部分递归函数，或者 Ruby）是否能够实现它们来收集证据。数学家和计算机科学家差不多从 20 世纪 30 年代开始就已经在这么做了，但到目前为止还没有人成功设计出这些系统不能执行的算法。因此我们可以对经验上的直觉相当自信：一台机器肯定能执行任何 算法。

另一个比较强的证据是这些系统中大多数都是为了尝试捕捉和分析一个算法的非形式化思想而独立发展的，只是后来才被发现彼此之间恰好等价。每一次对算法思想的建模尝试都产生了一个系统，这个系统的能力与一台图灵机的能力等价，而这是对一台图灵机足够表示一个算法的很好暗示。

任何算法都能被一台机器（特别是一台确定型的图灵机）执行的思想叫作邱奇 - 图灵论题（Church–Turing thesis）。尽管这仅仅是一个猜想而不是一个被证明的事实，但有足够的证据让它成为广泛接受的真理。

“图灵机能执行任何算法”是个哲学层面的断言，说的是算法的直观感觉和用来实现算法的形式系统之间的关系。它实际的含义是一个解释的问题：我们可以把它看成关于什么能计算以及什么不能计算的命题，或者作为单词“算法”的更严格的一个定义。

不管怎样，它都叫“邱奇 - 图灵论题”，而不是“邱奇 - 图灵定理”。因为它是一个非形式化的断言而不是一个可证明的数学断言——它没法用纯数学化的语言表达，因此没有办法构建数学证明。因为它与我们对计算本质的直觉判断和算法能做事情的证据相符，所以被广泛认为是真的，但我们仍旧称它为“论题”，以便提醒自己它的状态与毕达哥拉斯定理这样的可证明思想不同。

邱奇 - 图灵论题表明，图灵机尽管简单，但拥有执行任何计算所需要的所有能力，而这些计算原则上可以由一个人按照简单的指令执行。许多人比这更进一步，他们认为，既然所有对算法编码的尝试都归结到了与图灵机能力等价的通用系统上，那也就不可能做得更好了：任何现实世界中的计算机或者编程语言只能做到与图灵机做的一样多的事，不能再多了。是否 最终有可能构建一台比图灵机更强大的机器——能使用外来的物理法则执行超越我们对“算法”想象的任务——现在还不能确切知道，但可以肯定的是我们现在不知道如何做。

8.1.2　能够替代图灵机的程序

就像我们在第 5 章中看到的那样，图灵机的简单性使得为一个特定任务设计一个规则手册非常困难。为了避免对可计算性的研究被图灵机编程烦琐的细节干扰，我们将使用 Ruby程序作为替身，就像处理欧几里得算法那样。

这个方法可行要归因于通用性：原则上，我们可以把任何的 Ruby 程序转换成一个等价的图灵机，反之亦然。因此一个 Ruby 程序与一台图灵机相比不多不少正好能力相当，从而我们发现的关于 Ruby 能力的任何限制都应该可以同样适用于图灵机。

一个明显的异议是 Ruby 有大量的实用函数，而图灵机没有。Ruby 程序可以访问文件系统、发送和接收网络上的消息、接受用户输入、在点阵式显示器上绘图，等等，然而即使最精致的图灵机规则集合也只能在一条纸带上读写。但那不是根本的问题，因为所有这些额外的函数都能用一台图灵机模拟：如果必要，我们可以把纸带的某些部分设计成用来表示“文件系统”或者“网络”或者“显示器”或者任何东西，并把对这些区域的读写处理得就像与外边的真实世界交流一样。这些增强没有一个能改变图灵机的潜在计算能力；它们只是提供了对纸带上活动的高层次的解释。

在实践中，我们可以完全把自己限制在简单的 Ruby 程序避免使用任何有争议的语言特性，以此来规避这个异议。本章的其余部分，我们写程序时将坚持从标准输入中读取，进行一些计算，然后等结束的时候把字符串写到标准输出；输入字符串与一台图灵机纸带的初始内容类似，而输出字符串类似最终的纸带内容。

8.1.3　代码即数据

程序有两种身份。除了把程序当作控制一个特定系统的指令之外，我们还把程序看成是纯数据：一个表达式树，一个原始字符串，或者甚至一个大的数。这种双重性通常会被程序员认为理所当然，但程序能够被表示成数据以便它们能用做提供给其他程序的输入，对通用计算机来说是至关重要的。正是代码和数据的统一才使得软件成为可能。

我们在通用图灵机的讨论中已经看到了作为数据的程序，它期望另一台图灵机的规则手册能作为字符序列写到它的纸带上。像 Lisp3 和 XSLT 这样奇特的同体异构编程语言（即程 序与数据由同样的结构存储），程序被显式地写成语言本身可以操纵的数据结构：每一个Lisp 程序是一个称为 s 表达式的嵌套列表，而每一个 XSLT 样式表是一个 XML 文档。

3Lisp实际上是一个编程语言的家族，包括Common Lisp、Scheme以及Clojure，它们有着非常类似的语法。

在 Ruby 当中，通常只有解释器（至少在 MRI 中不是用 Ruby 写的）才会关心程序的结构化表示，但把代码当作数据的原则仍然适用。考虑下面这个简单的 Ruby 程序：

puts 'hello world'

对于一个熟悉 Ruby 语法和语义的观察者来说，这是一个带上字符串'hello world' 把一个puts 消息发给 main 对象的程序，它的执行结果就是 Kernel#puts 方法把 hello world 进行标准输出。但在更低的层次上，它只是一个字符序列，并且因为字符是表示成字节的，所以最终这个序列可以看成是一个很大的数：

>> program = "puts 'hello world'"
=> "puts 'hello world'"
>> bytes_in_binary = program.bytes.map { |byte| byte.to_s(2).rjust(8, '0') }
=> ["01110000", "01110101", "01110100", "01110011", "00100000", "00100111",
  "01101000", "01100101", "01101100", "01101100", "01101111", "00100000",
  "01110111", "01101111", "01110010", "01101100", "01100100", "00100111"]
>> number = bytes_in_binary.join.to_i(2)
=> 9796543849500706521102980495717740021834791

从某种意义上说，puts 'hello world' 是 Ruby 程序数9796543849500706521102980495717740021834791。4 反过来说，如果某个人告诉我们一个 Ruby 程序的数字，我们很容易把它转换回程序并执行它：

4只把数字赋值给语法有效的 Ruby 程序会更有用，但那么做会更复杂。

>> number = 9796543849500706521102980495717740021834791
=> 9796543849500706521102980495717740021834791
>> bytes_in_binary = number.to_s(2).scan(/.+?(?=.{8}*\z)/)
=> ["1110000", "01110101", "01110100", "01110011", "00100000", "00100111",
  "01101000", "01100101", "01101100", "01101100", "01101111", "00100000",
  "01110111", "01101111", "01110010", "01101100", "01100100", "00100111"]
>> program = bytes_in_binary.map { |string| string.to_i(2).chr }.join
=> "puts 'hello world'"
>> eval program
hello world
=> nil

当然，把程序编码成大数是为了把它存储到硬盘上，把它联接互联网，以及把它提供给一个 Ruby 解释器（解释器本身在硬盘上也是一个大数字！），以便让一个特定的计算发生。

既然每一个 Ruby 程序都有一个独一无二的数，那么我们可以自动生成所有可能的程序：从数字 1 开始生成程序，然后生成程序 2，以此类推。5如果用足够长的时间做下去的话，将会最终产生下一个热门的异步 Web 开发框架，然后我们就可以退休颐养天年了。

5那些数字中的大多数都不表示语法有效的 Ruby 程序，但我们可以把每个潜在的程序提供给 Ruby 解析器，如果有任何的语法错误的话， 就丢弃掉它。

8.1.4　可以永远循环的通用系统

我们已经看到通用目的的计算机是通用的：可以设计一台能模拟其他任何图灵机的图灵机，或者写一个能对其他任何程序求值的程序。通用性是个强大的思想，这样不同的任务只用一台可改写的机器而不是很多专门机器就可以完成。但它也有不方便的地方：任何强大到足以通用的系统，都不可避免地允许我们构建永不停机一直循环的计算。

超长时间运行的计算

“我想要说的是，”计算机咆哮着，“我的电路现在已经无法撤销地开始计算生命、宇宙和一切终极问题的答案。”它缓了一下，对现在能引起所有人的注意感到很满意，于是降低了音量：“但程序运行要稍微花费我一点儿时间。”

福克不耐烦地瞥了一眼他的手表。

“要多久？”他问。

“750 万年。”深思回答说。

——道格拉斯·亚当斯，《银河系漫游指南》
（The Hitchhiker’s Guide to the Galaxy）

如果我们试图执行一个算法——目的是把输入转成输出的指令列表——那么永远循环就是一件坏事了。我们想要一台机器（或者程序）在有限时间内运行然后停机并给出某些输出，而不只是安静地在那儿变热。所有其他都相等的情况下，最好能有计算机和语言，它们的每个任务都保证在有限步骤内结束，这样我们就不必关心最终是否会有答案了。

但是在一些实际的应用中，永远循环是设计好的。例如，一个像 Apache 或者 Ngnix 这样的 Web 服务器如果只能接受一个 HTTP 请求，发送响应然后就退出的话，是没什么用的；我们想要它无限期运行下去，在强制停止前继续为每个到来的请求服务。但从概念上讲，我们可以把一个单线程的 Web 服务器分成两部分：一是处理单个请求的代码，它应该总是能停机，以便能发送响应，二是它的外边应该有一个无限循环，能随 着每个新请求的到来不断调用请求处理器。在这种情况下，即使封装器需要永远运行，在复杂的请求处理代码里无限循环仍然是一件坏事。

真实世界提供了很多程序的实例，它们在一个无限循环中反复执行停机计算：Web 服务器、GUI 应用、操作系统，等等。尽管我们通常想要算法的输入输出程序总能停机，但这些长时间运行的系统的类似目标是高效，也就是说总是“保持运行”并且永远都不要陷入无响应的状态。

那么为什么每个通用系统都把非终结作为属性呢？有没有什么天才的方法能限制图灵机以便它们总是能停机，而不必在它们的用处上做出妥协呢？怎么知道我们某一天不会设计出一种编程语言，它与 Ruby 一样强大但不包含无限循环呢？对于为什么它们无法做到有各种具体的例子，但还有一个更通用的论据，让我们演练一下。

Ruby 是一种通用编程语言，因此写一个能对 Ruby 代码求值的 Ruby 代码一定是可能的。原则上讲，我们可以定义一个叫 #evaluate 的方法，它的参数是一个 Ruby 程序的代码和一个标准输入提供给程序的字符串，然后对那个程序求值得到结果（也就是说，字符串会发给标准输出）。

在本章中包含进 #evaluate 的实现过于复杂了，但下面是对它最可能工作方式的概括：

def evaluate(program, input)
  # 解析程序
  # 在捕获输出的同时基于输入对程序求值
  # 返回输出
end

方法 #evaluate 本质上是一个 Ruby 写的 Ruby 解释器。尽管我们还没有对其实现，但写出它来是可能的：首先把程序转成一个符号序列，然后分析它们构建一个解析树（参见 4.3 节），再根据 Ruby 的操作语义（参见 2.3 节）对这个分析树求值。这是一个大而复杂的工作，但它肯定能完成；不然的话，Ruby 就不能满足通用性了。

为了简单，假设我们对 #evaluate 的假想实现是无 bug 的，在它对程序求值的时候不会崩溃。当然它可能会返回某个结果，这个结果表明这个程序在求值的过程中会引发异常，但那与 #evaluate 本身实际执行中的崩溃是不一样的。

Ruby 恰好有一个内建的 Kernel#eval 方法能对 Ruby 代码的字符串求值，但这里利用这个方法有点自欺欺人，特别是因为（在 MRI 中）它是用 C 语言实现的，而不是 Ruby。它对当前的讨论也没有必要；我们把 Ruby 当作任意通用编程语言的典型实例，但许多通用性语言没有内建的eval。

但是请注意，既然它摆在那儿，为了让 #evaluate 减少一点想象的成分，我们不去用它就太不好意思了。下面是一次粗略的尝试，请多包涵：

require 'stringio'
  def evaluate(program, input)
    old_stdin, old_stdout = $stdin, $stdout
    $stdin, $stdout = StringIO.new(input), (output = StringIO.new)

  begin
    eval program
  rescue Exception => e
    output.puts(e)
  ensure
    $stdin, $stdout = old_stdin, old_stdout
end
output.string

end

这个实现有许多现实和哲学上的问题，它们都能通过写纯 Ruby 的 #evaluate来避免。另一方面，从演示角度看，这个实现足够简短而且工作得足够好：

>> evaluate('print $stdin.read.reverse', 'hello world')
=> "dlrow olleh"

方法#evaluate的存在允许我们定义另一个方法：#evaluate_on_itself，它返回用它自己的源代码作为输入对程序求值的结果：

def evaluate_on_itself(program)
  evaluate(program, program)
end

这可能有点荒唐，但是完全合法；程序只是一个字符串，因此我们完全可以把它既当成一个 Ruby 程序又当成对这个程序的输入。代码即数据，对吧？

>> evaluate_on_itself('print $stdin.read.reverse')
=> "esrever.daer.nidts$ tnirp"

既然我们知道可以用 Ruby 实现 #evaluate 和 #evaluate_on_itself，因而就能写出完整的Ruby 程序does_it_say_no.rb：

def evaluate(program, input)
  # 解析程序
  # 在捕获输出的同时基于输入对程序求值
  # 返回输出
end

def evaluate_on_itself(program)
  evaluate(program, program)
end

program = $stdin.read

if evaluate_on_itself(program) == 'no'
  print 'yes'
else
  print 'no'
end

这个程序是对现有代码的一个直接应用：它定义了 #evaluate 和 #evaluate_on_itself，然后从标准输入中读取另一个 Ruby 程序，最后把它传给 #evaluate_on_itself。来看看它以自身作为输入的时候程序能干什么。如果输出的结果是字符串'no'，does_it_say_no.rb 会输出 'yes'，否则它会输出 'no'。例如：6

6我们这里使用的是 Unix shell 语法。在 Windows 平台上，要忽略 echo 参数周围的单引号，或者把文本放到文件里，并把它用 < 输入重定向符提供给 ruby。

$ echo 'print $stdin.read.reverse' | ruby does_it_say_no.rb
no

这是期望的结果；就像我们上面看到的，在用其自身运行print$stdin.read.reverse时，会得到输出esrever.daer.nidts$tnirp，它与 no 不相等。得到输入no 的程序会怎么样呢？

$ echo 'if $stdin.read.include?("no") then print "no" end' | ruby does_it_say_no.rb
yes

这次仍然与期望一致。

那么下面是大问题了：在运行 ruby does_it_say_no.rb < does_it_say_no.rb 时，会发生什么呢？ 7在脑子中要记住does_it_say_no.rb 是一个真实的程序——用足够的时间和热情可以完整写出来的一个程序——因此，它一定有结果，只是没那么显而易见。让我们试着通过考虑所有的可能然后去掉讲不通的来把它实现出来。

7这是一个 shell 命令，以它自身源代码作为输入运行 does_it_say_no.rb。

首先，以自身代码作为输入来运行这个特定程序不能产生输入 yes。根据程序自己的逻辑，输出 yes只能在对自身代码运行 does_it_say_no.rb 输出no 时才会发生，这与原来的承诺是冲突的。因此这样不行。

好吧，那么可以改为输出 no。但程序的结构意味着，只有同样的计算没有输出 no 它才能输出 no——又冲突了。

有可能输出一些其他字符串，比如 maybe，甚至空字符串吗？那可能还是会冲突：如果evaluate_on_itself(program,program) 没有返回 no 那程序还是会输出 no。

因此它不能输出 yes 或者 no，不能输出别的什么，并且除非方法 #evaluate 含有 bug，不然它不可能崩溃，但这个已经假定不会了。唯一的可能性是它不产生任何输出，而这只会在程序永不停止的时候才会发生：#evaluate 一定要永远循环，不返回结果。

实际上几乎可以确定 ruby does_it_say_no.rb < does_it_say_no.rb 将会耗尽主机的有限内存，引起 ruby 崩溃，而不会真的永远循环下去。但这是外部施加给程序的资源限制，而不是程序本身的属性；理论上讲，只要有需要我们可以持续给计算机增加更多的内存让计算机无限运行下去。用这么复杂的方式说明 Ruby 允许我们写不停机程序看起来是没有必要的。毕竟 while true do end 能让我们做相同的事，但它简单得多。

但通过思考 does_it_say_no.rb 的行为，我们已经展示了不管系统有什么特性，不停机程序是通用性的一个不可避免的结果。我们的观点除了依赖 Ruby 的通用性之外不依赖 Ruby 的任何特殊能力，因此同样的思想也可以适用于图灵机，或者 lambda 演算，或者任何其他的通用系统。只要在使用一种强大到能对自身求值的语言，我们就知道一定可能使用#evaluate 的等价物构建永不停机的程序，而不需要知道关于语言能力的任何其他东西。

特别地，在编程语言中移除特性（如 while 循环）并不能阻止我们在保持语言足以通用的同时还能写出不停机的程序来。如果移除了一个特性让一个程序无法永远循环，一定也不可能实现 #evaluate 了。

被仔细地设计以保证它们的程序一定总是能停机的语言叫作完全编程语言。与之相对的是更常见的部分编程语言，这样语言的程序有时候能停机给出答案，有时候不能。完全编程语言仍然非常强大，能表达许多有用的计算，但它们不能做到的就是解释自身。

这很奇怪，虽然对一种完全编程语言，从定义上来说 #evaluate 的等价物一定总是能停机的，但用那种语言是无法实现的——如果它可以实现的话，我们就能使用 does_it_say_no.rb 技术让它永远循环了。

这让我们对一个不可能的程序有了初步了解：无法用完全编程语言写一个对其自身的解释器，即使为了解释它存在一个令人尊敬的保证能停机的算法也不行。事实上，它是如此令人尊敬以至于我们能用另一种更复杂的完全编程语言写出来，但这个新的完全编程语言也不能实现它自己的解释器。

虽然是个有意思的东西，但完全编程语言的设计有人为的限制；我们一直在寻找所有计算机或者编程语言不能完成的东西。我们最好继续努力。

8.1.5　能引用自身的程序

doesitsayno.rb 使用的自引用的小技巧构建出一个能读自己源代码的程序，但或许假定总是会有点自欺欺人。在我们的例子里，程序收到了自己的源代码作为一个明确的输入，这要感谢环境（如 shell）提供的功能；要没有这个选择的话，它可能也会利用 Ruby 的文件系统 API 和总是包含当前文件名的` _FILE 常量，直接用File.read(__FILE)` 从硬盘读取数据。

但我们应该提出一个通用的论点，只依赖 Ruby 的通用性，而不是依赖操作系统或者 File 类的能力。像 Java 和 C 这样运行时没有权限访问自身源代码的编译语言呢？像 JavaScript 这样通过网络连接被加载到内存而且可能根本不会存储到本地文件系统的程序呢？像图灵机和 lambda 演算这样自包含的通用系统，它们根本没有“文件系统”和“标准输入”的概念，又会怎样呢？

幸运的是，does_it_say_no.rb 参数能经受住这些异议，因为让一个程序从标准输入读取它自己的源代码只不过是一个对所有通用系统都能完成的某个事情的为简化，而且与它们的环境和其他特性无关。这是一个叫作 Kleene 第二递归定理的推论（Kleene’s second recursion theorem），它保证了任何程序都可以转换成能计算自身源代码的等价物。递归理论提供了我们所做简化的合理保证：本可以把 program = $stdin.read 用一些代码替换，以便生成does_it_say_no.rb 的源代码并把它赋给程序而不必进行任何 I/O。

来看看如何在一个简单的 Ruby 程序上做这种转换。例如：

x = 1
y = 2
puts x + y

我们想要把它转换成类似这样的程序：

program = '...'
x = 1
y = 2
puts x + y

……这里程序被赋予了一个含有完整程序源代码的字符串。但程序的值应该是多少呢？

一个天真的做法是尝试编造一个能赋值给程序的简单字符串，但这很快就会让我们陷入麻烦，因为这个字符串将是程序源代码的一部分从而会出现在自身的某个地方。这会要求程序以字符串'program =' 开头，后边是程序的值，这个值还会是字符串'program ='，后边再跟着程序的值，这样一直类推下去：

program = %q{program = %q{program = %q{program = %q{program = %q{program = %q{...}}}}}}
x = 1
y = 2
puts x + y

Ruby 的 %q 语法允许我们使用一对定界符来引用不可修改的字符串，在这个场景下是花括号，而不是一对引号。优点是只要定界符能正确匹配，这个字符串就可以包含定界符的非转义实例：

> puts %q{Curly brackets look like { and }.}
Curly brackets look like { and }.
=> nil
> puts %q{An unbalanced curly bracket like } is a problem.}
SyntaxError: syntax error, unexpected tIDENTIFIER, expecting end-of-input

使用 %q 而不是单引号可以帮助我们避免令人头疼的包含自身定界符的字符串里的字符转义：

program = 'program = \'program = \\\'program = \\\\\\\'...\\\\\\\'\\\'\''

从这个“坑”里爬出来的方法是利用一个事实，那就是一个程序中用到的值没有必要出现在它的源代码里，还可以从其他数据动态计算出来。这意味着我们可以把转换的程序构建成三部分：

A. 把一个字符串赋值给一个变量（如 data）；
B. 使用字符串计算当前程序的源代码并将其赋值给 pragram；
C. 做程序应该做的所有其他工作（原来代码的工作）。

因此，程序的结构将会变成这样：

data = '...'
program = ...
x = 1
y = 2
puts x + y

这作为一个一般策略听起来貌似有理，但在具体的细节上还有些问题。我们怎么知道 A 部分中要赋值给 data 什么字符串，并且我们怎么用其在 B 部分中对pragram 进行计算呢？下面是一个解决方案。

· 在 A 部分中，创建一个包含 B 和 C 部分的字符串，并把这个字符串赋值给 data。这个字符串不应该“包含自身”，因为它不是整个程序的源代码，只包含 A 部分之后的部分程序。

· 在 B 部分中，首先计算一个含有 A 部分源代码的字符串。因为 A 部分通常含有一个值可用作 data 的大的字符串，所以我们可以这么做。因此只需要用 'data =' 给 data 的值加上前缀，以此来重建 A 部分的源代码。然后只是把这个结果与 data 连接起来得到整个程序的源代码（因为 data 含有 B 部分和 C 部分的源代码了）并将其赋值给程序。

这个设计仍然有些不够直接（A 部分产生 B 部分的源代码，而 B 部分产生 A 部分的源代码），但它通过保证 B 部分只计算 A 部分的源代码而不必把它包含进来，这刚好避免了无限的倒退。

先把已知的做出来吧。我们已经有了 B 和 C 部分的大部分源代码，因此可以部分地完成数据的值了：

data = %q{
program = ...
x = 1
y = 2
puts x + y
}
program = ...
x = 1
y = 2
puts x + y

data 需要换行符。通过在一个不可修改的字符串里把这些表示为现行的换行符，而不是表示成可修改的 \n 转义序列，我们就能把 B 和 C 部分的源代码逐字的包括进来，而不必进行任何特殊的编码的转义。8 这样直接的复制粘贴让 A 部分的源代码更容易计算。

8因为 B 和 C 部分恰好不包含任何如反斜杠或者不平衡花括号的字符，我们才能绕行成功。如果它们包含的话，我们就得想办法对它们转义然后作为汇编 pragram 值的一部分撤销掉转义。

我们还知道 A 部分的源代码只是字符串 'data = %q{...}'，再加上花括号中间填充好的data的值，因此还可以部分地完成 pragram 的值：

data = %q{
program = ...
x = 1
y = 2
puts x + y
}
program = "data = %q{#{data}}" + ...
x = 1
y = 2
puts x + y

现在所有 pragram 中缺失的就是 B 和 C 部分的源代码了，这恰好就是 data 包含的内容，因此我们可以把 data 的值添加到程序来完成任务：

data = %q{
program = ...
x = 1
y = 2
puts x + y
}
program = "data = %q{#{data}}" + data
x = 1
y = 2
puts x + y

最后，回头改进一下data 的值以反映 B 部分：

data = %q{
program = "data = %q{#{data}}" + data
x = 1
y = 2
puts x + y
}
program = "data = %q{#{data}}" + data
x = 1
y = 2
puts x + y

就是它了！这个程序和原来的作用一样，但现在它有了额外的含有自身代码的本地变量，可它实际上没用那个变量做任何事情。如果转换一个程序，它需要一个程序的本地变量，然后用它做点什么，那会怎么样呢？看下面这个经典的例子：

puts program

这是一个尝试输出它自己源代码的程序，9 但它明显会失败。因为 program 是一个未定义的变量。如果我们通过自引用的变换来运行它，可以得到如下结果：

9侯世达（Douglas Hofstadter）为输出自己的程序杜撰了名字奎因（quine）

data = %q{
program = "data = %q{#{data}}" + data
puts program
}
program = "data = %q{#{data}}" + data
puts program

有点意思了。让我们在控制台上看看这个代码能干什么：

>> data = %q{
  program = "data = %q{#{data}}" + data
  puts program
}
=> "\nprogram = \"data = %q{\#{data}}\" + data\nputs program\n"
>> program = "data = %q{#{data}}" + data
=> "data = %q{\nprogram = \"data = %q{\#{data}}\" + data\nputs program\n}\n
program = \"data = %q{\#{data}}\" + data\nputs program\n"
>> puts program
data = %q{
program = "data = %q{#{data}}" + data
puts program
}
program = "data = %q{#{data}}" + data
puts program
=> nil

可以确定了，puts program 实际上输出了整个程序的源代码。

很明显这个变换不依赖程序本身的任何特别的属性，因此对任何 Ruby 程序它都能工作，而且不必使用 $stdin.read 或者File.read(__FILE__) 读取程序自身的源代码。10 它也不依赖 Ruby 本身的任何特别属性——只需要像任何其他通用系统一样根据旧值计算新值的能 力——这意味着任何图灵机都能引用它自己的编码，任何 lambda 演算表达式都能扩展成含有表示它自身语法的 lambda 演算表达式，以此类推。

10是不是忍不住要写一个能对任意 Ruby 程序执行这个转换的 Ruby 程序了？如果使用 %q{[] 来引用数据的值，那你如何处理原始代码中的反斜杠和不平衡的大括号呢？