第六章：尝试用极小的语言写程序

[murphywuwu]

在2~5章，我们已经讨论了几个熟悉的计算机示例：命令示编程语言、状态机，以及通用计算机。那些示例向我们展示了计算差不多就是使用一个系统操作信息并回答问题的过程。在第二部分我们将会大胆一些，先在不熟悉的地方寻求计算，最后探索关于计算机器所做之事的根本限制。

• [ ] 6.1 模拟lambda演算
  • [ ] 6.1.1 使用proc工作
  • [ ] 6.1.2 问题
  • [ ] 6.1.3 数字

[murphywuwu]

使用proc工作

管道

proc是值在程序中移动的管道

proc只是把一部分程序连接在一起并让值流向需要它的地方。

参数

proc可以带多个参数

我们总是可以将其重写为嵌入式的单参数proc

这叫做curry化，并且我们可以使用Proc#curry自动进行这个转换

等价

查明一个proc的内部代码的唯一途径就是调用它，因此如果使用同样的参数调用两个proc，会产生相同结果的话，那么即使它们的内部代码不同，它们也是可交换的。

p = -> n { n * 2 }

q = -> x { p.call(x) }

知道 p与-> x { p. call( x) }等价，这就为重构提供了新的机会。如果在我们的程序里看到-> x { p. call( x)}这种一般模式，我们可以选择用 p替换整个表达式来消除它

[murphywuwu]

问题

FizzBuzz程序： 写一个程序输出数字1到100。但如果数字是3的倍数，就不输出数字而是输出'Fizz'，如果是5的倍数就输出'Buzz'。对于那些3和5的公倍数，就输出'FizzBuzz'

(1..100).each do |n|
  if (n % 15).zero?
    puts 'FizzBuzz'
  elsif (n % 3).zero?
    puts 'Fizz'
  elsif (n % 5).zero?
    puts 'Buzz'
  else
    puts n.to_s
  end
end

[murphywuwu]

数字

我们准备从关注FizzBuzz中出现的数字开始。怎么才能不用Fixnum或者Ruby提供的任何其他数据类型，就表示出数字呢？

描绘数字特征的一种方式是某个动作的重复(或者叫做迭代)。

每一个数字都与重复一个动作的唯一方式对应：数字1对应的是只执行这个动作；数字2对应的是执行这个动作然后再次执行；以此类推。所以，数字0，也就对着根本不执行这个动作。

既然创建和调用proc是这里程序唯一可以执行的“动作”，我们可以尝试用代码实现一个数字n，在代码里对调用proc这个动作重复n次。

例如，如果允许定义方法---这是不允许的，不过我们只是玩一玩

def one(proc, x)
  proc[x]
end

def two(proc, x)
  proc[proc[x]]
end

def three(proc, x)
  proc[proc[proc[x]]]
end

def zero(proc, x)
  x
end

[murphywuwu]

布尔值

我们怎样才能用proc表示布尔值呢？ 如上，一个布尔值的真正工作是允许在两个选项中做选择，因此我们可以利用这一点。我们不是把一个布尔值看成一段无生命的代码，它被将来的代码读取并能决定选择两个选项中的哪一个。而只是直接把它实现为一段代码，这段代码在用两个选项调用的时候，要么选择第一个，要么选择第二个

[murphywuwu]

IF

def if(proc, x, y)
 proc[x][y]
end

转换成一个proc

IF = 
  -> b {
    -> x {
      -> y {
        b[x][y]
      }
    }          
}

等价替换

-> y {
  b[x][y]
}

IF = -> b {
  -> x {
   b[x] 
  }
}

-> x {
  b[x]
}

IF = -> b { b }

[murphywuwu]

谓词

我们下一步的工作是用基于proc的实现替换Fixnum#zero，这个实现将会于基于proc的数字一起工作。

处理ruby值的#zero?的基本算法像下面这样

def zero?(n)
  if (n == 0)
    true
  else 
    false
  end
end

ZERO    = -> p { -> x {       x    } }
ONE     = -> p { -> x {     p[x]   } }
TWO     = -> p { -> x {   p[p[x]]  } }
THREE   = -> p { -> x { p[p[p[x]]] } }
....

ZERO是唯一不调用p的数字---它只是返回x---所有其他的数字至少会调用p一次。我们可以利用这一点： 如果用TRUE作为第二个参数调用一个未知的数字，则如果数字是ZERO，它将立即返回TRUE。如果不是ZERO, 它会返回p调用返回的东西，因此如果让p成功总是返回FALSE的proc, 就会得到想要的行为:

def zero?(proc)
  proc[-> x { false }][TRUE]
end

# 重写成proc
IS_ZERO = -> n { n[ -> x { FALSE  }][TRUE] }

[murphywuwu]

数值运算

递增 首先它会以p和x作为参数调用n——因为n是一个数字，所以这意味着就像原始数字那样，“在x上对p进行n次调用”——然后对结果再调用一次p。那么总体说来，这个 proc的第一个参数会在它的第二个参数上调用 n + 1次，这恰好是表示数字 n + 1的方法。

递减

我们可以把slide转成一个proc，使用数字n的proc表示对由ZERO组成的有序对调用SLIDE n次，然后使用LEFT从结果的有序对中拉出左边的数

[murphywuwu]

我们想要m+n，只需要'从m开始对其递增n次'，同样这也适用于减法；有了ADD之后，我们进行m*n，方法是'从ZERO开始，对其进行n次ADD m'，使用MULTIPLY和ONE进行幂运算类似

[murphywuwu]

def mod(m, n)
  if n <= m
    mod(m-n, n)
  else
    m
  end
end

[murphywuwu]

def mod(m, n)
  IF[IS_LESS_OR_EQUAL[m][n]][
    mod(SUBTRACT[m][n], n)
  ][m]
end

MOD = -> m {
       -> n {
        IF[IS_LESS_OR_EQUAL[n][m]][
          MOD[SUBTRACT[m][n]][n]
        ][m]
  }
}