functional-programming - 有人可以用通俗的语言解释什么是函数式语言吗？

Question

这个问题在这里已经有了答案:




9年前关闭。

Possible Duplicate:
Functional programming and non-functional programming

恐怕维基百科没有给我带来任何进一步的信息。
非常感谢

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

Functional programming and non-functional programming

Answer 1

首先了解 Turing machine 是什么(来自维基百科)。

A Turing machine is a device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a computer.

这大约是 Lamda calculus.(来自维基百科)。

In mathematical logic and computer science, the lambda calculus, also written as the λ-calculus, is a formal system for studying computable recursive functions, a la computability theory, and related phenomena such as variable binding and substitution.

函数式编程语言使用 lambda 演算作为它们的基本计算模型，而所有其他编程语言使用图灵机作为它们的基本计算模型。 (好吧，从技术上讲，我应该说函数式编程语言 vr.s imperative programming 语言 - 因为其他范式中的语言使用其他模型。例如，SQL 使用关系模型，Prolog 使用逻辑模型等等。但是，几乎所有人们在讨论编程语言时实际考虑的语言要么是函数式的，要么是命令式的，所以我会坚持简单的概括。)

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

函数式语言的基本计算模型是 Lambda 演算，这表现为两种不同的方式。首先，许多函数式语言所做的一件事是根据对 lambda 演算的转换明确地编写它们的规范，以指定用该语言编写的程序的行为(这称为“指称语义”)。其次，几乎所有的函数式编程语言都实现了它们的编译器，以使用类似 lambda 演算的显式中间语言 - Haskell 有 Core，Lisp 和 Scheme 有它们的“脱糖”表示(在应用了所有宏之后)，Ocaml (Objective Categorical Abstract Machine Language) 有它的 lispish 中间语言代表等。

那么我一直在讨论的这个 lambda 演算是什么？嗯，基本思想是，要进行任何计算，您只需要两件事。您需要的第一件事是函数抽象——未命名的单参数函数的定义。首先定义 Lambda 演算的 Alonzo Church 使用相当晦涩的符号将函数定义为希腊字母 lambda，后跟函数参数的单字符名称，后跟一个句点，然后是作为函数体。因此，给定任何值的恒等函数只是简单地返回该值，看起来像“λx.x”。我将使用一种更易读的方法——我将用单词“替换 λ 字符” fun”，句点带有“->”，并允许空格和多字符名称。所以我可以把恒等函数写成“fun x -> x”，甚至“fun what -> what”。符号的变化不会改 rebase 本性质。请注意，这是引入未命名本地函数的 Haskell 和 Lisp 表达式等语言中名称“lambda 表达式”的来源。

您可以在 Lambda 演算中做的另一件事是调用函数。您可以通过对其应用参数来调用函数。我将遵循标准约定，即应用程序只是一行中的两个名称 - 因此 f x 将值 x 应用于名为 f 的函数。如果需要，我们可以用其他一些表达式(包括 Lambda 表达式)替换 f 并且我们可以在将参数应用于表达式时，将应用程序替换为函数体，并替换所有出现的参数名称应用任何值。所以表达式 (fun x -> x x) y 变成了 y y 。

理论家们竭尽全力通过“用应用的值替换所有出现的变量”来精确定义他们的意思，并且可以详细说明这是如何精确工作的(抛出诸如“alpha重命名”之类的术语)，但最终事情会像你期望的那样工作。表达式 (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 不同。

将函数应用程序视为字符串操作是完全有效的。如果我有一个 (fun x -> some expression)，并且我对其应用了一些值，那么结果只是一些表达式，其中所有 x 的文本都被替换为“某个值”(除了那些被另一个参数遮蔽的值) )。

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

这就是 Lambda 演算的全部内容。不，真的，这只是匿名函数抽象和函数应用程序。我可以看出你对此持怀疑态度，所以让我来解决你的一些担忧。

首先，我指定一个函数只接受一个参数——你怎么会有一个接受两个或更多参数的函数？很简单——你有一个接受一个参数的函数，并返回一个接受第二个参数的函数。例如，函数组合可以定义为 fun f -> (fun g -> (fun x -> f (g x))) - 将其读作一个接受参数 f 的函数，并返回一个接受参数 g 的函数并返回一个接受参数 x 并返回 f (g x) 的函数。

那么我们如何仅使用函数和应用程序来表示整数呢？很容易(如果不是很明显)——例如，第一个函数是函数 fun s -> fun z -> s z——给定一个“后继”函数 s 和一个“零”z，那么 1 就是 0 的后继函数。二是 fun 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)

我会让你来验证上面的代码

Wikipedia says

Imperative programs tend to emphasize the series of steps taken by a program in carrying out an action, while functional programs tend to emphasize the composition and arrangement of functions, often without specifying explicit steps. A simple example illustrates this with two solutions to the same programming goal (calculating Fibonacci numbers). The imperative example is in 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)

See this PDF also