Обчислення в Ліспі

Програма складається з форм та функцій

Під формою розуміється таке символьне вираження, значення може бути знайдено інтерпретатором. Раніше вже використовували найпростіші форми мови: константи, змінні, лямбда-дзвінки, виклики функцій та їх поєднання. Крім них були розглянуті деякі спеціальні форми, такі як'іsetq, які трактують свої аргументи інакше, ніж звичайні функції. Лямбда-вираз без фактичних параметрів не є формою. Обчислювані вирази можна поділити на три групи:

  1. Самовизначені форми. Ці форми, подібно до константів, є об'єктами, що представляють лише самих себе. Це такі форми, як числа та спеціальні константиtrue,falseтаnil, а також знаки та рядки.
  2. Символи, які використовуються як змінні.
  3. Форми у вигляді облікової структури, якими є:
  1. Виклики функцій та лямбда-дзвінки.
  2. Спеціальні форми, в які входятьsetq,'та багато описаних у цьому розділі форми, призначені для управління обчисленням та контекстом.
  3. Макровикли (розглянуті пізніше).
У кожної форми свій синтаксис та семантика, засновані, однак, на єдиному способі запису та інтерпретації.

Керівні структури Лиспа є формами

У поширених процедурних мовах поряд з основними діями є спеціальні керуючі механізми розгалуження обчислень та організації циклів. У Паскалі, наприклад, використовуються структуриіf then else,while do,caseта інші. Керуючі структури Лиспа (будемо для них використовувати термін пропозицію) виглядають зовні як виклики функцій. Пропозиції будуть записуватись у вигляді дужних виразів, другий елемент яких діє як ім'я керуючоїструктури, інші елементи - як " аргументи " . Результатом обчислення, як і в функції, є значення, тобто. Керівні структури є форми. Проте пропозиції є викликами функцій, і різні пропозиції використовують аргументи по-різному. Найбільш важливі з точки зору програмування синтаксичні форми можна на основі їх використання розділити на такі групи:Робота з контекстом:-'або блокування обчислення; - виклик функції та лямбда-виклик; - Пропозиціяlet.Форма виконання:- покроковаprogn; - паралельнаparallel; - незалежнаfork.Розгалуження обчислень:- умовні пропозиціїcond,if.Ітерації:- циклічні реченняfor,for*,while,do-while. Раніше вже розглядали форму', а також лямбда-виклик та виклик функції. Ці форми тісно пов'язані з механізмом визначення функцій та їхнього виклику. Інші форми переважно використовуються у тілі лямбда-выражений, визначальних функції.

LET створює локальний зв'язок

Обчислення функції створює на час обчислення нові зв'язки формальних параметрів функції. Нові зв'язки всередині форми можна створити за допомогою пропозиціїlet. Ця структура виглядає так:

Пропозиціяletобчислюється так, що спочатку динамічні змінніm1,m2, … з першого "аргументу" форми зв'язуються (одночасно) з відповідними значеннямизнач1,знач2, … Потім покроково обчислюються значення формформа1,форма2, … Як значення всієї форми повертається значення останньої форми. Як і у функцій, після закінчення обчислення зв'язку динамічних зміннихm1,m2, … ліквідуються і будь-які зміни їх значень (setq) небудуть видні ззовні. Наприклад:

Формаletє насправді синтаксичним видозміною лямбда-виклику, в якій формальні та фактичні параметри вміщені спільно на початку форми:

Тіло лямбда-виразу може складатися з декількох форм, які обчислюються покроково, і значення останньої форми повертається як значення лямбда-виклику. Значення змінним формиletприсвоюються одночасно. Це означає, що значення всіх змінних m i обчислюються до того, як здійснюється зв'язування з формальними параметрами. Нові зв'язку цих змінних ще діють у момент обчислення початкових значень змінних, які перелічені у вигляді пізніше. Наприклад:

Форма виконання: покрокова, паралельна та незалежна

Пропозиціїprogn,parallelіforkдозволяють працювати з декількома обчислюваними формами:

У цих спеціальних форм змінна кількість аргументів. Пропозиціяprognпокроково обчислює ці аргументи і повертає значення значення останнього аргументу. Пропозиціяparallelпаралельно обчислює всі ці аргументи і не повертає нічого, тобтоnil. Пропозиціяforkзапускає на обчислення форму(nil prognформа1 форма2 … формаn), не очікує її результату і нічого не повертає, тобтоnil. Ці форми не містять механізму визначення внутрішніх змінних:

За допомогою формиletпотрібно задавати область дії змінних. Дана форма дозволяє використовувати форми, що обчислюються покроково, і як результат повертає значення останньої форми. Цю властивість називають неявноюprogn.

Розгалуження обчислень: умовна пропозиція COND

Пропозиціяcondє основним засобомрозгалуження обчислень. Це синтаксична форма, що дозволяє керувати обчисленнями на основі умов, що визначаються предикатами. Структура умовної пропозиції така:

Предикатамиpiта результуючими виразамиaiможуть бути довільні форми. Значення реченняcondвизначається так:

  1. Виразиpi, що виконують роль предикатів, обчислюються покроково зліва направо (згори донизу) доти, доки не зустрінеться вираз, значенням якого не є ніnilніfalse, тобто. логічним значенням є істина.
  2. Обчислюється вираз, що відповідає цьому предикату, і отримане значення повертається як значення всієї пропозиціїcond.
  3. Якщо істинного предикату немає, то значенняcondбудеnil.
