94

如果函数式编程语言不能保存任何状态，那么它们如何做一些简单的事情，比如读取用户的输入？他们如何“存储”输入（或为此存储任何数据？）

例如：这个简单的 C 语言如何转化为 Haskell 等函数式编程语言？

#include<stdio.h>
int main() {
    int no;
    scanf("%d",&no);
    return 0;
}

（我的问题受到这篇优秀文章的启发：“名词王国中的执行”。阅读它让我更好地理解了究竟什么是面向对象编程，Java 如何以一种极端的方式实现它，以及函数式编程语言如何成为一种对比。）

4

10 回答 10

81

如果函数式编程语言不能保存任何状态，那么它们如何做一些简单的事情，比如读取用户的输入（我的意思是他们如何“存储”它），或者存储任何数据？

正如您所收集的，函数式编程没有状态——但这并不意味着它不能存储数据。不同之处在于，如果我按照以下方式编写（Haskell）语句

let x = func value 3.14 20 "random"
in ...

我保证 : 中的值x始终相同...：没有什么可以改变它。同样，如果我有一个函数f :: String -> Integer（一个接受字符串并返回一个整数的函数），我可以确定它f不会修改它的参数，或更改任何全局变量，或将数据写入文件，等等。正如 sepp2k 在上面的评论中所说，这种不可变性对于推理程序非常有帮助：您编写折叠、旋转和破坏数据的函数，返回新副本以便您可以将它们链接在一起，并且您可以确定没有这些函数调用可以做任何“有害”的事情。你知道x总是这样x，而且你不必担心有人x := foo bar在声明之间的某个地方写了x以及它的用途，因为那是不可能的。

现在，如果我想读取用户的输入怎么办？正如 KennyTM 所说，不纯函数是一个纯函数，它将整个世界作为参数传递，并返回其结果和世界。当然，您并不想实际这样做：一方面，它非常笨重，另一方面，如果我重用同一个世界对象会发生什么？所以这以某种方式被抽象了。Haskell 使用 IO 类型处理它：

main :: IO ()
main = do str <- getLine
          let no = fst . head $ reads str :: Integer
          ...

这告诉我们这main是一个不返回任何内容的 IO 操作；执行这个动作就是运行一个 Haskell 程序的意思。规则是 IO 类型永远不能逃脱 IO 动作；在这种情况下，我们使用do. 因此，getLine返回 an IO String，可以通过两种方式来考虑：首先，作为一个动作，它在运行时会产生一个字符串；其次，作为一个被IO“污染”的字符串，因为它是不纯的。第一个更正确，但第二个可能更有帮助。取出<-并存储它——但由于我们String处于IO 操作中，我们必须将其包装起来，因此它不能“逃脱”。下一行尝试读取一个整数 ( ) 并获取第一个成功匹配 (IO Stringstrreadsfst . head); 这都是纯粹的（没有 IO），所以我们给它起一个let no = .... no然后我们可以str在.... 因此，我们存储了不纯数据（从getLineinto str）和纯数据（let no = ...）。

这种使用 IO 的机制非常强大：它允许您将程序的纯算法部分与不纯的用户交互部分分开，并在类型级别强制执行。您的minimumSpanningTree函数不可能在代码中的其他地方更改某些内容，或者向您的用户写一条消息，等等。它是安全的。

这是在 Haskell 中使用 IO 所需要知道的全部内容；如果这就是你想要的，你可以在这里停下来。但是，如果您想了解为什么会这样，请继续阅读。（请注意，这些内容将特定于 Haskell——其他语言可能会选择不同的实现。）

所以这可能看起来有点作弊，不知何故为纯 Haskell 添加了杂质。但事实并非如此——事实证明，我们可以完全在纯 Haskell 中实现 IO 类型（只要我们有RealWorld. 想法是这样的：IO 动作IO type与函数相同RealWorld -> (type, RealWorld)，它接受现实世界并返回类型对象type和修改后的对象RealWorld。然后我们定义了几个函数，这样我们就可以使用这种类型而不会发疯：

return :: a -> IO a
return a = \rw -> (a,rw)

