Open AccessSolving Equations in the lambda-Calculus using Syntactic Encapsulation
Author(s) -
Mayer Goldberg
Publication year - 1995
Publication title -
brics report series
Language(s) - English
Resource type - Journals
eISSN - 1601-5355
pISSN - 0909-0878
DOI - 10.7146/brics.v2i49.19950
Subject(s) - mathematics , lambda , encapsulation (networking) , calculus (dental) , computer science , physics , medicine , computer network , dentistry , optics
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.