Мова логічного програмування "Пролог" - Комп'ютерні науки - Скачать бесплатно

Постановка завдання

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

Основні терміни:

Терм – будь-який об’єкт даних в Пролозі. Терм буває константою, змінною, складним термом.

Константа – представлена в Пролозі числами і атомами.

Атом – будь-яка послідовність символів, що взята в лапки.

Змінна – будь-яка послідовність символів, букв, цифр та символів-підкреслень, що починаються з писаної букви.

Складний терм (структура) – складається з атома, що називається головним функтором (предикатом), і послідовність термів – компонентів структури.

Факт – поодиноке безумовно істинне твердження.

Зміст

Вступ

1. З історії виникнення мови ПРОЛОГ

2. Актуальність та принцип роботи

3. Чистий ПРОЛОГ

4. Порядок правил та цілей

5. Ефективність програм та їх розробка

Приклади

Висновки

Список використаної літератури

Вступ

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

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

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

На сьогоднішній день існує багато мов програмування, та їх варіантів, які використовуються як починаючими програмістами, так і професіоналами. Але більшість з них не може надати простого рішення при розв’язанні навіть не дуже складної задачі про родинний зв’язок. Прологовський програміст надає простий та логічний опис поняття «дідусь»: дідусь – батько батька. Мовою Пролога це буде виглядати так:

grandfather(X, Z):-father(X, Y),parent(Y, Z).

Тільки-но Пролог-система дізналася, що таке дідусь, до неї можна звернутися з питанням, наприклад: хто є дідусем Івана? У визначеннях Пролога це питання та типова відповідь на нього мають вигляд:

grandfather(X, ivan)

X=petro;

X=egor.

Яким чином вирішувати цю задачу, як перебирати базу даних, в якій записані усі відношення «батько-син», це вже проблема самої Пролог-системи. Програміст тільки повідомляє системі те, що йому відомо та задає питання. Його в більшій ступені цікавлять знання і в меншій – алгоритми, за допомогою яких з цих знань вилучається необхідна інформація. Саме цьому для програмування мовою Пролог необхідно свіже логічне мислення, при якому знання таких мов програмування як Паскаль або Бейсик може бути справжньою поміхою. До речі, назва мови ПРОЛОГ є скороченням «ПРОграмування мовою ЛОГіки»

З історії виникнення мови ПРОЛОГ

Створення штучного інтелекту було і є актуальним протягом багатьох років. Перша версія мови програмування Пролог була створена ще в 1983 році і вдосконалюється до сьогодення. Останньою версією є Visual Prolog для Windows. Основи символьної логіки були закладені Булем, Де Морганом й іншими в минулому сторіччі. Сучасне, систематичне формулювання логіки першого порядку виклав Фреге. Протягом тривалого часу семантика (або “значення”) логіки залишалося заплутаним предметом, але зрештою значна ясність у нього була внесена Тарським.

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

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

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

Створення логічного програмування можна приписати Ковальському й Колмерое.

Ковальский розробив процедурну інтерпретацію хорнових диз’юнктів. Він показав, що аксіома А, якщо В1 й В2 й ... і Вn може розглядатися й виконуватися як рекурсивна мова програмування.

Логічне програмування виникло головним чином завдяки успіхам в автоматичному доказі теорем, зокрема завдяки розробці принципу резолюції. Одне з перших досліджень, що зв'язує резолюцію із програмуванням для ЕОМ, було почато Гріном. Загальна ідея, що складається в розгляді логічних пропозицій як операторів у програмах, а керованого висновку - як виконання програм, була досліджена Хайсом, Сандвеллом й іншими. Однак усвідомленню того, що логіка є мовою для програмування, особливо сприяла зазначена вище процедурна інтерпретація Ковальского.

Успіхи в технології реалізації також значною мірою сприяли поданню логіки як практичної формальної системи програмування. Перший експериментальний інтерпретатор був реалізований Русселом і Колмерое й іншими в університеті Екс – Марсель в 1972 році. Йому було дане ім'я Пролог (“програмування мовою логіки” – PROgramming in Logic), і він вплинув на розробку наступних систем.

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

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

