lambda calculus Hoe moet e-mail: (λx.jwkxcs.vu.nl)@ gelezen worden? Met lambda calculus (λ-calculus). De λ-calculus is de eenvoudigste programmeertaal die bestaat - de ‘oerprogrammeertaal’. De woorden in die taal heten λ-termen. Die worden successievelijk getransformeerd totdat een λ-term ontstaat die een ‘antwoord’ voorstelt. Eén enkele regel of voorschrift, volstaat om deze transformaties uit te voeren, de beta-regel (β-regel). Het wonder van de λ-calculus is dat die β-regel zo simpel is, en dat er toch elke berekening of symboolmanipulatie, hoe ingewikkeld ook, mee kan worden uitgevoerd. In de λ-calculus wordt het begrip ‘berekenen’ of ‘manipuleren met symbolen’, met informatie, tot de kleinst denkbare bestanddelen teruggebracht. De werking van deze magische regel bestaat eenvoudig uit het invullen van een woord in een tweede woord op de daarvoor aangegeven plaatsen. In de volgende voorbeelden kleuren we het woord dat wordt ingevuld rood, en het woord waarin wordt ingevuld, blauw. De plaatsen waar wordt ingevuld zijn zwarte letters (officieel variabelen), en de variabele waarvoor moet worden ingevuld staat achter de λ. Bijvoorbeeld. Vul voor elke letter z in het woord ziezo het woord aap in. Het resultaat is dan aapieaapo. Deze herschrijfstap of β-reductiestap wordt in wiskundige notatie zo opgeschreven: (λz. ziezo) aap → aapieaapo Een ander voorbeeld van een herschrijfstap is (λa. aap) ziezo → ziezoziezop In de taal van logica en wiskunde mogen woorden ook haakjes bevatten: ‘(‘ en ‘)’. Behalve deze symbolen wordt ook nog de punt ‘.’ gebruikt, zoals ook in de voorbeelden boven. We laten de kleuren verder weg. Een woord (officieel, een λ-term) kan ook uit een enkele letter bestaan. Dus we hebben ook bijvoorbeeld de stappen (λx.x)aap → aap (λx.yxy)z → yzy Een meer zinvol voorbeeld is het verdubbelen van woorden: (λx.xx)aap → aapaap Dus (λx.xx) is een woordverdubbelaar, elk woord waarop deze λ-term wordt ‘toegepast’, wordt in één stap verdubbeld. Een woord uitwissen kan ook: (λa.goed)slecht → goed Want goed bevat geen a! λ-termen kunnen ook op zichzelf worden toegepast: zelfapplicatie. Voor de verdubbelaar levert dit een interessant verschijnsel op: (λx.xx)(λx.xx) → (λx.xx)(λx.xx) Het is inmiddels wel in te zien dat (λx.jwkxcs.vu.nl)@ → het emailadres van J.W. Klop.

lambda calculus

Hoe moet e-mail: (λx.jwkxcs.vu.nl)@ gelezen worden? Met lambda calculus (λ-calculus).

De λ-calculus is de eenvoudigste programmeertaal die bestaat - de ‘oerprogrammeertaal’. De woorden in die taal heten λ-termen. Die worden successievelijk getransformeerd totdat een λ-term ontstaat die een ‘antwoord’ voorstelt. Eén enkele regel of voorschrift, volstaat om deze transformaties uit te voeren, de beta-regel (β-regel). Het wonder van de λ-calculus is dat die β-regel zo simpel is, en dat er toch elke berekening of symboolmanipulatie, hoe ingewikkeld ook, mee kan worden uitgevoerd. In de λ-calculus wordt het begrip ‘berekenen’ of ‘manipuleren met symbolen’, met informatie, tot de kleinst denkbare bestanddelen teruggebracht. De werking van deze magische regel bestaat eenvoudig uit het invullen van een woord in een tweede woord op de daarvoor aangegeven plaatsen. In de volgende voorbeelden kleuren we het woord dat wordt ingevuld rood, en het woord waarin wordt ingevuld, blauw. De plaatsen waar wordt ingevuld zijn zwarte letters (officieel variabelen), en de variabele waarvoor moet worden ingevuld staat achter de λ.

Bijvoorbeeld. Vul voor elke letter z in het woord ziezo het woord aap in.

Het resultaat is dan aapieaapo. Deze herschrijfstap of β-reductiestap wordt in wiskundige notatie zo opgeschreven:

(λz. ziezo) aap → aapieaapo

Een ander voorbeeld van een herschrijfstap is

(λa. aap) ziezo → ziezoziezop

In de taal van logica en wiskunde mogen woorden ook haakjes bevatten:

‘(‘ en ‘)’. Behalve deze symbolen wordt ook nog de punt ‘.’ gebruikt, zoals ook in de voorbeelden boven. We laten de kleuren verder weg.

Een woord (officieel, een λ-term) kan ook uit een enkele letter bestaan. Dus we hebben ook bijvoorbeeld de stappen

(λx.x)aap → aap

(λx.yxy)z → yzy

Een meer zinvol voorbeeld is het verdubbelen van woorden:

(λx.xx)aap → aapaap

Dus (λx.xx) is een woordverdubbelaar, elk woord waarop deze λ-term wordt ‘toegepast’, wordt in één stap verdubbeld. Een woord uitwissen kan ook:

(λa.goed)slecht → goed

Want goed bevat geen a!

λ-termen kunnen ook op zichzelf worden toegepast: zelfapplicatie. Voor de verdubbelaar levert dit een interessant verschijnsel op:

(λx.xx)(λx.xx) → (λx.xx)(λx.xx)

Het is inmiddels wel in te zien dat (λx.jwkxcs.vu.nl)@ → het emailadres van J.W. Klop.