Lambda Calculus, Functions, and Formal Computation: How Functions Define Computation

Last Updated June 17, 2026

Lambda calculus is one of the foundational languages of formal computation. It shows that computation can be understood through functions, variables, abstraction, application, and substitution. Before modern programming languages, software frameworks, type systems, functional programming, proof assistants, and formal methods became familiar, lambda calculus provided a minimal formal system for expressing computation itself.

The basic idea is simple but profound: computation can be modeled as the transformation of expressions. A function can be defined, applied to an argument, and reduced by substituting that argument into the function body. From this small set of ideas, lambda calculus helps explain programming languages, recursion, higher-order functions, evaluation strategies, type systems, logic, proof, and the relationship between functions and formal reasoning.

Lambda calculus matters because it connects computation to symbolic structure. It shows that a procedure does not have to be understood only as a sequence of machine instructions. Computation can also be understood as expression rewriting, function application, and formal transformation. This makes lambda calculus a bridge between logic, programming, mathematics, automated reasoning, and machine-checked systems.

This article explains lambda calculus as a foundation of formal computation. It introduces variables, abstraction, application, free and bound variables, substitution, alpha conversion, beta reduction, eta conversion, normal forms, evaluation strategies, recursion, fixed points, Church encodings, typed lambda calculus, functional programming, proof systems, type theory, and formal verification. It emphasizes why lambda calculus is not only a historical theory, but a living foundation for programming-language design, symbolic computation, proof assistants, and computational reasoning.

Why Lambda Calculus Matters

Lambda calculus matters because it gives computation a function-centered foundation. Instead of beginning with memory registers, machine instructions, hardware circuits, or step-by-step imperative commands, it begins with expressions and functions. Computation becomes the process of applying functions and reducing expressions.

This perspective shaped programming-language theory, functional programming, type systems, compiler design, denotational semantics, proof assistants, formal verification, logic, and the study of computation itself. Lambda calculus is one of the major formal models that helped clarify what it means for a function to be computable.

Lambda calculus shows that computation can be formalized through the structure of expressions themselves.

Back to top ↑

What Lambda Calculus Is

Lambda calculus is a formal system built from three basic forms: variables, abstractions, and applications. Variables name inputs or placeholders. Abstractions define functions. Applications apply functions to arguments.

The untyped lambda calculus allows expressions to be applied freely. Typed lambda calculi restrict expressions according to types, which makes many forms of reasoning, checking, and programming safer and more structured.

The system is minimal, but not trivial. Its simplicity is what makes it foundational.

Back to top ↑

Functions as Formal Objects

In ordinary mathematics, a function maps inputs to outputs. In lambda calculus, a function is represented as an expression. This means functions can be passed as arguments, returned as results, nested inside other functions, and transformed by rules.

This is the foundation of higher-order functions. A higher-order function is a function that takes functions as inputs or returns functions as outputs. Modern functional programming languages, proof assistants, and many programming-language semantics depend on this idea.

Treating functions as formal objects is one of lambda calculus’s deepest contributions to computation.

Back to top ↑

Variables, Abstraction, and Application

Variables, abstraction, and application are the grammar of lambda calculus. A variable names something. An abstraction binds a variable in a function body. An application applies one expression to another.

The abstraction \(\lambda x.e\) should be read as “the function of \(x\) whose body is \(e\).” Application then gives that function an argument.

The result reduces to \(a\).

These three forms are enough to build complex computational structures.

Back to top ↑

Free and Bound Variables

A variable is bound when it is introduced by a lambda abstraction. A variable is free when it appears in an expression without being bound by a surrounding abstraction.

Understanding free and bound variables is essential because substitution must avoid accidentally changing the meaning of an expression. This is one reason formal computation requires careful symbolic discipline.

The distinction between free and bound variables is also central to programming languages, scope, closures, compilers, and proof systems.

Back to top ↑

Substitution and Reduction

Substitution is the process of replacing a bound variable with an argument expression. Reduction is the process of simplifying lambda expressions by applying formal rules.

The most important reduction rule is beta reduction. It says that applying a function to an argument computes by substituting the argument for the function’s bound variable.

Example:

