(składnia)

Marek Sawerwain: Rachunek lambda – czyli teoria dla wyrażeń lambda

Programista 5/2022 (104) wrzesień/październik [okładka]

Rachunek lambda – λ-rachunek – opracowany został przez Alonzo Church'a w latach trzydziestych ubiegłego wieku. Pierwotnie narzędzie to służyć miało do tłumaczenia podstaw matematyki, podobnie jak teoria mnogości. Zamiar ten, jak możemy dziś ocenić, nie powiódł się, a zamiast tego rachunek lambda znalazł zastosowanie w informatyce w teorii obliczania oraz stał się podstawą języków programowania w paradygmacie funkcyjnym (m.in. Lisp, Scheme, Standard-ML). W artykule podamy wstępne informacje o rachunku lambda w tzw. odmianie bez typów. Zaprezentujemy też jego składnię i semantykę, a także trzy podstawowe konwersje/redukcje: α, β, η (oznaczone greckimi literami alfa, beta, eta).