Первая страница
Наша команда
Контакты
О нас

    Головна сторінка



Дисертації: способи трансляції процедурних мов програмування у функціональні мови, науковий керівник: Марченко О.І., к т. н., доцент

Скачати 422.29 Kb.

Дисертації: способи трансляції процедурних мов програмування у функціональні мови, науковий керівник: Марченко О.І., к т. н., доцент




Скачати 422.29 Kb.
Сторінка1/3
Дата конвертації07.06.2017
Розмір422.29 Kb.
  1   2   3

Національний технічний університет України

Київський політехнічний інститут”

Факультет прикладної математики

Кафедра системного програмування і спеціалізованих комп'ютерних систем

Освітньо-кваліфікаційний рівень “Магістр”

Напрям підготовки 6.

Те́хніка (від грец. techne - мистецтво, майстерність) - сукупність засобів, створених людством для обслуговування своїх потреб виробничого і невиробничого характеру. У техніці матеріалізовані знання і виробничий досвід, накопичені людством у процесі розвитку суспільного виробництва.

Систе́мне програмува́ння (або програмування систем) - це вид програмування, який полягає у розробці програм, які взаємодіють з системним програмним забезпеченням (операційною системою), або апаратним забезпеченням комп'ютера.

050102 ”Комп'ютерна інженерія”

Спеціальність 8.05010201 ”Комп'ютерні системи та мережі”

ЗАТВЕРДЖУЮ

Завідувач кафедри

__________ В.П.Тарасенко





“___” ___________ 2013 р.

З А В Д А Н Н Я

НА МАГІСТЕРСЬКУ ДИСЕРТАЦІЮ СТУДЕНТУ
Хоптинцю Вадиму Андрійовичу
1.

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

Дисерта́ція (лат. dissertatio - твір, обговорення, розсуд, доповідь) - спеціально підготовлена наукова праця на правах рукопису, яку виконують для прилюдного захисту на здобуття наукового ступеня. В Україні розрізняють дисертацію для здобуття наукового ступеня кандидата наук (кандидатська дисертація) та доктора наук (докторська дисертація).

Тема дисертації: СПОСОБИ ТРАНСЛЯЦІЇ ПРОЦЕДУРНИХ МОВ ПРОГРАМУВАННЯ У ФУНКЦІОНАЛЬНІ МОВИ,

науковий керівник: Марченко О.І., к.т.н., доцент,

затверджені наказом по університету від 20 березня 2015 року № 785-с.
2. Строк подання студентом дисертації: “19” червня 2015 р.
3. Об’єкт дослідження: внутрішні машино-незалежні форми представлення програм при трансляції.
4. Предмет дослідження: способи трансляції програм із процедурних мов програмування у функціональні мови програмування за допомогою внутрішніх форм представлення програм.

Трансляція (від старофр. translater, від лат. translatus, прикметник минулого часу від transferre - «передавати», «переносити», передача)

Компілятор (англ. Compiler від англ. to compile - збирати в ціле) - комп'ютерна програма (або набір к. програм), що перетворює (компілює) вихідний код, написаний певною мовою програмування (мова джерела, англ. source language)

Студе́нт (лат. studens, родовий відмінок studentis - «ретельно працюючий», «такий, що займається») - учень вищого, у деяких країнах і середнього навчального закладу.

Мо́ва програмува́ння (англ. Programming language) - це штучна мова, створена для передачі команд машинам, зокрема комп'ютерам. Мови програмування використовуються для створення програм, котрі контролюють поведінку машин, та запису алгоритмів.


5. Перелік задач, які потрібно вирішити:

  • провести аналіз існуючих внутрішніх форм;

  • провести аналіз існуючих способів трансляції з процедурних мов програмування у функціональні;

  • розробити способи трансляції програм з процедурних мов програмування у функціональні мови з використанням графу залежності даних і стану в якості внутрішньої форми;

  • розробити програмне забезпечення, яке реалізує запропонований спосіб;

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

    Програмне забезпечення Програ́мне забезпе́чення (програ́мні за́соби) (ПЗ; англ. software) - сукупність програм системи обробки інформації і програмних документів, необхідних для експлуатації цих програм.



  • провести аналіз отриманих результатів.