Substitution is simple in idea but subtle in formal practice.

Back to top ↑

Alpha, Beta, and Eta Rules

Lambda calculus has several important equivalence and transformation rules. Alpha conversion renames bound variables. Beta reduction performs function application. Eta conversion expresses a form of extensional equality between functions.

Alpha conversion is crucial for avoiding variable capture:

Beta reduction performs computation:

Eta conversion relates functions by behavior:

These rules support formal reasoning about when expressions are structurally different but computationally equivalent.

Back to top ↑

Evaluation Strategies

Evaluation strategy determines which reducible expression is reduced first. Different strategies can produce different practical behavior, especially when some expressions do not terminate.

Call-by-value evaluates arguments before applying functions. Call-by-name delays argument evaluation until needed. Call-by-need, used in lazy evaluation, shares delayed computations so they are evaluated at most once.

Example:

Evaluation strategy links lambda calculus to real language design. It affects performance, termination, reasoning, and program structure.

Back to top ↑

Recursion and Fixed Points

Recursion allows a computation to refer to itself. In lambda calculus, recursion can be represented through fixed points. A fixed point of a function \(F\) is a value \(x\) such that \(F(x) = x\).

In untyped lambda calculus, fixed-point combinators make recursion possible without naming a function directly. The famous \(Y\) combinator satisfies:

Recursion shows both the expressive power and the danger of formal computation. It enables rich computation, but it also introduces nontermination.

Back to top ↑

Church Encodings

Church encodings show that data can be represented using functions. Numbers, Booleans, pairs, lists, and control structures can all be encoded in lambda calculus.

For example, Church numerals represent natural numbers by repeated function application. The number zero applies a function zero times. The number one applies it once. The number two applies it twice.

Church encodings demonstrate the expressive completeness of functions as a computational foundation.

Back to top ↑

Typed Lambda Calculus

Typed lambda calculus adds type discipline to lambda expressions. Types describe what kind of value an expression may have and which applications are valid. A function from type \(A\) to type \(B\) has type \(A \rightarrow B\).

Typed systems prevent many invalid expressions. For example, applying a number as if it were a function can be rejected before execution.

Typed lambda calculus connects programming to proof. It is a foundation for type systems, verified programming, theorem proving, and proof assistants.

Back to top ↑

Functional Programming

Functional programming draws heavily from lambda calculus. It treats functions as central program structures, encourages immutability, supports higher-order functions, and often emphasizes expression evaluation over mutable state.

Languages such as Lisp, Scheme, ML, OCaml, Haskell, F#, Erlang, Elixir, Scala, Clojure, and many modern multi-paradigm languages reflect functional ideas. Even languages not usually called functional now include lambda expressions, closures, map, filter, reduce, and higher-order functions.

Functional programming is not identical to lambda calculus, but lambda calculus gives functional programming much of its formal vocabulary.

Back to top ↑

Logic, Proofs, and Type Theory

Lambda calculus is deeply connected to logic through type theory and the Curry-Howard correspondence. Under this correspondence, types can be interpreted as propositions, and programs can be interpreted as proofs.

A function type \(A \rightarrow B\) corresponds to implication: if we have a proof of \(A\), then we can produce a proof of \(B\). A program inhabiting a type can be understood as evidence for the proposition represented by that type.

This connection is foundational for proof assistants such as Coq, Agda, Lean, and related systems that combine computation, proof, and type checking.

Back to top ↑

Limits and Interpretation

Lambda calculus is powerful, but it must be interpreted carefully. Untyped lambda calculus can express nonterminating computations. Some expressions do not reduce to normal form. Typed systems can prevent many invalid programs, but the choice of type system determines what can be expressed and checked.

A formal expression may be correct within lambda calculus while still requiring interpretation when connected to real software, institutions, data, or models. Like all formal systems, lambda calculus clarifies structure but does not automatically solve representation, meaning, or governance.

Lambda calculus is a tool for making computation precise. Precision is powerful, but it must be connected to context.

Back to top ↑

Back to top ↑

Mathematics, Computation, and Modeling

The syntax of lambda calculus is minimal:

Beta reduction defines computation:

Alpha equivalence handles renaming:

