Пояснення і програми
Грецька буква lambda (?) використовується в лямбда-вирази та лямбда-терміни для позначення зв'язування змінної функції. Лямбда-числення може бути нетипизировано або надруковане. У першому варіанті функції можуть бути застосовані лише в тому випадку, якщо вони здатні приймати дані цього типу. Типізовані лямбда-числення слабкіше, можуть виражати менше значення. Але, з іншого боку, вони дозволяють доводити більше речей. Однією з причин того, що існує багато різних типів — це бажання вчених зробити більше, не відмовляючись від можливості доводити сильні теореми лямбда-числення. Система знаходить застосування в багатьох областях математики, філософії, лінгвістики, і комп'ютерних наук. В першу чергу, лямбда-числення — це розрахунок, який зіграв важливу роль у розвитку теорії мов програмування. Саме стилі функціонального створення реалізують системи. Вони також є актуальною темою досліджень в теорії цих категорій.Для чайників
Лямбда-числення була введена математиком Алонзо Черчем в 1930-х роках в рамках дослідження основ науки. Первісна система була показана як логічно несумісна в 1935 році, коли Стівен Клин і Дж. Б. Россер розробили парадокс Кліні-Россера. Надалі, у 1936 році Черч виділив і опублікував тільки ту частину, яка має відношення до розрахунків, те, що зараз називається нетипизированным лямбда-обчисленням. У 1940 він також представив більше слабку, але логічно несуперечливу теорію, відому як система простого типу. У свій роботі він пояснює всю теорію простою мовою, тому, можна сказати, що Черч опублікував лямбду обчислення для чайників. До 1960-х років, коли з'ясувалося його ставлення до мов програмування, ? стала лише формалізмом. Завдяки застосуванням Річарда Монтегю та інших лінгвістів у семантиці природної мови, обчислення стало займати почесне місце як у лінгвістиці, так і в інформатиці.Походження символу
Лямбда не позначає слово або абревіатуру, вона виникла, завдяки посилання в «Принципової математики» Рассела, за якою слідують два типографських зміни. Приклад позначення: для функції f f (y) = 2y + 1 дорівнює 2? + 1. І тут використовується символ каретки («капелюх») над y для позначення вхідної змінної.Церква споконвічно мала намір використовувати аналогічні символи, але складачі не змогли розмістити символ «капелюх» над літерами. Тому замість цього вони надрукували його спочатку як «/y.2y+1». У наступному епізоді редагування складачі замінили «/» на візуально схожий символ.
Введення в лямбда обчислення
Система складається з мови термінів, які вибираються певним формальним синтаксисом, і набору правил перетворення, які дозволяють маніпулювати ними. Останній пункт можна розглядати як эквациональную теорію або як операційне визначення. Всі функції в лямбда-численні є анонімними, тобто не мають імен. Вони приймають тільки одну вхідну змінну, при цьому каррирование використовується для реалізації графіків з кількома непостійними.Лямбда-терміни
Синтаксис обчислення визначає деякі вирази як допустимі, а інші — як недійсні. Також, як різні рядки символів є допустимими програмами на Сі, а якісь-ні. Дійсне вираження лямбда-числення називається лямбда-терміном».Наступні три правила дають індуктивне визначення, яке можна застосовувати для побудови всіх синтаксично допустимих понять: Змінна x сама по собі є дійсним лямбда-терміном:
Визначення
Лямбда-вирази складаються з:Позначення
Щоб зберегти позначення лямбда-виразів в незагроможденном вигляді, зазвичай застосовуються наступні угоди:Вільні і зв'язані змінні
Оператор ? з'єднує свою мінливу, де б він ні знаходився в тілі абстракції. Змінні, що потрапляють в область, називаються пов'язаними. У виразі ? x. М, частина ? х часто називають зв'язуючим. Як би натякаючи, що змінні стають групою з додаванням Х до М. Всі інші нестійкі називаються вільними.Наприклад, у виразі ? y. х х у, у — пов'язана непостійна, а х - вільна. І також варто звернути увагу, що змінна згрупована своєї «найближчій» абстракцією. У наступному прикладі рішення лямбда-числення представлено єдиним входженням x, яке пов'язане другої складової: ? x. y (? x. z x) Безліч вільних змінних M позначається як FV (M) і визначається рекурсією за структурою термінів наступним чином:
Скорочення
Значення лямбда-виразів визначається тим, як вони можуть бути скорочені. Існує три види обрізання:Якщо x не є вільною в M, ? х. М х також ет-REDEX з регулятором М.
?-перетворення
Альфа-перейменування дозволяють змінювати імена пов'язаних змінних. Наприклад, ? x. х може дати ? у. у. Терміни, які відрізняються тільки альфа-перетворенням, називаються ?-еквівалентними. Часто при використанні лямбда-числення ?-еквівалентні вважаються взаємними. Точні правила для альфа-перетворення не зовсім тривіальні. По-перше, при даної абстракції перейменовуються тільки ті змінні, які пов'язані з однією і тією ж системою. Наприклад, альфа-перетворення ? x.? x. x може призвести до ? y.? x. х, але це може не призвести до ?y.?x.y Останній має інший зміст, ніж оригінал. Це аналогічно поняттю програмування затінення змінних. По-друге, альфа-перетворення неможливо, якщо воно призведе до захоплення непостійною інший абстракцією. Наприклад, якщо замінити x на y ? x.? y. x, то можна отримати ? y.? y. у, що зовсім не те ж саме. У мовах програмування зі статичною областю видимості альфа-перетворення можна використовувати для спрощення дозволу імен. При цьому стежачи за тим, щоб поняття змінної не маскувало позначення, що містить області. У нотації індексу Де Брюйна будь-які два альфа-еквівалентних терміна синтаксично ідентичні.Заміна
Зміни, написані Е[V: = R], являють собою процес заміщення всіх вільних входжень змінної V у вираженні Е з обігом R. Підстановка в термінах ? визначається лямбдой обчислення рекурсії за структурою понять наступним чином (примітка: x і y - тільки змінні, а M і N - будь-яке ?-вираз).x[x: = N]? N y[x: = N]? y, якщо x ? y (M 1 M 2)[x: = N]? (M 1[x: = N]) (M 2[x: = N]) (? x.M)[x: = N]? ? x.M (? y.M)[x: = N]y ? y. (M[x: = N]), якщо x ? y, за умови, що y ? FV (N). Для підстановки в лямбда-абстракцію іноді необхідно ?-перетворити вираз. Наприклад, невірно, щоб (? x. Y)[y: = x]призводило до (? x. X), тому що замещенный x повинен був бути вільним, але в підсумку був пов'язаним. Правильна заміна у цьому випадку (? z. X) з точністю до ?-еквівалентності. Варто звернути увагу, що заміщення визначається однозначно з вірністю до лямбды.