gra*_*ski 15 haskell functional-programming
根据维基百科的说法,从lambda演算到组合逻辑的翻译是微不足道的.连接编程语言可以仅依靠堆栈进行内存分配.
什么阻止GHC将Haskell转换为连接编程语言,例如组合逻辑,然后简单地使用堆栈分配来处理所有事情？
这种翻译是否可行,从而消除了Haskell和OCaml等语言的垃圾收集？这样做有缺点吗？
小智 7
假设我有一个生成某种大小的链表的函数.大小是函数参数.
问题是:我在哪里为列表分配内存？我无法在函数堆栈上分配它,因为它在函数外出后无效.我无法在调用者的堆栈上分配它,因为我不知道在函数调用之前需要分配多少内存.所以我需要在堆上分配它.
我认为可能有RAII手动堆管理可用,但我根本看不到如何消除堆分配.
我无法将所有想法都纳入评论中,所以我在这里写下来.
基于堆栈的分配语言没有神奇之处.您仍需要知道数据何时相关,如果不相关则将其删除.
想象一下,你有一个单独的堆栈,你的功能可以控制推送和弹出数据.首先,不再有自动内存管理,即函数终止但数据不会自动解除分配.其次,如果你的函数分配了一些内存,需要支持例如列表计算,那么所有这些东西都会被你想要返回的列表改组.没有机会你可以释放未使用的内存(其他列表,树木等),因为你只需要推送和弹出操作.如果你有其他操作,那么与堆有什么区别？
几堆,而不是一堆？
你需要在某个地方分配它们,管理它们的增长,有时还能让它们恢复.这些堆栈是您需要手动管理的独立结构.没有自动内存管理.
基于堆栈的语言是可以的,但是忘记了大量的算法,这些算法是用"从某个地方获取内存"和"放回内存"这个概念发明的,比如哈希映射,红黑树,链表.当然,我们可以在堆栈上分配所有这些结构,但如果它们不再需要,我们就无法释放它们的部分.
怎么样"平凡"的lambda演算翻译到图灵机？
当然,如果你的资源是无限的,这是微不足道的.数学理论没有澄清这种翻译结构的时间和记忆复杂性.它只是认为这两个模型是等价的,我们可以用图灵机说的所有我们可以用lambda演算来说,反之亦然.不能保证它可以适应现实生活中的限制.
连接编程语言能够作为函数式编程语言耗尽内存.
垃圾收集地址的基本挑战是释放未以或不知道以类似堆栈的方式使用的内存.当源代码中没有明确的位置可以精确定位为对象生命周期的末尾时,它尤其有用.
如果您只是将函数式语言转换为只有堆栈分配的连接语言,那么您最终会溢出堆栈.
多年来,为了减少垃圾收集的需要,已经进行了各种努力.一个有趣(但非常复杂)的尝试是ML Kit中使用的区域推理系统.不幸的是,对于包括我自己在内的大多数程序员来说,这有点了解.我相信其他人一直在研究这样的系统; 我不知道目前的技术状况.
外卖是一些非常繁重的编译器机制,以及精心的程序员纪律和可能特殊的注释,有时可以减少或消除垃圾收集的需要; 没有琐碎的转变可以做到这一点.