33

我听到的反对函数式语言的一个论点是,单一赋值编码太难了,或者至少比“普通”编程困难得多。

但是通过我的代码,我意识到我真的没有很多(任何?)使用模式,如果你用一种相当现代的语言编写的话,这些模式不能用单一的赋值形式来编写。

那么在一次调用范围内变化的变量的用例是什么?请记住,在这种情况下,循环索引、参数和其他在调用之间变化的范围绑定值不是多重赋值(除非您出于某种原因必须在正文中更改它们),并假设您正在编写一些东西远远高于汇编语言级别,您可以在其中编写诸如

values.sum

或(如果未提供总和)

function collection.sum --> inject(zero, function (v,t) --> t+v )

x = if a > b then a else b

或者

n = case s 
  /^\d*$/ : s.to_int
  ''      : 0
  '*'     : a.length
  '?'     : a.length.random
  else    fail "I don't know how many you want"

当您需要时,并有列表推导、地图/收集等可用。

您是否发现在这样的环境中您仍然想要/需要可变变量,如果是,那是为了什么?

澄清一下,我不是要求背诵对 SSA 表格的反对意见,而是要求这些反对意见适用的具体示例。我正在寻找带有可变变量的清晰简洁的代码,没有它们就无法编写。

到目前为止我最喜欢的例子(以及我期望的最好的反对意见):

  1. Paul Johnson 的Fisher-Yates 算法答案,当您包含大 O 约束时,它非常强大。但是,正如 catulahoops 指出的那样,big-O 问题与 SSA 问题无关,而是与可变数据类型有关,并且将这些放在一边,算法可以在 SSA 中相当清楚地编写:

     shuffle(Lst) ->
         array:to_list(shuffle(array:from_list(Lst), erlang:length(Lst) - 1)).
     shuffle(Array, 0) -> Array;
     shuffle(Array, N) ->
         K = random:uniform(N) - 1,
         Ek = array:get(K, Array),
         En = array:get(N, Array),
         shuffle(array:set(K, En, array:set(N, Ek, Array)), N-1).
    
  2. jpalecek 的多边形面积示例:

    def area(figure : List[Point]) : Float = {
      if(figure.empty) return 0
      val last = figure(0)
      var first= figure(0)
      val ret = 0
      for (pt <- figure) {
        ret+=crossprod(last - first, pt - first)
        last = pt
      }
      ret
    }
    

    这可能仍然写成:

    def area(figure : List[Point]) : Float = {
        if figure.length < 3
            0
          else
            var a = figure(0)
            var b = figure(1)
            var c = figure(2)
            if figure.length == 3
                magnitude(crossproduct(b-a,c-a))
              else 
                foldLeft((0,a,b))(figure.rest)) { 
                   ((t,a,b),c) => (t+area([a,b,c]),a,c)
                   }
    

    或者,由于有些人反对这个公式的密度,它可以被改写:

    def area([])    = 0.0   # An empty figure has no area
    def area([_])   = 0.0   # ...nor does a point
    def area([_,_]) = 0.0   # ...or a line segment
    def area([a,b,c]) =     # The area of a triangle can be found directly
        magnitude(crossproduct(b-a,c-a))
    def area(figure) =      # For larger figures, reduce to triangles and sum
        as_triangles(figure).collect(area).sum
    
    def as_triangles([])      = []  # No triangles without at least three points
    def as_triangles([_])     = []
    def as_triangles([_,_])   = []
    def as_triangles([a,b,c | rest) = [[a,b,c] | as_triangles([a,c | rest])]
    
  3. Princess 关于用不可变结构实现 O(1) 队列的困难的观点很有趣(并且很可能为一个令人信服的例子提供基础),但正如所述,它基本上是关于数据结构的可变性,而不是直接关于多重分配问题.

  4. 我对埃拉托色尼筛法的答案很感兴趣,但不相信。在他引用的论文中给出的合适的 big-O,提取尽可能多的素数生成器在使用或不使用 SSA 的情况下看起来都不容易正确实现。


嗯,谢谢大家的尝试。由于大多数答案要么是 1)基于可变数据结构,而不是基于单一赋值,以及 2)它们是关于单一赋值形式的,因此本领域技术人员很容易反驳,我将从我的演讲和/或重组中划出界限(也许可以将其作为讨论主题作为备用,以防万一我在时间用完之前用完了单词)。

