在一个方法（被调用者）中如果想要获取调用者的绑定，最简单有效的方法自然是设置一个参数让调用者将其绑定传递过来。
def foo(binding)
eval("local_variables", binding)
end
bar = 1
p foo(binding) # => [:bar]
然而这种途径会使得每次调用方法都多出一个额外的参数，有时可能会使方法调用显得不太美观。这时，我们可以采用传递块的方式来实现相同的功能——让调用者在调用被调用者时附带一个空的块，并让被调用者将其转换为一个 Proc 对象，然后通过 Proc#binding 获取到调用者的绑定。当然，如果被调用者本身就需要一个块，自然就不用专门在调用时附带一个 dummy 的块了。
def foo(&block)
eval("local_variables", block.binding)
end
bar = 1
p foo {} # => [:bar]
可是这种方法仍然修改了调用方法的形式。难道在调用者不传递任何信息的情况下被调用者就无法获取调用者的绑定了吗？在 Ruby 语言层，似乎并没有现成的接口提供这样的功能，所以我们只能另辟蹊径。自行创建一个类似于调用栈的“绑定栈”来跟踪不同调用者的绑定就是一个可行的办法，虽然它带来了一定的开销。
class Binding
@@call_binding_stack = [ nil, TOPLEVEL_BINDING ]
class << self
def caller_binding
@@call_binding_stack[-2]
end
def push_caller_binding(binding)
@@call_binding_stack.push(binding)
end
def pop_caller_binding
@@call_binding_stack.pop
end
end
end
set_trace_func lambda { |event, file, line, id, binding, klass|
return if klass == Binding
case event
when 'call'
Binding.push_caller_binding(binding)
when 'return'
Binding.pop_caller_binding
end
}
def foo
eval("local_variables", Binding.caller_binding)
end
bar = 0
p foo # => [:bar]
Kernel#set_trace_func 可以让我们安装一个钩子，让解释器在所有方法被调用和返回时都回调我们的钩子过程，也就是这里的 lambda 闭包。方法调用时，我们就将当前的绑定压入绑定栈；方法返回时，我们就出栈。绑定栈初始时有两个元素，一个是 nil，这是因为顶层没有调用者；一个是 TOPLEVEL_BINDING，这是因为在顶层调用的方法，调用者自然是顶层本身。栈的顶部永远是当前（被调用者）的绑定，所以为了获取到调用者的绑定，我们需要返回顶部下面的第一个元素。
将对表达式的求值推迟到真正需要其值之时的行为被称为惰性求值。惰性求值在基于表的函数式语言（如 Haskell、Lisp 及其派生语言）中尤其有用，它使得在不产生死循环的情况下定义无限表成为了可能。
def i
5
end
def j
3
end
res = if true then i else j end
这是一段 Ruby 代码，最后一行是命令式语言中常见的一种惰性求值。此处，只有 i 和 j 的其中一个最终会被求值，而永远不会出现他们同时被求值的情况。然而，如果把最后一行替换为：
def fn(pred, u, v)
if pred then u else v end
end
res = fn true, i, j # => 5
那么，i 和 j 都会预先被求值，然后才传递给 fn。这被称为热情求值或及早求值。
在 Ruby 中，和大部分命令式语言一致的 if … then … else … 以及函数等结构都拥有惰性求值的特性，而同样是在语言层被支持的块、闭包、纤程和线程亦是如此。
这篇主题曾介绍过 Ruby 1.9 的纤程，其用到的例子程序中的纤程是一个生成 Fibonacci 序列的工人纤程。实际上，这个工人纤程就相当于基于表的函数式语言中的一个无限 Fibonacci 表，程序只在需要序列中某个 Fibonacci 数的时候才进行求值，否则生成一个无限表将会产生死循环，从而导致 OOM。
线程和纤程红花绿叶是一家，在惰性求值这一点上是没有差别的。
闭包则是一个有趣的实例——
fib = lambda do |n|
case n
when 1, 2
1
else
fib.call(n - 1) + fib.call(n - 2)
end
end
fib.call(6) # => 8
在 fib 还正在被定义的时候，竟然也可以引用 fib 来定义它本身。在数学中，这是很常见的递归定义，而惰性求值则使得这一数学技巧在程序语言的世界得到了完美的演绎。当然，同样的结构也可以由函数来完成，但 Ruby 的函数并非一级函数，并不能像 Proc 一样被当作闭包绑定到一个局部变量上。这使得这里的赋值语句尤为显眼，更能体现出惰性求值的特性。倘若这里不是闭包，而是用了如 a = a + 1 这样的语句，且 a 在之前又没有定义，那自然就会发生异常了。
布尔逻辑运算符的短路特性，有时也被称为惰性求值，因为它实际上也是 if … then … 结构。逻辑或运算时，如果对左边的运算元求值的结果是真，那么就不会继续求右边的运算元的值了。
与惰性求值相对的热情求值，在 Ruby 中也有很多实例。比如，Ruby 的所有字面值，都是被热情求值的。本主题 65 楼曾提到了正则表达式在词法分析时便已进行求值，那就是一种热情求值，其余字面值也均是在词法分析时就构建了相应的对象。另外一个比较明显的例子是字符串的内插求值：
$bar = :zhangsan
str = "#$bar"
$bar = :lisi
p str # => zhangsan
此处在字符串中内插了 $bar 这个变量，然而由于是热情求值，在字符串出现后才改变 $bar 的值，为时已晚。
一个最小二叉堆的 C++ 实现，底层采用了数组形式的 Vector 结构存放二叉树。add 添加元素到堆，shift 从堆顶部删除元素，peek 获取堆顶部元素。其中最重要的算法是 bubble-down，它把堆中放置位置过高的“重”（如果是最大堆，自然就是“轻”）物推到了合适位置。二叉堆再抽象一层，就可以用来实现优先队列。
#ifndef _BINARY_HEAP_H_
#define _BINARY_HEAP_H_
#include <vector>
template <typename T>
class BinaryHeap
{
public:
BinaryHeap()
{
}
BinaryHeap(const T& elem)
{
heap_.push_back(elem);
}
BinaryHeap(const std::vector<T>& elems)
{
heap_= elems;
for (int i = (heap_.size() - 1) / 2; i >= 0; --i)
bubbleDown(i);
}
virtual void insert(const T& elem)
{
int i = heap_.size();
heap_.resize(i + 1);
do {
/* Check heap_[i]'s parent. */
int j = (i - 1) / 2;
if (i <= 0 || elem >= heap_[j])
break;
heap_[i] = heap_[j];
i = j;
} while (true);
heap_[i] = elem;
}
virtual T shift(unsigned idx = 0)
{
if (heap_.size() <= idx)
throw "Heap is empty";
T ret = heap_[idx];
heap_[idx] = heap_.back();
heap_.pop_back();
bubbleDown(idx);
return ret;
}
virtual const T& peek() const
{
return heap_.front();
}
virtual BinaryHeap<T>& operator << (const T& elem)
{
insert(elem);
return *this;
}
virtual BinaryHeap<T>& operator >> (T& receiver)
{
receiver = shift();
return *this;
}
protected:
void bubbleDown(unsigned idx)
{
unsigned int max = idx;
do {
unsigned int i, j;
i = idx * 2 + 1;
j = i + 1;
/* Pick heap_[i]'s largest child. */
if (j < heap_.size() && heap_[j] < heap_[max])
max = j;
if (i < heap_.size() && heap_[i] < heap_[max])
max = i;
if (max == idx)
break;
/* Exchange heap_[i] and heap_[max_idx]. */
T tmp = heap_[idx];
heap_[idx] = heap_[max];
heap_[max] = tmp;
idx = max;
} while (true);
}
protected:
std::vector<T> heap_;
};
#endif /* _BINARY_HEAP_H_ */
同样的算法也用 Ruby 写了一份，但执行效率是有巨大差别的，特别是 Ruby 1.8。不过使用 Ruby 的好处是通过闭包可以方便地传递匿名比较函数，而在 C++ 中则需要传递函数指针，这个过程往往缺乏爱且伴随着痛苦。
class BinaryHeap
def initialize(*args, &cmptr)
@cmptr = cmptr
@heap = args.clone
i = (@heap.size - 1) >> 1
while i >= 0
bubble_down(i)
i -= 1
end
end
def insert(elem)
i = @heap.size
loop do
j = (i - 1) >> 1
if j < 0 || @cmptr.call(elem, @heap[j]) <= 0
@heap[i] = elem
break
else
@heap[i] = @heap[j]
i = j
end
end
self
end
def shift(idx = 0)
ret = @heap[idx]
len = @heap.size
if len > 1
@heap[idx] = @heap.pop
bubble_down(idx)
elsif 1 == len
@heap.clear
end
ret
end
def bubble_down(idx)
len = @heap.size
loop do
i = (idx << 1) + 1
j = i + 1
max = idx
max = j if j < len && @cmptr.call(@heap[j], @heap[max]) > 0
max = i if i < len && @cmptr.call(@heap[i], @heap[max]) > 0
if max != idx
@heap[idx],@heap[max] = @heap[max],@heap[idx]
idx = max
else
break
end
end
end
def to_s(indent = 8)
helper = lambda do |idx, acc|
if idx >= @heap.size then ''
else
child_base = idx << 1
helper.call(child_base + 2, acc + 1) +
' '*indent*acc + @heap[idx].to_s + "\n" +
helper.call(child_base + 1, acc + 1)
end
end
helper.call(0, 0)
end
def <<(elem)
add(elem)
end
end
DATA = 10
data = Array.new(DATA)
DATA.times do |i|
data[i] = rand(DATA<<1)
end
bh = BinaryHeap.new(*data) { |a, b| a <=> b }
print bh
bh << 1 << 3 << 0 << -3 << 0
print bh
bh.shift
print bh
bh.shift
print bh
第七水螰 