Amorphous Infrastructure for Language Implementation

Abstract

We propose a method for the robust implementation of simple graphical automataon an amorphous computer. This infrastructure is applied to the implementationof purely functional programming languages. Specifically, it is usedin conjunction with data-flow techniques to implement a toy language homologousto recurrence equations, exploiting control-flow parallelism through paralleloperand evaluation. Also, data parallelism is explored in a separate implementation,in which a simple mark-up syntax enables Scheme programs to performspatially-distributed tree-walking without modifying their semantics. This additionenables an idiomatically expressed interpreter to be trivially instrumented,producing a spatially distributed universal machine, and once again achievingcontrol flow parallelism in the interpreted language.