再次感谢。

4

14 回答 14

18

我遇到的最困难的问题是洗牌。Fisher-Yates算法(有时也称为 Knuth 算法)涉及遍历列表,将每个项目与随机的其他项目交换。该算法是 O(n),众所周知并且长期以来被证明是正确的(在某些应用程序中是一个重要属性)。但它需要可变数组。

这并不是说您不能在函数式程序中进行改组。Oleg Kiselyov 曾写过这方面的文章。但如果我正确理解他,功能改组是 O(n . log n) 因为它通过构建二叉树来工作。

当然,如果我需要在 Haskell 中编写 Fisher-Yates 算法,我只需将它放在ST monad中,它可以让您将涉及可变数组的算法封装在一个不错的纯函数中,如下所示:

-- | Implementation of the random swap algorithm for shuffling.  Reads a list
-- into a mutable ST array, shuffles it in place, and reads out the result
-- as a list.

module Data.Shuffle (shuffle) where


import Control.Monad
import Control.Monad.ST
import Data.Array.ST
import Data.STRef
import System.Random

-- | Shuffle a value based on a random seed.
shuffle :: (RandomGen g) => g -> [a] -> [a]
shuffle _ [] = []
shuffle g xs = 
    runST $ do
      sg <- newSTRef g
      let n = length xs
      v <- newListArray (1, n) xs
      mapM_ (shuffle1 sg v) [1..n]
      getElems v

-- Internal function to swap element i with a random element at or above it.
shuffle1 :: (RandomGen g) => STRef s g -> STArray s Int a -> Int -> ST s ()
shuffle1 sg v i = do
  (_, n) <- getBounds v
  r <- getRnd sg $ randomR (i, n)
  when (r /= i) $ do
    vi <- readArray v i
    vr <- readArray v r
    writeArray v i vr
    writeArray v r vi


-- Internal function for using random numbers
getRnd :: (RandomGen g) => STRef s g -> (g -> (a, g)) -> ST s a
getRnd sg f = do
  g1 <- readSTRef sg
  let (v, g2) = f g1
  writeSTRef sg g2
  return v
于 2009-03-07T16:57:12.903 回答
15

如果您想进行学术论证,那么在技术上当然没有必要多次分配变量。证明是所有代码都可以用SSA(单一静态分配)形式表示。事实上,这是对多种静态和动态分析最有用的形式。

同时,我们并非都以 SSA 形式编写代码是有原因的:

  1. 以这种方式编写代码通常需要更多语句(或更多行代码)。简洁是有价值的。
  2. 它几乎总是效率较低。是的,我知道您在谈论高级语言——一个公平的范围界定——但即使在远离汇编的 Java 和 C# 世界中,速度也很重要。很少有应用程序与速度无关。
  3. 这并不容易理解。尽管 SSA 在数学意义上“更简单”,但它更抽象于常识,这在现实世界的编程中很重要。如果你必须非常聪明才能理解它,那么它在整个编程中就没有立足之地。

即使在上面的示例中,也很容易戳洞。接受你的case陈述。如果有一个决定是否'*'允许的管理选项,以及一个单独的决定是否允许的选项'?'怎么办?此外,整数大小写不允许为零,除非用户具有允许它的系统权限。

这是一个带有分支和条件的更真实的示例。你能把它写成一个单一的“声明”吗?如果是这样,您的“陈述”真的与许多单独的陈述不同吗?如果没有,您需要多少个临时只写变量?这种情况是否比只有一个变量好得多?

于 2009-03-04T15:18:15.210 回答
12

我从来没有发现过这样的案例。虽然您总是可以发明新名称,例如转换为 SSA 形式,但我实际上发现每个值都有自己的名称是很容易和自然的。像 Haskell 这样的语言给了我很多关于命名哪些值的选择,以及两个不同的位置来放置名称绑定(letwhere)。我发现单一作业形式很自然,一点也不难。

我偶尔会错过能够在堆上拥有指向可变对象的指针。但是这些东西没有名字,所以不是同一个反对。(而且我还发现,当我在堆上使用可变对象时,我往往会写更多的错误!)

于 2009-03-05T00:12:51.900 回答
6