Eta equivalence expresses extensional behavior:

A typed abstraction can be written:

These formulas summarize the formal structure behind functions, evaluation, binding, substitution, and typed computation.

Back to top ↑

Python Workflow: Lambda Expression Reduction Audit

The Python workflow below creates a small dependency-light audit for lambda-calculus reasoning examples. It scores expression clarity, binding safety, substitution discipline, reduction traceability, evaluation-strategy clarity, recursion awareness, type-discipline clarity, proof connection, implementation relevance, and governance readiness.

# lambda_expression_audit.py
# Dependency-light workflow for evaluating lambda-calculus and formal-computation examples.

from __future__ import annotations

from dataclasses import asdict, dataclass
from pathlib import Path
import csv
import json
from statistics import mean

ARTICLE_ROOT = Path(__file__).resolve().parents[1]
TABLES = ARTICLE_ROOT / "outputs" / "tables"
JSON_DIR = ARTICLE_ROOT / "outputs" / "json"


@dataclass(frozen=True)
class LambdaExpressionCase:
    case_name: str
    computation_context: str
    formal_claim: str
    expression_clarity: float
    binding_safety: float
    substitution_discipline: float
    reduction_traceability: float
    evaluation_strategy_clarity: float
    recursion_awareness: float
    type_discipline_clarity: float
    proof_connection: float
    implementation_relevance: float
    governance_readiness: float


def clamp(value: float, low: float = 0.0, high: float = 100.0) -> float:
    return max(low, min(high, value))


def lambda_reasoning_quality(case: LambdaExpressionCase) -> float:
    return clamp(
        100.0 * (
            0.10 * case.expression_clarity
            + 0.12 * case.binding_safety
            + 0.12 * case.substitution_discipline
            + 0.10 * case.reduction_traceability
            + 0.10 * case.evaluation_strategy_clarity
            + 0.08 * case.recursion_awareness
            + 0.12 * case.type_discipline_clarity
            + 0.08 * case.proof_connection
            + 0.08 * case.implementation_relevance
            + 0.10 * case.governance_readiness
        )
    )


def formalization_risk(case: LambdaExpressionCase) -> float:
    weak_points = [
        1.0 - case.binding_safety,
        1.0 - case.substitution_discipline,
        1.0 - case.reduction_traceability,
        1.0 - case.evaluation_strategy_clarity,
        1.0 - case.recursion_awareness,
        1.0 - case.type_discipline_clarity,
        1.0 - case.proof_connection,
        1.0 - case.governance_readiness,
    ]
    return clamp(100.0 * mean(weak_points))


def diagnose(quality: float, risk: float) -> str:
    if quality >= 82 and risk <= 22:
        return "strong lambda-calculus reasoning posture with clear binding, substitution, typing, and reduction evidence"
    if quality >= 68 and risk <= 38:
        return "usable lambda-calculus reasoning posture with review needs"
    if risk >= 55:
        return "high formalization risk; binding, substitution, typing, or evaluation assumptions may be unclear"
    return "partial lambda-calculus reasoning posture; strengthen expression structure, traces, types, or governance"


