Функціональне програмування

Функциональное программирование

Н.Н.Непейвода, Інтернет Університет Інформаційних Технологій, INTUIT.ru.

Функциональное програмування пояснюється з прикладу діалекту Common Lisp мови LISP. Цей діалект найпоширеніший і має офіційний стандарт. Common Lisp може працювати у пакетному режимі (що він запускається як звичайна програма), а й у режимі диалога.

LISP — мабуть, перший із практично реалізованих языков1, яка ґрунтувалася на серйозному теоретичному фундаменті і намагався підняти практику програмування рівня концепцій, а чи не навпаки — опустити концепції рівня що існувала на даний момент створення мови практики.

В сьогодні функціональне програмування представлено цілим сімейством мов, але LISP своїми панівними позиціями не сдает.

?-абстракции В окремих випадках усвідомлене засвоєння концепцій навіть найбільш низький рівень нереально без базових теоретичних відомостей. А ознайомлення з таким базисом, в своє чергу, стимулює значно більше глибокий інтерес до теорії та сприяє розумінню те, що на вищі рівні знань і умінь не піднятися без оволодіння теорией.

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

В ?-исчислении виражальні засоби, здавалося б, вкрай скупі. Є дві базисні операції: застосування функції до аргументу (?x) і квантор освіти функції вираженню? x t[x]. У термінах ?-исчисления функція спорудження вересня квадрат записується як? x (sqrx) чи, якщо ближчі один до звичайних математичних позначенням, ?x x2.

Основная операція — символьне обчислення застосування функції до аргументу: (?x t[x] u) перетворюється на t[u]. Але це операція може застосовуватися у місці висловлювання, отже ніяка конкретна дисципліна обчислень не фіксується. Понад те, функції можуть обчислюватися точно як і, як аргументи. Вже ця маленька тонкість призводить до принциповому розширенню можливостей ?-исчисления проти звичайними викликами процедур. Якщо хочемо обмежитися лише нею, розглядається типізоване ?-исчисление, у якому, загальноприйнятий більшості сучасних систем програмування, значення суворо розділені по типам. У типизированном ?-исчислении є лише типи функцій, і цього вистачає, оскільки функції можуть приймати відвідувачів як параметрів і давати функции.

Но в вихідної своєї формі ?-исчисление є нетипизированным, будь-який об'єкт може бути функцією, і аргументом, і більше, функція може застосовуватися до сама собі. Звісно ж, у своїй з’являється можливість зациклення, але не матимуть неї не обійдеться жодна <универсальная> алгоритмічна система. Наприклад, выражение.

(?x (xx) ?x (xx)).

вычисляется нескінченно, а трохи більше складне выражение.

((?x ?y x a) (?x (xx) ?x (xx))).

может або a, або зациклитися, залежно від вибору порядку його обчислення. Але однаково, коли ми дійшли результату, він визначається однозначно. Так що спільність обчислень не псує однозначності, коли мова добре сконструирован.

Дж. Маккарті переніс ідеї ?-исчисления в програмування, не втративши практично з вихідних концепцій. Далі, він зазначив, що у рудиментарному вигляді у ?-исчислении з’явилося поняття списку, і переніс списки як основних структур даних на свій мову. ?-исчислением було навіяно і угоду мови LISP у тому, перший член списку сприймається як функція, застосовується до остальным.

Списки і функціональні выражения

Основной одиницею даних для LISP-системы є список.

Списки задаються наступним індуктивним определением.

Пустой список () (обозначаемый також nil) є списком.

Если l1,.. ., ln, n? 1 — атоми або списки, то (l1,. .. , ln) — також список.

Элементами списку (l1,. .. , ln) називаються l1,. .. , ln. Рівність списків задається наступним індуктивним определением.

l = nil тоді й тільки тоді, коли l також є nil.

(l1,. .. , ln) = (k1,. .. , km) тоді й тільки тоді, коли n = m і відповідні li = ki.

