Free
Faster access than browser!

# Lambda calculus

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. [1]

## Abstraction (computer science)

In software engineering and computer science, abstraction is.

## Alonzo Church

Alonzo Church (June 14, 1903 – August 11, 1995) was an American mathematician and logician who made major contributions to mathematical logic and the foundations of theoretical computer science.

## American Journal of Mathematics

The American Journal of Mathematics is a bimonthly mathematics journal published by the Johns Hopkins University Press.

## Applicative computing systems

Applicative computing systems, or ACS are the systems of object calculi founded on combinatory logic and lambda calculus.

## Argument

In logic and philosophy, an argument is a series of statements typically used to persuade someone of something or to present reasons for accepting a conclusion.

## Arithmetic

Arithmetic (from the Greek ἀριθμός arithmos, "number") is a branch of mathematics that consists of the study of numbers, especially the properties of the traditional operations on them—addition, subtraction, multiplication and division.

## Automated theorem proving

Automated theorem proving (also known as ATP or automated deduction) is a subfield of automated reasoning and mathematical logic dealing with proving mathematical theorems by computer programs.

## B, C, K, W system

The B, C, K, W system is a variant of combinatory logic that takes as primitive the combinators B, C, K, and W. This system was discovered by Haskell Curry in his doctoral thesis Grundlagen der kombinatorischen Logik, whose results are set out in Curry (1930).

## Beta normal form

In the lambda calculus, a term is in beta normal form if no beta reduction is possible.

## Big O notation

Big O notation is a mathematical notation that describes the limiting behaviour of a function when the argument tends towards a particular value or infinity.

## Binary combinatory logic

Binary combinatory logic (BCL) is a formulation of combinatory logic using only the symbols 0 and 1.

## C (programming language)

C (as in the letter ''c'') is a general-purpose, imperative computer programming language, supporting structured programming, lexical variable scope and recursion, while a static type system prevents many unintended operations.

## C Sharp (programming language)

C# (/si: ʃɑːrp/) is a multi-paradigm programming language encompassing strong typing, imperative, declarative, functional, generic, object-oriented (class-based), and component-oriented programming disciplines.

## C++11

C++11 is a version of the standard for the programming language C++.

## Calculus of constructions

In mathematical logic and computer science, the calculus of constructions (CoC) is a type theory created by Thierry Coquand.

## Cardinality

In mathematics, the cardinality of a set is a measure of the "number of elements of the set".

## Cartesian closed category

In category theory, a category is considered Cartesian closed if, roughly speaking, any morphism defined on a product of two objects can be naturally identified with a morphism defined on one of the factors.

## Categorical abstract machine

The categorical abstract machine (CAM) is a model of computation for programs that preserves the abilities of applicative, functional, or compositional style.

## Categorical logic

Categorical logic is the branch of mathematics in which tools and concepts from category theory are applied to the study of mathematical logic.

## Category theory

Category theory formalizes mathematical structure and its concepts in terms of a labeled directed graph called a category, whose nodes are called objects, and whose labelled directed edges are called arrows (or morphisms).

## Church encoding

In mathematics, Church encoding is a means of representing data and operators in the lambda calculus.

## Church–Rosser theorem

In mathematics and theoretical computer science, the Church–Rosser theorem states that, when applying reduction rules to terms in the lambda calculus, the ordering in which the reductions are chosen does not make a difference to the eventual result.

## Church–Turing thesis