我认为您会发现最高效的语言允许您混合函数式和命令式风格,例如 OCaml 和 F#。

在大多数情况下,我可以编写很简单的代码,即“将 x 映射到 y,将 y 减少到 z”。在 95% 的情况下,函数式编程简化了我的代码,但在一个领域,不变性表现出了它的优势:

易于实现和不可变堆栈与不可变队列之间的巨大差异。

堆栈很容易,并且与持久性很好地融合在一起,队列很荒谬。

不可变队列的最常见实现使用一个或多个内部堆栈和堆栈轮换。好处是这些队列大部分时间都在 O(1) 中运行,但有些操作会在 O(n) 中运行。如果您在应用程序中依赖持久性,那么原则上每个操作都可能在 O(n) 中运行。当您需要实时(或至少一致)性能时,这些队列并不好。

Chris Okasaki 在他的书中提供了不可变队列的实现,他们使用惰性来实现所有操作的 O(1)。它是一个非常聪明、相当简洁的实时队列实现——但它需要深入了解其底层实现细节,而且它仍然比不可变堆栈复杂一个数量级。

相反,我可以使用可变链表编写堆栈和队列,这些链表在所有操作中以恒定时间运行,生成的代码将非常简单。


关于多边形的面积,很容易将其转换为函数形式。假设我们有一个像这样的 Vector 模块:

module Vector =
    type point =
        { x : float; y : float}
        with
            static member ( + ) ((p1 : point), (p2 : point)) =
                { x = p1.x + p2.x;
                  y = p1.y + p2.y;}

            static member ( * ) ((p : point), (scalar : float)) =
                { x = p.x * scalar;
                  y = p.y * scalar;}

            static member ( - ) ((p1 : point), (p2 : point)) = 
                { x = p1.x - p2.x;
                  y = p1.y - p2.y;}

    let empty = { x = 0.; y = 0.;}
    let to_tuple2 (p : point) = (p.x, p.y)
    let from_tuple2 (x, y) = { x = x; y = y;}
    let crossproduct (p1 : point) (p2 : point) =
        { x = p1.x * p2.y; y = -p1.y * p2.x }

我们可以使用一些元组魔法来定义我们的区域函数:

let area (figure : point list) =
    figure
    |> Seq.map to_tuple2
    |> Seq.fold
        (fun (sum, (a, b)) (c, d) -> (sum + a*d - b*c, (c, d) ) )
        (0., to_tuple2 (List.hd figure))
    |> fun (sum, _) -> abs(sum) / 2.0

或者我们可以使用叉积代替

let area2 (figure : point list) =
    figure
    |> Seq.fold
        (fun (acc, prev) cur -> (acc + (crossproduct prev cur), cur))
        (empty, List.hd figure)
    |> fun (acc, _) -> abs(acc.x + acc.y) / 2.0

我没有发现任何一个功能不可读。

于 2009-03-10T17:03:53.830 回答
4

该混洗算法使用单个赋值来实现是微不足道的,实际上它与将迭代重写为尾递归的命令式解决方案完全相同。(Erlang,因为我可以比 Haskell 更快地编写它。)

 shuffle(Lst) ->
     array:to_list(shuffle(array:from_list(Lst), erlang:length(Lst) - 1)).

 shuffle(Array, 0) -> Array;
 shuffle(Array, N) ->
     K = random:uniform(N) - 1,
     Ek = array:get(K, Array),
     En = array:get(N, Array),
     shuffle(array:set(K, En, array:set(N, Ek, Array)), N-1).

如果这些数组操作的效率是一个问题,那么这是一个关于可变数据结构的问题,与单次赋值无关。

你不会得到这个问题的答案,因为没有例子存在。这只是对这种风格的熟悉程度的问题。

于 2009-03-08T09:41:50.790 回答
3

回应杰森——

function forbidden_input?(s)
    (s = '?' and not administration.qmark_ok) ||
    (s = '*' and not administration.stat_ok)  ||
    (s = '0' and not 'root node visible' in system.permissions_for(current_user))

n = if forbidden_input?(s)
    fail "'" + s + "' is not allowed."
  else
    case s
      /^\d*$/ : s.to_int
      ''      : 0
      '*'     : a.length
      '?'     : a.length.random
      else    fail "I don't know how many you want"
