动机:我希望能够在没有一阶函数的语言中使用玩具函数式编程，方法是使用自然数而不是函数。
通用函数是一个函数 f : N -> (N -> N)，相当于 f : N * N -> N 枚举所有可能的可计算函数。换句话说，有一个数字 k 使得 f(k) 是平方函数，有一个数字 j 使得 f(j) 是第 n 个素数函数等。
要编写这样一个函数，可以采用任何图灵完备的语言(编程语言编译器、lambda 演算、图灵机......)并枚举所有程序。我希望不仅允许评估，还允许对加法、合成、柯里化(Currying)等功能进行操作。例如，给定两个函数 f,g 的索引，我想知道函数 f+g 或由 g 组成的 f 的索引是什么。这将允许“玩具函数式编程”。
编写这样的代码库的好方法是什么？我不是在寻找难以计算 10 阶乘的简约 Turing tarpit，我也不想编写高级编译器。它应该具有一些基本功能，例如添加和编写循环的可能性，但仅此而已。
欢迎使用所有高级语言的解决方案。伪代码、Haskell 和 Python 是首选。您可以假设任意精度算术。使用 eval或类似的是不允许的。
澄清:枚举函数将包含所有 partial recursive (computable)那些 - 这包括不会在某些输入上停止的功能。在这种情况下，通用功能将挂起；当然这是不可避免的。另请参阅:m 递归函数 - http://en.wikipedia.org/wiki/Μ-recursive_function .
最佳答案
你想要的是一个解释器。
首先，任何具有您想要的属性的枚举都不适合您想要在前 2^32 甚至前 2^64 整数中操作的有趣函数。因此，您将需要更大的整数，分配在内存中的某个位置并通过指针引用。
那么，为什么不在任何现有语法中使用表示程序的字符(字符串)数组呢？
如果这让您满意，可以将这样的字符串视为整数。要计算的函数数f1()+f2()是由(f1 的表示)、“+”和(f2 的表示)组成的字符串。你明白了……
这种方法没有的是函数表示的唯一性，这可能暗示在您的问题中(我不确定)。我可以肯定的是，表示的唯一性与对函数表示的简单甚至可计算的组合操作是不相容的——例如，如果不是这种情况，就会有一个简单的解决方案来解决停止问题。
关于language-agnostic - 如何编写所有可计算函数的枚举？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/1797457/