Незважаючи на достаток теоретичних робіт і хвилюючих ідей, концепція логічного програмування здавалася нереалістичною. У цей період у результаті дослідження, проведеного в США, були виявлені серйозні недоліки “мов штучного інтелекту наступного покоління”. Основні претензії до таких мов програмування полягали в наступному: вони були неефективні й дуже важкі в реалізації.

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

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

Актуальність та принцип роботи

Prolog - це здійснена компанією Borland Іnternatіonal реалізація мови програмування високого рівня. Prolog компиляторного типу. Її відрізняє більша швидкість компіляції й рахунку. Prolog призначений для видачі відповідей, які він логічно виводить за допомогою своїх потужних внутрішніх процедур. Так програма на Prolog у кілька рядків може замінити кілька сторінок тексту при програмуванні на якій-небудь іншій мові. Завдяки наявності потужних засобів зіставлення, Prolog придатний не тільки для використання в додатках, що ставляться до області штучного інтелекту й обробці природно-мовних конструкцій, але також застосовуємо в таких традиційних областях, як, наприклад, керування базами даних. Ідея використання логіки у мовах програмування виникла у початку 70-х років. Першими дослідниками, які розроблювали цю ідею, були Роберт Ковальський, Мартен ван Емден та Ален Колмерое з Единбургу. Своєю популярністю серед професіоналів створення штучного інтелекту Пролог зобов’язаний ефективною реалізацією цієї мови в Единбурзі Девідом Уорреном.

Існує безліч історично складених та протидіючих один одному поглядів на Пролог. Пролог швидко завоював популярність в Європі як практичний інструмент програмування. В Японії Пролог опинився у центрі розробки комп’ютерів нового покоління. З іншого боку, через визначені історичні факти, в США Пролог отримав визнання трохи пізніше. Один з цих факторів був пов’язаний з Мікропленнером, мовою, близькою до логічного програмування, але реалізованою неефективно. Цей негативний досвід, який відноситься до Мікропленнера, був невиправдано розповсюджений і на Пролог. Але пізніше після появи ефективної реалізації, запропонованої Девідом Уорреном, цей погляд було скасовано.

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

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

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

parent(tom, bob).

Ця програма містить шість речень. Кожне речення оголошує один факт існування відношення «батько». Питання до системи – це завжди послідовність, що складається з однієї або кількох цілей. Для того, щоб відповісти на питання, система намагається досягти всіх вказаних цілей. Що означає досягти цілі? Досягти цілі – це означає показати, що твердження, які містяться в питанні, дійсні у реченні, що усі відносини програми дійсні. Іншими словами, досягти цілі – це означає показати, що вона логічно витікає з фактів та правил програми. Якщо питання містить змінні, система повинна до того ж знайти конкретні об’єкти, які забезпечують досягнення цілі.

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

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

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

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

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

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

У циклічні алгоритми входить послідовність команд, виконувана багаторазово. Така послідовність команд називається тілом циклу.

Алгоритми можуть бути описані різними способами:

· записані на природній мові;

· зображені у виді блок-схеми;

· записані на алгоритмічній мові;

· закодовані на мові програмування.

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

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

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

Мова програмування характеризується властивими йому механізмами керування й обробки даних. Пролог як універсальну мову програмування можна розглядати й із цих точок зору. При успішному виконанні обчислення засобу керування програм мовою Пролог подібні до засобів керування у звичайних процедурних мовах. Звертання до деякої мети відповідає виклику процедури, порядок цілей у тілі правила відповідає послідовності операторів. Точніше, правило А В1,В2,...,Вn можна розглядати як визначення процедури:

Procedure A

Call B1

Call B2

.

.

.

Call Bn

End.

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

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

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

