Paper Info
Title
Self-replicating expressions in the Lambda Calculus
Abstract
The study of self-replicating structures in Computer Science 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.
Year
Venue
Keywords
2004
ACSC
standard normal order reduction,parallel reduction,hybrid reduction,self-replicating expression,self-replicating lambda calculus expression,arbitrary data,lambda calculus,trivially self-replicating program,cellular automata,self-replicating structure,functional programming
Field
DocType
Citations 
Discrete mathematics,Binary lambda calculus,Simply typed lambda calculus,Typed lambda calculus,Fixed-point combinator,Church encoding,Higher-order function,Dependent type,Process calculus,Calculus,Mathematics
Conference
0
PageRank 
References 
Authors
0.34
2
2
Name
Order
Citations
PageRank
James Larkin1195.59
Phil Stocks226320.84