Conferences in Research and Practice in Information Technology
  

Online Version - Last Updated - 20 Jan 2012

 

 
Home
 

 
Procedures and Resources for Authors

 
Information and Resources for Volume Editors
 

 
Orders and Subscriptions
 

 
Published Articles

 
Upcoming Volumes
 

 
Contact Us
 

 
Useful External Links
 

 
CRPIT Site Search
 
    

Self-Replicating Expressions in the Lambda Calculus

Larkin, J. and Stocks, P.

    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 im- plemented in an interpreter.
Cite as: Larkin, J. and Stocks, P. (2004). Self-Replicating Expressions in the Lambda Calculus. In Proc. Twenty-Seventh Australasian Computer Science Conference (ACSC2004), Dunedin, New Zealand. CRPIT, 26. Estivill-Castro, V., Ed. ACS. 167-173.
pdf (from crpit.com) pdf (local if available) BibTeX EndNote GS
 

 

ACS Logo© Copyright Australian Computer Society Inc. 2001-2014.
Comments should be sent to the webmaster at crpit@scem.uws.edu.au.
This page last updated 16 Nov 2007