函数式编程是如何在底层实现的？

Question

Haskell、Scala、...和函数式编程语言一般是如何在底层实现的？也就是说，如果是冯·诺依曼，计算机实际上如何运行一个功能程序？代码是怎么翻译的（一般是解释型，不知道有没有编译型函数式语言）？

Answer 1

简答：

通过将功能转换为动作序列（某些虚拟机或真实机器中的指令）。

更长的答案：

考虑这个函数式程序，使用 Lisp 符号来使我们摆脱句法困难：

;; function definitions
(defun square (x) (* x x))
(defun difference (a b)
  (if (> a b)
    (- a b)
    (- b a)))
;; actual program
(difference (square 5) 5)

假设严格（不是惰性）评估，在计算 difference 之前，您显然需要计算 square。概括这个想法意味着为了计算一个函数，你首先需要计算它的参数。计算参数的顺序可能未指定，但为了简单起见，我们假设它们是从左到右计算的。然后，您可以将上面的程序（省略函数定义）转换为以下命令式描述：

1: use value 5 as parameter
2: call square using 1 parameter, use result as parameter
3: use value 5 as parameter
4: call difference using 2 parameters

例如，对于基于堆栈的机器，可以相对容易地编译此操作序列：

square:
   dup ; duplicate top of stack
   mul ; pops 2 numbers from stack, multiplies them and pushes the result
   ret

difference:
   compare_greater_than ; uses the top 2 numbers from stack, pushes result
   jmpif L ; pops 1 number from stack, jumps if non zero
   swap ; swap top 2 numbers on stack
L: sub
   ret

main:
   push 5
   call square
   push 5
   call difference

当然，这只是一个非常粗略的草图，但希望能让您了解从哪里开始。我在这里的其他两个答案中实施了 as well as a more 。两者都是解释函数式程序的示例。

然后，还有关于如何实际实现函数式语言的很好的教程，例如 http://www.buildyourownlisp.com/。

我的回答完全集中在 "practical" 方法上。还有很多我完全遗漏的理论，比如 spineless tagless G-machine、向连续传递样式的转换或一些严肃的图表内容，但我希望我的回答能让你知道从哪里开始。

Answer 2

你犯了逻辑谬误，当你问：

That is, how a computer can actually run a functional program if it's Von Neumann?

但是我们的计算机可以计算任何可以计算的东西，无论硬件架构如何。这就好像你在问：当计算机由电子元素组成时，它如何帮助化学。

函数式编程是如何在底层实现的？

How is functional programming implemented in low level?

functional-programming

low-level

简答：

更长的答案：