[Программирование, Алгоритмы, Компиляторы] Клонированные переменные

Ответить на тему

Автор

Сообщение

news_bot ^®

Стаж: 6 лет 9 месяцев
Сообщений: 27286

news_bot ^® написал(а)
01-Фев-2021 08:31

Цитировать

Как-то попалось интересное (для меня), хотя и довольно давнее обсуждение языков программирования, где упоминался и язык PL/1. В конце концов, как всегда и бывает на таких форумах, все стороны остались при своем мнении, и тогда один из участников предложил написать на разных языках и затем сравнить простой тест, один из тех, которые часто дают студентам «для закрепления пройденного»: Стандартный входной поток содержит произвольное (и заранее не известное) количество целых чисел. Нужно все их прочитать, а затем вывести нечетные числа в стандартный выходной поток в порядке, обратном исходному. Чтобы "не заслонять лес деревьями", будем считать, что доступная память бесконечна. Критерии сравнения предлагаю следующие (в порядке убывания их приоритета):

точность решения сформулированной задачи;
эффективность кода (по требуемой памяти и скорости работы);
простота её реализации на данном языке;
понятность алгоритма при минимуме комментариев;
читабельность кода;
краткость кода.

Для языка PL/1 был предложен следующий вариант:

PL1_EXAMPLE: PROCEDURE OPTIONS(MAIN);
DECLARE I FIXED CONTROLLED;
ON ENDFILE(SYSIN) GOTO L2;
L1: ALLOCATE I;
GET LIST(I);
IF MOD(I,2)=0 THEN FREE I;
GOTO L1;
L2: FREE I;
DO WHILE(ALLOCATION(I));
PUT LIST(I);
FREE I;
END;
END PL1_EXAMPLE;

На мой взгляд, можно было бы ещё укоротить текст. Поставив метку L2 прямо внутрь цикла DO WHILE и сократив, тем самым, один оператор FREE. Но согласен, это не лучший стиль программирования — входить в цикл не через заголовок.В этом тесте использовалось такая возможность PL/1 как «управляемые» (controlled) переменные. Название «управляемые», на мой взгляд, неудачное. Программист, по большому счету, всегда управляет размещением объектов программы, даже, если это и делается неявно. Наверное, больше бы подошло название «клонированные» переменные. Controlled-переменные требуют явного создания оператором ALLOCATE и после использования – явного уничтожения оператором FREE. Однако в отличие от «обычных» т.н. «базированных» (based) переменных, controlled-переменные после оператора FREE не исчезают, а получают предыдущее значение, если операторов ALLOCATE было несколько. Например, целая переменной X будет принимать следующие значения:

ALLOCATE X; X=1;
ALLOCATE X; X=2;
FREE X; // X принимает предыдущее значение 1
FREE X; // X больше не существует

Чтобы узнать существуют ли ещё экземпляры controlled-переменной, в языке предусмотрена встроенная функция ALLOCATION, которая возвращает «да/нет» для заданного объекта. Таким образом, для каждой controlled-переменной по существу создается свой отдельный стек, хотя и реализованный в виде связанного списка в «куче».В компиляторе, который я использую и сопровождаю, «клонированных» переменных не было. А поскольку их реализация казалась слишком сложной, я внушал себе (методом «зелен виноград»), что такая возможность и не очень-то и нужна. Но читая указанную дискуссию, мне вдруг пришла мысль, что controlled-переменные легко реализовать, используя такое свойство языка, как неявные указатели. В PL/1 можно в описании based-переменной не объявлять, какой указатель нужно использовать для данной based-переменной, но тогда в операторах программы его нужно каждый раз указывать явно. А можно наоборот, явно объявить один раз указатель в описании переменной и затем просто забыть про него – компилятор при каждом обращении к based-переменной будет подставлять его по умолчанию.В данном случае компилятору достаточно просто переводить controlled-переменные в based-переменные, указывая каждый раз не «обычные», описанные программистом, а специальные служебные указатели, имена которых меняются самим компилятором, например, на единицу. А при разборе операторов ALLOCATE и FREE компилятору нужно проверить использование обычного или такого служебного указателя. Если используется служебный указатель, то для ALLOCATE нужно увеличить размер заказанной памяти ещё на размер указателя, а затем в конец выделенного участка памяти записать текущее значение этого указателя перед тем, как заполнить его новым значением. А в операторе FREE перед освобождением памяти необходимо ещё содержимое последних байт указанного фрагмента памяти поместить в служебный указатель как его восстановленное значение. Для x86-64 эти дополнительные коды будут выглядеть так (учитывая, что в «куче» есть двунаправленный связанный список и восемью байтами «выше » в «куче» находится адрес следующего участка выделяемой памяти):для ALLOCATE

E800000000 call ?ALLOA ; выделяем память для переменной
488BCB mov rcx,rbx ; запомнили начало памяти в куче
F048871D20000000 xchg ?P0001,rbx ; запомнили и достали предыдущее
488B49F8 mov rcx,0FFFFFFF8h[rcx] ; предыдущий адрес переменной
488959F8 mov 0FFFFFFF8h[rcx],rbx ; запомнили пред.адрес в текущем экземпляре

для FREE