Пример 8.2.2. Усі списки (), (()), ((())) тощо. буд. різні. Різні ще й списки nil, (nil, nil), (nil, nil, nil) тощо. Попарно різняться списки ((a, b), з), (a, (b, c)), (a, b, c), де a, b, з — різні атомы.

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

Вершины списку l задаються наступним індуктивним определением.

Элементы списку є її вершинами.

Вершины елементів списку є її вершинами.

Длиной списку називається кількість елементів у ньому. Глибиною списку називається якомога більше вкладених пар скобок у ньому. З'єднанням списків (l1,. .. , ln) і (k1,. .. , km) називається список.

(l1,. .. , ln, k1,. .. , km).

Замена вершини a списку l на атом або список m виходить заміною поддерева l, відповідного a, на дерево для m. Заміна позначається l[a | m]. Через l[a || m] будемо позначати результат заміни кількох входжень вершини a на m.

Атомами у мові lisp є числа, імена, істина T. Брехнею служить порожній список nil, який у принципі атомом перестав бути, але у мові lisp під час перевірки те що, чи є він атомом, видається істина. Так само видається істина і за перевірці, чи є він списком. Але всі списковые операції застосовні до nil, інші ж, які працюють із атомами, часто щодо нього неприйнятні. Наприклад, спроба присвоювання значення видає ошибку.

Основная операція для завдання списків (list a b. .. z). Вона обчислює свої аргументи і збирає в список. З цією операції без обчислення аргументів є скоропис «(a b. .. z). вона є приватним випадком функції quote (скорочено обозначаемой »), що забороняє всякі обчислення у своїй аргументі і копіює їх у результат оскільки він есть.

По традиції, елементарні операції розбору списків позначаються іменами, які розпочинаються з з і закінчуються на r, а середині йде деяка послідовність літер a і d; (car p. s) виділяє голову (перший член списку), (cdr p. s) — хвіст (подсписок всіх членів, починаючи з другого). Букви a і d застосовуються, починаючи з кінця. Загальна кількість символів в получающемся атомі має не понад шість. Розглянемо фрагмент діалогу, який ілюструє ці операції. Щойно у діалозі вводиться яке закінчила вираз, воно обчислюється або видається ошибка.

[13]>(setq a «(b з (d e) f g)).

(B З (D E) F G).

[14]> (cddr a).

((D E) F G).

[15]> (cddar a).

*** - CDDAR: B is not a list.

1. Break [16]> ^Z.

[17]> (caaddr a).

D.

[18]> (cdaddr a).

(E).

Поле зору полі памяти

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

Таким чином, в lisp, як і, як і сентенциальных мовами, структура даних програми розвитку й поля пам’яті, оброблюваного програмою, збігаються. Певне, це одне з найвдаліших форм підтримки концептуального єдності для высокоуровневых систем.

У центрі пам’яті з кожним атомом-именем може бути пов’язані атрибути. Стандартний атрибут — значення атома. Для установки цього атрибута є функція (setq atom value), аналогічна присвоюванню. Ця функція не обчислює свій «перший аргумент, вона трактується як ім'я, якому потрібно приписати значение.

Значение у мові lisp то, можливо локальним. Якщо ми змінили значення атома всередині деякого блоку, то таке «присвоювання «діє лише всередині мінімальних объемлющих його скобок і зникає зовні блоку. Крім значення, імена можуть мати хоч греблю гати інших атрибутів, які обов’язково глобальні. Вони належать самому імені, а чи не блоку. Спосіб установки значень цих атрибутів кілька штучний. Є ще одне функція setf, вычисляющая свій «перший аргумент, дає посилання місце, якому можна приписати значення (наприклад, на атрибут). Функція отримання значення атрибута get, навіть якщо атрибута ще немає, свідчить про його місце. Наступний приклад демонструє, як і работает.

[38]> (setf (get «b «weight) «(125 kg)).

(125 KG).

[39]> (get «b «weight).

(125 KG).

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

Типы даних (себто програмування) в lisp є, але де вони визначаються динамічно. Зокрема, якщо дійсне число надано атома як значення, то тип атома стає float.

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

