В настоящее время современный рынок труда испытывает острую нехватку специалистов, способных решать насущные информационные проблемы наиболее эффективными и экономичными методами, в том числе с использованием декларативных или неалгоритмических языков программирования. Следовательно, научные работы, которые направлены на исследование проблем изучения декларативных языков программирования и путей их решения, остаются актуальными [1]. Наиболее актуальны на данный момент методы и инструменты программирования, которые позволяют прогнозировать будущие тенденции развития технологий [2]. Язык программирования Prolog используется при решении большого класса задач, связанных с разработкой систем искусственного интеллекта, который используется для обработки естественного языка и имеет обширные возможности, позволяющие обрабатывать информацию из баз данных [3].
Основное назначение генератора объектного кода – развертывание и обработка последовательности атомов, построенных синтаксическим анализатором в последовательность машинных команд. Многие детали генератора кода зависят от окружения, в котором он работает, а также от машины, для которой порождается объектный код.
Цель работы – выявление наиболее эффективных способов решения задач с применением генератора объектного кода средствами языка логического программирования Prolog.
Материалы и методы исследования
В данной работе применялись теоретический метод (анализ научной, учебно-методической литературы по вопросам исследования), методы обобщения, систематизации знаний, тестирования программы, анализ хода ее выполнения.
Результаты исследования и их обсуждение
Информация для человека играет немаловажную роль, поэтому основной из задач человечества является обработка данной информации и упорядочивание [4]. База знаний логического языка Prolog представляет собой предикатную модель фрагмента предметной области – совокупность правил и фактов, которыми декларируется решение задачи [5]. Мониторинг научно-исследовательских работ позволяет находить и создавать новые решения для упрощения и автоматизации процессов разработки [6].
Структура генератора кода представляется следующими блоками: блок моделирования исполнения, блок распределения памяти, элементы таблиц, процедура генерации кода, блок управления сумматором. В состав генератора входит набор процедур генерации ассемблерных или машинных команд.
Блок моделирования исполнения определяет процедуру вычисления выражений, в частности, для выражения (А + В) + (Х + Y), что представляет собой очевидный способ его вычисления, с точки зрения машинного языка представлен на рис.1. Каждому из трех сложений предшествует своя последовательность команд загрузки и записи.
Для создания данного кода генератор кода хранит некоторую информацию о том, что произойдет во время выполнения сгенерированного им кода. Работа по хранению этой информации называется моделированием производительности. Модель, задаваемая на языке ПРОЛОГ, должна быть корректной, иначе получаются неверные следствия, выводы [7].
Блок распределения памяти отвечает за организацию памяти машины во время выполнения скомпилированной программы. Один из способов представления распределения памяти показан на рис. 2.
Рис. 1. Процедура вычисления (А + В) + (Х + Y)
Рис. 2. Способ представления распределения памяти
С каждой из областей связывается переменная периода исполнения, которые являются указателями на очередную свободную ячейку памяти соответствующей ей области. Если значение переменной равно нулю, то переменная в данный момент находится в сумматоре.
Элементы таблиц содержат элементы о параметрах атомов. С целью оптимизации программного кода табличные элементы представляются с помощью двоичных справочников. Табличные элементы формируются на этапе лексического и синтаксического анализа.
Процедура поиска элемента таблиц может быть описана следующими отношениями:
lookup(Key,dict(X,Left,Right),Value):- !,
X=Value.
lookup(Key,dict(X,Left,Right),Value):-
Key<Key_1, lookup(Key,Left,Value);
Key>Key_1, lookup((Key,Right,Value).
Поиск осуществляется по ключу Key (поле «Вид»). Значением Value (поле «Значение» или «Адрес») может быть целочисленная или вещественная величина или адрес идентификатора исходной программы, адрес именованной метки. Двоичный справочник dict(Key, X, Left, Right) упорядочен в лексикографическом порядке имен.
Блок управления сумматором следит за содержимым сумматора в период исполнения программы. Для его функционирования используется переменная периода компиляции, которая содержит информацию о текущем состоянии сумматора. Он также используется для генерации команд запоминания, обновляя одновременно информацию о соответствующем табличном элементе. Если сумматор не занят, значение переменной равно нулю. Если сумматор занят, то он содержит указатель на табличный элемент, который соответствует промежуточному результату. Генератор кода взаимодействует с блоком управления сумматором через набор процедур.
Процедуры для атомов. Множество атомов определяется набором ключевых слов и операций исходного языка. В генераторе кода должен присутствовать вектор начального перехода, использующий имя входного атома для перехода к процедуре, обрабатывающий этот атом. Если установлен флаг ошибки, генерация кода прекращается. Управление передается предыдущим анализаторам.
Составление программы для решения простой вычислительной задачи на языке Prolog потребует освоения особого подхода, связанного со спецификой логического программирования [8]. Концепция выполнения программы неразрывно связана с формальным определением программ [9]. В предлагаемой статье рассматриваются атомы для вычисления арифметических операций, например addition (p, q, r) – сложение, subtraction (p, q, r) – вычитание, multiplication (p, q, r) – умножение, division (p, q, r) – деление. Здесь p, q, r – соответственно левый, правый операнды и результат операции.
Обобщенный алгоритм функционирования процедур следующий:
if(Address(p) = 0) then
{
// p левый операнд в сумматоре
// сумматор использован
gen(op, q); // op – операция, q – правый
операнд, результат в сумматоре
load(q); // сохранение результата
}
else (Address(q)=0) then
{
// q правый операнд в сумматоре
// сумматор использован
gen_ reverse (op, p); // gen_ reverse – обратная
операция
load(p); // сохранение результата
}
Основное отношение, моделирующее генератор объектного кода, описывается выражением encode:
encode(Structure, Dictionary, Code), где:
− Structure – дерево вывода арифметического выражения, построенного синтаксическим анализатором;
− Dictionary – словарь идентификаторов и меток;
− Code – объектный код, который представляет собой процедуру, содержащую ассемблерный код некоторой машины, выполняющей действие, предписанное данной операцией.
При разработке генератора объектного кода набор процедур, выполняющих арифметические действия (суммирование, вычитание и т.д.), операции загрузки, передачи управления, готовится заранее. Эти процедуры должны учитывать семантику своих аргументов. В частности, аргумент может быть целочисленным или вещественным (константой) или же идентификатором. Анализ построенных и апробированных процедур динамической генерации состояний и генерации фактов позволяет говорить о применимости такого решения для определенных прикладных задач [10].
Оптимизация одного атома. Некоторые простые виды оптимизации можно осуществить, выясняя для каждого атома, образуют ли значения его параметров один из выделенных частных случаев, позволяющих генерировать более эффективный код. Например, можно посмотреть, не окажется ли один из операндов атома сложения константой, равной нулю. Это возможно, когда оба операнда – константы, тогда сложение можно выполнить в период компиляции, и генерировать код также не требуется.
Другой пример – возведение в степень, равную некоторой небольшой константе. Например, для возведений в квадрат проще сгенерировать код умножения вместо генерации вызова функции возведения в степень.
Иногда система команд машины имеет команды, используемые только в специальных случаях, например запись нуля в ячейку памяти.
Оптимизация фиксированной цепочки атомов. В некоторых случаях возможности для оптимизации можно выделить, исследуя некоторое фиксированное число последовательных атомов, называемых «окном». Пусть в грамматике языка имеется правило [6]:
<operator> -> if(<logical_expression>) then <operator>
Соответствующее правило атрибутной транслирующей грамматики, используемой в синтаксическом анализаторе, может иметь вид
<operator> – > if(<logical_expression>)R1 then
{ crossing_the_lie R2,L1} <operator>
{label L2}
(L1,L2) <- NewAtom (R2 <- R1)
Процедура NewAtom дает указатель на новый табличный элемент для метки.
Если за then следует оператор перехода, то такому условному оператору может соответствовать типичная цепочка атомов:
transition_in_default (39,62) transition (92) label (62)
Эту цепочку атомов можно заменить более эффективной цепочкой:
transition_in_truth (39,92).
Оптимизация одного оператора. Переупорядочение выражений. Часто возможно генерировать более эффективный код для вычисления арифметических выражений, если использовать порядок вычислений, отличный от порядков атомов, соответствующий польскому переводу исходного выражения. Допустим, имеется выражение A*B-C*D. Если выполнять команды в соответствии с порядком польской записи, то объектный код будет состоять из восьми команд. Однако если выражение переупорядочить таким образом, чтобы C*D вычислялось раньше, чем A*B, то количество команд сократится до шести.
Вызовы процедур. Имеется возможность сокращения времени выполнения процедур (функций), вызываемых внутри оператора. Во многих императивных языках имеются Inline-функции, подставляемые в точку вызова. Время выполнения существенно снижается, однако растет объем памяти, занимаемый программой.
Комбинирование переходов. Во многих практических приложениях используются условные и безусловные переходы на метку, а первый атом после нее – это переход на некоторую другую метку. В этом случае первый переход можно заменить переходом на вторую метку. Например, имеется выражение
if(x>y) z = q else goto L;
Условный переход в случае x = <y можно адресовать непосредственно метке L, а код для оператора goto L генерировать не нужно.
Оптимизация нескольких операторов. Общие подвыражения. Общим подвыражением называется такое подвыражение, которое встречается в программе более одного раза. Например, (A+B)*C+D/(A+B),
Здесь сложение A+B достаточно выполнить только один раз.
Общие подвыражения часто используются при вычислении адресов индексированных переменных, например, в операторе
arr_1(i,j) = arr_1(i,j)+arr_2(i,j);
адрес переменной arr_1(i,j) достаточно вычислить один раз.
Выполнение константных действий. Операции над константами можно выполнить на этапе компиляции, не откладывая их до периода исполнения программы. Во многих случаях результаты таких операций можно распространить по нескольким операторам. Например,
int a = 1;
int b = 2;
int c = a+b;
сложение в третьем операторе можно выполнить на этапе компиляции, а сам оператор заменить более эффективным
int c = 3;
Распространение констант очень часто используется при вычислении адресов индексированных переменных, в тех случаях, когда значения индексов можно определить на этапе компиляции.
Оптимизация циклов. Вынесение кода или чистка цикла. Во многих случаях часть кода можно вынести так, чтобы она исполнялась перед выполнением цикла. Например, если в теле цикла используется подвыражение A*B, причем A и B не изменяют своих значений в пределах цикла, то это произведение можно вычислить один раз перед входом в цикл, а в теле цикла использовать результат.
Расчленение циклов. В некоторых случаях цикл можно разбить на два цикла, из которых будет выполняться только один. Это позволит вынести из тела основного цикла многие операторы, существенно сократив время выполнения и машинные ресурсы.
Уменьшение силы операции. Преобразования касаются замены одной операции другой, выполняемой быстрее. Например, в некоторых случаях возможно использование операции сложения вместо операции умножения.
Развертывание цикла. Развертывание цикла означает уменьшение числа повторений цикла за счет выполнения вычислений, соответствующих двум повторениям старого цикла. Данное преобразование уменьшает число проверок переменных цикла.
Линеаризация массивов. Линеаризация n-мерного массива означает, что компилятор генерирует код так, как если бы массив был одномерным. Например, двумерный массив
int arr[20][20] array_int;
следует трактовать как одномерный
int arr[400] array_int;
Заключение
Модель исследования научного предмета логического программирования значительно отличается от алгоритмического подхода, который применяется в императивных языках. Логическая программа является базой знаний и не содержит последовательности инструкций, который предполагает порядок выполнения вычислений. Последовательность работы с такой базой подразумевает правильную формулировку вопросов к ней и автоматизированное заключение решений. Механизм логического вывода уже интегрирован в среду программирования, и программист должен только результативно им управлять. На начальном этапе логического программирования программисту сложнее всего отказаться от алгоритмического мышления в пользу декларативного. Однако на настоящий момент развития компьютерной техники полный переход к декларативному программированию невозможен, поскольку сами компьютеры работают последовательно, а результат поиска решений существенно зависит от порядка записи и, следовательно, унификации фактов и правил в логической программе. Логический язык программирования можно использовать наиболее эффективно для решения комбинаторных задач, написания систем поддержки принятия решений, разработки экспертных систем и моделирования интеллектуальной деятельности.
Библиографическая ссылка
Обломов И.А., Ржавин В.В., Первова В.В., Герасимова А.Г. ИССЛЕДОВАНИЕ МОДЕЛИ ГЕНЕРАТОРА ОБЪЕКТНОГО КОДА, АССЕМБЛЕРА И БЛОКА ОПТИМИЗАЦИИ ИМПЕРАТИВНОГО ЯЗЫКА НА ЯЗЫКЕ PROLOG // Современные наукоемкие технологии. – 2022. – № 6. – С. 52-56;URL: https://top-technologies.ru/ru/article/view?id=39199 (дата обращения: 20.04.2024).