|
A General Schema for Constructing One-Point Bases in the Lambda
Calculus
Mayer Goldberg September 2001 |
Abstract:
In this paper, we present a schema for constructing one-point
bases for recursively enumerable sets of lambda terms. The novelty of the
approach is that we make no assumptions about the terms for which the
one-point basis is constructed: They need not be combinators and they may
contain constants and free variables. The significance of the construction is
twofold: In the context of the lambda calculus, it characterises one-point
bases as ways of ``packaging'' sets of terms into a single term; And in the
context of realistic programming languages, it implies that we can define a
single procedure that generates any given recursively enumerable set of
procedures, constants and free variables in a given programming
language
Available as PostScript, PDF, DVI. |