Михайло Козлов
Введення
Стаття Андерсона [1], якому, мабуть, належить сама ідея схемної реалізації мови програмування високого рівня, з'явилася практично одночасно (1961р.) якщо не з зародженням цих мов (FORTRAN, 1949), то з виходом їх «на широку арену» (COBOL , 1959, ALGOL-60 як спроба «офіційної мови публікацій алгоритмів» і т.п.). У дійсності ж передісторія проблеми охоплює більші часові інтервали, а сама проблема глибше, ніж це може представитися на перший погляд. Невипадково суворе формулювання поняття алгоритму безпосередньо передувало появі перших обчислювальних машин. Очевидно, що цей факт є наслідком тісного зв'язку алгоритму з тим «суб'єктом», який цей алгоритм реалізує. Тому першим суворим визначенням алгоритму стало саме поняття машини (автомата) Тьюрінга (1936г.). На відміну від цієї суто математичної абстракції в основі переважної більшості коли-небудь створених досі комп'ютерів лежить більш багата деталями схема, яка є все-таки в тому чи іншому сенсі еквівалентним автомату Тьюрінга визначенням алгоритму - фон неймановскую архітектура обчислювальної машини (1945 р.), з якої безпосередньо пов'язано уявлення обчислювальних алгоритмів командними програмами.
Висновок, який можна зробити зі сказаного, полягає в якійсь нетривіальності взаємини між «хардом» і «софтом». При цьому використання алгоритмічного мови високого рівня можна розглядати як моделювання більш складної машини засобами простий, що відповідає звичайному поняттю про «мовному процесорі». Ясно, що така многоступенчатость робить комп'ютер більш загадковим і недоступним, ніж він представлявся спочатку, і чим він є насправді. Серед практичних спроб все ж таки «напоумити» і «олюднити хард» можна виділити отримали деяке поширення ЕОМ серії «Світ» (СРСР) [2, 3] зі схемної реалізацією алголоподобного вхідної мови і «Систему 432» фірми Intel [4], що є, мабуть, останнім за часом (80-і роки) експериментом в цьому напрямку. Проте в цілому, як очевидно, ці спроби не виявилися продуктивними.
Найбільш суттєві обмеження тут полягають у значному ускладненні пристрої мовної машини на всіх рівнях її функціональної схеми і помітне зниження її швидкодії в порівнянні з командним комп'ютером. При цьому також втрачається або значно слабшає одне з фундаментальних властивостей комп'ютера - його універсальність. Хоча на мовній машині в принципі можна реалізувати будь-який з існуючих алгоритмічних мов, своєрідна несумісність багатьох з них може породжувати значну неефективність роботи програми, написаної на "чужому" мовою. При цьому також загальна математична «незручність» алгоритму як абстрактного об'єкта взагалі і досить звичайна складність алгоритмічних проблем зокрема вже давно привели до відмови від думки про «універсальному» мовою програмування або іншому подібному інструментальному засобі, яке могло б бути однаково придатним і ефективним в рішенні будь-яких завдань, на схемну реалізацію якого було б не шкода витрачати зусилля.
Тим не менш, протягом всього періоду існування електронної обчислювальної техніки протікає процес накопичення практичного досвіду, одним з аспектів якого є триваюча відпрацювання і самого поняття алгоритму і природний розвиток спочатку штучно створеного «мови комп'ютера» у його різноманітних «діалектах». Тут можна виділити як один з яскравих ранніх (1968р.) прикладів принцип програмування без оператора переходу (go to) [5], ефективність якого пояснити і обгрунтувати було досить важко.
У початкових етапах розвитку обчислювальної техніки ситуація, коли набір командних кодів процесора змінювався паралельно з розробкою його математичного забезпечення була частою. Коди вводилися і вичищати із системи команд у відповідність з думкою програміста про їх необхідність або непотрібність. Масове поширення комп'ютерів і стандартизація «софтвера» зробило животрепетної проблему сумісності кодових таблиць і переносимості матзабезпечення, і оснащення чергового Pentium "додатковим набором графічних команд реалізується як довго готується акція,« ринкова »відповідальність якої непорівнянна з майже хуліганським за сьогоднішніми мірками ставленням до кодовою розділами полуунікальних ЕОМ 60-х років.
Те, що ми хочемо запропонувати в цій статті, можна розглядати в аналогії з згаданим графічним розширенням, у відношенні, однак, до «мовної» проблеми. При цьому відповідна дія не можна звести до простого розширення системи команд, так як воно тягне перебудову і реорганізацію основної функціональної схеми самого виконуючого ядра обчислювальної системи, хоча і зберігає значну частку спадкоємності по відношенню до сучасної. А саме, пропонується перехід на операторно-формульний код як якусь версію розширення командного представлення програми, з єдиною істотною особливістю: допущенням формульного подання аргументів оператора (команди або інструкції) програми.
Наступні обставини дозволяють вважати, що даний підхід може уявити реальний практичний інтерес.
Використовуване в якості внутрішнього коду представлення програми послідовністю операторів зі списками аргументів з одного боку, універсально близько практично будь-якому алгоритмическому мови, з іншого - при всій своїй «мовного» зберігає найбільшу подібність командного програмі з притаманною або приписується їй особливою гнучкістю.
Виконуючий пристрій для формульної програми за рівнем складності та швидкодії відповідає звичайному командному процесору, на відміну від відомих систем схемної реалізації мови високого рівня.
Трансляція будь-якого вхідного мови в формульний код істотно простіше трансляції в командний код, при цьому також значно спрощується будь-який контроль виконуваної програми (наприклад, при її налагодженні).
Відповідне символьне представлення алгоритму майже не містить специфічних елементів і дуже близько до поширеної общематематическими символіці. Операторно-формульний код, таким чином, має якусь "об'єктивну" основу, що знижує різноманітність можливих його варіантів, на противагу системам команд звичайних процесорів, різноманіття яких може бути приведене до деякого єдності лише більш-менш примусової або вимушеної стандартизацією.
Формульне ядро дозволяє найбільш природним чином обладнувати схему додатковими засобами апаратної підтримки мовних та інших інформаційно-логічних структур.
Алгоритмічні формули
Основним видом елементів практично будь-якої мови високого рівня є оператор або функція в наступному записі:
ім'я оператора або функції (аргумент1 ,..., аргументn).
Інструкція (команда) машинного мови найчастіше виглядає приблизно так:
код команди | операнд1 | операнд2.
Як бачимо, в найбільш узагальненій формі ці конструкції досить подібні. Найбільше відмінність полягає в тому, що аргументи оператора можуть являти собою формульні вирази, що включають в себе безліч змінних, знаків операцій, дужок і ідентифікаторів функцій, в той час як операнди команди можуть бути лише індивідуальними адресними посиланнями на клітинки оперативної пам'яті. Але саме наявність формул в мові становить саму «неприємну», якщо не складну для обробки складову частину символьної програми, тому що при їх трансляції порушується природне лінійне відповідність між командами об'єктної програми і лінгвістичними конструкціями вихідного запису алгоритму.
Тепер ми можемо уявити, що елементами формули є ті ж адресні посилання на елементи пам'яті, відповідні змінним, коди операцій, дужок та інших символьних обмежувачів, а також посилання на підпрограми-функції, аналогічні тим, які використовуються в командах переривання на підпрограму. Таким чином, в ролі окремого елемента (псевдокоманди) такий "формульної" програми виступить практично той же символ (змінна, код (ім'я) оператора, код операції, символ-обмежувач, код (ім'я) підпрограми-функції й т.д.), що і в мові високого рівня. При цьому однак, ці елементи функціонально повинні бути пов'язані тісніше, ніж команди звичайної програми, і найменшій замкнутої виконуваної (так би мовити, «з результатом») одиницею з'явиться все-таки цілісний оператор, складність будови якого в принципі обмежена лише ресурсом оперативної пам'яті.
Як відомо [6], «найменший» універсальна мова може бути зведений до простих змінним, операторам присвоювання і операторам умовного і безумовного переходу. Цей набір відповідає мові логічних схем Ляпунова - Янова (ЯЛС) [7 ... 9], що є однією з ранніх математичних моделей мови програмування високого рівня. Зазначимо, що перші з отримали найбільше поширення мов високого рівня (FORTRAN, COBOL, ALGOL ...) були далеко не мінімальні за складом своїх образотворчих засобів і при цьому значно відрізнялися один від одного. Проте з плином часу сформувалося досить певне ядро з набору операторів, систематично відтворюються в більшості сучасних мов.
Таблиця 1
Відповідність операторно-формульного подання алгоритму операторам мови BASIC
Символ і його назва | Оператори BASIC | |
(F) | завантаження контексту | SELECT CASE f |
(X, f) | присвоєння (завантаження) | x = f |
(X, f, ..., g) | циклічна завантаження | - |
└ (M) | відсилаючи полускобка Янова | GOTO M |
└ (t, M) | умовна полускобка Янова | IF t THEN GOTO M |
┘ (M) | приймаюча полускобка Янова | M: |
[(T) | відкриває умовна дужка | IF t THEN |
] [ | else-дужка | ELSE |
] | закриває умовна дужка | END IF |
{ | відкриває циклова дужка | DO |
{(T) | відкриває циклова дужка | WHILE t |
{(N) | відкриває циклова дужка | FOR loop = 1 TO n |
{(M, k) | відкриває циклова дужка | FOR loop = M TO k |
{(M, k, l) | відкриває циклова дужка | FOR loop = M TO k STEP l |
} | закриває циклова дужка | NEXT або LOOP |
} (T) | закриває циклова дужка | WHILE t |
C [ | контекстна відкриває умовна дужка (при логічному, арифметичному або строковому контексті) | CASE -1, |
CASE IS0 або | ||
CASE IS "" | ||
C [(g) | контекстна відкриває у.с. | CASE g |
E [ | контекстна else-дужка | CASE ELSE |
Тут t - логічне вираження; n - ціле невід'ємне вираз; m, k, l - арифметичні (тобто цілі або речові) вираження; s - строкове; f, g - довільні вирази; x - змінна, M - мітка.
Алгоритмічні формули (АФ; табл.1, рис.1) представляють собою формальну систему, що є розвитком ЯЛС допомогою включення в нього конструкцій, адекватних згаданому мовною ядра. Головним фактом, що лежить в основі цього формалізму, є можливість розглядати основні елімінатор оператора переходу - умовні оператори, оператори вибору та оператори організації циклу, - як особливі (операторні) дужки, в принципі аналогічні звичайним за своїми властивостями і функцій. Відповідно до цього «програма» розглядається як дужкових виразів (рядок), структура якого оформляється трьома видами дужок: алгебраїчними (круглими), умовними (прямими) та цикловими (фігурними).
Рис. 1. Алгоритм Евкліда знаходження найбільшого спільного дільника в поданні різними мовами програмування: I - мовою логічних схем (Ляпунов, Янов, 1958), II - на одному з найбільш поширених мов програмування (BASIC) в «старій» (A) і «новою» ( B) нотації, III - у вигляді алгоритмічної формули, адекватної кодом формульного процесора
Елементом алгоритмічної формули є оператор, що складається з імені оператора та списку аргументів, укладеного в алгебраїчні дужки. Алгоритмічна формула (див. рис.1) є послідовністю операторів, що відділяються один від одного знаком-роздільником (крапка з комою). Основу формалізму складають оператор збереження значення (присвоювання) і оператори-дужки, іменами яких служать символи фігурних (циклових) або квадратних (оператори умов і вибору) дужок. Умовні та циклові дужки аналогічні відповідним операторам більшості поширених мов (табл.1 і рис.1). Наприклад, що відкриває прямий дужка в якості імені оператора, з логічним умовою в якості єдиного аргументу, і парний їй оператор закриває дужки, що не має аргументів, обмежують підпослідовність операторів, виконуються, якщо виконано дане логічне умова. Подібні парні оператори, іменами яких є символи дужок, обмежують підрядок, що виконує кратне число разів, заданий значенням параметра циклу, або в залежності від виконання відповідного логічного умови. Оператор присвоювання є безіменним, традиційна запис x: = F (y1 ,..., yn) відповідає оператору (x, F (y1 ,..., yn)). Безліч всіх інших («іменованих») операторів, набори функцій і відносин, як і допустимі класи змінних чи інші обмежувальні символи, можуть бути в тій чи іншій мірі специфічними.
Таким чином, алгоритмічна формула відрізняється від ЯЛС головним чином в тому відношенні, що, з одного боку, найбільш послідовно проводиться принцип лінеаризації запису алгоритму з повністю уніфікованим операторних поданням його елементів, з іншого - у відповідності зі сформованою практикою в формалізм введено найбільш поширені засоби елімінації операторів переходу (оператори-дужки).
У алгоритмічних формулах легко вбачається природний розвиток звичайної функціонально-алгебраїчної символіки. Вже при обчисленні найпростіших виразів виникає необхідність зберігати проміжні результати. У звичайних (алгебраїчних або арифметичних) формулах цей процес однозначний. Більш загальна ситуація вимагає явного введення осередків-змінних. Подібним чином, оператори-дужки є лише узагальненням алгебраїчних, що визначають послідовність дій з вхідними в вираз об'єктами. У зв'язку з цим ми вважаємо за можливе розглядати АФ як розширення общематематическими семіотики, а не як мова програмування або його математичну модель. Тому ми вважаємо також допустимими будь-які можливі розширення (клони) цієї мови, як завгодно своєрідні в залежності від контексту різних сфер його застосування. Зокрема, у відповідних ситуаціях, легко уявити застосування у складі АФ будь-якої відомої общематематическими символіки - кванторів, похідних, інтегралів, - і т.п., аби при цьому формула залишалася «зрозумілою» в тій же, наприклад, настільки, наскільки зрозуміло доказ будь-якого математичного твердження, як правило не доводимое до рівня досконалої формально-логічної строгості. У цьому ракурсі і сам ЯЛС можна трактувати як окремий випадок або клон АФ.
Можна було б окремо розглянути питання про мінімальності набору власних символів АФ: по суті достатня лише один різновид операторних дужок - циклові, з блокуванням тіла циклу при нульовому значенні числа повторень. Навіть логіко-алгебраїчні формули для АФ-термів в якомусь сенсі є розширенням мови, можна було б обійтися і чисто функціональної записом виразів. Однак очевидно, що у відповідність із загальними тенденціями розвитку мінімальність набору безпосередньо виконуваних процесором операцій ні в якому відношенні не є метою, фактично в якості такої виступають досить важко і повільно виробляються інші критерії оптимальності цього набору. Представлений підхід полягає в тому, що сутністю АФ оголошується общематематическими сенс деяких специфічно програмістських за походженням символів - привласнення і операторних дужок. Їх використання може бути уподібнено практику застосування формально-логічних за походженням знаків кванторів або функціональних символів інтегрування і диференціювання. Конкретизація («локалізація») відповідного формалізму в чітко визначений перелік або алгоритмічний код так чи інакше повинна бути прив'язана до контексту ситуації і в загальному вигляді не виробляється, як вона не виробляється і для наведених аналогічних об'єктів.
У алгебраїчної інтерпретації [6, 10] нормальна (без полускобок Янова) алгоритмічна формула - це вільна конструкція над алгеброю функцій внутрішніх станів (ПС) якогось автоматичного пристрою (АУ) і тим чи іншим безліччю іменованих операторів, виділене підмножина яких характеризується як «дії» АУ, а інші виступають у ролі викликів підпрограм (тобто, в кінцевому рахунку, як скорочення). При цьому, при «виконанні» АФ, з неї видаляються всі внутрішні змінні і оператори перетворення внутрішнього стану (елімінація ВС), а аргументи залишаються в результуючої рядку іменованих операторів-дій отримують визначається значення. Таким чином, АФ як формальний об'єкт грає роль шаблону, за яким, при заданому векторі умов, за певними правилами, обчислюється вихідна рядок дій АУ.
Синтаксична правильність АФ складається з правильності будови термів і операторів, дотримання парності входять до неї дужкових операторів і правильності чергування умовних і циклових дужок. Семантична правильність вельми природно визначається як елімініруемость ЗС на елементах обумовленого підмножини допустимих варіантів вхідного файлу. Семантично тотожні на даному безлічі вхідних умов формули породжують на ньому ідентичні послідовності дій, вибір підмножини дій серед операторів, таким чином, зумовлює це відношення.
Операторно-формульна запис алгоритму, на відміну від мовного або командного, найбільш зручна як для дослідження, так і машинного аналізу, генерації й оптимізації програмного коду. Вона також найбільш природно («обчислювальний») представляє об'єкти алгоритмічної природи, подібні програмами, що суттєво, якщо мова йде про можливість формування нового стандарту внутрішнього представлення програм. Більше того, ми вважаємо, що формульна запис, поряд із загальноприйнятими рекурсивними функціями, автоматом Тюринга або алгорифм Маркова, найбільш придатна виступати в ролі «програмною» версії визначення алгоритму взагалі. Мова програмування як технічний об'єкт в АФ редукується практично повністю, зводячись лише до декількох символів і правил общематематическими характеру, причому це не супроводжується введенням будь-яких специфічних об'єктів або знаків, таких, як мітки передачі управління.
Формульний процесор
Головною характеристикою АФ, як ми вважаємо, є можливість побудови для них виконуючого пристрою - процесора з формульної архітектурою ([11], рис.2), - за рівнем складності та швидкодії порівнянного з існуючими командними процесорами. Це істотно відрізняє даний процесор від будь-якої відомої системи схемної реалізації, для яких характерне багаторівневе ускладнення логіки виконуючою системи з включенням в неї безлічі додаткових регістрів (іноді настільки специфічних, як, наприклад, лічильники дужок), зв'язків, логічних схем, прошитих в ПЗУ програмних модулів , фактично інтерпретують в кінцевому рахунку оператори вхідної мови і т.д. і т.п. На відміну від цього, базова ідея формульної архітектури може бути відображена в одній фразі: для організації прямого виконання операторно-формульного коду програми в код виконуваної команди включаються прапори декларованого стану завантаження ряду регістрів місцевої (внутріпроцессорной) пам'яті. Такий спрощує підхід до виконавчій системі відповідає більш адекватному розподілу функцій між нею і системами транслюють або інтерпретують. Більш сильна підгонка схеми під ту чи іншу мову або інструментальне засіб на сьогоднішній день виглядає недоцільною. У разі формульного процесора всі програмні засоби залишаються в рівному положенні по відношенню до виконуючої системі, а транслює фаза хоча й помітно спрощується, все ж таки зберігається як така, зберігаючи разом з собою і природну можливість використання найхимерніших прийомів програмування і керуючих протоколів.
Рис. 2. Можлива функціональна схема формульного процесора Головною ідеєю, що лежить в основі формульного процесора є включення прапорів стану завантаження регістрів місцевої (внутріпроцессорной) пам'яті в код виконуваної команди для організації прямого обчислення формульних виразів. Прапори завантаження складають частину бітів регістра формувача-дешифратора коду команди управління. Іншу його частину становлять ознаки коду черговий псевдокоманди, що представляє той чи інший символ операторно-формульного коду. Рис. 3. Структура псевдокоманди формульного процесора Програма-емулятор формульного процесора представляє собою інформаційно-логічну модель, що реалізує приклад системи кодів псевдокоманди і тактовою схеми процесора. Псевдокоманди - структурні обмежувачі є однобайтовим кодами символів-обмежувачів алгоритмічних формул (знаки арифметико-логічних операцій, дужки, знаки-роздільники, коди виділених операторів). Адресно-літеральние псевдокоманди складаються з однобайтное коду-визначника, що описує формат і спосіб адресації даного, і самого цього даного або відповідної адресної посилання. В адресній формі вони можуть задавати початковий адресу як операнда, так і підпрограми-оператора або підпрограми-функції. Внутрішнє двійкове подання формульного коду нагадує одноадресних систему команд. Кожна окрема псевдокоманди (елементарна інструкція) відповідає одному символу операторно-формульного коду і складається з поля-визначника, що містить код-визначник, подібний коду операції, і, можливо, єдиного поля операнда (рис.3). Псевдокоманди поділяються на адресно-літеральние та структурні обмежувачі, що не містять поля операнда. Структурні обмежувачі виконують роль символів-обмежувачів (знаки операцій, дужки, знаки-роздільники, привілейовані оператори), а адресно-літеральние псевдокоманди відповідають константам, змінним або іменам операторів і функцій, тобто складають код оператора або функції. При цьому полі операнда адресно-літеральної псевдокоманди може містити безпосередньо операнд арифметико-логічної операції, або адресну посилання того чи іншого виду на такий операнд або на підпрограму, що відповідає оператору або функції. У цих псевдокоманди полі-визначник задає формат операнда і спосіб його адресації. Приклад можливої системи команд формульного процесора і тактовою схеми їх виконання був протестований на реалізація в програмі-емуляторі (табл.2 представляє частину відповідної кодової таблиці). Таблиця 2 Структурні обмежувачі
|