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

Question

如果函数式编程语言不能保存任何状态,他们如何做一些简单的事情,比如从用户那里读取输入？他们如何"存储"输入(或存储任何数据？)

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

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

(我的问题受到了这篇优秀文章的启发:"名词王国的执行".阅读它让我更好地理解了什么是面向对象的编程,Java如何以一种极端的方式实现它,以及函数式编程语言是如何实现的对比.)

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"污染"的字符串,因为它是不纯的.第一个更正确,但第二个可能更有帮助.该<-取String出来的IO 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'

第一个允许我们讨论不执行任何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有点躲闪; 即使不是,它肯定不是那么优雅.根据Per @ Conal的观察,看看Simon Peyton-Jones在处理尴尬小队[pdf]中所说的内容,3.1节; 他提出了可能相当于这些方面的替代模型的东西,但随后因其复杂性而放弃它并采取不同的方法.

再次,这解释了(几乎)IO和一般的可变性如何在Haskell中工作; 如果你想知道这一切,你可以在这里停止阅读.如果你想要最后一剂理论,请继续阅读 - 但请记住,在这一点上,我们离你的问题已经走得很远了!

所以最后一件事:结果是这种结构 - 带有return和的参数类型>>=- 非常通用; 它被称为monad和do符号return,并>>=与它们中的任何一个一起工作.正如你在这里看到的那样,单子并不是神奇的; 所有这些神奇的是do块变成了函数调用.这种RealWorld类型是我们看到任何魔法的唯一地方.类似[]列表构造函数的类型也是monad,它们与不纯的代码无关.

你现在知道(几乎)关于monad概念的一切(除了一些必须满足的法则和正式的数学定义),但你缺乏直觉.在线有一些荒谬的monad教程; 我喜欢这个,但你有选择.但是,这可能对你没有帮助 ; 获得直觉的唯一真正方法是通过结合使用它们并在合适的时间阅读几个教程.

但是,您不需要那种直觉来理解IO.完全普遍地理解monad是锦上添花,但你现在可以使用IO.在我向您展示第一个main功能后,您可以使用它.您甚至可以将IO代码视为不纯净的语言!但请记住,有一个潜在的功能表示:没有人作弊.

(PS:对不起长度.我走得有点远.)

Answer 2

这里有很多好的答案,但它们很长.我将尝试给出一个有用的简短回答:

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

  • 在函数式语言中,"变量"在进入范围(通过函数调用或let-binding)时获取其初始值,并且该值在之后不会更改.类似地,在堆上分配的对象立即用其所有字段的值初始化,之后不会改变.

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

• IO通过技巧工作.产生字符串的副作用计算由一个以World作为参数的函数描述,并返回包含字符串和新World的对.世界包括所有磁盘驱动器的内容,发送或接收的每个网络数据包的历史记录,屏幕上每个像素的颜色以及类似的东西.诀窍的关键在于严格限制对世界的访问

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

  • 没有任何计划可以扔掉世界

  使用这个技巧可以创造一个独特的世界,其状态随着时间的推移而演变.语言运行时系统不是用函数式语言编写的,它通过更新唯一的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正在实现其目的:

开放问题:IOmonad已成为Haskell的罪魁祸首.(每当我们不理解某些东西时,我们就把它扔进IO monad.)

(来自Simon PJ的POPL演讲穿着头发衬衫戴着头发衬衫:回顾Haskell.)

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

然而,我们将采用基于过程计算语义的标准方法的操作语义.

找不到精确和有用的指称模型的失败是我为什么看到Haskell IO偏离精神和我们称之为"函数式编程"的深层利益,或者Peter Landin更具体地命名为"外延编程"的根本原因. . 在这里看评论.

Answer 4

功能编程源自lambda Calculus.如果您真的想了解功能编程,请查看http://worrydream.com/AlligatorEggs/

学习lambda微积分是一种"有趣"的方式,让您进入令人兴奋的功能编程世界!

了解Lambda微积分如何有助于函数式编程.

所以Lambda Calculus是许多真实编程语言的基础,例如Lisp,Scheme,ML,Haskell,....

假设我们想要描述一个为任何输入添加三个的函数,我们会写:

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视为" egg ".现在我们已经创建了两个函数或" Alligators ",我们可以这样做:

(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鳄鱼.

然后你就可以使用这个简单的" Alligators " 规则来吃 " Alligators "来设计一个语法,从而出现了函数式编程语言!

因此,您可以看到,如果您了解Lambda Calculus,您将了解Functional Languages的工作原理.

Answer 5

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

在具有状态的编程语言中,通常在某处存储某些值,执行某些代码,然后存储新值.在命令式语言中,这种状态只是"在后台"的某个地方.在(纯)函数语言中,您可以将其显式化,因此您可以显式编写转换状态的函数.

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

Monads是帮助组织这一工作的众多工具之一.但monad实际上并不是问题的解决方案.解决方案是考虑状态转换而不是状态.

这也适用于I/O. 实际上会发生这样的事情:不是从用户那里获得直接等效的输入scanf,而是将其存储在某个地方,而是编写一个函数来说明scanf如果你拥有了它你会做什么,然后传递给你功能到I/O API.这正是>>=你IO在Haskell中使用monad的原因.因此,您永远不需要在任何地方存储任何I/O的结果 - 您只需要编写说明您希望如何转换它的代码.

Answer 6

(某些功能语言允许不纯的功能.)

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

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

不同的语言有不同的策略来抽象世界,远离程序员.例如,Haskell使用monads来隐藏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);
}