def build_cases() -> list[LambdaExpressionCase]:
    return [
        LambdaExpressionCase(
            case_name="Identity reduction",
            computation_context="Basic beta reduction of an identity function.",
            formal_claim="The expression (lambda x. x) a reduces to a.",
            expression_clarity=0.92,
            binding_safety=0.90,
            substitution_discipline=0.92,
            reduction_traceability=0.90,
            evaluation_strategy_clarity=0.82,
            recursion_awareness=0.70,
            type_discipline_clarity=0.82,
            proof_connection=0.76,
            implementation_relevance=0.78,
            governance_readiness=0.74,
        ),
        LambdaExpressionCase(
            case_name="Capture-avoiding substitution",
            computation_context="Substitution where variable names must be managed carefully.",
            formal_claim="Alpha conversion prevents free variables from becoming accidentally bound.",
            expression_clarity=0.84,
            binding_safety=0.90,
            substitution_discipline=0.88,
            reduction_traceability=0.82,
            evaluation_strategy_clarity=0.74,
            recursion_awareness=0.64,
            type_discipline_clarity=0.76,
            proof_connection=0.78,
            implementation_relevance=0.82,
            governance_readiness=0.78,
        ),
        LambdaExpressionCase(
            case_name="Fixed-point recursion",
            computation_context="Recursive behavior represented through fixed points.",
            formal_claim="A fixed-point combinator enables self-referential computation.",
            expression_clarity=0.76,
            binding_safety=0.76,
            substitution_discipline=0.78,
            reduction_traceability=0.74,
            evaluation_strategy_clarity=0.80,
            recursion_awareness=0.90,
            type_discipline_clarity=0.68,
            proof_connection=0.76,
            implementation_relevance=0.82,
            governance_readiness=0.74,
        ),
        LambdaExpressionCase(
            case_name="Typed function abstraction",
            computation_context="Typed lambda expression used to model safe function application.",
            formal_claim="A function with type A to B may only be applied to values of type A.",
            expression_clarity=0.86,
            binding_safety=0.84,
            substitution_discipline=0.82,
            reduction_traceability=0.78,
            evaluation_strategy_clarity=0.76,
            recursion_awareness=0.68,
            type_discipline_clarity=0.92,
            proof_connection=0.86,
            implementation_relevance=0.86,
            governance_readiness=0.82,
        ),
    ]


def run_audit() -> list[dict[str, object]]:
    rows: list[dict[str, object]] = []
    for case in build_cases():
        quality = lambda_reasoning_quality(case)
        risk = formalization_risk(case)
        rows.append({
            **asdict(case),
            "lambda_reasoning_quality": round(quality, 3),
            "formalization_risk": round(risk, 3),
            "diagnostic": diagnose(quality, risk),
        })
    return rows


def write_csv(path: Path, rows: list[dict[str, object]]) -> None:
    path.parent.mkdir(parents=True, exist_ok=True)
    with path.open("w", newline="", encoding="utf-8") as handle:
        writer = csv.DictWriter(handle, fieldnames=list(rows[0].keys()))
        writer.writeheader()
        writer.writerows(rows)


def write_json(path: Path, payload: object) -> None:
    path.parent.mkdir(parents=True, exist_ok=True)
    path.write_text(json.dumps(payload, indent=2, sort_keys=True), encoding="utf-8")


def summarize(rows: list[dict[str, object]]) -> dict[str, object]:
    return {
        "case_count": len(rows),
        "average_lambda_reasoning_quality": round(mean(float(row["lambda_reasoning_quality"]) for row in rows), 3),
        "average_formalization_risk": round(mean(float(row["formalization_risk"]) for row in rows), 3),
        "highest_quality_case": max(rows, key=lambda row: float(row["lambda_reasoning_quality"]))["case_name"],
        "highest_risk_case": max(rows, key=lambda row: float(row["formalization_risk"]))["case_name"],
        "interpretation": "Lambda-calculus reasoning quality depends on expression clarity, binding safety, substitution discipline, reduction traceability, evaluation strategy, recursion awareness, type discipline, proof connection, implementation relevance, and governance."
    }


def main() -> None:
    rows = run_audit()
    summary = summarize(rows)

    write_csv(TABLES / "lambda_expression_audit.csv", rows)
    write_csv(TABLES / "lambda_expression_audit_summary.csv", [summary])
    write_json(JSON_DIR / "lambda_expression_audit.json", rows)
    write_json(JSON_DIR / "lambda_expression_audit_summary.json", summary)

    print("Lambda expression audit complete.")
    print(TABLES / "lambda_expression_audit.csv")


if __name__ == "__main__":
    main()

This workflow treats lambda calculus as a formal reasoning system where expression structure, binding, substitution, reduction, types, and evaluation strategy must remain visible.

Back to top ↑

R Workflow: Functional Structure Summary

The R workflow reads the Python-generated audit table and creates summary outputs and visualizations using base R. It compares lambda-reasoning quality and formalization risk across synthetic examples.

# lambda_expression_summary.R
# Base R workflow for summarizing lambda-calculus and formal-computation examples.

args <- commandArgs(trailingOnly = FALSE)
file_arg <- grep("^--file=", args, value = TRUE)

