Functional programming languages are all based on the lambda calculus. Some languages in this general category incorporate features into the language that aren’t translatable into lambda expressions. Haskell is a pure functional language.
The word purity in functional programming is sometimes also used to mean what is more
properly called referential transparency. Referential transparency means that the
same function, given the same values to evaluate, will always return the same result
in pure functional programming, as they do in math.
Scala is an objective oriented language, which incorporates functional programming features.
Function
A function is a relation between a set of possible inputs and a set of possible outputs. The function itself defines and represents the relationship.
Lambda’s structure
The lambda calculus has three basic components, or lambda terms: expressions, variables,
and abstractions.
The expression refers to a superset of all those things: an expression can be a variable
name, an abstraction, or a combination of those things. The simplest expression is a
single variable.
Variables here have no meaning or value, they are names for potential inputs to functions.
An abstraction is a function. It is a lambda term that has a head (a lambda) and a body
and is applied to an argument. An argument is an input value.
Abstractions consisit of two parts: the head and the body. The head of the function is
a \(\lambda\) followed by a variable name. The body of the function is another expression.
Following is a simple function:
The variable named in the head is the parameter and binds al instances of that same
variable in the body of the function. The . separates the parameters of the lambda from
the function body. It is the identity function.
We note that the lambda abstraction \(\lambda x.x\) has no name. It is an anonymous
function. A named function can be called by name by another function; an anonymous
function cannot.
Reduction
The meaning of lambda expressions is defined by how expressions can be reduced.
There are three kinds of reduction:
- \(\alpha\)-conversion: changing bound variables (alpha);
- \(\beta\)-reduction: applying functions to their arguments (beta);
- \(\eta\)-conversion: which captures a notion of extensionality (eta).
We also speak of the resulting equivalences: two expressions are \(\beta\)-equivalent, if they can be \(\beta\)-converted into the same expression, and \(\alpha\)/\(\eta\)-equivalence are defined similarly.
The term redex, short for reducible expression, refers to subterms that can be reduced by one of
the reduction rules. The expression to which a redex reduces is called its reduct.
Alpha conversion
In the abstraction \(\lambda x.x\), the variable \(x\) is not semantically meaningful except
in its role in that single expression. There’s a form of equivalence between lambda terms
called alpha equivalence. That says,
all mean the same thing. They are all the same function.
The alpha conversion, sometimes known as alpha renaming, allows bound variable names to be
changed. Terms that differ only by alpha conversion are called \(\alpha\) equivalent.
Frequently, in uses of lambda calculus, \(\alpha\) equivalent terms are considered to be
equivalent.
Beta reduction
Beta-reduction is defined in terms of substitution: When we apply a function to an argument, we
substitute the input expression for all instances of bound variables within the body of the
abstraction, and eliminate the head of the function as well, since its only purpose was to bind a
variable. This process is called beta reduction.
Applications in the lambda calculus are left associative.
The purpose of the head of the function is to tell us which variables to replace when we apply our function, that is, to bind the variables. A bound variable must have the same value throughout the expression.
Free variables
Sometimes the body expression has variables that are not named in the head. Those variables are
called free variables.
Multiple arguments
Each lambda can only bind one parameter and can only accept one argument. Functions that require
multiple arguments have multiple, nested heads. When you apply it once and eliminate the first
(left most) head, the next one is applied, and so on. This formulation is commonly called currying.
The following
is a convinent shorthand for two nested lambdas:
And also note that in the following lambda:
The substitution process can become a tangle of xs that are not the same x because each was
bound by a different head.
With free variables and multiple parameters, the basic process of beta reduction will remain the same. The process of beta reduction stops when there are either no more heads, or lambdas, left to apply or no more arguments to apply functions to.
The beta normal form is when you cannot beta reduce (apply lambdas to arguments) the terms any
further. This corresponds to a fully evaluated expression, or, in programming, a fully excuted
program.
Eta conversion
Eta-conversion expresses the idea of extensionality, which in this context is that two functions are the same if and only if they give the same result for all arguments. Eta-conversion converts between \(\lambda x.(f x)\) and \(f\) whenever \(x\) does not appear free in \(f\).
Following is an exmple in Scala:
1
2
3
4
5
def sum(x: Int, y :Int): Int = x + y
val sumFunc = sum
// or val sumFunc = sum(_: Int, _: Int)
Combinators
A combinator is a lambda term with no free variables. Combinators, as the name suggests, serve
only to combine the arguments it is given.
Divergence
Not all reducible lambda terms reduce neatly to a beta normal form. This isn’t because they’are
already fully reduced, but rather because they diverge. Divergence here means that the reduction
process never terminates or ends. Reducing terms should ordinarily converge to beta normal form,
and divergence is the opposite of convergence, or normal form. Following is an example of a lambda
term called omega that diverges:
This matters in programming because terms that diverge are terms that don’t produce an answer or
meaningful result.
Haskell
There things all apply to Haskell, as they do to any pure functional languages, because semantically
Haskell is a lambda calculus. Haskell is a typed lambda calculus with a lot of surface-level
decoration sprinkled on top, but the semantics of the core language are the same as the lambda
calculus.
The meaning of Haskell programs is centered around evaluating expressions rather than executing instructions, although Haskell has a way to execute instructions too.
Scala
Well, Scala uses objects to simulate lambda calculus.
