Lambda calculus is a formal system in mathematical logic for expressing abstraction-based calculations and applying functions using binding and variable substitution. This is a universal model that can be applied to the design of any Turing machine. The lambda calculus was first introduced by Church, a famous mathematician, in the 1930s.
The system consists of building lambda members and performing reduction operations on them.
Explanations and Applications
The Greek letter lambda (λ) is used in lambda expressions and lambda terms to denote the binding of a variable in a function.
Lambda calculus can be untyped or typed. In the first variant, functions can only be used if they are capable of receiving data of this type. Typed lambda calculi are weaker, can express a smaller value. But, on the other hand, they allow you to prove more things.
One reason there are so many different types is the desire of scientists to do more without giving up the opportunity to prove strong lambda calculus theorems.
The system has applications in many different areas of mathematics, philosophy, linguistics, and computer science. First of all, the lambda calculus is a calculus that has played an important role in the development of the theory of programming languages. It is the styles of functional creation that systems implement. They are also a hot topic of research in the theory of these categories.
For dummies
The lambda calculus was introduced by the mathematician Alonzo Church in the 1930s as part of his research into the foundations of science. The original system was shown to be logically inconsistent in 1935 when Stephen Klin and J. B. Rosser developed the Kleene-Rosser paradox.
Later, in 1936, Church singled out and published only the part that is relevant to calculations, what is now called the untyped lambda calculus. In 1940 he also introduced a weaker but logically consistent theory known as the prime type system. In his work, he explains the whole theory in simple terms, so it can be said that Church published the calculus lambda for dummies.
Until the 1960s, when its relation to programming languages became clear, λ was just a formalism. Thanks to the applications of Richard Montagu and other linguists in the semantics of natural language, calculus has taken pride of place in both linguistics and computer science.
Origin of the symbol
Lambda doesn't stand for a word or acronym, it comes from a reference in Russell's Principal Mathematics followed by two typographical changes. Notation example: for a function f with f (y)=2y + 1 is 2ŷ + 1. And here we use the caret symbol (“hat”) over y to label the input variable.
The church originally intended to use similar symbols, but typesetters were unable to place the "hat" symbol above the letters. So instead they printed it originally as "/\y.2y+1". In the next episode of editing, typists replaced "/ \" with a visually similar character.
Introduction to lambda calculus
The system consists of a language of terms, which are chosen by a certain formal syntax, and a set of transformation rules that allow them to be manipulated. The last point can be considered as an equational theory or as an operational definition.
All functions in the lambda calculus are anonymous, meaning they don't have names. They take only one input variable, and currying is used to implement plots with multiple variables.
Lambda terms
The calculus syntax defines some expressions as valid and others as invalid. Just like different strings of characters are valid C programs and some are not. The actual expression of the lambda calculus is called the "lambda term".
The following three rules provide an inductive definition that can beapply to the construction of all syntactically valid concepts:
The x variable itself is a valid lambda term:
- if T is LT and x is non-constant, then (lambda xt) is called an abstraction.
- if T as well as s are concepts, then (TS) is called an application.
Nothing else is a lambda term. Thus, a concept is valid if and only if it can be obtained by repeated application of these three rules. However, some brackets may be omitted according to other criteria.
Definition
Lambda expressions consist of:
- variables v 1, v 2, …, v n, …
- symbols of abstraction 'λ' and dot '.'
- brackets ().
The set Λ can be defined inductively:
- If x is a variable, then x ∈ Λ;
- x is not constant and M ∈ Λ, then (λx. M) ∈ Λ;
- M, N ∈ Λ, then (MN) ∈ Λ.
Designation
To keep the notation of lambda expressions uncluttered, the following conventions are commonly used:
- Outer brackets omitted: MN instead of (MN).
- Applications are assumed to remain associative: ((MN) P) can be written MNP.
- The body of abstraction extends further to the right: λx. MN means λx. (MN), not (λx. M) N.
- The sequence of abstractions is reduced: λx.λy.λz. N can be λxyz. N.
Free and bound variables
The operator λ connects its variable wherever it is in the body of abstraction. Variables that fall into the scope are called bound. In the expression λ x. M, the λ x part is often referred to as a binder. As if hinting that the variables become a group with the addition of X x to M. All other unstable ones are called free.
For example, in the expression λ y. x x y, y - bound non-permanent, and x - free. And it's also worth noting that the variable is grouped by its "nearest" abstraction. In the following example, the lambda calculus solution is represented by a single occurrence of x, which is related to the second term:
λ x. y (λ x. z x)
The set of free variables M is denoted as FV (M) and is defined by recursion over the structure of terms as follows:
- FV (x)={x}, where x is a variable.
- FV (λx. M)=FV (M) {x}.
- FV (MN)=FV (M) ∪ FV (N).
A formula that does not contain free variables is called closed. Closed lambda expressions are also known as combinators and are equivalent to terms in combinatorial logic.
Abbreviation
The meaning of lambda expressions is determined by how they can be shortened.
There are three types of cuts:
- α-transform: changing bound variables (alpha).
- β-reduction: applying functions to their arguments (beta).
- η-transform: covers the notion of extensionality.
Here it is alsowe are talking about the resulting equivalences: two expressions are β-equivalent if they can be β-transformed into the same component, and α / η-equivalence is defined similarly.
The term redex, short for reducible turnover, refers to subtopics that can be reduced by one of the rules. Lambda calculus for dummies, examples:
(λ x. M) N is a beta redex in the expression for replacing N with x in M. The component to which a redex reduces is called its reduct. The reduction (λ x. M) N is M [x:=N].
If x is not free in M, λ x. M x also em-REDEX with regulator M.
α-transformation
Alpha renames allow you to change the names of bound variables. For example, x. x can give λ y. y. Terms that differ only in alpha transformation are said to be α-equivalent. Often, when using the lambda calculus, α-equivalents are considered reciprocal.
The exact rules for alpha conversion are not entirely trivial. First, with this abstraction, only those variables that are associated with the same system are renamed. For example, the alpha transform λ x.λ x. x can lead to λ y.λ x. x, but this may not lead to λy.λx.y The latter has a different meaning than the original. This is analogous to the concept of variable shadowing programming.
Secondly, an alpha transform is not possible if it would result in being captured by a non-permanent other abstraction. For example, if you replace x with y in λ x.λ y. x, then you can getλy.λy. u, which is not the same at all.
In programming languages with static scope, alpha conversion can be used to simplify name resolution. At the same time, taking care that the concept of a variable does not mask the designation in the containing area.
In De Bruyne index notation, any two alpha-equivalent terms are syntactically identical.
Replacement
The changes written by E [V:=R] are the process of substituting all free occurrences of the variable V in the expression E with the turnover R. Substitution in terms of λ is defined by the lambda of the recursion calculus on the concept structure as follows (note: x and y - only variables, and M and N - any λ-expression).
x [x:=N] ≡ N
y [x:=N] ≡ y if x ≠ y
(M 1 M 2) [x:=N] ≡ (M 1 [x:=N]) (M 2 [x:=N])
(λ x. M) [x:=N] ≡ λ x. M
(λ y. M) [x:=N] y λ y. (M [x:=N]) if x ≠ y, provided that y ∉ FV (N).
To substitute into a lambda abstraction, sometimes it is necessary to α-transform an expression. For example, it is not true that (λ x. Y) [y:=x] results in (λ x. X) because the substituted x should have been free, but ended up being bound. The correct replacement in this case is (λ z. X) up to α-equivalence. Note that substitution is defined uniquely up to lambda.
β-reduction
Beta reduction reflects the idea of applying a function. Beta-reductive is defined in termssubstitution: ((X V. E) E ') is E [V:=E'].
For example, assuming some encoding 2, 7, ×, there is the following β-reduction: ((λ n. N × 2) 7) → 7 × 2.
Beta reduction can be seen as the same as the concept of local reducibility under natural deduction via the Curry-Howard isomorphism.
η-transform
This conversion expresses the idea of extensionality, which in this context is that two functions are equal when they give the same result for all arguments. This conversion exchanges between λ x. (F x) and f whenever x doesn't seem free in f.
This action can be considered as the same as the concept of local completeness in natural deduction through the Curry-Howard isomorphism.
Normal forms and fusion
For an untyped lambda calculus, the β-reduction rule is generally neither strong nor weak normalizing.
Nevertheless, it can be shown that the β-reduction merges when running before the α-transformation (i.e., two normal forms can be considered equal if an α-transformation from one to the other is possible).
Therefore, both strongly normalizing terms and weakly adjusting terms have a single normal form. For the first terms, any reduction strategy is guaranteed to result in a typical configuration. Whereas for weakly normalizing conditions, some reduction strategies may not find it.
Additional programming methods
There are a lot of creation idioms for the lambda calculus. Many of them were originally developed in the context of using systems as the basis for the semantics of a programming language, effectively applying them as a low-level construct. Since some styles include a lambda calculus (or something very similar) as a snippet, these techniques also find use in practical creation, but may then be perceived as obscure or foreign.
Named constants
In lambda calculus, a library takes the form of a set of previously defined functions, where the terms are just concrete constants. Pure calculus has no concept of named immutables since all atomic lambda terms are variables. But they can also be mimicked by taking the mutable as the name of the constant, using a lambda abstraction to bind that volatile in the body, and applying that abstraction to the intended definition. So if you use f to represent M in N, you could say
(λ f. N) M.
Authors often introduce a syntactic concept such as let to allow things to be written in a more intuitive way.
f=M to N
By chaining such definitions, one can write a lambda calculus "program" as zero or more function definitions followed by a single lambda member, using those definitions that make up the bulk of the program.
A notable limitation of this let is that the name f is not defined in M,since M is outside the binding scope of the lambda abstraction f. This means that a recursive function attribute cannot be used as M with let. The more advanced letrec syntax, which allows you to write recursive function definitions in this style, additionally uses fixed-point combinators instead.
Printed analogues
This type is a typed formalism that uses a symbol to represent an anonymous function abstraction. In this context, types are usually objects of a syntactic nature that are assigned to lambda terms. The exact nature depends on the calculus in question. From a certain point of view, typed LI can be considered as refinements of untyped LI. But on the other hand, they can also be considered a more fundamental theory, and the untyped lambda calculus is a special case with only one type.
Typed LIs are the foundation of programming languages and the backbone of functional languages such as ML and Haskell. And, more indirectly, imperative styles of creation. Typed lambda calculi play an important role in the development of type systems for programming languages. Here, typability usually captures the desired properties of the program, for example, it will not cause a memory access violation.
Typed lambda calculi are closely related to mathematical logic and proof theory through the Curry–Howard isomorphism, and can be thought of as an internal language of category classes, for example, whichsimply is the style of Cartesian closures.
