函数式编程语言如何工作？

Question

如果函数式编程语言无法保存任何状态，那么它们如何执行简单的操作，例如读取用户的输入？它们如何“存储”输入（或存储与此相关的任何数据？）

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

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

（我的问题受到这篇优秀帖子的启发：《名词王国中的执行》。阅读它让我更好地理解了面向对象编程到底是什么、Java 如何以一种极端的方式实现它，以及函数式编程语言的对比。）< /em>

Answer 1

如果函数式编程语言无法保存任何状态，那么它们如何做一些简单的事情，例如读取用户的输入（我的意思是它们如何“存储”它），或存储与此相关的任何数据？

正如您所了解的，函数式编程没有状态，但这并不意味着它不能存储数据。不同之处在于，如果我按照以下方式编写（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 返回一个 IO String，可以通过两种方式来考虑它：首先，作为一个操作，在运行时生成一个字符串；第二，作为一个操作，在运行时生成一个字符串。其次，作为一个被 IO“污染”的字符串，因为它是不纯粹获取的。第一个更正确，但第二个可能更有帮助。 <- 从 IO String 中取出 String 并将其存储在 str 中 - 但因为我们'当处于 IO 操作中时，我们必须将其重新包装起来，这样它就无法“逃逸”。下一行尝试读取一个整数 (reads) 并获取第一个成功的匹配项 (fst . head)；这都是纯粹的（无 IO），因此我们用 let no = ... 为其命名。然后我们可以在 ... 中同时使用 no 和 str。因此，我们存储了不纯数据（从 getLine 到 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'

第一个函数允许我们讨论不执行任何操作的 IO 操作：return 3 是一个不执行任何操作的 IO 操作查询现实世界并仅返回3。 >>= 运算符，发音为“bind”，允许我们运行 IO 操作。它从 IO 操作中提取值，通过函数将其与现实世界一起传递，然后返回结果 IO 操作。请注意，>>= 强制执行我们的规则，即永远不允许 IO 操作的结果逃逸。

然后，我们可以将上面的 main 转换为以下一组普通的函数应用程序：

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

Haskell 运行时以初始 RealWorld 跳转启动 main，并且我们准备好了！一切都很纯粹，只是有一个奇特的语法。

