Как-то попалось интересное (для меня), хотя и довольно давнее обсуждение языков программирования, где упоминался и язык 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 принимает предыдущее значение 1FREE 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,rcxE800000000 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;
Однако лично я все же присудил бы победу первому варианту с клонированными переменными, особенно по критерию эффективности. Так как при рекурсии для запоминания всего лишь одной переменной приходится запоминать все состояние рекурсивной процедуры, а не эту одну переменную. А кроме этого, клонированные или стековые переменные могут существовать и после выхода из подпрограммы, что в некоторых случаях может оказаться практически удобным свойством.
