Alonzo Church skulle løse et problem; et matematisk problem kaldet Entscheidungsproblem, eller beslutningsproblemet på dansk. Er det muligt at konstruere en algoritme, der kan tage ethvert matematisk udsagn og bevise, at det enten er sandt eller falsk?
For at kunne besvare det spørgsmål måtte Alonzo Church først definere et formelt system i matematisk logik, der kunne hjælpe ham med at modellere beregnelighed. Lambda-kalkuler var født, og det hjalp Alonzo Church til at løse Entscheidungsproblemet i 1936. Han kom frem til, at det ikke er muligt at konstruere en algoritme, der kan bevise ethvert matematisk udsagn. Kort tid efter nåede en anden teoretisk matematiker, Alan Turing, frem til samme konklusion som Alonzo; ikke ved at benytte lambda-kalkuler, men ved hjælp af sin logiske konstruktion, Turing-maskine.
Det første funktionelle sprog
På det tidspunkt fandtes der slet ikke nogle computere, men Alonzo Churchs og Alan Turings arbejde fik vidtrækkende betydning for de computere og den software, som blev bygget i de følgende år. Turing-maskinen blev det teoretiske fundament for de imperative sprog, mens Alonzo Churchs lambda-kalkuler blev grundlaget for funktionelle sprog. Den amerikanske datalog og pioner inden for kunstig intelligens, John McCarthy, var den første til at blive inspireret af lambda-kalkuler til at udvikle et programmeringssprog. Han så muligheden for at udnytte matematisk logik til at skabe kunstig intelligens og udviklede Lisp i 1958 på basis af Churchs lambda-kalkuler. Lisp blev hurtigt det foretrukne programmeringssprog for datidens kunstig intelligens-programmer. Lisp var blot det første i en række funktionelle programmeringssprog, der siden er kommet til. Mange af dem anvendes mest til forskning og undervisning, men i de senere år er der kommet nye sprog til, som bygger videre på de funktionelle dyder og kombinerer dem med objektorienterede principper. Resultatet er hybride sprog som F# på .Net-platformen og Scala til Java-platformen, der er anvendes til at udvikle kommercielle systemer. Til forskel fra de hybride former findes eksempelvis Haskell, der betegnes som et rent (pure) funktionelt programmeringssprog. Haskell tillader eksempelvis ikke, at der er nogen sideeffekter, når en funktion eksekveres, til forskel fra F#.
Rene og hybride former
Men det er ikke kun sprog som F#, der baserer sig på det funktionelle paradigme og har fået tilsat objektorienterede features, som er med til at bringe funktionel programmering ud til mainstream-programmører. Funktionelle features begynder at snige sig ind i eksisterende mainstream-objektorienterede programmeringssprog som eksempelvis C#. Specielt udbredelsen af flerkerne-processorer er med til at gøre det funktionelle programmeringsparadigme interessant. I stedet for at øge klok-frekvensen tilbyder chipproducenterne i dag mere regnekraft ved at introducere flere kerner på en chip. Det er således op til programmørerne at udnytte kernerne ved at skrive kode, der kan deles op og eksekveres parallelt. Her kan funktionelle programmeringssprog med immutable objekter (objekter, som ikke kan ændres, efter at de er oprettet), ingen sideeffekter og ingen delt memory mellem funktioner være med til at gøre parallel eksekvering af kode på flere kerner nemmere.
Så da Alonzo Church i 1936 løste Entscheidungsproblemet ved hjælp af lambda-kalkulerne, var han på en måde også med til at løse problemer for programmører i dag.