Immutability The Dark Side

发布于 2024-01-04 03:12:56 字数 13775 浏览 16 评论 0

FPer 对 OO 批评最多的是：由于 OO 允许在运行时修改状态，从而无法做到引用透明（Referiential Transparency）。换句话说：对于同一个函数，使用相同的输入参数，每次调用返回的结果却不相同。比如：

struct Foo {
  int inc(int b) {
    a += b;
    return a;
  }
  private: int a = 1;
};
void f() {
  Foo foo;
  std::cout << foo.inc(2) << std::endl; // 3
  std::cout << foo.inc(2) << std::endl; // 5
}

但是，OO 社区的人对此却并不买账。认为对象的状态虽然允许修改，但其实并没有改变引用透明性。因为函数 Foo::inc 事实上有一个隐藏参数 this 。站在这个角度，两次调用的输入参数其实并不相同。反过来，对于状态完全相同的两个对象，如果其它输入参数也相同，其输出也必然相同。Nothing Different！

但是，在多线程模式下，如果两个线程同时持有同一个可修改状态的对象，那么程序运行结果将会处于不确定状态。除非像 FP 那样，将对象修改为不可变的，每次计算都产生一个新的对象来作为输出。比如：

struct Foo{
  Foo(int a) : a(a) {}
  Foo inc(int b) const{
    return a + b;
  }
  private: int a = 1;
};

这就是多线程模式下的 Shared Nothing 策略。

另外，对于支持惰性求值（Lazy Evaluation）的语言，不可变性（Immutability）是必须被保证的。因为在非严格（non-strict）、惰性求值的语言里，表达式都是按需求值（call-by-need）的。换句话说，对于任意两个表达式，其估值顺序很可能是不确定的。这就意味着，如果两个表达式持有同一个可修改状态的对象，那么计算结果也会随着求值顺序的变化而变化。这也丧失了引用透明性。

当然，并不是所有的 FP 语言都支持惰性求值。而惰性求值本身也是个充满争议的选择。因而，对于严格求值的语言，不可变性的价值就仅限于并行计算。

因而，OO 程序员的观点是：并行计算真正需要的是 Shared Nothing。而 Shared Nothing 有更为廉价的手段来满足。而不是只有代价高昂的不可变性这一种选择。

比如，多线程间可以全部通过消息来通信，同样可以达到线程间 Shared Nothing 的目的。同时线程内部允许修改状态，又能够避免不必要的性能损失。两全其美！

而这正是多核时代绝大多数程序员的选择。这也是 go-lang 的并发策略：

Do not communicate by sharing memory; instead, share memory by communicating.

当然，FPer 可以继续阐述不可变性的好处：由于其绝大部分代码天然就是 Shared Nothing 的，可以更容易的将任何一段代码投入并行运算。

这确实是一个无可比拟的优势。但在现实项目中，需要发挥这种优势的概率有多高，却是一个值得思考的问题。毕竟，不可变性不是免费的。在考虑它能发挥的价值的同时，也必须要为之付出的代价，把两个因素放到一起，结合项目的实际情况，做出务实的选择，才是一个合格的工程师应该具备的态度。

性能永远都是一个问题

很多 FPer 为了鼓吹 FP 在描述算法方面的优势时，总爱举这个例子：

quicksort []     = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
    where
        lesser  = filter (< p) xs
        greater = filter (>= p) xs

确实优雅的无与伦比。

对比之下，C 语言版本的实现就就冗长的多：

void qsort(int a[], int lo, int hi) {
  int h, l, p, t;
  if (lo < hi) {
  l = lo;
  h = hi;
  p = a[hi];
  do {
    while ((l < h) && (a[l] <= p)) 
        l = l+1;
    while ((h > l) && (a[h] >= p))
        h = h-1;
    if (l < h) {
        t = a[l];
        a[l] = a[h];
        a[h] = t;
    }
  } while (l < h);


  a[hi] = a[l];
  a[l] = p;
  qsort( a, lo, l-1 );
  qsort( a, l+1, hi );
  }
}