于 2009-03-04T17:28:57.563 回答
3

我会错过非纯函数式语言的作业。主要是因为它们阻碍了循环的有用性。示例(斯卡拉):

def quant[A](x : List[A], q : A) = {
  var tmp : A=0
  for (el <- x) { tmp+= el; if(tmp > q) return el; }
  // throw exception here, there is no prefix of the list with sum > q
}

这应该计算列表的分位数,注意tmp多次分配的累加器。

一个类似的例子是:

def area(figure : List[Point]) : Float = {
  if(figure.empty) return 0
  val last = figure(0)
  var first= figure(0)
  val ret = 0
  for (pt <- figure) {
    ret+=crossprod(last - first, pt - first)
    last = pt
  }
  ret
}

主要注意last变量。

可以在元组上使用 fold 重写这些示例以避免多次分配,但这实际上无助于可读性。

于 2009-03-07T16:15:52.550 回答
1

本地(方法)变量当然不必分配两次。但即使在函数式编程中重新分配变量也是允许的。它正在改变(部分)不允许的值。正如 dsimcha 已经回答的那样,对于非常大的结构(可能位于应用程序的根目录),替换整个结构对我来说似乎不可行。想想看。应用程序的状态最终都包含在应用程序的入口点方法中。如果绝对没有状态可以在不被替换的情况下改变,那么您必须在每次击键时重新启动应用程序。:(

于 2009-03-07T15:30:04.190 回答
1

如果您有一个构建惰性列表/树然后再次对其进行缩减的函数,则函数式编译器可能能够使用deforestation对其进行优化。

如果它很棘手,它可能不会。那么你有点不走运,性能和内存明智,除非你可以迭代和使用可变变量。

于 2009-03-07T17:19:24.083 回答
1

感谢 Church-Turing Thesis,我们知道任何可以用图灵完备语言编写的东西都可以用任何图灵完备语言编写。所以,当你开始着手时,如果你足够努力的话,在 Lisp 中没有什么是你在 C# 中做不到的,反之亦然。(更重要的是,无论如何,在大多数情况下,任何一种都会被编译成 x86 机器语言。)

所以,你的问题的答案是:没有这样的情况。所有的情况下,人类更容易用一种范式/语言或另一种来理解——这里的理解容易程度与培训和经验有关。

于 2009-03-09T16:16:58.723 回答
1

也许这里的主要问题是语言循环的风格。在我们使用递归的语言中,任何在循环过程中发生变化的值都会在再次调用函数时重新绑定。在块中使用迭代器的语言(例如,Smalltalk 和 Ruby 的inject方法)往往是相似的,尽管 Ruby 中的许多人仍然会使用each可变变量 over inject

另一方面,当您使用whileand对循环进行编码时,当您可以将多个参数传递给执行循环一次迭代的代码块时,您无法轻松地自动重新绑定变量,因此不可变变量for会比较不方便。

在 Haskell 中工作是研究可变变量必要性的一种非常好的方法,因为默认值是不可变的,但可变变量是可用的(如IORefsMVars等)。我最近呢,呃,自己也是这样“调查”的,得出了如下结论。

  1. 在绝大多数情况下,可变变量不是必需的,没有它们我很高兴。

  2. 对于线程间通信,可变变量是必不可少的,原因很明显。(这是 Haskell 特有的;在最低级别使用消息传递的运行时系统当然不需要它们。)但是,这种使用非常少见,因此不必使用函数来读取和写入它们(readIORef fooRef val等等)。很大的负担。

  3. 我在单个线程中使用了可变变量,因为它似乎使某些事情变得更容易,但后来我后悔了,因为我意识到很难推断存储在那里的值发生了什么。(有几个不同的函数在操纵这个值。)这有点让人大开眼界。在典型的温水锅里的青蛙风格中,我没有意识到 Haskell 让我能够轻松地推理值的使用,直到我遇到了一个我过去如何使用它们的例子.

所以这些天来,我已经相当坚定地站在不可变变量的一边。

由于之前对这个问题的回答混淆了这些东西,我觉得有必要在这里非常有力地指出,这个问题与纯度和函数式编程都是正交的。例如,我认为 Ruby 将受益于具有单赋值局部变量,尽管可能需要对语言进行一些其他更改,例如添加尾递归,以使其真正方便。

于 2009-05-18T01:59:13.427 回答
0

当您需要对大型数据结构进行小的更改时怎么办?您真的不想每次修改几个元素时都复制整个数组或大类。

于 2009-03-04T15:06:59.823 回答
0

除了现在你指出来,我还没有真正考虑过这一点。

实际上,我尝试不下意识地使用多个作业。

这是我在python中谈论的一个例子

start = self.offset%n
if start:
    start = n-start

以这种方式编写以避免不必要的额外模数或减法。这与 bignum 样式的长整数一起使用,因此它是值得优化的。不过,关于它的事情是它确实是一个单一的任务。

我根本不会错过多项任务。

于 2009-03-07T15:34:02.667 回答
0

我知道您要求的代码确实显示了可变变量的好处。我希望我能提供它。但正如之前所指出的——没有不能用两种方式表达的问题。尤其是因为您指出 jpalecek 的多边形示例区域可以用折叠算法编写(恕我直言,这更加混乱,并将问题带到不同程度的复杂性)-这让我想知道为什么您要降低可变性所以难的。因此,我将尝试提出共同点以及不可变和可变数据共存的论点。

在我看来,这个问题有点忽略了要点。我知道我们程序员倾向于喜欢干净和简单的东西,但我们有时会错过混合也是可能的。这可能就是为什么在关于不变性的讨论中很少有人采取中间立场的原因。我只是想知道为什么,因为让我们面对现实吧——不变性是抽象各种问题的好工具。但有时它是一种巨大的痛苦。有时它只是太约束了。仅这一点就让我停下来想一想——我们真的想放松可变性吗?真的是非此即彼吗?难道我们不能达成一些共同点吗?不变性什么时候可以帮助我更快地实现我的目标,可变性什么时候可以帮助我实现目标?哪种解决方案更易于阅读和维护?(对我来说哪个是最大的问题)

很多这些问题都受到程序员的品味和他们习惯于编程的影响。所以我将关注通常是大多数支持不变性论点的中心的一个方面 - 并行性:

围绕不变性的争论经常被引入并行性。我处理过需要 100 多个 CPU 在合理时间内解决的问题。它教会了我一件非常重要的事情:大多数时候并行处理数据图实际上并不是最有效的并行化方式。它肯定会受益匪浅,但不平衡是该问题空间中的一个真正问题。因此,通常并行处理多个可变图并使用不可变消息交换信息会更有效。这意味着,当我知道图是孤立的,我没有向外界透露它时,我想以我能想到的最简洁的方式对其进行操作。这通常涉及改变数据。但是在对数据进行这些操作之后,我想向全世界开放数据——如果数据是可变的,这就是我通常会有点紧张的地方。因为程序的其他部分可能会破坏数据,状态变得无效,......因为在向世界开放之后,数据通常确实会进入并行世界。

因此,现实世界的并行程序通常具有在确定的单线程操作中使用数据图的区域 - 因为它们根本不为外界所知 - 以及它们可能涉及多线程操作的区域(希望只是提供未被操纵的数据) . 在这些多线程部分中,我们从不希望它们改变——处理过时的数据比处理不一致的数据更好。这可以通过不变性的概念来保​​证。

这让我得出了一个简单的结论:对我来说真正的问题是,我所熟悉的编程语言中没有一种允许我说:“在这一点之后,整个数据结构将是不可变的”“给我一个可变的副本这个不可变的数据结构在这里,请验证只有我可以看到可变副本”。现在我必须自己通过翻转只读位或类似的东西来保证它。如果我们可以让编译器支持它,它不仅可以保证我在翻转所述位后没有做任何愚蠢的事情,而且它实际上可以帮助编译器进行以前无法做到的各种优化。另外 - 对于更熟悉命令式编程模型的程序员来说,该语言仍然很有吸引力。

所以总结一下。恕我直言,程序通常有充分的理由同时使用数据图的不可变和可变表示。我认为数据在默认情况下应该是不可变的,编译器应该强制执行这一点——但我们应该有私有可变表示的概念,因为自然存在多线程永远无法到达的领域——并且可读性和可维护性可以受益于更多命令式结构。

于 2009-03-13T12:11:18.020 回答