Untyped Lambda Calculus Calculator

Calculator Input

Quick example

Reduction strategy

Maximum reduction steps

Lambda expression

Use variables, parentheses, application by spacing, and abstractions like \x. x or \x y. x.

Enable eta reduction when possible

Formula Used

This calculator follows standard untyped lambda calculus rules. Expressions are built from variables, abstractions, and applications. Application associates to the left, so a b c means ((a b) c).

Abstraction: λx. M defines a function with parameter x.
Application: (M N) applies term M to term N.
Beta reduction: (λx. M) N → M[x := N].
Alpha renaming: bound variables are renamed to avoid capture.
Eta reduction: λx. (F x) → F when x is not free in F.

Normal order reduces the outermost leftmost redex first. Applicative order reduces deeper arguments first, then performs beta substitution.

How to Use This Calculator

Enter a lambda expression using backslash notation such as \x. x.
Choose normal order or applicative order reduction.
Set a safe step limit for long or non-terminating expressions.
Turn eta reduction on when you want compact final forms.
Click Reduce Expression to see the final form above the form.
Review the trace, graph, free variables, and recognized Church encodings.
Export the trace as CSV or save the result block as PDF.

Example Data Table

Input Expression	Strategy	Expected Result	Notes
`(\x. x) y`	Normal	`y`	Simple identity reduction.
`(\x. \y. x) a b`	Normal	`a`	K combinator keeps the first argument.
`\f. \x. f (f x)`	Normal	`λf. λx. f (f x)`	Recognized as Church numeral 2.
`\t. \f. t`	Normal	`λt. λf. t`	Recognized as Church TRUE.
`\f. \x. f x`	Normal + eta	`f`	Eta reduction removes the final redundant wrapper.

Why This Helps in AI & Machine Learning

Lambda calculus is foundational for symbolic computation, functional semantics, reduction systems, and program transformations. This calculator helps explore term rewriting, expression normal forms, substitution safety, and compact reasoning patterns that also appear in interpreters, theorem provers, differentiable programming tools, and language-model reasoning experiments.

FAQs

1. What does this calculator compute?

It parses untyped lambda expressions, applies selected reduction rules, and shows the resulting form, trace, graph, free variables, and structural metrics.

2. What is the difference between normal and applicative order?

Normal order reduces the outermost leftmost redex first. Applicative order reduces inner arguments first. They can reach different intermediate traces and termination behavior.

3. Why can some expressions fail to finish?

Untyped lambda calculus allows non-terminating expressions, such as self-application patterns. The step limit prevents the tool from expanding forever.

4. What is alpha renaming here?

Alpha renaming changes bound variable names during substitution. It protects free variables from accidental capture and preserves meaning.

5. What does eta reduction do?

Eta reduction removes a redundant abstraction like λx. F x when x is not free in F. It produces a shorter equivalent term.

6. Can it detect Church numerals or booleans?

Yes. The result panel tries to recognize common Church numeral and boolean final forms after reduction completes.

7. How should I enter multi-argument lambdas?

Write them as \x y. x. The parser converts that into nested abstractions automatically, equivalent to \x. \y. x.

8. Why does the graph use term size?

Term size offers a quick visual measure of structural growth or contraction across reductions. It helps compare strategies and detect explosive traces.