• People
• Events
• Research

Unlimp: Uniqueness as a Leitmotiv for Implementation

Abstract: When evaluation in functional programming languages is explained using lambda-calculus and/or term rewriting systems, expressions and function definitions are often defined as terms, that is as trees. Similarly, the collection of all terms is defined as a forest, that is a directed, acyclic graph where every vertex has at most one incoming edge. Concrete implementations usually drop the last restriction (and sometimes acyclicity as well), i.e. many terms can share a common subterm, meaning that different paths of subterm edges reach the same vertex in the graph. Any vertex in such a graph represents a term. A term is represented uniquely in such a graph if there are no two different vertices representing it. Such a representation can be established by using hash-consing for the creation of heap objects. We investigate the consequences of adopting uniqueness in this sense as a leitmotiv for implementation (called Unlimp), i.e. not allowing any two different vertices in a graph to represent the same term.

This file is a slightly modified version of the LFCS Technical Report. This version appeared in the Proceedings of the 4th International Symposium on Programming Language Implementation and Logic Programming, Leuven, August 1992. Pages 115-129. Editors M. Bruynooghe and M. Wirsing.

LFCS report ECS-LFCS-92-219, June 1992.