First t is replaced by an alpha-equivalent The substitution takes place in two steps. No, this is the idenity function, not the constant function with Obtained by a simple text-for-text replacement of x by y. What is t? It is not lambda(y,y), as would be Suppose t is lambda(y,x), the constant function with value x. We use the notation t to denote the result of substituting term r for variable x in term t.
ALPHA REDUCTION IN LAMBDA CALCULUS FREE
Substitution of terms for variables is slightly tricky to define (or implement) correctly, because we have to avoid "accidental capture" of free variables. The first axiom of the lambda calculus is the "alpha" axiom: t=r if t and r are alpha-equivalent. As an exercise, students should stop here to give a precise definition of alpha equivalence. (The"scope" of the binding is the lambda term whose first argument is the bound variable in question.) For example, in lambda(x,y), you cannot rename x to y. You cannot rename a bound variable using the name of a variable that already occurs free in the scope of the binding.
The reason for using a fancier term is that not every renaming of bound variables is allowed. A fancier term for this is "alpha-equivalence". They are said to "differ by renaming bound variables". For example, lambda(x,x) and lambda(y,y) both denote the identity function. That means, intuitively, that the value of the expression does not depend For example, lambda(x, lambda(y,x)) is the function whose value at any x is the constant function with value x. Lambda calculus", but it is much newer and less studied than lambda calculus. There is no such thing as an undefined expression. Thus in lambda calculus, allįunctions are "total", i.e. This says, if we apply the identityĪp is an ordinary function symbol, like any function symbol in logic, so Ap(f,x) always has a value.
The connection between Ap and lambda is illustrated by this example: Ap(lambda(x,x),c) = c. Use ascii notation, for two reasons: it's easy to render in HTML, and we have to use it in computer input files, and it's better The identity function is λx.x, or in ascii form as lambda(x,x). We write that in computer-readableįorm ("ascii form") as lambda(x,c). For instance, the constant function with value c is &lambda x. You can read it mentally as "as a function of", The second fundamental symbol in the lambda calculus is λ. Rules and objects is dropped completely in the formalism. The result is another object, which may of course be a rule. Rule (or object) f to object (or rule) x.
With this picture it makes sense to have a function symbol Ap and write Ap(f,x) for the result of applying Later condition true by arbitrarily defining every non-rule to behave as a rule in some arbitrary way, for instance to be a constantįunction returning itself. Just another kind of "object" and every object is thought of as some kind of (possibly trivial) rule.
(non-computable) "function" we do not specify we will just write down some axioms about these "rules". Whether these rules are programs or some kind of more general Lambda calculus, or calculus, is a theory of "rules". This essay gives the basic definitions and a few main points about the subject. Lambda calculus is a large and complicated subject.
0 kommentar(er)