Для lisp (як й у іншого функціонального мови) не обязательно2 говорити, де і розміщуються структури даних (списки).

.

Рис. 8.1. Структура інформації, сопоставленной атома мови LISP.

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

До виконання кроку обчислення — це список, до складу якого ім'я функції і його аргументи.

Во час виконання кроку обчислення — це фрагменти списковою структури поля зору, доступними від використання вычисляемой функцією (зокрема, у тому числі список, пов’язаний з ім'ям функції, що визначає її обчислювальний процес).

После виконання кроку обчислень — це результати обчислень. Результати можна розділити втричі групи:

значение, що видається викликом функції: воно заміщає до поля зору відпрацьований виклик функції;

побочные ефекти, розкидані структурі поля даних;

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

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

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

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

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

Списки lisp, пов’язані з послідовними обчисленнями. Структура графа задається як сукупність лінійних списків, що об'єднує імена функцій і покажчики аргументів. Голова списку сприймається як вказівку функції, а хвіст — як аргументи.

Коммутационные схеми, що будуються з урахуванням поділу функцій та об'єктивності даних: функції видаються вершинами графа, які аргументы-данные передаються по дугам, що з'єднує вершини. Дуги розглядаються як каналів зв’язку. Функція активізується, коли її аргументи з’являються у каналах.

Ассоциативные схеми, у яких вершины-функции залишаються віртуальними. Вони в результаті зв’язування даних, мають однаковий ключ. Ситуація, коли ці дані з’являються у асоціативної пам’яті, сприймається як готовність аргументів для обчислення функції, ідентифікованої цим ключом.

Коммутационные і асоціативні схеми розглянуті під час обговорення неимперативных моделей обчислень. Вибір послідовно просматриваемой структури на першому функціонального мови обумовлений єдиною на той час можливістю реалізації функціональності шляхом моделювання її операційними засобами традиційну модель обчислень. Спискова структура будується у вигляді більш-менш стандартного для традиційну модель адресного уявлення. З мовної погляду саме такий вибір забезпечує однорідність структури програми розвитку й даних, з урахуванням якої Дж. Маккарті вдалося побудова системи коштів, достатню для практичного функціонального программирования.

Программа мовою lisp задається як список застосувань функцій, частина у тому числі може обчислюватися під час виконання самої програми. Зазвичай, задані в програмі списки інтерпретуються як застосування функцій і обчислюються, якщо інше не визначають раніше активовані функції (ви бачили, що функція quote забороняє обчислення свого аргументу, функція setq забороняє обчислення лише першого з цих двох аргументів, а функція setf змушує обчислити перший аргумент лише до стадії, коли отримана посилання його значення). Будь-яке вираз видає значення, що використовується, зокрема, при діалогової працювати з lisp (на прикладі якої ілюструються понятия).

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

(block name e1. .. en) (8.1).

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

(return-from name value) (8.2).

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

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

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

[1]> (defun fact (n) (if (= n 0) 1.

(* (fact (- n 1)) n))).

FACT.

[2]> (fact 40).

[3]> ((lambda (x) (fact (* x x))) 5).

[4]> (setq g «(lambda (x) (fact (* x x)))).

(LAMBDA (X) (FACT (* X X))).

[5]> (eval (list g 3)).

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

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

[23]> (defun f (x) (progn (setf.

(get «x «weight) «(25 kg)) (+ x 3))).

F.

[24]> (setf (get «x «weight) «(30 kg)).

(30 KG).

[25]> (get «x «weight).

(30 KG).

[26]> (setq x 5).

[27]> (f 3).

[28]> x.

[29]> (get «x «weight).

(25 KG).

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

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

[32]>(setq a «(b з d)).

(B З D).

[33]>(setq b 5).

[34]> (list (let ((b 6)) (eval (car a))).

(eval (car a))).

(5 5).

[35]> (list (let ((b 6)) b) (eval (car a))).

(6 5).

[36]> (list (let ((b 6)) (list b a)).

(eval (car a))).

((6 (B З D)) 5).

[37]> (list (let ((b 6)) (eval (car.

(list «b a)))) (eval (car a))).

(5 5).

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

[57]> (setq a (list 1 5 7 9 11 13 15 19 22 28)).

(1 5 7 9 11 13 15 19 22 28).

[58]> (mapcar (function (lambda (x) (* x x))) a).

(1 25 49 81 121 169 225 361 484 784).

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

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

И, нарешті, наведемо пример3.

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

Лістинг 8.4.1. Автомат перебування всіх входжень деякою системи слів у вхідний потік (html, txt).

Прагматические додавання і динамічний породження программ

Разберем можливості мови lisp в комплексе.

Выразительные кошти конкретно-синтаксического уявлення загальної структури даних, і програм мови lisp вкрай скупі. Але цей спектакль дозволяє практично однозначно зв’язати синтаксис і реалізаційну структуру.

Реализационное уявлення якнайкраще відповідає угоді про спільність функціональної структури та структури даних: у кожному списку голова сприймається як вказівку (ім'я, посилання абощо) на функцію, а хвіст — як послідовність вказівок на аргументи. Завдання властивості списку же не бути функцією, т. е. скасування виділеного статусу голови, що означає функцію, досягається з допомогою блокування. Це вдале рішення, у умовах прийнятого угоди, що дозволяє трактувати нефункціональний списку константну функцію, <вычисляющую> своє зображення (уявлення). Ще важливіше те, що воно забезпечує гнучкість уявлення: функцію eval, змушує список примусово обчислюватися, природно трактувати просто як зняття блокування. Зауважимо, на рівні абстрактного синтаксису функція eval зобов’язана бути універсально застосовувану до будь-якого списку.

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

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

Внимание!

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

Структура списків lisp ідеальна до подання абстрактного синтаксису мови. І хоча недоброзичливці називають цей синтаксис <утомительным нагромадженням скобок>, він у точності відповідає абстрактному синтаксису. Якщо навіть враховувати переваги зазначеного відповідності, то залишається простота уявлення програм, тож даних як лінійної текстовій послідовності символов.

Другие гіпотетичні кандидати в ролі конкретного синтаксису за цим критерієм явно програють. Традиційні математичні форми завдання функцій та його застосувань є текстуально надмірними (як префиксная, і постфиксная записи вимагають обов’язкового обрамлення параметрів дужками), а бесскобочная нотація Лукасевича (і пряма, та зворотний) ще більше дезорієнтували б тексти з порівнянню з <утомительным нагромадженням скобок>. Але з допомогою внеязыковых прагматичних угод у тому, як розташовувати на двовимірному носії (на папері чи екрані) скобочную структуру, можна істотно полегшити. Якщо ж система програмування підтримуватиме (і перевіряти!) прагматичні угоди (що вирізняло розвинених систем), то вид програм стане цілком читаним. Отже долаються незручності лінійного представления.

Сегодня можна було говорити про інших форматах конкретного синтаксису lisp, у цьому однині і які пов’язані з лінійним поданням. Використання розвинених коштів графіки при екранному наборі програм дозволяє на повну потужність підключити двумерную роботу. Проте традиції, і стихійно сформовані стандарти не залишають змогу впровадження таких форматів. Тут у вкотре й у повною мірою проявилися шкідливі ефекти ранньої стандартизації, заважають розвитку напрями, що залишається однією з концептуально багатих і перспективных.

Диктат лінійності був закоріненим настільки глибоко, що у тому випадку, коли він міг бути подолано безболісно, мовна система найчастіше однаково будується як лінійна. Ідеться як функціонального стиля5.

Объекты і LISP

Стандартная надбудова над Common Lisp, яка імітує объектно-ориентированный стиль, це модуль CLOS — Common Lisp Object System. Сама собою объектность це не дає ніякого виграшу проти мовою lisp, оскільки можливості динамічного обчислення функцій в lisp навіть ширше. Певне, саме у CLOS є дві цікавих модифікації, які його ні схожим на стандартне ООП.

Начнем із поняття структури даних у мові Common Lisp. Структура визначається функцією defstruct вида.

(defstruct pet name (species «cat) age weight sex).

Задание структури автоматично задає функцию-конструктор структури make-pet, яка може приймати ключові аргументи кожного з полей:

(make-pet :nick «viola :age «(3 years) :sex «femina)).

и функцію доступу кожного з полів, наприклад pet-nick, использующуюся для отримання значення поля чи посилання нього. Якщо полі не инициализировано (ні за умовчанням, ні конструктором), вона бере початкова значення nil. Ніякої подальшої специфікації полів структур нет6.

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

(defclass pet (animal possession) (.

(species :initform «cat).

(nick :accessor nickof.

:inintform «Pussy.

:initarg namepet).

).

Этот клас успадковує поля, функції доступу та інші від класів animal і possession. Наприклад, полі cost є у значенні класу, коли вона є у одному з цих класів. Оскільки статичних типів у полів немає, немає і конфликтов.

Основная функція наслідування в CLOS — визначення упорядкування на класах. Із кожним класом пов’язано своє впорядкування. Спадкоємець менше своїх покійних предків, з предків меншим вважається той, який раніше перераховано у списку наслідування при визначенні класу. CLOS добудовує цей частковий порядок до лінійного. Спосіб поповнення порядку можливо, у будь-якої миті і оповіщення змінено, і хакерское використання особливостей конкретного поповнення вважається грубої стилістичній помилкою. Якщо цю систему знаходить несумісність у визначенні порядку, вона видає помилку, як і наступному примере:

[6]> (defclass init () ()).

#<STANDARD-CLASS INIT>

[7]> (defclass a (init) ()).

#<STANDARD-CLASS A>

[8]> (defclass b (init) ()).

#<STANDARD-CLASS B>

[9]> (defclass c1 (a b) ()).

#<STANDARD-CLASS C1>

[10]> (defclass c2 (b a) ()).

#<STANDARD-CLASS C2>

[11]> (defclass contr (c1 c2) ()).

*** - DEFCLASS CONTR:

inconsistent precedence graph,.

cycle (#<STANDARD-CLASS A> #<STANDARD-CLASS B>).

В CLOS можуть задаватися методи, які від функцій тим, що й аргументи специфицированы, например

(defmethod inspectpet ((x pet) (y float)).

(setf weightofanimal 3.5)).

Как це випливає з цього прикладу, методи необов’язково пов’язані з класами. Вони можуть бути пов’язані із будь-якими типами. Методи в CLOS може мати додаткові специфікації. А, щоби доскіпатися, щоб ці специфікації взаємодіють з упорядкуванням типів класів, розглянемо таку програму і генерований у її виконанні результат.

Лістинг 8.6.1. Взаємодія додаткових специфікацій методів у CLOS з упорядкуванням типів класів (html, txt).

При завантаженні цього файла відбувається следующее:

Приклад 8.6.2. Результат завантаження програми 8.6.1 (html, txt).

Видно, що упорядкованість класів стосовно наслідування дозволяє вибудовувати цілі послідовності дій при виклик одного метода.

Поскольку в CLOS немає механізмів приховання конкретних уявлень, ні механізмів заміни прямого доступу до даних на функції, ні інших характерних рис ОВП, ми бачимо іще одна приклад того, як модним словом (у разі ОВП) прикривається інша, щонайменше цікава сутність: простий планування дій зі структурі типів даних. У зв’язку з цим не слід нагадати блискучий експеримент планування обчислень структурою даних, зараз (судячи з усього, тимчасово) забутий: естонську систему PRIZ [Тыугу Э. Х. Концептуальне програмування. М. Наука. 1984. — 256 с.].

Неадекватное теоретизування заважає уздріти і розвинути реальні гідності системи та закріплює слабкі места.

Список литературы

Для підготовки даної роботи було використані матеріали із сайту internet.