有人可以用外行的方式解释什么是函数式语言？

Question

可能重复:
功能编程和非功能编程

我担心维基百科没有给我带来任何进一步的信息.非常感谢

PS:这个过去的帖子也很好,不过我很高兴我再次问这个问题,因为新答案很棒 - 谢谢

功能编程和非函数编程

Answer 1

首先要了解图灵机是什么(来自维基百科).

图灵机是根据规则表操纵条带上的符号的设备.尽管它很简单,但图灵机可以适用于模拟任何计算机算法的逻辑,并且在解释计算机内部CPU的功能时特别有用.

这是关于Lamda演算.(来自维基百科).

在数学逻辑和计算机科学中,lambda演算也被称为λ演算,是用于研究可计算递归函数的正式系统,可计算性理论以及诸如变量绑定和替换的相关现象.

函数式编程语言使用lambda演算作为其基本计算模型,而所有其他编程语言使用图灵机作为其基本计算模型.(从技术上讲,我应该说函数式编程语言vr.s 命令式编程语言 - 其他范例中的语言使用其他模型.例如,SQL使用关系模型,Prolog使用逻辑模型,等等.人们在讨论编程语言时实际考虑的所有语言都是功能性的或必要的,所以我会坚持简单的通用性.)

"基本计算模型"是什么意思？好吧,所有语言都可以分为两层:一个是图灵完整语言的核心,然后是抽象或语法糖的层次(取决于你是否喜欢它们),它们是用基础图灵定义的 - 完整的语言.命令式语言的核心语言是经典的图灵机器计算模型的变体,可以称之为"C语言".在这种语言中,内存是一个可以读取和写入的字节数组,并且您有一个或多个读取内存,执行简单算术,分支条件等的CPU.这就是我对这些语言的基本计算模型的意思是图灵机.

函数式语言的基本计算模型是Lambda微积分,它以两种不同的方式显示.首先,许多函数式语言所做的一件事是根据对lambda演算的转换来明确地编写它们的规范,以指定用该语言编写的程序的行为(这称为"指称语义").和第二,几乎所有的函数式编程语言实现自己的编译器使用显式的λ演算般的中间语言- 哈斯克尔具有核心,Lisp的和计划有自己的"脱"表示(已应用于所有宏之后),ocaml的(目标范畴摘要机器语言)它具有低级中间表示,等等.

那么我一直在讨论的这个lambda演算是什么？嗯,基本的想法是,要做任何计算,你只需要两件事.您需要的第一件事是函数抽象 - 一个未命名的单参数函数的定义.首先定义Lambda演算的Alonzo Church使用相当模糊的符号将函数定义为希腊字母lambda,然后是函数参数的单字符名称,后跟一个句点,然后是表达式,即身体的功能.因此,赋予任何值的身份函数只返回该值,看起来像"λx.x"我将使用稍微更人性化的方法 - 我将用"有趣的",带有" - >"的句号,并允许空格并允许多字符名称.所以我可能会将身份函数写成"fun x - > x",甚至是"fun what - > whatever".符号的改变不会改变基本性质.请注意,这是引用未命名的本地函数的Haskell和Lisp-表达式等语言中名称"lambda expression"的来源.

在Lambda微积分中你唯一能做的就是调用函数.通过对其应用参数来调用函数.我将遵循标准约定,即应用程序只是连续的两个名称 - 所以f x将值x应用于名为f的函数.我们可以用一些其他表达式替换f,包括一个Lambda表达式,如果我们想要 - 我们可以当你将一个参数应用于一个表达式时,用一个函数的主体替换应用程序,替换所有出现的参数名称无论应用什么价值.所以表达(fun x -> x x) y成了y y.

理论家们竭尽全力通过"用所应用的值替换变量的所有出现"来精确定义它们的含义,并且可以继续研究它的精确程度(抛出像"alpha renaming"这样的术语),但最终事情的工作方式与你期望的完全一样.表达式(fun x -> x x) (x y)变为(x y) (x y)- x匿名函数x中的参数与应用的值之间没有混淆.这甚至可以在多个级别中起作用 - 表达式(fun x -> (fun x -> x x)) (x x)) (x y)首先成为(fun x -> x x) ((x y) (x y))然后((x y) (x y)) ((x y) (x y)).最里面的函数(“(fun x -> x x)”)中的x是与其他x不同的x.

