Lambdakalkyle

Lambdakalkyle (også Lambda-kalkyle eller Lambda kalkyle) er et formelt system indenfor den matematiske logik. Systemet giver en formel notation for definition af funktioner udtrykt ved et antal ubundne variable. Systemet og den tilhørende notation blev oprindelig opfundet af den amerikanske matematiker Alonzo Church i 1930'erne som et værktøj i studiet af matematikkens fundament. Systemet kan imidlertid også opfattes som en fundamental notation for computer programmering og mødes derfor også indenfor datalogien. En række programmeringssprog kaldet funktionssprog implementerer forskellige maskinelle fortolkninger af lambdakalkylen, f.eks. LISP, men disse har indtil midt i 00'erne primært været af teoretisk interesse. I dag er anonyme funktioner dog almindeligt brugt i mainstream sprog som C# og JavaScript.

Notation

Systemet betegnes "lambda" kalkyle fordi man benytter det græske bogstav Lambda til at denotere den ubundne variabel i et udtryk. F.eks. betegner λx.x+1 den funktion der lægger et til et tal. Dette skal sammenlignes med den "normale" matematiske notation f(x)=x+1 der betegner den samme funktion, men hvor man samtidig tildeler funktionen navnet "f". Herved adskiller tænkemåden i "normal" matematik sig fra den matematiske logik, hvor man i den "normale" matematik netop vælger bogstavet f, det første bogstav i ordet funktion, for at antyde at navnet er uden betydning.

I et (fiktivt) programmeringssprog, det der kaldes pseudokode, kunne man f.eks. skrive

function f(x integer)
begin
 return x+1
end

Men her har navnet betydning. I næsten samtlige nuværende "mainstream" programmeringssprog er det muligt at give angive en funktion som parameter til en anden funktion, men i de sprog hvor man ikke kan angive anonyme funktioner er det ikke muligt at angive en funktionsparameter direkte, men man må erklære den først og så angive navnet som parameteren. I sprog der tillader anonyme funktioner kan man derimod angive funktionen direkte som parameter, hvilket i nogen tilfælde giver programkode der er nemmere at læse (udover læselighed er det også andre årsager til at anonyme funktioner kan være ønskelige).

Leksikalsk parsning

I den matematiske logik beskæftiger man sig bl.a. med hvor få antagelser man kan nøjes med for at kunne påbegynde matematisk argumentation. En problemstilling her er forståelsen af matematiske udtryk, f.eks. hvis man skriver en tekststreng x+1, hvordan kan man så med sikkerhed udpege at x er den ubundne variabel der kan erstattes med "noget andet" mens + og 1 har givne betydninger. Her er det i udtrykket f(x)=x+1 klart at det er teksten mellem ( og ) der angiver den ubundne variabel, mens det i λx.x+1 er teksten mellem λ og .

I den almindelige matematiske notation må man for at påtrykke funktionen imidlertid bruge 2 skridt og skrive

f(x)=x+1
f(7)

for at få svaret 8.

I lambdakalkylen kan man imidlertid nøjes med et skridt og skrive

(λx.x+1)(7)