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

Question

Haskell、Scala 等以及函数式编程语言一般是如何在低层实现的？也就是说，如果是冯·诺依曼，计算机如何真正运行功能程序？代码是如何翻译的(一般是解释型，不知道有没有编译型函数式语言)？

Answer 1

简短回答:

通过将函数转换为 Action 序列(某些虚拟机或真实机中的指令)。

更长的答案:

考虑这个函数式程序，使用 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)

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

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

当然，这只是一个非常粗略的草图，但希望能让您了解从哪里开始。我已经实现了a small sketch以及更多complete version在我的其他两个答案中。两者都是解释函数式程序的示例。

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

我的回答完全侧重于“实用”方法。还有很多理论我完全省略了，比如 spineless tagless G-machine ，转换为连续传递风格或一些严肃的图形内容，但我希望我的回答能让您知道从哪里开始。