将函数应用程序视为字符串操作是完全有效的.如果我有一个(有趣的x - >某个表达式),并且我对它应用了一些值,那么结果只是一些表达式,所有x的文本替换为"some value"(除了被另一个参数遮蔽的那些) ).

顺便说一句,我会在需要消除歧义的地方添加括号,并在不需要的地方省略它们.他们唯一的区别是分组,他们没有其他意义.

这就是Lambda演算的全部内容.不,真的,这只是匿名函数抽象和函数应用程序.我可以看到你对此表示怀疑,所以让我解决你的一些担忧.

首先,我指定一个函数只接受一个参数 - 你如何拥有一个带有两个或更多参数的函数？容易 - 你有一个带有一个参数的函数,并返回一个带第二个参数的函数.例如,函数组合可以定义为fun f -> (fun g -> (fun x -> f (g x)))- 读取作为接受参数f的函数,并返回一个接受参数g的函数,并返回一个带参数x并返回f(gx)的函数.

那么我们如何仅使用函数和应用程序来表示整数呢？很容易(如果不是很明显) - 例如,第一个是一个函数fun s -> fun z -> s z- 给定一个"后继"函数s和一个"零"z,然后一个是零的后继者.两个是有趣的s - > fun z -> s s z,继承者的继承者为零,三个是fun s -> fun z -> s s s z,依此类推.

如果微妙的话x,添加两个数字,比如说y,又简单了.添加功能正好fun x -> fun y -> fun s -> fun z -> x s (y s z).这看起来很奇怪,所以让我通过一个例子来说明它确实如此,实际上工作 - 添加数字3和2.现在,三个只是(fun s -> fun z -> s s s z)两个就是(fun s -> fun z -> s s z),所以我们得到(每一步应用一个参数一个函数,没有特别的顺序):

(fun x -> fun y -> fun s -> fun z -> x s (y s z)) (fun s -> fun z -> s s s z) (fun s -> fun z -> s s z)

(fun y -> fun s -> fun z -> (fun s -> fun z -> s s s z) s (y s z)) (fun s -> fun z -> s s z)

(fun y -> fun s -> fun z -> (fun z -> s s s z) (y s z)) (fun s -> fun z -> s s z)

(fun y -> fun s -> fun z -> s s s (y s z)) (fun s -> fun z -> s s z)

(fun s -> fun z -> s s s ((fun s -> fun z -> s s z) s z))

(fun s -> fun z -> s s s (fun z -> s s z) z)

(fun s -> fun z -> s s s s s z) 

最后,我们得到了接班人继任者继任者的接班人的不足为奇的答案,继承人是零的继承者,更通俗地称为五人.加建工程通过替换zero的(或者我们开始算起)x与值y值-定义乘法,我们不是用"接班人"的概念,骗取:

(fun x -> fun y -> fun s -> fun z -> x (y s) z)

我会留给你验证上面的代码

维基百科说

命令式程序倾向于强调程序在执行操作时采取的一系列步骤,而功能程序往往强调功能的组成和安排,通常不指定明确的步骤.一个简单的例子用两个解决方案来说明相同的编程目标(计算Fibonacci数).命令式示例是在C++中.

// Fibonacci numbers, imperative style
int fibonacci(int iterations)
{
    int first = 0, second = 1; // seed values

    for (int i = 0; i < iterations; ++i) {
        int sum = first + second;
        first = second;
        second = sum;
    }

    return first;
}

std::cout << fibonacci(10) << "\n";

功能版本(在Haskell中)有不同的感觉:

-- Fibonacci numbers, functional style

-- describe an infinite list based on the recurrence relation for Fibonacci numbers
fibRecurrence first second = first : fibRecurrence second (first + second)

-- describe fibonacci list as fibRecurrence with initial values 0 and 1
fibonacci = fibRecurrence 0 1

-- describe action to print the 10th element of the fibonacci list
main = print (fibonacci !! 10)

另见PDF