if (length(file_arg) > 0) {
  script_path <- normalizePath(sub("^--file=", "", file_arg[1]), mustWork = TRUE)
  article_root <- normalizePath(file.path(dirname(script_path), ".."), mustWork = TRUE)
} else {
  article_root <- getwd()
}

setwd(article_root)

tables_dir <- file.path(article_root, "outputs", "tables")
figures_dir <- file.path(article_root, "outputs", "figures")

if (!dir.exists(tables_dir)) {
  dir.create(tables_dir, recursive = TRUE)
}

if (!dir.exists(figures_dir)) {
  dir.create(figures_dir, recursive = TRUE)
}

input_path <- file.path(tables_dir, "lambda_expression_audit.csv")

if (!file.exists(input_path)) {
  stop(paste("Missing", input_path, "Run the Python workflow first."))
}

data <- read.csv(input_path, stringsAsFactors = FALSE)

summary_table <- data.frame(
  case_count = nrow(data),
  average_lambda_reasoning_quality = mean(data$lambda_reasoning_quality),
  average_formalization_risk = mean(data$formalization_risk),
  highest_quality_case = data$case_name[which.max(data$lambda_reasoning_quality)],
  highest_risk_case = data$case_name[which.max(data$formalization_risk)]
)

write.csv(
  summary_table,
  file.path(tables_dir, "r_lambda_expression_summary.csv"),
  row.names = FALSE
)

comparison_matrix <- rbind(
  data$lambda_reasoning_quality,
  data$formalization_risk
)

colnames(comparison_matrix) <- data$case_name
rownames(comparison_matrix) <- c("Lambda-reasoning quality", "Formalization risk")

png(
  file.path(figures_dir, "lambda_reasoning_quality_vs_risk.png"),
  width = 1400,
  height = 800
)

barplot(
  comparison_matrix,
  beside = TRUE,
  las = 2,
  ylim = c(0, 100),
  ylab = "Score",
  main = "Lambda Reasoning Quality vs. Formalization Risk"
)

legend(
  "topleft",
  legend = rownames(comparison_matrix),
  pch = 15,
  bty = "n"
)

grid()
dev.off()

png(
  file.path(figures_dir, "lambda_reasoning_dimensions.png"),
  width = 1400,
  height = 800
)

dimension_means <- colMeans(data[, c(
  "expression_clarity",
  "binding_safety",
  "substitution_discipline",
  "reduction_traceability",
  "evaluation_strategy_clarity",
  "recursion_awareness",
  "type_discipline_clarity",
  "proof_connection",
  "implementation_relevance",
  "governance_readiness"
)]) * 100

barplot(
  dimension_means,
  las = 2,
  ylim = c(0, 100),
  ylab = "Average score",
  main = "Average Lambda-Calculus Evidence by Dimension"
)

grid()
dev.off()

print(summary_table)

This workflow helps compare identity reduction, capture-avoiding substitution, fixed-point recursion, typed abstraction, and other formal-computation examples by how clearly they expose structure and assumptions.

Back to top ↑

GitHub Repository

The companion repository for this article will provide reproducible code, synthetic datasets, workflow documentation, generated outputs, and lambda-calculus diagnostics that extend the article into executable examples.

