Характеристика функціонального підходу до програмування. Поняття функції, конверсії, рекурсії. Переваги і недоліки функціонального підходу.
У лекції обговорюються питання, що стосуються історії розвитку, ідеології, математичного обгрунтування і можливостей програмних систем на основі функціонального підходу до проектування та реалізації програмного забезпечення.
Класифікація підходів до програмування була побудована нами в ході лекції 1.
Зосередимося на найважливішому для даного курсу функціональному підході до програмування.
Перш за все, звернемося до історії фундаментальних математичних досліджень, які привели до появи функціонального підходу до програмування.
Час появи теоретичних робіт, які обгрунтовують функціональний підхід, відноситься до 20-м - 30-х років XX століття. Як ми переконаємося згодом, теорія часто значно випереджає практику програмування, і найважливіші роботи, які сформували математичну основу підходу, були написані задовго до появи комп'ютерів і мов програмування, які потенційно могли б реалізувати цю теорію.
Що стосується першої реалізації, то вона з'явилася в 50-х роках XX століття у формі мови LISP, про який мова піде далі.
Нагадаємо, що найважливішою характеристикою функціонального підходу є та обставина, що всяка програма, розроблена на мові функціонального програмування, може розглядатися як функція, аргументи якої, можливо, також є функціями.
Функціональний підхід породив ціле сімейство мов, родоначальником яких, як уже зазначалося, стала мова програмування LISP. Пізніше, в 70-х роках, був розроблений первісний варіант мови ML, який згодом розвинувся, зокрема, в SML, а також ряд інших мов. З них, мабуть, самим "молодим" є створений вже зовсім недавно, в 90-х роках, мова Haskell.
Важливою перевагою реалізації мов функціонального програмування є автоматизоване динамічний розподіл пам'яті комп'ютера для зберігання даних. При цьому програміст позбавляється від необхідності контролювати дані, а якщо буде потрібно, може запустити функцію "збірки сміття" - очищення пам'яті від тих даних, які більше не знадобляться програмі.
Складні програми при функціональному підході будуються за допомогою агрегування функцій. При цьому текст програми являє собою функцію, деякі аргументи якої можна також розглядати як функції. Таким чином, повторне використання коду зводиться до виклику раніше описаної функції, структура якої, на відміну від процедури імперативного мови, математично прозора.
Оскільки функція є природним формалізмом для мов функціонального програмування, реалізація різних аспектів програмування, пов'язаних з функціями, істотно спрощується. Інтуїтивно прозорим стає написання рекурсивних функцій, тобто функцій, що викликають самих себе в якості аргументу. Природною стає і реалізація обробки рекурсивних структур даних.
Завдяки реалізації механізму зіставлення зі зразком, такі мови функціонального програмування як ML та Haskell добре використовувати для символьної обробки.
Природно, мови функціонального програмування не позбавлені і деяких недоліків.
Часто до них відносять нелінійну структуру програми і відносно невисоку ефективність реалізації. Проте перший недолік досить суб'єктивний, а другий успішно подоланий сучасними реалізаціями, зокрема, низкою останніх трансляторів мови SML, включаючи і компілятор для середовища Microsoft. NET.
Для професійної розробки програмного забезпечення на мовах функціонального програмування необхідно глибоко розуміти природу функції. Дослідженню закономірностей і особливостей природи функції в основному і присвячені лекції 2 - 12 цього курсу.
Зауважимо, що під терміном "функція" в математичній формалізації і програмної реалізації маються на увазі різні поняття.
Так, математичної функцією f з областю визначення A та областю значень B називається множина упорядкованих пар
У свою чергу, функцією в мові програмування називається конструкція цієї мови, що описує правила перетворення аргументу (так званого фактичного параметра) в результат.
Для формалізації поняття "функція" була побудована математична теорія, відома під назвою ламбда-числення. Більш точно це обчислення слід іменувати обчисленням ламбда-переходів.
Під конверсією розуміється перетворення об'єктів обчислення (а в програмуванні - функцій і даних) з однієї форми в іншу. Вихідною задачею в математиці було прагнення до спрощення форми виразів. У програмуванні саме це завдання не є настільки суттєвою, хоча, як ми побачимо надалі, використання ламбда-числення як вихідної формалізації може сприяти спрощенню виду програми, тобто вести до оптимізації програмного коду.
Крім того, конверсії забезпечують перехід до знову введеним позначенням і, таким чином, дозволяють представляти предметну область в більш компактному або більш детальному вигляді, або, кажучи математичною мовою, змінювати рівень абстракції по відношенню до предметної області. Цю можливість широко використовують також мови об'єктно-орієнтованого і структурно-модульного програмування в ієрархії об'єктів, фрагментів програм і структур даних. На цьому ж принципі засновано взаємодія компонентів програми в. NET. Саме в цьому сенсі перехід до нових позначень є одним з найважливіших елементів програмування в цілому, і саме ламбда-числення (на відміну від багатьох інших розділів математики) являє собою адекватний спосіб формалізації переобозначеній.
Систематизуємо еволюцію теорій, що лежать в основі сучасного підходу до ламбда-обчисленню.
Розглянемо еволюцію мов програмування, що розвиваються в рамках функціонального підходу.
Ранні мови функціонального програмування, які беруть свій початок від класичного мови LISP (LISt Processing), були призначені, для обробки списків, тобто символьної інформації. При цьому основними типами були атомарний елемент і список з атомарних елементів, а основний акцент робився на аналізі вмісту списку.
Розвитком ранніх мов програмування стали мови функціонального програмування з сильною типізацією, характерним прикладом тут є класичний ML, і його прямий нащадок SML. У мовах з сильною типізацією кожна конструкція (або вираз) повинна мати тип.
При цьому в більш пізніх мовах функціонального програмування немає необхідності в явному приписуванні типу, і типи спочатку невизначених виразів, як в SML, можуть виводитися (до запуску програми), виходячи з типів пов'язаних з ними виразів.
Наступним кроком у розвитку мов функціонального програмування стала підтримка поліморфних функцій, тобто функцій з параметричними аргументами (аналогами математичної функції з параметрами). Зокрема, поліморфізм підтримується в мовах SML, Miranda і Haskell.
На сучасному етапі розвитку виникли мови функціонального програмування "нового покоління" з наступними розширеними можливостями: зіставлення зі зразком (Scheme, SML, Miranda, Haskell), параметричний поліморфізм (SML) і так звані "ледачі" (по мірі необхідності) обчислення (Haskell, Miranda, SML).
Сімейство мов функціонального програмування досить численне. Про це свідчить не стільки значний список мов, скільки той факт, що багато мов дали початок цілим напрямкам у програмуванні. Нагадаємо, що LISP дав початок цілому сімейству мовами: Scheme, InterLisp, COMMON Lisp та ін
Не став винятком і досліджуваний нами мову програмування SML, який був створений у формі мови ML Р. Мілнером (Robin Milner) в MIT (Massachusetts Institute of Technology) і спочатку призначений для логічних висновків, зокрема, докази теорем. Мова відрізняється строгою типізацією, в ньому відсутня параметричний поліморфізм.
Розвитком "класичного" ML стали відразу три сучасних мови з практично однаковими можливостями (параметричний поліморфізм, зіставлення зі зразком, "ліниві" обчислення). Це мова SML, розроблений у Великобританії і США, CaML, створений групою французьких вчених інституту INRIA, SML / NJ - діалект SML з New Jersey, а також російська розробка - mosml ("московський" діалект ML).
Близькість до математичної формалізації і початкова функціональна орієнтованість послужили причиною наступних переваг функціонального підходу:
простота тестування та верифікації програмного коду на основі можливості побудови строгого математичного доказу коректності програм;
уніфікація представлення програми і даних (дані можуть бути інкапсульовані в програму як аргументи функцій, означивание або обчислення значення функції може проводитися по мірі необхідності);
безпечна типізація: неприпустимі операції з даними виключені;
динамічна типізація: можливе виявлення помилок типізації під час виконання (відсутність цієї властивості в ранніх мовах функціонального програмування може приводити до переповнення оперативної пам'яті комп'ютера);
незалежність програмної реалізації від машинного представлення даних і системної архітектури програми (програміст зосереджений на деталях реалізації, а не на особливості машинного представлення даних).
У порівнянні з іншими мовами програмування, у тому числі з ранніми функціональними мовами, SML має ряд безперечних достоїнств. До них, в першу чергу, відносяться:
безпека програмного коду, тобто гарантія відсутності переповнення пам'яті (у разі коректно написаної програми) і, відповідно, захисту від потенційної нестійкості роботи системи за допомогою штучного створення переповнення (такі мови програмування як "класичний" C і C + + потенційно небезпечні);
статична типізація: всі помилки невідповідності типів виявляються вже на стадії контролю відповідності типів у ході трансляції (а не під час виконання програми, як в LISP і Scheme);
виводимість типів (немає необхідності явно вказувати тип кожного виразу, при цьому результуючий програмний код стає більш легким для читання, його легше зберігати і повторно використовувати).
До числа інших переваг мови функціонального програмування SML слід віднести параметричний поліморфізм (можливість обробляти аргументи абстрактного типу). При цьому трудовитрати на розробку програмного забезпечення скорочуються за рахунок універсальності розроблюваних функцій (скажімо, стає можливим написати уніфіковану функцію для впорядкування за зростанням елементів списку, яка зможе упорядковувати і список з цілочисельних елементів, і список з символьних рядків).
Ще одним потужним засобом, що полегшує символьну обробку (зокрема, декомпозицію і верифікацію програм), є механізм зіставлення зі зразком.
Побудова програм з модулів сприяє розділенню інтерфейсної (описової) частини та реалізації (змістовної частини) функцій, що забезпечує уніфікацію і скорочує час створення складних програмних проектів, полегшуючи тестування на відповідність специфікаціям замовника.
Обробка виняткових ситуацій, які описують хід виконання програми у разі виникнення тих чи інших щодо рідкісних подій, а також теоретично цікавого механізму продовжень, створює можливість реалізації програмних систем, що взаємодіють з користувачем в реальному часі.
Зауважимо, що реалізація переваг, які надають мови функціонального програмування, істотно залежить від вибору програмно-апаратної платформи.
У разі вибору в якості програмної платформи технології. NET, практично незалежно від апаратної реалізації, програміст або керівник програмного проекту додатково отримує наступні переваги:
інтеграція різних мов функціонального програмування (при цьому максимально використовуються переваги кожного з мов, зокрема, Scheme надає механізм зіставлення зі зразком, а SML - можливість обчислення в міру необхідності);
інтеграція різних підходів до програмування на основі міжмовної інфраструктури Common Language Infrastructure, або CLI (зокрема, можливе використання C # для забезпечення переваг об'єктно-орієнтованого підходу і SML - функціонального, як у справжньому курсі);
загальна уніфікована система типізації Common Type System, CTS (однакове і безпечне управління типами даних в програмі);
багатоступенева, гнучка система забезпечення безпеки програмного коду (зокрема, на основі механізму збірок).