Концепція функціонального програмування.
Лекція 3 . 2 . Парадигми програмування
Вступ. Існує близько 2 500 мов програмування (і це не перебільшення), однак, попри таку різноманітність, число мов, на яких пише більшість, у межах десятка.
Причин, чому деяка мова не стала популярною, не менш, чим самих мов. Це й чвари між їхніми творцями, і погано організований продаж, і поява нових технологій, і просто відверта «кривизна», традиції.
Історію розвитку мов програмування представляють у формі деякої мережі.
У спрощеній формі наближення до генеалогічного дерева мов високого рівня має наступний вигляд, де явний, безпосередній зв'язок відображений суцільною стрілкою, а побічний вплив – пунктирною.
У принципі всі мови програмування створюють для рішення задач із використанням математики (практично всіх її розділів). Найбільш близькою до людини є мова математичного запису умови задачі і її рішень. Мається на увазі не лише строго формалізованого правила математичних позначень, а й виклад із застосуванням природних для людей прийомів оформлення й коментування. Можливо навіть із застосуванням фраз на звичайних мовах спілкування, подібно до того як записують задачі школярі або студенти.
Історія програмування показує прагнення, з одного боку наблизитись до цього ідеалу, а, з іншого - якнайбільше автоматизувати процес рішення задач, щоб програміст не описував у всіх подробицях алгоритми й дії. Ідеальною автоматизацією є повна відсутність будь-яких послідовностей дій - оператор має вводити лише умови задачі - все інше, включаючи вибір методу рішення, побудова структур даних, породження алгоритмів має виконувати сама система програмування. Оці міркування побудовано у вигляді діаграми [Орехов А.И. Языки программирования – эволюция? – 2005 г. http://softcraft.ru/paradigm/common/evol/index.shtml].
|
|
|
Згідно діаграми, мови програмування еволюціонують за деякою загальною закономірністю. Їхній рівень і ступінь декларативності плавно і взаємозалежно зростають. Найпрогресивнішими для прикладного високорівневого програмування є, мабудь мови, що ґрунтуються на функціональному й логічному підходах. Звичайно є величезна кількість мов, здатних зайняти деяке положення на діаграмі, але мається на увазі лише загальна тенденція розвитку.
Діаграма рівня мов математичного запису.
Залишається питання, що перебуває в правому нижньому куті діаграми? Це повинна бути мова, максимально наближена до апаратного рівня машин, але при цьому бути вкрай декларативною. Для такої мови навіть пропонують назву - Ідеальний Асемблер. Можливо в майбутньому (може бути й не такому вже й далекому) такі надінтелектуальні процесори будуть створені.
|
|
|
Типи парадигм. Усі мови і системи програмування за типом їхньої парадигми розподіляють на чотири різновиди:
§ директивні (directive), процедурні (procedural) або імперативні (imperative),
§ структурні ,
§ декларативні (declarative),
§ об'єктно-орієнтовані (object-oriented).
Визначення 1 . Парадигма:
§ згідно з Томасом Куном — це система ідеалів і норм постановки й вирішення проблем;
§ у програмуванні— це сукупність ідей і понять, що визначають стиль написання програм, тобто сукупність правил, що лежать в основі синтаксису й семантики мови програмування.
Імперати́вне програмування — описує процес обчислення у вигляді інструкцій, що змінюють стан програми. Засноване на абстракції машини Тьюринга-Поста як альтернативного визначення поняття алгоритму.
Це – мови Асемблер, Фортран, Алгол, Бейсик, Кобол, Паскаль, Си й багато інших.
1. Вирішуючи задачу, імперативний програміст спочатку створює модель у деякій формальній системі, а потім переписує рішення на імперативну мову в термінах комп'ютера. Але, по-перше, для людини міркувати в термінах комп'ютера досить неприродно. По-друге, переписування рішення на мову програмування, по-суті, не має відношення до розв'язку вихідного завдання. Часто імперативні програмісти навіть розділяють роботу відповідно до двох вказаних етапів: постановники задач формулюють розв'язок задачі у мові специфікації, а інші – кодують його у мові програмування.
|
|
|
2. Неструктурне програмування допускає використання в явному виді команди безумовного переходу (типу GOTO). Імперативна програма схожа на природно мовні накази, команди, які повинен виконати комп’ютер. В усіх мовах директивного програмування команди зводяться або до присвоювання змінній деякого значення, або до вибору наступної команди. Присвоюванню може передувати ряд арифметичних і інших операцій, а команди вибору реалізуються у вигляді умовних операторів і операторів повторення (циклів).
3. Для класичних директивних мов характерно, що послідовність виконуваних команд однозначно визначається її вхідними даними, тобто поведінка імперативної програми повністю детермінована.
4. Директивне програмування – один з найприродніших для людини стилів написання програм, які призводять зрештою до обчислення шуканих величин.
Даний стиль успадкований від програм мовою асемблера, оскільки там команда переходу є обов'язковою. Однак у мовах високого рівня наявність команди переходу спричинює масу серйозних недоліків:
|
|
|
§ програма перетворюється в “спагетті” з нескінченними переходами нагору-униз, її дуже важко супроводжувати й модифікувати;
§ фактично неструктурний стиль програмування не дозволяє розробляти великі проекти;
§ первісне навчання програмуванню на базі неструктурної мови приводить до величезних труднощів при переході на більш сучасні стилі. Як зазначав відомий голандський учений Е. Дейкстра, “програмісти, початково орієнтовані на Бейсик, розумово неповноцінні без надії на зцілення”.
Директивне програмування стали називати процедурним, коли в процесі збільшення складності моделюємих систем і розміру одержуваних програм виникла концепція підпрограм, називаних також процедурами, функціями або методами. Підпрограма дозволяє локалізувати в ній процес виконання певної дії, яка може бути повторена багаторазово за допомогою механізму виклику.
СтруктУрне програмУВАННЯ — методологія розробки програмного забезпечення, в основі якої лежить подання програми у вигляді ієрархічної структури блоків. Запропонована в 1968 році Е. Дейкстрой на противагу необгрунтово частому використанню програмістами оператора goto безумовного переходу, розроблена й доповнена Н. Віртом.
Відповідно до даної методології
§ Кожен програмний модуль (блок, функція, процедура) повинен мати лише один вхід і тільки один вихід. Задача розбивається на велике число дрібних підзадач, кожна з яких вирішується своєю процедурою або функцією (декомпозиція задачі). Проектування програми йде за принципом зверху вниз: спочатку визначаються необхідні для розв'язку програми модулі, їх входи й виходи, а потім уже розробляються ці модулі. Такий підхід разом з локальними іменами змінних дозволяє розробляти проект силами великої кількості програмістів.
§ Будь-який алгоритм можна реалізувати, використовуючи лише три керуючі конструкції:
o послідовне виконання — однократне виконання операцій у тому порядку, у якому вони записані в тексті програми;
o розгалуження — однократне виконання однієї із двох або більш операцій, залежно від виконання деякої заданої умови;
o цикл з передумовою, або із постумовою — багатократне виконання однієї й тієї ж операції доти, поки виконується деяка задана умова (умова продовження циклу).
o У програмі базові конструкції можуть бути вкладені довільним чином, але інших засобів (зокрема, команди GOTO) керування послідовністю операцій не передбачається
§ Логічно цілісні обчислювальні блоки (повторювані або не повторювані) можуть оформлятися у вигляді процедур або функцій. Тоді в тексті основної програми, замість поміщеного в підпрограму фрагмента, вставляється інструкція виклику підпрограми. При виконанні такої інструкції виконується викликана підпрограма, після чого виконується інструкція, наступна за командою виклику підпрограми.
В 1966 році італійськими математиками К. Бомом і Дж. Якопини була сформульована теорема, як можна уникнути використання оператора переходу GOTO.
Теорема про структурне програмування :
Будь-яку схему алгоритму можна представити у вигляді композиції вкладених блоків begin і end, умовних операторів if, then, else, циклів із предумовою (while) і можливо додаткових логічних змінних (прапорів).
Правила зв'язку програмних модулів по керуванню:
§ Передача керування викликуваному модулю завжди здійснюється через його початок, тобто через перший оператор або команду.
§ По закінченні виконання викликуваного модуля керування передається у модуль, що викликав, на оператор, безпосередньо наступний за оператором виклику.
§ Модулі нижчих рівнів чи одного рівня ієрархії можуть викликатись для виконання лише модулями вищих рівнів, тобто модулі нижчих рівнів не можуть викликати модулі вищих рівнів, а модулі одного рівня - викликати один одного.
§ Для виконання модуля з деякої внутрішньої точки виклик здійснюється стандартним чином (через перший оператор), а точка початку задається параметром. При цьому на початку викликуваного модуля повинен стояти перемикач, що забезпечує передачу керування до внутрішніх точок входів по параметру, зазначеному у зверненні.
§ У будь-якому модулі повинна бути передбачена можливість підключення контрольних засобів і засобів налагодження; оператори, що реалізують ці засоби, звичайно зосереджують наприкінці модуля.
Правила зв'язку програмних модулів по інформації:
§ Інформація зон глобальних змінних доступна для використання будь-яким модулям із складу комплекса програм (КП) або групи програм згідно до області дії зони глобальних змінних. Тобто глобальні змінні можуть бути доступні не для всього КП, а лише для зазначеної в описі групи модулів.
§ Локальні змінні доступні лише в межах того модуля, у якому вони визначені або оголошені.
§ Для міжмодульної взаємодії створюються зони обмінних змінних, інформація з яких доступна лише модулям, безпосередньо зв'язаним по керуванню.
§ Для обміну інформацією між модулями забороняється користуватись регістрами й комірками пам'яті, використовуваними як регістри. Тобто по закінченню роботи викликуваного модуля вважається, що регістри не містять інформації щодо результату його роботи.
§ Інформація, наявна в регістрах модуля виклику, має бути збережена на період виконання викликуваного модуля і відновлена при поверненні у модуль виклику. Регістри можуть зберігати як модуль виклику, так і викликуваний модуль, однак прийнята угода повинна бути єдиною для всіх викликів модулів.
Принципи структурного програмування були реалізовані в мові Алгол, але найбільшу популярність завоювала мова Паскаль, створена в 1970 році швейцарським ученим Н. Віртом. Вона може вважатись зразковою мовою програмування, найбільш популярною і зараз (наприклад, у версії Delphi фірми Imprise).
Деякі позитивні якості структурного програмування:
1. Структурне програмування значно скорочує число варіантів побудови програми згідно специфікації, що значно знижує складність програми й, що ще важливіше, полегшує розуміння її іншими розроблювачами.
2. У структурованих програмах логічно зв'язані оператори перебувають візуально ближче, а слабко зв'язані — далі, що дозволяє обходитись без блок-схем і інших графічних форм зображення алгоритмів (по суті, сама програма є власною блок-схемою).
3. Сильно спрощується процес тестування і налагодження структурованих програм.
Як основний формалізм для представлення структур програм використовуються Бекусо-Наурови форми та розширені БНФ (РБНФ).
Опис структури в РБНФ є набір правил, що визначають відношення між терміналами і нетерміналами.
Термінали - елементи структури, що не мають власної структури. У РБНФ термінали - це або визначені поза РБНФ ідентифікатори (імена, що вважаються заданими для даного опису структури), або ланцюжки - послідовності символів у лапках або апострофах.
Нетермінали - елементи структури, що мають власні імена й структуру. Кожне ім'я є рядок символів, а структура визначається правилами, що фіксують його залежність від одного або більше терміналів й/або нетерміналів.
Правило в РБНФ має вигляд:
ідентифікатор = вираз.
де ідентифікатор - ім'я нетермінального символу, а вираз - комбінація терміналів і нетерміналів, об’єднаних спеціальними знаками синтаксису правил РБНФ. Крапка наприкінці - символ, що вказує на завершення правила.
Семантика правила РБНФ: нетермінал, заданий ідентифікатором ліворуч від знака "=", визначається деяким відношенням терміналів і нетерміналів.
Повний опис структури є набір правил, що визначають всі нетермінали так, що кожен нетермінал може бути зведений до комбінації терміналів шляхом послідовного (рекурсивного) застосування правил.
Набір можливих конструкцій РБНФ : конкатенація, альтернативний вибір, умовне входження й ітерація.
Конкатенація визначається послідовним записом символів виразу, що розділяються одним або більше пробільними символами. Правило виду A = B C. позначає, що нетермінал A складається із двох символів - B і C. Наприклад,
Присвоювання = Змінна ":=" Вираз.
- тут нетермінал Присвоювання визначений як конкатенація термів Змінна, ":=" і Вираз.
Альтернативний вибір позначається вертикальною рискою. Правило A = B|C|D. позначає, що нетермінал A може складатись або з B, або з C, або з D.
Умовне входження. Квадратні дужки виділяють необов'язковий елемент виразу. Правило A = [B]. позначає, що нетермінал A або є порожнім, або складається із символу B.
Ітерація. Фігурні дужки позначають конкатенацію будь-якого числа (включаючи нуль) записаних у ній елементів. Правило виду A = {B}. позначає, що A - або порожній, або є конкатенація деякого числа символів B.
Крім основних операцій, у РБНФ можуть використатися звичайні круглі дужки для групування елементів при формуванні складних виразів. Наприклад, правило A = (B|C)(D|E). позначає, що A складається із двох символів, першим з яких є або B, або C, другим - або D, або E, тобто A може бути одним з ланцюжків BD, BE, CD, CE.
Вочевидь, окремим випадком структурного програмування є атрибутні граматики, запропоновані Д. Кнутом для формального опису семантики мов програмування. Атрибутні трансляційні граматики є узагальненням КС-граматики за рахунок приєднання до синтаксичних правил граматики функцій, що обчислюють, так звані, "атрибути" вузлів дерева виводу й, тим самим, "значення" твердження КС-мови. Для цієї ж мети, у свій час, були розроблені й застосовувались і інші формальні системи такі, як W-Граматики, Віденська метамова. Атрибутні трансляційні граматики, як формалізм опису систем, використовують і зараз.
Задачі ШІ вимагають роботи з даними й знаннями у вигляді символьних структур. В обробці символьної інформації важлива не лише форма розглянутих знань, але і їх зміст і значення.
Причиною виникнення наприкінці 1950-х років програмних засобів символьної обробки є нездатність процедурних мов у вигляді чисел і масивів відображати природно об'єкти і ситуації дійсності. Цей недолік, зокрема, утруднював реалізацію евристичних методів, застосовуваних у розв'язку задач ШІ.
В основі ДЕКЛАРАТИВНИХ мов лежить формалізована людська логіка:
людина лише формулює розв'язувану задачу, а пошуком рішення займається імперативна система .
У підсумку одержуємо:
§ значно більшу швидкість розробки додатків,
§ значно менший розмір вихідного коду,
§ легкість запису знань на декларативних мовах,
§ програми, більш зрозумілі за імперативні.
Відоме впорядкування мов програмування по їхній близькості або до машинної, або до природної мови.
Аsm АМ ФП ЛП ПМ I________I_________I_________I_________I
Аsm - асемблер
АМ - алгоритмічні (процедурні) мови
ФП - мови функціонального програмування
ЛП - мови логічного програмування
ПМ - Природні мови (англійська, українська й ін.)
Рис.1. Близькість до природної мови.
Ті, що ближчі до комп'ютера, відносять до мов низького рівня, а ті, що ближчі людям, - мовами високого рівня. У цьому сенсі декларативні мови можна назвати мовами надвисокого або найвищого рівня, оскільки вони дуже близькі до людської мови й людського мислення.
Також цікавим є погляд на розвиток мов і парадигм програмування в історичному аспекті. За рівнем декларативності та часом появи найвідоміші мови програмування розташовуються відповідно до рис. 2 [Сошников. Парадигма лог. Прогр.].
Рис.2. Еволюція мов програмування.
ДЕКЛАРАТИВНИМИ є функціональні (functional), або аппликативні, і логічні (logic) мови. Головне полягає в наступному:
декларативна програма заявляє (декларує), що повинне бути досягнуте в якості мети, а директивна - пропонує, як її досягти.
Пояснимо це на наступному прикладі: Нехай треба пройти в місті з пункту А в пункт Б.
Декларативна програма - це план міста, у якому зазначено обоє пункти, плюс правила вуличного руху. Керуючись цими правилами й планом міста, кур'єр сам знайде шлях від пункту А до пункту Б.
Директивна програма - це список команд, наприклад:
від пункту А по вул. Садовій на північ до пл. Слави, далі по вул. Пушкіна два квартали, потім повернути праворуч і йти до Театрального провулка, по якому ліворуч по правій стороні до будинку 20, що і є пункт Б.
Декларативні програми не пропонують послідовність дій, у них лише дається дозвіл на них. Виконавець сам має знайти спосіб досягнення мети, поставленої програмістом, причому найчастіше це можна зробити по-різному – детермінованість у цьому випадку відсутня.
Не можна казати, що одна мова краща за іншу лише тому, що в ній є можливості, які відсутні в іншій. Тут більш важливо не те, які можливості має мова, а те, чи наявні в неї можливості підтримки стилю програмування, обраного для розв'язку певного кола задач.
ФУНКЦІОНАЛЬНЕ ПРОГРАМУВАННЯ припускає достатнім обчислення функцій від вихідних даних і результатів інших функцій, і не припускає явного зберігання стану програми. Найвідоміші мови: LISP, F#, Haskell, Erlang , APL, ML, Scala, Miranda, Nemerle, XQuery, Python.
Концепція функціонального програмування.
1. Функціональне – це програмування за допомогою функцій у їхньому математичному розумінні. Воно засноване на ідеї: результатом кожної дії є значення, яке може бути аргументом наступної дії.
2. Програми будуються з визначень функцій, кожне з них складається з організуючих обчислення керуючих структур і із вкладених, у тому числі рекурсивних викликів функцій. Кожна функція повертає деяке значення у ту функцію, що її викликала, обчислення якої після цього триває; цей процес повторюється доти, поки функція, що почала процес обчислень, не поверне кінцевий результат.
3. "Чисте" функціональне програмування не має оператора присвоювання, у ньому обчислення функції не приводить до побічних ефектів. Розгалуження обчислень засноване на обробці аргументів умовного твердження, а циклічні обчислення реалізуються за допомогою рекурсії.
4. Відсутність оператора присвоювання робить змінні функціональних мов програмування подібними до змінних в математиці - одержавши одного разу свої значення, вони більш ніколи їх не міняють.
5. Відсутність побічних ефектів у процесі обчислення функцій приводить до того, що порядок виконання окремих фрагментів програми не суттєвий - підсумкове значення в кожному разі буде однаковим.
6. Функціональне програмування досить гарне й іноді в якості першої мови програмування, досліджуваної студентами, обирається Haskell або Lisp. Для успішного оволодіння даним стилем програмування, втім, необхідно досить глибоке розуміння багатьох розділів математики.
ЛОГІЧНЕ ПРОГРАМУВАННЯ засноване на автоматичному доказі теорем, на теорії й апараті математичної логіки з використанням математичних принципів резолюцій. Найвідомішою мовою логічного програмування є Prolog.
Пролог (програмування в логіці) - одна з найбільш широко використовуваних мов логічного програмування. Як і для інших декларативних мов, ми описуємо ситуацію (правила й факти) і формулюємо мету (запит), доручаючи інтерпретаторові Прологу знайти за нас розв'язок задачі.
Програма на Прологу складається з предикатів. Програма на Прологу і база знань – синоніми. Мета формулюється також у вигляді предикатів. Виконання програми на Прологу – це резолюція мети.
Під інтерпретатором Прологу будемо розуміти механізм рішення задачі за допомогою мови Пролог. Інакше кажучи, інтерпретатор мови Пролог - це виконавець Пролог-програм, тобто та "активна сила", яка виконує програми, написані на Прологу.
У кожної з мов програмування є своє коло задач, при розв'язку яких вони використовуються з найбільшою ефективністю.
Для Прологу це задачі, пов'язані з розробкою систем штучного інтелекту (різні експертні системи, програми-перекладачі, інтелектуальні ігри). Використовується для обробки природної мови й має потужні принципово відмінні від традиційних засоби для вилучення інформації з баз даних. Пролог знайшов застосування й у ряді інших областей, наприклад, при рішенні задач складання розкладів. При цьому він не є універсальною мовою програмування й не призначений, зокрема, для розв'язку задач, пов'язаних із графікою або чисельними методами.
Логічне програмування - це концепція, що дозволяє описувати предметну область проблеми без складання алгоритму пошуку розв'язку. Складність програмування нікуди не зникає, вона просто "перетікає" з області побудови алгоритму машинною мовою в область формулювання задачі для її розв'язку машиною.
Пролог є не стільки мовою для програмування, скільки мов ою для опису даних і логіки їхньої обробки. І рішення задачі записується не в термінах комп'ютера, а в термінах предметної області задачі, у дусі модного зараз об’єктно-орієнтованого програмування.
Пролог дуже добре підходить для опису відношень між об'єктами. Тому Пролог називають реляційною мовою. Причому "реляційність" Прологу значно могутніша й розвинена, чим "реляційність" мов для обробки баз даних. Часто Пролог використається для створення систем керування базами даних, де є дуже складні запити, які досить легко записати на Прологу.
У Прологу дуже компактно, порівняно з імперативними мовами, описуються багато алгоритмів. По статистиці, рядок тексту програми мовою Пролог відповідає чотирнадцяти рядкам тексту програми тої ж задачі імперативною мовою. Пролог-програму, як правило, дуже легко писати, розуміти й налагоджувати. Це приводить до того, що час розробки додатка мовою Пролог у багатьох випадках на порядок швидший, ніж на імперативних мовах. У Прологу легко описувати й обробляти складні структури даних.
Прологу властивий ряд механізмів, відсутніх у традиційних мовах програмування: зіставлення зі зразком, вивід з пошуком і вертанням. Ще одна істотна відмінність полягає в тім, що для зберігання даних у Прологу використаються списки, а не масиви. У мові відсутні оператори присвоювання й безумовного переходу, покажчики. Природним і найчастіше єдиним методом програмування є рекурсія.
Пролог вимагає відмови від стереотипів, стилю мислення імперативного програмування.
Основні області застосування Прологу:
§ швидка розробка прототипів прикладних програм;
§ автоматичний переклад з однієї мови на іншу;
§ створення природно-мовних інтерфейсів для існуючих систем;
§ символьні обчислення для рішення рівнянь, диференціювання й інтегрування;
§ проектування динамічних реляційних баз даних;
§ експертні системи й оболонки експертних систем;
§ автоматизоване керування виробничими процесами;
§ автоматичний доказ теорем;
§ напівавтоматичне складання розкладів;
§ системи автоматизованого проектування;
§ базоване на знаннях програмне забезпечення;
§ організація сервера даних або, точніше, сервера знань, до якого може звертатись клієнтський додаток, написаний на якій-небудь мові програмування.
Області, для яких Пролог не призначений: великий обсяг арифметичних обчислень (обробка аудио, відео й т.д.); написання драйверів.
Дата добавления: 2022-01-22; просмотров: 15; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!