Рекомендується в якості останнього предикату використовувати символtrue, і відповідний вираз буде обчислюватися завжди в тих випадках, коли жодна інша умова не виконується. У наступному прикладі за допомогою пропозиціїcondвизначено функцію, що визначає тип виразу:

У умовному реченні може бути відсутній виразaiабо його місці часто може бути кілька форм:

Якщо умові не ставиться у відповідність вираз, то як результат пропозиціїcondпри істинності предикату видається саме значення предикату. Якщо ж умові відповідає кілька форм, то при його істинності форми обчислюються покроково зліва направо і результатом пропозиції буде значення останньої форми (неявнийprogn). Як приклад використання умовної пропозиції визначимо логічні дії логіки висловлюваньand,or,not,=>(імплікація) і (тотожність):

Імплікацію можна визначити через інші операції:

Предикатиandтаorвходять до складу вбудованих функцій Лиспа. Число їх аргументів може бути довільним.

Пропозиціїcondможна комбінувати так само, як і виклики функцій. Наприклад, предикатxor, який дійсний за наявності єдиного ствердного аргументу, можна визначити так:

У цій функції на місці вираження першої умови знову стоїть пропозиціяcond. На місці, певному умові, також можна використовувати ще одну умовну пропозицію, і в цьому випадку ми отримаємо умовну умову. Такі побудови дуже швидко призводять до важких визначень.

Інша умовна пропозиція: IF

Пропозиціяcondє найбільш загальну умовну структуру. Її критикують за велику кількість дужок і за те, що структура цієї пропозиції зовсім відірвана від природної мови. Тому в Лісп-системах використовуються й інші, у різних відносинах природніші, умовні пропозиції. Але можна обійтися і за допомогою лишеcondпропозиції. У простому випадку можна скористатися цілком природною і містить мало дужок формоюif.

(nil ifумова то-форма інакше-форма) ≡ (nil cond (умова то-форма) (trueінакше-форма))

Циклічні обчислення: пропозиції FOR, FOR*, WHILE та DO-WHILE

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

Покроково локальній змінній надаються числа від0дочисло-1. При кожному такому значенні обчислюється тіло циклу. Для прикладу за допомогою пропозиціїfor*визначимо функцію, що обчислюєn-у ступінь числа (n-ціле, позитивне):

Циклforвідрізняється відfor*тим, що в ньому все тіло обчислюється паралельно, і кожен процес має власну змінну. Застосовується цей цикл при обслуговуванні елементів вектора (у разі, якщо обчислення є незалежними від їх порядку). Ці цикли визначені ще для обслуговування елементів списку та рядків.

Наступний циклwhileпризначений для покроково виконуваних дій до отримання результатів, що задовольняють.

Циклdo-whileвідрізняється відwhileтільки порядком перевірки та дій:

Повторення через ітерацію чи рекурсію

У "чистому" функціональному Лиспі немає ні циклічних пропозицій (for,prognта інші), ні тим більше операторів передачі управління. Для програмування обчислень, що повторюються, в ньому використовуються лише умовні пропозиції та визначення рекурсивних, або викликають самих себе, функцій. Наприклад, рекурсивний варіант функціїexptможна було б визначити так:

Функціяexptвикликає себе доти, доки використовуваний як лічильник аргументnне зменшиться до одиниці, тобто. всього лишеn-1разів. Після цього як результат виклику функціїexptповертається значенняthis. При кожній передачі значення попередній рівень результат множиться наthis. Такthisвиявиться перемноженим вінnраз. Рекурсивне визначення функціїexptкоротше, і краще відбиває суть функції, ніж версії, засновані наfor*. Розглянемо ще одну функцію, що просто визначається через рекурсію, - факторіал (факторіал - це твір даного числа на всі цілі позитивні числа, менші від даного. Наприклад, факторіал від 5, позначений як 5!, є 1 * 2 * 3 * 4 *5 = 120. Факторіалом нуля вважається1):

Ітеративні та рекурсивні програми теоретично однакові за своїми обчислювальними можливостями, іншими словами, безлічі функцій, що обчислюються з їх допомогою, збігаються (так звані частково рекурсивні функції). Отже, будь-яке обчислення в принципі, можна запрограмувати будь-яким із цих способів. Однак властивості ітеративних та рекурсивних варіантів програм можуть суттєво відрізнятися. У зв'язку з цим часто доводиться вирішувати, який із способів програмування найбільше підходить для даної задачі. Від зробленого вибору залежить простота та природність програмування, і навіть його ефективність з погляду часу виконання та використання пам'яті. За допомогою ітеративного програмування, як правило, більш довгого та складного у здійсненні, результат може обчислюватися значно простіше та швидше. Це відбувається з двох причин, по-перше, тому, що обчислювальні машини загалом орієнтовані на покрокові обчислення, і, по-друге, тому, що транслятори не завжди в змозі перетворити рекурсивне визначення на ітеративне і використовують при обчисленнях стек, незважаючи на те що він не завжди потрібний. Рекурсивне програмування загалом більш коротке та змістовне. Особливо корисно використовувати рекурсію у випадках, коли вирішуване завдання чи оброблювані дані власне рекурсивні. Наприклад, математичне визначення факторіалу рекурсивне та його реалізація через рекурсивну функцію цілком природна:

n! = 1, якщо n=0
n! = n * (n-1)!, якщо n>0

Рекурсивне рішення добре підходить для роботи зі списками, оскільки списки можуть рекурсивно містити підписки. Рекурсивними функціями можна з успіхом користуватися прироботі з іншими динамічними структурами, які наперед не повністю відомі. Рекурсивні процедури займають важливе місце майже у всіх програмах, пов'язаних із штучним інтелектом.