У логічному програмуванні обробка даних повністю укладена в алгоритмі уніфікації. В уніфікації реалізовані:

• однократне присвоювання,

• передача параметрів,

• розміщення записів,

• доступ до полів записів для одночасних читання/запису.

Традиційні мови, як правило, містять різного ступеня складності засоби обробки помилкових і виняткових ситуацій. Чистий Пролог не містить механізм обробки помилок і виняткових ситуацій, вбудованих в опис мови. На відміну від традиційних мов ситуації, що призводять до помилки (наприклад, відсутність потрібної галузі в операторі case, розподіл на нуль), у чистому Пролозі призводять до “відмови”.

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

Чистий ПРОЛОГ

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

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

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

Порядок правил та цілей

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

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

Принцип обходу дерева в глибину, що використовується у Пролозі призводить до серйозних проблем. Якщо дерево пошуку мети щодо деякої програми містить нескінченну область, то обчислення не завершиться. Пролог може не знайти рішення мети, навіть якщо існує кінцеве обчислення, що вирішує питання. Нескінченні обчислення з'являються при використанні рекурсивних правил. Рекурсивні правила, в яких рекурсивна мета є першою метою в тілі правила, називаються лівими рекурсивними правилами. Ліві рекурсивні правила в Пролозі приносять чимало турбот. У випадку невідповідних аргументів використання цих правил призводить до нескінченних обчислень.

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

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

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

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

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

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

Ефективність програм та їх розробка

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Наявні засоби й системи програмування не нав'язують і не підтримують специфічну методику розробки програм. Однак, як й в інших символьних мовах програмування, найбільш природною стратегією розробки програм є стратегія швидкої зміни прототипів. При такій стратегії на кожній стадії розробки є краще працюючий прототип програми. Розробка відбувається шляхом переробки або розширення прототипу. Інший підхід до розробки програм, іноді комбінуючий з першим, складається в “спадному аналізі й висхідній реалізації”. Хоча проектування системи варто проводити спадним способом, ґрунтуючись на аналізі мети, реалізацію системи найкраще будувати “знизу нагору”. У процесі висхідного програмування кожен написаний фрагмент програми може бути негайно налагоджений. Глобальні проектні рішення, такі, як подання, можуть бути перевірені на невеликих сегментах системи, які будуть наведені в порядок й очищені від помилок на початковій стадії програмування. Крім того, експерименти з однією підсистемою можуть привести до зміни проектних рішень, що ставляться до інших підсистем.

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

Приклади

Приклад1

/*

База даних містить факти: людина(ім’я,вік). Програма має внутрішню мету, що заносить факти СБД в ДБД за допомогою методу ОПН, друкує отриману ДБД на екран, а потім знищує з неї всіх людей, вік яких старше 30 років і друкує частину, що залишилась в ДБД, додає нову інформацію в ДБД, друкує результуючу ДБД і зберігає її в файл "dbd.dat".

*/

domains

name = symbol

age = integer

database

dpeople(name,age)

predicates

people(name,age)

assert_db

create_db

retract_db

write_db

end

goal

makewindow(1,5,5,"DATABASE",0,0,25,80), clearwindow,

create_db, nl, write("1. Створена ДБД"),

nl, write_db, write(" Press any key"), readchar(_),nl,

nl, write("2. Знищується інформація про людей старше 30 років"),

retract_db, nl, write(" Залишок ДБД"), nl,

write_db, write(" Press any key"), readchar(_),nl,

nl, assert_db, write(" Результуюча ДБД"),nl,

write_db, write(" Press any key"), readchar(_), nl,

nl, write("4. Зберігаємо ДБД в файл"),nl, save("dbd.dat"),

write("Press any key"), readchar(_), end, removewindow.

clauses

people("Вася",32).

people("Коля",28).

people("Свєта",40).

create_db:- people(X,Y), assertz(dpeople(X,Y)), fail.

create_db.

retract_db:- dpeople(X,Y), Y>30, retract(dpeople(X,Y)), fail.

