A Hierarchy of Memory for Parallel Functional Programming

计算机内存是分层结构的，例如（从内部寄存器到外部寄存器，“主”内存/RAM和磁盘）。每一个都比里面的慢，但比里面的大。这些层反映在传统编程语言的设计中（分别通过局部变量、非局部变量和数组以及文件），程序的设计是为了充分利用它们的相对速度、大小和持久性。函数式或应用程序编程语言最有希望用于并行处理，但它们还没有处理这种内存分层。相反，目前的做法是将所有内存视为RAM，将其结构化为链接数据结构的“堆”，尽管这种单层模型限制了它们的效用。此外，尽管链接结构对于处理器之间的分区问题非常有吸引力，但并行堆管理是一个开放的问题。这个项目探索了将物理内存的必要分层与纯函数式编程的实践相协调的方法。其中一个目标是演示引用计数内存（RCM）硬件的性能，它可以管理由许多处理器共享的堆。计算内存地址——从任何处理器远程计算——它可以恢复大部分未使用的内存，而无需任何处理器同步和很少的额外通信。另一个目标是在纯函数式语言中实现持久文件系统。持久性要求文件在某些不可预测的故障中存活下来。因此，系统必须保留文件的当前状态，尽管状态的概念在函数式编程中是被禁止的。

Computer memory is structured in layers, for example (moving from inner to outer registers, "main" memory/RAM, and disk. Each is slower but larger than those within it. These layers are reflected in the design of conventional programming languages (respectively, by local variables, non-local variable and arrays, and files), and programs are designed to take best advantage of their relative speed, size, and persistency. Functional or applicative programming languages are most promising for parallel processing, but they do not yet deal with this layering of memory. Rather, present practice there is to treat all memory as RAM, structured as a "heap" for linked data structures, even though this unilevel model restricts their utility. Furthermore, although linked structures are very attractive for partitioning problems among processors, parallel heap management is an open problem. This project explores methods of reconciling the necessary layering of physical memory into the practice of purely functional programming. One goal is to demonstrate performance of reference-counting memory (RCM) hardware, which can manage a heap shared by many processors. Reckoning at the memory address--remotely from any processor--it recovers most unused memory without any processor synchronization and little additional communication. Another goal is to implement a persistent file system within a purely functional language. Persistency requires that files survive certain unpredictable failures. Therefore, the system must retain current state of the files, even though the concept of state is forbidden in functional programming.