不过那些 FPer 没有告诉你们故事的另一面：相对于 C 语言版本，那份看起来很优雅的 Haskell 实现，无论在时间效率还是空间效率方面，都糟糕的一塌糊涂。

Haskell 是一门默认惰性求值的 FP 语言。从理论上，惰性求值可以可以让程序员可以站在更高抽象层面写程序，不用关心程序的执行顺序，语言的 runtime 会自动避免掉那些不必要的计算。

但惰性求值也不是免费的，对于暂时无需求值的表达式，需要以 thunk 的形式在内存中驻留，这就会导致不可控的空间占用。另外，由于需要不断的对是否已经求值进行判断，惰性求值也会付出一定的性能代价。

更为麻烦的是，作为一门惰性求值语言，正如我们之前所描述的，即便不考虑并行运算，只是因为其求值顺序的不确定，就会导致：即便在局部范围，每一个变量的不可变性也是必须的。

而这种不可变性对于性能的损耗，在很多“状态修改密集型”的算法面前，已经到了让人无法容忍的地步。

为了解决这类问题，不得不引入局部状态可修改的机制。其中之一，就是 Monad.ST。

Monad.ST

Monad.ST 的思想，就是引入引用的概念。也就是说，在一段计算中，不同的表达式，可以通过引用，指向同一个可修改的数据。不同表达式都可以根据需要对数据直接修改，而不是创建一份新数据的拷贝。

-- A MutVar# behaves like a single-element mutable array.
data MutVar# s a

-- Create MutVar# with specified initial value in specified state thread.
newMutVar# :: a -> State# s -> (# State# s, MutVar# s a #)

-- Read contents of MutVar#. Result is not yet evaluated.
readMutVar# :: MutVar# s a -> State# s -> (# State# s, a #)

-- Write contents of MutVar#.
writeMutVar# :: MutVar# s a -> a -> State# s -> State# s

这是个 GHC 编译器内部实现的 MutVar# ，从它的名字就可以看出，这是一个 Mutable Variable。而其后缀符号#则说明，这是一个 Unboxed Type。其三个主要函数用到了另外一个类型 State# ，也是一个 GHC 编译器内部实现的 Unboxed Type。

data State# s

MutVar# 是一个类型构造器，有两个参数： a 是要存储的数据类型。而 s 则代表是状态。从逻辑上， MutVar# 自身是一个引用，其引用的数据类型为 a ，而空间则从 s 所管理的存储上分配。如下图所示。

因而，我们可以写出下面的代码：

