- •1. Вступ в логічне програмування
- •1.1. Виникнення логічного програмування
- •1.2. Сучасний стан логічного програмування
- •Опис задачі на пролозі. Факти і правила
- •2.1. Опис задачі на пролозі
- •2.2. Факти
- •Цільове твердження
- •Умовні твердження
- •Приклад програми на пролозі
- •2.6. Виконання програми на пролозі
- •2.7. Статична та динамічна бази даних
- •2.8. Підготовка фактів для внутрішньої бази даних
- •2.9. Опис фактів внутрішньої бази даних
- •2.10. Предикати роботи з внутрішньою базою даних
- •2.11. Приклади використання внутрішньої бази даних
- •3. Основні поняття visual-prolog
- •3.1. Загальні відомості
- •3.3. Домени елементарних об’єктів
- •3.4. Терми
- •3.4.1. Константа
- •Анонімна змінна
- •3.4.3. Структури
- •3.5. Програма на пролозі
- •4. Механізми прологу
- •Механізм узгодження цілі з базою даних
- •4.2. Механізм звороту
- •4.3. Механізм звороту і відсік
- •4.4. Рекурсія
- •4.4.1. Рекурсивний метод розв’язку задач
- •Рекурсивні методи 2-х доменів:
- •Застосуємо висхідний метод рекурсії до розв’язку задачі:
- •Висхідна рекурсія
- •4.4.4. Предикат repeат
- •Міркування про те, як треба писати програму
- •5. Обробка рядків
- •5.1. Загальні відомості
- •1.1 Стандартні предикати обробки рядків
- •5.3. Лексиграфічне порівняння рядків
- •2Низхідна рекурсія
- •6.1. Метод низхідної рекурсії
- •6.2. Загальна характеристика рекурсивних методів
- •6.3. Низхідна та висхідна рекурсії
- •7. Робота зі списками
- •7.1. Списки. Оголошення списків
- •7.2. Увід-вивід списків
- •7.3. Основна операція на списках
- •7.4. Формування списків стандартним предикатом
- •Процедура з’єднує два списки.
- •Процедура розділяє список на два за вказаним елементом.
- •2.1 Сортування списків на пролозі
- •Сортування методом пухирця
- •7.8. Складені списки
- •8. Предикати вводу-вивіду
- •8.1. Предикати вводу
- •8.2. Предикати виводу
- •9. Файли
- •9.1. Символічне ім’я файлу
- •9.2. Вхідний і вихідний потоки
- •9.3. Організація файлу та методи доступу до файлу
- •9.4. Робота з файлами різними методами доступу
- •9.5. Закриття файлу
- •9.6. Предикати роботи з каталогами
- •9.7. Предикати, що працюють з атрибутами файлів
- •Література
5.3. Лексиграфічне порівняння рядків
Рядки можна порівнювати між собою, при цьому виконується лексиграфічне порівняння – порівняння по кодах.
Можливе порівняння рядків типу string; символів типу char. Ідентифікатори типу symbol порівнювати не можна. Щоб порівняти ідентифікатори, ними треба попередньо конкретизувати змінні, а потім порівнювати значення змінних.
Приклади порівняння рядків:
“ABC” > ”AAD” True
“\65\ 66\ 67” > ”\65\ 65\68” True
‘S’ < ‘A’ Fail
do:-N= day, N1= date, N1<N, write(N).
В останньому прикладі виконується порівняння day < date.
Порівняння символів з кодами з 7 бітами завжди виконується вірно. При порівнянні 8 бітових кодів порівняння виконується не для всіх платформ вірно.
Алгоритм лексиграфічного порівняння:
Порівняння рядків виконується зліва направо. З рядків вибираються символи, що знаходяться в одній і тій же позиції. Порівнюються коди цих символів. Якщо коди рівні, то продовжується порівняння наступних символів. Порівняння виконується доти, доки тест не виявиться істинним чи помилковим. Якщо один рядок коротше іншого, то короткіший рядок менше.
“ba” > “aa” True
“ba” > “bb” Fail
“dfd” < “dfdr”
При порівнянні по ознаці „=” порівняння виконується або до помилкового результату, або до кінця рядку.
“bac” = “bac” True
“bac” = “bag” Fail
2Низхідна рекурсія
6.1. Метод низхідної рекурсії
Метод низхідної рекурсії часто використовують до рекурсивних даних, тому що метод не змінює порядок елементів у результаті відносно початкових даних при застосуванні більшості стандартних предикатів.
Розглянемо метод низхідної редукції на прикладі обробки рекурсивного даного рядку.
Завдання. Замінити в рядку всі крапки на ! .
Фаза редукції: Від рядку послідовно відділяється символ і заноситься в стек до тих пір, поки рядок не стане порожнім.
Нехай задано рядок: ”.2..3.”.
Старий рядок Новий рядок
1 рівень ”.2..3.” ””
2 рівень ”2..3.” ””
3 рівень ”..3.” ””
4 рівень ”.3.” ””
5 рівень ”3.” ””
6 рівень ”.” ””
7 рівень ”” гранична умова ””
При рекурсивному виклику підзадача, це відділення символу від рядку. Коли старий рядок стає порожнім, то і новий рядок покладають порожнім.
Фаза одержання рішення:
Старий рядок Новий рядок
1 рівень ”.2..3.” ”!2!!3!”
2 рівень ”2..3.” ”2!!3!”
3 рівень ”..3.” ”!!3!”
4 рівень ”.3.” ”!3!”
5 рівень ”3.” ”3!”
6 рівень ”.” ”!”
7 рівень ”” гранична умова ””
На фазі одержання рішення до початку нового рядку додається символ „!” замість крапки або переноситься старий символ рядку.
Реалізуємо програму за алгоритмом розглянутим вище. Предикат, що виконує заміну має ім’я zam та аргументи „новий рядок”, „старий рядок”.
Predicates
zam (string, string)
Goal
zam(“.2..3.”, S), write (S).
Clauses
zam(Sl, S):-frontchar(S1, ‘.’, R),zam(R, S2),frontchar (S, ‘!’, S2);(1)
frontchar(S1,C,R),zam(R, S2), frontchar(S, C, S2). (2)
zam(“”, “”).
Предикат zam має дві гілки:
по першій гілці до рекурсивного виклику(фаза редукції) відділяється крапка. Старий рядок зменшується на символ. Після рекурсивного виклику (фаза одержання рішення) виконується заміна крапки на знак оклику;
по другій гілці до рекурсивного виклику (фаза редукції) символ відокремлюється і заноситься в стек. Старий рядок зменшується на символ. Після рекурсивного виклику (фаза одержання рішення) символ зі стеку додається в початок нового рядку.
Таким чином символи, що занесено в стек останніми, приєднуються до нового рядку першими.
На фазі редукції у першій гілці крапки в стеку не зберігаються, тому що вони задаються константою.
У фазі редукції аргументи рекурсивного предикату повинні сходитися до аргументів граничної умови.
Компілятор вважає, що рекурсія низхідна, якщо після рекурсивного виклику є хоч один будь-який предикат.