Декларативні і функціональні парадигми

Размещено на http://www.allbest.ru/

Доповідь

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

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

Functional and declarative programming paradigms

декларативний функціональний програмування парадигма

Анотація

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

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

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

Аннотация

В докладе были рассмотрены такие парадигмы программирования, как декларативная и функциональная. Было проведено сравнение декларативного программирования и широкоупотребляемой в современных информационных технологиях императивного программирования, выделены основные преимущества и недостатки декларативной парадигмы.

Кроме того, рассмотрена история развития декларативного и функционального программирования от истоков в начале ХХ века и к созданию таких популярных функциональных языков как Лисп и Хаскеля. Эволюцию синтаксиса было отслежено на примере такой тривиальной задачи, как определение факториала.

Также было дано определение понятию функционального программирования, определены основные категории и термины, применяемые в данной парадигме, рассмотрены преимущества и недостатки такого подхода и представлен пример практического применения функционального программирования в современных информационных технологиях.

Summary

The report deals with declarative and functional programming paradigm. It compares the declarative programming and wide-used in modern information technology and imperative programming, highlights the main advantages and disadvantages of declarative paradigm.

Also, it represents the history of the declarative and functional programming from sources in the early twentieth century and to the creation of such popular functional languages ??like Lisp and Haskel. The evolution of syntax has been tracked by the example of such a trivial task, as the definition of factorial.

Finally, it gives the definition of functional programming, the main categories and terms used in this paradigm, describes the advantages and disadvantages of this approach and examples of practical application for functional programming in modern information technologies.

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

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

