simplytyped

Simplytyped, in the context of logic and computer science, refers to the simply typed lambda calculus (STLC). STLC is a typed version of the lambda calculus that assigns a simple type to every term, preventing ill‑formed expressions such as applying a non-function to an argument. The basic idea is to separate terms into base types and function types, so every term has a well-defined type.

Terms in STLC are built from variables, abstractions, and applications. Types are either base types (such as Bool or Nat) or function types T -> U. The typing judgments are written as Gamma ⊢ t : T, where Gamma is a context mapping variables to their types. The standard rules are: for a variable, if x : T ∈ Gamma then Gamma ⊢ x : T; for abstraction, if Gamma, x : T1 ⊢ t2 : T2 then Gamma ⊢ λx:T1. t2 : T1 -> T2; for application, if Gamma ⊢ t1 : T1 -> T2 and Gamma ⊢ t2 : T1 then Gamma ⊢ t1 t2 : T2. Reduction uses beta-reduction, with terms simplifying via (λx:T. t) v → t[x := v].

STLC enjoys type safety: well-typed terms do not get stuck, and every well-typed term terminates (strong normalization). Extensions add product types, sums, and booleans, while preserving many core properties. STLC serves as a foundational model in type theory and the design of many functional languages. It underpins the Curry–Howard correspondence, linking types to propositions and terms to proofs, and provides contrast to more expressive systems that support recursion or polymorphism, such as System F or dependently typed calculi.