Menu
I have problems understanding lambda calculus operators precedence.
For example the following code:
lambda x.x z lambda y.x y
is going to be:
lambda x. (x (z lambda y. x y))
or
lambda x. ((x z) (lambda y. x y))
?
Even more complicated examples:
(lambda x.x z) lambda y.w lambda w.w x y z
where in the above example the parentheses go ?
I know that lambda application is left associative but does lambda values have higher precedence over applications?
232
A redex, or reducible expression, is a subexpression of a λ expression in which a λ can be applied to an argument. With more than one redex, there is more than one evaluation order. e.g. (+(* 3 4) (* 7 6)). Normal Order Evaluation. Always reduce leftmost redex.
Lambda calculus (also written as λ-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation that can be used to simulate any Turing machine.
Evaluating a Lambda Expression A lambda calculus expression can be thought of as a program which can be executed by evaluating it. Evaluation is done by repeatedly finding a reducible expression (called a redex) and reducing it by a function evaluation until there are no more redexes.
x) (λy. y). As in SML, application terms are left-associative, so x y z is the same thing as (x y) z. For simplicity, multiple variables may be placed after the lambda, and this is considered shorthand for having a lambda in front of each variable.
Application has higher precedence than abstraction. Together with the fact that application is left-associative and abstraction is right-associative, this leads to the following:
lambda x.x z lambda y.x y
is
lambda x. ( (x z) (lambda y. (x y)) )
and
(lambda x.x z) lambda y.w lambda w.w x y z
is
(lambda x. (x z)) (lambda y. (w (lambda w. (((w x) y) z))))
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