BB20000000 mov q rbx,offset ?P0001 ; адрес указателя
488B0B mov q rcx,[rbx] ; значение указателя
488B49F8 mov q rcx,0FFFFFFF8h[rcx] ; предыдущий адрес
488B49F8 mov q rcx,0FFFFFFF8h[rcx] ; предыдущая память
F048870B xchg q rcx,[rbx] ; предыдущий адрес в указатель
488BD9 mov q rbx,rcx
E800000000 call ?FREOP ; освободили память текущего экземпляра

Однако даже в такой простой реализации оказался свой подводный камень – число служебных указателей (?P0001,?P0002…) становится известным только после полного разбора исходного текста, а проще всего заводить их как раз в начале разбора, просто дописывая в таблицу стандартных объектов. Чтобы не переусложнять компилятор, число служебных указателей я сделал настраиваемым через реестр (как и ключи компилятора). Небольшое число таких указателей компилятор имеет, на всякий случай, всегда, а если требуется большое число controlled-переменных, тогда их число всегда можно увеличить через реестр, не меняя сам компилятор.Также для упрощения функции ALLOCATION её пришлось сделать с параметром «адрес», что потребовало ещё обращаться к имеющейся встроенной функции ADDR. Т.е. вместо обращения типа:

IF ALLOCATION(X) THEN…

применяется более громоздкое обращение:

IF ALLOCATION(ADDR(X)) THEN…

Которое зато позволяет вообще не менять компилятор, а лишь дописать в его таблицу стандартных функций новое имя и тип параметра. Таким образом, у меня тест принял следующий вид:

TEST:PROC MAIN;
DCL I FIXED(31) STACK;
ON ENDFILE(SYSIN) GO L1;
DO REPEAT;
ALLOCATE I;
GET LIST(I);
IF MOD(I,2)=0 THEN FREE I;
END REPEAT;
L1:FREE I;
DO WHILE(ALLOCATION(ADDR(I)));
PUT LIST(I);
FREE I;
END WHILE;
END TEST;

Или то же самое с русскими ключевыми словами:

ТЕСТ:ПРОЦ ГЛАВНАЯ;
ОПС I ТОЧНОЕ(31) СТЕК;
КОГДА КОНЕЦ_ФАЙЛА(СТД_ВВОД) ИДТИ L1;
ЦИКЛ ПОВТОРЯЯ;
ДАТЬ_ПАМЯТЬ I;
ЧИТАТЬ В_ВИДЕ(I);
ЕСЛИ ОСТАТОК(I,2)=0 ТОГДА ВЕРНУТЬ_ПАМЯТЬ I;
КОНЕЦ ПОВТОРЯЯ;
L1:ВЕРНУТЬ_ПАМЯТЬ I;
ЦИКЛ ПОКА(ЕСТЬ_В_СТЕКЕ(АДРЕС(I)));
ПЕЧАТАТЬ В_ВИДЕ(I);
ВЕРНУТЬ_ПАМЯТЬ I;
КОНЕЦ ПОКА;
КОНЕЦ TEСT;

Легко проверить, что если запустить такой тест и вводить с клавиатуры, например, 1 2 3 4 5 6 7 8 9 Ctrl+Z (последний символ сигнализирует о конце ввода), то на экран выдается требуемая последовательность: 9 7 5 3 1. Поскольку я считаю название «controlled» неинформативным, на русский язык я перевел его все-таки как «СТЕК» и приравнял атрибуты памяти CONTROLLED и STACK, подчеркивая, тем самым, организацию памяти в виде стека (пусть фактически и в виде связанного списка), а функцию ALLOCATION соответственно как ЕСТЬ_В_СТЕКЕ. Итак, не внося серьезных изменений в компилятор, удалось добавить в язык возможность, которая изначально была в полном стандарте языка и использовалась на практике. Получились своеобразные «клонированные» или «стековые» переменные, не в том смысле, что для их создания достаточно передвинуть указатель стека (увы, действий гораздо больше), а в том смысле, что при создании очередного экземпляра такой переменной, его предыдущее значение заталкивается в индивидуальный стек этой переменной. Такой индивидуальный стек расположен в общей «куче».Что касается предложенного теста, то, скорее всего, изначально он задумывался для демонстрации рекурсии, например, на том же PL/1 такой текст даже короче (не нужно явно выделять и освобождать память), хотя делает то же самое:

TEST:PROC MAIN;
F;
F:PROC RECURSIVE;
DCL I FIXED;
ON ENDFILE(SYSIN) GO L1;
GET LIST(I);
F;
IF MOD(I,2)^=0 THEN PUT LIST(I);
L1:
END F;
END TEST;

Однако лично я все же присудил бы победу первому варианту с «клонированными» переменными, особенно по критерию эффективности. Так как при рекурсии для запоминания всего лишь одной переменной приходится запоминать все состояние рекурсивной процедуры, а не эту одну переменную. А кроме этого, «клонированные» или «стековые» переменные могут существовать и после выхода из подпрограммы, что в некоторых случаях может оказаться практически удобным свойством.
===========
Источник:
habr.com
===========
Похожие новости:

Теги для поиска: #_programmirovanie (Программирование), #_algoritmy (Алгоритмы), #_kompiljatory (Компиляторы), #_pl/1, #_stek (стек), #_kucha (куча), #_programmirovanie (
Программирование
), #_algoritmy (
Алгоритмы
), #_kompiljatory (
Компиляторы
)

Профиль ЛС

Ответить на тему

Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы

Текущее время: 22-Ноя 12:21
Часовой пояс: UTC + 5