[编辑：正如@Conal指出的< /a>，这实际上并不是Haskell用来做IO的。如果你添加并发性，或者在 IO 操作中添加任何改变世界的方式，这个模型就会被破坏，所以 Haskell 不可能使用这个模型。它仅对于顺序计算是准确的。因此，Haskell 的 IO 可能有点躲闪；即使不是，它也肯定没有这么优雅。根据 @Conal 的观察，请参阅 Simon Peyton-Jones 在 解决尴尬的小队问题 [pdf]，第 3.1 节；他沿着这些思路提出了可能相当于替代模型的东西，但随后由于其复杂性而放弃了它并采取了不同的策略

。如果这就是您想知道的一切，您可以停止阅读此处。如果您想要最后一剂理论，请继续阅读 - 但请记住，在这一点上，我们已经离您的问题非常远了！

最后一件事：事实证明，这种结构（带有 return 和 >>= 的参数类型）非常通用；它称为 monad，do 表示法、return 和 >>= 可以与其中任何一个一起使用。正如您在这里所看到的，单子并不神奇；它是由单子组成的。神奇之处在于 do 块会变成函数调用。 RealWorld 类型是我们唯一能看到魔法的地方。像 [] 这样的类型（列表构造函数）也是 monad，它们与不纯的代码无关。

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

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

（PS：抱歉，篇幅太长了。我扯得有点远了。）

Answer 2

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

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

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

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

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

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

  • 没有程序可以抛弃世界

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

  西蒙·佩顿·琼斯 (Simon Peyton Jones) 和菲尔·瓦德勒 (Phil Wadler) 在他们的里程碑式论文中对这一技巧进行了精彩的解释 “命令式函数式编程”。

Answer 3

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

我写道：

据我所知，这个 IO 故事 (World -> (a,World)) 在应用于 Haskell 时是一个神话，正如该模型所解释的那样仅纯粹的顺序计算，而 Haskell 的 IO 类型包括并发。通过“纯顺序”，我的意思是，除了由于该计算之外，甚至世界（宇宙）都不允许在命令式计算的开始和结束之间发生变化。例如，当您的计算机正在运转时，您的大脑等却无法运转。并发可以通过类似于 World ->; 的方式来处理。 PowerSet [(a,World)]，允许不确定性和交错。

诺曼写道：

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

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

开放问题：IO monad 已成为 Haskell 的 sin-bin。 （每当我们不理解某些东西时，我们就把它扔进 IO monad 中。）

（摘自 Simon PJ 的 POPL 演讲 穿着 Hair 衬衫穿着 Hair 衬衫：Haskell 回顾。）

解决尴尬小队，西蒙指出了什么对于 type IO a = World -> 不起作用(a, World)，包括“当我们添加并发性时，该方法无法很好地扩展”。然后他提出了一种可能的替代模型，然后放弃了指称解释的尝试，说

但是，我们将采用基于过程计算语义的标准方法的操作语义。

这种未能找到精确的&有用的指称模型是我认为 Haskell IO 背离了我们所谓的“函数式编程”（或者 Peter Landin 更具体地称为“指称编程”）的精神和深层好处的根本原因。 在此处查看评论。

Answer 4

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

这是一个“有趣”的方式来学习 lambda 微积分，带您进入令人兴奋的函数式编程世界！

了解 Lambda 演算对函数式编程有何帮助。

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

假设我们想要描述一个将 3 与任何输入相加的函数，我们可以这样写：

plus3 x = succ(succ(succ x)) 

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

请注意，该函数将 3 与任何数字相加数字不必命名为 plus3；名称“plus3”只是命名此函数的方便简写

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

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

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

现在考虑抽象：

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

参数 f 用于函数位置（在调用中）。
我们将 ga 称为高阶函数，因为它需要另一个函数作为输入。
您可以将其他函数调用 f 视为“eggs”。
现在，利用我们创建的两个函数或“鳄鱼”，我们可以执行以下操作：

(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 鳄鱼吃掉了 λ x 鳄鱼，然后 λ x 鳄鱼就死了。然后我们的 λ x 鳄鱼在 λ f 的鳄鱼蛋中重生。然后重复这个过程，左边的 λ x 鳄鱼现在吃掉右边的另一只 λ x 鳄鱼。

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

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

Answer 5

Haskell 中处理状态的技术非常简单。而且你不需要了解 monad 来掌握它。

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

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

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

这也适用于 I/O。实际上发生的情况是这样的：您不是使用 scanf 的直接等效项从用户那里获取输入并将其存储在某个地方，而是编写一个函数来说明您将如何处理 < code>scanf（如果有），然后将该函数传递给 I/O API。这正是当您在 Haskell 中使用 IO monad 时 >>= 所做的事情。因此，您永远不需要在任何地方存储任何 I/O 的结果 - 您只需要编写代码来说明您希望如何转换它。

Answer 6

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

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

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);
}

Answer 7

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

例如，查看 Haskell 的 State Monad。

Answer 8

可能有用，
面向我们其他人的函数编程

Answer 9

haskell：

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

你当然可以用函数式语言将东西赋值给变量。你只是无法改变它们（所以基本上所有变量都是函数语言中的常量）。

Answer 10

如果函数式编程语言无法保存任何状态，那么它们如何执行简单的操作，例如读取用户的输入[以供以后使用]？

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

按照这个速度，实现现在任何一天都将承担所有沉闷的 I/O 活动 - 然后你将听到外延语言...是的，还有更多针对新手的行话！但现在，我们将重点关注已经存在的功能 - 函数式语言：它们如何执行简单的 I/O 操作，例如读取输入？

非常小心！

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

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

---

^{...等一下：“真正无限的以 I/O 为中心的操作”？ 有限的实现不可能容纳所有这些，因此完全指示性语言将始终受到限制某种方式涉及其程序的外部交互。因此，I/O 必须始终是任何通用编程语言的一部分。}