Date of this Version
The study of self-replicating structures in ComputerScience has been taking place for more than half a century, motivated by the desire to understand the fundamental principles and algorithms involved in self-replication. The bulk of the literature explores self-replicating forms in Cellular Automata. Though trivially self-replicating programs have been written for dozens of languages, very little work exists that explores self-replicating forms in programming languages.
This paper reports initial investigations into self replicating expressions in the Lambda Calculus, the basis for functional programming languages. Mimicking results from the work on Cellular Automata, self-replicating Lambda Calculus expressions that also allow the application of an arbitrary program to arbitrary data are presented. Standard normal order reduction, however, will not reduce the sub-expression representing the program application. Two approaches of dealing with this, hybrid reduction and parallel reduction, are discussed, and have been implemented in an interpreter.
This document has been peer reviewed.