(>>=) :: IO a -> (a -> IO b) -> IO b
ioa >>= fn = \rw -> let (a,rw') = ioa rw in fn a rw'

第一个允许我们谈论不做任何事情return 3的 IO 动作：是一个不查询现实世界而只是返回的 IO 动作3。操作符，发音为“ >>=bind”，允许我们运行 IO 操作。它从 IO 动作中提取值，通过函数传递它和现实世界，并返回生成的 IO 动作。请注意，这>>=强制执行我们的规则，即永远不允许 IO 操作的结果逃逸。

那么我们就可以把上面的main变成如下普通的一组函数应用：

main = getLine >>= \str -> let no = (fst . head $ reads str :: Integer) in ...

Haskell 运行时从main初始 开始RealWorld，我们准备好了！一切都是纯粹的，它只是有一个花哨的语法。

[编辑： 正如@Conal 指出的那样，这实际上并不是 Haskell 用来做 IO 的。如果您添加并发性，或者在 IO 操作中间添加任何改变世界的方式，这个模型就会失效，所以 Haskell 不可能使用这个模型。它仅对顺序计算是准确的。因此，Haskell 的 IO 可能有点躲闪；即使不是，它也肯定不是那么优雅。根据@Conal 的观察，请参阅 Simon Peyton-Jones 在Tackling the Awkward Squad [pdf]第 3.1 节中所说的话；他提出了沿着这些思路可能构成替代模型的东西，但随后因其复杂性而放弃了它并采取了不同的策略。]

同样，这（几乎）解释了 IO 和一般的可变性如何在 Haskell 中工作；如果这就是您想知道的全部内容，您可以在此处停止阅读。如果您想要最后一剂理论，请继续阅读 - 但请记住，此时，我们离您的问题已经很远了！

所以最后一件事：事实证明，这种结构——一个带有returnand的参数类型>>=——是非常通用的；它被称为 monad，do符号 ,return和>>=与它们中的任何一个一起使用。正如你在这里看到的，单子并不神奇。神奇的是do块变成了函数调用。RealWorld类型是我们看到任何魔法的唯一地方。列表构造函数之类的类型[]也是 monad，它们与不纯代码无关。

您现在（几乎）了解有关 monad 概念的所有内容（除了一些必须满足的定律和正式的数学定义），但您缺乏直觉。网上有大量可笑的 monad 教程；我喜欢这个，但你有选择。但是，这可能对您没有帮助；获得直觉的唯一真正方法是结合使用它们并在正确的时间阅读一些教程。

但是，您不需要这种直觉来理解 IO。全面了解 monad 是锦上添花，但您现在可以使用 IO。在我向您展示了第一个main功能之后，您就可以使用它了。您甚至可以将 IO 代码视为不纯语言！但请记住，有一个潜在的功能表示：没有人在作弊。

（PS：对不起，我走的有点远。）

于 2010-05-01T20:41:52.763 回答
23

这里有很多好的答案，但它们很长。我将尝试给出一个有用的简短答案：

  • 函数式语言将状态放在与 C 相同的位置：在命名变量中和在堆上分配的对象中。不同之处在于：

    • 在函数式语言中，“变量”在进入作用域时（通过函数调用或 let 绑定）获取其初始值，之后该值不会改变。同样，在堆上分配的对象会立即使用其所有字段的值进行初始化，此后不会更改。

    • “状态变化”不是通过改变现有变量或对象来处理的，而是通过绑定新变量或分配新对象来处理的。

  • IO 通过一个技巧来工作。产生字符串的副作用计算由一个函数描述，该函数将 World 作为参数，并返回包含字符串和新 World 的对。世界包括所有磁盘驱动器的内容、曾经发送或接收的每个网络数据包的历史、屏幕上每个像素的颜色等等。诀窍的关键是对世界的访问受到严格限制，因此

    • 没有程序可以复制世界（你会把它放在哪里？）

    • 没有程序可以抛弃世界

    使用这个技巧可以有一个独特的世界，它的状态会随着时间而变化。语言运行时系统不是用函数式语言编写的，它通过更新唯一的 World 而不是返回一个新的 World 来实现副作用计算。

    Simon Peyton Jones 和 Phil Wadler 在他们具有里程碑意义的论文“Imperative Functional Programming”中很好地解释了这个技巧。

于 2010-05-01T20:59:26.653 回答
19

我正在中断对新答案的评论回复，以提供更多空间：

我写：

据我所知，这个故事IO（通过“纯顺序”，我的意思是即使是世界（宇宙）也不允许在命令式计算的开始和结束之间改变，除非是由于该计算。例如，当您的计算机运行时，您的大脑等无法运行。并发可以由更像 的东西来处理，它允许不确定性和交错。World -> (a,World)IOWorld -> PowerSet [(a,World)]

诺曼写道：

@Conal：我认为 IO 故事很好地概括为非确定性和交错；如果我没记错的话，“尴尬小队”论文中有一个很好的解释。但是我不知道有什么好的论文可以清楚地解释真正的并行性。

@Norman：在什么意义上概括？我建议通常给出的指称模型/解释World -> (a,World)与 Haskell 不匹配，IO因为它没有考虑非确定性和并发性。可能有一个更复杂的模型适合，例如World -> PowerSet [(a,World)]，但我不知道这样的模型是否已经制定并显示出足够和一致的。我个人怀疑是否能找到这样的野兽，因为它IO由数千个 FFI 导入的命令式 API 调用组成。因此，IO正在实现其目的：

未解决的问题：IOmonad 已成为 Haskell 的 sinbin。（每当我们不理解某些东西时，我们就把它扔到 IO monad 中。）

（摘自 Simon PJ 的 POPL 演讲穿着毛衣 穿着毛衣：Haskell 回顾展。）

在Tackling the Awkward Squad 的第 3.1 节中，Simon 指出了哪些不起作用type IO a = World -> (a, World)，包括“当我们添加并发时，该方法无法很好地扩展”。然后他提出了一个可能的替代模型，然后放弃了指称解释的尝试，他说

然而，我们将采用基于过程演算语义的标准方法的操作语义。

未能找到精确且有用的指称模型是我认为 Haskell IO 背离我们所谓的“函数式编程”或更具体地称为“指称编程”的精神和深刻好处的根本原因. 请参阅此处的评论。

于 2010-05-02T17:14:44.740 回答
17

函数式编程源自 lambda 演算。如果您真的想了解函数式编程，请查看http://worrydream.com/AlligatorEggs/

这是一种学习 lambda 演算的“有趣”方式，带您进入令人兴奋的函数式编程世界！

了解 Lambda 演算如何有助于函数式编程。

所以 Lambda 演算是许多现实世界编程语言的基础，例如 Lisp、Scheme、ML、Haskell ......

假设我们要描述一个向任何输入添加三个的函数，我们将编写：

plus3 x = succ(succ(succ x))

阅读“plus3 是一个函数，当应用于任何数字 x 时，会产生 x 的后继者的后继者”</p>

请注意，对任何数加 3 的函数不必命名为 plus3；“plus3”这个名字只是命名这个函数的一个方便的简写

(plus3 x) (succ 0) ≡ ((λ x. (succ (succ (succ x)))) (succ 0))

请注意，我们将 lambda 符号用于函数（我认为它看起来有点像鳄鱼，我猜这就是鳄鱼蛋的想法的来源）

lambda 符号是鳄鱼（一个函数），x 是它的颜色。您也可以将 x 视为一个参数（Lambda 演算函数实际上只假设有一个参数），其余的您可以将其视为函数的主体。

现在考虑抽象：

g ≡ λ f. (f (f (succ 0)))

参数 f 用于函数位置（在调用中）。我们称 ga 高阶函数是因为它需要另一个函数作为输入。您可以将其他函数调用 f 视为“鸡蛋”。现在使用我们创建的两个函数或“鳄鱼”，我们可以做这样的事情：

(g plus3) = (λ f. (f (f (succ 0)))(λ x . (succ (succ (succ x)))) 
= ((λ x. (succ (succ (succ x)))((λ x. (succ (succ (succ x)))) (succ 0)))
 = ((λ x. (succ (succ (succ x)))) (succ (succ (succ (succ 0)))))
 = (succ (succ (succ (succ (succ (succ (succ 0)))))))

如果您注意到，您可以看到我们的 λ f Alligator 吃掉了我们的 λ x Alligator，然后 λ x Alligator 吃掉了。然后我们的 λ x Alligator 在 λ f 的 Alligator 蛋中重生。然后这个过程重复，左边的 λ x Alligator 现在吃掉了右边的另一个 λ x Alligator。

然后你可以使用这组简单的“鳄鱼”吃“鳄鱼”的规则来设计语法，函数式编程语言就这样诞生了！

因此，如果您了解 Lambda 演算，您将了解函数式语言的工作原理。

于 2010-05-01T19:36:46.703 回答
14

Haskell 中处理状态的技术非常简单。而且您无需了解 monad 即可掌握它。

在具有状态的编程语言中，您通常会在某处存储一些值，执行一些代码，然后存储一个新值。在命令式语言中，这种状态只是“在后台”的某个地方。在（纯）函数式语言中，您将其明确化，因此您明确地编写了转换状态的函数。

因此，您不必编写某种 X 类型的状态，而是编写将 X 映射到 X 的函数。就是这样！您从考虑状态切换到考虑要对状态执行哪些操作。然后，您可以将这些功能链接在一起，并以各种方式将它们组合在一起以制作整个程序。当然，您不仅限于将 X 映射到 X。您可以编写函数以将各种数据组合作为输入，并在最后返回各种组合。

单子是帮助组织这一点的众多工具中的一种。但单子实际上并不是问题的解决方案。解决方案是考虑状态转换而不是状态。

这也适用于 I/O。实际上发生的情况是这样的：不是直接从用户那里获取输入scanf，然后将其存储在某个地方，而是编写一个函数来说明scanf如果你有结果你会做什么，然后传递它I/O API 的函数。这正是您在 Haskell 中>>=使用 monad 时所做的事情。IO所以你永远不需要在任何地方存储任何 I/O 的结果——你只需要编写代码来说明你想如何转换它。

于 2010-05-02T04:57:32.483 回答
8

（一些函数式语言允许不纯函数。）

对于纯函数式语言，现实世界的交互通常作为函数参数之一包含在内，如下所示：

RealWorld pureScanf(RealWorld world, const char* format, ...);

不同的语言有不同的策略来将世界从程序员那里抽象出来。例如，Haskell 使用 monad 来隐藏world参数。

但是函数式语言本身的纯部分已经是图灵完备的，这意味着在 C 中可行的任何事情在 Haskell 中也是可行的。命令式语言的主要区别在于，它不是在原地修改状态：

int compute_sum_of_squares (int min, int max) {
  int result = 0;
  for (int i = min; i < max; ++ i)
     result += i * i;  // modify "result" in place
  return result;
}

您将修改部分合并到函数调用中，通常将循环转换为递归：

int compute_sum_of_squares (int min, int max) {
  if (min >= max)
    return 0;
  else
    return min * min + compute_sum_of_squares(min + 1, max);
}
于 2010-05-01T19:43:41.607 回答
3

函数式语言可以保存状态！他们通常只是鼓励或强迫您明确表示这样做。

例如，查看 Haskell 的State Monad。

于 2010-05-01T19:43:26.660 回答
3

可能 对我们其他人有用，函数编程

于 2010-05-02T00:04:33.617 回答
1

哈斯克尔：

main = do no <- readLn
          print (no + 1)

您当然可以将事物分配给函数式语言中的变量。您只是无法更改它们（因此基本上所有变量都是函数式语言中的常量）。

于 2010-05-01T19:37:17.410 回答
0

如果函数式编程语言不能保存任何状态，那么它们如何做一些简单的事情，比如从用户那里读取输入[供以后使用]？

该语言可能不会，但它的实现肯定会！想想那里的所有状态——至少一个堆栈、一个或多个堆、各种文件描述符、当前配置等等。值得庆幸的是，处理所有这些的是计算机，而不是你。嗯 - 让计算机处理无聊的部分：多么好的概念！

以这种速度，实现将在任何一天承担所有沉闷的 I/O 活动——然后您将听到有关指称语言的信息……是的，更多的行话适合新手！但是现在，我们将专注于已经存在的东西——函数式语言：它们如何做简单的 I/O 工作，例如读取输入？

很小心！

大多数函数式语言与命令式语言的不同之处在于，只允许直接操作 I/O 的状态——您不能在定义中匿名定义一些额外的状态，例如记录它被使用的次数。为了防止这种情况发生，通常使用类型来区分基于 I/O 和无 I/O 的代码，Haskell和Clean广泛使用了该技术。

这可以很好地工作，甚至使函数式语言能够通过所谓的“外来函数接口”以命令式语言调用子例程过程。这允许将真正无限的以 I/O 为中心的操作（以及随之而来的基于 I/O 的状态的操作）引入到函数式语言中——scanf()这仅仅是开始……

...等一下：“以 I/O 为中心的操作确实无穷无尽”？有限的实现不可能包含所有这些，因此完全外延的语言在其程序的外部交互方面总是会受到某种方式的限制。因此，I/O 必须始终是任何通用编程语言的一部分。

于 2021-10-27T22:27:36.443 回答