НОУ ІНТУІТ, Лекція, Функціональне програмування

Модель обчислень LISP

Для LISP (як і для будь-якої іншої функціональної мови) не обов'язково 2 А для запобігання трюкам хакерів і небажано! говорити, де і як розміщуються структури даних (списки).

лекція

Їх варто розглядати як суто математичні об'єкти зі складною структурою, яка завжди точно вказує на поточні обчислювальні елементи:

  1. До виконаннякроку обчислення - це список, що включає ім'я функції та її аргументи.
  2. Під час виконаннякроку обчислення — це фрагменти спискової структури поля зору , які доступні використання обчислюваної функцією (зокрема, у тому числі є список , що з ім'ям функції, що визначає її обчислювальний процес).
  3. Після виконаннякроку обчислень - це результати обчислень. Результати можна поділити на три групи:
  4. значення, яке видається викликом функції: воно заміщає в поле зору відпрацьований виклик функції;
  5. побічні ефекти, розкидані структурою поля даних;
  6. чергова функція, яка обчислюватиметься далі. У традиційному програмуванні зазвичай повертаються до обчислень тієї функції, яка активізувала завершальну. У функціональному програмуванні може бути інакше. Результат може виявитися функцією або описаною в статичному тексті програми або скомпонованою в ході обчислень.

Загальну структуру даних і програми функціональної мови можна розглядати як зв'язний навантажений граф, що динамічно змінюється в ході обчислень, у якого є активні вершини , тобто функції, що обчислюються в даний момент, потенційно активні вершини 10>, відповідні функцій, яким призначенообчислення або продовження обчислення (відкладеного, призупиненого тощо), та пасивні вершини, участь яких у обчисленнях в даний момент не заплановано. Дуги графа відзначають зв'язки з управління чи даних між функціями. Такий граф далі називається абстрактним графом функціональних обчислень.

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

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

У практиці реалізації функціональних систем програмування є три варіанти конкретизації подання графа:

  1. Списки LISP, пов'язані з послідовними обчисленнями. Структура графа задається як сукупність лінійних списків, що поєднують імена функцій та вказівники аргументів. Голова списку трактується як зазначення функції, а хвіст як аргументи.
  2. Комутаційні схеми, які будуються на основі поділу функцій і даних: функції надаються вершинами графа, а їх аргументи-дані передаються по дугах, що з'єднують вершини. Дуги розглядаються як канали зв'язку. Функція активізується, коли її аргументи з'являються каналах.
  3. Асоціативні схеми, у яких вершини-функції залишаються віртуальними. Вони утворюються внаслідок зв'язування даних, які мають однаковий ключ. Ситуація, коли такі дані з'являються в асоціативній пам'яті, сприймається як готовність аргументів для обчислення функції, що ідентифікується цим ключем.

Основні керуючі функціїконцептуально єдині та дозволяють динамічно будувати блокову структуру програми. Зокрема, функція

обчислює свої аргументи, починаючи з другого, один за одним, тим самим задаючи послідовність команд. Перший її аргумент, name, служить іменем блоку. У будь-який момент з будь-якого об'ємного блоку можна вийти і видати значення за допомогою функції

Цим LISP вигідно відрізняється більшості мов, де такі структурні переходи або неповні, або некоректно реалізовані.

Далі блоком вважається будь-який опис функції. Опис функції проводиться за допомогою функції defun, яка, у свою чергу, визначається через примітиви function і lambda. Перший задає, що ім'я, що є його аргументом, розглядається як функція (він часто скорочується в конкретному синтаксисі до # '), другий утворює значення функціонального типу. Ім'я функції є ім'ям функціонального блоку.

Приклад 8.4.1. У цьому прикладі ілюструються визначення факторіалу, виклик анонімної функції та можливість обчислення довільного функціонального виразу, створеного у програмі.

Потрібно зауважити, що визначення функції з даним ім'ям та значення імені можуть задаватися незалежно. Наприклад, ми можемо в цьому ж контексті задати (setq fact 7), хоча, звичайно ж, це огидний спосіб програмування.

Усі формальні параметри функцій є локальними змінними. Жодні зміни їх значень не виходять назовні. Але й інші властивості залишаються глобальними! Наведемо приклад.

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

Значення імені, успадкованого ззовні, всеі буде зовнішнім! Дивіться приклад нижче.

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

Функціонал mapcar застосовує свій перший аргумент до всіх членів другого.

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

І, нарешті, наведемо приклад 3 Люб'язно наданий Л. Городній (ІСІСО РАН та НГУ).

Приклад 8.4.2. Ця програма будує автомат для знаходження всіх входжень певної системи слів у вхідний потік. Пізніше вона аналізується з погляду автоматного програмування.