6. Перелік обов’язкового ілюстративного матеріалу:



  • Алгоритм формування графу залежності записів;

  • Алгоритм формування графу залежності даних і стану;

  • Алгоритм генерації коду;

  • Загальна структура програмної системи;

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

    Матеріа́л - речовина, або суміш речовин, первинний предмет праці, який використовують для виготовлення виробу (основний матеріал), або які сприяють якимось діям. У останньому випадку уточнюють, що це допоміжний, чи витратний матеріал.

    Генерація - покоління, що представлене більш чи менш одноманітними особинами, які змінюються наступним поколінням, яке при диференціації життєвого циклу може істотно відрізнятися від попереднього. Наприклад: при чергуванні поколінь (гетерогонії, метагенезі) у тлі (Aphidoidea), галиць (Cecidomyiidae) та деяких інших комах.

    Програма (фр. programme письмове оголошення, порядок денний, від грец. prógramma вказівка) - заздалегідь затверджена (визначена) дія.



  • Результати ефективності способу трансляції;

  • Порівняльний аналіз способів трансляції.

7. Дата видачі завдання: “15” жовтня 2013 р.



КАЛЕНДАРНИЙ ПЛАН


з/п


Назва етапів виконання магістерської дисертації


Строк виконання етапів

Примітка

1.

Ґрунтовне ознайомлення з предметною галуззю

17.12.2013




2.

Визначення структури магістерської дисертації; вивчення літератури, пошук додаткової літератури, патентний пошук

05.03.2014




3.

Робота над першим розділом магістерської дисертації; проведення наукового дослідження

15.05.2014




4.

Проведення наукового дослідження; робота над другим

розділом магістерської дисертації; розроблення програмного забезпечення



15.10.2014




5.

Проведення наукового дослідження; робота над статтею за

результатами наукового дослідження



15.12.2014




6.

Проведення наукового дослідження; робота над третім

розділом магістерської дисертації; підготовка матеріалів

доповіді на конференції ПМК-2015


11.03.2015




7.

Завершення роботи над основною частиною

магістерської дисертації; підготовка ілюстративного матеріалу



15.05.2015




8.

Оформлення текстової і графічної частини магістерської дисертації

01.06.2015




9.

Попередній захист магістерської дисертації

03.06.2015






Студент _________ Хоптинець В.А.

Науковий керівник _____________ Марченко О.І.

2. ОПИС ЗАПРОПОНОВАНОГО СПОСОБУ ТРАНСЛЯЦІЇ
2.1 Граф залежності даних і стану
При реалізації транслятора, що має і на вході, і на виході мову програмування високого рівня (МВПР), перші етапи трансляції є такими самими, як і в класичних компіляторах – лексичний та синтаксичний аналіз.

Трансля́тор (англ. translator) - програма або технічний засіб, який виконує перетворення чи іншу обробку текстів програм.

Про́даж - це оплатна передача майна однією особою у власність іншій особі.

Лексика (від дав.-гр. τὸ λεξικόν - сукупність слів якоїсь мови чи діалекту та словниковий склад мови письменника чи художнього твору) - словниковий склад мови. Наука, яка вивчає словниковий склад, називається лексикологією.

Синтакси́чний ана́ліз (па́рсинг) (англ. parsing) - в інформатиці це процес аналізу вхідної послідовності символів, з метою розбору граматичної структури згідно із заданою формальною граматикою. Синтаксичний аналізатор (англ. parser)

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


Граф залежності даних і стану – функціональне представлення програми, що представляє потік виконання як потік даних та явно відображає всі сторонні ефекти, такі як запис у пам’ять [19].

Застосунок, застосовна програма або прикладна програма (англ. application, application software, app) - користувацька комп'ютерна програма, що дає змогу вирішувати конкретні прикладні задачі користувача.

Нитка (англ. thread) або повніше нитка виконання (англ. thread of execution), часто застосовується назва потік виконання) та англіцизм тред - в інформатиці так називається спосіб програми розділити себе на дві чи більше паралельні задачі.

Поті́к да́них (англ. data stream) в телекомунікаціях і програмуванні - це послідовність кодованих когерентних сигналів (пакетів даних) в цифровій формі, яка використовується, щоб передавати або отримати інформацію це знаходиться в передачі.

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


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

1. Примітивна операція. До цього типу відносяться арифметичні операції, константи тощо.

Константа (лат. constans - стала величина, інша назва - стала) - величина, що не змінює свого значення протягом певного процесу (на відміну від змінної, значення якої може змінюватись). Прикладами констант є число пі, коефіцієнти многочленів, температура під час ізотермічного процесу.

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

Арифме́тика (дав.-гр. ἀριϑμητική - мистецтво лічби, вчення про числа, від дав.-гр. αριθμός - число) - наука про числа, їх властивості й операції над ними.

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



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

