函数式编程语言如何工作？ [英] How do functional programming languages work?

问题描述

如果函数式编程语言不能保存任何状态，他们如何做简单的事情，比如读取用户的输入？他们如何存储输入（或存储任何数据）？例如：这个简单的C函数将如何转化为像Haskell这样的函数式编程语言？

  #include< stdio.h> 
 int main（）{
 int no; 
 scanf（％d，& no）; 
返回0; 
 
  

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

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

正如你所收集的，函数式编程没有状态—但是，意味着它不能存储数据。不同之处在于，如果我按照

  let x = func值3.14 20random的顺序编写一条（Haskell） 
 in ... 
  

我保证 x 在 ... 中总是相同的：没有东西可以改变它。同样，如果我有一个函数 f :: String - >整数（一个函数接受一个字符串并返回一个整数），我可以确定 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字符串，这可以认为有两种方式：首先，运行时产生一个字符串;其次，它是一个被IO污染的字符串，因为它是不纯的获得的。第一个更正确，但第二个可能更有帮助。 < - 将字符串从 IO字符串 >并将其存储在 str —但由于我们处于IO操作中，因此我们必须将其重新包装起来，因此它不能转义。下一行尝试读取一个整数（读取）并抓取第一个成功匹配（ fst。head ）;这是纯粹的（没有IO），所以我们用 let no = ... 来给它命名。我们可以在 ... no 和 str C>。因此，我们存储了不纯的数据（从 getLine 到 str ）和纯数据（ let no = ... ）。

这种使用IO的机制非常强大：它可以让您将纯粹的算法部分程序来自不纯的用户交互方面，并在类型级别执行此操作。你的 minimumSpanningTree 函数不可能改变代码中其他地方的东西，或者给你的用户写一条消息，等等。这是安全的。

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

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

  return :: a  - > IO a 
返回a = \ rw  - > （a，rw）
 
（>> =）:: IO a  - > （a→IO b）→> IO b 
 ioa>> = fn = \ rw  - >让（a，rw'）= ioa rw in fn a rw'
  

第一个允许我们讨论IO操作，它不会执行任何操作： return 3 是一个IO操作，它不查询真实世界并返回 3 。 >> = 操作符，发音为bind，允许我们运行IO操作。它从IO操作中提取值，通过函数传递它和现实世界，并返回生成的IO操作。请注意，>> = 强制执行我们的规则，即IO操作的结果永远不会被允许转义。


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



  main = getLine>> = \str  - > let $ =（fst。head $ reads str :: Integer）in ... 
  

Haskell运行时使用初始 RealWorld 跳转启动 main ，然后我们设置！一切都是纯粹的，它只是一个花哨的语法。

$ b [编辑： 解决Awkward Squad [pdf] 第3.1节;他提出了什么可能相当于一个替代模式沿着这些线，但然后放弃它的复杂性，并采取不同的方式。]

再次，这解释（几乎）一般来说，IO和可变性在Haskell中是如何工作的;如果 是你想知道的所有内容，你可以在这里停止阅读。如果你想要最后一剂理论，请继续阅读 - 但请记住，在这一点上，我们离你的问题还有很远的距离！所以最后一件事：它变成了这个结构 - 一个参数类型，它带有 return 和>> = —非常一般;它叫做monad， do 表示法， return 和>> = 可以与其中任何一个配合使用。正如你在这里看到的，单子不是神奇的;所有这一切都很神奇，因为 do 块会变成函数调用。 RealWorld 类型是我们看到魔法的唯一地方。像 [] 这样的列表构造函数也是monad，它们与不纯代码无关。

你现在几乎都知道monad的概念（除了必须满足的几个定律和正式的数学定义），但是你缺乏直觉。网上有一些荒谬的monad教程，我喜欢这一个，但你有选择。然而，这可能不会帮助你;获得直觉的唯一方法是通过使用它们并在正确的时间阅读一对夫妇教程的组合。然而，你并不需要直觉了解IO 。全面了解monad是锦上添花，但你现在可以使用IO。在我向您展示第一个 main 函数后，您可以使用它。您甚至可以将IO代码视为不纯的语言！但请记住，有一个潜在的功能表示：没有人在欺骗。

（PS：对不起，我走了很远。）

If functional programming languages cannot save any state, how do they do simple stuff like reading input from a user? How do they "store" the input (or store any data for that matter?)

For example: how would this simple C thing translate to a functional programming language like Haskell?

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

(My question was inspired by this excellent post: "Execution in the Kingdom of Nouns". Reading it gave me some better understanding of what exactly object oriented programming is, how Java implements it in one extreme manner, and how functional programming languages are a contrast.)

解决方案

If functional programming languages cannot save any state, how do they do some simple stuff like reading input from a user (I mean how do they "store" it), or storing any data for that matter?

As you gathered, functional programming doesn't have state—but that doesn't mean it can't store data. The difference is that if I write a (Haskell) statement along the lines of

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

I am guaranteed that the value of x is always the same in the ...: nothing can possibly change it. Similarly, if I have a function f :: String -> Integer (a function taking a string and returning an integer), I can be sure that f will not modify its argument, or change any global variables, or write data to a file, and so on. As sepp2k said in a comment above, this non-mutability is really helpful for reasoning about programs: you write functions which fold, spindle, and mutilate your data, returning new copies so you can chain them together, and you can be sure that none of those function calls can do anything "harmful". You know that x is always x, and you don't have to worry that somebody wrote x := foo bar somewhere in between the declaration of x and its use, because that's impossible.

Now, what if I want to read input from a user? As KennyTM said, the idea is that an impure function is a pure function that's passed the entire world as an argument, and returns both its result and the world. Of course, you don't want to actually do this: for one thing, it's horribly clunky, and for another, what happens if I reuse the same world object? So this gets abstracted somehow. Haskell handles it with the IO type:

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

This tells us that main is an IO action which returns nothing; executing this action is what it means to run a Haskell program. The rule is that IO types can never escape an IO action; in this context, we introduce that action using do. Thus, getLine returns an IO String, which can be thought of in two ways: first, as an action which, when run, produces a string; second, as a string that's "tainted" by IO since it was obtained impurely. The first is more correct, but the second can be more helpful. The <- takes the String out of the IO String and stores it in str—but since we're in an IO action, we'll have to wrap it back up, so it can't "escape". The next line attempts to read an integer (reads) and grabs the first successful match (fst . head); this is all pure (no IO), so we give it a name with let no = .... We can then use both no and str in the .... We've thus stored impure data (from getLine into str) and pure data (let no = ...).

This mechanism for working with IO is very powerful: it lets you separate the pure, algorithmic part of your program from the impure, user-interaction side, and enforce this at the type level. Your minimumSpanningTree function can't possibly change something somewhere else in your code, or write a message to your user, and so on. It's safe.

This is all you need to know to use IO in Haskell; if that's all you want, you can stop here. But if you want to understand why that works, keep reading. (And note that this stuff will be specific to Haskell—other languages may choose a different implementation.)

So this probably seemed like a bit of a cheat, somehow adding impurity to pure Haskell. But it isn't—it turns out that we can implement the IO type entirely within pure Haskell (as long as we're given the RealWorld). The idea is this: an IO action IO type is the same as a function RealWorld -> (type, RealWorld), which takes the real world and returns both an object of type type and the modified RealWorld. We then define a couple functions so we can use this type without going insane:

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'