retract_db.

write_db:- dpeople(X,Y), write(X," ",Y), nl, fail.

write_db.

assert_db:- write("3. Додаємо інформацію"),nl,

write("Введіть ім’я "), readln(X),

write("Введіть вік "), readint(Y),

assertz(dpeople(X,Y)).

end:- dpeople(_,_),retractall(dpeople(_,_)),fail.

end.

Приклад 2

/* Навчальна програма (підрахунок населення у всіх містах бази даних з використанням комірки динамічної пам’яті (лічильника) */

DOMAINS

name=symbol

num=integer

DATABASE

ds(num)

PREDICATES

town(num,name,num)

rw(num,name,name,num)

proc(num)

make_win

menu

repeat

count(num,num)

dist(name,name,num)

dcount

GOAL

make_win, menu.

CLAUSES

town(1,"Донецьк",1250).

town(2,"Moсква",8000).

town(3,"Київ",5500).

town(4,"Харків",1300).

town(5,"ХХХ",10).

rw(1,"Донецьк","Харків",400).

rw(2,"Харків","Москва",650).

rw(3,"Донецьк","Київ",600).

rw(4,"Київ","Москва",700).

repeat.

repeat:-repeat.

make_win:- makewindow(1,7,7,"MENU",0,0,25,80), clearwindow,

makewindow(2,3,5,"PROC_1",10,10,14,60), clearwindow,

makewindow(3,6,6,"PROC_2",10,10,14,60), clearwindow,

makewindow(4,4,4,"PROC_3",10,10,14,60),clearwindow,

makewindow(5,5,5,"PROC_4",10,10,14,60),clearwindow.

menu:- repeat, shiftwindow(1), nl,nl, write("1 - process 1"),nl,

write("2 - process 2"),nl, write("3 - process 3"),nl,

write("4 - process 4"),nl, write("5 - EXIT"),nl,nl,

write("Enter your choice "),

readint(C), clearwindow, proc(C), C=5,

removewindow(1,1) , removewindow(2,1), removewindow(3,1),

removewindow(4,1), removewindow(5,1) .

proc(1):- shiftwindow(2), nl, write("Список міст"),

nl,nl, town(_,X,Y), write(X," ",Y),

nl, fail.

proc(1):- nl, write("Press any key"), readchar(_),

clearwindow.

proc(2):- shiftwindow(3), nl, write("Список міст з населенням більше даного"),

nl,nl, write("Input population "),

readint(P),nl,

town(_,X,Y), Y>P, write(X," ",Y), nl, fail.

proc(2):- nl, write("Press any key"), readchar(_),

clearwindow.

proc(3):- shiftwindow(4), nl,

write("Distance between 2 towns"),nl,

write("Input town A "),readln(A),nl,

write("Input town B "), readln(B),

dist(A,B,T),nl,

write("Dist. B/W 2 Cities - ",A," and ",B," is ",T),nl,

write("Press any key"), readchar(_),

clearwindow.

proc(5):- nl,nl,nl, write(" Bye! Press any key"),

readchar(_).

proc(4):- shiftwindow(5), nl, asserta(ds(0)),

dcount, ds(X),

write("Population in all towns is ",X),nl,nl,

write("Press any key"), readchar(_),

retractall(ds(_)), clearwindow.

count(N,Sum):- town(N,_,Y), SumNew=Sum+Y, Nnew=N+1,

count(Nnew,SumNew),!.

count(N,Sum):-nl,nl, N1=N-1,

write("Sum. Popul. in ", N1, " towns is ", Sum),

nl.

dcount:- town(_,_,Y), ds(X), Z=X+Y, retractall(ds(_)),

asserta(ds(Z)), fail.

dcount.

dist(A,B,T):- rw(_,A,B,T),!.

dist(A,B,T):- rw(_,B,A,T),!.

dist(A,B,T):- rw(_,A,C,T1), dist(C,B,T2), T=T1+T2,!.

Висновки

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

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