articles/lambda-calculus-functions-and-formal-computation/
├── python/
│   ├── lambda_expression_audit.py
│   ├── lambda_reducer.py
│   ├── substitution_examples.py
│   ├── church_encoding_examples.py
│   ├── typed_lambda_examples.py
│   ├── calculators/
│   │   ├── lambda_reasoning_quality_calculator.py
│   │   └── formalization_risk_calculator.py
│   └── tests/
├── r/
│   ├── lambda_expression_summary.R
│   ├── functional_structure_visualization.R
│   └── reduction_trace_report.R
├── julia/
│   ├── lambda_reduction_examples.jl
│   └── church_numeral_examples.jl
├── sql/
│   ├── schema_lambda_cases.sql
│   ├── schema_reduction_traces.sql
│   └── lambda_calculus_queries.sql
├── haskell/
│   ├── LambdaTerms.hs
│   ├── Reducer.hs
│   └── Main.hs
├── rust/
│   └── src/
├── go/
│   └── main.go
├── c/
│   └── lambda_reasoning_audit.c
├── cpp/
│   └── lambda_reasoning_audit.cpp
├── fortran/
│   └── lambda_quality_model.f90
├── java/
│   └── src/main/java/org/contentcatalyst/algorithms/
├── typescript/
│   └── src/
├── prolog/
│   └── lambda_rules.pl
├── racket/
│   └── lambda_reduction_interpreter.rkt
├── docs/
│   ├── methodology.md
│   ├── article-notes.md
│   ├── lambda-calculus-functions-and-formal-computation.md
│   ├── governance-notes.md
│   └── responsible-use.md
├── data/
│   └── synthetic_lambda_expression_cases.csv
├── outputs/
│   ├── tables/
│   ├── figures/
│   ├── json/
│   ├── logs/
│   └── reports/
├── notebooks/
│   └── lambda_calculus_functions_and_formal_computation_walkthrough.ipynb
├── canvas/
│   ├── canvas_manifest.json
│   ├── canvas_cards.json
│   └── canvas_index.md
└── shared/
    ├── schemas/
    ├── templates/
    ├── taxonomies/
    ├── benchmarks/
    └── governance/

Back to top ↑

A Practical Method for Lambda-Calculus Reasoning

A practical method for lambda-calculus reasoning begins by making the expression structure visible. The goal is to identify variables, bindings, applications, reduction steps, evaluation strategy, typing assumptions, and possible nontermination.

This method helps make lambda calculus useful for programming-language design, compiler reasoning, type systems, formal verification, and computational education.

Back to top ↑

Common Pitfalls

A common pitfall is treating lambda calculus as merely historical. In reality, it remains central to programming-language theory, functional programming, type theory, proof assistants, and formal computation.

Another pitfall is ignoring variable binding. Many errors in lambda-calculus reasoning come from careless substitution, accidental capture, or failure to distinguish free and bound variables.

Common pitfalls include:

• variable-capture errors: substituting expressions without alpha conversion when needed;
• confusing syntax with meaning: treating different variable names as different functions when they are alpha-equivalent;
• ignoring evaluation strategy: assuming all reduction orders behave the same;
• forgetting nontermination: assuming every expression reduces to normal form;
• overlooking types: using untyped examples without explaining what typed systems would reject;
• mistaking encoding for convenience: assuming Church encodings are always practical data structures;
• separating functions from proof: missing the connection between typed programs and logical propositions;
• overformalization: treating formal expression structure as if it captures all real-world context;
• implementation confusion: assuming programming-language syntax exactly matches pure lambda calculus;
• lost reduction traces: failing to show the steps that justify a computational result.

The remedy is disciplined symbolic practice: track binding, substitution, reduction, types, evaluation strategy, and interpretation.

Back to top ↑

Why Lambda Calculus Still Matters

Lambda calculus still matters because it reveals computation in one of its purest forms. A function is abstracted. An argument is applied. An expression is reduced. From these simple operations, a vast theory of computation, programming languages, type systems, recursion, proof, and formal reasoning emerges.

Its importance is not only theoretical. The ideas of lambda calculus appear in everyday programming through anonymous functions, closures, callbacks, higher-order functions, currying, type inference, lazy evaluation, and functional composition. They appear in advanced systems through proof assistants, typed intermediate languages, theorem proving, verified compilers, and formal semantics.

Lambda calculus teaches a lasting lesson for computational reasoning: the structure of computation matters. Names, scopes, substitutions, reductions, types, and evaluation rules are not incidental details. They are the formal grammar through which functions become computation.

Back to top ↑

Related Articles

• Logic and Computation
• Formal Languages and Symbolic Representation
• Proof, Correctness, and Algorithmic Verification
• Termination, Invariants, and Edge Cases
• Computability and the Limits of Procedure
• The Halting Problem and the Limits of Automation
• Automated Reasoning and Mechanical Inference
• Formal Methods and Machine-Checked Reasoning

Further Reading

