Share this page

Learn X in Y minutes

Where X=Lambda Calculus

Calculo λ

Calculo lambda, creato principto per Alonzo Church, es lingua de programmatura computatro maximo parvo. Quamquam non habe numero, serie de charactere vel ullo typo de data non functionale, id pote repraesenta omne machina de Turing.

Tres elemento compone calculo lambda: quantitate variabile (q.v.), functione et applicatione.

Elemento Syntaxe Exemplo
Quantitate variabile <nomine> x
Functione λ<parametro>.<corpore> λx.x
Applicatione <functione><q.v. aut functione> (λx.x)a

Functione fundamentale es identitate: λx.x cum argumento primo x et cum corpore secundo x. In mathematica, nos scribe id: x↦x.

Quantitate variabile libero et ligato

Valutatione

Valutatione es facto per reductione beta (reductione β) que es essentialiter substitutione lexicale.

Dum valutatione de formula (λx.x)a, nos substitue omne evento de x in corpore de functione pro a.

Pote etiam crea functione de ordine supero: (λx.(λy.x))a vale λy.a.

Etsi calculo lambda solo tracta functione de uno parametro, nos pote crea functione cum plure argumento utente methodo de Curry: λx.(λy.(λz.xyz)) es scriptura informatica de formula mathematico f: x, y, z ↦ x(y(z))).

Ergo, interdum, nos ute λxy.<corpore> pro λx.λy.<corpore>.

Arithmetica

Logica de Boole

Es nec numero nec booleano in calculo lambda.

Primo, nos pote defini functione «si t tunc a alio b» per si = λtab.tab. Si t es vero, valutatione da (λxy.x) a b id es a. Similiter si t es falso, nos obtine b.

Secundo, nos pote defini operatore de logica:

Numeros

Nos pone:

Cum mente generale, successore de numero n es S n = λf.λx.f((n f) x) (n+1: f↦f⚬fⁿ). Id es n est functione que da fⁿ ex functione f.

Postremo additione es λab.(a S)b

Ut progrede

In lingua anglo

  1. A Tutorial Introduction to the Lambda Calculus per Raúl Roja
  2. The Lambda Calculus, CS 312 Recitation 26

Got a suggestion? A correction, perhaps? Open an Issue on the Github Repo, or make a pull request yourself!

Originally contributed by Max Sun, and updated by 0 contributor(s).