Породження комбінаторних об’єктів

CAR-елементом визначення функції є ім’я типу фукції — LAMBDA, NLAMBDA чи MACRO. Тип функції дає інтерпретаторові інформацію про те, як використовувати дану функцію.

Визначення функцій та їх обчислення в Ліспі основано на лямбда-численні Чорча. Лямбда вираз, який взято з лямбда числення, є важливим механізмом у програмуванні. В лямбда численні Чорча функція записується у вигляді:

lambda (x1, x2, ..., xn) . f

В Ліспі лямбда вираз має вигляд:

(LAMBDA (x1 x2 ... xn) f)

Символ LAMBDA говорить нам про визначення функції. Символи xi – це формальні параметри, f – тіло функції. Тілом функції може бути довільна форма, значення якої може обчислити інтерпретатор Ліспа. Функцію, яка обчислює суму квадратів двох чисел, можна визначити так:

(LAMBDA (x y) (+ (* x x) (* y y)) )

Формальність параметрів вказує на те, що ми можемо замінити їх на інші символи, але від цього не зміниться сутність обчислення функції.

Лямбда вираз – це визначення обчислення та параметрів функції в чистому вигляді без фактичних параметрів або аргументів. Для застосування такої функції до певних аргументів, необхідно поставити лямбда вираз на місце імені функції:

(лямбда-вираз a1 a2 ... an)

Тут ai – форми, що задають фактичні параметри. Наприклад, множення (* 3 4) можна записати з використанням лямбда виклику:

$ ((LAMBDA (x y) (* x y)) 3 4)

12

Наступний виклик будує список з двох аргументів:

$ ((LAMBDA (x y) (CONS x (CONS y NIL))) ‘dog ‘cat)

(dog cat)Таку форму виклику називають лямбда викликом. Обчислення лямбда виклику відбувається в два етапи. Спочатку обчислюються значення фактичних параметрів та відповідні формальні параметри зв’язуються з отриманими значеннями. На другому етапі обчислюється форма, яка є тілом лямбда виразу. Отримане значення повертається в якості значення лямбда виклику. По завершенню обчислення формальним параметрам повертаються зв’язки , які існували до лямбда виклику. Весь цей процес називається лямбда перетворенням.

Пам’ятайте, що лямбда вираз без фактичних параметрів є лише визначення, а не форма, яку можна обчислити. Сам по собі лямбда вираз інтерпретатором не сприймається. Якщо ви введете: (LAMBDA (x y) (CONS x (CONS y NIL))), то інтерпретатор Ліспу видасть повідомлення про помилку.

Лямбда вираз є як чисто абстрактним механізмом для визначення та опису обчислення, так і механізмом для зв’язування формальних та фактичних параметрів під час виконання обчислення. Лямбда вираз є функцією без імені.

Ми вже говорили про те, як визначити нову функцію – це можна здійснити за допомогою функції DEFUN. Визначення функції викликається так:

(DEFUN <і’мя> <лямбда вираз>)

Для спрощення опустимо зовнішні дужки у лямбда виразі та сам атом LAMBDA. Тоді ми отримаємо знайоме нам визначення функції. Наступні визначення еквівалентні: