Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
16
Київський національний університет
імені Тараса Шевченка
Вінник Вадим Юрійович
УДК 681.3.06
Еталонні моделі символьної обробки
01.05.03 –математичне та програмне забезпечення
обчислювальних машин і систем
АВТОРЕФЕРАТ
дисертації на здобуття наукового ступеня
кандидата фізико-математичних наук
Київ –
Дисертацією є рукопис
Робота виконана на кафедрі програмного забезпечення обчислювальної техніки Житомирського державного технологічного університету.
Науковий керівник — Доктор фізико-математичних наук, професор, академік НАНУ
Редько Володимир Никифорович, Київський національний університет імені Тараса Шевченка, професор
Офіційні опоненти — Доктор фізико-математичних наук, старший науковий співробітник
Клименко Віталій Петрович, Інститут проблем математичних машин і систем НАНУ, заступник директора по науковій роботі, м. Київ
Доктор технічних наук, професор
Цейтлін Георгій Овсійович, Міжнародний Соломонів університет, завідувач кафедри, м. Київ
Провідна установа — Інститут програмних систем НАН України, відділ проблем соціально-економічного моделювання, м. Київ
Захист відбудеться 18 грудня 2003 року о 14 годині на засіданні спеціалізованої вченої ради Д 26.001.09 Київського національного університету імені Тараса Шевченка за адресою: 03127, м. Київ-127, проспект Акад. Глушкова, 2, корпус 6, Київський національний університет імені Тараса Шевченка, факультет кібернетики, ауд. 40. Тел. 259-04-24
З дисертацією можна ознайомитися в бібліотеці Київського національного університету імені Тараса Шевченка (вул. Володимирська, 58)
Автореферат розісланий “14” листопада 2003 року
Учений секретар
спеціалізованої вченої ради,
кандидат фізико-математичних наук, доцент В.П.Шевченко
Загальна характеристика роботи
Актуальність теми. Поняття перетворювача над символьними даними, дослідження властивостей різних спеціальних класів таких перетворювачів посідають центральне місце в фундаментальних дослідженнях з теорії алгоритмів, теорії формальних мов та граматик і лежать в основі їх застосувань до теорії та практики програмування. Різновидами символьної обробки (СО), що мають велике практичне значення, є синтаксичний аналіз та компіляція, автоматичне реферування, переклад, інтелектуальний пошук та різноманітні засоби обробки текстів природними мовами, символьна алгебра та аналітичні обчислення, доведення теорем у логіко-математичних численнях.
Побудова складних систем СО потребує математичних моделей та методів, які відображають їх властивості та підтримують процеси проектування. Як відомо, сучасна тенденція розвитку методів програмування полягає в переході від розрізнених невеликих систем, що вирішують кожна окрему задачу, до складних великих систем, що вирішують комплекс задач різного типу у різних галузях. Все це вимагає особливих математичних моделей, спрямованих на цілісне вивчення складного предмету.
Разом з тим, як і в багатьох інших галузях інформатики, суто технічні аспекти, пов’язані зі створенням систем СО, випереджають розвиток теорії даної предметної області. В наслідок цього, значні успіхи інформаційних технологій сусідять з серйозними теоретичними та практичними труднощами, причина яких полягає в неадекватності теорій та моделей СО.
Відомі моделі СО можна поділити на декілька груп. До першої відносяться моделі перетворювачів символьної інформації, що за метою та галуззю застосування стосуються абстрактної математики (наприклад, нормальні алгоритми Маркова, їх узагальнення у вигляді алфавітних операторів Бургіна та Бородянського). Для них характерний високий рівень загальності та абстрактність проблематики, але слабкий зв’язок з програмуванням.
Моделі другої групи, що стосуються конкретних класів структур символьних даних та відповідні спеціалізовані алгоритми обробки (граматики Хомського, методи синтаксичного аналізу LL(k) тощо) знаходять застосування в найбільш поширених інструментальних засобах програмування. Разом з тим, для них характерна жорстка орієнтація на відносно обмежений клас задач, тоді як багато інших важливих застосувань СО не мають подібного по глибині та якості розробки теоретичного апарату.
Моделі конкретних мов та засобів обробки довільної символьної інформації (третя група), такі як модель мови Рефал В.Ф.Турчина, мають практичну цінність, підтверджену створенням та успішною експлуатацією ряду реальних програмних систем. Слід відзначити, що в деякій мірі від зазначених вад звільнена алгебро-алгоритмічна модель СО, відома з робіт Г.О.Цейтліна.
Таким чином, задача розробки моделі СО, що поєднує широту об’єму з глибиною змісту і відображає сутність предмету без спотворень, була і залишається актуальною. Рішення окресленої проблеми передбачає інтегральний розгляд предмету СО як цілого, з точки зору загальнозначущих суттєвих ознак поняття СО.
Зв’язок з науковими програмами, планами, темами. Робота виконана у рамках державно-бюджетної теми “Дослідження універсальних та спеціальних програмних логік” (номер державної реєстрації 0197U003444), що розробляється на кафедрі теорії програмування Київського національного університету імені Тараса Шевченка, а також в рамках досліджень, що проводяться на кафедрі програмного забезпечення обчислювальної техніки Житомирського Державного технологічного університету.
Мета і задачі дослідження. Метою роботи є розробити модель СО, яка задовольняє таким вимогам:
Адекватне відображення сутнісно-визначальних властивостей та змісту СО та абстрагування від несуттєвих деталей;
Відображення типових структур символьних даних та семантики програмних конструктів даної галузі програмування, а також логіки процесів створення програм;
Можливість гнучкої переорієнтації (шляхом доповнення специфічними властивостями) абстрактної та загальної моделі СО на конкретні класи задач;
Забезпечення ієрархічністі моделі у вигляді системи взаємопов’язаних моделей різних аспектів СО на різних рівнях абстракції, побудованих у спільному концептуально-методологічному середовищі та поєднаних апаратом (інтерфейсом) коректного переходу.
Наскрізним методом роботи є метод експлікативного програмування (ЕП), розроблений акад. НАН України В.Н.Редьком, який дозволяє побудову адекватної теоретичної моделі прикладного програмування у формі ієрархії моделей його категорій та аспектів, причому за основу найвищих рівнів ієрархії беруться найсуттєвіші та найзагальніші риси об’єкту. Також у дисертації використовуються методи теорії множин (розділі 3) та методи теорії рекурсивних функцій (розділі 4).
Об’єктом дослідження є СО, як галузь програмування. Предметом дослідження є моделі найсуттєвіших та найзагальніших характеристик СО і зв’язки між ними. Згідно положень ЕП, даний предмет уточнюється як еталонні моделі СО.
Метою обумовлені такі задачі дослідження.
Створити цілісну концепцію еталонної моделі СО, основану на загальному понятті еталонної моделі та на аналізі загальнозначущих характеристик, які становлять сутність СО. Визначити вимоги до форми (структури, складових підмоделей та зв’язків між ними) та змісту (які характеристики ЕП та на якому рівні мають бути відображені).
Застосувати вказану загальну концепцію та побудувати еталонні моделі визначних часткових випадків СО, довести їх повноту та обґрунтувати адекватність. Виявити зв’язки між моделями, показати можливість виразити одну модель в другій. Для цього розглянути такі відгалуження СО: обробку слів як об’єктів, зіставлених з літер, обробку, основану виключно на операції конкатенації, та обробку довільних ієрархічних структур слів, що допускають однозначний розбір.
Узагальнити отримані моделі і розробити таку еталонну модель СО, що поєднує в собі попередні моделі як часткові випадки, наслідуючи їх основні і найбільш значущі властивості, та водночас відображає найзагальніші сутнісні риси, характерні для СО в цілому і може слугувати основою для побудови інших специфічних моделей різноманітних аспектів СО.
Наукова новизна одержаних результатів. В даній роботі, завдяки методу експлікативного програмування, аналіз змісту та семантики СО істотно вдосконалено:
В роботі сформульовано та вирішено нове питання про розробку такої системи засобів обробки літерних структур слів, яка не лише породжує весь клас обчислюваних функцій, але й відображає типові засоби створення програм та процедури їх застосування, і є зручною мовою специфікації та програмування задач, що допускають постановку в термінах літерних структур.
Сформовано нове поняття про систему засобів програмування СО, основану виключно на операції конкатенації, побудовано відповідну композиційну мову та досліджено умову її конструктивності.
Отримано нову композиційну семантику нормальних алгоритмів Маркова яка відрізняється від класичної меншою кількістю залучених базових та проміжних понять, а також відображенням логічної структури побудови алгоритму.
Проведено аналіз спеціальних умов, яким повинні задовольняти операції породження слів, щоб адекватно відображати поняття структур слів, і отримано нову математичну модель структур слів, породжених довільними операціями (відмінними від приписування літер та конкатенації).
На методологічному рівні сформульовано нову цілісну концепцію еталонної моделі СО, її конкретизовано до рівня математичної моделі загальнозначущих властивостей СО та універсальної композиційної мови СО.
Практичне значення одержаних результатів. Композиційні мови, розроблені в дисертації, дозволяють описувати алгоритми СО на природному для них рівні абстракції. Як наслідок, семантику наявних мов та систем СО можливо описати в термінах еталонних моделей СО, як їх прикладну спеціалізацію. Суттєвіше, що завдяки побудові моделі СО як конкретизації та складової частини загальної моделі програмування, а також завдяки масштабованості та ієрархічності моделі і закладеному в ній апарату абстрагування та конкретизації, еталонна модель СО може слугувати для гнучкої, за потребою, семантичної специфікації проблемно-орієнтованих мов СО, налаштованих на конкретні класи задач.
Результати дисертації застосовуються в навчальному процесі на факультеті інформаційно-комп’ютерних технологій Житомирського Державного технологічного університету, в курсі “Сучасні технології програмування”, та при розробці програмного пакету для візуального семантичного конструювання програм, що також призначений для потреб навчального процесу.
Особистий внесок здобувача. Всі результати, що виносяться на захист, отримані автором самостійно. Друковані праці, в яких висвітлено результати дисертації, опубліковані автором одноосібно.
Апробація результатів дисертації. Результати роботи доповідалися на 1-й Міжнародній конференції з індуктивного моделювання МКІМ-2002 (м. Львів), 3-й Міжнародній конференції з програмування УкрПРОГ’(м. Київ), 5-й Міжнародній конференції “Electronic Computers and Informatics” (м. Кошиці, Словацька Республіка), Міжнародній конференції “Інформаційно-комп’ютерні технології 2002” (м. Житомир), на наукових семінарах Київського національного університету імені Тараса Шевченка, Житомирського Державного технологічного університету та Кібернетичного центру НАН України.
Публікації. За темою дисертації опубліковано 6 робіт, з яких 3 є статтями у фахових періодичних виданнях, затверджених ВАК, 3 є доповідями на міжнародних наукових конференціях.
Структура та обсяг дисертації. Дисертація складається з вступу, п’яти розділів, висновків та списку використаних джерел з 58 найменувань. Робота містить 1 ілюстрацію. Загальний обсяг дисертації становить 138 с., основний зміст викладено на 123 сторінках.
Основний зміст роботи
У вступі обґрунтовано актуальність обраної теми, визначено мету та задачі, предмет та об’єкт роботи, методи дослідження, викладено наукову новизну, практичну та теоретичну цінність одержаних результатів.
У першому розділі “Постановка задачі та методологічні аспекти” розглянуто основні характеристики символьної обробки як предмету дослідження; описано галузь практичних застосувань СО; обґрунтовано потребу в адекватній теоретичній моделі СО; описано методологію, концептуальний та формальний апарат експлікативного програмування (ЕП), які скрізь використовуються в роботі; зроблено критичний огляд деяких відомих з літератури моделей СО та обґрунтовано їх недостатність; виявлено основні вимоги до моделі СО, яку потрібно побудувати, та сформульовано уточнену постановку основної задачі дисертації в термінах ЕП.
Експлікативне (від лат. explicatio —роз’яснення) та композиційне програмування (ЕП, КП) —напрямок у теорії програмування, що виходить з мети адекватного відображення сутності програмування або його прикладної галузі. Програмування характеризується певною сукупністю понять та засобів оперування поняттями, що разом складають його логіку. Програмні об’єкти в ЕП розглядаються з точки зору процесів їх створення, породження. Логіка програмування розглядається як логіка процесів породження програм шляхом конструювання складніших програм з простіших за допомогою операцій, які називаються композиціями. Якщо семантику програм описувати за допомогою функцій, що вхідним даним ставлять у відповідність результати, то композиції відображаються як операції алгебри функцій.
Існує сукупність композицій, яка експлікує найзагальніші структури програмування. Описати прикладне програмування значить побудувати такі композиції, які є специфічними та характерними для нього. Через багатоаспектність предмету жодна конструктивна сукупність композицій не може бути достатньою для його повного опису, але скінченною сукупністю композицій можливо описати загальнозначущі ознаки предметної галузі та створити базу для її розгортання, тобто породження більш специфічних композицій за потребою. Експлікація прикладного програмування будується як система взаємопов’язаних підмоделей часткових аспектів, доповнена метамоделлю коректного переходу між підмоделями.
Відомі з літератури спроби моделювання СО не задовольняють критеріям експліцитності та не вирішують в повній мірі задачу побудови адекватної теоретичної моделі засобів програмування задач СО. Однією з основних причин є відображення в моделях семантики та властивостей програм як таких, а не процесів та засобів їх побудови.
На відміну від імперативних мов, що описують послідовності дій над даними, мови СО переважно декларативні, описують сукупності правил обробки даних. Розвинені засоби співставлення зі зразком дозволяють аналізувати вхідні дані не лише послідовно, але й в довільному порядку. Апарат співставлення зі зразком дозволяє стисло описувати складні умови, що накладаються на класи вхідних даних. В основі структур управління обчисленнями лежать переважно рекурсії. Ці ознаки добре узгоджується з природними процесами переробки інформації людиною.
Далі введено засоби формалізації. Композиційна система є трійка #, де # є клас даних, # є множина базових функцій, # є множина композицій над функціями.
Композиція абстрактної мультиплікації ставить у відповідність функціям # та # функцію #, таку, що #.
Через # позначимо проекцію відношення # по #-й компоненті. Нехай # —клас денотатів, # —клас імен. Іменна множина (ІМ) є об’єкт # вигляду #, де #, … # —довільні, #, …, # —попарно різні. Якщо #, то # називають #-іменною множиною (#-ІМ). Класи ІМ, #-ІМ позначимо #, #, або просто #. Кортеж # може бути зображений як ІМ #.
ІМ # та # називаються узгодженими (#), якщо однакові імена в них мають однакові денотати. Операція узгодженого об’єднання #: якщо #, то #, інакше не визначено. Якщо # є #-ІМ, #, то існує єдина #-іменна підмножина #.Операції іменного обмеження # та видалення # з параметром # ставлять у відповідність #-ІМ # нову #-ІМ, відповідно, #-ІМ
Операція іменного заміщення # ставить у відповідність #-ІМ # та #-ІМ # нову #-ІМ #.
Іменними функціями (ІФ) називають функції, аргументами та (або) значеннями яких є ІМ. Якщо область визначення (значень) ІФ є # (#), її називають #-арною (#-альною); #-арну та #-альну ІФ називають #-альною. Поняття ІФ експлікує семантику програм над іменованими змінними. Іменна аплікація # ставить #-арній ІФ # та #-ІМ #, #, значення функції # на об’єкті #. В ЕП семантику імперативних програм прийнято відображати таким чином, що стан пам’яті після застосування імперативної програми # для початкового стану # є #.
Параметризована функція іменування # ставить у відповідність об’єкту # ІМ #. Параметризована функція розіменування # ставить у відповідність ІМ # такий об’єкт #, що #, якщо він існує, в іншому випадку значення # не визначене. Позначимо #, #, #. Композиції іменного обмеження, видалення та заміщення визначаються так:
Позначимо #, #, #. Нехай # —тотожна іменна функція, така, що #. Похідною є композиція послідовного виконання #. Нехай функції #, #, ..., # іменні, #, ..., # —деякі імена. Тоді композиція суперпозиції ставить їм у відповідність функцію
Множину різноманітних схем рекурсії позначено через #.
У другому розділі “Еталонні моделі літерної обробки” побудовано еталонну модель засобів програмування такого типу обробки слів, в основі якого лежить уточнення поняття слова виключно через характеристичну властивість “бути зіставленим з літер”, та виявлено основні властивості даної моделі.
Якісний аналіз сутнісних характеристик поняття літерної зіставленості слів веде до наступної формалізації. В універсумі слів індивідуалізовано спеціальний об’єкт # —порожнє слово. Нехай задана деяка скінченна і непорожня множина # з # об’єктів, що не є об’єктами даних, #. Множину # домовимося називати алфавітом, а об’єкти # —літерами. Функціями правого приписування літер назвемо #-індексоване сімейство # тотальних функцій # типу #, #, причому 1) множина # є замикання множини # відносно множини операцій #; 2) для будь-яких літер # та для будь-яких слів # рівність # має місце тоді і тільки тоді, коли # та #. Слова в такому випадку називаємо словами в алфавіті #. Позначимо #. Четвірка # є система літерних слів. Клас даних складається з класу слів # та класу #-іменних множин слів #.
Побудовано прикладну композиційну мову програмування, яка базується на зазначеній моделі слів. Основу структур функцій становить специфічна композиція —права іменна літерна диз’юнкція. Якщо функція # іменна #-арна типу #, #, …, # —іменні функції, відповідно #, …, #-арні, # —ім’я, то # є #-арна, #, іменна функція, така, що
Композиційна система літерної обробки є трійка #, де #, #, #.
Показано процеси синтезу програм в композиційній системі #. Лема 2.1 стверджує, що можливо виразити будь-яку функцію константу #, таку, що # для довільного слова #. За лемою 2.2 можливо побудувати функцію відсічення останньої літери, таку, що # для будь-якої літери #, і значення # не визначене. Згідно леми 2.3 можливо побудувати функцію розпізнавання рівності слів # з параметрами # та #, #-арну, таку, що для # значенням # є слово #, якщо #, та деяке непорожнє слово в іншому випадку. Побудовано також функцію конкатенації #, яка ІМ # ставить у відповідність слово #, отримане зі слова # приписуванням тих літер, що складають слово #, у тому ж порядку (лема 2.4). Виражено операції алгебри логіки, що дозволяє виражати предикати над словами (лема 2.5). Розглянуто синтез функції реверсування, яка довільному слову ставить у відповідності слово, записане з тих же літер в зворотному порядку (лема 2.6). Як наслідок, виражено функції лівого приписування літери і похідну композицію лівої іменної літерної диз’юнкції та виявлено їх основні властивості (лема 2.7 та теорема 2.1), повністю аналогічні властивостям операцій правого приписування та композиції правої іменної літерної диз’юнкції.
Побудовано похідні композиції, що здійснюють цикл ітеративного типу по всіх розбиттях заданого слова на конкатенацію двох слів (лема 2.13), та цикл по всіх входженнях підслів у задане слово #, тобто по всіх трійках #, таких, що #, де # —конкатенація (лема 2.14). Нехай # — деяке фіксоване слово-параметр, функція # іменна #-арна, що приймає значення у класі слів, функція # має тип #. Побудовано (лема 2.15) похідну композицію диз’юнкції по першому входженню, яка для довільного слова # або застосовує функцію # до ІМ #, де # є перше входження слова # в слово #, якщо таке входження існує, або застосовує # до # в іншому випадку. На основі зазначених засобів показано побудову в системі # функції, що відображає семантику довільного нормального алгоритму (теорема 2.2). Отже, в даній композиційній системі може бути виражена будь-яка обчислювана функція над словами.
Таким чином, основою для експлікації програмування літерної обробки є модель специфічного різновиду символьних даних, яка включає не лише екстенсиональний опис множини слів, але й інтенсиональну їх характеристику через опис засобів їх породження. Такими засобами породження є операції приписування літери. Літери як такі не є об’єктами теорії слів та не є об’єктами обробки у програмах. Специфічні засоби управління обчислювальним процесом основані на розпізнаванні структури символьних даних відносно способу їх породження. Такий розбір є однозначним, чому відповідає композиція типу диз’юнкції. В даній моделі поняття обробки символьних даних можуть бути означені на природному для них рівні абстракції.
В третьому розділі “Еталонні моделі конкатенаційної обробки” побудовано еталонну модель засобів програмування такого різновиду обробки слів, де поняття слова визначено виключно через операцію конкатенації, та виявлено основні властивості моделі.
Система конкатенаційних слів є четвірка #, де # —деяка нескінченна множина об’єктів, які за означенням називаємо словами, # —виділене слово, яке домовимося називати порожнім, # —тотальна бінарна операція типу #, яку назвемо конкатенацією, асоціативна, #, така, що порожнє слово є її одиницею, #, і в алгебрі # немає жодних тотожностей, крім логічних наслідків зазначених співвідношень. Іншими словами, # є вільною напівгрупою з одиницею #.
Нехай слова #, # та # такі, що #. Тоді # називається початком, # (власним початком, #, якщо #), а # (власним, якщо #) кінцем слова #. Відношення # є частковим порядком. Множина усіх початків слова # відносно порядку # лінійно впорядкована, має найменший елемент # та найбільший # (лема 3.2). Пару # при # називаємо розбиттям слова #. Порядок на множині розбиттів: якщо #, то за означенням #.
Конструктивність обробки слів обумовлює додаткову умову, накладену на властивості системи слів. Систем\у конкатенаційних слів будемо називати фінітною, якщо будь-яке слово має скінченну множину початків. Всюди далі вивчаються фінітні системи.
Побудовано прикладну композиційну мову програмування, яка базується на зазначеній моделі слів. Базовими функціями є функції # та # правої та лівої деконкатенації, параметризовані, з параметрами # та #, типу #, такі, що для довільного слова # їх значення визначається співвідношеннями #, #, де #, #, #. Функція конкатенації є параметризована, з парамтерами # та # типу імен, #-арна функція, така, що #. Якщо дано функції #, # та #, де 1 та 2 —імена, то за допомогою функцій іменування та розіменування можливо утворити функцію #, #, # з довільними #, #.
Символьна диз’юнкція по порівнянню є композиція #, яка іменним функціям #, # типу # та іменним функціям #, # ставить у відповідність іменну функцію #, таку, що при позначеннях #, #
Через # позначимо функцію-константу: #. Композиційна система конкатенаційної обробки є трійка #, де #, #, #, а параметр # є скінченна множина #-арних функцій-констант #, таких, що #, де # —деякі наперед фіксовані слова.
В найбіднішій системі # з порожньою множиною констант можливо виразити поняття циклу по всіх розбиттях заданого слова як похідну композицію # (лема 3.3). На цій основі можливо, як для літерних структур слів, означити цикл по входженнях підслів у задане слова, диз’юнкції по першому входженню і семантику довільного нормального алгоритму (теорема 3.1). Отже, дана композиційна система є повною.
Досліджено умову конструктивності конкатенаційної обробки та її зв’язок з моделлю літерної обробки. Показано, що за відсутності умови фінітності або втрачають сенс означення функцій деконкатенації, або не гарантується завершення циклу по розбиттях. Отже, умова фінітності є необхідною для конструктивності конкатенаційної обробки.
Оскільки множина всіх початків кожного слова скінченна та впорядкована, то для кожного слова # існує слово #, безпосередній попередник, такий, що #. Разом з тим, # є попередником # ттт, коли існує деяке слово #, таке, що #. Слово # називатимемо кінцевим приростом слова #, #, якщо # та #. Якщо система слів фінітна, то кінцевий приріст визначений для будь-якого непорожнього слова. Тоді можна розглянути множину # всіх кінцевих приростів.
Мають місце наступні твердження. Слово # неможливо представити конкатенацією двох непорожніх слів # (лема 3.7). Довільне слово # можливо зобразити у вигляді скінченної конкатенації #, де # (лема 3.8). Порядок # співпадає з транзитивним замиканням відношення # (лема 3.9). Поставимо у відповідність кожному атомарному слову # параметризовану унарну функцію #, таку, що #, і запровадимо позначення #, #, тоді множина слів # є замиканням множини # відносно сукупності операцій # (лема 3.10). Для будь-яких слів #, # рівність # має місце тоді і тільки тоді, коли # та # (лема 3.11). Отже, в системі конкатенаційної обробки можливо виразити основні означення літерної обробки (теорема 3.2). На відміну від останньої, в основу конкатенаційної обробки закладено поняття про неоднозначність структури слова. Цим обумовлена суттєва відмінність способу побудови моделей: конотативний (явне конструювання похідних засобів з елементарних) для літерної та денотативний (шляхом опису властивостей) для конкатенаційної обробки.
Таким чином, як і для літерних структур, логіка організації перетворювачів над словами істотно залежить від структури слів. Неоднозначність розбору структур слів обумовлює особливі засоби декомпозиції слова на компоненти, основані на ідеї перебору всіх можливих розбиттів. Умови, накладені на конкатенаційні структури, є природним продовженням вимоги конструктивності перебору.
В четвертому розділі “Однозначні структури слів” побудовано еталонну модель програмування такого типу обробки слів, що визначається уточненням поняття слова як об’єкту, побудованого з інших слів за допомогою певних операцій довільної арності, причому побудова будь-якого слова може бути однозначно розпізнана.
Система однозначно структурованих слів є трійка #, де # —клас об’єктів, які за означенням називатимемо словами, # —виділене слово, яке називатимемо порожнім, # —скінченна сукупність базових функцій # над словами, тотальних поліарних, типу #, #, причому 1) сукупність # містить принаймні одну #-арну функцію, серед яких є функція #, така, що #. Якщо #, то #; 2) сукупність # містить принаймні одну #-арну функцію, #. Якщо #, #, #, то #; 3) рівність # має місце тоді і тільки тоді, коли одночасно виконуються рівності #, # та #; 4) клас # не містить інших об’єктів, крім зазначених в пп. 1 та 2 даного означення. Іншими словами, #-арні базові функції задають атомарні слова-константи, а решта дозволяють будувати з них як завгодно складні слова.
Виявлено властивості даного типу структур слів. Відсутність одиниць (лема 4.1): якщо #, #, #, то # для #. Однозначність розбору (лема 4.2): рівняння # відносно невідомих #, # для будь-якого # має один і тільки один розв’язок.
За означенням, відношення # є таке, що # має місце ттт, коли для деяких #, #, # має місце #, #. Відношення # є транзитивне, а # є рефлексивно-транзитивне замикання відношення #. Відношення # є частковим порядком на множині # (лема 4.3). Слово # є мінімальний елемент множини # відносно порядку # (лема 4.4). Нехай # —деяке задане слово. Побудуємо послідовність # таким чином. Покладемо #. Нехай # для # та #, тоді візьмемо довільне слово #. Будь-яка з послідовностей # має скінченну кількість членів # та # —лема 4.5. Отже, конструктивним є розбір слова і, більше того, процес послідовної декомпозиції слова на компоненти, компоненти компонентів і т.д., оскільки такий процес обов’язково завершиться за скінченну кількість кроків, і його результатами є атомарні порожні слова, подальша декомпозиція яких неможлива.
Побудовано прикладну композиційну мову програмування, яка базується на зазначеній моделі слів. Нехай #, …, # —іменні функції, #. Композиція символьної диз’юнкції по однозначній декомпозиції утворює функцію #, таку, що
де # та # є #-іменною множиною для кожного #.
Композиційна система символьної обробки з однозначно структурованими словами є трійка #, де
Доведено повноту даної композиційної системи. Доведення здійснено за допомогою нумераційного методу в три етапи. На першому етапі побудовано нумерацію слів #, таку, що кожне слово має рівно один #-номер (лема 4.7), але не кожне натуральне число є #-номером слова. Побудовою функції розпізнавання, такої, що #, якщо # є #-номером деякого слова, та # в іншому випадку (лема 4.8), доведено, що множина #-номерів примітивно рекурсивна. Побудовано функцію підрахунку #-номерів #, таку, що # є кількість усіх #-номерів, що не перевищують числа # (лема 4.11). На її основі будується загальнорекурсвна функція перенумерації #, яка взаємно однозанчно відображає множину натуральних чисел на множину #-номерів (леми 4.12–4.15). Звідси отримано взаємно однозначну нумерацію слів # (теорема 4.1).
На другому етапі будується клас # вербонумералів —власна підмножина класу слів, яка взаємно однозначно відображається на множину # натуральних чисел. Вербонумерал, що відповідає числу #, позначається #. За означенням, #, #, де # —деяка виділена базова функція. Вербонумеральне зображення натуральної функції # типу # є функція # типу #, така, що її аргументи та значення є вербонумералами відповідних аргументів та значення функції #. Доведено, що в композиційній системі # можливо виразити вербонумеральні зображення функцій додавання та віднімання одиниці (лема 4.16), а також операторів примітивної рекурсії (лема 4.17) та мінімізації (лема 4.18). Отже, справедлива теорема 4.2: у системі # можливо виразити вербонумеральне зображення будь-якої частково рекурсивної функції.
На третьому етапі на основі нумерації # в системі # побудовано функцію, яка взаємно однозначно відображає множину слів на множину вербонумералів (теорема 4.3). Згідно теореми 4.4, в системі # можуть бути виражені функції, що довільному слову ставлять у відповідність його наступника та попередника в нумерації #. Оскільки в системі # породжуються вербонумеральні зображення усіх частково рекурсивних функцій, в цій системі породжується і клас усіх обчислюваних функцій над словами (теорема 4.5).
Отже, знайдено адекватну математичну модель однозначних (ієрархічних) структур слів. Літерна обробка є частковим випадком даної моделі. Як і в попередніх випадках, засоби обробки слів обумовлені їх структурами: однозначний розбір відповідає композиціям типу диз’юнкції. Апарат композиційного програмування забезпечує гнучке доповнення системи похідними поняттями, що налаштовують модель на конкретний клас задач.
В п’ятому розділі “Неоднозначні структури слів” узагальнено попередні моделі часткових випадків СО і виявлено загальні сутнісні характеристики СО. Особливістю СО є чергування (у порядку, що визначається певним механізмом управління) дій типу аналізу аргументу та синтезу результату. Конкретизаціями загального поняття аналізу аргументу у практичних застосуваннях є розбір слова та співставлення зі зразком. Синтез результату уточнюється як породження слова. Дії типу аналізу та синтезу дуальні одна до одної. Дії типу породження слова допускають обернення у вигляді розбору. Синтез результату на високому рівні загальності здійснюється з тих компонентів, на які розкладено аргумент при розборі. Рушієм обчислювального процесу у СО є процес аналізу аргументу.
Поняття породження слова в загальному випадку уточнюється наступним чином. Система неоднозначно структурованих слів є пара #, де # —клас об’єктів, які за означенням називатимемо словами, # —скінченна сукупність базових функцій # над словами, тотальних, поліарних, типу #, #, причому 1) якщо #, то #; 2) якщо #, #, #, то # і # для кожного #; 3) клас # не містить ніяких інших об’єктів крім визначених в пп. 1 та 2; 4) рівняння розбору # відносно невідомих # та # для кожного заданого # має скінченну та непорожню множину розв’язків; 5) транзитивне замикання # відношення # є частковим порядком на #.
Експліковано поняття структури слова. ІФ # типу # назвемо структурною, якщо для кожного # рівняння # відносно невідомої #, #, має скінченну (можливо, порожню) множину розв’язків, та # для кожного #. З означень слідує, що базові функції # є структурними.
Будь-яка структурна функція над словами може виступати в ролі засобу конструювання похідних символьних структур, оскільки суперпозиція структурних функцій у структурну функцію є також структурна функція (теорема 5.1). Зокрема, якщо #, то рівняння розбору перетворюється на систему
Обґрунтовано адекватність зведення експлікації символьної обробки до наступного часткового випадку. Система неоднозначно по компонентах структурованих слів є така система неоднозначно структурованих слів, що 1) з # слідує #; 2) для кожного # на множині розв’язків рівняння розбору # визначено деякий лінійний порядок #. Якщо слово # таке, що # для деяких #, #, то говоримо, що # є в слові # головною структурою, а слово # називаємо #-словом.
Для неоднозначних по компонентах структур слів введено зручні прикладні композиції. Параметризована, з параметрами # та #, композиція # диз’юнкції по наступному співставленню ставить у відповідність функціям # та # типу # функцію #, значення якої на об’єкті # визначено таким чином. Нехай #,
#, тоді #. Якщо #, то #. Аналогічно означується композиція # диз’юнкції по попередньому співставленню. Композиційна система обробки неоднозначно по компонентах структурованих слів є трійка #, де #, #, #. Доведено, що в даній системі можливо виразити композицію # перебору всіх розв’язків рівняння розбору в заданому порядку (теорема 5.2). Система однозначно структурованих слів є частковим випадком системи неоднозначно структурованих слів, коли рівняння розбору має один і тільки один розв’язок. Система обробки однозначно структурованих слів # є похідною від системи # (теорема 5.3). Побудовано композицію співставлення зі складним зразком, що є суперпозицією структурних функцій, і доведено коректність такої побудови (теорема 5.4).
Ідея подальшої конкретизації структур слів полягає в тому, щоб відокремити однозначні підструктури слів, а неоднозначність звести до однієї лише операції конкатенації. Для даного типу структур слів також побудовано композиційну систему та показано, що композиційна система обробки неоднозначно по компонентах структурованих слів та система конкатенаційної обробки є похідними від неї (теореми 5.6 та 5.6).
Таким чином, загальнозначуща логіка організації обчислювального процесу у СО полягає в керованому чергуванні дуальних дій типу аналізу та синтезу символьних даних. Особливістю породження об’єктів в СО є структурність. Структури символьних даних визначають засоби обробки, семантику та логічну організацію цих засобів. Математичну модель структур слів складають операції, які словам-компонентам ставлять у відповідність слово, певним чином зіставлене з них. Клас операцій, які можуть відігравати роль структуротвірних, виділяється спеціальними умовами, що випливають з аналізу змістовного поняття про структуру. По-перше, слово не може містити себе як свою складову частину, отже відношення “бути частиною” є порядком. По-друге, для будь-якого слова структуру можливо конструктивно розпізнати, виділивши як слова-компоненти, так і спосіб їх зіставлення. Аналіз в СО уточнюється як розпізнавання структури слова та розбір на компоненти, або співставлення зі зразком. Такий розбір може бути неоднозначним, але обов’язково зі скінченною множиною варіантів. Характерною особливістю СО є те, що синтез результату здійснюється переважно з тих компонентів, які були виділені при аналізі вхідних даних, поєднанням їх в іншу структуру. Основою структур управління обчислювальним процесом та основним засобом логічної структуризації програм є перебір всіх варіантів співставлення слова зі зразком. Обґрунтовано, що без втрати адекватності експлікація загального поняття структур слів може бути обмежена експлікацією таких структур, в яких неоднозначність розбору обмежена лише неоднозначністю по компонентах, на які розкладається слово. Побудовано композиційну систему, що відповідає даному типу структур слів, та дано загальний опис семантики засобів співставлення зі зразком. Всі описані в попередніх розділах моделі часткових випадків та специфічних відгалужень СО адекватно вкладаються в побудовану узагальнену еталонну модель СО
Висновки
В дисертації наведено теоретичне узагальнення та нове вирішення наукової задачі, що полягає в розробці адекватної моделі засобів символьної обробки і методики її застосування до конкретних різновидів СО. Це включає такі результати.
1. Побудовано та досліджено еталонні моделі (у формі композиційних систем) визначних відгалужень СО (літерна, конкатенаційна, з однозначних структурами), що характеризуються різними типами структур слів та різними логічними структурами програмування. Для цих моделей доведено повноту (у сенсі можливості виразити довільну обчислювану функцію над словами даної структури), обгрунтовано адекватність відображення в них логіки програм та підтримку звичних процесів конструювання програм. Узагальнення одержаних результатів для часткових випадків СО дозволило побудувати еталонну модель СО в цілому.
2. Виявлено та математично обґрунтовано сутнісно-визначальні та загальнозначущі ознаки поняття символьної обробки. При відмінностях різноманітних відгалужень СО вони мають спільну основу семантики та логіки програмування, що робить можливою концептуально єдину експлікацію СО в цілому. Для моделей різних відгалужень СО показано можливість виразити одну в іншій, чим підтверджується єдність СО.
3. Доведено, що семантичні засоби СО і типова логіка програмування допускають експлікацію в термінах композиційного програмування. Основу всіх моделей СО становлять експлікація характерного різновиду символьних даних в термінах структури та базових операцій породження, а також експлікація логіки програм та засобів управління обчисленнями, основаних на розпізнаванні (розборі) структур слів.
4. Побудовано математичну модель загального поняття структури слів, що містить моделі конкретних різновидів структур як часткові випадки. Розбір однозначних структур адекватно підтримується спеціальними диз’юнкціями, а неоднозначних —циклічним перебором по всіх варіантах розбору. Доведено умови, яким повинні задовольняти структури слів, щоб їх обробка була конструктивною: ієрархічні символьні дані повинні мати скінчену глибину ієрархії, і множина варіантів розбору повинна бути скінченою.
5. Математично обґрунтовано, що використана методологічна основа дозволяє гнучко, за потребою, утворювати нові спеціалізовані моделі логіки та семантики програмування, налаштовані на конкретні класи задач, а також встановлювати зв’язок моделей СО з загальними програмологічними та семантичними структурами програмування. Еталонні моделі придатні для специфікації складних систем, які містять підсистеми СО.
Еталонні моделі СО можуть використовуватися при програмуванні задач символьної обробки в якості мов специфікацій, що відображають природний зміст, притаманний предметній галузі, та водночас допускають конструктивну інтерпретацію, як проблемно-орієнтовані мови високого рівня.
Опубліковані праці за темою дисертації
1. Вінник В.Ю. Композиційні моделі літерних структур слів // Вісник Київського університету. Серія: фізико-математичні науки —. —№ 1 —С. 199–.
2. Вінник В.Ю. Структури функцій символьної обробки літерного рівня // Вісник Київського університету. Серія: фізико-математичні науки —. —№ 2. —С. 169–.
3. Вінник В.Ю. Про експлікацію символьної обробки: загальна характеристика проблеми та методологічні аспекти // Проблемы программирования. —. —№ 1-2. —С. 51–.
4. Vinnik V.Yu. On formal models of pattern matching // Proceedings of the fifth international scientific conference “Electronic Computers and Informatics 2002”, Košice–Herľany (Slovakia). —. — P. 57–.
5. Вінник В.Ю. Еталонні моделі символьної обробки: конкатенаційний рівень // МКІМ-2002. Міжнародна конференція з індуктивного моделювання, Львів, 20–травня 2002: Праці в 4-х томах. —Т. 2. —Львів: Державний НДІ інформаційної інфраструктури, 2002. —С. 47–.
6. Вінник В.Ю. Композиційна семантика мови Рефал // Вісник Житомирського інженерно-технологічного інституту. Серія: технічні науки. Спец. випуск за матеріалами Міжнародної науково-технічної конференції “Інформаційно-комп’ютерні технології 2002”. —. —С. 44–.
Анотації
Вінник В.Ю. Еталоннi моделi символьної обробки. —Рукопис. Дисертацiя на здобуття наукового ступеня кандидата фiзико-математичних наук за спецiальнiстю 01.05.03 - математичне та програмне забезпечення обчислювальних машин і систем. - Київський нацiональний унiверситет iм. Тараса Шевченка, Київ, 2003.
Дисертацію присвячено розробці та дослідженню системи взаємопов’язаних адекватних моделей символьної обробки (СО). Моделі відображають семантику програм СО, як функцій над символьними даними визначеної структури. Досліджено визначні конкретні різновиди структур символьних даних (літерна зіставленість, конкатенація, ієрархія) та відповідні їм засоби обробки. Запропоновано узагальнену математичну модель поняття структури символьних даних в термінах операції синтезу та аналізу. За методом композиційного програмування змодельовано типові засоби побудови програм СО та логіки їх структурної організації. Для моделей суттєво різних типів СО показано можливість виразити одну в одній, чим підтримується концептуальна єдність предмету. Моделі ґрунтуються на аналізі сутності та змісту предмету і мають на меті їх точне відображення. Моделі СО є конкретизаціями моделей загальнозначущих структур програмування, що забезпечує їх інтеграцію в середовище моделей інших галузей програмування. Моделі добре узгоджуються з практично значущими засобами логіки програмування, підтримують процеси конструювання програм та можуть застосовуватися як мови специфікації задач символьної обробки та водночас як проблемно-орієнтовані мови високого рівня.
Ключові слова: символьна обробка, еталонна модель, експлікація, композиція, слово, літера, конкатенація, співставлення зі зразком, семантика.
Винник В.Ю. Эталонные модели символьной обработки. —Рукопись. Диссертация на соискание ученой степени кандидата физико-математических наук по специальности 01.05.03 - математическое и программное обеспечение вычислительных машин и систем. - Киевский национальный университет им. Тараса Шевченко, Киев, 2003.
Ставится и решается задача разработки и исследования системы взаимосвязанных адекватных теоретических моделей символьной обработки (СО), как области прикладного программирования, отражающих семантику программ и средств их построения, средств структурно-логической организации программ и средств управления вычислительным процессом. В качестве общей концептуально-методологической базы построения таких моделей используется экспликативное и композиционное программирование. Выявлены и положены в основу экспликации наиболее характерные, сущностно-определяющие особенности СО. В основе структур программ в данной области лежат дуальные действия типа синтеза и анализа символьных данных. Понятие синтеза слова уточняется той или иной совокупностью операций порождения слов. Особенностью символьных данных является структурность, которая отображается специальными свойствами операций синтеза. Исходя из анализа содержательного понятия структуры, выявлены свойства структур слов и построены соответствующих математические модели для важных частных случаев. Рассмотрены литерный (слова рассматриваются как объекты, составленные из букв операцией правого приписывания) и конкатенационный (слова рассматриваются как объекты, над которыми определена лишь операция конкатенации) типы структур. Литерные структуры характеризуются однозначным, а конкатенационные —неоднозначным разбором. Рассмотрены также иерархические структуры слов с однозначным разбором. На основе сопоставления данных результатов и содержательного анализа общего понятия структуры предложена обобщенная эталонная модель структур слов. Обоснован тезис, что всевозможные структуры слов могут быть описаны как частные случаи данной эталонной модели. Понятие анализа символьных данных соответствует сопоставлению с образцом и разбору слова. В математической модели это уточняется как распознавание способа порождения слова: структуры (операции, которой оно построено) и компонентов (более простых слов, к которым применена операция). Показано, что различными типами структур слов обусловлены различные средства логико-структурной организации программ их обработки. В основе управляющих структур программ лежат специальные дизъюнкции по разбору однозначных структур слов и циклы по всем вариантам разбора для неоднозначных структур. В работе рассмотрены эталонные модели литерной и конкатенациионной обработки, а также обработки произвольных структур слов, допускающих однозначный разбор. Продемонстрирована взаимная выразимость этих моделей и показано, что переход от конкатенационной модели к литерной обусловлен требованием конструктивности. Построена обобщенная эталонная модель средств программирования СО, соответствующая обобщенной эталонной модели структур слов. Рассмотренные модели средств программирования частных случаев СО являются частными случаями последней, что дает основания полагать, что и прочие всевозможные ответвления СО могут быть адекватно описаны в рамках этой модели. Построенная система моделей СО обладает следующими свойствами. Если спецификация задачи допускает естественное задание на определенном уровне абстракции, то решение этой задачи адекватно поддерживается соответствующей эталонной моделью. Общая модель СО есть результат развертывания и конкретизации модели общезначимых средств программирования, т.е. СО представлено как частный случай программирования. Этим обеспечивается интеграция моделей СО в среду моделей других прикладных программирований. Таким же образом, модели специфических разновидностей СО являются частными случаями общей модели СО. Целостность предмета СО поддерживается общей понятийной и методологической базой построения моделей, а на формальном уровне —их взаимной выразимостью. Построенные эталонные модели могут использоваться в качестве языков исполняемых спецификаций для задач СО, а также в качестве проблемно-ориентированных языков высокого уровня.
Ключевые слова: символьная обработка, эталонная модель, экспликация, композиция, слово, литера, конкатенация, сопоставление с образцом, семантика.
Vinnyk V.Yu. Etalon models of symbolic processing. - Manuscript. Thesis for the degree of candidate of physico-mathematical sciences on the speciality 01.05.03 - mathematical and software support of computing machines and systems. - Kyiv National Taras Shevchenko university, Kyiv, 2003.
The thesis is devoted to developing and research of a system of interrelated adequate models of symbolic processing (SP). The models reflect semantics of SP programs as functions over symbolic data of a certain structure. A valuable concrete examples of symbolic data structures are examined (letter combination, concatenation, hierarchy), together with corresponding means of processing. A generalized mathematical model of symbolic data structure notion by means of synthesis and analysis operations. Following the composition programming method, typical means of SP program construction and means of their structural organization logic are modeled. For the models of significantly different types of SP, their mutual expressibility is shown. That supports the conceptual unification of the subject. The models are based on the analysis of the essence and meaning of the subject and aim to their precise reflection. The models of SP are concretizations of models of general programming structures. That enables their integration into the environment of models of models of other areas of programming. The models correspond well to practically valuable means of programming logic, support processes of program construction and can be applied as specification languages for SP problems, and as problem-oriented high level programming languages as well.
Keywords: etalon model, symbolic processing, explication, composition, word, letter, concatenation, pattern matching, semantics.