In computability theory, the Church–Turing thesis (also known as computability thesis, the Turing–Church thesis, the Church–Turing conjecture, Church's thesis, Church's conjecture, and Turing's thesis) is a hypothesis about the nature of computable functions.

## Classical logic

Classical logic (or standard logic) is an intensively studied and widely used class of formal logics.

## Combinatory logic

Combinatory logic is a notation to eliminate the need for quantified variables in mathematical logic.

## Communications of the ACM

Communications of the ACM is the monthly journal of the Association for Computing Machinery (ACM).

## Computability

Computability is the ability to solve a problem in an effective manner.

## Computable function

Computable functions are the basic objects of study in computability theory.

## Computational complexity theory

Computational complexity theory is a branch of the theory of computation in theoretical computer science that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other.

## Computer science

Computer science deals with the theoretical foundations of information and computation, together with practical techniques for the implementation and application of these foundations.

## Confluence (abstract rewriting)

In computer science, confluence is a property of rewriting systems, describing which terms in such a system can be rewritten in more than one way, to yield the same result.

## Consistency

In classical deductive logic, a consistent theory is one that does not contain a contradiction.

## Curry–Howard correspondence

In programming language theory and proof theory, the Curry–Howard correspondence (also known as the Curry–Howard isomorphism or equivalence, or the proofs-as-programs and propositions- or formulae-as-types interpretation) is the direct relationship between computer programs and mathematical proofs.

## Currying

In mathematics and computer science, currying is the technique of translating the evaluation of a function that takes multiple arguments (or a tuple of arguments) into evaluating a sequence of functions, each with a single argument.

## Dana Scott

Dana Stewart Scott (born October 11, 1932) is the emeritus Hillman University Professor of Computer Science, Philosophy, and Mathematical Logic at Carnegie Mellon University; he is now retired and lives in Berkeley, California.

## De Bruijn index

In mathematical logic, the de Bruijn index is a notation invented by the Dutch mathematician Nicolaas Govert de Bruijn for representing terms in the λ calculus with the purpose of eliminating the names of the variable from the notation.

## Deductive lambda calculus

Deductive lambda calculus considers what happens when lambda terms are regarded as mathematical expressions.

## Denotational semantics

In computer science, denotational semantics (initially known as mathematical semantics or Scott–Strachey semantics) is an approach of formalizing the meanings of programming languages by constructing mathematical objects (called denotations) that describe the meanings of expressions from the languages.

## Director string

In mathematics, in the area of lambda calculus and computation, directors or director strings are a mechanism for keeping track of the free variables in a term.

## Distributed computing

Distributed computing is a field of computer science that studies distributed systems.

## Domain theory

Domain theory is a branch of mathematics that studies special kinds of partially ordered sets (posets) commonly called domains.

## Eager evaluation

In computer programming, eager evaluation, also known as strict evaluation or greedy evaluation, is the evaluation strategy used by most traditional programming languages.

## Eiffel (programming language)

Eiffel is an object-oriented programming language designed by Bertrand Meyer (an object-orientation proponent and author of Object-Oriented Software Construction) and Eiffel Software.

## Esoteric programming language

An esoteric programming language (sometimes shortened to esolang) is a programming language designed to test the boundaries of computer programming language design, as a proof of concept, as software art, as a hacking interface to another language (particularly functional programming or procedural programming languages), or as a joke.

## Evaluation strategy

Evaluation strategies are used by programming languages to determine when to evaluate the argument(s) of a function call (for function, also read: operation, method, or relation) and what kind of value to pass to the function.

## Explicit substitution

In computer science, lambda calculi are said to have explicit substitutions if they pay special attention to the formalization of the process of substitution.

## Exponentiation

Exponentiation is a mathematical operation, written as, involving two numbers, the base and the exponent.

## Extensionality

In logic, extensionality, or extensional equality, refers to principles that judge objects to be equal if they have the same external properties.

## Factorial

In mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n. For example, The value of 0! is 1, according to the convention for an empty product.

## First-class citizen

In programming language design, a first-class citizen (also type, object, entity, or value) in a given programming language is an entity which supports all the operations generally available to other entities.

## First-class function

In computer science, a programming language is said to have first-class functions if it treats functions as first-class citizens.

## Formal system

A formal system is the name of a logic system usually defined in the mathematical way.

## Formalism (philosophy of mathematics)

In foundations of mathematics, philosophy of mathematics, and philosophy of logic, formalism is a theory that holds that statements of mathematics and logic can be considered to be statements about the consequences of certain string manipulation rules.

## Foundations of mathematics

Foundations of mathematics is the study of the philosophical and logical and/or algorithmic basis of mathematics, or, in a broader sense, the mathematical investigation of what underlies the philosophical theories concerning the nature of mathematics.

## Free On-line Dictionary of Computing

The Free On-line Dictionary of Computing (FOLDOC) is an online, searchable, encyclopedic dictionary of computing subjects.

## Free variables and bound variables

In mathematics, and in other disciplines involving formal languages, including mathematical logic and computer science, a free variable is a notation that specifies places in an expression where substitution may take place.

## Function (mathematics)

In mathematics, a function was originally the idealization of how a varying quantity depends on another quantity.

## Function application

In mathematics, function application is the act of applying a function to an argument from its domain so as to obtain the corresponding value from its range.

## Function pointer

A function pointer, also called a subroutine pointer or procedure pointer, is a pointer that points to a function.

## Functional programming

In computer science, functional programming is a programming paradigm—a style of building the structure and elements of computer programs—that treats computation as the evaluation of mathematical functions and avoids changing-state and mutable data.

## Futures and promises

In computer science, future, promise, delay, and deferred refer to constructs used for synchronizing program execution in some concurrent programming languages.

## Gödel numbering

In mathematical logic, a Gödel numbering is a function that assigns to each symbol and well-formed formula of some formal language a unique natural number, called its Gödel number.

## Gödel's incompleteness theorems

Gödel's incompleteness theorems are two theorems of mathematical logic that demonstrate the inherent limitations of every formal axiomatic system containing basic arithmetic.

## Graph reduction

In computer science, graph reduction implements an efficient version of non-strict evaluation, an evaluation strategy where the arguments to a function are not immediately evaluated.

## Hacker culture

The hacker culture is a subculture of individuals who enjoy the intellectual challenge of creatively overcoming limitations of software systems to achieve novel and clever outcomes.

## Harrop formula

In intuitionistic logic, the Harrop formulae, named after Ronald Harrop, are the class of formulae inductively defined as follows.

Haskell is a standardized, general-purpose compiled purely functional programming language, with non-strict semantics and strong static typing.

## Henk Barendregt

Hendrik Pieter (Henk) Barendregt (born 18 December 1947, Amsterdam) is a Dutch logician, known for his work in lambda calculus and type theory.

## Higher-order function

In mathematics and computer science, a higher-order function (also functional, functional form or functor) is a function that does at least one of the following.

## If and only if

In logic and related fields such as mathematics and philosophy, if and only if (shortened iff) is a biconditional logical connective between statements.

## Imperative programming

In computer science, imperative programming is a programming paradigm that uses statements that change a program's state.

## Interaction nets

Interaction nets are a graphical model of computation devised by Yves Lafont in 1990 as a generalisation of the proof structures of linear logic.

## Internet Encyclopedia of Philosophy

The Internet Encyclopedia of Philosophy (IEP) is a scholarly online encyclopedia, dealing with philosophy, philosophical topics, and philosophers.

## J. Barkley Rosser

John Barkley Rosser Sr. (December 6, 1907 – September 5, 1989) was an American logician, a student of Alonzo Church, and known for his part in the Church–Rosser theorem, in lambda calculus.

## Java (programming language)

Java is a general-purpose computer-programming language that is concurrent, class-based, object-oriented, and specifically designed to have as few implementation dependencies as possible.

## JavaScript

JavaScript, often abbreviated as JS, is a high-level, interpreted programming language.

## Kappa calculus

In mathematical logic, category theory, and computer science, kappa calculus is a formal system for defining first-order functions.

In mathematics, the Kleene&ndash;Rosser paradox is a paradox that shows that certain systems of formal logic are inconsistent, in particular the version of Curry's combinatory logic introduced in 1930, and Church's original lambda calculus, introduced in 1932&ndash;1933, both originally intended as systems of formal logic.

## Knights of the Lambda Calculus

The Knights of the Lambda Calculus is a semi-fictional organization of expert Lisp and Scheme hackers.

## Krivine machine

In theoretical computer science, the Krivine machine is an abstract machine (sometimes called virtual machine).

## Lambda calculus

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.

## Lambda calculus definition

Formal definitions of the Lambda calculus.

## Lambda cube

In mathematical logic and type theory, the λ-cube is a framework for exploring the axes of refinement in Thierry Coquand's calculus of constructions, starting from the simply typed lambda calculus (written as λ→ in the cube diagram) as the vertex of a cube placed at the origin, and the calculus of constructions (higher-order dependently typed polymorphic lambda calculus; written as λPω in the diagram) as its diametrically opposite vertex.

## Lambda-mu calculus

In mathematical logic and computer science, the lambda-mu calculus is an extension of the lambda calculus introduced by M. Parigot.

## Lazy evaluation

In programming language theory, lazy evaluation, or call-by-need is an evaluation strategy which delays the evaluation of an expression until its value is needed (non-strict evaluation) and which also avoids repeated evaluations (sharing).

## Let expression

In computer science, a "let" expression associates a function definition with a restricted scope.

## Library (computing)

In computer science, a library is a collection of non-volatile resources used by computer programs, often for software development.

## Linguistics

Linguistics is the scientific study of language, and involves an analysis of language form, language meaning, and language in context.

## Lisp (programming language)

Lisp (historically, LISP) is a family of computer programming languages with a long history and a distinctive, fully parenthesized prefix notation.

## Low-level programming language

A low-level programming language is a programming language that provides little or no abstraction from a computer's instruction set architecture—commands or functions in the language map closely to processor instructions.

## Mathematical logic

Mathematical logic is a subfield of mathematics exploring the applications of formal logic to mathematics.

## Mathematical proof

In mathematics, a proof is an inferential argument for a mathematical statement.

## Mathematics

Mathematics (from Greek μάθημα máthēma, "knowledge, study, learning") is the study of such topics as quantity, structure, space, and change.

## Minimalism (computing)

In computing, minimalism refers to the application of minimalist philosophies and principles in the design and use of hardware and software.

## Miranda (programming language)

Miranda is a lazy, purely functional programming language designed by David Turner as a successor to his earlier programming languages SASL and KRC, using some concepts from ML and Hope.

## MIT Press

The MIT Press is a university press affiliated with the Massachusetts Institute of Technology (MIT) in Cambridge, Massachusetts (United States).

## ML (programming language)

ML (Meta Language) is a general-purpose functional programming language.

## Model of computation

In computer science, and more specifically in computability theory and computational complexity theory, a model of computation is a model which describes how a set of outputs are computed given a set of inputs.

## Model theory

In mathematics, model theory is the study of classes of mathematical structures (e.g. groups, fields, graphs, universes of set theory) from the perspective of mathematical logic.

## Name binding

In programming languages, name binding is the association of entities (data and/or code) with identifiers.

## Name collision

The term "name collision" refers to the nomenclature problem that occurs in computer programs when the same variable name is used for different things in two separate areas that are joined, merged, or otherwise go from occupying separate namespaces to sharing one.

## Name resolution (programming languages)

In programming languages, name resolution refers to the resolution of the tokens within program expressions to the intended program components.

## Natural number

In mathematics, the natural numbers are those used for counting (as in "there are six coins on the table") and ordering (as in "this is the third largest city in the country").

## Normalization property (abstract rewriting)

In mathematical logic and theoretical computer science, a rewrite system has the (strong) normalization property or is terminating if every term is strongly normalizing; that is, if every sequence of rewrites eventually terminates with an irreducible term, also called a normal form.

## North Holland

North Holland (Noord-Holland, West Frisian Dutch: Noard-Holland) is a province of the Netherlands located in the northwestern part of the country.

## Object (computer science)

In computer science, an object can be a variable, a data structure, a function, or a method, and as such, is a value in memory referenced by an identifier.

## Operational definition

An operational definition is the articulation of operationalization (or statement of procedures) used in defining the terms of a process (or set of validation tests) needed to determine the nature of an item or phenomenon (a variable, term, or object) and its properties such as duration, quantity, extension in space, chemical composition, etc.

## Operator associativity

In programming languages, the associativity of an operator is a property that determines how operators of the same precedence are grouped in the absence of parentheses.

## Parallel computing

Parallel computing is a type of computation in which many calculations or the execution of processes are carried out concurrently.

## Partially ordered set

In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set.

## Pascal (programming language)

Pascal is an imperative and procedural programming language, which Niklaus Wirth designed in 1968–69 and published in 1970, as a small, efficient language intended to encourage good programming practices using structured programming and data structuring. It is named in honor of the French mathematician, philosopher and physicist Blaise Pascal. Pascal was developed on the pattern of the ALGOL 60 language. Wirth had already developed several improvements to this language as part of the ALGOL X proposals, but these were not accepted and Pascal was developed separately and released in 1970. A derivative known as Object Pascal designed for object-oriented programming was developed in 1985; this was used by Apple Computer and Borland in the late 1980s and later developed into Delphi on the Microsoft Windows platform. Extensions to the Pascal concepts led to the Pascal-like languages Modula-2 and Oberon.

## PDF

The Portable Document Format (PDF) is a file format developed in the 1990s to present documents, including text formatting and images, in a manner independent of application software, hardware, and operating systems.

## Peter Landin

Peter John Landin (5 June 1930, Sheffield – 3 June 2009) was a British computer scientist.

## Philosophy

Philosophy (from Greek φιλοσοφία, philosophia, literally "love of wisdom") is the study of general and fundamental problems concerning matters such as existence, knowledge, values, reason, mind, and language.

## Procedural programming

Procedural programming is a programming paradigm, derived from structured programming, based upon the concept of the procedure call.

## Process calculus

In computer science, the process calculi (or process algebras) are a diverse family of related approaches for formally modelling concurrent systems.

## Programming idiom

A programming idiom or code idiom is expressing a special feature of a recurring construct in one or more programming languages.

## Programming language

A programming language is a formal language that specifies a set of instructions that can be used to produce various kinds of output.

## Programming language theory

Programming language theory (PLT) is a branch of computer science that deals with the design, implementation, analysis, characterization, and classification of programming languages and their individual features.

## Proof theory

Proof theory is a major branchAccording to Wang (1981), pp.

## Pure type system

In the branches of mathematical logic known as proof theory and type theory, a pure type system (PTS), previously known as a generalized type system (GTS), is a form of typed lambda calculus that allows an arbitrary number of sorts and dependencies between any of these.

## Recursion

Recursion occurs when a thing is defined in terms of itself or of its type.

## Recursive definition

A recursive definition (or inductive definition) in mathematical logic and computer science is used to define the elements in a set in terms of other elements in the set (Aczel 1978:740ff).

## Reduction strategy (lambda calculus)

In lambda calculus, a branch of mathematical logic concerned with the formal study of functions, a reduction strategy is how a complex expression is reduced to a simple expression by successive reduction steps.

## Rewriting

In mathematics, computer science, and logic, rewriting covers a wide range of (potentially non-deterministic) methods of replacing subterms of a formula with other terms.

## Richard Montague

Richard Merritt Montague (September 20, 1930 – March 7, 1971) was an American mathematician and philosopher.

## Ruy de Queiroz

Ruy J. Guerra B. de Queiroz (born January 11, 1958 in Recife) is an associate professor at Universidade Federal de Pernambuco and holds significant works in the research fields of Mathematical logic, proof theory, foundations of mathematics and philosophy of mathematics.

## Scala (programming language)

Scala is a general-purpose programming language providing support for functional programming and a strong static type system.

## Scheme (programming language)

Scheme is a programming language that supports multiple paradigms, including functional programming and imperative programming, and is one of the two main dialects of Lisp.

## Scope (computer science)

In computer programming, the scope of a name binding – an association of a name to an entity, such as a variable – is the region of a computer program where the binding is valid: where the name can be used to refer to the entity.

## Scott continuity

In mathematics, given two partially ordered sets P and Q, a function f \colon P \rightarrow Q between them is Scott-continuous (named after the mathematician Dana Scott) if it preserves all directed suprema, i.e. if for every directed subset D of P with supremum in P its image has a supremum in Q, and that supremum is the image of the supremum of D: that is, \sqcup f.

## SECD machine

The SECD machine is a highly influential (See: #Landin's contribution) virtual machine and abstract machine intended as a target for functional programming language compilers.

## Self-reference

Self-reference occurs in natural or formal languages when a sentence, idea or formula refers to itself.

## Simply typed lambda calculus

The simply typed lambda calculus (\lambda^\to), a form of type theory, is a typed interpretation of the lambda calculus with only one type constructor: \to that builds function types.

## Singleton (mathematics)

In mathematics, a singleton, also known as a unit set, is a set with exactly one element.

## SKI combinator calculus

The SKI combinator calculus is a combinatory logic, a computational system that may be perceived as a reduced version of the untyped lambda calculus.

## Smalltalk

Smalltalk is an object-oriented, dynamically typed, reflective programming language.

## Standard ML

Standard ML (SML; "Standard Meta Language") is a general-purpose, modular, functional programming language with compile-time type checking and type inference.

## Stephen Cole Kleene

Stephen Cole Kleene (January 5, 1909 – January 25, 1994) was an American mathematician.

## Structure and Interpretation of Computer Programs

Structure and Interpretation of Computer Programs (SICP) is a textbook aiming to teach the principles of computer programming, such as abstraction in programming, metalinguistic abstraction, recursion, interpreters, and modular programming.

## Studia Logica

Studia Logica is an international journal of mathematics and logic.

## Subroutine

In computer programming, a subroutine is a sequence of program instructions that performs a specific task, packaged as a unit.

## Substitution (algebra)

In algebra, the operation of substitution can be applied in various contexts involving formal objects containing symbols (often called variables or indeterminates); the operation consists of systematically replacing occurrences of some symbol by a given value.

## Subtyping

In programming language theory, subtyping (also subtype polymorphism or inclusion polymorphism) is a form of type polymorphism in which a subtype is a datatype that is related to another datatype (the supertype) by some notion of substitutability, meaning that program elements, typically subroutines or functions, written to operate on elements of the supertype can also operate on elements of the subtype.

## Syntactic sugar

In computer science, syntactic sugar is syntax within a programming language that is designed to make things easier to read or to express.

## System F

System F, also known as the (Girard–Reynolds) polymorphic lambda calculus or the second-order lambda calculus, is a typed lambda calculus that differs from the simply typed lambda calculus by the introduction of a mechanism of universal quantification over types.

## Template (C++)

Templates are a feature of the C++ programming language that allows functions and classes to operate with generic types.

## Thierry Coquand

Thierry Coquand (born 18 April 1961 in Jallieu, Isère, France) is a professor in computer science at the University of Gothenburg, Sweden.

## Thunk

In computer programming, a thunk is a subroutine used to inject an additional calculation into another subroutine.

## Truth value

In logic and mathematics, a truth value, sometimes called a logical value, is a value indicating the relation of a proposition to truth.

## Turing completeness

In computability theory, a system of data-manipulation rules (such as a computer's instruction set, a programming language, or a cellular automaton) is said to be Turing complete or computationally universal if it can be used to simulate any Turing machine.

## Turing machine

A Turing machine is a mathematical model of computation that defines an abstract machine, which manipulates symbols on a strip of tape according to a table of rules.

## Type system

In programming languages, a type system is a set of rules that assigns a property called type to the various constructs of a computer program, such as variables, expressions, functions or modules.

## Typed lambda calculus

A typed lambda calculus is a typed formalism that uses the lambda-symbol (\lambda) to denote anonymous function abstraction.

## Universal Turing machine

In computer science, a universal Turing machine (UTM) is a Turing machine that can simulate an arbitrary Turing machine on arbitrary input.

## Unlambda

Unlambda is a minimal, "nearly pure" functional programming language invented by David Madore.