In fact, we have expressions like λx.λy.xzy so often that we like to abbreviate them as λxy.xzy. Functions are expressions, and expressions can contain other expressions, so functions can be parts of the bodies of other functions, or be part of the replacing expression. Q: Can functions contain other functions?Ī: Absolutely. Once we have gotten rid of all the lambdas, or if there are no more expressions after the remaining functions, we cannot replace anything any more. The resolution of functions is the only thing we can ever do in the Lambda Calculus. Resolving a function: Replacing all occurrences of `y` with the expression `(ab)` Having done that, we throw the head away, because it has served its purpose: telling us which variable to replace. We cut the expression after the function, and paste it into the body, in every place indicated by the head. The resolution works by taking the variable mentioned in the head, and replacing all of its occurrences within the body with the expression after the function. Cut & Pasteįunctions can be resolved if they are followed by another expression. If we also agree to read all lambda expressions from left to right, we can omit a few of the parenthesis: (λy.xy) ab is the simplified version of (((λy.(x y)) a) b). From these three rules, we can construct all valid expressions. If x and y are lambda terms, then (x y) is a lambda term, and (λx.y) is a lambda term. Slightly more formally, we can say: All variables are lambda terms (a valid expression in the lambda calculus). The typesetter turned it into (λy.xy) ab, which is visually close enough. In the typed manuscript, he put the roof in front of the head, so it became (⋀y.xy) ab. Initially, Alonzo Church just drew a little roof to mark the head variable, like this: (ŷ xy) ab. The only thing we can do with it is to resolve it.Ī: An accident, perhaps. It is just a kind of expression, with a head and a body. You can rename variables all you want, without changing the expression.Ī: Nothing, really. The only thing that matters is: when two variables have the same name, they are the same. Q: What is the value or meaning of a variable?Ī: None. part of a function is called its head, and the remainder (the expression) is called the body. The λ does not have any complicated meaning: it just says that a function starts here. A function starts always with the λ and a variable, followed by a dot, and then comes an expression. With λ and the dot, we can write functions. The greek letter λ (pronounced, of course: Lambda), and the dot.Where we don’t have parentheses, we look at expressions simply from left to right. Parentheses can be used to indicate that some part of an expression belongs together (just as the braces around this part of the sentence make it belong together). More generally, we can write any two or more expressions together to get another expression. An expression can be a single letter, or several letters in a row.
0 Comments
Leave a Reply. |