Предикат Str_len (Рядок, Довжина)
(string, integer)
Предикат працює в 3х режимах:
1) При конкретизації змінних (і, o) предикат знаходить довжину рядка.
Наприклад, do: - str_len (“abc”, Dl), write (Dl). Вивід: 3
2) При конкретизації змінних (і, і) порівнюється, чи дорівнює довжина рядка вказаній.
Наприклад, do: - str_len (“abc”, 3), write (“Так”). Якщо довжина рядка інша, то предикат повертає FAIL.
3) При конкретизації змінних (о, і) предикат формує рядок із пропусків зазначеної довжини.
Наприклад, do:-str_len(S, 43) у змінній S формується рядок з 43 пропусків.
Предикат subchar(Рядок, Позиція, Символ)
(і, і, о)
Предикат одержує символ рядку за позицією. Позиції рахуються з 0. Якщо позиція більше ніж довжина рядку, робота предикату закінчується помилкою.
Предикат substring(Вхідний _ Рядок, Позиція, Довжина, Підрядок)
(і, і, і, о)
Предикат одержує з рядку підрядок за номером початку підрядку і його довжиною. Вхідний рядок не змінюється. Якщо Позиція або Довжина виходять за межі рядку робота предикату закінчується помилкою.
Предикат searchchar(Рядок, Символ, Позиція)
(і, і, о)
Предикат шукає символ в рядку і повертає позицію першого знайденого символу. Якщо символ відсутній в рядку, то предикат повертає fail. При наявності у рядку декількох вказаних символів треба повторити дії для залишку рядку.
Предикат searchstring(Рядок, Підрядок, Позиція)
(і, і, о)
Предикат шукає підрядок в рядку і повертає позицію першого знайденого підрядка. Якщо підрядка немає або підрядок завдовжки рядка, то предикат повертає fail.
Предикати перетворення доменів даних
Предикати перетворюють рядки до певних доменів даних або навпаки.
Предикат str_char(Рядок, Символ)
(string, char)
Предикат працює в таких режимах роботи:
(i, o) – перетворює рядок з одного символу типу string в символ типу char.
(o, i) - перетворює символ типу char в рядок з одного символу типу string.
(і, і) - порівнює рядок з одного символу типу string і один символ типу char.
При довжині рядку більше одного символу предикат повертає fail.
Наприклад: str_char(“K”, R) предикат повертає R = ‘K’
str_char(R, ‘K’) предикат повертає R = “K”
str_char(“K”, ‘K’) предикат повертає true.
str_char(“Kb”, ‘K’) предикат повертає fail.
Предикат str_int(Рядок, Ціле число)
(string, integer)
Предикат працює в таких режимах роботи:
(i, o) – перетворює рядок типу string в ціле число.
(o, i) - перетворює ціле число в рядок типу string.
(i, i) - порівнює ціле число з його текстовим подаванням типу string.
Наприклад: str_int(“273”, N) предикат повертає N = 273
str_int(S, 273) предикат повертає S = “273”
str_int(“273”, 273) предикат повертає true.
Предикат str_real(Рядок, Дійсне число)
(string, real)
Предикат працює в таких режимах роботи:
(i, o) – перетворює рядок типу string в дійсне число.
(o, i) - перетворює дійсне число в рядок типу string.
(і, i) - порівнює дійсне число з його текстовим подаванням типу string.
Наприклад:str_real(“34.15”, R) предикат повертає R = 34.15
str_real(R, 12.3) предикат повертає R = ”12.3”
str_real(”12.3”, 12.3) предикат повертає true.
Предикат char_int(Символ, Код символу)
(char, integer)
Предикат працює в таких режимах роботи:
(i, o) – перетворює символ в код символу.
(o, i) - перетворює код символу в символ.
(і, i) - порівнює код символу з символом.
Наприклад: char_int(‘A’, R) предикат повертає R = 65
char_int(R, 97) предикат повертає R = ‘a’
char_int(‘a’, 97) предикат повертає true.
Предикат upper-lower(Символи верхнього регістру, Символи нижнього регістру)
(string, string)
(symbol, symbol)
Предикат працює в таких режимах роботи:
upper-lower (i, o) – перетворює символи верхнього регістру в символи нижнього регістру.
upper-lower (o, i) - перетворює символи нижнього регістру в символ верхнього регістру.
upper-lower (і, i) - порівнює символи нижнього регістру з символами верхнього регістру.
Наприклад: upper-lower (‘A’, R) предикат повертає R = ‘a’
upper-lower(R, ‘a’) предикат повертає R =‘A’
upper-lower(‘A’, ‘a’ ) предикат повертає true.
Предикат term_str(Тип терму, Терм, Рядок)
(symbol, _ , string), де 2 аргумент будь-якого типу.
Предикат term_str – універсальний. Його можна застосовувати для перетворення даних будь-якого типу.
Предикат працює в таких режимах роботи:
(i, i, o) – перетворює дане будь-якого типу в рядок.
(i,o, i) - перетворює рядок в дане вказаного типу.
Наприклад: term_str(real, 12.6, Str) предикат повертає Str = “12.6”.
term_str(real, R, “12.5”) предикат повертає R = 12.5
Розглянемо приклад використання розглянутих стандартних предикатів.
Завдання: Сформувати рядок зазначеної довжини.
Do: - write (“Уведіть рядок”), readln (Str), write (“Уведіть довжину рядка”), readint (D1), form (Str, D1).
form (Str, D1): - str_len (Str, D1), write (Str), nl;
str_len (Str, D), D < D1, D2 = D1 – D,
str_len (Str1, D2), Concat (Str, Str1, S), write(S), nl;
write (“Рядок має великий розмір”),
frontstr (D1, Str, Str1, Str2), write (Str1), nl.
В програмі вводиться рядок і яка в нього повинна бути довжина.
Рядок вказаної довжини просто виводиться. Якщо довжина рядка менше, то рядок доповнюється пропусками. Інакше виводиться частина рядка.
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
6. НИЗХІДНА РЕКУРСІЯ
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 має дві гілки:
Ø по першій гілці до рекурсивного виклику(фаза редукції) відділяється крапка. Старий рядок зменшується на символ. Після рекурсивного виклику (фаза одержання рішення) виконується заміна крапки на знак оклику;
Ø по другій гілці до рекурсивного виклику (фаза редукції) символ відокремлюється і заноситься в стек. Старий рядок зменшується на символ. Після рекурсивного виклику (фаза одержання рішення) символ зі стеку додається в початок нового рядку.
Таким чином символи, що занесено в стек останніми, приєднуються до нового рядку першими.
На фазі редукції у першій гілці крапки в стеку не зберігаються, тому що вони задаються константою.
У фазі редукції аргументи рекурсивного предикату повинні сходитися до аргументів граничної умови.
Компілятор вважає, що рекурсія низхідна, якщо після рекурсивного виклику є хоч один будь-який предикат.
6.2. ЗАГАЛЬНА ХАРАКТЕРИСТИКА РЕКУРСИВНИХ МЕТОДІВ
Рекурсивні методи мають ряд переваг перед ітераційними методами при реалізації операцій, що повторюються:
Ø Ними зручно оброблювати рекурсивні дані.
Ø За допомогою рекурсії можна реалізувати такі алгоритми, які не можна реалізувати ітерацією. При ітераційному методі змінна не зберігає свого значення від однієї ітерації до другої. При рекурсії значення змінних автоматично зберігаються для кожного рівня виклику у стеку.
Ø Рекурсивна програма більш компактна.
6.3. НИЗХІДНА ТА ВИСХІДНА РЕКУРСІЇ
Порівняємо низхідний і висхідний типи рекурсії:
Ø Рекурсивна процедура, що написана висхідним методом рекурсії, може мати всередині предикати з декількома рішеннями. Такий тип рекурсивної процедури використовує стек. При поверненні з рекурсивного предикату змінні зі стеку звільнюються. Тому для збереження рішення використовують додаткові змінні. Низхідний метод додаткових змінних не вимагає.
Ø При утворенні нового списку зі старого, висхідний метод змінює порядок елементів на зворотний. Низхідний метод зберігає порядок елементів в списку.
Ø При утворенні нового файлу зі старого, висхідний метод залишає порядок компонент файлу. Низхідний метод змінює порядок компонент файлу на зворотний.
Ø При роботі з рядками порядок елементів залежить від засобів, якими користується програміст. Предикат Concat дозволяє приєднувати до рядку інший рядок як з початку, так і в кінець. Предикати Frontchar та Fronttoken приєднують рядок тільки з початку.
7. РОБОТА ЗІ СПИСКАМИ
7.1. СПИСКИ. ОГОЛОШЕННЯ СПИСКІВ
Списком називають об’єкт, що має впорядкований набір інших об’єктів. Список може мати будь-яке скінчене число об’єктів. В Пролозі об’єкти списку можуть бути усякого типу, але всі об’єкти повинні бути одного типу. Такі списки називають однодоменними.
Кожний об’єкт списку називають елементом. Списки можуть містити елементи, що повторюються. Список записується у квадратних дужках і кожний елемент відокремлюється комою.
Наприклад список цілих чисел: [1, 2, 5, 7, 3, 2]. Порожній список записується [ ].
Перший елемент списку називають головою списку. Якщо відокремити від списку перший елемент, то залишок списку теж список. Такий залишок називають хвостом списку.
За першими буквами слів Head(голова) та Tail(Хвіст) в літературі прийняті позначення голови – Н, хвоста – Т. Однак, програміст може вибирати будь-які ідентифікатори для елементів списку або хвосту.
Тип списку визначається в секції Domains:
Domains
list = integer * /*список цілих чисел */
list1 = char* /*список символів */
Ідентифікатор типу список задає користувач. Він записується перед „=”. В наших прикладах: list, list1. Після „=” записується тип елементів списку. Для першого прикладу тип елементів integer для другого прикладу char. Символ „*” означає, що об’являється список.
Пролог дозволяє оголошувати тип список списків.
Наприклад:
Domains
lst1 = integer *
lst = lst1*
Щоб визначити список з елементами різних доменів, треба об’явити типом елементу складений тип. До складеного типу можуть відноситися елементи різних доменів.
Наприклад:
Domains
d = kol( integer);
ves( real);
fam(string)
lst=d*
Список визначеного типу може бути:
[fam(“Петренко”),kol(4), ves(30.2), fam(“Ким”), kol(2), ves(12.3)]
7.2. УВІД-ВИВІД СПИСКІВ
Для введення списків використовують універсальний предикат: readterm(тип списку, Змінна).
Розглянемо приклад вводу списку.
Domains
list1=char*
Predicates
do (list1)
Goal
readterm (list1, L), do(L).
Clauses
do (L):- write(“Список ”,L).
Вводиться список: [‘5’, ‘1’, ‘3’]
Вивід списку виконують стандартним предикатом write:
Список [‘5’, ‘1’, ‘3’]
7.3. Основна операція на списках
Пролог розглядає списки типу стек. Тому з елементами списку працюють через голову списку. Для того, щоб працювати з елементом списку, треба спочатку відкинути попередні елементи списку, зробивши цей елемент головою списку.
Для відсіку голови списку, його подають у вигляді структури:
[H | T], де подовжена двокрапка “|” - основна операція на списку.
Відсік голови списку застосовують у двох випадках:
Ø При співставленні предикатів;
Ø При співставленні списків.
Розглянемо приклад відсіку голови списку при співставленні предикатів.
Завдання: Ввести список. Вивести на екран голову і хвіст списку.
Domains
sp= real*
Predicates
prnt (sp)
Goal
readterm (sp, L), prnt (L).
Clauses
prnt ([H | T]):- write(H), nl, write (T).
Введемо список: [3, 5, 7, 9]. При співставленні змінної L, яка конкретизована введеним списком , і структури в голові правила, список поділяється на голову Н=3 і хвіст Т=[5, 7, 9].
Вивід: 3
[5, 7, 9]
Співставлення списків може виконуватися предикатом „=”.
Розглянемо завдання: Ввести список. Вивести на екран голову і хвіст списку.
Domains
Sp= real*
Goal
Readterm (sp, L), L = [H | T], write (H,’ ‘, T).
Введемо список [7]. При співставленні змінної L, яка конкретизована введеним списком , і структури в голові правила, список поділяється на голову Н=7 і хвіст Т=[].
Вивід: 7
[]
Основна операція на списку працює залежно від конкретизації змінних в різних режимах.Режими роботи операції аналогічні режимам роботи предикату frontchar:
Ø Змінна L конкретизована, а змінні Н та L вільні.
Тоді операція L=[H|T], працює на відсікання голови в списку.
Приклад1: do:- L = [1,2,3], L = [H|T], write (H), nl, write (T).
Вивід: Н= 1, Т=[2, 3].
Приклад2: do:- L=[ ], L = [H|T].
Порожній список не можна поділити на голову і хвіст. Операція повертає fail.
Приклад3: do:- L = [[1],[2],[3]], L = [H|T], write (H), nl, write (T).
Вивід: Н= [1], Т=[[2], [3]].
У прикладі подано список списків. Тому елемент списку також список.
Ø Змінні Н і Т конкретизовані: H=2, T=[3, 5], а L вільна змінна. Тоді операція L = [H|T], приєднує елемент Н до початку Т.
Приклад: do : - H=2, T = [3, 5], L = [H | T], write (L).
Вивід: [2, 3, 5].
Ø Операція „|” може працювати на порівняння конкретизованої змінної Н та голови списку. При вірному порівняні вільна змінна Т конкретизується хвостом списку.
Приклад1: do : - L=[1, 2, 3], H=1, L=[H | T], write (Т).
Значення змінної Н дорівнює голові списку. Змінна Т одержує значенням хвіст списку. Вивід: [2, 3].
Приклад2: do : - L=[1, 2, 3], H=2, L=[H | T].
Значення змінної Н не дорівнює голові списку. Предикат повертає fail.
Ø Операція „|” може працювати на порівняння конкретизованої змінної Т та хвоста списку. При вірному порівняні вільна змінна Н конкретизується головою списку.
Приклад1: do : - L=[1, 2, 3], Т=[2, 3], L=[H | T], write (Н).
Значення змінної Т список [2, 3] дорівнює хвосту списку. Змінна Н одержує голову списку. Вивід: 1.
Приклад2: do : - L=[1, 2, 3], Т=[1, 3], L=[H | T].
Значення змінної Т список [1, 3] не дорівнює хвосту списку. Предикат повертає fail.
Ø Операція „|” може працювати на з’ясування чи складається список з вказаних частин. При вірному порівняні операція повертає TRUE.
Приклад: do : - L=[1, 2, 3], H=1, T=[2, 3], L=[H | T].
У списку можна виділити відразу 2, 3 голови, а хвіст завжди один
Приклад: do : - L = [1, 2, 3, 4], L = [H1, H2 | T],
write (H1,’ ‘,H2,’ ‘,T).
Вивід: 1 2 [3, 4].
7.4. Формування списків стандартним предикатом
Предикат Findall(Змінна, Факт, Список)
Предикат findall розглядає групу певних фактів. Вибирає значення вказаного аргументу для кожного факту і формує з цих значень список.
Аргумент „Факт” задає які факти розглядати. Аргумент „Змінна” вказує на аргумент факту, значення якого вибирається. Аргумент „Список” одержує сформований список.
Наприклад.
Завдання: Сформувати список прізвищ пасажирів літаку, у яких відсутній багаж.
Predicates
Do
Bag(string, integer, real)
Goal
Do.
Clauses
Bag(“Кузенко”,10,10.0).
Bag(“Крот”,0,0.0).
Bag(“Михайлов”,12,6.4).
Bag(“Грач”,0,0.0).
Do:- findall(F, bag(F,0,_), L), write(L).
7.5. СПИСКИ І МНОЖИНИ
Множини можна подавати списками. При роботі з такими списками треба пам’ятати:
1 В множині немає елементів, що повторюються.
2 Для множини не важливий порядок елементів.
7.6. ПРОЦЕДУРИ РОБОТИ ЗІ СПИСКАМИ
Список рекурсивний об’єкт, тому що хвіст списку теж список. Такі структури зручно оброблювати рекурсивними процедурами.
Подамо список у формі дерева, що дозволить зрозуміти рекурсивність списку.
Розглянемо список [3, 1, 5, 11]. Розділимо список на голову і хвіст. Хвіст списку в свою чергу теж список. Його теж можна розділити на голову і хвіст. Процес можна повторювати до тих пір, поки список не стане порожнім.
[3, 1, 5, 11]
3 [1, 5, 11]
1 [5, 11]
5 [ 11]
11 []
Зображене дерево бінарне, але можна відокремлювати зразу декілька голів.
Розглянемо приклад програми, яка виводить на екран елементи списку в зворотному порядку. Програма написана низхідним методом рекурсії.