• Abelson, H. and Sussman, G.J. (1996) Structure and Interpretation of Computer Programs. 2nd edn. Cambridge, MA: MIT Press. Available at: MIT Press.
• Barendregt, H.P. (1984) The Lambda Calculus: Its Syntax and Semantics. Revised edn. Amsterdam: North-Holland. Publisher information available at: Elsevier.
• Church, A. (1932) ‘A set of postulates for the foundation of logic’, Annals of Mathematics, 33(2), pp. 346–366. Available through: JSTOR.
• Church, A. (1936) ‘An unsolvable problem of elementary number theory’, American Journal of Mathematics, 58(2), pp. 345–363. Available through: JSTOR.
• Girard, J.-Y., Lafont, Y. and Taylor, P. (1989) Proofs and Types. Cambridge: Cambridge University Press. Available through the author archive at: Paul Taylor Archive.
• Hindley, J.R. and Seldin, J.P. (2008) Lambda-Calculus and Combinators: An Introduction. 2nd edn. Cambridge: Cambridge University Press. Available at: Cambridge University Press.
• Pierce, B.C. (2002) Types and Programming Languages. Cambridge, MA: MIT Press. Available at: MIT Press.
• Pierce, B.C. et al. (2024) Software Foundations. Electronic textbook series. Available at: University of Pennsylvania.
• Reynolds, J.C. (1998) Theories of Programming Languages. Cambridge: Cambridge University Press. Available at: Cambridge University Press.
• Selinger, P. (2008) Lecture Notes on the Lambda Calculus. Dalhousie University. Available at: Dalhousie University.
• Sørensen, M.H. and Urzyczyn, P. (2006) Lectures on the Curry-Howard Isomorphism. Amsterdam: Elsevier. Publisher information available at: Elsevier.

References

• Abelson, H. and Sussman, G.J. (1996) Structure and Interpretation of Computer Programs. 2nd edn. Cambridge, MA: MIT Press. Available at: https://mitpress.mit.edu/9780262510875/structure-and-interpretation-of-computer-programs/.
• Barendregt, H.P. (1984) The Lambda Calculus: Its Syntax and Semantics. Revised edn. Amsterdam: North-Holland. Publisher information available at: https://www.elsevier.com/books/the-lambda-calculus/barendregt/978-0-444-87508-2.
• Church, A. (1932) ‘A set of postulates for the foundation of logic’, Annals of Mathematics, 33(2), pp. 346–366. Available at: https://www.jstor.org/stable/1968337.
• Church, A. (1936) ‘An unsolvable problem of elementary number theory’, American Journal of Mathematics, 58(2), pp. 345–363. Available at: https://www.jstor.org/stable/2371045.
• Girard, J.-Y., Lafont, Y. and Taylor, P. (1989) Proofs and Types. Cambridge: Cambridge University Press. Author archive available at: https://www.paultaylor.eu/stable/Proofs+Types.html.
• Hindley, J.R. and Seldin, J.P. (2008) Lambda-Calculus and Combinators: An Introduction. 2nd edn. Cambridge: Cambridge University Press. Available at: https://www.cambridge.org/core/books/lambdacalculus-and-combinators/3A3E409B7F6B50A09D16C0E27D251C71.
• Pierce, B.C. (2002) Types and Programming Languages. Cambridge, MA: MIT Press. Available at: https://mitpress.mit.edu/9780262162098/types-and-programming-languages/.
• Pierce, B.C. et al. (2024) Software Foundations. Electronic textbook series. Available at: https://softwarefoundations.cis.upenn.edu/.
• Reynolds, J.C. (1998) Theories of Programming Languages. Cambridge: Cambridge University Press. Available at: https://www.cambridge.org/core/books/theories-of-programming-languages/49BC03459ED4CC02CB2E1F9A1C17E3E1.
• Selinger, P. (2008) Lecture Notes on the Lambda Calculus. Dalhousie University. Available at: https://www.mscs.dal.ca/~selinger/papers/lambdanotes.pdf.
• Sørensen, M.H. and Urzyczyn, P. (2006) Lectures on the Curry-Howard Isomorphism. Amsterdam: Elsevier. Publisher information available at: https://www.elsevier.com/books/lectures-on-the-curry-howard-isomorphism/sorensen/978-0-444-52077-7.

Back to top ↑