У своїй статті "Алгоритм = Логіка + Управління" [1] Роберт Ковальський підкреслював той факт, що у всякій програмі можна виділити дві складові: логіку, яка описує власне рішення проблеми і керування процесом обчислень. У цій термінології декларативне програмування - опис логіки алгоритму, але не (обов'язково) управління.

Мабуть, найкраще описує ключову ідею декларативного програмування наступне визначення (належить Джону Робінсону [2]): програма є теорією, а обчислення є висновок у цій теорії.

Ще одне, негативне визначення: декларативні програми не використовують поняття стану і не містять змінних. Отже, вони не можуть використовувати оператори присвоювання, так як нема чому привласнювати. Крім того, поняття послідовності виконання команд стає безглуздим і, отже, марними стають оператори управління процесом обчислень. Виходячи з цього визначення, можна прийти до висновку, що декларативні мови - всього лише збиткові версії імперативних, з яких вилучені деякі зручні і звичні засоби. Але цікаво звернути увагу, що багато важливих удосконалення в техніці програмування пов'язані радше з обмеженням, а не розширенням можливостей доступних програмісту. Ранні мови високого рівня, починаючи з Фортрану, розділили глобальну пам'ять на області коду і даних, і встановили обмеження, що тільки дані можуть змінюватися. Концепції модульності, структурного програмування, суворої типізації також обмежують свободу програміста. Останні віяння - більш строгі інтерфейси і заборони на безпосередні зміни об'єктів. Декларативне програмування може розглядатися як ще один, більш радикальний, крок в цьому напрямку. Джон Хьюз порівнював функціональних програмістів із середньовічними ченцями, що відкидають задоволення життя. Зрозуміло що, приймаючи схиму і відмовляючись від коштів, які менш побожні програмісти вважають стандартними, ми сподіваємося отримати деякі переваги.

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

Повернемося до рівняння "Алгоритм = Логіка + Управління". При програмуванні на імперативній мові, ці дві складових переплетені і у програміста немає вибору, окрім як вникати в низькорівневі подробиці виконання програм. У декларативних мовах, логіка і керування розділені. Необхідність мати справу тільки (або переважно) з логічним компонентом значно спрощує програмування. Декларативну програму, взагалі кажучи, простіше написати і, що важливо, легше зрозуміти, ніж відповідну імперативну програму. Крім того, виникає можливість передачі відповідальності за створення управління комп'ютера. Часто наявність найбільш ефективного алгоритму не настільки вже й важливо і можна задовольнитися розумно ефективним алгоритмом, який знаходить сама система. Більше того, з'являються цікаві можливості використовувати нетривіальні алгоритми управління, такі як недетермінованні, "ліниві" і паралельні обчислення.

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

Декларативні мови добре підходять для програмування паралельних комп'ютерів. Вони не вимагають спеціальних методів опису паралелізму. Паралелізм програми визначається неявно її інформаційними зв'язками. Іншими словами, чи працює програма на послідовному або паралельному комп'ютері, програмісту байдуже. Чим більше декларативна мова програмування, тим більш імовірна наявність неявного паралелізму і тим простіше буде паралельне виконання програми. Таке неявне використання паралелізму дуже зручне для програміста, оскільки для нього не виникає додаткових труднощів понад ті, які присутні в програмі для послідовного комп'ютера. Але сама система повинна бути достатньо "розумна", щоб знайти найбільш ефективний спосіб виконання програми. Це дуже важке завдання, але деякі позитивні результати вже досягнуті і можна сподіватися, що в найближчому майбутньому стане можливо ефективно виконати декларативні програми на паралельних комп'ютерах "прозоро" для програміста.

Ще одна перевага декларативних мов - придатність для формальних міркувань. Відомо, що тестування дозволяє виявити помилки, але не може гарантувати їх відсутності. Єдиний спосіб переконатися в правильності програми - проаналізувати її код. На жаль, існуючі методи формального аналізу програм надзвичайно трудомісткі. Справа в тому, що широко використовуються мови типу Сі мають дуже складну і заплутану семантику. Це означає, що дуже важко формально (і навіть неформально) розмірковувати про програми на таких мовах. Багато зусиль було спрямовано на створення більш простих і суворих мов, а також на вдосконалення методів аналізу, але результати не обнадіюють. Застосування формальних методів залишається дуже дорогим і обмежується тими областями, де надійність програмного забезпечення критична.

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

Але, окрім переваг, у декларативного програмування існує ряд недоліків.

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

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

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

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

Поки ж на практиці воліють включати в декларативні мови програмування імперативні властивості. Такий підхід не позбавлений сенсу. Зрештою, не дарма ж існують наказові пропозиції і, якщо ми хочемо, щоб щось сталося, найпростіше сказати "зроби це". Але прямолінійний додавання імперативних операторів часто перекреслює багато гідності декларативних мов. Об'єднання різних парадигм в рамках однієї мови, вимагає ретельного опрацювання. На жаль, довгий час творці функціональних і логічних мов недостатньо серйозно ставилися до ідеї декларативності і в результаті практичні програми на Пролозі або Лісп ненабагато легше аналізувати, ніж навіть програми на Сі.

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

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

Фактично сучасну математичну логіку заснував Готлоб Фреге. У 1899 р. він придумав Begriffsschrift ("обчислення понять" або "система позначення понять") [Frege]. Це був самий значний крок в логіці з часів Аристотеля. Формальна система Фреге дозволила логікам розробити суворе визначення доведень. Крім того, Фреге був першим, хто серйозно поставився до ідеї застосування функцій до сутностей відмінним від чисел (і зокрема до інших функцій).

З початку XX століття математична логіка - об'єкт пильної уваги математиків. Для інформатики велике значення має робота Жака Ербран [Herbrand], в якій він запропонував кілька версій процедури доведення теорем в логіці першого порядку.

У 1920 р. радянський математик Мойсей Шенфінкель в своєму повідомленні "Про будівельні камені математичної логіки" [Schonfinkel] проголосив нові тенденції в математичній базі. Сутністю нової концепції був обчислювальний (або алгоритмічний) підхід до поняття функції, на відміну від традиційного її визначення як безлічі пар виду (аргумент, значення). У певному сенсі це було повернення до уявлень математиків XVIII століття, але на новому рівні строгості. Шенфінкель розглядав функції як композиції базових "комбінаторів" і намагався знайти мінімальний набір таких комбінаторів, придатний для визначення будь-якої функції. Обчислення комбінаторів було незалежно розроблено і глибоко досліджено Хаскелем Каррі і отримало найменування "комбінаторної логіки". З'явилися й інші формалізми, такі як "лямбда-числення" Алонзо Черча, що стало основою багатьох мов функціонального програмування та теорія рекурсивних функцій.

Власне історія починається в 1958 році, коли Джон Маккарті винайшов мову Лісп [McCarthy] (LISP - LISt Processing) першу в світі функціональну мову програмування. У якомусь сенсі Лісп - функціональний еквівалент Фортрану. Протягом деякого часу Лісп, і Фортран були єдиними широко доступними мовами програмування (крім асемблерних мов). Як "перший млинець" Лісп мав низку недоліків. Найбільш помітний з них - громіздкий синтаксис.

Наприклад, визначення факторіала:

(Define fac (n)

(If (eq n (quote 0))

(Quote 1)

(Mul n (fac (sub n (quote 1))))))

Ця велика кількість дужок дала привід деяким гострословам стверджувати, що LISP в дійсності означає "Lots of Infuriating, Stupid Parenthesis". Спочатку такий запис передбачалося використовувати тільки для даних і як проміжне представлення, а для програм застосовувати іншу нотацію, щось на кшталт:

fac [n] = [eq [n; 0] -> 1;

T -> mul [n; fac [n - 1]]]

Але виникли труднощі (перші реалізації Ліспу працювали на комп'ютерах з 8K слів пам'яті), а після появи першого інтерпретатора ці плани були відкладені на невизначений час. Користувачі звикли до синтаксису Ліспу. Час від часу виникали спроби створення діалектів з Алгол-подібним синтаксисом, але широкої підтримки не знаходили. Прихильники Ліспу стверджують, що його простий синтаксис дозволяє краще зосередитися на семантиці програми. В афористичній формі цю думку висловив Алан Перліс: "Синтаксичний цукор викликає рак крапок з комою".

Інший, більш істотний недолік - динамічне зв'язування змінних. Маккарті, не був добре знайомий з лямбда-обчисленням і запозичив його мову, але не семантику. Незручності такого підходу легко можуть оцінити всі, кому доводилося програмувати на мовах сімейства dBase. Деякі версії Ліспу обзавелися спеціальними конструкціями, що гарантують статичне зв'язування, але повністю цей недолік був усунений тільки в похідному від Ліспу мовою Scheme.

Можна перераховувати і інші недоліки Ліспу. І все ж деякі мови можуть зрівнятися з ним за кількістю нових ідей привнесених у програмування. І, мабуть, головна з них - мова програмування зовсім не зобов'язаний відображати особливості обчислювальної машини.

Дещо відволікаючись від теми. З Лісп пов'язані багато нововведення, що стали нині звичними: повноекранні редактори, і багатовіконний графічний інтерфейс, символічні дебагери та інспектори даних, інкрементні компілятори і діалогові системи програмування не кажучи вже про автоматичне управління пам'яттю і "прибирання сміття". Common Lisp - перша стандартизована мова об'єктно-орієнтованого програмування. Що ж до декларативного (і зокрема функціонального) програмування, Лісп в міру розвитку віддалявся від нього, обзавівшись повним набором імперативних інструментів аж до таких маргінальних, як go.

У 1964 р. Пітер Ландін продемонстрував зв'язок мов програмування, в тому числі Ліспу і Алгол з лямбда-обчисленням, придумав абстрактну машину для обчислення лямбда-виразів "SECD-машину" [Landin64]. З тих пір варіанти цієї машини часто використовувалися для реалізації функціональних мов.

У 1966 р. Ландін запропонував мову ISWIM (If you See What I Mean) [Landin66], який зіграв роль Алгол у функціональному програмуванні. Він не використовувався як промисловий мову, але послужив прототипом для всіх "сучасних" функціональних мов. ISWIM створювався як лямбда-числення з більш звичним синтаксисом (звичним, по крайней мере, для тих, хто читає математичні тексти). Саме Ландін ввів в ужиток термін "синтаксичний цукор". Серед нововведень - інфіксні операції, локальні визначення (let-і where-вирази) використання відступів для визначення структури програми. Факторіал на ISWIM виглядає цілком сучасно.

rec fac (n) = (n = 0) -> 1; n fac (n-1)

У 1963 р. Джон Алан Робінсон [Robinson] реалізував метод автоматичного доведення теорем, що отримав назву "принцип резолюції". Ідея цього методу належить Ербрану, але оскільки той не думав про застосування свого методу на комп'ютерах (що не дивно в 1930 р.), він виявився не дуже підходящим з обчислювальної точки зору. Робінсон зробив його придатним для реального застосування і розробив ефективний алгоритм уніфікації, що є основою методу.

В 1971 Ален Колмерое поклав резолюцію в основу Прологу (PROLOG - PROgrammation en LOGique) [Colmerauer] - першої мови логічного програмування. Щоб домогтися прийнятної ефективності та уникнути "комбінаторних вибухів" на мову були накладені істотні обмеження. Роберт Ковальський показав [Kowalski], що ці обмеження еквівалентні використанню відомого підмножини логіки предикатів, так званих Хорновськими диз'юнктів [Horn] і таким чином підбив теоретичний фундамент під Пролог. Саме процедурна інтерпретація логічних пропозицій, запропонована Ковальським, дає підстави говорити про Пролозі як про перший логічному мовою, незважаючи на те, що раніше вже існували системи, засновані на логіці, такі як Absys Майкла Фостера і Теда Елкока [Elcock, Foster] і ПРИЗ Енна Тиугу [Тиугу]. Цікаво що, працюючи над Лісп, Маккарті також намагався створити логічний мову, але відсутність ефективних алгоритмів висновку не дозволило йому зробити це.

У 1976 р. Девідом Уорреном створена реалізація Прологу, відома як Edinburgh Prolog [Warren]. Компілятор Уоррена продемонстрував ефективність не гірше, ніж кращі існуючі в той час реалізації Ліспу і викликав інтерес до Прологу як до реального мови програмування. Програми на Пролозі компілювалися в команди спеціально розробленої віртуальної машини, що отримала назву WAM (Warren's Abstract Machine). У цій реалізації Пролог знайшов свій звичний вигляд. На довгий час Edinburgh Prolog став стандартом де-факто для Прологу.

Пролог виявився досить вдалою мовою. Це сприяло його популярності, як і популярності логічного програмування в цілому, але мало і тіньові сторони. На багато недоліків Прологу закривали очі. Деякі не дуже вдалі засоби мови, такі як відсікання і динамічна зміна коду, міцно увійшли в арсенал програмістів і ними навіть навчають користуватися. Виникло стійке (і помилкове) думка, що механізм виведення, який застосовується в Пролозі, і становить сутність логічного програмування.

Визначення факторіала на Пролозі

fac (0, 1).

fac (N, M): - sub (N, 1, N1), fac (N1, M1), mul (N, M1, M).

демонструє одну незручність реляційних мов - необхідність вводити позначення для проміжних результатів.

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

У 1976 р. Петер Хендерсон і Джеймс Морріс реалізували діалект Ліспу Lispkit [Henderson], в якому вперше використовувалися ледачі обчислення - важлива концепція сучасного функціонального програмування. Власне ледачі обчислення були введені ще в Алгол-60 як наслідок передачі параметрів по імені, але там вони сприймалися як помилка творців мови і ніколи не реалізовувалися в повному обсязі. Дійсно, така схема обчислень суперечить принципу імперативного програмування - явного опису послідовності обчислень.

Значний вплив на популяризацію функціонального програмування справила лекція Джона Бекуса і його стаття [Backus]. У 1977 р. Бекуса отримує премію Тьюринга, перш за все за участь у створенні Фортрану і Алгол. У своїй лекції він обрушується з критикою на імперативні мови, за те, що вони змушують програміста зосередиться на операціях з пам'яттю комп'ютера, а не на проблемі, яку треба вирішити і за те, що вони не володіють корисними математичними властивостями для міркувань про програми. Дістається і лямбда-обчисленню. Бекуса порівнює його з використанням довільних передач управління в імперативних мовах. Натомість він пропонує системи програмування, засновані на "функціональних формах" (тобто функціях вищого порядку або комбінаторів), які виражають загальні зразки обчислень. Функції вищого порядку - важлива особливість сучасних функціональних мов програмування, але інші пропозиції Бекуса широкого визнання не отримали. Програмування без змінних - не легке заняття і потрібні деякі зусилля, щоб зрозуміти визначення факторіала на FP.

def fac = eq o [id, 0] -> 1; xo [id, fac o - o [id, 1]]

У 1977 р. в Единбурзькому університеті з'явилися дві мови, що зробили значний вплив на подальший розвиток функціональних мов.

ML (Meta Language, початкове призначення-метамова для системи доказів) [Gordon] дуже схожий на ISWIM, але мав важливу особливість: поліморфну ??систему типів даних розроблену Робіном Мілнером [Milner]. Подібна система була раніше запропонована Роджером Хиндлі [Hindley] і зараз часто називається системою типів Хиндлі-Мілнера. Наявність механізму виведення типів дозволило позбавити програміста від необхідності явно описувати типи функцій і в той же час проводити суворий контроль типів.

ML не чисто функціональна мова, вона включає і імперативні інструкції. З тих пір ML розвивався і включив в себе багато особливостей інших функціональних мов. З'явилося кілька діалектів, найбільш відомі з яких Standard ML [Harper], CAML [Cousineau] і чисто функціональний Lazy ML [Augustsson].

Факторіал на ML:

fun fac (n) = if n = 0 then 1 else n * fac (n-1);

Інша мова, Hope [Burstall], використовує подібну систему типів, але вимагає явних оголошень типів. Важливі нововведення - алгебраїчні визначення типів і зіставлення зі зразком - різновид уніфікації.

Факторіал на Hope:

dec fac: num -> num;

--- Fac (0) <= 1;

--- Fac (n) <= n * fac (n-1);

ілюструє цю останню особливість мови.

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

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

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

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

л-числення є основою для функціонального програмування, багато функціональні мови можна розглядати як "надбудову" над ними

2. Концепції

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

2.1. Функції вищих порядків

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

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

Функції вищих порядків дозволяють використовувати каррінг - перетворення функції від пари аргументів у функцію, що бере свої аргументи по одному. Це перетворення отримало свою назву на честь Х. Каррі.

2.2. Чисті функції

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

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

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

с Якщо немає ніякої залежності за даними між двома чистими функціями, то порядок їх обчислення можна поміняти або распараллелить (інакше кажучи обчислення чистих функцій задовольняє принципам thread-safe)

с Якщо вся мова не допускає побічних ефектів, то можна використовувати будь-яку політику обчислення. Це надає свободу компілятору комбінувати і реорганізовувати обчислення виразів у програмі (наприклад, виключити деревоподібні структури).

До тих пір поки більшість компіляторів імперативних мов програмування розпізнають чисті функції і видаляють загальні подвираженія для дзвінків чистих функцій, вони не зможуть робити це завжди для попередньо скомпільованих бібліотек, які, як правило, не надають цю інформацію. Деякі компілятори, такі як gcc, з метою оптимізації надають програмісту ключові слова для позначення чистих функцій. Fortran 95 дозволяє позначати функції як "pure" (чисті).

2.3. Рекурсія

У функціональних мовах цикл зазвичай реалізується у вигляді рекурсії. Строго кажучи, у функціональній парадигмі програмування немає такого поняття як цикл. Рекурсивні функції викликають самі себе, дозволяючи операції виконуватися знову і знову. Для використання рекурсії може знадобитися великий стек, але цього можна уникнути в разі хвостовій рекурсії. Хвостова рекурсія може бути розпізнана і оптимізована компілятором в код, отриманий після компіляції аналогічної ітерації в імперативному мовою програмування. Стандарти мови Scheme вимагають розпізнавати і оптимізувати хвостову рекурсію. Оптимізувати хвостову рекурсію можна шляхом перетворення програми в стилі використання продовжень при її компіляції, як один із способів. [джерело не вказано 930 днів]

Рекурсивні функції можна узагальнити за допомогою функцій вищих порядків, використовуючи, наприклад, катаморфізм і анаморфізм (або "згортка" і "розгортка"). Функції такого роду відіграють роль такого поняття як цикл в імперативних мовах програмування.

2.4. Підхід до обчислення аргументів

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

print length ([2 +1, 3 * 2, 1 / 0, 5-4])

При строгому підході до обчислення на виході буде помилка, так як у третьому елементі присутній поділ на нуль. А при нестрогому підході функція поверне значення 4. При строгому обчисленні заздалегідь підраховуються значення всіх аргументів перед обчисленням самої функції. При нестрогому підході значення аргументів не обчислюється до тих пір, поки їх значення не знадобиться при обчисленні функції [5].

Як правило нестрогий підхід реалізується у вигляді редукції графа. Нестрогое обчислення використовується за умовчанням в кількох чисто функціональних мовах, у тому числі Miranda, Clean і Haskell.

2.5. ФП в нефункціональних мовами

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

У мові C покажчики на функцію можуть бути використані для отримання ефекту функцій вищого порядку. Функції вищого порядку і відкладена списковому структура реалізовані в бібліотеках С + +. У мові C # версії 3.0 і вище можна використовувати л-функції для написання програми в функціональному стилі. У складних мовах, типу Алгол-68, наявні засоби метапрограмування (фактично - доповнення мови новими конструкціями) дозволяють створити специфічні для функціонального стилю об'єкти даних і програмні конструкції, після чого можна писати функціональні програми з їх використанням.

3. Стилі програмування

Імперативні програми мають схильність акцентувати послідовності кроків для виконання якоїсь дії, а функціональні програми до розташування і композиції функцій, часто не позначаючи точної послідовності кроків. Простий приклад двох рішень однієї задачі (використовується один і той же мова Python) ілюструє це.

# Imperative style target = [ ] # Create empty list for item in source_list: # Iterate over each thing in source trans1 = G ( item ) # Transform the item with the G () function trans2 = F ( trans1 ) # Second transform with the F () function target. append ( trans2 ) # Add transformed item to target

Функціональна версія виглядає по-іншому

# Functional style # FP-oriented languages ??often have standard compose () compose2 = lambda A , B: lambda x: A ( B ( x ) ) target = map ( compose2 ( F , G ) , source_list )

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

4. Особливості

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

4.1. Сильні сторони

4.1.1. Підвищення надійності коду

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

4.1.2. Комфортність організації модульного тестування

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

Таким чином є можливість протестувати кожну функцію в програмі, просто обчисливши її від різних наборів значень аргументів. При цьому можна не турбуватися ні про виклик функцій в правильному порядку, ні про правильне формування зовнішнього стану. Якщо будь-яка функція в програмі проходить модульні тести, то можна бути впевненим у якості всієї програми. В імперативних програмах перевірка повертається функції недостатня: функція може модифікувати зовнішній стан, яке теж потрібно перевіряти, чого не потрібно робити у функціональних програмах [6].

4.1.3. Можливості оптимізації при компіляції

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

4.1.4. Можливості паралелізму

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

4.2. Недоліки

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

Для подолання недоліків функціональних програм вже перші мови функціонального програмування включали не тільки чисто функціональні засоби, а й механізми імперативного програмування (привласнення, цикл, "неявний PROGN" були вже в LISPе). Використання таких засобів дозволяє вирішити деякі практичні проблеми, але це означає відхід від ідей (і переваг) функціонального програмування і написання імперативних програм на функціональних мовах.

5. Практичне застосування

Влітку 2009 року в МінЖКГ впроваджена система збору та аналізу статистичної звітності про підготовку муніципалітетів Московської області до осінньо-зимового періоду виключно мовою ФП (XQuery), без використання традиційних мов програмування

Висновки

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

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

Ця парадигма мов програмування відмінна від імперативних мов програмування, таких як, наприклад, Фортран, C, і Java, які вимагають від розробника детального описання алгоритма отримання результатів.

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

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

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

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

Іншими словами, функційне програмування є способом створення програм, в яких єдиною дією є виклик функції, єдиним способом розбиття програми є створення нового імені функції та задання для цього імені виразу, що обчислює значення функції, а єдиним правилом композиції є оператор суперпозиції функцій. Жодних комірок пам'яті, операторів присвоєння, циклів, ні, тим більше, блок схем чи передачі управління.[1]

Ширша концепція функційного програмування визначає набір спільних правил та тем замість переліку відмінностей від інших парадигм. До таких, що часто вважаються важливими, належать функції вищого порядку[2] та першого класу, замикання, та рекурсія. До інших поширених можливостей функційних мов програмування належать продовження, система типізації Хіндлі-Мілнера, нечіткі обчислення (включно з, але, не обмежуючись лінивими обчисленнями), та монади.

Основну увагу функційним мовам програмування, особливо, «чисто функційним», приділили академічні дослідники. Однак, до відомих функційних мов програмування, які використовуються в промисловості та комерційному програмуванні належить Erlang (паралельні програми), R (статистика), Mathematica (символьні обчислення)), J та K (фінансовий аналіз), та спеціалізовані мови програмування наприклад XSLT. Істотний вплив на функційне програмування здійснило лямбда-числення, мова програмування APL, мова програмування Lisp та новіша мова програмування Haskell.

Джерела

1. http://uk.wikipedia.org/

2. http://zdorovie.sdyks.com/%D0%A4%D1%83%D0%BD%D0%BA%D1%86%D1%96%D0%BE%D0%BD%D0%B0%D0%BB%D1%8C%D0%BD%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D1%83%D0%B2%D0%B0%D0%BD%D0%BD%D1%8F

3. R. A. Kowalski Algorithm = Logic + Control. CACM 22(7), 1979

4. J. A. Robinson : Editor's Introduction. Journal of Logic Programming Vol.1 1984

5. J. W. Lloyd Practical Advantages of Declarative Programming. Proceedings of the 1994 Joint Conference on Declarative Programming.

6. D.A. Turner Programs as executable specifications. In C. A. R. Hoare and J. C. Shepherdson, Mathematical Logic and Programming Languages, 1985.

Размещено на Allbest.ru

...