Схема програми
Схема програми
Схеми програм — це формалізми, які призначені для опису синтаксису та семантики програм (далі будемо скорочено називати їх СхП). Тому вони широко використовуються при проектуванні програм. При такому підході останні виступають як інтерпретовані схеми програм. Для інтерпретації схеми програм необхідно вибрати предметну область і задати на ній значення функціональних та предикатних символів схеми. Відомо багато класів СхП, тому тут ми обмежимося тільки загальним їх оглядом. Початок теорії схем програм поклали радянські вчені О. А. Ляпунов, Л. А. Калужнін, Ю. І. Янов, А. П. Єршов та інші. Сам схемний підхід до опису програм започаткував О. А. Ляпунов (операторні схеми). Він полягає у співставленні програмам певного їх абстрактного синтаксичного зображення - схеми програми, яка в тій чи іншій мірі відтворює їхню семантичну структуру і в якій конкретні елементарні операції та предикати замінені на не інтерпретовані функціональні та предикатні символи певної базової сигнатури.
Відправним поняттям теорії схем програм є поняття функціональної еквівалентності. Дві схеми функціонально еквівалентні, якщо для будь-якої інтерпретації відповідні програми обчислюють однакові функції. Кожному виконанню програми можна зіставити егопротокол - особливого роду терм в сигнатурі базових операцій, що відображає порядок їх виконання. Якщо звести значення істинності предикатів, що входять в програму, то протокол за цими значеннями будується однозначно, при цьому для побудови не потрібно знати інтерпретації базових операцій. Якщо вибирати значення істинності предикатів довільно, то в результаті для схеми програми створюється деяка множина формальних протоколів, зване детермінантою. Дві схеми формально еквівалентні, якщо їх детермінанти збігаються. Формальна еквівалентність коректна, якщо з неї слідує функціональна еквівалентність. Оскільки детермінант будується чисто комбінаторно на основі довільного вибору з кінцевої множини, він утворює формальну мова, що сприймається деяким автоматом. Становлять особливий інтерес такі визначення протоколу схем програм, які призводять до разрешиких детерминантах. Для таких детермінантів можна ставити питання про пошук системи преобразованій схем програм, повної в тому сенсі, що будь-які дві формально еквівалентні схеми перетвореними одна в іншу цими перетвореннями.
Структура теорії схем програм склалася на базі основоположних робіт О. А. Ляпунова та Ю. І. Янова. Для загальної моделі операторних схем функціональна еквівалентність виявилася нерозв'язною, однак вдалося знайти форму протоколу – логіко-термальну історію, яка призводить до вирішуваного детермінанту. Цей протокол фіксує послідовність виконання та значення предикатів схеми, а для кожного аргументу предиката вказує функціональний терм, який обчислював значення цього аргумента при виконанні програми. Автоматом, що сприймає детермінант, є двухленточний кінцевий автомат. Для логіко-термальної формальної еквівалентності також знайдена повна система перетворень. Істотне місце в теорії схем програм займають питання перекладу схем програм з одної чтслової моделі в іншу. Операторні схеми ефективно переводяться в рекурсивні схеми в сигнатурі, проте зворотна трансляція неможлива, тому що виконання рекурсивної програми вимагає, взагалі кажучи, як завгодно великого числа елементів пам'яті. Детермінант рекурсивної схеми може бути заданий у вигляді контекстно-вільного мови, однак питання про можливість розв'язання відповідної формальної еквівалентності залишається відкритим. Теорія схем програм займається також вивченням окремих класів схем програм з метою відокремити випадки вирішуваних еквівалентностей, вона також збагачує базову обчислювальну модель додатковими конструкціями мов програмування, вивчаючи при цьому виразну силу збагачень і питання збіжності.
За подання СхП поділяються на графічні та вербальні (словесні у вигляді різного виду термів), а класифікуються за типом їх базової сигнатури, за засобами іменування даних та за типом композицій, які описують семантичні програмні структури. Виділяюють два основних типи СхП: унарні та загальні. Загальні СхП спираються на модель іменованих даних, збагачених засобами для подання структурованих даних (масивів, стеків тощо), а композиції ті ж, що і у випадку унарних СхП. Це граф-схеми Калужніна [2], операторі схеми Єршова [2], стандартні схеми програм [2], загальні ССП та загальні рекурсивні схеми, схеми з масивами[2] тощо.
Схеми Янова – схеми програм, які були введені в літературу О. А. Ляпуновим і Ю. І. Яновим в 1958 р [1][2].
Для схем Янова проблема еквівалентності розв'язна і побудована повна система еквівалентних перетворень — система перетворень, що зберігають еквівалентність, Повна в тому сенсі, що будь-яку пару еквівалентних схем можна трансформувати одна в одну послідовним застосуванням цих перетворень.
Унарні СхП відповідають рівню абстрактних неструктурованих предметних областей і розподіляються на регулярні та рекурсивні. До регулярних належать:
- функціональні терми САА та РАА.
- унарні стандартні схеми.
- структурні блок-схеми та їхній вербальний еквівалент - структурні схеми програм.
Структурні блок-схеми (СБС) є спеціальними графами на площині з трьома типами вершин – прямокутними, ромбічними та еліпсоїдними. Ці графи мають по одній вхідній і вихідній стрілці й побудовані за допомогою композицій множення, розгалуження та ітерації [5].
Стандартна СхП — це схема програм з пам'яттю. Дослідження стандартних схем становить основний зміст загальної теорії схем програм. На відміну від інших видів схем стандартні схеми враховують розбиття пам'яті на змінні і дозволяють досліджувати більш широкий клас перетворень програм. Однак при цьому стандартні схеми забороняють структурність змінних Кожен оператор в такій схемі є або перетворювачем-оператором, що змінює стан пам'яті, або розпізнавачем-оператором, що здійснює вибір для виконання одного з кількох своїх наступників. Перетворювач має одну вихідну дугу, а розпізнавач - дві вихідні дуги, одна з яких називається плюс-стрілкою (або 1-дугою), а друга — мінус-стрілкою (або 0-дугою). Кожному з розпізнавачів при інтерпретації зіставляється деякий предикатний терм, а перетворювачам - оператор присвоєння, що має вигляд: y := t, де y — символ змінної, а t — функціональний терм. Сукупність всіх змінних у схемі утворюють її пам'ять.
Графічно стандартна схема може задаватися у вигляді кінцевого орієнтованого графа переходів, що має зазвичай одну вхідну і одну вихідну вершини.
Програма виконується рухом по графу переходів: 1) при попаданні на розпізнавач обчислюється предикатний терм і відбувається перехід по дузі, що відповідає значенням предиката;та 2) при попаданні на перетворювач y := t обчислюється значення t і присвоюється змінній х і здійснюється перехід за його стрілкою. Результат виконання програми — стан пам'яті при попаданні у вихідну вершину.
Рекурсивні схеми відповідають схемам індуктивних означень систем функцій. Індуктивно означені функції (ІОФ) визначаються на індуктивно означених областях. Необхідно, щоб кожний елемент області визначення можна було розкласти на близькі до нього один або кілька елементів того самого чи іншого типу. Наприклад, число розкладається на числа n та 1. ІОФ теж має базу індукції (БФ), індуктивний перехід (ІФ) і повноту (ПФ) [5].
Дізнатися:
- чи буде довільна СхП даного класу при будь-якій інтерпретації працювати нескінченно (проблема пустоти)
- чи дають дві довільні СхП даного класу при будь-якій інтерпретації однаковий результат (проблема функціональної еквівалентності)
- чи є довільна СхП даного класу тотальною.
Усі ці проблеми алгоритмічно розв'язні для унарних нерекурсивних СхП та деяких підкласів унарних рекурсивних. Для стандартних схем програм вони алгоритмічно нерозв'язні.
Одна з важливих проблем теорії схем програм - пошук тих чи інших класів еквівалентних перетворень СхП (перетворень, які зберігають семантичну рівність) та повної сукупності таких перетворень. Остання вирішена для схем Янова та деяких класів САА. Спеціальні еквівалентні перетворення СхП лежать в основі трансформаційного програмування, деяких оптимізаційних перетворень (задача економії пам’яті) тощо [3][4].
- [1] Ляпунов А. А. О логических схемах программ / Проблемы кибернетики: Сб. статей. Вып. 1. – М.: Физматгаз, 1958. – С. 46 – 74.
- [2] Янов Ю. И. О логических схемах алгоритмов / Проблемы кибернетики: Сб. статей. Вып. 1. – М.: Физматгаз, 1958. – С. 75 – 127.
- [3] Ершов А. П. Введение в теоретическое программирование. — М.: Наука, 1977.
- [4] Котов В.Е., Сабельфельд В.К. Теорія схем програм / Москва «Наука», 1991. - 248 с.
- [5] Зубенко В. В., Омельчук Л.Л. Програмування: Навчальний посібник / ВПЦ «Київський університет», 2011. - 625 с.
 | На цю статтю не посилаються інші статті Вікіпедії. Будь ласка розставте посилання відповідно до прийнятих рекомендацій. |