Solving Equations in the lambda-Calculus using Syntactic Encapsulation

  • Mayer Goldberg

Abstract

Syntactic encapsulation is a relation between an expression and one of
its sub-expressions, that constraints how the given sub-expression can
be used throughout the reduction of the expression. In this paper, we
present a class of systems of equations, in which the right-hand side of
each equation is syntactically encapsulated in the left-hand side. This
class is general enough to allow equations to contain self-application,
and to allow unknowns to appear on both sides of the equation. Yet
such a system is simple enough to be solvable, and for a solution
(though of course not its normal form) to be obtainable in constant
time.


Keywords: lambda-calculus, programming calculi.

Published
1995-06-19
How to Cite
Goldberg, M. (1995). Solving Equations in the lambda-Calculus using Syntactic Encapsulation. BRICS Report Series, 2(49). https://doi.org/10.7146/brics.v2i49.19950