calc' :: (Num a) => State# s -> a -> a
calc' initS initV =
  let (# s1, ref #) = newMutVar# initV initS
  (# s2, v1 #) = readMutVar# ref s1
  s3 = writeMutVar# ref (v1*10)  s2
  (# s4, v2 #) = readMutVar# ref s3
  s5 = writeMutVar# ref (v2+20)  s4
(# _finalS, finalV #) = readMutVar# ref s5 in finalV

从这段代码，可以清晰的看出一个三部曲操作模式：

在初始状态分配一个内容为初始值的数据，然后得到一个引用，以及被修改的状态；
不断通过引用，读写数据内容；注意，中间状态也在不断改变和传递；
最后，丢弃最终状态，从引用里读出数据返回。

在各个步骤间，变量的依赖，保证了即便在惰性求值下它们也会按照顺序处理。由于变化的是状态，状态依次在步骤间传递，这样的模式，是一种典型的 State Monad。

newtype ST s a = ST (STRep s a)
type STRep s a = State# s -> (# State# s, a #)

instance Monad (ST s) where
return x = ST ( s -> (# s, x #))

(ST m) >>= k
  = ST $ \s ->
      case (m s) of { (# new_s, r #) ->
      case (k r) of { ST k2 -> (k2 new_s) }}</code></pre>

为了方便于 Monad 内部的代码编写，以及类型系统的约束，再提供如下辅助函数：

data STRef s a = STRef (MutVar# s a)


newSTRef :: a -> ST s (STRef s a)
newSTRef init = ST $ </span>s1# ->
case newMutVar# init s1# of { (# s2#, var# #) ->
(# s2#, STRef var# #) }

readSTRef :: STRef s a -> ST s a
readSTRef (STRef var#) = ST $ </span>s1# -> readMutVar# var# s1#

writeSTRef :: STRef s a -> a -> ST s ()
writeSTRef (STRef var#) val = ST $ </span>s1# ->
case writeMutVar# var# val s1# of { s2# ->
(# s2#, () #) }

modifySTRef :: STRef s a -> (a -> a) -> ST s ()
modifySTRef ref f = writeSTRef ref . f =<< readSTRef ref

然后就可以这样来写代码：

calc' ::  Int -> ST s Int
calc' initV = do 
  ref <- newSTRef initV
  v1  <- readSTRef ref
  writeSTRef $ v1 * 10
  v2  <- readSTRef ref
  writeSTRef $ v2 + 20
  readSTRef ref

需要特别指出的是，由于 State 和 initV 都是 calc'函数的参数，因而 calc'依然是个 pure function，因而具备 pure function 的一切特质。比如引用透明。其中每个步骤都是一个 State Transformer，通过>>=,>>组合为一个更大的 State Transformer，这也正是是 ST 名字的由来。

不过，calc'的结果依然还保存在 ST Monad 里。好在除了 IO Monad 之外，其它 Monad 的数据都可以从 Monad 里逃出。对于 ST Monad，则是通过 runST：

runST :: (forall s. ST s a) -> a
runST st = runSTRep (case st of { ST st_rep -> st_rep })
runSTRep :: (forall s. STRep s a) -> a
runSTRep st_rep = case st_rep realWorld# of
(# _, r #) -> r

在 runST 里，一个具体的状态实例作为参数传给了 State Transformer。而这个实例，则是 GHC 编译器提供的 readWorld#，其类型为 GHC 内置的 ReadWorld#。

因而我们的例子可以写成：

calc :: Int -> Int
calc initValue = runST $ calc' initValue

对命令式的模仿

runST 是一个重要的边界：它创建了一个初始状态，传递给 State Transformer，然后得到一个最终状态，以及计算的结果。最后，抛弃掉最终状态，仅保留计算结果。

如果我们把这一系列的机制和命令式语言对应起来，可以看出，这完全是对命令式语言局部变量处理的模拟。

对于命令式语言，所有的局部变量都是在线程的栈上分配，从而修改了 Stack 的状态。随后所有的读写操作也都在栈上进行，不断修改 Stack 的状态。在一个函数处理结束后，在栈上分配的局部变量都会自动释放，关心的数据则当作函数的返回值返回。如下图所示。

stack

而在 ST Monad 里，runST 对应的是命令式语言的函数，而 Stack 对应的则是 State：在计算开始时，提供一个 State，计算在 State 上分配数据，存取 State 的状态，等计算结束后，State 的最终状态被抛弃，返回计算结果。如下图所示。

这样的模仿，相对于命令式语言的局部变量可变性，并未得到任何额外的好处。但很明显，命令式语言在这类问题上的处理要简洁的多。同时也说明了，允许局部变量的可修改性，对于引用透明和线程安全没有任何影响，只会带来简洁和性能。

Rank 2 Type

我们设想一下，在命令式语言里，在一个函数调用结束后，如果其在栈里的分配的数据不释放，可以被随后的函数访问，那么那些数据就与全局变量无异了。我们都知道，全局变量是违背 Shared Nothing 原则的。

通过上述对照，我们知道 State 是对 Stack 的模仿。在 runST 结束后，State 也必须像 Stack 一样被释放，避免被其它计算继续使用，这才能保证线程安全。

可是，如果我们写下这样的代码：

f1 :: STRef s a -> ST s a
f1 ref = do 
  v  <- readSTRef ref
  writeSTRef $ v * 10
  readSTRef ref
let ref = runST $ newSTRef 10
v1  = runST $ readSTRef ref
v2  = runST $ f1 ref
in  ...

这就造成了 ref 在多个 runST 之间传递。对于惰性求值的语言而言，runST 的求值顺序是不确定的，从而导致 v1 和 v2 计算结果的不确定。这就像多线程程序共享同一份数据，却没有任何措施来保证对共享数据访问的序列化一样，是一个严重的问题。

不过，ST 设计者通过引入 Rank 2 Types 解决了这个问题。Rank 2 Types 不属于 Hindley-Milner 类型系统的范畴。也不在 haskell 98 里。但这对于很多设计却又是比不可少的。

在 Rank 1 Type 的一个函数里，每个类型变量，只能被绑定为一个类型。这就导致了，如果一个高阶函数的某个参数是一个参数化多态（Parametric Polymorphism）函数，那么在这个高阶函数里，无论那个参数化多态函数被调用多少次，其类型变量所绑定的类型都必须是一致的。比如下面的代码就无法通过编译：

g :: (a -> a) -> (Bool, Char)
g f = (f True, f 'c')

因为，f 在同一个函数 g 的上下文里，两次调用里，其类型变量 a 被绑定的类型是不同的：一个是 Bool，一个是 Char。

这明显是一个给程序员带来麻烦的问题。因而，GHC 给出了一个扩展，叫 Rank2Types。它允许程序员通过将上面例子中函数 g 的类型修改为：

g :: (forall a. a -> a) -> (Bool, Char)

某种程度上，你可以将 Rank 2 Types 理解为 C++的 Template Template Parameter 技术，比如：

template <typename T, typename G, 
  template <typename E> class Container >
struct Foo
{
   Container<T> tContainer;
   Container<G> gContainer;
};

下面我们来看看为何 Rank 2 Type 可以解决 runST 状态泄漏的问题。我们先来推导一下表达式 runST $ newSTRef 10 的类型：

runST :: (forall s. ST s a) -> a
newSTRef 10 :: forall s. ST s (STRef s Int)
[STRef s Int ~ a]

因而，

runST $ newSTRef 10 :: (forall s. ST s (STRef s Int)) -> STRef s Int

其中，s 已经出现在$\forall s$的限定范围之外，因而编译器将不会通过编译。

但是，如果 runST 的类型为 forall s. ST s a -> a，上述类型则变为：

runST $ newSTRef 10 :: forall s. ST s (STRef s Int) -> STRef s Int

在这个类型里，两个 s 都在同一个限定符的作用范围内，因而它能够通过编译。

反过来，假设 ref = runST $ newSTRef 10 这样的代码通过了编译，它将被代入的表达式：

runST $ readSTRef ref：
\(
\frac{ { \ldots, s=State\ RealWorld,\ ref=STRef\ \ s\ \ Int } }{b}
\)
\[
\frac{{\dots, s=State#\ \ RealWorld#,\ ref=STRef\ \ s\ \ Int } \vdash readVar\ \ ref::ST\ \ s\ \ Int}
{\Gamma \vdash readVar\ \ ref::ST\ \ (State#\ \ RealWorld#)\ \ Int}
\]

由此可见，s 是环境中的自由变量，readVar ref 的类型与 runST 所需的$\forall s. ST\ \ s\ \ a$类型不匹配，因而也无法通过编译。

因此，借助于 Rank 2 Types 的类型检查，程序员不可能写出能够让 state 从一个 runST 泄露的代码。从而保证了安全性。

模仿 C 语言算法

搞定了 ST Monad 之后，我们终于可以使用它所提供的机制来模仿 C 语言算法了：

import Control.Monad (when)
import Control.Monad.ST
import Data.Array.ST
import Data.Array.IArray
import Data.Array.MArray

qsort :: (IArray a e, Ix i, Enum i, Ord e) => a i e -> a i e
qsort arr = processArray quickSort arr

processArray :: (IArray a e, IArray b e, Ix i)
=> (forall s. (STArray s) i e -> ST s ()) -> a i e -> b i e
processArray f (arr :: a i e) = runST $ do
arr' <- thaw arr :: ST s (STArray s i e)
f arr'
unsafeFreeze arr'

quickSort :: (MArray a e m, Ix i, Enum i, Ord e) => a i e -> m ()
quickSort arr = qsort' =<< getBounds arr
where
qsort' (lo, hi) | lo >= hi = return ()
| otherwise = do
p <- readArray arr hi
l <- mainLoop p lo hi
swap l hi
qsort' (lo, pred l)
qsort' (succ l, hi)

mainLoop p l h  | l >= h    = return l
                | otherwise = do
    l' <- doTil (\l' b -> l' < h  && b <= p) succ l
    h' <- doTil (\h' b -> h' > l' && b >= p) pred h
    when (l' < h') &\$& do
        swap l' h'
    mainLoop p l' h'

doTil p op ix = do
    b <- readArray arr ix
    if p ix b then doTil p op (op ix) else return ix

swap xi yi = do
    x <- readArray arr xi
    readArray arr yi >>= writeArray arr xi
    writeArray arr yi x</code></pre>

这个版本，相对于 C 语言版本，已经比 C 的写法还要繁杂。但不幸的是，即便经过这样的努力，此版本的性能，虽然相对于之前那个简介而优雅的版本，得到了一定的提升，但其性能依然得到了这样的评价：

The program below is working very very slowly. It's probably slowsort... :o)

终于，有高手看不过去了，干脆祭出 unsafe 大法：通过放弃编译器检查的安全性，来提高程序的性能，然后得到了这个版本：

import Data.Array.Base (unsafeRead, unsafeWrite)
import Data.Array.ST
import Control.Monad.ST

myqsort :: STUArray s Int Int -> Int -> Int -> ST s ()
myqsort a lo hi
| lo < hi = do
let lscan p h i
| i < h = do
v <- unsafeRead a i
if p < v then return i else lscan p h (i+1)
| otherwise = return i
rscan p l i
| l < i = do
v <- unsafeRead a i
if v < p then return i else rscan p l (i-1)
| otherwise = return i
swap i j = do
v <- unsafeRead a i
unsafeRead a j >>= unsafeWrite a i
unsafeWrite a j v
sloop p l h
| l < h = do
l1 <- lscan p h l
h1 <- rscan p l1 h
if (l1 < h1) then (swap l1 h1 >> sloop p l1 h1) else return l1
| otherwise = return l
piv <- unsafeRead a hi
i <- sloop piv lo hi
swap i hi
myqsort a lo (i-1)
myqsort a (i+1) hi
| otherwise = return ()

终于，得到了这样的评价：是 C 语言版本运行时间的 2 倍以内。

... reports that this version runs within 2x of the C version.

结论

对于命令式语言而言，对于一个函数内的局部变量的修改，并不会引入任何副作用，因为每个线程都有自己的栈，不同线程会从自己的栈上为局部变量分配空间。因而线程间也是 100%的 Shared Nothing。

但 FP 对于不可变性的坚持，让程序员在这类问题上也不得不付出不必要的代价。为了解决这类的问题，FP 也不得不去模拟在命令式语言的行为。这这类的模拟行为必须有编译器的内建支持，否则，在 Pure FP 自身的语义下，是不可能存在 reference to mutable variable 这样的元素的。而这一切的努力，在命令式语言里，不过是再自然不过的内建支持。另外，即便付出这样的努力，由于 FP 自身的特点，其性能依然比 C 语言要慢的多。

由于变量的缺位，FP 只能以递归的方式来处理循环问题。但一些 FPer 却把这种不得不为之的结果鼓吹为: 递归是描述问题最自然的方式。

但事实上，确实一些问题用递归描述起来更加自然，但同样也有一些问题，用迭代的方式描述起来更加自然。更不用说，在性能约束面前，很多无法自然描述为尾递归问题的算法，不得不修改为迭代算法，却又受语言能力所限，不得不用递归的语法表述迭代算法，让代码看起来更加晦涩。

而命令式语言，同时支持递归和迭代两种方式，其中一些（比如 C++)也支持对于尾递归的优化。这就让程序员拥有了更加自由的选择。可以根据不同问题域做出最合理的决策。

因而，给出灵活度和自由度，让程序员自己根据需要做出决策，要比强制程序员——特别是真正的程序员——必须在所有情况下都必须遵守某种方式要更有价值。

分享到QQ

分享到微博