3. Замикання ( ), що видає значення-функцію.

4. Виклик функції. Ці вершини приймають на вхід значення-функцію та параметри (що відповідають формальним параметрам вхідної функції).

Пара́метр (від дав.-гр. παραμετρέω) - відмірюю, розмірюю)(рос. параметр, англ. parameter, нім. Parameter m, Kennwert m, Kenngrösse f, Kennzahl f) - величина, що нею характеризують якусь властивість, стан, розмір або форму об'єкта, робочого тіла, процесу, явища або системи тощо.

Такі вершини повертають значення із вершини результату вхідної функції.


5. Формальний параметр. Ці вершини не мають входів, а на виході мають значення, що було передано у дану функцію через даний формальний параметр.

6. Вільна змінна. Такі вершини видають на вихід значення зі зовнішнього контексту.

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

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

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

Алгори́тм (латинізов. Algorithmi за араб. ім'ям узб. математика аль-Хорезмі) - набір інструкцій, які описують порядок дій виконавця, щоб досягти результату розв'язання задачі за скінченну кількість дій; система правил виконання дискретного процесу, яка досягає поставленої мети за скінченний час.

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

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



Вершина графу d домінує над вершиною n (записується як d = dom(n)), якщо кожен шлях від вхідної вершини графу до вершини n проходить через вершину d. Таким чином, кожна вершина домінує сама над собою.

Відповідно, вершина графу d постдомінє над вершиною n (записується як d = pdom(n)), якщо кожен шлях від вершини n до вихідної вершини графу проходить через вершину d. Таким чином, кожна вершина постдомінує сама над собою.

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

Існува́ння (від екзистенція) - центральне поняття екзистенціалізму, унікальна особистісна сутність людини, що втілює в собі духовну, психоемоційну неповторність особи.

Таким чином якщо d != n та d = dom(n), то d = dom(m). Це все справедливо і для постдомінаторів.

Справедливість - мораль та чеснота, вразливість як на суспільне добро, так і на суспільне зло. За Платоном, справедливість - це найвища чеснота, що утримує мужність, поміркованість та мудрість в повній рівновазі й гармонії («кожному своє»).


2.2 Алгоритм побудови внутрішньої форми
Побудова графу залежності даних і стану складається зі двох основних етапів:

1. Побудова графу залежності записів (store dependence graph – SDG).

2. Символьна інтерпретація SDG.

Інтерпретатор мови програмування (interpreter) - програма чи технічні засоби, необхідні для виконання інших програм, вид транслятора, який здійснює пооператорну (покомандну, построкову) обробку, перетворення у машинні коди та виконання програми або запиту (на відміну від компілятора, який транслює у машинні коди всю програму без її виконання).


Граф залежності записів має наступні типи вершин:

1. Блокові вершини. Такі вершини генерують нові значення запису із вхідних значень запису.

2. Умовні вершини. Генерують булеве значення в залежності від вхідного значення запису.

3. γ-вершини. Ці вершини видають одне з вхідних значень запису в залежності від умовного виразу (результат якого також подається на вхід).

4. Вершини вхідного та вихідного записів. Ці вершини відповідають значенням запису на вході і виході відповідної програми.

5. λ-вершини, що видають значення-функцію.

6. Виклик функції. Ці вершини приймають на вхід значення-функцію та параметри (що відповідають формальним параметрам вхідної функції). Такі вершини повертають значення із вершини результату вхідної функції.
Граф залежності записів можна отримати з графу потоку виконання наступним чином:

1. Базовий блок графу потоку виконання замінюється на відповідний базовий блок графу залежності записів.

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

Заміну слід виконувати з початкової вершини графу потоку виконання до кінцевої. Вхідна та вихідна вершини графу потоку виконання замінюються відповідно на вершини вхідного та вихідного записів.


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

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

4. Всі інші об’єднуючі вершини автоматично будуть оброблені при трансформації умовних вершин.
Щоб визначити, які саме об’єднуючі вершини потребують створення додаткових λ-вершин, а також визначити відповідні кінці розгалужень/об’єднань необхідно виконати аналіз одиничного входу та виходу (single-entry-single-exit – SESE analysis) [20]. SESE аналіз оперує наступними визначеннями.

Циклічна еквівалентність.

Логічна еквівалентність (еквіваленція) - двомісна логічна операція, що має значення «істина» тоді і тільки тоді, коли обидва операнди мають однакове значення. В інших випадках еквіваленція буде хибною.

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


SESE регіон. Вершини графу потоку виконання a і b обмежують SESE регіон тоді, і тільки тоді, коли існують дуги α, що входять у a і дуги β, що виходять із b, при чому α домінують над β, β постдомінують над α, а також α і β є циклічно-еквівалентними. Сам SESE регіон складається з вершин a і b, а також всіх вершин для яких a є домінатором, а b є постдомінатором.

SESE дно. Вершина b являється SESE дном, якщо для якоїсь вершини a, a і b обмежують SESE регіон.

Функція bottom. Функція bottom від довільної вершини a графу потоку виконання повертає постдомінатор найменшого SESE регіону, що містить вершину a.

SESE аналіз ставить у відповідність кожній умовній вершині вузол, що являється кінцем умови, а кожній об’єднуючій вершині – кінець об’єднання. Під час аналізу розглядається два випадки, коли поточна вершина являється SESE дном і коли ні. Якщо умовна вершина являється SESE дном, то кінцем розгалуження являється вершина-наступник, що не входить у поточній SESE регіон. Якщо об’єднуюча вершина є SESE дном, то сама ця вершина і є кінцем розгалуження. При визначенні відповідного кінця (розгалуження або об’єднання) для вершини n, що не є SESE дном, нехай z буде кінцем (розгалуження або об’єднання) для bottom(n). При цьому ми ігноруємо вершини, що містяться у вкладених SESE регіонах, тобто такі вершини a, для яких bottom(a) != bottom(n). Кінець розгалуження для умовної вершини n, що не є SESE дном являється найближчий постдомінатор, який є або об’єднуючою вершиною, або вершиною z. Кінець об’єднання для об’єднуючої вершини n, що не є SESE дном являється найближчий постдомінатор, який є або умовної вершиною, або z. SESE аналіз залежить лише від розміру дерев постдомінаторів і має лінійну складність [21].

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

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

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

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

В результаті даної перебудови внутрішні λ-вершини та відповідні їм вершини викликів лише відповідають циклам у вхідній програмі. Дана побудова називається λ-γ трансформацією.


λ-γ трансформації для даної λ-вершини складається з трьох кроків:

1. Будується проекція дерева залежності виконання для всіх викликів даної λ-вершини.

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

Предика́т (від лат. praedicare - проголошувати, заявляти, присуджувати) у сучасній логіці зазвичай означає булевозначну функцію P: X→ , яка називається предикатом на X. Однак, предикати мають багато різних інтерпретацій та способів використання у математиці та логіці, і їх точне визначення різниться від теорії до теорії.

В якості записів, що приймає новостворена γ-вершини використовуються записи, що входять у відповідні вершини викликів даної λ-вершини.


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

Автома́тика (грец. αύτόματος - самодіючий) - галузь науки і техніки, яка розробляє технічні засоби і методи для здійснення технологічних процесів без безпосередньої участі людини.

Збирання сміття (англ. garbage collection) - одна з форм автоматичного керування оперативною пам'яттю комп'ютера під час виконання програм. Підпрограма - «прибиральник сміття» - вивільняє пам'ять від об'єктів, які не будуть використовуватись програмою в подальшому.



Розглянемо у якості прикладу фрагмент графу потоку виконання, який зображено на рис.2.1. У гілці true умови q, після базового блоку s4 виконання передається на мітку, що відповідає базовому блоку s5. Граф залежності записів, що відповідає наведеному графу потоку виконання наведено на рис.2.2. Як видно з рисунку, було створено одну λ-вершину і дві вершини викликів, що їй відповідають.

Фрагмент (лат. fragmentum - уламок, шматок, скалка) - яка-небудь частина цілого.

Гра́фіка (нім. Graphik, грец. graphikos «написаний») - вид образотворчого мистецтва, для якого характерна перевага ліній і штрихів, використання контрастів білого і чорного та менше, ніж у живописі, використання кольору.

Виконанню без переходу відповідає виклик λ-вершини, в який передається запис після базового блоку s3, безумовному переходу відповідає виклик, в який передається запис після базового блоку s4. В даному випадку, можна замінити λ-вершину і обидва її виклики на одну додаткову γ-вершину. Ця вершина буде обирати який з записів необхідно передати на вхід базового блоку s5 – запис після виконання базового блоку s3 чи s4. Результуючий граф зображено на рис.2.3.

  1   2   3


Скачати 422.29 Kb.