Self-replicating expressions in the Lambda Calculus

James Larkin, Bond University
Phil Stocks, Bond University

Article comments

Published Version.

Larkin, J. & Stocks, P. (2004). Self-replicating expressions in the Lambda Calculus. Paper presented at the 27th Australasian Computer Science Conference (ACSC2004), The University of Otago, Dunedin, New Zealand. Subsequently published in Conferences in Research and Practice in Information Technology, 26(1), 167-173.

Access the Conference Series website.

Copyright © 2004, Australian Computer Society, Inc. This paper appeared at 27th Australasian Computer Science Conference, The University of Otago, Dunedin, New Zealand. Conferences in Research and Practice in Information Technology, Vol. 26. V. Estivill-Castro, Ed. Reproduced for academic, not-for profit purposes permitted provided this text in included.

Abstract

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.