Формализация списков в метаязыке нормальных форм знаний
Впервые предложена формализация предикатов на списках в метаязыке нормальных форм знаний, базируясь на известных описаниях этих понятий на Прологе, использующих списковый домен. Среди описанных предикатов: добавление элемента в список, удаление элемента, удаление повторов, принадлежность элемента сп...
Збережено в:
| Дата: | 2017 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Видавничий дім "Академперіодика" НАН України
2017
|
| Назва видання: | Доповіді НАН України |
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/126979 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Формализация списков в метаязыке нормальных форм знаний / А.Ф. Кургаев // Доповіді Національної академії наук України. — 2017. — № 10. — С. 18-27. — Бібліогр.: 8 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-126979 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-1269792025-02-23T20:18:39Z Формализация списков в метаязыке нормальных форм знаний Формалізація списків у метамові нормальних форм знань The formalization of lists in the metalanguage of normal forms of knowledge Кургаев, А.Ф. Інформатика Впервые предложена формализация предикатов на списках в метаязыке нормальных форм знаний, базируясь на известных описаниях этих понятий на Прологе, использующих списковый домен. Среди описанных предикатов: добавление элемента в список, удаление элемента, удаление повторов, принадлежность элемента списку, поиск последнего элемента списка, поиск соседних элементов списка, конкатенация списков, реверс и др. Вперше запропоновано формалізацію предикатів на списках у метамові нормальних форм знань, базуючись на відомих описах цих понять на Прологу, які використовують списковий домен. Серед описаних предикатів: додавання елемента в список, видалення елемента, видалення повторів, приналежність елемента списку, пошук останнього елемента списку, пошук сусідніх елементів списку, конкатенація списків, реверс й ін. The formalization of list-based predicates in the meta-language of normal forms of knowledge is presented for the first time, based on the known descriptions of these concepts in Prolog, which use a list-domain. Among the predica tes described are the following: adding an element to the list, removing an element, removing duplicates, checking if an element is in a list, finding the last element of a list, finding adjacent elements in a list, concatenation of lists, re versing a list, etc. 2017 Article Формализация списков в метаязыке нормальных форм знаний / А.Ф. Кургаев // Доповіді Національної академії наук України. — 2017. — № 10. — С. 18-27. — Бібліогр.: 8 назв. — рос. 1025-6415 DOI: doi.org/10.15407/dopovidi2017.10.018 https://nasplib.isofts.kiev.ua/handle/123456789/126979 004.8 ru Доповіді НАН України application/pdf Видавничий дім "Академперіодика" НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Інформатика Інформатика |
| spellingShingle |
Інформатика Інформатика Кургаев, А.Ф. Формализация списков в метаязыке нормальных форм знаний Доповіді НАН України |
| description |
Впервые предложена формализация предикатов на списках в метаязыке нормальных форм знаний, базируясь на известных описаниях этих понятий на Прологе, использующих списковый домен. Среди описанных предикатов: добавление элемента в список, удаление элемента, удаление повторов, принадлежность элемента списку, поиск последнего элемента списка, поиск соседних элементов списка, конкатенация списков, реверс и др. |
| format |
Article |
| author |
Кургаев, А.Ф. |
| author_facet |
Кургаев, А.Ф. |
| author_sort |
Кургаев, А.Ф. |
| title |
Формализация списков в метаязыке нормальных форм знаний |
| title_short |
Формализация списков в метаязыке нормальных форм знаний |
| title_full |
Формализация списков в метаязыке нормальных форм знаний |
| title_fullStr |
Формализация списков в метаязыке нормальных форм знаний |
| title_full_unstemmed |
Формализация списков в метаязыке нормальных форм знаний |
| title_sort |
формализация списков в метаязыке нормальных форм знаний |
| publisher |
Видавничий дім "Академперіодика" НАН України |
| publishDate |
2017 |
| topic_facet |
Інформатика |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/126979 |
| citation_txt |
Формализация списков в метаязыке нормальных форм знаний / А.Ф. Кургаев // Доповіді Національної академії наук України. — 2017. — № 10. — С. 18-27. — Бібліогр.: 8 назв. — рос. |
| series |
Доповіді НАН України |
| work_keys_str_mv |
AT kurgaevaf formalizaciâspiskovvmetaâzykenormalʹnyhformznanij AT kurgaevaf formalízacíâspiskívumetamovínormalʹnihformznanʹ AT kurgaevaf theformalizationoflistsinthemetalanguageofnormalformsofknowledge |
| first_indexed |
2025-11-25T01:26:22Z |
| last_indexed |
2025-11-25T01:26:22Z |
| _version_ |
1849723697479286784 |
| fulltext |
18 ISSN 1025-6415. Dopov. Nac. acad. nauk Ukr. 2017. № 10
ОПОВІДІ
НАЦІОНАЛЬНОЇ
АКАДЕМІЇ НАУК
УКРАЇНИ
ІНФОРМАТИКА
Постановка задачи. Простота структуры списков, эффективность представления в форме
списков разнородной информации в памяти компьютеров и естественность их использо-
ва ния в символьной обработке информации многие годы обеспечивают решающие пре иму-
щест ва и популярность старейшего (после Фортрана) семейства высокоуровневых языков
программирования Лисп (LISP, от англ. LISt Processing — “обработка списков”) в решении
задач искусственного интеллекта. Единство структуры данных признается достоинством
системы программирования: “Лучше иметь 100 функций, которые работают с одной струк-
турой данных, чем 10 функций, работающих с 10 структурами” [1, п. 2.2.1].
Списки позволяют представить практически любые неоднородные и/или иерархиче-
ские структуры данных, возможные в символьных вычислениях, и поддерживают функ цио-
наль ный стиль программирования. В виде списков удобно представлять формулы, функ-
ции, деревья, графы, множества и многие другие сложные объекты. На протяжении истории
появился ряд диалектов языка Лисп: Common Lisp, Haskell 98, Scheme, Standard LISP
и др., по зво ляющих использовать, наравне со списками, структуры, определённые поль-
зователем, и такие структуры, как: vector, hash table [1—3].
Список — один из самых простых и полезных типов структур составных объектов ло ги-
ческого программирования, позволяющий во многих случаях улучшить “читабельность”
программ [4—6].
В метаязыке нормальных форм знаний [7, 8], в отличие от ЛИСПа и Пролога, нет та-
кой встроенной структуры данных, как список, эффективность которой обоснована не толь-
© А.Ф. Кургаев, 2017
doi: https://doi.org/10.15407/dopovidi2017.10.018
УДК 004.8
А.Ф. Кургаев
Институт кибернетики им. В.М. Глушкова НАН Украины, Киев
E-mail: afkurgaev@ukr.net
Формализация списков
в метаязыке нормальных форм знаний
Представлено академиком НАН Украины А.В. Палагиным
Впервые предложена формализация предикатов на списках в метаязыке нормальных форм знаний, бази-
руясь на известных описаниях этих понятий на Прологе, использующих списковый домен. Среди описан-
ных предикатов: добавление элемента в список, удаление элемента, удаление повторов, принадлежность
элемента списку, поиск последнего элемента списка, поиск соседних элементов списка, конкатенация спис-
ков, реверс и др.
Ключевые слова: метаязык нормальных форм знаний, список, предикат, определение, рекурсия.
19ISSN 1025-6415. Допов. Нац. акад. наук Укр. 2017. № 10
Формализация списков в метаязыке нормальных форм знаний
ко теоретически, но и обширной практикой использования этих языков при создании сис-
тем искусственного интеллекта. Потому, для практического использования метаязыка нор-
мальных форм знаний (НФЗ) важно реализовывать и понятие списка, и предикаты на
списках, опираясь на стандартные домены метаязыка НФЗ.
В качестве базовой используем структуру области данных из [7, 8]:
• домен D представлен двумя независимыми массивами — входным INP и выходным
OUT, с которыми связаны переменные m и n, принимающие значения текущих координат
соответствующих массивов;
• две библиотеки одноименных предикатов — библиотеку анализа над данными из INP
и библиотеку порождения над данными из OUT;
• набор системных процедур, управляющих этими элементами домена D:
RB — истинный предикат переключения библиотек;
RIO — истинный предикат переключения массивов INP и OUT;
UIO — истинный предикат объединения/разделения массивов INP и OUT.
Во всех последующих формальных описаниях предикатов на списках использована
нотация метаязыка НФЗ [7, 8], включая элементарные операции: распознавание, распо-
знавание со следом и порождение над информационными структурами, которые обозна-
чаются соответственно знаками “?”, “#” и “!”, присоединяемыми к имени понятия, вводя-
щего некоторую информационную структуру.
1. Представление задачи. В терминах метаязыка НФЗ всякая задача формулирует ся
как доказательство категорического суждения P(x), предикат P которого задан именем, а
субъект (возможно, многоместный аргумент x) задан последовательностью элементов, ог-
раниченной круглыми скобками:
subject = “( )” / “(“ element (“,”element ) ”)”;
Структуру термина element примем подобной в Прологе и в нотации метаязыка НФЗ
[7, 8] опишем так:
element = term / list;
list = ′[′ list_content ′]′;
list_content = element (′,′ element) / head comma tail / variable / true;
head = term (′,′ term);
comma = ′,′ / true;
tail = list;
term = natural / variable / atom / structure;
structure = atom ′(′ term (′,′ term) ′)′;
variable = letter1 (letter / letter1 / number);
letter1 = A / B / C / ... / Z;
letter = a / b / c / ... / z;
natural = numeral (numeral);
numeral = 0/1/2/3/4/5/6/7/8/9;
atom = letter (letter / letter1 / numeral);
Список является рекурсивной структурой данных, потому нужны и рекурсивные ал-
горитмы для его обработки. Главный способ обработки списка — это поэлементный про-
смотр и обработка списка до его исчерпания. Эти алгоритмы обычно задаются двумя ут-
20 ISSN 1025-6415. Dopov. Nac. acad. nauk Ukr. 2017. № 10
А.Ф. Кургаев
верж дениями: одно определяет, что делать с пустым списком, второе — что делать с обыч-
ным списком.
При описании всякой задачи необходимо, прежде всего, определиться с аргументами
предиката, принять некоторую структуру области данных, описать процесс анализа кон-
кретного значения аргументов и, далее, — процесс вывода заключения. Среди базовых пре-
дикатов на списках: формирование, объединение списков; поиск элемента в списке; вставка
элемента в список и удаление из списка и др.
2. Печать списков. Печать элементов списка в Прологе задается двумя утверждениями:
wrіte_a_lіst([ ]).
wrіte_a_lіst([Н|Т]):- wrіte(H), nl, wrіte_a_lіst(Т).
Первое из них утверждает факт истинности для пустого списка, второе — иници ирует
печать головы непустого списка и рекурсивный вызов печати хвоста списка. В метаязыке
НФЗ этот предикат определяется так:
wrіte_a_lіst=′(′ ′[′ L# ′]′ ′)′ viv_wrіte_a_lіst;
viv_wrіte_a_lіst = ^genL ^Х / ^stepL? Х wrіte nl! viv_wrіte_a_lіst;
/* nl - переход на новую строку */
^genL = RIO L ′]′! RIO;
^stepL = Х comma L# ;
X = term;
L = term (′,′ term) / true;
Здесь, в первом утверждении описан анализ структуры аргумента предиката wrіte_a_lіst,
в процессе которого с переменной L связывается исходное значение списка, и, далее, вызы-
вается предикат viv_wrіte_a_lіst, первая альтернатива которого утверждает, что пустой спи-
сок печатать не надо, а вторая альтернатива утверждает поэлементную печать го ловы спи-
ска и рекурсивный вызов предиката viv_wrіte_a_lіst на сокращенном списке.
3. Добавление элемента в список. У предиката add(X,L,L1]) три аргумента: добав-
ляемый элемент X, начальный список L и результирующий — L1. Проще всего добавить
элемент в список — вставить его в самое начало, как голову нового списка L1. В Прологе
это записывают в виде факта:
add(X,L,[X|L]).
Все варианты вывода предиката add(X,L,L1]) (добавление: известного элемента X к
пустому или непустому списку L с получением неизвестного списка L1, неизвестного эле-
мента X к известному списку L с получением известного списка L1, неизвестного элемента
X к неизвестному списку L с получением известного списка L1, известного элемента X к из-
вестному списку L с получением известного списка L1) в метаязыке определим в форме
пяти альтернативных определений термина add:
add = ′(′ X# ′,′ ′[′ ′]’ ′,′? ′[′ A# ′]′ ′)′ wrіteХS / ′(′ X# ′,′ ′[′ Т# ′]′ ′,′? ′[′ A# ′]′ ′)′ wrіteAdd
/ ′(′ A# ′,′ ′[′ L1# ′]′ ′,′? ′[′ L2# ′]′ ′)′ ^genL2 сontrolAdd wrіteХ
/ ′(′ A# ′,′ ′[′ B# ′]′ ′,′? ′[′ L2# ′]′ ′)′ ^genL2 bindingХ_L1 wrіteVV
/ ′(′ Х# ′,′ ′[′ L1# ']' ',' '['? L2# ′]′ ′)′ ^genL2 analysХ_L1;
wrіteХS = A ′=′ ′[′ X ′]′ nl!;
wrіteAdd = A ′=′ ′[′ X ′,′ Т ′]′ ′;′ nl!;
^genL2 = RIO L2 ′]′! RIO;
21ISSN 1025-6415. Допов. Нац. акад. наук Укр. 2017. № 10
Формализация списков в метаязыке нормальных форм знаний
сontrolAdd = Х# analysL1 ^′,′;
analysL1 = RB L1! RB / ^RB;
bindingХ_L1 = Х# comma L1# ^′,′;
wrіteVV = A ′=′ X ′,′ B ′=′ L1 ′;′ nl!;
analysХ_L1 = RB Х comma L1! RB / ^RB;
А = variable;
B = variable;
Т = term (′,′ term);
L1 = term (′,′ term) / true;
L2 = term (′,′ term) / true;
Первая альтернатива завершается порождением одноэлементного списка, вторая аль-
тернатива — порождением нового списка, составленного из известного элемента с прис-
тыковкой к нему известного списка. Третья альтернатива после успешного вычитания
первого списка из второго завершается порождением оставшейся головы второго списка.
Четвертая альтернатива после успешного разделения второго списка на его голову и хвост
завершается порождением найденных элемента и первого списка. Пятая альтернатива со-
стоит в проверке на эквивалентность второго списка с конкатенацией известного элемента
и первого списка.
4. Удаление элемента. Предикат away(X,L,L1) удаления элемента оперирует тремя
аргументами: L1 — это список L, из которого изъят элемент X. В Прологе это записывают
двумя утверждениями, первое из которых — простой факт, завершающий вычисление, а
второй — рекурсивное правило:
away(X, [X|T],T).
away(X, [Y|T], [Y|T1]):- away(X,T,T1).
Все четыре варианта (удаление известного элемента X из известного списка L с полу-
чением неизвестного списка L1; выяснение, действительно ли известный список L1 полу-
чен удалением известного элемента Х из известного списка L; выяснение неизвестного
спис ка L, из которого удален известный элемент X с получением известного списка L1;
выяснение неизвестного элемента X, удаленного из известного списка L с получением из-
вестного списка L1) вывода предиката away(X,L,L1) в метаязыке определим в форме соот-
ветствующих четырех альтернатив.
away = away1 / away2 / away3 / away4;
away1=′(′ X# ′,′ ′[′? Т# ′]′ ′,′? A L# ′)′ viv_away1 wrіteL;
viv_away1 = ^genТ analysX ′,′? Т# ^form_result / ^current_result viv_away1;
away2=′(′ X# ′,′ ′[′? Т# ′]′ ′,′ ′[′? L1 L# ′]′ ′)′ viv_away1 ^genL analysL1;
away3=′(′ X# ′,′? A# ′,′ ′[′? L1# ′]′ ′)′ ^genXL1? L# wrіteL;
away4=′(′ A# ′,′ ′[′? Т# ′]′ ′,′ ′[′? L# ′]′ ′)′ viv_away2;
viv_away2 = ^genT ^headTail1 ^genL searchMatches viv_away2 / wrіteX;
searchMatches = analysX / Y comma searchMatches;
^headTail1 = X ′,′ T#;
^genXL1 = RIO X ′,′ L1! RIO;
^form_result = ^genL variantsL? L#;
variantsL = ^T? ^genT? / ^concatL_Т;
22 ISSN 1025-6415. Dopov. Nac. acad. nauk Ukr. 2017. № 10
А.Ф. Кургаев
^concatL_Т = RIO L ′,′ Т RIO!;
^current_result = Y ′,′ Т# ^genL currentL? L#;
currentL = ^T? ^genY / ^concatL_Y;
^concatL_Y = RIO L ′,′ Y RIO!;
^genT = RIO Т ′]′! RIO;
^genY = RIO Y ′]′! RIO;
wrіteL = A ′=′ ′[′ L ′]′ nl!;
wrіteX = A ′=′ X ′;′ nl!;
analysХ = RB Х! RB / ^RB;
Y = term;
5. Принадлежность элемента списку. У предиката member(X,L) принадлежности эле-
мента Х списку L два аргумента: L — некоторый список и Х — объект того же типа, что и
элементы списка L. Его определение основывается на следующем: X — или голова списка
L, или X принадлежит его хвосту. В Прологе это записывают в виде двух утверждений, пер-
вое из них — факт, завершающий вычисление, второй — рекурсивное правило. Если же спи-
сок пуст, то предикат ложен: у пустого списка нет элементов:
member(X, [X| _ ]).
member(X, [ _ | T ]):- member(X,T).
В метаязыке предикат member(X,L) можно определить рекурсией: если X совпадает с
головой списка, то, независимо от значения его хвоста, получим результирующее значение
истинности “истина”; иначе, делается очередной шаг исследования следующего элемента
списка L после удаления головы текущего списка.
member = ′(′ X# ′,′ ′[′ Т# ′]′ ′)′ viv_member / ′(′ А# ',' '['? X# wrіteХ (′,′ X# wrіteХ) ′]′ ′)′;
viv_member = ^genT analysX / ^step2 viv_member;
^step2 = Y comma? Т#.
Этот предикат можно использовать двояко: во-первых, конечно, для проверки, есть ли в
списке конкретное значение, и, во-вторых, — получить элементы заданного списка.
6. Конкатенация списков. У предиката conc(L1,L2,L3) конкатенации списков три ар-
гумента; первые два L1 и L2 — объединяемые списки, а третий — список L3 является ре-
зультатом конкатенации первых двух. За основу определения этого термина берут рекур-
сию по первому списку, а за базис — факт, утверждающий, что присоединение произволь-
ного списка к пустому списку дает тот самый произвольный список.
conc([ ], L, L).
conc([H|T], L, [H|T1]) :- conc(T,L,T1).
Этот предикат можно применять для решения разных задач: для получения списка, яв-
ляющегося конкатенацией двух заданных; для проверки, является ли третий список конка-
тенацией двух первых; для разбивки третьего списка на подсписки; для поиска одного из
первых списков по заданным двум другим и др. Для этих вариантов использования преди-
кат конкатенации conc(L1,L2,L3) определим в метаязыке так:
conc = conc_1 / conc_2 / conc_3 / conc_4 / conc_5;
conc_1 = ′(′ ′[′ ′]′ ′,′ ′[′ ′]′ ′,′ analysA1 ′)′ / ′(′ ′[′ L1# ′]′ ′,′ ′[′ ′]′ ′,′ analysA2 ′)′
/ ′(′ ′[′ ′]′ ′,′ ′[′? L2# ′]′ ′,′ analysA3 ′)′ / ′(′ ′[′? L1# ′]′ ′,′ ′[′? L2# ′]′ ′,′ analysA4 ′)′;
analysA1 = A# wrіteEmpty / ′[′ ′]′;
23ISSN 1025-6415. Допов. Нац. акад. наук Укр. 2017. № 10
Формализация списков в метаязыке нормальных форм знаний
wrіteEmpty = A ′=′ ′[′ ′]′ nl!;
analysA2 = A# wrіteL1 / analysL1 ^′,′;
wrіteL1 = A ′=′ ′[′ L1 ′]′ nl!;
analysA3 = A# wrіteL2 / analysL2 ^′,′;
wrіteL2 = A ′=′ ′[′ L2 ′]′ nl!;
analysL2 = RB L2! RB / ^RB;
analysA4 = A# wrіteL1_L2 / analysL1_L2 ^′,′;
wrіteL1_L2 = A ′=′ ′[′ L1 ′,′ L2 ′]′ nl!;
analysL1_L2 = RB L1 ′,′ L2! RB / ^RB;
conc_2 = ′(′? A# ′,′ ′[′? L2# ′]′ ′,′ ′[′? L3# ′]′ ′)′ ^genL3 analysCon6;
^genL3 = RIO L3 ′]′! RIO;
analysCon6 = analysL2 ^′,′ wrіteEmpty / ^headTail3 ^hypothes1 ^takeL1 ^genL3 analysC;
^headTail3 = X ′,′ L3#;
^hypothes1 = RIO X ′]′! RIO;
analysC = analysL1_L2 ^′,′ wrіteL1 / ^headTail3 ^hypothes2 ^takeL1 ^genL3 analysC;
^hypothes2 = RIO L1 ′,′ X ′]′! RIO;
conc_3 = ′(′ ′[′? L1# ′]′ ′,′? A# ′,′ ′[′? L3# ′]′ ′)′ ^genL3 analysL1 wrіteConc5;
wrіteConc5 = ^′,′ wrіteEmpty / ′,′ L2# wrіteL2;
conc_4 = ′(′? A L1# ′,′? B# ′,′ ′[′ L3# ′]′ ′)′ ^genL3 ^takeL2 wrіtePair ^headTail2 below;
below = ^hypothes1 ^takeL1 wrіtePair (^genL2 ^headTail2 ^hypothes2 ^takeL1 wrіtePair);
^takeL2= L2#;
^headTail2 = X comma L2#;
^takeL1 = L1#;
wrіtePair = A ′=′ ′[′ L1 ′]′ ′,′ B ′=′ ′[′ L2 ′]′ ′;′ nl!;
conc_5 = ′(′? A L1# ′,′ ′[′? Y ′,′ B# ′]′ ′,′ ′[′ zeroPair nextPair;
zeroPair = Т3# ′]′ ′)′ ^genT3 ^listL2? wrіtePair / ^takeХL2 ^genХ;
nextPair = ^takeL1 ^genL2 ^listL2 wrіtePair / ^takeХL2 ^hypothes2 nextPair;
^listL2= analysY comma? L2#;
analysY = RB Y! RB / ^RB;
^takeXL2 = X comma L2#;
^genT3 = RIO T3 ′]′! RIO;
^genХ = RIO Х ′]′! RIO;
L3 = term (′,′ term) / true;
L4 = term (′,′ term) / true;
T1 = term (′,′ term);
T2 = term (′,′ term);
T3 = term (′,′ term);
T4 = term (′,′ term);
Первая альтернатива conc_1 определяет варианты формирования результата, если пер-
вых два списка составлены из констант или один из них или оба являются пустыми, а тре-
тий список задан константами или именован переменной. Вторая альтернатива conc_2
определяет вариант поиска первого списка, если второй и третий списки составлены из
констант. Третья альтернатива conc_3 определяет вариант поиска второго списка, если пер-
24 ISSN 1025-6415. Dopov. Nac. acad. nauk Ukr. 2017. № 10
А.Ф. Кургаев
вый и третий списки составлены из констант. Четвертая альтернатива conc_4 определяет
вариант поиска первого и второго списков, если третий список составлен из констант. Пятая
альтернатива conc_5 определяет вариант поиска первого A и второго B списков, находя-
щихся соответственно левее и правее заданного элемента Y третьего списка ′[′ T3 ′]′, состав-
ленного из констант.
7. Поиск последнего элемента списка. В Прологе предикат last (L,X) определяется так:
last ([X],X). /* последний элемент одноэлементного списка является этим элементом */
last ([_|L],X):- last (L,X). /*последний элемент списка — это последний элемент его хвоста*/
В метаязыке этот предикат можно определить, используя итерацию:
last = ′(′ ′[′ (Y ′,′ )? X# ′]′ ′,′? A# ′)′ wrіteХ.
В этом определении итерация (Y ′,′ ) выбирает первые n−1 элементов списка L , по-
следний элемент которого связывает переменную Х#, чье значение далее составляет ре-
зультат решения.
8. Два соседних элемента списка. У этого предиката neighbors(X,Y,L) три параметра:
первые два X, Y — элементы, третий L — список элементов такого же типа. Для случая, ког-
да порядок размещения элементов X,Y в списке L важен, в Прологе этот предикат опреде-
ляют с использованием предиката конкатенации:
neighbors(X,Y,L):- conc(_,[X,Y|_],L).
Все пять вариантов (выяснение, действительно ли известные два элемента X, Y со-
седствуют в известном списке L; выяснение, какой неизвестный элемент X является сосед-
ним слева от известного элемента Y в известном списке L; выяснение, какой элемент Y яв-
ляется соседним справа от известного элемента X в известном списке L; выяснение, какие
пары элементов X, Y соседствуют в известном списке L; сконструировать новый список из
двух известных элементов) вывода предиката neighbors(X,Y,L) в метаязыке определим в
форме соответствующих альтернатив.
В метаязыке предикат neighbors(X,Y,L) можно определить так:
neighbors = neighbors1 / neighbors2 / neighbors3 / neighbors4 / neighbors5;
neighbors1 = ′(′ X# ′,′ Y# ′,′ ′[′ L# ′]′ ′)′ viv_neighbors1;
viv_neighbors1 = ^genL analysXY / ^step1 viv_neighbors1;
neighbors2=′(′ X# ′,′? Y# ′,′ ′[′? A# ′]′ ′)′ wrіteXYS;
neighbors3 = ′(′ X# ′,′? A# ′,′ ′[′? L# ′]′ ′)′ viv_neighbors3;
viv_neighbors3 = ^genL analysX? Y# wrіteY / ^step1 viv_neighbors3;
neighbors4=′(′ A# ′,′? Y# ′,′ ′[′? L# ′]′ ′)′ viv_neighbors4;
viv_neighbors4 = ^genL? X# analysY wrіteX / ^step1 viv_neighbors4;
neighbors5=′(′ A# ′,′? B# ′,′ ′[′? L# ′]′ ′)′ (^genL? Х comma Y# wrіteXY ^genL ^step1);
analysXY = RB X ′,′ Y! RB / ^RB;
wrіteY = A ′=′ Y ′;′ nl!;
wrіteXY = A ′=′ X ′,′ B ′=′ Y ′;′ nl!;
9. Реверс списка. У этого предиката reverse(L1, L2) два параметра: первый — исхо-
дный список L1, второй — обращенный список L2. За базис определения этого термина
принимают факт, утверждающий, что реверс пустого списка дает пустой список. Шаг ре-
курсии состоит в конкатенации обращенного хвоста списка с первым элементом исход-
ного списка:
25ISSN 1025-6415. Допов. Нац. акад. наук Укр. 2017. № 10
Формализация списков в метаязыке нормальных форм знаний
reverse([ ],[ ]).
reverse([X|T],Z):— reverse(T,S), conc(S,[X],Z).
В метаязыке предикат reverse(L1, L2) можно определить так:
reverse = ′(′ ′[′ ′]′ ′,′ A# ′)′ wrіteEmpty / ′(′ ′[′ L2# ′]′ ′,′ A# ′)′ viv_reverse wrіteL1
/ ′(′ ′[′ L2# ′]′ ′,′ ′[′? L3# ′]’ ′)′ viv_reverse ^genL1 analysL3;
viv_reverse = ^genL2 ^headTail2 ^genX ^takeL1 further
further = (^genL2 ^headTail2 ^hypothes2 ^takeL1);
analysL3 = RB L3! RB / ^RB.
10. Палиндром. Палиндромом называют список, совпадающий со своим обращением.
В Прологе предикат palindrom(L) определяют через предикат reverse (L,L) с двумя оди-
наковыми аргументами:
palindrom(L):- reverse (L,L).
Подобное метаязыковое определение состоит из двух последовательных преобразо -
ва ний: обращение заданного списка и проверка, совпадает ли результат с начальным
списком:
palindrom = ′(′ ′[′ L2# ′]′ ′)′ ^genL2 ^headTail2 viv_reverse ^genL1 analysL2;
viv_reverse = ^genX ^takeL1 (^genL2 ^headTail2 ^hypothes2 ^takeL1).
11. Удаление из списка всех вхождений заданного значения. Этот предикат delete_
all(X,[L],[L1]) имеет три параметра: первый Х — удаляемый элемент, второй L — начальный
список, а третий L1 — результат удаления из начального списка L всех вхождений заданного
элемента Х.
Определение на Прологе включает три утверждения: первое является базовым фак-
том — пустой список не уменьшается; второе утверждает, что после удаления заданного эле-
мента из головы начального списка L результирующий список является хвостом списка L
без вхождений заданного элемента Х; третье утверждает, что результирующий список яв-
ляется конкатенацией последовательности элементов без удаляемого и результата удале-
ния заданного элемента из хвоста начального списка.
delete_all(_,[],[]).
delete_all(X,[X|L],L1):- delete_all (X,L,L1).
delete_all (X,[Y|L],[Y|L1]):- X<>Y, delete_all (X,L,L1).
Метаязыковое определение включает две рекурсивные альтернативы: удаление головы
текущего списка в случае ее тождественности заданному элементу; иначе присоединить го-
лову текущего списка к текущему составу результирующего списка.
delete_all = ′(′ Y# ′,′ ′[′ L2# ′]′ ′,′ ′[′ A L3# ′]′ ′)′ viv_delete_all;
viv_delete_all=^genL2 ^listL2 viv_delete_all / ^takeXL2 ^upbuildingL3 ^takeL3 viv_
delete_all / wrіteL3;
^genL3X = RIO L3 ′,′ X ′]′! RIO;
^upbuildingL3 = ^genL3 ^nullX ^genL3X / ^genХ;
^nullX = X;
^takeL3= L3#;
wrіteL3 = A ′=′ ′[′ L3 ′]′ nl!;
Если нужно изъять не все вхождения определенного значения в список, а только первое,
то в Прологе используют следующее определение:
26 ISSN 1025-6415. Dopov. Nac. acad. nauk Ukr. 2017. № 10
А.Ф. Кургаев
delete_one(_,[],[]).
delete_one(X,[X|L],L):-!.
delete_one(X,[Y|L],[Y|L1]):- delete_one(X,L,L1).
Метаязыковое определение этой семантики получает вид:
delete_one = ′(′ Y# ′,′ ′[′ L2# ′]′ ′,′ ′[′ A L3# ′]′ ′)′ viv_delete_one;
viv_delete_one = ^genL2 ^listL2 wrіteL3_L2 / ^takeXL2 ^upbuildingL3 ^takeL3 viv_
delete_one / wrіteL3;
wrіteL3_L2 = A ′=′ ′[′ L3 ′,′ L2 ′]′ nl!;
Заключение. Базируясь на известных описаниях на Прологе, использующих спис ковый
домен, впервые разработана в метаязыке НФЗ практически пригодная формализация мно-
жества предикатов на списках.
Представляется, что метаязыковая формализация практически пригодна не только в
качестве новой реализации задач оперирования списками, но и в качестве спецификации
для реализации этих задач в составе других систем.
ЦИТИРОВАННАЯ ЛИТЕРАТУРА
1. Abelson H., Sussman G.J., Sussman J. Structure and interpretation of computer programs. Cambridge: MIT
Press, 1996. 576 р.
2. Haskell 98. Language and Libraries. The Revised Report. Ed. S.P. Jones. Cambridge Academ. 2003. 277 p.
3. Seibel P. Practical Common Lisp. Apress, 2005. 501 р. doi: https://doi.org/10.1007/978-1-4302-0017-8
4. Братко И. Алгоритмы искусственного интеллекта на языке PROLOG. 3-е изд. Пер. с англ. Москва: Изд.
дом “Вильяме”, 2004. 640 с.
5. Адаменко А.Н., Кучуков А.М. Логическое программирование и Visual Prolog. СПб.: БХВ-Петербург,
2003. 992 с.
6. Клоксин У., Меллиш К. Программирование на языке Пролог. Москва: Мир, 1987. 334 с.
7. Кургаев А.Ф., Григорьев С.Н. Нормальные формы знаний. Допов. Нац. акад. наук України. 2015. № 11.
С. 36—43.
8. Кургаев А.Ф., Григорьев С.Н. Метаязык нормальных форм знаний. Кибернетика и системный анализ.
2016. 52, № 6. С. 11—20.
Поступило в редакцию 12.06.2017
REFERENCES
1. Abelson, H., Sussman, G. J. & Sussman, J. (1996). Structure and interpretation of computer programs.
Cambridge: MIT Press.
2. Haskell 98. (2003). Language and Libraries. The Revised Report. Ed. S.P. Jones. Cambridge Academ.
3. Seibel, Peter. (2005). Practical Common Lisp. Apress. doi: https://doi.org/10.1007/978-1-4302-0017-8
4. Bratko, Ivan. (2012). Prolog Programming for Artificial Intelligence. Third Edition. Addison-Wesley.
5. Adamenko, A. N. & Kuchukov, A. M. (2003). Logical Programming and Visual Prolog. St. Petersburg: BHV-
Petersburg (in Russian).
6. Clocksin, William., Mellish & Christopher, S. (2003). Programming in Prolog: Using the ISO Standard 5th
Edition. Berlin etc.: Springer. doi: https://doi.org/10.1007/978-3-642-55481-0
7. Kurgaev, A. & Grygoryev, S. (2015). The normal forms of knowledge. Dopov. Nac. acad. nauk Ukr. No. 11, pp.
36-43 (in Russian).
8. Kurgaev, A. & Grygoryev, S. (2016). Metalanguage of Normal Forms of Knowledge. Cybernetics and Systems
Analysis. 52(6), pp. 839-848. doi: https://doi.org/10.1007/s10559-016-9885-3
Received 12.06.2017
27ISSN 1025-6415. Допов. Нац. акад. наук Укр. 2017. № 10
Формализация списков в метаязыке нормальных форм знаний
О.П. Кургаєв
Інститут кібернетики ім. В.М. Глушкова НАН України, Київ
E-mail: afkurgaev@ukr.net
ФОРМАЛІЗАЦІЯ СПИСКІВ
У МЕТАМОВІ НОРМАЛЬНИХ ФОРМ ЗНАНЬ
Вперше запропоновано формалізацію предикатів на списках у метамові нормальних форм знань, базую-
чись на відомих описах цих понять на Прологу, які використовують списковий домен. Серед описаних
предикатів: додавання елемента в список, видалення елемента, видалення повторів, приналежність еле-
мента списку, пошук останнього елемента списку, пошук сусідніх елементів списку, конкатенація списків,
реверс й ін.
Ключові слова: метамова нормальних форм знань, список, предикат, визначення, рекурсія.
A. F. Kurgaev
V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kiev
E-mail: afkurgaev@ukr.net
THE FORMALIZATION OF LISTS IN THE META-LANGUAGE
OF NORMAL FORMS OF KNOWLEDGE
The formalization of list-based predicates in the meta-language of normal forms of knowledge is presented for the
first time, based on the known descriptions of these concepts in Prolog, which use a list-domain. Among the
predica tes described are the following: adding an element to the list, removing an element, removing duplicates,
checking if an element is in a list, finding the last element of a list, finding adjacent elements in a list, concatena-
tion of lists, re versing a list, etc.
Keywords: meta-language of normal forms of knowledge, list, predicate, definition, recursion.
|