The first one allows us to talk about IO actions which don't do anything: return 3 is an IO action which doesn't query the real world and just returns 3. The >>= operator, pronounced "bind", allow us to run IO actions. It extracts the value from the IO action, passes it and the real world through the function, and returns the resulting IO action. Note that >>= enforces our rule that the results of IO actions never be allowed to escape.

We can then turn the above main into the following ordinary set of function applications:

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

The Haskell runtime jump-starts main with the initial RealWorld, and we're set! Everything's pure, it just has a fancy syntax.

[Edit: As @Conal points out, this is not actually what Haskell uses to do IO. This model breaks if you add concurrency, or indeed any way for the world to change in the middle of an IO action, so it would be impossible for Haskell to use this model. It is accurate only for sequential computation. Thus, it may be that Haskell's IO is a bit of a dodge; even if it isn't, it's certainly not quite this elegant. Per @Conal's observation, see what Simon Peyton-Jones says in Tackling the Awkward Squad [pdf], section 3.1; he presents what might amount to an alternative model along these lines, but then drops it for its complexity and takes a different tack.]

Again, this explains (pretty much) how IO, and mutability in general, works in Haskell; if this is all you want to know, you can stop reading here. If you want one last dose of theory, keep reading—but remember, at this point, we've gone really far afield from your question!

So the one last thing: it turns out this structure—a parametric type with return and >>=— is very general; it's called a monad, and the do notation, return, and >>= work with any of them. As you saw here, monads aren't magical; all that's magical is that do blocks turn into function calls. The RealWorld type is the only place we see any magic. Types like [], the list constructor, are also monads, and they have nothing to do with impure code.

You now know (almost) everything about the concept of a monad (except a few laws that must be satisfied and the formal mathematical definition), but you lack the intuition. There are a ridiculous number of monad tutorials online; I like this one, but you have options. However, this probably won't help you; the only real way to get the intuition is via a combination of using them and reading a couple tutorials at the right time.

However, you don't need that intuition to understand IO. Understanding monads in full generality is icing on the cake, but you can use IO right now. You could use it after I showed you the first main function. You can even treat IO code as though it was in an impure language! But remember that there's an underlying functional representation: nobody's cheating.

(PS: Sorry about the length. I went a little far afield.)

这篇关于函数式编程语言如何工作？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！