Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

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



План:


Введення

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


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

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

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

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

Найбільш відомими мовами функціонального програмування є [2] :

Ще не повністю функціональні початкові версії і Lisp і APL внесли особливий внесок у створення і розвиток функціонального програмування. Пізніші версії Lisp, такі як Scheme, а також різні варіанти APL підтримували всі властивості та концепції функціональної мови.

Як правило, інтерес до функціональних мов програмування, особливо чисто функціональним, був скоріше науковий, ніж комерційний. Однак, такі примітні мови як Erlang, OCaml, Haskell, Scheme (після 1986) а також специфічні R (статистика), Mathematica (символьна математика), J і K (фінансовий аналіз), і XSLT ( XML) знаходили застосування в індустрії комерційного програмування. Такі широко розповсюджені декларативні мови як SQL і Lex / Yacc містять деякі елементи функціонального програмування, наприклад, вони остерігаються використовувати змінні. Мови роботи з електронними таблицями також можна розглядати як функціональні, тому що в осередках електронних таблиць задається масив функцій, як правило залежать лише від інших осередків, а при бажанні змоделювати змінні доводиться вдаватися до можливостей імперативного мови макросів.


1. Історія

λ-числення дозволили здійснити теоретичний опис функції і її обчислення.

Хоча функція частіше розглядається як математична абстракція, а не поняття з мови програмування, вона склала базис всіх мов функціонального програмування на сьогоднішній день. Подібне теоретичне поняття, комбінаторна логіка, є більш абстрактним ніж λ-числення і було засновано раніше. Ця логіка використовується в деяких езотеричних мовах, наприклад в Unlambda. І λ-числення, і комбінаторна логіка були розроблені для більш ясного і точного опису принципів і основ математики. [3]

Першим функціональним мовою була Lisp, створений Джоном МакКарті в період його роботи в Массачусетському технологічному інституті на початку п'ятдесятих. Lisp ввів безліч понять функціональної мови, хоча при цьому сповідував не тільки парадигму функціонального програмування. Пізніші Scheme і Dylan були спробами спростити і вдосконалити Lisp. [джерело не вказано 930 днів]

Мова обробки інформації (ІПЛ) іноді визначається як найперший машинний функціональний мову. Це мова ассемблерного типу для роботи зі списком символів. У ньому було поняття "генератора", який використовував функцію як аргумент, а також, оскільки це мова ассемблерного рівня, він може позиціонуватися як мова, що має функції вищого порядку. Однак, в цілому ІПЛ акцентований на використання імперативних понять. [джерело не вказано 930 днів]

Кеннет Е. Айверсон розробив мову APL на початку шістдесятих, документувати його у своїй книзі A Programming Language. APL справив значний вплив на FR-мова, створена Джоном Бекуса. На початку дев'яностих Айверсон і Роджер Хьюї створили наступника APL - мова програмування J. У середині дев'яностих Артур Вітні, який раніше працював з Айверсон, створив мову K, який згодом використовувався у фінансовій індустрії на комерційній основі. [джерело не вказано 930 днів]

У сімдесятих в університеті Единбургу Робін Мілнер створив мову ML, а Девід Тернер починав розробку мови SASL в університеті Сент-Ендрюса і, згодом, мова Miranda в університеті міста Кент. У кінцевому підсумку на основі ML були створені кілька мов, серед яких найбільш відомі Objective Caml і Standard ML. Також у сімдесятих здійснювалася розробка мови програмування, побудованого за принципом Scheme (реалізація не тільки функціональної парадигми), що отримав опис у відомій роботі "Lambda Papers", а також у книзі вісімдесят п'ятого року "Structure and Interpretation of Computer Programs", в якій принципи функціонального програмування були донесені до більш широкої аудиторії. [джерело не вказано 930 днів]

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


2. Концепції

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


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

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

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

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


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

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

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

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


2.3. Рекурсія

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

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


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

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

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

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

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


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

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

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


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. Особливості

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


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

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

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


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

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

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


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

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


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

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

4.2. Недоліки

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

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


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

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

Примітки

  1. А. Філд, П. Харрісон Функціональне програмування: Пер. з англ. - М.: Мир, 1993. - 637 с, іл. ISBN 5-03-001870-0. Стор. 120 [Глава 6: Математичні основи: λ-числення].
  2. Tiobe Programming Community Index - www.tiobe.com / index.php / content / paperinfo / tpci / index.html
  3. Роджер Пенроуз. Новий розум короля. Про комп'ютери, мисленні і законах фізики. [Глава 2: Лямбда-числення Черча]
  4. Завантажити PDF: "Техніки функціонального програмування, В. А. Потапенко" стр. 8 "Функції вищих порядків" - wm-help.net/books/book/49.html.
  5. Н. А. Роганова Функціональне програмування: Навчальний посібник для студентів вищих навчальних закладів - М.: ГІНФО, 2002. - 260 с. Стор. 14 п. 3.1. Ледачі і енергійні обчислення
  6. Ахмечет В. "Функціональне програмування для всіх" - www.rsdn.ru / article / funcprog / fp.xml

Література

  • Городня Л. В. Основи функціонального програмування. Курс лекцій - М.: Інтернет-університет інформаційних технологій, 2004. С. 280. ISBN 5-9556-0008-6
  • Душкин Р. В. Функціональне програмування мовою Haskell. - М.: ДМК Пресс, 2006. С. 608. ISBN 5-94074-335-8
  • А. Філд, П. Харрісон Функціональне програмування: Пер. з англ. - М.: Мир, 1993. - 637 с, іл. ISBN 5-03-001870-0
  • Н. А. Роганова Функціональне програмування: Навчальний посібник для студентів вищих навчальних закладів - М.: ГІНФО, 2002. - 260 с.

Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Функціональне рівняння
Функціональне рівняння Коші
Програмування
Апплікатівное програмування
Структурне програмування
Структура (програмування)
Черга (програмування)
Делегат (програмування)
Конструктор (програмування)
© Усі права захищені
написати до нас
Рейтинг@Mail.ru