Pl/1

Введение

Зарегистрирована партия нового типа.

Личность типа выясняется.

Старая шутка.

Вот уже 38 лет мне приходится решать разнообразные задачи путем составления соответствующих программ. За все эти годы диапазон таких задач получился весьма большим: от программирования контроллера AT90S2313 до программы автоматического обращения русско-немецкого технического словаря в немецко-русский, и от расчета оптимального сечения стрингера до рисования вида земной поверхности из иллюминатора с орбиты методом обратной трассировки лучей.

Несмотря на разнообразие задач, все их, пожалуй, можно отнести к одному классу, который я условно называю инженерный, поскольку большей частью они оперируют понятиями научно-технического характера. При решении всех этих задач я не видел пользы в применении таких понятий, как абстрактный тип, т.е. назначению некоторого произвольного свойства объектам программы. Обычно эти свойства при трансляции имеют внутреннее представление в виде целых чисел.

Могут возразить, что я не вижу смысла в таких типах потому, что в старых языках (вроде используемого мною PL/1) вообще не было типизации в современном понимании. Нет, понятие типа все-таки было. Например, если в том же PL/1 описать два несовпадающих объекта пусть даже одинакового объема и попытаться присвоить один другому, то при компиляции получится предсказуемое сообщение об ошибке (рис. 1).

Тогда за какое же отсутствие типов критиковали старые языки, в том числе PL/1? Например, за возможность присвоения объекта строка объекту число в формате IEEE-754. Ведь в этом случае ошибок при компиляции уже не будет.

Верно, ошибки не будет. Но в моем понимании это вовсе не разные типы. Это всего лишь работа с числовыми значениями в разном представлении. Просто здесь число в виде строки цифр и специальных символов переводится в число же, но в формате IEEE-754. А сам тип объекта остается одним и тем же числовым. Но в том же PL/1 вполне можно проследить и разницу между строкой и числом.

Например:

Declare (S1, S2) char(*) varying;S1=S1||S2;S1=S1+S2;

В первом случае происходит склейка двух строк в одну, а во втором каждая строка сначала преобразуется в числовое значение, затем эти значения складываются и результат снова преобразуется в строку цифр и, возможно, специальных знаков. Правила языка были разработаны таким образом, чтобы преобразование числовых значений из одной формы представления в другую проходило по возможности без потери точности. Непонимание, что транслятор постоянно применяет эти правила и приводит к неверным утверждениям об отсутствии типов в PL/1.

Огорчает, что абстрактные типы, обычно представляемые в целых числах, часто создают лишь иллюзию упрощения задачи, не помогая ее решению. Причем внимание к типизации все время возрастает, а польза от их применения, по крайней мере, в инженерных задачах - сомнительна. Если тип целое число, его можно только сравнить с другими типами, а для перечисляемых типов определить предыдущий/следующий из списка. В учебниках охотно приводят как пример перечисляемого типа день недели: понедельник, вторник Но что это дает, например, для практической задачи определения дня недели по заданной дате? Тип день недели никак не помогает, зато помогает формула:

День_недели=([2.6*Месяц-0.2]+День+Год+[Год/4]+[Столетие/4]-2*Столетие) mod 7

где квадратные скобки означают целую часть числа.

В современных языках при решении инженерной задачи я легко могу ввести абстрактные типы, например, длина и ширина. Но при использовании механизма таких типов, единственное, что при этом получаю по умолчанию это запрет использования их в одной операции без специального указания на преобразование типов. А по физическому смыслу все просто: длина и ширина - однотипные величины, если умножить длину на ширину должен получиться тип площадь. А при делении длины на ширину должен получиться безразмерный коэффициент, который, как и обычные константы может быть использован в выражениях с любыми другими типами.

Разумеется, можно учитывать все эти правила, переопределяя операции языка, имеющего развитую типизацию. Но у многих ли хватает желания и терпения сделать это?

Даже один из авторов языка Ада Н. Джехани в ретроспективе сожалел, что в этот язык изначально им не была встроена система типов в виде единиц измерений [1]. Для класса инженерных задач эта идея использовать как систему типов Международную систему единиц СИ, всегда казалась мне очевидной и потенциально полезной, но почему-то нигде в современных распространенных языках не реализованной, за исключением некоторых возможностей в Matlab и Mathcad. И я решил поэкспериментировать со своим транслятором PL/1 [2] и добавить новую типизацию не в виде абстрактных понятий, а прямо в виде размерностей из базовых величин СИ, и затем на примере реальной задачи посмотреть какие плюсы и минусы это даст программисту, а также оценить сложность доработок транслятора.

Физический смысл типов в инженерных задачах

Приписывая при решении инженерной задачи объектам программы не абстрактный, а физический смысл (и используя как тип размерность, т.е. выражение производной величины через первичные), мы сразу добавляем хорошо определенное множество зависимостей для этих объектов, а значит, облегчаем транслятору автоматическую проверку корректности действий и, тем самым, повышаем надежность программы.

При этом теоретическое обоснование системы независимых физических типов уже давно имеется в виде успешно применяемой теории размерности, основная теорема (пи-теорема) которой формулируется следующим образом [3]: соотношение, не зависящее от выбора единиц измерения между (n+1) размерными величинами a, a₁, a₂,a_n, k из которых имеют независимые размерности, может быть представлено в виде соотношения между (n+1-k) величинами П, П₁, П₂, П_n-k, представляющими собой безразмерные комбинации (n+1) размерных величин.

Основной смысл пи-теоремы состоит в том, что всякое физическое соотношение между размерными величинами можно сформулировать как соотношение между безразмерными величинами.

Следовательно, поскольку в СИ независимыми являются лишь семь физических величин:

- длина L (единица - метр),

- масса M (единица - килограмм),

- время T (единица - секунда),

- термодинамическая температура (единица - Кельвин),

- сила электрического тока I (единица - ампер),

- сила света J (единица - кандела),

- количество вещества N (единица - моль),

то в программе любой переменной, которой мы приписали физический смысл, может быть сопоставлен физический же тип в виде размерности из степенного одночлена, выраженного через основные единицы: [x]=L^l M^m T^t Iⁱ J^j Nⁿ.

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

Масштабный коэффициент в физических типах

На практике величины, имеющие физический смысл, часто задаются в производных единицах измерения, отличающихся от базовых единиц масштабным коэффициентом. Например, длины - в км, площади - в Га и т.д. Поэтому целесообразно ввести в представление физических типов еще и масштабный коэффициент в виде одного числа в формате IEEE-754.

Наличие такого коэффициента позволит транслятору автоматически учитывать масштабы при генерировании операций для выражений. Например, если переменным X1, X2, X3 приписаны типы соответственно [км], [см] и [мм], то при вычислении выражения X1=X2+X3, транслятор должен автоматически добавить операции умножения X2 на 0.01 и X3 на 0.001, а затем результат сложения перед присваиванием X1 еще разделить на 1000.

Наличие приближенного масштабного коэффициента дает важное следствие физические типы могут быть тоже только у приближенных переменных, т.е. только у переменных в формате с плавающей запятой. Однако для класса инженерных задач такое ограничение на переменные практически несущественно.

При этом автоматическая подстановка масштабных коэффициентов при трансляции выражений означает, что все расчеты в программе будут производиться в базовых величинах СИ, как в приведенном выше примере в метрах. Это также означает, что масштабные коэффициенты в физическом типе могут быть только у переменных, но не у выражений, где масштабы уже учтены при генерации операций загрузки переменных этого выражения.

Дополнительные величины в физических типах

Хотя в СИ имеется лишь семь базовых величин, на практике используются еще две вспомогательные величины плоский угол (единица - радиан) и телесный угол (единица - стерадиан).

Здесь наблюдается некоторое противоречие с точки зрения формального определения типа. В самом деле, радиан и стерадиан по определению безразмерные величины и могут быть использованы или не использованы в выражениях для других производных единиц СИ. Однако в некоторых случаях они ведут себя как обычные (размерные) величины. Например, в PL/1 имеется встроенная функция sin, входным параметром которой должно быть выражение в радианах и функция sind, входным параметром которой должно быть выражение в градусах. Переменная с физическим типом градус отличается от переменной с физическим типом радиан, масштабным коэффициентом /180.

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

W=/t; // угловая скорость (угол делится на время)

V=R*W; // линейная скорость (радиус поворота умножается на угловую скорость)

В самом деле, если угол имеет физический тип радиан, то получается, что угловая скорость W имеет физический тип радиан в секунду, а линейная скорость после умножения на радиус метр на радиан в секунду, что не соответствует требуемой размерности скорости метр в секунду.

Поэтому хотя вспомогательные величины радиан и стерадиан действительно также представлены в степенном одночлене физического типа, но ведут себя не совсем так, как семь остальных базовых величин. Они считаются размерными величинами, только если остальные величины в одночлене имеют нулевые показатели степени (т.е. отсутствуют). Как только при вычислениях появляется любая другая величина радиан и стерадиан сокращаются, т.е. их показатель степени транслятором обнуляется. Тогда в приведенном примере выражение /t (и угловая скорость W) получает физический тип единица, деленная на секунду, а выражение R*W правильный физический тип скорости метр в секунду. Но при этом выражение, например, sin(2*) по-прежнему можно проверить на корректный физический тип аргумента радиан.

Внутреннее представление физического типа в трансляторе

Исходя из приведенных выше теоретических и практических соображений, каждой переменной программы, которой может быть приписан некоторый физический смысл, программистом может быть присвоен универсальный физический тип из величин СИ. Данный тип в таблице транслятора PL/1 представлен в виде одного масштабного коэффициента в формате IEEE-754 и занимающего восемь байт, а также девяти показателей степени основных и вспомогательных величин в смысле единиц СИ.

Поскольку вычисления в инженерных задачах проводятся и с дробными степенями, например, Z=SQRT(X**2+Y**2), то показатели степени в универсальном физическом типе представлены рациональными (и возможно неправильными) дробями. При этом байт занимает числитель и байт знаменатель. Таким образом, показатели степени в трансляторе могут быть представлены числами от -128 до 127, а в целом каждый физический тип переменной занимает в таблице транслятора 8+9*2=26 байт.

Действия с физическими типами при вычислении выражений

При анализе выражений в программе и генерации операций над переменными с физическими типами транслятор производит вполне очевидные действия, чтобы получить текущий физический тип всего выражения.

При умножении переменных показатели степеней их физических типов складываются. Поскольку степени представлены дробями, то и складываются они, естественно, как дроби.

При делении переменных показатели степеней их физических типов вычитаются.

При возведении переменной в степень-константу показатели степеней физического типа умножаются на эту константу. При этом возведение в нецелую степень или в степень-переменную для физического типа считается ошибкой, за исключением случая представления степени-константы в виде дроби. Например, в выражении X**(1e0/3e0) показатели степени физического типа переменной X будут умножены на дробь 1/3, т.е. в данном случае знаменатели степеней будут умножены на три.

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

При сложении, вычитании, сравнении и присваивании переменных с физическими типами, сами типы, естественно, не меняются, а просто сравниваются на совпадение. При этом масштабные коэффициенты учитываются в выражениях и присваиваниях и поэтому в этих операциях могут не совпадать. Однако есть частные случаи присваивания или сравнения (например, векторов), когда присваивание или сравнение реализуется просто побайтным переписыванием или сравнением двух участков памяти. В таких случаях и масштабные коэффициенты физических типов у сравниваемых или присваиваемых переменных обязаны также совпадать.

Задание физических типов в исходном тексте программы

При доработке транслятора для удобства задания физических типов с сохранением возможности трансляции уже написанных программ (без таких типов), были использованы символы квадратных скобок, ранее вообще не применявшиеся в языке PL/1, например:

Declare V float(53) [м/с];

Внутри квадратных скобок могут быть записаны произвольные выражения, состоящие из скобок, знаков умножения, деления, возведения в степень, числовых констант и девяти имен базовых и вспомогательных величин СИ: м, кг, с, а, к, моль, кд, рад, ср. Для угловых величин допустимо также имя ПИ.

Например:

Declare Mu float(53) [(1000*m)**3/c**2];

Declare Fi float(53) [пи/180*рад];

Встроенная таблица физических типов в трансляторе имеет лишь девять первых заполненных строк перечисленными выше базовыми величинами, однако с помощью препроцессорного оператора замены %replace в нее можно добавлять произвольное число нестандартных типов, например:

%Replace

[км] by [1000*м],

[час] by [3600*c],

[миля] by [1852*м],

[узел] by [миля/час];

Declare

скорость float(53) [км/час],

скорость_судна float(53) [узел];

При этом после выполнения оператора %Replace имена км, час, миля и узел становятся допустимыми только внутри квадратных скобок описания физического типа, но не в остальном тексте программы.

Присваивание переменным с физическими типами начальных значений

При обработке оператора присваивания переменной с физическим типом транслятор проверяет, что показатели степени девяти величин СИ в представлении типа в левой и правой части присваивания совпадают. Но как быть при присваивании переменной начального значения не выражения, а, например, константы?

Вроде бы напрашивается непосредственное указание физического типа у констант прямо в операторах программы, например:

V=10 [км/час];

Но мне такой подход не кажется логичным. Все-таки числовые константы, записываемые непосредственно в физических уравнениях не должны иметь собственной размерности. Это удел переменных, даже, если они и не меняют в данном конкретном случае своих величин. Поэтому инициализация значений в доработанном трансляторе выполняется так:

Declare // константыg float(53) static init(9.81e0) [м/c**2],v0 float(53) static init(10e0) [км/час],// переменныеm float(53) [кг],v float(53) [км/час],F float(53) [кг*м/с**2];v=v0; F=g*m;

Исключение составляет константа 0. Ее физический тип может быть любым:

v=0; F,m=0;

Чтение и запись переменных с физическими типами

В файловом обмене языка PL/1 существует два вида чтения/записи объектов: двоичный и текстовый, реализуемые соответственно операторами read/write и get/put.

Естественно, что двоичный обмен операторами read/write осуществляется без каких-либо преобразований и поэтому переменные с физическими типами записываются и читаются из файлов точно так же как и любые другие переменные.

А вот в другом случае появляется несколько непривычное свойство вывода переменных с физическими типами. Поскольку в общем случае текстового вывода выдаваемый объект это выражение, то для переменных с физическими типами в нем автоматически будут учтены масштабные коэффициенты, а, следовательно, выражение всегда будет выведено в базовых единицах СИ, например, в метрах, даже когда выводится одна переменная и она задана в километрах или в миллиметрах.

Для того чтобы операторы put и get оставались зеркальными транслятор автоматически учитывает масштабный коэффициент переменной и при чтении ее оператором get, т.е. при чтении также подразумевается, что значения хранятся в файлах в базовых единицах СИ.

Если все же необходим текстовый обмен без учета масштабных коэффициентов, то в PL/1 это можно реализовать, используя т.н. наложенные переменные, т.е. описав переменные без физических типов по тем же адресам памяти, что и переменные с физическими типами, например, в случае:

DeclareX1 float(53) static init(10e0) [км],X2 float(53) defined(X1);put skip list(X1,X2);

будут выданы значения 10000 и 10.

Встроенная переменная ?TYPE для выражений с физическими типами

При добавлении в транслятор физических типов традиционно следовало бы добавить и встроенную функцию, например, с именем TYPE, возвращающую физический тип своего аргумента. Однако я решил вместо этого ввести встроенную переменную (строку) ?TYPE, автоматически принимающую значение физического типа (т.е. размерности) последнего вычисленного выражения.

В самом деле, вычислять физический тип для одной переменной с помощью встроенной функции довольно бессмысленно, поскольку эта же переменная описана с этим же физическим типом здесь же, в исходном тексте. Физический тип обычно нужен при выводе результатов в виде выражений, но тогда выражение транслятору придется вычислять два раза, например:

put skip list(s/t,type(s/t));

Поэтому для вывода удобнее использовать встроенную переменную, а не функцию, например при выполнении оператора вывода в данном примере:

Declares float(53) static init(10) [км],t float(53) static init(5) [час];put skip list(s,?type,t,?type,s/t,?type);

будут выданы следующие значения (рис. 2):

Физические типы формальных параметров подпрограмм

Формальные параметры подпрограмм, как и обычные переменные, естественно, также могут иметь физический тип с масштабным коэффициентом. При вычислении и подстановке фактического параметра транслятор выполняет те же действия, что и при обычном присваивании, т.е. сравнивает показатели степеней базовых величин и умножает на масштабный коэффициент.

Однако если параметром является не скалярная величина, а сразу агрегат данных, масштабный коэффициент формального и фактического параметров должны строго совпадать и в этом случае на коэффициент, конечно, ничего не умножается.

Также, разумеется, физический тип может иметь возвращаемое подпрограммой значение:

Declare

//модуль радиус-вектора

Vmod entry((3) float(53)[км]) returns(float(53)[км]);

Поскольку на практике используются и подпрограммы с полиморфными типами, я допустил задание в формальных параметрах неопределенного физического типа (с помощью знака ?), при котором проверки на совпадение и учет масштабных коэффициентов отключаются.

Declare

//модуль любого вектора

Vmod0 entry((3) float(53)[?]) returns(float(53)[?]);

Еще один особый случай представляет встроенная функция квадратного корня SQRT. Она, разумеется, тоже имеет неопределенный физический тип формального аргумента, но возвращает всегда такой же тип как у фактического аргумента и в степени .

К сожалению, это правило нельзя распространить на любые подпрограммы с неопределенными типами, поскольку в общем случае они могут возвращать физические типы не обязательно совпадающие с типом входного аргумента.

Отладочные средства для физических типов

Кроме встроенной переменной ?TYPE, есть еще два отладочных средства. Это возможность вывести всю таблицу переменных программы, включая теперь и их физические типы с масштабными коэффициентами и собственно сообщения при компиляции о несоответствии типов в вычисляемых выражениях (рис. 3). В данном случае в небольшом тесте, приведенном ниже, в операторе сравнения физические типы справа и слева оказались не равны.

test:proc main;%replace[км] BY [1000*м],[час] BY [3600*с];declares float(53) static init(10) [км],t float(53) static init(5) [час],v float(53) [км/час];if s*t>v*t then stop;

Пример применения физических типов

Для оценки удобства применения физических типов была взята программа расчета орбитальных параметров, написанная и, разумеется, тщательно отлаженная еще много лет назад. Поскольку программа уже была создана, требовалось лишь восстановить физический смысл ее величин, учесть в некоторых случаях масштабные коэффициенты и убедиться, что с точки зрения размерностей физических типов все уравнения записаны корректно.

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

Примеры изменений исходного текста данной программы приведены ниже.

а) Потребовалось ввести ряд переменных с типами вместо ранее безразмерных констант, например:

// СКОРОСТЬ ВРАЩЕНИЯ ЗЕМЛИ

WEarth float(53) static init(0.000072921158e0) [РАД/C],

// ДВА ПИ

Dpi float(53) static init(6.28318530717958648e0) [РАД],

// Epsilon/Mu

Em float(53) static init(66072.1866e0) [KM**2],

// ГРАВИТАЦИОННЙ ПОТЕНЦИАЛ

Mu float(53) static init(398600.4e0) [KM**3/C**2],

// ПОЛУОСЬ ДЛЯ СРЕДНЕЙ ВСОТ 358 КМ

Am float(53) static init(6736e0) [KM],

//ЭКВАТОРИАЛЬНЙ РАДИУС ЗЕМЛИ

Re float(53) static init(6378.137e0) [KM],

б) Потребовалось убрать ряд приведений масштабов переменных, например:

Было:

//---- ПРИВЕДЕНИЕ МАСШТАБОВ К КМ И +-180 ----

do i=1 to 3;

vsg(i)=vsg0(i)/1000e0; // ПЕРЕВЕЛИ В КМ

vrg(i)=vrg0(i)/1000e0; // ПЕРЕВЕЛИ В КМ

if Lamseans(i) > 180e0 then Lamseans(i)-=360e0;

end i;

Стало:

//---- ПРИВЕДЕНИЕ МАСШТАБОВ К КМ И +-180 ----

do i=1 to 3;

vsg(i)=vsg0(i); // АВТОМАТИЧЕСКИЙ ПЕРЕВОД В КМ

vrg(i)=vrg0(i); // АВТОМАТИЧЕСКИЙ ПЕРЕВОД В КМ

if Lamseans(i) > У_180 then Lamseans(i)-=У_360;

end i;

Было:

BetaBal=60e0*(per2-per1)/(te2s-te1s)/2e0; // ПЕРИОД БЛ В МИНУТАХ

Стало:

BetaBal=(per2-per1)/(te2s-te1s)/2e0; // ПЕРИОД БЛ В МИНУТАХ

в) Некоторые произвольно разбитые на части формулы потребовалось свернуть, чтобы не вводить промежуточных переменных с нестандартной размерностью, например:

Было:

//---- ТЕКУЩИЙ РАДИУС ДЛЯ РАСЧЕТА ВСОТ ----

Radius = J3-et1+dz1*dz1+J4*cos(ArgLat+ArgLat);

Radius *= Axe*(1e0+J7*tp);

Стало:

//---- ТЕКУЩИЙ РАДИУС ДЛЯ РАСЧЕТА ВСОТ ----

Radius = Axe*(1e0+J7*tp)* (J3-et1+dz1*dz1+J4*cos(ArgLat+ArgLat));

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

//---- ОЦЕНКА ПОЛУОСИ ПО ЗНАЧЕНИЮ ПЕРИОДА ----

do AxeOfPer=Am, i=1 to 4; // НАЧИНАЕМ С ВСОТ 358 КМ

AxeOfPer=((Period/Dpi)**2*Mu)**(1e0/3e0)

/(1e0-2e0/3e0*Em/AxeOfPer/AxeOfPer*(4e0*CosIncl*CosIncl-1e0));

end;

Однако одна логическая ловушка с точки зрения размерностей в программе все-таки нашлась:

//---- ШИРОТА В ГРАДУСАХ С УЧЕТОМ ЭЛЛИПСОИДНОСТИ ЗЕМЛИ ----

Fi = Fi + Alz*sin(2e0*Fi);

Здесь Alz безразмерный коэффициент сжатия земного эллипсоида, равный 1/298.257. Получается, что в формуле угол Fi в радианах складывается с заведомо безразмерным синусом, т.е. несоответствие размерности. Так сказалось формальное представление углов условно размерной величиной радиан, несмотря на то, что реальный радиан величина безразмерная. Для формального же преодоления этого несоответствия в формуле пришлось дополнительно умножить синус на переменную с физическим типом радиан и единичным значением.

Заключение

Встраивание в транслятор языка PL/1 дополнительной типизации и назначение нового свойства переменным, определенного как физические типы в виде базовых и вспомогательных единиц Международной системы СИ позволило:

- автоматически проверять по размерности корректность записи уравнений, имеющих физический смысл;

- автоматически учитывать различные несистемные единицы измерений, при этом организовать сами вычисления всегда в семи базовых и двух вспомогательных единицах СИ.

Если внутреннее представление абстрактного типа целое число, то с таким типом можно выполнять лишь простейшие действия, например, сравнивать на совпадение или определять предыдущий/следующий тип. Обычно автоматически при вычислениях такой тип не меняется.

В отличие от абстрактных типов, которых может быть бесконечное число и отношения между которыми должен задавать программист, число физических типов мало и они независимы друг от друга по определению.

Кроме этого физический тип изначально хранит гораздо больше информации об объекте и автоматически меняется при вычислении выражений по вполне очевидным правилам. Масштабный коэффициент физического типа позволяет легко оперировать внесистемными единицами измерений и при этом автоматически сводить все вычисления к системным единицам. На практике, пользоваться в инженерных задачах физическими типами оказалось вполне удобно и естественно. Объем доработок транслятора оказался сравнительно небольшим.

Несмотря на то, что некоторые действия в программе из-за новых типов упрощаются, а некоторые встроенные функции (например, упомянутая выше sind) стали ненужными, в целом число операций в вычислениях может увеличиться (из-за добавления умножений на масштабные коэффициенты). Однако при этом проверки корректности программы облегчаются и ее надежность возрастает.

Как пример важности таких проверок корректности можно привести неудачу миссии Mars Climate Orbiter 23 сентября 1999 года из-за расчетов в не тех единицах измерения. Вполне вероятно, что если бы используемые трансляторы тогда имели бы механизм физических типов, подобный приведенному выше, а также автоматический вывод в системных единицах, можно было бы выполнять расчеты в злополучных фунт-силах, но при этом избежать последующих разночтений с печальными последствиями.

Литература

1. Языки программирования Ада, Си, Паскаль. Сравнение и оценка. Под редакцией А. Фьюера, Н. Джехани. Радио и связь, 1989, с. 182.

2. Д.Ю.Караваев К вопросу о совершенствовании языка программирования RSDN Magazine #4 2011, с. 15-21.

3. А.С Романов, А.В. Семиколенов, С.Н. Тараненко, А.П. Шахорин Теория подобия и размерности. Пограничный слой. Электронное учебное издание МГТУ им. Н.Э. Баумана, 2011, с. 8.

Введение

Где хранить деньги? это шутливое название поста, периодически появляющегося на компьютерных форумах. Имеется в виду вопрос: в переменных какого типа следует хранить результаты вычислений финансово-экономических расчетов. Обычно такой вопрос возникает у программистов, впервые сталкивающихся с подобными расчетами. Интуитивно они понимают, что здесь округления нежелательны или недопустимы. Интересно, что при этом часто вспоминают легенды о хитрых программистах, сумевших разницу между точным и округленным значением финансовых расчетов перечислять на свой собственный счет. Правда, эти истории названы сказками еще в книге [1], написанной 50 лет назад, причем даже там речь шла лишь о ревизиях банковских систем, основаниями для которых (т.е. для ревизий) могли бы служить подобные истории.

Компьютеры применяются для экономических расчетов уже более 60 лет. Приемы и инструменты таких расчетов хорошо развиты и изучены. Тем не менее, поскольку все-таки возникают вопросы, подобные вынесенному в заголовок, представляется полезным для лучшего понимания проблем экономических расчетов привести как пример одну из самых простых и проверенных временем реализаций в трансляторе аппарата точных вычислений и его особенностей. Под точными далее будут подразумеваться вычисления без округлений и с исходными данными, представленными в виде десятичных дробей. Разумеется, не все данные можно точно представить в десятичном виде, поэтому понятие точный здесь имеет некоторые ограничения, однако для экономических расчетов в большинстве случаев эти ограничения несущественны.

Пример необходимости точных вычислений

Рассмотрим простейший пример: рассчитать выплату 13% с суммы 1 рубль 30 копеек. Это значение легко сосчитать на бумаге столбиком и притом точно: 16.9 копейки. Но если запрограммировать этот же расчет с использованием данных типа double, то получится ответ вроде 1.68999999999999E-001 рубля, поскольку значение 0.169 точно представить в формате IEEE-754 нельзя. Вот тут и начинаются сомнения: не приведет ли ряд подобных вычислений к накоплению погрешности? Определение итоговой погрешности для нетривиальных расчетов само является нетривиальной математической задачей и лучший способ ее решения не допускать погрешностей вообще. Но как это сделать? И какой тип данных должен быть, если тип целый не годится, а тип float обязательно даст погрешность?

Виды представления чисел

Может показаться, что автор ломится в открытую дверь. Есть же в языках типы для работы с деньгами, например, тип DECIMAL в языке C#. Как следует из описания языка [2], Тип значения Decimal подходит для финансовых вычислений, требующих большого количества значимых целых и дробных цифр и отсутствия ошибок округления. Избежать округления с помощью типа Decimal нельзя. Однако он позволяет минимизировать связанные с ним ошибки. Странно, требуется избежать ошибок округления и одновременно утверждается, что этого сделать нельзя.

Одной из причин затруднений в таких случаях является, на мой взгляд, не совсем четкая классификация представления чисел. Многие привыкли делить числа только на целые и действительные, хотя правильнее было бы вначале разделить их на точные и приближенные. При этом целые это подмножество точных, а не все множество. В приведенном примере расчета на бумаге хотя и получились копейки с долями, т.е. нецелое значение, никакой потери точности не произошло. Тип DECIMAL в языке C# корректнее было бы назвать модифицированным FLOAT, поскольку он содержит те же знак, мантиссу и порядок. И значения этого типа все же приближенные, хотя и с очень большим числом значащих цифр.

Аппаратная поддержка точных вычислений

А ведь в процессорах архитектуры IA-32 имеется набор специальных команд так называемой десятичной и двоично-десятичной арифметики. Они предназначены как раз для проведения точных вычислений. Удивительно, но в 64-разрядном режиме эти команды становятся недоступными, можно предположить, что в фирме Intel разработчики заранее расчищают кодовое пространство для новых команд. Но в 32-разрядном режиме такие команды доступны, упрощая вычисления со сколь угодно большой точностью и без округлений. Для проверки автор задавал вопросы коллегам по поводу назначения двоично-десятичной арифметики и убедился, что многие имеют о ней нечеткие представления, например, отвечая, что она нужна только для того, чтобы не переводить число из текста в двоичное и обратно. Такой ответ тоже допустим, поскольку числа действительно представлены не в обычном виде. Но все-таки следует еще раз подчеркнуть, что главное назначение нестандартной арифметики упростить организацию вычислений без потери точности.

Программная поддержка точных вычислений

Механизм вычислений без округлений был встроен, например, в язык PL/1. Этот язык изначально разрабатывался для применения и в области экономических расчетов, для чего он получил наследство от языка экономических задач Кобола. Можно даже предположить, что команды двоично-десятичной арифметики были вставлены в архитектуру IA-32 (точнее, еще в IA-16 в 1978 году) именно для поддержки в языках высокого уровня типа PL/1 аппарата точных вычислений. Поскольку автор сопровождает и использует транслятор языка PL/1 [3], дальнейшее изложение будет относиться к конкретной реализации. Сама реализация довольна проста и объем команд транслятора, обеспечивающих генерацию точных вычислений, не превышает 3-4% от размера транслятора.

Представление чисел FIXED DECIMAL

Граница между представлениями чисел в PL/1 проведена корректно: все числа точного представления имеют тип FIXED, а приближенного представления FLOAT. К сожалению, сами названия FIXED/FLOAT (вместо ТОЧНОЕ/ПРИБЛИЖЕННОЕ) не вносят ясности и интуитивно непонятны. Как, кстати, и распространенное в языках, но совершенно неинформативное название double.

В операторах описания на PL/1 точное представление чисел имеет атрибуты FIXED DECIMAL, после которых указывается общий размер числа и размер дробной части числа, например, FIXED DECIMAL(15,0)или FIXED DECIMAL(12,4) т.е. так можно точно представлять и целые и нецелые значения. Значения можно также представлять и как FIXED BINARY, но далее будет рассматриваться только тип, который может иметь десятичную дробную часть.

В рассматриваемом трансляторе этот тип реализован в двоично-десятичном упакованном коде BCD (Binary Coded Decimal). Каждая цифра BCD записывается в половину байта. При этом старшая значащая пара цифр BCD размещается по старшему адресу. Самая старшая позиция BCD резервируется для знака, который для положительных чисел - ноль, для отрицательных - девять. Число байт для FIXED DECIMAL определяется заданной точностью p (допустимой в стандарте языка от 1 до 15) и равно FLOOR((p+2)/2).

Например, число 12345 с точностью 5, для которого PL/1 выделит FLOOR((5+2)/2)=3 байта памяти, будет записано в байтах как 45 23 01. Максимально допустимое значение, которое можно записать в таком виде 999999999999999. Например, чтобы представить точно значение государственного долга США, который,например, на начало 2013 года составлял около $16,400,000,000,000, потребуется переменная типа FIXED DECIMAL(14,0). Правда, если долг вырастет еще раз в 60, представить его точно в формате стандарта PL/1 будет уже нельзя.

Отрицательное число записывается в дополнительном до 9 коде, который получается вычитанием каждой цифры из 9 и прибавлением к числу единицы. Например, число -2 имеет код (9-2)+1=8 и с точностью 1 будет записано как байт 98, а с точностью 5 будет выглядеть в байтах как 98 99 99.

Может показаться странным, что в этом представлении нет указания положения десятичной точки. Но ведь и в логарифмической линейке не было указателя точки приходилось держать ее позицию в уме. В данном случае за положением десятичной точки следит транслятор и явно указывает ее как параметр при вызове подпрограмм преобразований, ввода-вывода и т.п. А при генерации самих вычислений положение точки рассчитывается транслятором так, чтобы не терялась точность, и тоже держится в уме пока ее не потребуется использовать. Если вернуться к примеру, при генерации умножения транслятор назначит константе 1.3 атрибуты FIXED DECIMAL(2,1), константе 0.13 - атрибуты FIXED DECIMAL(3,2), а результату (значению 0.169) атрибуты FIXED DECIMAL(6,3), совсем как при умножении столбиком, когда ширина результата складывается из размеров множителей. Правда в данном случае ширина должна была бы быть 5, а не 6, но по особенности PL/1 он считает длину результата при точном умножении как p₁+p₂+1, поскольку стандарт учитывает даже случай умножения комплексных чисел по формуле (a₁a₂-b₁b₂)+(a₁b₂+b₁a₂)i, где становится возможен еще один перенос разряда.

Системные вызовы точных вычислений

Поскольку точные вычисления не могут быть реализованы за одну-две команды, транслятор генерирует множество вызовов системных подпрограмм, обеспечивающих все необходимые действия: арифметику, функции FLOOR/CEIL/TRUNC, сравнение и т.п. Операнды типа FIXED DECIMAL передаются через стек и туда же возвращается результат операции. При этом операнды всегда расширяются до максимальной длины 8 байт и дописываются или нулями или байтами 99 (для отрицательных).

Ниже приведен фрагмент исходного текста системной библиотеки, обеспечивающий функции вычитания и сложения. Для краткости, текст остальных функций в данной статье не приводится.

; ВЧИТАНИЕ DECIMAL В СТЕКЕ PUBLIC ?DSUOP: ;ГЕНЕРИРУЕТСЯ ВЗОВ ИЗ PL/1 LEA ESI,[ESP]+4 ;НАЧАЛО 1 DECIMAL (УЧЛИ RET) MOV ECX,8 ;МАКСИМАЛЬНАЯ ДЛИНА DECIMAL CLC ;СБРОС ПЕРЕНОСА LEA EDI,[ESI+ECX] ;НАЧАЛО 2 DECIMAL;---- ЦИКЛ ВЧИТАНИЯ ----M2187:MOV AL,[EDI] SBB AL,[ESI] ;ВЧИТАНИЕ С КОРРЕКЦИЕЙ DAS STOSB ;ЗАПИСЬ РЕЗУЛЬТАТА INC ESI LOOP M2187POP ECX ;АДРЕС ВОЗВРАТА MOV ESP,ESI ;ОЧИСТКА СТЕКА JMP ECX      ; СЛОЖЕНИЕ DECIMAL В СТЕКЕ EXTRN ?DOVER:NEARPUBLIC ?DADOP: ;ГЕНЕРИРУЕТСЯ ВЗОВ ИЗ PL/1 LEA ESI,[ESP]+4 ;НАЧАЛО 1 DECIMAL (УЧЕТ RET) MOV ECX,8 ;МАКСИМАЛЬНАЯ ДЛИНА DECIMAL CLC ;СБРОС ПЕРЕНОСА LEA EDI,[ESI+ECX] ;НАЧАЛО 2 DECIMAL;---- ЦИКЛ СЛОЖЕНИЯ ДВУХ DECIMAL В СТЕКЕ ----M2283:LODSBADC AL,[EDI] ;СЛОЖЕНИЕ С КОРРЕКЦИЕЙ DAA STOSB ;ЗАПИСЬ ОТВЕТА LOOP M2283;---- ПРОВЕРКА НА ПЕРЕПОЛНЕНИЕ ---- AND AL,0F0H ;ВДЕЛИЛИ ПОСЛЕДНЮЮ ЦИФРУ JZ @ CMP AL,90H ;ОТРИЦАТЕЛЬНЙ НЕ ПЕРЕПОЛНИЛСЯ ? JNZ ?DOVER ;OVERFLOW ДЛЯ DECIMAL  ;---- ВХОД С ОЧИСТКОЙ СТЕКА ----@: POP ECX ;АДРЕС ВОЗВРАТА MOV ESP,ESI ;ОЧИСТКА СТЕКА JMP ECX

Как следует из этого текста, для двоично-десятичной арифметики используются команды сложения и вычитания с учетом переноса (ADC/SBB) и две специфические команды коррекции результата (DAA/DAS), те самые, которые исключены в 64-разрядном режиме.

Умножение и деление требует большего числа команд, и поэтому будет выполняться медленнее, хотя в экономических расчетах объем вычислений часто невелик по сравнению, например, с объемом ввода-вывода, и сравнительно медленное выполнение арифметических операций обычно не является критичным.

Обратите внимание, что нет принципиальных ограничений на длину данных типа FIXED DECIMAL: цикл побайтной обработки пар цифр можно сделать любой длины (а, значит, и точности), хотя в соответствии со стандартом языка PL/1 под каждый операнд при вычислениях выделяется 8 байт и эта максимальная длина записана как константа. Если в трансляторе изменить предел размера типа, например с 15 до 31, а в системных подпрограммах заменить константу 8 на 16, то переменные автоматически станут получать длину до 16 байт и обрабатываться с точностью до 31 десятичного разряда теми же самыми подпрограммами. Скорость обработки при этом уменьшится.

Выполнение точных вычислений в PL/1

Вернемся к простейшему примеру точных вычислений, теперь на языке PL/1, добавив деление на ту же константу, чтобы вернуть исходное значение переменной. Вычисления проведем и для типа FIXED DECIMAL и для типа FLOAT(53) аналога типа double в других языках.

test:proc main;dcl x fixed decimal(6,3);x=1.3;x=x*0.13;put skip data(x);x=x/0.13;put skip data(x);dcl y float(53);y=1.3;y=y*0.13;put skip data(y);y=y/0.13;put skip data(y);end test;

Результат вычислений представлен на рисунке.

Последовательное умножение и деление на одно и то же число для типа FIXED DECIMAL вернуло точное исходное значение переменной, а для типа FLOAT - нет. Хотя, если, например, сначала разделить на три переменную типа FIXED DECIMAL, а затем умножить на три, может появиться вынужденная погрешность, обусловленная невозможностью точно представить рациональное число одна треть десятичной дробью.

Таким образом, аппарат точных вычислений, встроенный в язык PL/1, достаточно прост, компактен, легко реализуется в системной библиотеке и всегда готов к применению. Но иногда такие возможности играют злую шутку с программистами, ранее имевших дело только с целыми и действительными числами и даже не подозревающими о наличии в языке точных вычислений. Например, если в программе на PL/1 в числовой константе нет показателя степени E и при этом явно не указано на преобразование в тип FLOAT, то по умолчанию считается, что требуется точное представление и точные вычисления. Поэтому, например, выражение 25.0+1/3 даст исключение переполнения при выполнении, поскольку транслятор разместит рациональное число 1/3 с максимальной точностью (т.е. займет все допустимые 15 десятичных разрядов) и потом добавить еще два разряда целой части результата сложения будет уже некуда. В то же время выражение 25.0+1Е0/3 будет вычислено приближенно и никакого переполнения не произойдет.

Все эти особенности становятся понятными и логичными, если программист ясно представляет, какой нецелый результат ему нужен в данном месте программы: точный или достаточно приближенного. Если в языке есть только целые и действительные приближенные числа, таких сложностей не возникает, но тогда возникают вопросы при необходимости провести точные вычисления с дробной частью.

Заключение

Хранить деньги, т.е. проводить расчеты, избегая округлений, лучше всего на языках, специально разработанных для решения экономических задач типа Кобола или PL/1 или Бухгалтерия 1С. Однако как показано выше, реализация средств точных вычислений достаточно проста и практически на любом языке можно самостоятельно создать свой аппарат такой обработки. Например, в книге [4] приводится пример организации вычислений со сверхточностью и в сверхдиапазоне. Процессоры архитектуры IA-32 даже имеют специальные команды, облегчающие арифметические вычисления без округлений. Правда в 64-разрядном режиме используемая для этой цели пара команд DAA/DAS становится недоступной, однако это не сильно затруднит реализацию, поскольку такие команды несложно эмулировать программно, например:

;--------------- ЭМУЛЯЦИЯ DAA, ЗАПРЕЩЕННОЙ В РЕЖИМЕ X86-64 ------------------PUBLIC DAA_X86_64:      PUSH      RDX,RAX      LAHF      MOV       EDX,EAX         ;OLD CF И OLD AL      AND       AH,NOT 1B       ;СБРОСИЛИ CF;---- ОБРАБОТКА МЛАДШЕЙ ТЕТРАД ----      TEST      AH,10000B       ;ЕСЛИ ЕСТЬ AF      JNZ       @      PUSH      RAX      AND       AL,0FH      CMP       AL,9            ;ИЛИ ЕСЛИ ЦИФРА БОЛЬШЕ 9      POP       RAX      JBE       M2270@:    ADD       AL,6            ;КОРРЕКЦИЯ ЦИФР      OR        AH,10000B       ;УСТАНАВЛИВАЕМ AF;---- ОБРАБОТКА СТАРШЕЙ ТЕТРАД ----M2270:TEST      DH,1B           ;ЕСЛИ СТОЯЛ OLD CF      JNZ       @      CMP       DL,99H          ;ИЛИ НУЖЕН ПЕРЕНОС      JBE       M2271@:    OR        AH,1B           ;УСТАНАВЛИВАЕМ CF      ADD       AL,60H          ;КОРРЕКЦИЯ ТЕТРАД;---- ПИШЕМ ГОТОВЙ БАЙТ И ВОССТАНАВЛИВАЕМ РЕГИСТР И ФЛАГИ ----M2271:SAHF      MOV       [RSP],AL      POP       RAX,RDX      RET

Основой точных вычислений является точное представление чисел в памяти компьютера. Двоично-десятичное представление позволяет легко организовать точные вычисления для чисел любой длины, т.е. любой точности. Проверено на практике, что для большинства экономических расчетов вполне хватает длины в 15 десятичных разрядов.

Литература

1. Д.Р. Джадд Работа с файлами. Издательство Мир Москва, 1975

2. http://msdn.microsoft.com/ru-ru/library/system.decimal.aspx

3. Д. Караваев К вопросу о совершенствовании языка программирования. RSDN Magazine #4 2011

4. Л.Ф. Штернберг Ошибки программирования и приемы работы на языке ПЛ/1, Москва Машиностроение, 1993

Введение

Еще в 1964 году известный специалист Дональд Кнут предложил простой тест [1], названный им Man or boy? (в вольном переводе взрослый или детский?) для проверки трансляторов с языка Алгол-60.

Тест выглядел так:

beginreal procedure A(k,x1,x2,x3,x4,x5); value k; integer k; begin real procedure B; begin k:=k-1; B:=A:=A(k,B,x1,x2,x3,x4); end B; if k<=0 then A:=x4+x5 else B; end A;outreal(A(10,1,-1,-1,1,0);end;

Смысл теста в построении в памяти дерева из рекурсивных вызовов процедур A и B, причем каждый вызов должен вычисляться в нужном контексте, иначе конечный результат (в оригинальном примере -67 для начального числа, равного 10) недостижим. Начальное число N при запуске теста определяет максимальную глубину дерева вызовов как 2^(N-1).

Тест оказался удачным как для демонстрации возможностей языковых средств, так и для оценки ресурсов, предоставляемых операционными системами, поэтому он переведен на разные языки [2], а допустимое начальное число на больших системах намного превысило первоначальное значение 10.

Часть первая, 32-х разрядная. Рекорд почти не виден.

Автор статьи также решил проверить используемую им систему на PL/1, скопировав соответствующий пример на этом языке из [2]. Утверждалось, что пример корректно работал в трех разных средах: OS PL/I V2.3.0, Enterprise PL/I V3R9M0 и PL/I for Windows V8.0, при этом допустимое начальное число достигало значений 15, 23 и 26 соответственно.

Однако для испытуемого компилятора PL/1-KT [3] ничего не вышло, поскольку при передаче параметра-ссылки на процедуру он автоматически не передавал соответствующий контекст, т.е. по терминологии Кнута представлял собой детскую систему.

Это фиаско заставило проанализировать задачу в целом и попытаться спасти лицо следующим образом:

а) решить задачу средствами языка не подражая алгольной записи. Имевшийся пример не сработал, но в стандарте PL/1 и не оговорено, что передача ссылки на процедуру должна вызывать передачу или запоминание ее контекста, хотя очевидно, что приведенные выше компиляторы сделали это. В случае если не удастся превзойти результаты, полученные этими взрослыми компиляторами, их действительно придется признать умными. Однако если все-таки удастся получить лучший результат, значит, они не оптимально использовали ресурсы и ценность их ума становится не очевидной.

б) полностью мобилизовать все ресурсы операционной системы на решение данной задачи. Во-первых, это необходимое условие получения наилучшего результата, а во-вторых, и это главное, примененные методы мобилизации ресурсов (памяти) в дальнейшем можно будет использовать в реальных задачах.

Были приняты также следующие ограничения:

1. Тест должен выполняться на заурядном, доступном компьютере с обычной операционной системой. Конкретно был взят ультра ноутбук SONY с процессором Intel Solo 1,33 ГГц и 1 Гб ОЗУ. Операционная система Windows Vista Business. Хотя время выполнения данного теста не считается определяющим, оно должно было быть приемлемым.

2. Тест должен иметь нормальный ввод и вывод и выполняться в реальной рабочей, а не искусственной среде. Например, практически все программы не могут обойтись без загрузки стандартных библиотек вроде kernel32.dll, хотя в данном случае (ответ - единственное значение) можно было бы обойтись даже без стандартного вывода.

Алгоритмически тест должен быть решен исключительно стандартными средствами языка. Очевидно, что заведомо наилучшие результаты дал бы ассемблер, но тогда теряется весь смысл теста как проверки языка.

Наоборот, задача мобилизации ресурсов должна решаться не языковыми средствами, а модернизацией системной библиотеки и настройкой операционной среды, поскольку в самом языке (в данном случае в PL/1) допустимый размер ресурсов не определен.

Решение теста Кнута

Общая идея новой реализации теста Кнута на PL/1 такова:

1. Моделируется стековая память как массив структур. Индексом такого массива является вложенность процедуры А. При очередном вызове А вложенность увеличивается, при выходе из А уменьшается.

2. Вложенность полностью определяет текущий контекст вызова А и В и задается как параметр процедуры B.

3 Вложенность каждого вызова добавляется также к параметрам процедуры А как явное указание контекста вызовов, т.е. вместо 6 у нее становится 11 параметров.

Такой подход позволяет отказаться от формального объявления в программе процедур А и В рекурсивными, хотя фактически они продолжают оставаться таковыми. При этом выключается умное запоминание рекурсивных данных средствами компилятора и остается только явно заданное программистом. Собственно стек требуется теперь лишь для хранения адресов возврата из процедур А и В.

На одну пару вызовов А и В потребуется 4+4 байт адресов возврата, 4 байта для текущего значения начального числа, 4х4 байт для вызовов-параметров и 4х4 байт для их контекстов (пятый вызов и его контекст как будет показано ниже не требует запоминания). Итого получается 44 байта. Тогда для выполнения теста с "рекордным" начальным числом 27 потребуется глубина в 2²⁶ пар вызовов или 2,952,790,016 байт. Учитывая, что 32-х разрядная Windows позволяет выделять программам до 3 Гбайт виртуальной памяти, расчет с начальным числом 27 становится принципиально возможным.

Выделение памяти для теста Кнута

При задании ключа /3GB в файле BOOT.INI Windows XP, или при выполнении команды bcdedit /set increaseuserva 3221225471 для 32-х разрядной Windows Vista и Windows-7, операционная система выделяет программе до 3 Гбайт виртуальной памяти, при условии, что в заголовке EXE-файла установлен ключ IMAGE_FILE_LARGE_ADDRESS_AWARE.

Однако возникает проблема непрерывного пространства, поскольку обычно системные библиотеки типа kernel32.dll или user32.dll продолжают загружаться в конец второго, а не третьего гигабайта, разбивая свободную память на две неравные области. В данном случае, дело облегчалось тем, что для теста область стека можно задавать отдельно от области, выделяемой для массива структур.

Первая задача, которую нужно было решить это сделать доступной программе на PL/1 (т.е. операторам ALLOCATE и FREE) области памяти и ниже и выше системных библиотек. Поскольку куча в данной реализации PL/1 представляет собой двунаправленный связанный список фрагментов памяти с отметкой занятых и свободных, данная задача решилась легко: области, занятые системными библиотеками, просто помечались как занятые до конца работы программы, для чего в конце доступных областей создавались дополнительные фиктивные ссылки на занятые области.

Некоторую проблему составило и то, что автор сразу не догадался, как определить наибольший размер непрерывной свободной области, который можно указать при выделении памяти с помощью процедуры Win-32 API VirtualAlloc. Поэтому просто задавался максимально возможный размер памяти при обращении к VirtualAlloc. Если запрос не получался, размер уменьшался на 50% от предыдущей попытки, если получался захваченная область тут же освобождалась обращением к VirtualFree, и размер увеличивался на 50% от предыдущей попытки. Такими итерациями быстро находятся все свободные области с заданной точностью (конкретно задана точность в 1 Мбайт). Затем все найденные области сортируются в порядке возрастания адресов, и из них составляется связанный список свободных с автоматическим созданием фиктивных смежных занятых областей, обходящих адресное пространство системных библиотек.

Все эти действия были вставлены внутрь системной библиотеки PL/1 и теперь автоматически выполняются при каждом запуске любой PL/1-программы. В результате доступная для использования куча в программах возросла почти до 3200 Мбайт.

Однако наличие двух даже больших не смежных областей памяти все равно не позволяло выделить область для массива из 2²⁶ элементов по 36 байт каждый, т.е. размером 2416 Мбайт, поскольку размер одной области стал около 2140 Мбайт, а второй 1073 Мбайт. Поэтому операторами ALLOCATE приходится выделять память для теста по частям:

1. Сначала оператором ALLOCATE выделяется необходимая область для стека размером 8х2²⁶ байт плюс некоторый резерв для служебных целей. Поскольку в PL/1-KT возможно прямое обращение к регистрам [3], адрес вершины выделенной области прямо присваивается регистру стека ESP.

2. С помощью имеющейся в PL/1-KT служебной процедуры определения максимального размера непрерывной свободной области MAXWDS находится и затем оператором ALLOCATE захватывается оставшийся наибольший непрерывный фрагмент свободной памяти. Очевидно, что это опять будет фрагмент из первой области, так как после выделения стека в ней еще останется почти 1.5 Гбайт.

3. Опять с помощью процедуры MAXWDS находится и затем захватывается самая большая из оставшихся свободными областей. Очевидно, что в данном случае это будет вся область в третьем гигабайте.

В результате из кучи выделена гарантированно непрерывная область для стека и две не смежные области для массива (адреса первой области ниже адресов второй), сумма которых достаточна для выполнения теста с начальным числом 27.

Далее используется допустимость описания в PL/1 базированных массивов, поскольку в качестве базы можно задавать не только указатель, но и процедуру без параметров, возвращающую указатель. В этом случае компилятор будет автоматически генерировать вызов такой процедуры при каждом обращении к массиву. Сама процедура-указатель написана так, как показано на рис. 1: если текущий индекс массива X1 входит в первую выделенную область памяти, процедура-указатель возвращает указатель P1 на первую область, а компилятор генерирует смещение A1. Если же индекс X2 массива превышает размер первой области, процедура-указатель вернет фиктивный указатель P3, равный указателю на вторую область P2 минус размер первой области. В точке обращения компилятор генерирует смещение массива A2 и прибавит его к фиктивному указателю P3, получив тем самым доступ к нужному элементу.

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

Исходный текст реализации теста Кнута на языке PL/1-KT

Исходный текст приведен ниже. Он должен лишь убедить читателей, что никакого обмана в проведении вычислений нет, действительно создается дерево вызовов. В программе присутствует ряд несущественных деталей, позволяющих контролировать ход вычислений. Замысловатые действия при вычислении суммы X4+X5 связаны с экономией памяти. Ссылка на X5 нужна лишь один раз, но перед этим необходимо вычислить X4 (если сначала вычислять X5, а затем X4, изменится число шагов теста). Поэтому ссылка на X5 запоминается на месте X4, а контекст X5 на месте контекста X4. Потом на этом же месте контекста запоминается результат вычисления X4, а находившийся там ранее контекст с помощью оператора обмена перемещается в переменную Z. Все это позволяет не выделять память или стек для хранения промежуточного результата сложения X4 и X5, а также память для хранения однократно требующейся ссылки на X5 и ее контекста. Иначе пришлось бы увеличивать размер элемента массива еще на 12 байт.

// РКК "'ЭНЕРГИЯ" ТЕСТ НА ВОЗМОЖНОСТИ СИСТЕМ "ВЗРОСЛЙ ИЛИ ДЕТСКИЙ"// ОТДЕЛ ??? СЕКТОР ??? ИCПOЛHИTEЛЬ: КАРАВАЕВ ЯЗK PL/1-KT// MOДУЛЬ MORB BEPCИЯ 1.0 ДATA COЗДAHИЯ 13.5.2012// ИCПOЛЬЗУEME MATEPИAЛ: HTTP://EN.WIKIPEDIA.ORG/WIKI/MAN_OR_BOY_TEST// ВНЕСЕННЕ ИЗМЕНЕНИЯ:// МОДУЛЬ ВПОЛНЯЕТ ТЕСТ ДОНАЛЬДА КНУТА// ДЛЯ ДОСТИЖЕНИЯ БАЗ=27 НЕОБХОДИМО ЗАПУСКАТЬ WINDOWS-XP C КЛЮЧОМ /3GB// ВНУТРИ BOOT.INI ИЛИ С КОМАНДОЙ BCDEDIT /SET INCREASEUSERVA=3221225471 ДЛЯ// WINDOWS-VISTA ИЛИ WINDOWS-7MORB: PROC(БАЗА) MAIN;DECLARE//---- НАЧАЛЬНОЕ ЧИСЛО ТЕСТА ИЗ КОМАНДНОЙ СТРОКИ (ПО УМОЛЧАНИЮ НОЛЬ) ----БАЗА CHAR(*) VAR,//---- ЗАДАВАЕМЕ РЕСУРС В PL/1-KT ----?MEMORY FIXED(31) EXT INIT(-1), // ИСПОЛЬЗУЕМ ВСЮ ПАМЯТЬ?MEM_ALL FIXED (7) EXT INIT(1), // НЕ СМЕЖНМИ УЧАСТКАМИ//---- СЛУЖЕБНЕ ПРОЦЕДУР PL/1-KT ----MAXWDS RETURNS(FIXED(31)), // ПОДСЧЕТ МАКСИМАЛЬНОГО УЧАСТКА//---- ТАБЛИЦА СОБСТВЕННХ ЗНАЧЕНИЙ И КОНТЕКСТОВ ----1 ТАБЛИЦА (1:2) BASED(АДР_ТАБЛ()), // РАЗМЕРНОСТЬ 1:2 ФИКТИВНА2 KK FIXED(31), // ТЕКУЩЕЕ ЗНАЧЕНИЕ НАЧАЛЬНОГО ЧИСЛА2 (XX1, // ВЗОВ XX2, XX3, XX4) ENTRY(FIXED(31)) RETURNS(FIXED(31)),2 (NN1, NN2, // КОНТЕКСТ NN3, NN4) FIXED(31),//---- ПАМЯТЬ, ВДЕЛЕННАЯ 1 УЧАСТКУ ----P1 PTR, // УКАЗАТЕЛЬ НА 1 УЧАСТОКДЛН1 FIXED(31), // ДЛИНА 1 УЧАСТКА В СТРОКАХ ТАБЛИЦ//---- ПАМЯТЬ, ВДЕЛЕННАЯ 2 УЧАСТКУ ----P2 PTR, // УКАЗАТЕЛЬ НА 2 УЧАСТОКF2 FIXED(31) DEF(P2), // ОН ЖЕ КАК ЦЕЛОЕ ДЛЯ АДРЕСНОЙ АРИФМЕТИКИДЛН2 FIXED(31), // ДЛИНА 2 УЧАСТКА В СТРОКАХ ТАБЛИЦP2_ФИКТ PTR, // ФИКТИВНЙ АДРЕС НАЧАЛА 2 УЧАСТКАF2_ФИКТ FIXED(31) DEF(P2_ФИКТ), // ОН ЖЕ КАК ЦЕЛОЕДЛН FIXED(31), // ОБЩЕЕ ЧИСЛО СТРОК ТАБЛИЦ ДЛЯ КОНТРОЛЯ//---- ВЛОЖЕННОСТЬ ВЗОВОВ ПРОЦЕДУР A ----N FIXED(31), // ТЕКУЩАЯ ВЛОЖЕННОСТЬИНДЕКС FIXED(31), // ВЛОЖЕННОСТЬ КАК ИНДЕКС ТАБЛИЦ//---- УКАЗАТЕЛЬ НА ОБЛАСТЬ СТЕКА ----P4 PTR, // УКАЗАТЕЛЬ НА НАЧАЛО ОБЛАСТИ СТЕКАF4 FIXED(31) DEF(P4), // ОН ЖЕ КАК ЦЕЛОЕ ДЛЯ АДРЕСНОЙ АРИФМЕТИКИ?ESP FIXED(31), // ДЛЯ ПРЯМОГО ДОСТУПА К ESP В PL/1-KTРАЗМ_СТЕК FIXED(31), // РАЗМЕР СТЕКА//---- РАБОЧИЕ ПЕРЕМЕННЕ И СЧЕТЧИКИ ----I FIXED(31), // НАЧАЛЬНОЕ ЧИСЛО ЗАПУСКА ТЕСТАL FIXED(31), // КОНЕЧНЙ ОТВЕТ ТЕСТАZ FIXED(31), // ОТВЕТ ПРОЦЕДУР AJ FIXED(31); // СЧЕТЧИК ДЛЯ ВДАЧИ НА ДИСПЛЕЙ//---- ВДАЧА ШАПКИ ----PUT SKIP(2) LIST('^I^IТЕСТ "MAN OR BOY", ВЕРСИЯ',?DATE);//---- ВВОД НАЧАЛЬНОЙ БАЗ ИЗ КОМАНДНОЙ СТРОКИ ----IF LENGTH(БАЗА)>0 THEN I=БАЗА;//----------------- ВДЕЛЕНИЕ РЕСУРСОВ ДЛЯ РАБОТ ТЕСТА ---------------------PUT SKIP(2) EDIT(TOTWDS,' ДОСТУПНХ СЛОВ ПАМЯТИ, ВДЕЛЕНО:') (P'ZZZ,999,999,999',A);PUT SKIP;//---- ВДЕЛЯЕМ МАКСИМАЛЬНУЮ ПАМЯТЬ ДЛЯ СТЕКА ----РАЗМ_СТЕК=2**26*8+1024*1024; // ДЛЯ БАЗ 27ALLOCATE(РАЗМ_СТЕК) SET(P4); // ВДЕЛЯЕМ МЕСТО ДЛЯ СТЕКА?ESP=F4+РАЗМ_СТЕК; // ВЕРШИНУ - ПРЯМО В РЕГИСТР ESP//---- ВДЕЛЯЕМ ПАМЯТЬ (1 УЧАСТОК) ДЛЯ ТАБЛИЦ КОНТЕКСТОВ ----ДЛН1=MAXWDS*2; // БЕРЕМ МАКСИМАЛЬНЙ НЕПРЕРВНЙ УЧАСТОКALLOCATE(ДЛН1) SET (P1); // ВДЕЛЯЕМ ЕГО КАК 1 УЧАСТОКДЛН1=ДЛН1/36; // ПЕРЕВЕЛИ В ЧИСЛО СТРОК 1 УЧАСТКАPUT SKIP EDIT(ДЛН1,' СТРОК ТАБЛИЦ 1 УЧАСТКА')(P'ZZZ,ZZZ,999,999',A);//---- ВДЕЛЯЕМ ПАМЯТЬ (2 УЧАСТОК) ДЛЯ ТАБЛИЦ КОНТЕКСТОВ ----ДЛН2=MAXWDS*2; // БЕРЕМ МАКСИМАЛЬНЙ НЕПРЕРВНЙ УЧАСТОКALLOCATE(ДЛН2) SET(P2); // ВДЕЛЯЕМ ЕГО КАК 2 УЧАСТОКДЛН2=ДЛН2/36; // ПЕРЕВЕЛИ В ЧИСЛО СТРОК 2 УЧАСТКАPUT SKIP EDIT(ДЛН2,' СТРОК ТАБЛИЦ 2 УЧАСТКА')(P'ZZZ,ZZZ,999,999',A);//---- ПОЛУЧАЕМ ЗНАЧЕНИЯ ДЛЯ УСКОРЕНИЯ ВЧИСЛЕНИЙ ----ДЛН=ДЛН1+ДЛН2; // ОБЩЕЕ ЧИСЛО СТРОК ДЛЯ КОНТРОЛЯ ИНДЕКСАF2_ФИКТ=F2-ДЛН1*36; // ФИКТИВНОЕ НАЧАЛО 2 УЧАСТКАPUT SKIP(2) LIST('-'(40),'^M');//------------------------- ЦИКЛ ЗАПУСКОВ ТЕСТА ----------------------------DO I=I TO 27; // ОТ ЗАДАННОГО ЧИСЛА ИЛИ НУЛЯ ДО МАКСИМАЛЬНОГО   //---- ВДАЛИ ЗАГОЛОВОК ---- PUT SKIP EDIT(TIME,' ЗАПУСК С НАЧАЛЬНМ ЧИСЛОМ =',I)(A,A,F(2)); PUT SKIP; //---- СОБСТВЕННО РАСЧЕТ (ВНУТРИ ЕСТЬ ВДАЧА НА ДИСПЛЕЙ) ---- L=A((I), X1,0, X2,0, X3,0, X4,0, X5,0); //---- ВДАЧА ОТВЕТА ---- PUT LIST(' '(20),'^M'); PUT SKIP EDIT(TIME,'БАЗА = ', I,L)(A(8),X(1),A,P'z9b',P'---,---,---,--9'); PUT SKIP LIST('-'(40),'^M');END I;//------------------- ПЕРВАЯ РЕКУРСИВНАЯ ПРОЦЕДУРА ТЕСТА --------------------A:PROC(K,X1,N1,X2,N2,X3,N3,X4,N4,X5,N5) RETURNS(FIXED(31));DECLAREK FIXED(31), // БАЗОВОЕ ЧИСЛО(X1,X2,X3,X4,X5) ENTRY(FIXED(31)) RETURNS(FIXED(31)), // ВЗОВ(N1,N2,N3,N4,N5) FIXED(31); // НОМЕР КОНТЕКСТА ВЗОВОВ//---- УВЕЛИЧИВАЕМ ВЛОЖЕННОСТЬ ПРОЦЕДУР A ----N+=1;//---- ПРОВЕРКА ПЕРЕПОЛНЕНИЯ ТАБЛИЦ СОБСТВЕННХ ЗНАЧЕНИЙ ----IF N>ДЛН THEN PUT SKIP LIST('ТАБЛИЦА',STOP);//---- ВВОДИМ ТЕКУЩЕЕ СОСТОЯНИЕ ТЕСТА НА ДИСПЛЕЙ ----J+=1;IF J>8191 THEN // НЕ НА КАЖДОМ ЦИКЛЕ ДЛЯ СКОРОСТИ {; J=0; PUT EDIT(TIME,' ',N,'^M')(A,A,P'ZZZ,999,999',A); };//-------------------- САМО ВПОЛНЕНИЕ РЕКУРСИВНОГО ТЕСТА -------------------//---- СОХРАНЯЕМ ОЧЕРЕДНЕ СОБСТВЕННЕ ЗНАЧЕНИЯ ПРОЦЕДУР A ----ИНДЕКС=N; // ДЛЯ ВДАЧИ АДРЕСА 1/2 УЧАСТКАXX1(N)=X1; // ЗАПОМИНАЕМ ВЗОВXX2(N)=X2;XX3(N)=X3;XX4(N)=X4;NN1(N)=N1; // ЗАПОМИНАЕМ КОНТЕКСТ ВЗОВОВNN2(N)=N2;NN3(N)=N3;NN4(N)=N4;KK (N)=K; // ЗАПОМИНАЕМ ТЕКУЩЕЕ БАЗОВОЕ ЧИСЛОIF K<=0 THEN // ИЩЕМ СУММУ ВЗОВОВ X4 И X5 {; XX4(N)=X5; // \ ЗАПОМНИЛИ ВЗОВ NN4(N)=N5; // / И КОНТЕКСТ #5 Z=X4(N4); // ВПОЛНИЛИ ВЗОВ #4 В КОНТЕКСТЕ #4 ИНДЕКС=N; // ДЛЯ ВДАЧИ АДРЕСА 1/2 УЧАСТКА NN4(N)<=>Z; // ЗАПОМНИЛИ РЕЗУЛЬТАТ #4 И ДОСТАЛИ КОНТЕКСТ #5 Z=XX4(N)(Z); // ВПОЛНИЛИ ВЗОВ #5 В КОНТЕКСТЕ #5 ИНДЕКС=N; // ДЛЯ ВДАЧИ АДРЕСА 1/2 УЧАСТКА Z+=NN4(N); // ЗНАЧЕНИЕ X4+X5 }; ELSE Z=B((N)); // ИНАЧЕ РЕКУРСИВНО ОБРАЩАЕМСЯ К ПРОЦЕДУРЕ B//---- УМЕНЬШАЕМ ВЛОЖЕННОСТЬ A ----N-=1;//---- ВХОДИМ С ОТВЕТОМ ----RETURN(Z);//-------------------- ВТОРАЯ РЕКУРСИВНАЯ ПРОЦЕДУРА ТЕСТА -------------------B:PROC(Y) RETURNS(FIXED(31));DCL Y FIXED(31); // ТЕКУЩИЙ КОНТЕКСТ ВЗОВАИНДЕКС=Y; // ДЛЯ ВДАЧИ АДРЕСА 1/2 УЧАСТКАKK(Y)-=1; // УМЕНЬШАЕМ БАЗОВОЕ ЧИСЛО НУЖНОГО СОСТОЯНИЯ//---- РЕКУРСИВНО ВЗВАЕМ ПЕРВУЮ ПРОЦЕДУРУ ----RETURN(A(KK(Y),B,Y,XX1(Y),NN1(Y),XX2(Y),NN2(Y),XX3(Y),NN3(Y),XX4(Y),NN4(Y)));END B;END A;//------------ ПРОЦЕДУРА ВДАЧИ АДРЕСА 1 ИЛИ 2 УЧАСТКА ТАБЛИЦ --------------АДР_ТАБЛ:PROC RETURNS(PTR);//---- ЕСЛИ ИНДЕКС ВНУТРИ 1 УЧАСТКА ПАМЯТИ ----IF ИНДЕКС<=ДЛН1 THEN RETURN(P1); // ВОЗВРАЩАЕМ ССЛКУ НА 1 УЧАСТОК//---- ЕСЛИ ИНДЕКС ВНУТРИ 2 УЧАСТКА ПАМЯТИ ----RETURN(P2_ФИКТ); // ВОЗВРАЩАЕМ ФИКТИВНОЕ НАЧАЛО 2 УЧАСТКАEND АДР_ТАБЛ;//---------------------- ВЗОВ НАЧАЛЬНХ ЗНАЧЕНИЙ --------------------------X1:PROC(Y) RETURNS(FIXED(31)); DCL Y FIXED(31); RETURN( 1); END X1;X2:PROC(Y) RETURNS(FIXED(31)); DCL Y FIXED(31); RETURN(-1); END X2;X3:PROC(Y) RETURNS(FIXED(31)); DCL Y FIXED(31); RETURN(-1); END X3;X4:PROC(Y) RETURNS(FIXED(31)); DCL Y FIXED(31); RETURN( 1); END X4;X5:PROC(Y) RETURNS(FIXED(31)); DCL Y FIXED(31); RETURN( 0); END X5;END MORB;

Результаты работы теста

Результат приведен на рис. 2. Тест с начальным числом 27 выполнился менее, чем за 9 минут, получив значение -46750171 и построив для этого дерево глубиной 67 миллионов вложенных вызовов процедур А и В, а всего вызвав эти процедуры 292 миллиона раз. Поскольку компьютер имел лишь 1 Гбайт физической памяти, происходило обращение к диску, что существенно замедляло работу.

Заключение

Конечно, можно считать, что тест на взрослость все-таки в части рекурсии не выполнен, поскольку не удалось записать алгоритм в коротком алголоподобном стиле. Однако если обратиться к сути этой остроумной задачи (составление максимально возможного дерева в памяти и обход его), то окажется, что она выполнима на проверяемом компиляторе и даже с лучшими результатами, чем у взрослых компиляторов PL/1 (да, пожалуй, и всех других 32-х разрядных систем). Ведь ими был достигнут уровень 26 лишь на 64-х разрядной Windows-8 с 16 Гбайт оперативной памяти. Здесь же достигнут результат 27, уже близкий к теоретическому пределу для 32-х разрядных систем и при этом автор, занимаясь вроде бесполезной задачей, получил механизм использования памяти выше системных библиотек и метод обращения к единому массиву в не смежных областях памяти, пригодные уже не для искусственного теста, а для практического применения.

Часть вторая. 64-х разрядная. Опыты со стеком.

Описание теста Д. Кнута Man or boy? на сайте [2] мне попалось на глаза случайно, но очень увлекло. Помнится, в прекрасном произведении Три толстяка был один персонаж (цирковой) стрелок. Он во время погони увидел пролетающий воздушный шарик и сразу обо всем забыл, в том числе о погоне. Главное для него стало попасть в шар. Я стал в чем-то похож на этого стрелка (который, кстати, в шар так и не попал- помешала шляпа стоящего рядом директора). В ущерб работе и другим занятиям, главным для меня стало выполнить тест Кнута с хорошим результатом, т.е. максимально эффективно использовать доступные стек и память так, чтобы добиться правильного завершения теста с наибольшим базовым значением. Базовое значение теста по существу является показателем степени числа рекурсивно вложенных вызовов, если такое число представить в виде 2ⁿ.

Дело осложнялось тем, что компилятор, который я использую [3], не запоминает контекст вызова рекурсивных процедур и, по сути, вообще не может выполнить этот тест. Эти трудности были обойдены моделированием запоминания контекстов через обращение к массиву, а собственно аппаратный стек стал использоваться только для запоминания адресов возврата из рекурсивных процедур. Кроме этого, возникли сложности с фрагментацией памяти из-за фиксированного размещения системных библиотек Windows-XP, что не позволяло использовать все доступные 3 Гбайт памяти как одну непрерывную область. Но и эти сложности были преодолены. Результаты я представил в статье (см. часть 1) и был очень горд тем, что смог выполнить на обычном и слабом ноутбуке тест с базовым значением 27, что на тот момент являлось мировым рекордом среди всех результатов, перечисленных на сайте [2].

Поскольку этот сайт постоянно обновляется и дополняется, я года полтора продолжал считать себя действующим чемпионом по выполнению теста Кнута, хотя и отдавал себе отчет в том, что, например, массовый переход на Win64 изменит эту ситуацию. И вот на сайте появилось сообщение, что тест, написанный на Haskell, выполнен для базового значения 30. Таким образом, по использованным ресурсам мой рекорд был превзойден сразу в восемь раз, а я превратился в экс-чемпиона. Разумеется, новый рекорд был установлен не на маленьком домашнем ноутбуке c 32-разрядной Windows, а на солидном AMD Opteron 6282SE c 384 Гбайт доступной памяти в куче.

Но и я к тому времени приобрел для дома ноутбук c Intel Core i5-3210M, c 4 Гбайт памяти и домашней Windows 7 и занялся переводом своих средств разработки на Win64. Естественно, что первым тестом, который проверялся для доработанного компилятора, стал все тот же тест Кнута. С точки зрения языка PL/1, на котором я пишу, все получилось изящно в доработанном для Win64 компиляторе появилась возможность определять переменные как целые со знаком размером в 8 байт, т.е. с атрибутами BINARY FIXED(63), которыми и были заменены в исходном тексте теста (текст на PL/1 см. часть 1) все переменные, ранее имевшие тип BINARY FIXED(31). Кроме этого, появилось все-таки не два, а целых три не смежных участка памяти (из-за странной загрузки системных библиотек), а также вместо регистра ESP теперь необходимо использовать RSP. Ради интереса, я добавил и вывод максимальной глубины вложений.

В целом, сложности, которые пришлось преодолевать в Win32, остались и в Win64. Например, некоторые системные библиотеки вроде NTDLL.DLL или KERNEL32.DLL и в Windows 7 упорно не хотят загружаться в верхние адреса памяти, разбивая свободное адресное пространство на несколько не смежных фрагментов, хотя теперь потери при этом не превышают 1 Гбайт.

Однако самым сложным для меня оказалась работа с большим стеком. Даже психологически трудно после стольких лет работы с Win32 привыкнуть к тому, что для хранения указателя вершины стека реально нужно 8 байт. Помните старое заявление Билла Гейтса, что 640 Кбайт хватит для всех задач? Так вот, для выполнения теста Кнута с базовым значением 30 даже при моем построении алгоритма (напомню, в стеке хранится только дерево из адресов возврата двух рекурсивных процедур) для стека уже требуется 16*2²⁹=4294967296 байт. И это только для хранения адресов возврата! Но возникшую сложность работы со стеком я решил обратить себе на пользу и специально в разных других тестах, там, где таких больших значений не требовалось, начал устанавливать значение указателя стека больше 2³². Этот прием позволил быстро выявить все свои ошибки перевода с Win32 на Win64, связанные со стеком. И речь идет не просто о пропущенных в ассемблерных текстах системных подпрограмм ESP вместо требуемых теперь RSP, но и о более сложных связях. Тест Кнута неожиданно оказался прекрасной проверкой правильности средств разработки в среде Win64.

В результате мои программы стали более ошибкоустойчивы и как приятный бонус я вернул себе звание чемпиона мира, выполнив в Windows 7 тест с базовым значением 31.

Как следует из этого скриншота, через полтора часа после запуска теста глубина вложенных вызовов превысила миллиард. Т.е. при переходе на Win64 по сравнению с предыдущим лучшим своим результатом в Win32 удалось увеличить задействованные в программе ресурсы (память и стек) в 16 раз! Поскольку сами объекты теста (контексты вызовов, адреса возврата и возвращаемое значение) тоже увеличились с 4 до 8 байт, абсолютно использованные ресурсы (в байтах) увеличились по сравнению с Win32 даже в 32 раза.

Конечно, при этом тест считается не быстро из-за недостаточного размера физической памяти. Кстати, на этом же ноутбуке можно было бы в принципе выполнить и тест с базовым значением 32, но для этого пришлось бы освободить весь 250 Гбайтный диск для файла подкачки страниц (нужно более 200 Гбайт). Очевидно, что следующие рекорды нужно ставить не на домашних компьютерах. Ну, или подождать, пока ресурсы домашних компьютеров не достигнут соответствующих величин.

Наверняка у читателя назрел вопрос: зачем было нужно это соревнование автора с неведомыми ему соперниками? И не напоминает ли оно соревнование людоедки Эллочки с дочерью миллионера Вандербильда? Нет, не напоминает. Потому, что решение сложной задачи использования всех возможных ресурсов компьютера (пусть даже эти ресурсы и довольно скромны по современным понятиям), позволяет использовать затем эти же приемы в реальных задачах, о чем я уже и писал в предыдущей статье (часть 1).

В моем случае, приемы работы с большими массивами, размещенными к тому же в нескольких областях памяти, пригодились впоследствии при обработке больших объемов картографических данных. С помощью теста Кнута я научился реально использовать в программе всю доступную память.

И при достижении наилучших результатов элемент состязательности весьма важен. Поэтому призываю всех принять участие в чемпионате по выполнению теста Кнута. Как показывает мой опыт, время, потраченное на разработку новых приемов использования доступной памяти и стека, не пропадает даром.

P.S. Некоторые коллеги говорили мне, что, мол, время потрачено зря, результат теста Кнута, даже рекордный, можно легко вычислить и не прибегая к собственно выполнению алгоритма. Конечно можно, причем можно сразу вычислить результат теста для такого показателя, для расчета которого современным средствам потребуется больше времени, чем существует Вселенная. Но конечное число теста лишь квитанция, что он выполнен правильно, т.е. всю используемую память алгоритм обошел в правильном порядке. Именно так воспринимали этот тест (рекурсия, но, главное, сколько можно занять памяти) еще в Советском Союзе [4].

Литература

1. Donald Knuth (July 1964). Man or boy?. http://www.chilton-computing.org.uk/acl/applications/algol/p006.htm. Retrieved Dec 25,2009

2. http://rosettacode.org/wiki/Man_or_boy_test

3. Д.Ю.Караваев К вопросу о совершенствовании языка программирования RSDN Magazine #4 2011

4. https://keldysh.ru/papers/2013/prep2013_29.pdf

Введение

Начну с мелочи. Удобно ли сейчас организована типичная смена раскладки клавиатуры? В смысле переключения на русский/латинский? На мой взгляд, в смартфонах и то удобнее. Не надо нажимать одновременно все эти Shift и Alt. На моем первом домашнем компьютере Электроника-901 (он же ai-PC16) было даже две специальных пустых клавиши примерно там, где сейчас клавиши-окна. Одна переключала на русскую раскладку постоянно, а другая - временно (на время нажатия). Это гораздо удобнее. Впрочем, самый удобный вариант переключения в свое время я сделал сам из массивной педали от швейной машинки Тула, просто соединив ее двумя проводами с контактами DTR и DSR разъема RS-232. В этом случае если программно установить бит DTR в 1, то наличие сигнала DSR означает, что педаль нажата, иначе отпущена. Переключать раскладку без рук оказалось очень эргономично. Увы, по мере распространения новых интерфейсов, RS-232 постепенно сошел на нет и сейчас в ноутбуке педаль просто некуда подключить.

Кстати, дарю идею фирмам, выпускающим всякую USB-ерунду, вроде пластикового хамелеона, периодически высовывающего язык: выпустить USB-устройство в виде педали, при нажатии на которую эмулируются нажатия заданных пользователем клавиш. Правда уже есть USB-руль с педалями, но там все-таки много лишнего. Наиболее очевидное использование нового простого устройства переключение раскладки клавиатуры без помощи рук.

Справедливости ради: на некоторых клавиатурах есть отдельная клавиша переключения (на ней обычно нарисован глобус). Сложность в том, что на многих других компьютерах ее нет. В древнем текстовом редакторе SideKick я даже когда-то использовал обе клавиши Shift, поскольку они есть всегда: правая переключала постоянно (и поэтому как Shift вообще не работала), а левая временно, первые две секунды как Shift, а уже затем как переключатель. Смысл в том, что тогда можно печатать, например, по-русски, затем, удерживая мизинцем клавишу, одно слово по-английски, затем отпустить и опять продолжать по-русски.

Но, повторю, громоздкое переключение - это мелочь, не проблема, а, скорее, следствие отношения к использованию русского языка как к чему-то второстепенному и не стоящему внимания. Хотя и эта мелочь нет-нет, да и напомнит о себе, хотя бы в виде модной, но глупой аббревиатуры КВТ (вместо RSDN) на форумах сайта RSDN.RU.

Настоящей проблемой, на мой взгляд, является появление на тех же компьютерных форумах обсуждений на тему: мешает ли русский язык программированию. С точки зрения той части российских программистов, которые работают в западных фирмах или поставили себе такую цель (с возможным и желательным отъездом за границу) русский язык в программировании это действительно зло, дополнительный барьер, мешающий быстрее адаптироваться в англоязычной среде. Но мне кажется, им мешает не русский язык в программировании, а русский язык вообще.

Естественность использования родного языка

Язык неразрывно связан с мышлением. Например, когда я пишу текст программы, я невольно мысленно произношу требуемое действие. Конечно, оно не звучит внутри голосом Левитана и даже не всегда это именно звуки, но что-то типа: если и а и б нулевые, то уходим в мыслях проносится. На типичном современном языке программирования эту мысль в виде программного текста я должен выразить как-нибудь так:

if (a==0 && b==0) return;

Т.е. мысленно про себя произношу если, уходим, а писать все-таки должен if, return. Незаметно приходится все время переводить, пусть и в самой простейшей форме. Поэтому для меня более естественна запись того же оператора в виде:

если a=0 и b=0 тогда возврат;

Я именно так и пишу. И это вовсе не псевдокод, а реальный оператор языка [1], где ключевые слова имеют русские эквиваленты, не требуется различать присваивание и сравнение (а, значит, не нужно удвоение символов), и логические операции можно писать просто как И, ИЛИ, НЕ. Оператор больше стал похож на мысленную фразу и перевод с мысленного русского на программный английский уже не требуется.

Для человека, который давно программирует, наверное, все это кажется несущественным и непривычным, поскольку с самого начала он учился составлять программный текст как последовательность специальных знаков и слов, не связанных с родным языком. Да, язык программирования никогда не совпадет с родным языком, но на этапе освоения (например, в школе) элементы родного языка очень помогают понять записываемые действия. Больше становится тех, кто быстро схватил суть и меньше тех, кто сразу же теряет интерес к изучению программирования потому, что сталкивается с цепочками непонятных иероглифов и иностранных слов.

Например, когда моя жена училась в Московском математическом техникуме, основы программирования им преподавали с помощью специального языка (нечто вроде псевдокода), который так и назывался: Русский Алгоритмический Язык, сокращенно РАЯ. (Смешно. Выходит, в нашей семье жена знакома с языком РАЯ, а муж с языком Ада). На мой взгляд, это был мудрый прием. Родной язык, конечно, не панацея и не обеспечивал выпуск суперпрограммистов, но то, что он способствовал более глубокому пониманию основ на самом важном начальном этапе несомненно.

Разумные границы использования

Попытки превратить язык программирования в национальный или, наоборот, избавиться от национальных особенностей в тексте программы были предприняты еще более полувека назад. Я имею в виду языки Кобол и АПЛ.

Язык Кобол предполагал, что программу можно будет писать просто по-английски. Поэтому он имел большое число зарезервированных и даже шумовых (необязательных) слов. Но ничего хорошего из этого не вышло. Текст программ все равно получался не на английском, а на ломаном английском, а их анализ усложнялся. Точно так же не получится писать программы и на любом другом настоящем, например, русском языке, поскольку обычный язык никогда не будет тождественен программному. Однако наличие некоторого множества слов и их частых сочетаний на родном языке все же улучшает и на интуитивном уровне облегчает понимание текста программы, ведь, в конце концов, человек не сканер транслятора и не анализирует текст посимвольно.

Другую крайность представлял язык АПЛ, имевший большое число специальных знаков для всяких операций. Запись программы на АПЛ внешне напоминала записи, которыми пользуются математики. АПЛ остался в истории знаменитым тем, что программу, записанную на одной строке, т.е. не более 80 знаков, можно было анализировать часами, т.е. долго разгадывать, что же, собственно говоря, она делает. Получалось, что кроме авторов в таких программах вообще никто не мог разобраться, и идея сверхкомпактной записи большим числом специальных знаков была заброшена.

На мой взгляд, программные тексты должны иметь золотую середину между этими крайностями. Они, конечно, не должны быть слишком многословными и этим напоминающими старинные поваренные книги, но и шарады из цепочек значков и скобок (можно вспомнить Лисп, где встречалось до двадцати скобок подряд) это тоже не идеал. А если в тексте программы все же используются не одни значки, но и слова, то лучше, чтобы они были на родном языке.

Опыт использования родного языка

Если обратиться к собственному опыту использования родного языка, то считаю, что мне в какой-то мере даже повезло: период обучения и освоения пришелся на время, когда русский язык использовался не то, чтобы широко, но вполне естественно, поскольку применялись программные и аппаратные средства отечественной разработки. Как программист я начинал с БЭСМ-6, операционной системы ОС-Диспак, транслятора БЭСМ-АЛГОЛ и диалоговой программы Пульт (при этом работа за терминалом VT-340 очень напоминала работу за первыми персональными компьютерами). В те времена даже в кодовой таблице сначала шел русский алфавит, а затем латинские буквы, отличающиеся по написанию от кириллицы. Вся документация была, естественно, на русском, например, в описании команд БЭСМ-6 все аббревиатуры команд были кириллицей, не было никаких MOV или JMP.

В отличие от ЕС-ЭВМ, в направлении БЭСМ (и Эльбрус) все оставалось по-русски. Правда, до тех пор, пока не появилась разработка дубнинского ядерного центра мониторная система Дубна, в составе которой был ассемблер (тогда такие языки назывались автокодами) со странным именем Мадлен. Так как транслятор сначала переводил на него, некоторые сообщения об ошибках выдавались на уровне ассемблера. И все они были по-английски! Получалось, что одни советские программисты писали сообщения для других советских программистов не на родном языке. Разумеется, Дубна изначально была предназначена для совместной работы где-нибудь в ЦЕРН, поэтому там и было все в международном варианте. Но нам она была поставлена как отечественная система и при этом бесцеремонно отодвинула от родного языка. Например, аббревиатуры команд в Мадлен стали не такими как в исходной документации на БЭСМ-6, что вызывало непонимание и раздражение.

Еще через несколько лет (для меня в 1987 году) в части родного языка все перевернулось с появлением американских персональных компьютеров. Объективно и естественно в первое время никакого русского языка там не было в принципе. Но поскольку это требовалось для набора текстов, приспосабливать их под родной язык все-таки пришлось. Т.е. пришлось перепрошивать ПЗУ видеокарт, наклеивать переводные картинки кириллицы на боковые стенки клавиш, учиться писать драйверы клавиатуры, попутно привыкая к аббревиатурам системы команд x86. Очень скоро русификацией компьютеров и принтеров уже занимались во многих организациях, имеющих ПК, и дело было поставлено буквально на поток. Но при этом русификацией получаемых вместе с компьютерами трансляторов обычно никто не занимался, в лучшем случае лишь переводились руководства.

Возможно, я стал одним из первых, кто озаботился этим и то лишь потому, что полученный вместе с IBM-PC/XT транслятор с языка PL/1 не позволял писать по-русски даже комментарии: все символы с кодом больше 7FН воспринимались им как управляющие. Из-за этого на первых порах комментарии выглядели как теперешние SMS по-русски с телефонов, не имеющих кириллицы. Но разрабатывать программы, не используя родной язык, было для меня совершенно недопустимым. Первое исправление транслятора, которое разрешило кириллицу, оказалось очень легким и привело к мысли дизассемблировать весь транслятор, чтобы стать полноправным владельцем и постепенно сделать его целиком русским. Учитывая, что в PL/1 ключевые слова не зарезервированы, можно иметь одновременно два варианта слов: английский и русский. Поэтому уже написанные программы можно было оставить английскими, зато новые программы можно было писать уже по-русски.

Впоследствии в транслятор было внесено множество доработок, приведенных в [1]. По части русификации были добавлены русские ключевые слова, включая И-ИЛИ-НЕ вместо знаков &, ! и ~. Такой перевод логических операций на русский сразу сделал тексты программ гораздо легче воспринимаемыми. Диагностические сообщения также были переведены и расширены. Много ли существует современных программных средств, которые выдают сообщения об ошибках на русском языке? А ведь это первое, с чем сталкиваются новички. Им и так-то бывает нелегко разобраться, что именно вызвало ошибку, а тут еще и сообщения не на родном языке. Поэтому часто даже вполне внятные сообщения начинают восприниматься ими одинаково: транслятор ругается, а поиск ошибок в тексте производится бессистемным образом, вне связи с полученным сообщением.

В результате всех преобразований в части родного языка я практически вернулся в тот программный мир, в котором работал до эпохи ПК, тексты программ стали выглядеть даже лучше. Например, при записи программы (кроме имен импортируемых подпрограмм, всех этих GetEnhMetaFilePaletteEntries, выглядящих в русском тексте китайской грамотой) я практически вообще могу не переключаться на латинский алфавит. Само собой, идентификаторам всегда стараюсь дать значимые имена по-русски.

Но большинство программистов моего поколения перешли на языки с Си-образным синтаксисом и практически перестали использовать в текстах программ кириллицу.

Заключение

На первый взгляд кажется, что сейчас никаких проблем с русским языком нет. Действительно, давно локализованы на национальные языки операционные системы, офисные программы и игры, а кириллица наносится на клавиши заводским способом. Но если обратится к программированию, то здесь русский язык почти полностью вытеснен. Конечно, есть и исключения, например, Бухгалтерия 1С. При этом я ни в коем случае не призываю создавать специально русские языки программирования (остряки сразу же добавят: православные). Напомню, что даже в самом первом международном документе по языку программирования [2] предполагалось три уровня его представления: эталонный, язык публикаций и конкретные представления. Т.е. с самого начала предполагалось, что знаки языка могут быть различными в разных странах, однако должно быть сохранено однозначное соответствие с эталонным представлением.

Сам я использую язык PL/1, созданный на Западе (большей частью в Великобритании), наличие готового транслятора с которого было в свое время даже одним из аргументов принятия в СССР решения копировать IBM 360 в виде ЕС ЭВМ. Но, возможно, обоснованное на тот момент решение в своей программной части в дальнейшем не было подкреплено развитием первоначально скопированного эталона. Конечно, сейчас с позиции послезнания легко советовать, что надо было делать тогда. Впрочем, и тогда многим это было понятно: урок освоения ОС ЕС ясен: можно, и иногда нужно осваивать отдельные образцы зарубежного программного обеспечения, но нельзя становиться на путь постоянного следования за ними [3].

Мой опыт энтузиаста-дилетанта (без профильного образования), показывает, что разобраться в существующем компиляторе не так уж и трудоемко. Коллектив из 4-5 человек где-нибудь в Академгородке сделал бы это быстро и качественно, например, с компилятором IBM для PL/1. Т.е. дизассемблировал бы его и научился транслировать и собирать точную копию исходного. И это надо было делать, конечно, не для русификации, а для того, чтобы стать хозяином транслятора и с этой стартовой площадки продолжить его развитие дальше, уже независимо ни от кого, снабжая армию пользователей ЕС ЭВМ качественным и, главное, совершенствующимся продуктом. А перевод на русский язык компилятора и других утилит был бы всего лишь бонусом, облегчающим сопровождение и использование. Но транслятор с языка PL/1 на ЕС ЭВМ так и не был освоен. Я делаю такой вывод потому, что он так и не был русифицирован, хотя попытки развить язык и были [5].

Я освоил транслятор и сделал русификацию уже для ПК-версии языка, причем затраты на перевод на русский оказались пренебрежимо малы по сравнению с другими доработками транслятора. И при этом получилось то самое конкретное представление, совпадающее с эталонным, поскольку результат трансляции в виде объектного модуля уже ничем не отличается от результата трансляции исходного текста программы в эталонном виде. И, кстати, простейшим переводом всегда можно вернуться к эталонному представлению исходного текста программы, т.е. такие представления обратимы.

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

Однако, на мой взгляд, языки программирования имеют гораздо больше общих черт с обычными языками, чем абстрактное математическое или химическое представление. Если человек думает по-русски, в большинстве случаев он никогда не начнет думать по-английски. Запрещая использовать элементы родного языка при изучении основ программирования, мы изначально ставим наших школьников и студентов в отстающее положение по сравнению с их англоязычными сверстниками.

Зато появились уже поколения программистов, которые считают, что так и должно быть. Попадалась даже парадоксальная точка зрения, что не использование родного языка это как раз наше преимущество над англоязычными программистами, потому, что собственно конструкции операторов программы не похожи, например, на текст комментариев, а, дескать, у них все это смешивается. По такой логике надо предложить англоязычным использовать в программах русские ключевые слова, чтобы, так сказать, догнать нас. А лучше сразу перейти на китайские иероглифы, чтобы все (кроме, разумеется, несчастных китайцев) имели это преимущество непохожести исходного кода на родной язык .

Использование русского языка отражает и общее состояние дел в развитии программирования. Пока в СССР шли собственные разработки - использовался, естественно, и русский язык, например, в таком выдающемся проекте, как Эль-76, где были задействованы большие силы всей страны: в разработке ПО для Эльбруса участвовал ряд университетов, включая Таллин и Кишинев. Прекратились разработки вот русский язык и исчез, а попытки возрождения, например, проект Национальной Программной Платформы, терпят неудачу.

Русский язык это то, что всех нас (и программистов и не программистов) объединяет. Использование родного языка в программировании является и признаком независимого развития этой отрасли и одновременно объективной базой такого развития.

Напоследок приведу исторический анекдот: когда Петр Первый организовывал выпуск нового российского рубля (монеты), ему советовали все надписи сделать на латыни, иначе, мол, такие деньги не будут принимать за границей. Спасибо тому скажу, кто придумает, как оставить деньги в Отечестве, а не тому, кто выведет их иноземцам ответил Петр.

Литература

1. Д.Ю. Караваев К вопросу о совершенствовании языка программирования RSDN Magazine #4 2011

2. А.П. Ершов, С.С. Лавров, М.Р. Шура-Бура Алгоритмический язык АЛГОЛ-60. Пересмотренное сообщение. Москва Мир 1965

3. Г.С. Цейтин Доклад Итоги освоения ОС ЕС (заметки пользователя) 29.08.1983

4. В.М. Табаков Специализированная система гиперпрограммирования для языка ПЛ/1 : диссертация кандидата физико-математических наук : 05.13.11. Калинин, 1984.

Введение

Как-то на одном из компьютерных форумов участники делились соображениями, чего им не хватает в языках, так сказать, в повседневной деятельности. Один заявил, что ему очень не хватает оператора типа put data. Для тех, кто не слышал о таком, поясню, что в языке PL/1 был предусмотрен оператор вывода (или ввода) значений переменных вместе с их именами, т.е. вместе с идентификаторами.

Например, если обычный вывод put list(X,Y); давал что-нибудь вроде:

1280 1024

то оператор put data(X,Y); печатал:

X= 1280 Y= 1024

не заставляя писать для этого вывод в виде оператора:

put list(X=,X,Y=,Y);

Чаще всего это использовалось в отладочных целях, но не обязательно. Например, используя вывод в текстовый файл с помощью put data, а затем ввод этих же данных как исходных в другой программе с помощью зеркального оператора get data можно было получить удобную для чтения и редактирования форму представления исходных данных в текстовом виде.

Можно возразить, что современные оболочки систем программирования легко позволяют вывести значения (и имена) любых объектов программы в интерактивном режиме безо всяких put data и поэтому в нем больше нет необходимости.

Я тоже использую встроенный интерактивный отладчик, с помощью которого можно посмотреть любые, даже сложные (составные) данные. Однако потребность в возможностях put data не исчезла. Иногда нужен и анализ данных на распечатке, (т.е. в логе) с возможностью быстрого и удобного добавления в текст программы вывода для отладки. К тому же для работы отладочных интерактивных систем используется дополнительная информация, которая обычно в выполняемом exe-файле отсутствует. В этом же случае все имена переменных зашиты в самой программе. Таким образом, удобства, предоставляемые языком в виде оператора, подобного put data, не заменяют, а дополняют возможности отладчиков. Кстати, в стародавние времена так называемая посмертная выдача на печать после ошибки иногда включала в себя и вывод полного списка всех имен переменных вместе с их текущими значениями. Некоторым программистам так нравился такой вывод, что они специально в конце своей программы ставили деление на ноль.

Реализации ввода-вывода с именами

В исходном варианте компилятора, которым я пользуюсь и который по мере сил развиваю, оператора put data не было. И мне его тоже очень не хватало в процессе отладки. Требовалось его ввести, причем хотелось сделать все как можно проще, компактнее и не внося больших изменений в компилятор. Поэтому была принята следующая схема реализации:

1. Сначала компилятором выполняется обычный разбор очередного объекта, перечисленного в списке ввода-вывода. Но при этом все лексемы, которые выдал лексический анализатор по запросу компилятора, еще и запоминаются в специальном буфере. По окончании разбора результат (т.е. все получившиеся операции внутреннего представления программы) отбрасывается, но характеристики объекта, например, его имя в программе, размерность и т.п., становятся известны.

2. Затем разбор повторяется заново, теперь полученные операции внутреннего представления программы будут использованы для генерации кода. Однако при разборе вместо лексического анализатора подключается его эмулятор, который уже не проводит лексический анализ исходного текста, а просто достает и выдает компилятору разобранные ранее и запомненные лексемы. Кроме них эмулятор может выдать и новые, сгенерированные им самим, лексемы.

Получается, что компилятор как бы сам для себя на ходу изменяет и дописывает исходный текст программы и тут же исправленный текст обрабатывает штатным образом. В чем-то эти действия немного похожи на макроподстановку.

Для реализации put data достаточно проанализировать запомненные в буфере лексемы, найти конец разбираемого элемента (это запятая вне скобок или внешняя закрывающая скобка) и все предыдущие лексемы объединить в одну строку, которую в начале работы эмулятора и выдать с признаком текстовая константа.

В конце этой автоматически сформированной строки для наглядности дописывается знак равенства. После выдачи лексемы-строки эмулятор еще выдает лексему запятая, а затем начинает выдавать все лексемы из буфера. По исчерпанию лексем в буфере эмулятор вместо себя опять подключает настоящий лексический анализатор, т.е. тот, который продолжит чтение исходного текста, и компилятор становится готов к разбору следующего объекта ввода-вывода.

Таким образом, например, текст:

put data(x(i+1,j-1));

внутри компилятора будет восприниматься как:

put list(x(i+1,j-1)=,x(i+1,j-1));

Разумеется, так будут обрабатываться не только объекты-переменные, но и любые выражения при выводе. Исключение составляет лишь вывод текстовых констант. Для них дополнительные лексемы, конечно же, не формируются во избежание бессмысленного вывода одного и того же текста два раза подряд со знаком равенства посередине.

Ввод-вывод не скалярных объектов

Идея исправлять исходный текст программы на лету позволила легко решить поставленную задачу. Однако полученный механизм жаль было использовать только для такой мелочи как put data, поскольку этот же подход можно было применить и для более объемной задачи ввода-вывода не скалярных объектов. Автоматический ввод-вывод всех элементов не скалярного объекта также был предусмотрен в языке и тоже отсутствовал в исходной версии компилятора, хотя на практике часто требовался.

Здесь ситуация сложнее, чем с put data для скаляра, так как для вывода массива вместо текста:

put data(x);

требовалось на лету сформировать уже что-нибудь вроде:

do i=lbound(x) to hbound(x); put data(x(i)); end;

Но и это еще не все. Например, если x двумерный массив целых (например, матрица 3х3), тот же самый оператор put data(x); уже должен осуществлять вывод по двум циклам, чтобы дать в результате что-то такое:

X(1,1)= 1 X(1,2)= 2 X(1,3)= 3 X(2,1)= 4 X(2,2)= 5 X(2,3)= 6 X(3,1)= 7 X(3,2)= 8 X(3,3)= 9

Но при этом оператор put data(x(2)); должен вывести лишь одну строку матрицы:

X(2,1)= 4 X(2,2)= 5 X(2,3)= 6

А если x это набор разнотипных элементов (в PL/1 такой набор называется структурой), то нужно еще выводить и имена отдельных полей этого набора, например:

declare

1 a,

2 a1 fixed,

2 a2 fixed,

2 b,

3 b1 fixed,

3 b2 float;

put data(a);

A.A1= 0 A.A2= 0 A.B.B1= 0 A.B.B2= 0.000000E+00

Учитывая, что в структуре могут быть подструктуры, в свою очередь включающие массивы (т.е. могут быть и структуры массивов и массивы структур), то задача автоматического вывода элементов становится довольно громоздкой:

declare

1 a(1:2),

2 a1 fixed,

2 a2 fixed,

2 b,

3 b1 (-5:3) fixed,

3 b2 float;

put data(b);

B(1).B1(-5)= 0 B(1).B1(-4)= 0 B(1).B1(-3)= 0 B(1).B1(-2)= 0 B(1).B1(-1)= 0 B(1).B1(0)= 0 B(1).B1(1)= 0 B(1).B1(2)= 0 B(1).B1(3)= 0 B(1).B2= 0.000000E+00 B(2).B1(-5)= 0 B(2).B1(-4)= 0 B(2).B1(-3)= 0 B(2).B1(-2)= 0 B(2).B1(-1)= 0 B(2).B1(0)= 0 B(2).B1(1)= 0 B(2).B1(2)= 0 B(2).B1(3)= 0 B(2).B2= 0.000000E+00

Однако в языке PL/1 есть хорошая основа для доработок в виде возможности записать оператор цикла прямо внутри оператора ввода-вывода. В свое время разработчикам языка вывод массивов казался очень важным. Поэтому они разрешили писать цикл ввода-вывода в виде:

put list((x(i) do i=lbound(x) to hbound(x)));

вместо обычного цикла:

do i=lbound(x) to hbound(x); put list(x(i)); end;

Признаком начала цикла внутри оператора ввода-вывода является открывающая скобка. Кстати, разработчики PL/1 здесь немного попали впросак, поскольку при выводе выражения, начинающегося со скобки, большинство компиляторов воспримет эту скобку за начало цикла. Программистам приходилось писать выражения в экзотическом виде, только чтобы они не начинались со скобки:

put list(1e0*(x1+x2)/2e0));

Тем не менее, это сильно упрощает доработку компилятора, поскольку для вывода всех элементов массива достаточно при разборе очередного объекта ввода-вывода поставить его в скобки, дописать индексы и написать в этих же скобках заголовок цикла. В заголовке цикла начальное и конечное значение переменной цикла это константы, которые берутся из описания не скалярного объекта. В данной версии компилятора разрешено только статическое описание границ массивов и это также сильно упрощает доработку.

Легко заметить, что вывод с именами (put data) и вывод не скалярных объектов это дополняющие друг друга возможности. Объединяет их то, что в обоих случаях разбор объекта при трансляции выполняется два раза. Сначала все лексемы при лексическом разборе объекта запоминаются, а при повторном разборе выдаются из буфера так, как если бы из исходного текста. Но при этом в нужный момент выдаются и новые лексемы. В обоих случаях вместо лексического анализатора работает его эмулятор. Когда нужны обе возможности одновременно работают оба эмулятора, один на более низком уровне выдает лексемы для индексов, названий полей структур и заголовков циклов, а второй добавляет к ним элементы с текстовыми константами-именами.

Причем эмулятор верхнего уровня, создающий текстовые константы-имена, даже не подозревает, что лексический анализатор уже заменен на эмулятор для выдачи элементов массива и имен структур. Обе доработки компилятора не мешают друг другу и действуют независимо.

При этом работа эмулятора нижнего уровня гораздо сложнее, чем в случае put data, здесь используется такой алгоритм, как конечный автомат. Т.е. эмулятор имеет несколько состояний, запоминаемых между вызовами, при разборе переходя от одного к другому и выдавая в каждом состоянии лексемы разного типа. Это позволяет сначала выдать одну или несколько лексем - открывающих скобок, затем все имена промежуточных уровней структуры и все индексы, как переменные циклов, а затем набор лексем, обозначающих заголовки циклов по каждой размерности и, наконец, лексемы - закрывающие скобки.

Естественно, что если в исходном тексте старшие индексы объекта были явно указаны, то эмулятор дописывает только недостающие младшие индексы. Поэтому, например, для трехмерного массива x(1:10,1:10,1:10) оператор вывода:

put list(x); выдаст 1000 значений

put list(x(5)); выдаст 100 значений

put list(x(5,6)); выдаст 10 значений.

А для оператора put list(x(5,6,8)); эмулятор вообще не сгенерирует дополнительных лексем-индексов и будет напечатано единственное значение.

Недостатком описанной реализации оказалось то, что при применении оператора put data к не скалярным объектам на печати вместо всех значений индексов печатались идентификаторы переменных циклов, которые подставлялись в исходный текст в момент трансляции. А поскольку для этой цели использовались служебные целые переменные ?A, ?B, ?С,?O (всего 15 штук для максимально возможной размерности массива 15) выдача выглядела странно и во многом теряла ценность:

X(?A,?B)= 1 X(?A,?B)= 2 X(?A,?B)= 3 X(?A,?B)= 4 X(?A,?B)= 5 X(?A,?B)= 6 X(?A,?B)= 7 X(?A,?B)= 8 X(?A,?B)= 9

Для исправления этого недостатка потребовалось доработать системную библиотеку. В случае оператора put data с индексами компилятор не просто формирует текстовую константу имя переменной с подставленными индексами ?A, ?B, ?С,?O, но и дописывает перед каждым индексом специальный не выводимый символ 07FH.

При выполнении программы служебная процедура чтения очередного байта внутри системного вызова, с помощью которого обеспечивается весь вывод, обнаружив этот символ, в свою очередь, превращается в конечный автомат, который распознает идущую следом букву и находит текущее значение соответствующей переменной. Затем он переводит это значение в текст и посимвольно начинает выдавать этот текст вместо служебного символа и названия индекса внутри текстовой строки. В результате, наконец, получается правильное перечисление всех индексов элементов массива.

Переменные с именами при вводе

Естественно, имеется парный оператор к put data - это get data, который должен вводить значения переменных, заданные вместе с их именами. Но здесь, на мой взгляд, разработчики PL/1 переусложнили данный оператор. В соответствии со стандартом языка оператор ввода должен не просто пропускать имена, но распознавать их и записывать следующее далее значение по нужному адресу. Например, если перетасовать значения, выданные put data(x);, в другом порядке:

X(1,2)= 2 X(1,1)= 1 X(2,3)= 6 X(2,1)= 4 X(2,2)= 5 X(3,1)= 7 X(1,3)= 3 X(3,2)= 8 X(3,3)= 9

То оператор get data(x); все равно должен ввести значения в правильном порядке, распознав каждое имя и индексы перед знаком равенства. И хотя такая обработка дает дополнительные удобства, например, можно пропускать данные, которые не меняются при вводе, все-таки это слишком хлопотно и сложно для реализации. А, главное, для такой возможности нужно иметь таблицу имен переменных и их адресов в каждом exe-файле, использующем get data. Поэтому я не стал реализовывать распознавание имен при вводе, а ограничился при чтении простым пропуском всех символов до знака равенства при разборе очередного элемента. Самое важное для меня операторы put data и get data остались зеркальными и выдача данных оператором put позволяет потом безошибочно читать их оператором get с таким же списком объектов.

Заключение

Как показывает практика, большую часть времени программист тратит все-таки на отладку. Поэтому любые средства и языка, и системы программирования в целом, хоть как-то облегчающие процесс отладки, должны только приветствоваться. Одним из таких простейших средств является встроенный ввод-вывод объектов программы вместе с их именами, реализация которого, как показано выше, не требует значительных затрат в компиляторе.

Мало этого, в данном случае удалось, не затрагивая работу основных частей компилятора, добавить дополняющие друг друга возможности и автоматического формирования имен, и автоматического вывода всех элементов массива. Объем кода доработок составил менее процента от общего объема компилятора, однако они оказывают существенную помощь, особенно при отладке, экономя и время, и внимание программиста при написании операторов ввода-вывода.

Послесловие

По личному опыту знаю, что, самая распространенная реакция на подобные заметки обычно сводится к двум заявлениям:

1. Это нафиг никому не нужно.

2.Это легко повторить на любом современном языке.

Первое заявление должно было бы звучать как мне это не нужно и тогда оно было бы корректным, но тогда непонятно, зачем об этом объявлять, а не просто пройти мимо.

Второе заявление, в принципе, верно. Например, в языке Немерле, есть доступ к такому свойству переменной, как имя в тексте программы, т.е. как раз нужная база для отладочного вывода, подобного put data.

Поэтому мне была предложена несложная библиотека на Немерле, реализующая, как уверял ее автор, вывод с именами и повторяющий возможности старого PL/1:

using System.Console;using PL1.Macro;module Program{  Main() : void  {    def x = 1280;    def y = 1024;    put data(x, y);    put data(x, y, x + y, x.ToString() + "asd");    _ = ReadLine();  }}using Nemerle;using Nemerle.Compiler;using Nemerle.Compiler.Parsetree;using System.Collections.Generic;using System.Linq;namespace PL1.Macro{  public macro PutData(args)  syntax ("put", "data", args)  {    PutDataImpl.Impl(args)  }  module PutDataImpl  {    public Impl(args : PExpr) : PExpr    {      match (args)      {        | PExpr.Tuple as args =>          def code = List();          foreach (arg in args.args)          {            code.Add(<[ $(arg.ToString()) ]>);            code.Add(<[ "=" ]>);            code.Add(arg);            code.Add(<[ " " ]>);          }          code.RemoveAt(code.Count - 1);          def code = code.Aggregate((a1, a2) => <[ $a1 + $a2 ]>);          <[ System.Console.WriteLine($(code)) ]>        | _ => PExpr.Error(args.Location, "Tuple expected.")      }    }  }}

Однако на предложение доработать библиотеку, чтобы она позволяла выводить и не скалярные объекты с печатью всех индексов (и тогда действительно бы повторяла возможности PL/1), мне в ответ было предложено сделать это самому в виде домашнего задания. Оказанную честь я отклонил, под предлогом того, что вообще-то у меня все это уже давно есть и используется. Судя по всему, автор библиотеки просто сразу не сообразил, как это сделать. И почему-то вспомнилась сцена из фильма Формула любви, где Калиостро удивив всех поеданием вилки, все-таки отказался съесть при этом еще и тарелку.

Введение

В свете все возрастающего потока англоязычных околонаучных терминов в области программирования и следуя за модой, в названии статьи можно было бы вместо некрасивого модификация исполняемого кода написать что-нибудь вроде run-time reflection. Суть от этого не меняется. Речь о реализации в компиляторе такого непростого объекта, как массив с заранее неизвестными границами. Типичный пример использования подобных объектов это операции (в математическом смысле) с матрицами разных размеров.

В данном случае имеется в виду многомерный массив, который занимает непрерывный участок памяти и у которого границы задаются уже при работе программы, причем нижние границы не обязательно начинаются с нуля. Реализация обращения к таким массивам гораздо сложнее случая границ-констант, известных при компиляции.

Обычно текущие значения границ пишутся в специальную структуру (паспорт массива) и затем используются в командах вычисления адресов элементов массива. Для границ-констант, известных при компиляции, паспорт в общем случае в выполняемой программе не требуется.

Из сложности реализации таких массивов следует неприятное следствие: обращение к массивам с динамическими границами выполняется существенно медленнее, чем к массивам с границами-константами. Желательно было бы соединить мощь и удобство работы с массивами с задаваемыми при исполнении кода границами с быстротой доступа к массивам с границами-константами, когда часть вычислений адресов элементов может производиться уже на этапе компиляции программы.

Далее все рассуждения приводятся на примере конкретной реализации компилятора PL/1-KT с языка PL/1 для Win64.

Подход к реализации

Самый простой подход к решению данной задачи, который первым приходит в голову заменить значения границ-констант массивов на новые нужные значения и просто перетранслировать программу. Разумеется, во многих случаях такой подход неприемлем. Но рассмотрим, чем будет отличаться выполняемый код? Например, такому обращению к элементу массива:

dcl x(100,100) float(53);dcl (i,j)      fixed(63);x(i,j)=12345e0;

соответствует такой исполняемый код x86-64:

48693DB838010020030000   imul rdi,I,80048A1C038010000000000     mov  rax,J488DBCC710FDFFFF         lea  rdi,X+0FFFFFCD8h[rdi+rax*8]BE30000000               mov  rsi,offset @00000030h48A5                     movsq

Видно, что при разных значениях границ-констант массива исполняемый код будет отличаться лишь разными значениями операндов-констант в некоторых командах. В данном случае это значение третьего операнда-константы операции IMUL и константа-смещение в операции LEA.

Следовательно, если в выполняемом модуле сохранить информацию об адресах таких команд, а также информацию, каким образом получены такие операнды-константы, то можно создать служебную подпрограмму, которая при вызове во время исполнения программы заменит все нужные операнды-константы на новые значения, соответствующие новым требуемым значениям границ массивов.

После этого, исполнение кода пойдет так, как если бы при трансляции были заданы такие новые границы-константы. Получаются массивы как бы с динамическими границами, т.е. изменяемыми при выполнении программы, но обращение к которым идет точно так же, как и к массивам со статическими границами.

Это принципиально отличается от JIT-компиляции, поскольку код создавать не требуется, а нужно лишь самым простейшим образом скорректировать части нескольких уже готовых команд.

Некоторую сложность такому подходу добавляет тот факт, что операнд-константа может быть из нескольких составляющих и только часть из них определяется именно границами массива. Поэтому служебная подпрограмма должна заменять в операнде-константе только ту часть, которая меняется при изменении значений границ.

Выделение памяти для массивов с динамическими границами

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

Поэтому память для массивов с динамическими границами должен явно выделять программист из кучи оператором ALLOCATE и освобождать оператором FREE. В языке PL/1 такие объекты считаются объектами с управляемой (CONTROLLED) памятью.

Следовательно, новые значения констант должны быть определены до собственно создания массива, т.е. до выполнения соответствующего оператора ALLOCATE. Поэтому и обращение к служебной подпрограмме замены констант для данного массива должно быть тоже прежде выполнения оператора ALLOCATE, так как объем выделяемой для массива памяти это также операнд-константа в одной из команд перед вызовом ALLOCATE, зависящий от размеров границ.

Обработка констант

Константы, которые вычисляются из границ-констант массива и которые, в конечном итоге, становятся частью операндов-констант исполняемого кода, формируются на этапе анализа исходного текста программы при компиляции.

Компилятор PL/1-KT переводит текст программы в промежуточную обратную польскую запись, где каждая константа это отдельная операция, имеющая единственный операнд само значение константы (4 байта). Для реализации динамических массивов вводится новая операция модифицированная константа, которая имеет не значение, а операнд-ссылку на таблицу компилятора. По ссылке располагается само значение константы, а также вся необходимая информация, позволяющая определить, как получилось данное значение, и, следовательно, позволяющая рассчитать новое значение при новых границах.

После окончания трансляции эти ссылки сохраняются и в выполняемом модуле, причем к ним добавляются адреса команд, в код которых замешивается данная константа, а также адрес служебного (создаваемого компилятором) указателя на выделенную динамическому массиву память.

Служебная подпрограмма подготовки кода имеет один параметр служебный указатель и рассматривает только те ссылки на команды, в которых используется указатель, совпадающий с ее входным параметром. Для этих ссылок определяется место в команде, где записана сама константа, формируется новая константа из новых значений границ, к ней добавляется часть исходной константы, которая не зависит от границ. Новая константа заменяет в команде старую, и подпрограмма ищет следующую ссылку для заданного массива, т.е. для заданного указателя.

Исправляемые таким образом команды текстуально могут находиться и выше и ниже вызова служебной подпрограммы. Но, разумеется, если начать выполнять еще не приведенный к правильным границам код, поведение программы станет непредсказуемым.

Объекты программы, зависящие от размеров границ массивов

Таких объектов в программе на языке PL/1 оказалось восемь:

- встроенные функции языка LBOUND/HBOUND/DIMENSION, выдающие значения нижней/верхней границы или числа элементов для заданной размерности;

- оператор ALLOCATE, неявно имеющий входным параметром число выделяемых массиву байт, зависящее от его границ;

- индекс, т.е. собственно команды вычисляющие часть адреса по очередному индексу-переменной при обращении к элементу массива;

- последний индекс, появляется только в случае режима компиляции с контролем выхода индекса за границы массива. Для данного элемента корректировать константу в команде не требуется, например, это случай одномерного массива, где вычисление адреса умножением по единственному индексу не зависит от значения границ, но где-то далее имеются команды контроля выхода индекса за границы и их-то константы и необходимо скорректировать;

- смещение массива, это последняя из команд вычисления адреса элемента массива. К этому моменту уже вычислены составляющие адреса от индексов-переменных и в этой команде для x86-64 обычно реализуется базово-индексный режим адресации, причем в команде имеется постоянное смещение, которое как раз и зависит от значений границ и должно быть скорректировано. Ненулевое смещение возникает, так как нижние границы не обязательно нулевые, некоторые индексы могут быть константами, а элемент, адрес которого вычисляется, сам может быть элементом структуры (агрегата разнотипных элементов), имеющим свое постоянное смещение - начало каждого элемента внутри этой структуры;

- участок памяти - при обращении к части массива или к массиву целиком как к непрерывному участку памяти необходимо скорректировать число обрабатываемых байт, так как оно также зависит от текущих значений границ.

Наиболее громоздким для обработки является корректировка константы в команде элемента смещение, поскольку в константу команды-смещение входят и части от индексов-констант. Служебной подпрограмме необходимо повторить весь расчет адресной части заново, причем, если по дороге были индексы-константы, еще необходимо тут же проверить их на выход за пределы новых значений границ.

Синтаксис массивов с изменяемыми границами

В стандарте языка PL/1 изменяемые границы массивов просто задаются выражениями, например:

dcl  n      fixed(31),     x(0:n) float ctl;get list(n);allocate x;

Для описываемой реализации такая запись бессмысленна, поскольку границы будут меняться другим способом, поэтому в описании вместо переменных используется знак *, этот пример эквивалентен предыдущему:

dcl  n      fixed(31),     x(*)   float ctl;get list(n);?index(1,1)=0; ?index(1,2)=n; // устанавливаем новые границыcall ?ret(addr(x));           // меняем константы кода обращения к xallocate x;

Для изменения границ в компилятор PL/1-KT введены служебные элементы в виде встроенного глобального двумерного массива новых значений нижних и верхних границ:

dcl ?index(15,2) fixed(31) external;

Первая размерность этого массива 1:15, поскольку это максимально допустимое число размерностей массива в компиляторе PL/1-KT.

А также введена служебная подпрограмма перетрансляции, т.е. корректировки констант в командах, использующая текущие значения массива ?index:

dcl ?ret entry(ptr) external;

Служебный массив ?index и подпрограмма ?ret предопределены в компиляторе PL/1-KT. При запуске программы все значения границ в массиве ?index по умолчанию заданы единичными.

Передача новых значений границ через глобальный массив ?index, а не через входные параметры подпрограммы ?ret сделана для большей гибкости их использования. Например, в этом случае не требуется повторять задания границ для массивов одинаковых размеров, не требуется каждый раз перечислять нижние границы каждой размерности, если они всегда остаются единичными и т.п.

В случае какой-либо ошибки корректировки констант, эта подпрограмма не возвращает код ошибки, но инициирует перехватываемое исключение, поскольку далее обращение к массиву, указанному как входной параметр, даст непредсказуемые результаты.

Компилятор PL/1-KT отмечает в своей таблице признак изменяемой границы у данного массива, а сам значок * просто заменяет на некоторые некруглые значения границ. Это сделано для того, чтобы далее в процессе компиляции создавались обычные команды для массивов с границами-константами. А некруглые значения не позволяют оптимизатору применять более короткие формы команд, поскольку тогда невозможно скорректировать их другими, например, большими значениями.

Динамические границы, обозначаемые *, могут быть только старшими размерностями и следовать подряд. При этом такие границы могут быть не только у массивов однородных элементов, но и у массивов структур, т.е. агрегатов данных разных типов. Младшие размерности при этом могут оставаться константами, например:

dcl // структура-массив с изменяемыми границами1 s(*,*)       ctl, 2 x1          char(100) var, 2 y1 (-1:25)  float, // внутри могут быть и границы-константы 2 z1 (100)    fixed(31);

Ссылка на массивы с изменяемыми границами

Для передачи в подпрограммы массивов с изменяемыми границами как параметров, учитывается тот факт, что такие массивы всегда неявно используют указатели. Но поскольку это служебные указатели, создаваемые компилятором, напрямую использовать их имена нельзя. Обращение к указателю без явного использования его имени возможно в языке PL/1 в случае применения встроенной функции ADDR, например:

dcl x(100) float based(p1),   (p1,p2) ptr;p2=addr(x); //это эквивалентно p2=p1;

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

call умножение_матриц(addr(a),addr(b),addr(c),m,n,q);

и тогда описание параметров таких подпрограмм становится единообразным, не зависящим от самих массивов:

dcl умножение_матриц entry(ptr,ptr,ptr,fixed(31),fixed(31),fixed(31));

Этот прием позволяет передавать динамические массивы в подпрограммы, но не позволяет принимать их внутри подпрограмм, поскольку тогда опять нужно присваивать указатели-параметры служебным указателям с недоступными именами. Поэтому в компиляторе PL/1-KT дополнительно разрешено использовать и в левой части присваивания встроенную функцию ADDR:

dcl x(*) float ctl,    p1   ptr;addr(x)=p1; //эквивалентно оператору <служебный указатель на x>=p1;

Пример использования динамических массивов как параметров

В данном примере применена описанная выше технология корректировки констант для универсального умножения матриц задаваемого размера. Динамические массивы-матрицы создаются оператором ALLOCATE и передаются (неявно, указателями) в универсальную процедуру умножения матриц. Корректировка констант в исполняемом коде производится как для фактических параметров A1, B1,C1, так и для формальных A, B, C внутри подпрограммы. Кроме этого, формальным параметрам присваиваются фактические значения с помощью разрешения использовать функцию ADDR в левой части присваивания. Процедура УМНОЖЕНИЕ_МАТРИЦ может находиться в отдельном модуле и транслироваться автономно.

TEST:PROC MAIN;DCL (A1,B1,C1)(*,*) FLOAT CTL; // ДИНАМИЧЕСКИЕ МАТРИЦDCL (M1,N1,Q1)      FIXED(31); // ЗАДАВАЕМЕ ГРАНИЦDCL (I,J)           FIXED(31); // РАБОЧИЕ ПЕРЕМЕННЕ//---- ДЛЯ ТЕСТА ЗАДАЕМ НЕКОТОРЕ ЗНАЧЕНИЯ ГРАНИЦ ----M1=5; N1=4; Q1=3;//---- КОРРЕКТИРУЕМ КОНСТАНТ A1(M1,N1), B1(N1,Q1), C1(M1,Q1) ----?INDEX(1,2)=M1; ?INDEX(2,2)=N1;?RET(ADDR(A1));                   // ИЗМЕНЯЕМ КОМАНД ДЛЯ A1?INDEX(1,2)=N1; ?INDEX(2,2)=Q1;?RET(ADDR(B1));                   // ИЗМЕНЯЕМ КОМАНД ДЛЯ B1?INDEX(1,2)=M1;?RET(ADDR(C1));                   // ИЗМЕНЯЕМ КОМАНД ДЛЯ C1//---- СОЗДАЕМ МАТРИЦ A1(M1,N1), B1(N1,Q1) И C1(M1,Q1) ----ALLOCATE A1,B1,C1;//---- ДЛЯ ТЕСТА ЗАПОЛНЯЕМ МАТРИЦ НЕКОТОРМИ ЗНАЧЕНИЯМИ ----DO I=1 TO M1; DO J=1 TO N1; A1(I,J)=I+J; END J; END I;DO I=1 TO N1; DO J=1 TO Q1; B1(I,J)=I-J; END J; END I;//---- УМНОЖЕНИЕ МАТРИЦ A1 И B1, РЕЗУЛЬТАТ - МАТРИЦА C1 ----УМНОЖЕНИЕ_МАТРИЦ(ADDR(A1),ADDR(B1),ADDR(C1),M1,N1,Q1);//---- ВДАЕМ ПОЛУЧЕННЙ РЕЗУЛЬТАТ ----PUT SKIP DATA(C1);FREE A1,B1,C1;//========== УМНОЖЕНИЕ МАТРИЦ ЗАДАННОГО РАЗМЕРА ==========УМНОЖЕНИЕ_МАТРИЦ:PROC(P1,P2,P3,M,N,Q);//---- ВХОД A(M,N) И B(N,Q), ОТВЕТ - МАТРИЦА C(M,Q) ----DCL (P1,P2,P3)   PTR;       // УКАЗАТЕЛИ НА МАТРИЦDCL (M,N,Q)      FIXED(31); // ЗАДАННЕ ГРАНИЦDCL (A,B,C)(*,*) FLOAT CTL; // ДИНАМИЧЕСКИЕ МАТРИЦDCL (I,J,K)      FIXED(31); // РАБОЧИЕ ПЕРЕМЕННЕ//---- НОВЕ ОПЕРАТОР ПРИСВАИВАНИЯ УКАЗАТЕЛЕЙ ----ADDR(A)=P1;     // АДРЕС ДЛЯ МАССИВА AADDR(B)=P2;     // АДРЕС ДЛЯ МАССИВА BADDR(C)=P3;     // АДРЕС ДЛЯ МАССИВА C//---- КОРРЕКТИРУЕМ КОНСТАНТ МАТРИЦ A(M,N), B(N,Q), C(M,Q) ----?INDEX(1,2)=M; ?INDEX(2,2)=N;?RET(ADDR(A));                    // ИЗМЕНЯЕМ КОМАНД ДЛЯ A?INDEX(1,2)=N; ?INDEX(2,2)=Q;?RET(ADDR(B));                    // ИЗМЕНЯЕМ КОМАНД ДЛЯ B?INDEX(1,2)=M;?RET(ADDR(C));                    // ИЗМЕНЯЕМ КОМАНД ДЛЯ C//---- САМО УМНОЖЕНИЕ МАТРИЦ ----DO I=1 TO M;   DO J=1 TO Q;          C(I,J)=0;          DO K=1 TO N;                 C(I,J)+=A(I,K)*B(K,J);          END K;   END J;END I;END УМНОЖЕНИЕ_МАТРИЦ;END TEST;

Эта тестовая программа эквивалентна приведенной ниже программе с обычными границами-константами у матриц.

TEST:PROC MAIN;DCL (P1,P2,P3)      PTR;             // УКАЗАТЕЛИ НА МАТРИЦDCL A1(5,4)         FLOAT BASED(P1), // СТАТИЧЕСКАЯ МАТРИЦА А1    B1(4,3)         FLOAT BASED(P2), // СТАТИЧЕСКАЯ МАТРИЦА B1    C1(5,3)         FLOAT BASED(P3); // СТАТИЧЕСКАЯ МАТРИЦА C1DCL (M1,N1,Q1)      FIXED(31);       // ЗАДАВАЕМЕ ГРАНИЦDCL (I,J)           FIXED(31);       // РАБОЧИЕ ПЕРЕМЕННЕ//---- ДЛЯ ТЕСТА ЗАДАЕМ НЕКОТОРЕ ЗНАЧЕНИЯ ГРАНИЦ ----M1=5; N1=4; Q1=3;//---- СОЗДАЕМ МАТРИЦ A1(M1,N1), B1(N1,Q1), C1(M1,Q1) ----ALLOCATE A1,B1,C1;//---- ДЛЯ ТЕСТА ЗАПОЛНЯЕМ МАТРИЦ НЕКОТОРМИ ЗНАЧЕНИЯМИ ----DO I=1 TO M1; DO J=1 TO N1; A1(I,J)=I+J; END J; END I;DO I=1 TO N1; DO J=1 TO Q1; B1(I,J)=I-J; END J; END I;//---- УМНОЖЕНИЕ МАТРИЦ A1 И B1, РЕЗУЛЬТАТ - МАТРИЦА C1 ----УМНОЖЕНИЕ_МАТРИЦ(ADDR(A1),ADDR(B1),ADDR(C1),M1,N1,Q1);//---- ВДАЕМ ПОЛУЧЕННЙ РЕЗУЛЬТАТ ----PUT SKIP DATA(C1);FREE A1,B1,C1;//========== УМНОЖЕНИЕ МАТРИЦ ЗАДАННОГО РАЗМЕРА ==========УМНОЖЕНИЕ_МАТРИЦ:PROC(P1,P2,P3,M,N,Q);//---- ВХОД A(M,N) И B(N,Q), ОТВЕТ - МАТРИЦА C(M,Q) ----DCL (P1,P2,P3)   PTR;             // УКАЗАТЕЛИ НА МАТРИЦDCL (M,N,Q)      FIXED(31);       // ЗАДАННЕ ГРАНИЦDCL A(5,4)       FLOAT BASED(P1), // СТАТИЧЕСКИЕ МАТРИЦ    B(4,3)       FLOAT BASED(P2),    C(5,3)       FLOAT BASED(P3);DCL (I,J,K)      FIXED(31);       // РАБОЧИЕ ПЕРЕМЕННЕ//---- САМО УМНОЖЕНИЕ МАТРИЦ ----DO I=1 TO M;   DO J=1 TO Q;          C(I,J)=0;          DO K=1 TO N;                 C(I,J)+=A(I,K)*B(K,J);          END K;   END J;END I;END УМНОЖЕНИЕ_МАТРИЦ;END TEST;

Обе программы дают идентичный результат:

C1(1,1)=  2.600000E+01 C1(1,2)=  1.200000E+01 C1(1,3)= -2.000000E+00C1(2,1)=  3.200000E+01 C1(2,2)=  1.400000E+01 C1(2,3)= -4.000000E+00C1(3,1)=  3.800000E+01 C1(3,2)=  1.600000E+01 C1(3,3)= -6.000000E+00C1(4,1)=  4.400000E+01 C1(4,2)=  1.800000E+01 C1(4,3)= -8.000000E+00C1(5,1)=  5.000000E+01 C1(5,2)=  2.000000E+01 C1(5,3)= -1.000000E+01

Заключение

Массивы с динамически меняющимися границами являются мощным и гибким инструментом и допустимы в ряде языков программирования. Однако этот инструмент требует и более сложного вычисления адресов элементов, в отличие от статических границ, когда часть вычислений можно выполнить уже на этапе компиляции.

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

Это требует времени для подготовки выполняемого кода перед созданием очередного массива. Однако после такой корректировки констант в коде программы, ее выполнение идет так, словно границы массивов были изначально заданы нужными значениями, что позволяет сократить операции вычисления адресов элементов массивов и в целом ускорить программу, поскольку обычно требуется корректировка лишь нескольких команд, которые затем будут выполняться многократно.

В чем-то похожие подходы применялись и ранее, например, в языке Visual Basic имеется операция reDim, задающая границы при исполнении программы. Однако в этих случаях динамически меняются все же данные в программе, а не операнды команд ее исполняемого кода.

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

Послесловие

Обращаю внимание гг. комментаторов, что утверждение: это никому не нужно, поскольку наш компилятор создает прекрасные динамические массивы некорректно. Корректно оно в виде мне и моим коллегам по проекту это не нужно. В этом случае я рад за вас, но считаю, что радовать остальных читателей такими комментариями необязательно.

Введение

Впервые термин экстракод я услышал еще применительно к командам БЭСМ-6. Сейчас это слово практически не используется, наиболее близкое понятие - системный вызов. Из-за особенностей системы команд БЭСМ-6, те экстракоды действительно больше напоминали дополнительные встроенные инструкции, чем, например, вызов функции в MS-DOS с помощью INT 21H.

Смысл термина экстракод вполне прозрачен: это расширение системы команд для того, чтобы создать из реальной машины виртуальную машину для заданного языка, например, Паскаль-машину или Лисп-машину. А транслятор после этапа анализа исходного текста программы должен провести синтез программы т.е. перевести результаты анализа в команды этой виртуальной машины.

Кстати, Лисп-машину когда-то действительно собирались воплотить в аппаратуре. Однако создание таких машин для конкретных языков было бы экономически слишком невыгодно по сравнению с универсальными и поэтому мы сейчас используем исключительно универсальные (с точки зрения языков) компьютеры. Правда, по мере развития и удешевления технологий разработки и производства процессоров, экономические преимущества универсальных систем команд над специальными могут стать не столь очевидными.

Пример использования экстракода при компиляции

Я утверждаю, что понятия языка PL/1 лучше, чем у многих других языков отражены в командах архитектуры IA-32, поскольку в момент разработки процессора 8086 (вторая половина 70-х годов) требования поддержки языков высокого уровня ориентировались на основные языки того времени, среди которых заметное место занимал и PL/1.

Рассмотрим на простом примере, как понятия языка высокого уровня преобразуются в команды IA-32. Например, в PL/1 есть такие объекты, как строки постоянной длины.

В рассматриваемом подмножестве языка длина такой строки не должна превышать число, занимающее байт. Со строками можно работать различным образом, например, сравнивать на равенство или даже на больше-меньше. А в архитектуре IA-32 есть команда CMPSB, которая как раз и сравнивает две цепочки байт в памяти. Казалось бы, и компилятор должен реализовать сравнение строк постоянной длины с помощью одной этой команды (с повторением) REPE CMPSB. Однако на самом деле сравнение реализовано так:

declares1 char(10),s2 char(15);if s1>s2 then BF0A000000          mov    edi,offset S2B00F                mov    al,15BE00000000          mov    esi,offset S1B10A                mov    cl,10E800000000          call   ?SCCCM7505                jbe    @1

Почему же даже для такой простой операции потребовался системный вызов? Дело в том, что команда CMPSB близка к понятию сравнения строк в PL/1, но не полностью совпадает. В языке, если сравниваются две строки разной длины, то сначала более короткая из них дополняется пробелами, а уже после идет само сравнение.

Команда же CMPSB по определению не сравнивает строки разной длины. Зачем же потребовалось вводить в язык такое странное требование, как продолжать сравнивать одну строку, когда другая уже закончилась? Как раз в понятиях языка все логично. Короткая строка дополняется пробелами не только при сравнении, но и при присваивании в более длинную строку. Тогда после такого присваивания и сравнения, получится правильный результат строки равны, хотя они и продолжают иметь разную длину. Если же заканчивать сравнение по исчерпанию одной из строк, можно получить неверный результат сравнения, например, для строк 12345 и 123456, которые, очевидно, не равны.

Вот если бы в процессоре была команда сравнения PL1_CMPSB, которая не только бы выполняла действия, аналогичные CMPSB, но и по значению, скажем, в регистре AL определяла бы, сколько еще байт осталось в более длинной строке и сравнивала бы этот остаток с пробелами, вот тогда компилятор мог бы генерировать сравнение строк в смысле языка PL/1 одной этой командой.

А ведь в примере компилятор как раз это и делает. Только несуществующую команду PL1_CMPSB он заменяет вызовом системной подпрограммы, которую я называю экстракодом. Этот конкретный экстракод имеет странное имя-аббревиатуру ?SCCCM, буквы которой систематизированы и в данном случае показывают, что идет работа со строками (String) и сравниваются (Compare) две строки постоянной длины (Сhar и Char), находящиеся не в стеке, а в статической памяти (Memory). Система при составлении названий экстракодов нужна, поскольку их разновидностей достаточно много.

Отличия экстракодов от системных подпрограмм

Может показаться, что слишком много внимания уделено обычному вызову системной процедуры при генерации программы. Но это не совсем обычный вызов.

Первое отличие экстракодов от обычных вызовов подпрограмм это отсутствие общих правил передачи параметров. В этом они больше похожи на команды IA-32, где тоже нет общих правил, а в каждом случае могут быть свои. Например, просто из вида команды REPE CMPSB, не имеющей параметров, невозможно догадаться, что она одновременно использует и меняет регистры ESI, EDI и ECX.

Конечно, и передача параметров в обычные подпрограммы может быть организована через регистры, а не, например, через стек. Собственно так и сделано в 64-разрядных Windows API, где используются регистры RCX, RDX, R8 и R9. Но там всегда используются эти регистры, в то время как в каждом конкретном экстракоде (как и в каждой конкретной команде) могут быть разные. Поэтому в приведенном выше примере загрузка адресов и длин строк идет в конкретные регистры, сразу, так сказать, на свои места и дополнительных пересылок внутри экстракода уже не требуется.

Второе отличие экстракода от обычной системной подпрограммы его полная открытость для компилятора. В отличие от идеи модуля-черного ящика, когда снаружи известен только вход и выход, компилятору известно, какие регистры портит (т.е. использует) данный экстракод при выполнении.

Это позволяет проводить ряд оптимизаций при распределении регистров. Хотя часто и при работе с обычными подпрограммами компилятор также использует некоторую информацию (например, соглашение о не меняющихся внутри подпрограммы ESI и EDI), в случае экстракода работа идет по-другому. Соглашение о ESI и EDI по существу означает запрет на их использование. Точнее, подпрограмма при использовании должна сохранить, а затем восстановить их значения. Внутри же экстракода, как и внутри команды, никаких запретов нет и сохранять регистры не требуется (например, они и являются результатом), а при необходимости это сделает компилятор снаружи вызова.

Наконец, третье отличие от простых вызовов системных подпрограмм это отсутствие общих правил возврата результата. В примере со сравнением строк экстракод возвращает не какое-либо значение в регистре EAX как типичная подпрограмма, а прямо состояние регистра флагов процессора, собственно как это и должна делать команда сравнения CMPSB (так как внутри экстракода ?SCCCM она и является основным действием).

Все эти отличия делают экстракоды более похожими на команды, чем на подпрограммы, а стиль генерации программы экстракодами больше похожим на программирование на ассемблере, хотя формально в программе получается много вызовов системных подпрограмм.

Правда, если тело экстракода короткое, его можно вставить в программу напрямую, без команды вызова. Но обычно команд внутри экстракода достаточно много, чтобы не обращать внимания на экономию времени за счет исключения инструкций вызова и возврата, особенно учитывая, что при подстановке экстракодов, так сказать, inline, код программы сильно увеличивается и это совсем не ускоряет ее исполнение.

Могут возразить, что понятие экстракода избыточно, поскольку уже есть термин интринсик. На мой взгляд, между экстракодом и интринсиком есть такие же различия, как между программированием снизу вверх и сверху вниз. Интринсик это момент перехода от абстрактных команд к командам конкретного процессора (сверху-вниз), а экстракод это конструирование новых команд из имеющихся в процессоре для применения в программе (т.е. снизу-вверх). При этом в обоих случаях могут генерироваться одни и те же реальные команды процессора.

Да и слово интринсик очень неудобопроизносимое по-русски.

Типы экстракодов при компиляции выражений

Несмотря на то, что входные и выходные параметры экстракодов могут быть организованы совершенно по-разному, при компиляции выражений над объектами, которые не помещаются в обычные регистры (например, строки или даже 8-байтные числа в формате IEEE-754), получается 4 группы схожих экстракодов, в зависимости от операндов или как просто переменных, или как результатов предыдущих вычислений. Например, вот 4 разновидности экстракода операции деления :

declare(x,y,z) float(53);z=x/y;          оба операнда в переменных, экстракод деления ?FDF_Mz=(x+1)/y;      левый операнд в стеке,     экстракод деления ?FDF_Lz=x/(y+1);      правый операнд в стеке,    экстракод деления ?FDF_Rz=(x+1)/(y+1);  оба операнда в стеке,      экстракод деления ?FDF_S

Различаются эти разновидности, естественно, способом загрузки исходных параметров, или через указатель стека ESP (RSP) или через адрес переменной. При генерации выражения компилятор выбирает нужный тип экстракода исходя из числа операций внутреннего представления программы. Если операнд загружается одной единственной операцией значит, он берется из переменной. Если же операций несколько значит, данный операнд сам является результатом вычисления и как результат уже помещен в стек предыдущими сгенерированными командами.

В случае работы с FPU процессора в большинстве случаев используется стек FPU, а не стек самого процессора. Только в этом случае последний из типов экстракода, например, деления ?FDF_S может быть сведен к генерации единственной команды FDIV.

Наибольшее число разновидностей экстракодов получается при работе с комплексными числами, поскольку в этом случае каждая из 4 групп экстракодов делится еще на 3 подгруппы, в зависимости оба ли операнда комплексные или один операнд комплексный, а другой действительный.

Пример оптимизации при использовании экстракодов

Рассмотрим еще один простой пример, часто встречающийся в программах на PL/1:

s=substr(s,2); 

Здесь из строки s выбрасывается первый символ, что обычно используется в цикле обработки символов, пока строка s не станет пустой. В данном случае обрабатывается объект строка переменной длины (ее текущая длина записана первым байтом по адресу строки).

declares char(*) varying;s=substr(s,2);B202                mov    dl,2BE00000000          mov    esi,offset S8BFE                mov    edi,esiE800000000          call   ?VS2ADE800000000          call   ?SMCVF

Реализация отбрасывания первого символа строки выполнена с помощью двух экстракодов, один из которых выделяет подстроку, а второй переписывает ее в заданную строку, в данном случае в ту же самую.

Причина, по которой нельзя выполнить это прямо двумя командами типа LEA ESI,[ESI+EDX]-1 и REP MOVSB по сути та же самая, что и в предыдущем примере: эти команды близки, но не тождественны командам PL/1-машины выделение подстроки и присвоение строке.

Поэтому хотя команды LEA и MOVSB и являются основами соответствующих экстракодов, требуется выполнить еще ряд действий. Например, при выделении подстроки в смысле PL/1 нужно еще убедиться, что строка не пустая и заданное начало подстроки не выходит за ее границу. А при присваивании строки в общем случае может еще потребоваться дописывание пробелами, как и в разобранном выше сравнении строк.

В данном примере видно, как информация о работе экстракодов используется для сокращения команд подготовки параметров. Компилятор знает, что экстракод выделения подстроки ?VS2AD не использует EDI и поэтому сразу загружает его значением, нужным для последующей пересылки. А поскольку это значение сначала совпадает с загрузкой ESI, вместо команды mov edi,offset s используется более короткая команда mov edi,esi.

Экстракод ?VS2AD возвращает результат через регистр ESI (начало подстроки) и AL (длина подстроки), причем всегда еще и CL=AL. Для работы второго экстракода пересылки ?SMCVF нужно установить значения в регистры ESI, EDI и CL, поскольку внутри все сведется, в конце концов, к выполнению команды REP MOVSB.

Но регистр EDI уже установлен, нужное значение в регистре ESI загружено после работы первого экстракода и в CL уже находится длина переписываемой подстроки. Поэтому компилятору можно сразу генерировать вызов второго экстракода без дополнительных загрузок регистров. Получается, что на выполнение оператора отбрасывания первого символа строки в программе потребовалось всего 19 байт кодов.

При этом выполнение требуемых действий осуществляется внутри экстракодов максимально эффективно для архитектуры IA-32, а именно командами загрузки адреса LEA и цепочечной пересылкой MOVS. Кроме этого внутри экстракодов выполняются дополнительные проверки и действия, необходимые для соблюдения требований языка PL/1. Компилятору не нужно каждый раз генерировать эти действия, он имеет дело только с экстракодами, по существу со своей специальной системой команд.

Конечно, всегда имеются и обычные встроенные функции, например, ACOS, которые компилятор обрабатывает как стандартный вызов подпрограммы без привлечения понятия экстракода. Эти встроенные функции имеют такие же общие правила передачи параметров и возврата результата, как и подпрограммы, описанные пользователем, и ничем от таких подпрограмм не отличаются, за исключением того, что их не нужно описывать и их тела находятся в той же системной библиотеке, что и тела экстракодов.

Отличие компилятора от транслятора

Немного отвлекаясь от темы статьи, хотелось бы отметить, что я везде использую термин компилятор, а не транслятор.

В определении отличия компилятора от транслятора, на мой взгляд, существует некоторая путаница. Например, в Википедии прямо написано, что компиляция это трансляция программ. Получается, что компилятор и транслятор это одно и то же.

Наверное, правильнее было бы обратить внимание в той же Википедии на статью литературная компиляция, поскольку человек, первый применивший термин компиляция в программировании, конечно же имел ввиду именно ее аналог в литературе. Эта компиляция происходит от латинского слова compilatio - ограбить.

Получается, что компилятор - это грабитель. Ну, или менее экзотично, литературный и компьютерный компиляторы создают свое с помощью чужого. На мой взгляд, это и есть главное отличие компилятора от транслятора. В своей работе, он использует чужие, заранее написанные коды с помощью системных вызовов или, как в рассмотренных случаях, с помощью экстракодов.

Если же чужие коды в принципе не используются это транслятор. Например, не может быть компилятора с ассемблера, поскольку никаких чужих кодов при генерации ассемблерных команд ему использовать не требуется. Но вернемся к экстракодам.

Случай совпадения команд виртуальной и реальной машины

Разумеется, если команды виртуальной машины совпадают с реальными командами, экстракоды исчезают. Например, это происходит при работе с целыми числами:

declare(x,y,z) fixed(31);x=y*10-z/4;6B05040000000A      imul   eax,Y,108B1D08000000        mov    ebx,ZC1FB02              sar    ebx,22BC3                sub    eax,ebxA300000000          mov    X,eax

Здесь все действия однозначно отображаются на соответствующие команды процессора, хотя некоторые встроенные функции, например min и max могут реализовываться и через экстракоды.

Экстракоды и CISC-команды

Анализ применения экстракодов заставил даже по-новому взглянуть на RISC- и CISC-процессоры (т.е. на процессоры с сокращенным и обычным набором команд).

Безусловно, есть ряд задач, которые успешно решаются упрощенным набором команд. Однако в большом числе случаев RISC-команды создают только иллюзию упрощения решения, а на самом деле перекладывают сложность выполнения с процессора на программу. Команды становятся проще, а программа из них сложнее, да и число обращений к памяти больше.

Экстракоды при компиляции с языка достаточно высокого уровня это, конечно, аналог CISC-команд. Но даже в простой операции сравнения строк имеющейся CISC-команды CMPSB оказалось недостаточно для полного соблюдения требований языка.

Я бы предпочел, чтобы, например, все действия гипотетической команды PL1_CMPSB выполнялись бы внутри процессора. Это еще усложнило бы CISC-команды, но повысило бы общую производительность программы. Т.е. для упрощения компиляции и снижения числа обращений к памяти не хватает именно CISC- , а не RISC-команд. И с помощью экстракодов приходится создавать все новые и новые CISC-команды.

В конце концов, количество транзисторов на кристалле все время увеличивается. Для организации полноценной памяти на одном кристалле их все равно мало, а для реализации даже полной системы команд уже с избытком. Так пусть уж процессор больше действий выполняет внутри себя, не обращаясь к памяти.

Преимущества такого подхода хорошо видны на примере команды извлечения квадратного корня. Эта команда необходима во многих алгоритмах. Конечно, можно было бы не включать команду FSQRT в FPU процессора, а вычислять ее подпрограммой (например, по методу Ньютона). Однако вряд ли удалось бы реализовать такое вычисление быстрее, чем микропрограммой в кристалле процессора. Притом, что во время (длительного) выполнения команды FSQRT возможно параллельное выполнение других команд, например, целочисленной арифметики, что еще больше увеличивает общую производительность.

Заключение

Технология генерации программ с помощью экстракодов, как и любая другая, имеет и достоинства и недостатки.

Экстракоды могут уменьшить число уровней абстракции при приближении понятий языка к машинным командам. Причем, если понятия языка хорошо отображаются на процессорные инструкции, экстракоды становятся короткими и быстрыми, в ряде случаев просто исчезая и однозначно превращаясь в соответствующие команды процессора.

Использование экстракодов с одной стороны несколько усложняет компилятор, поскольку появляется большое число разновидностей передачи параметров и возврата результатов, что отражает архитектуру процессора, в данном случае команды IA-32. Зато, с другой стороны, весь процесс компиляции упрощается и сводится к единообразным вызовам экстракодов даже в случае достаточно сложных действий, над сложными объектами, описанными в программе.

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

Экстракоды находятся между двумя крайними стилями генерации кодов программы. Одна крайность это генерация в виде байт-кода, когда виртуальная машина совершенно не похожа на реальную, и требуется интерпретатор для исполнения каждой виртуальной команды. Другая крайность это генерация строго в машинные коды, по существу программирование на ассемблере.

Экстракоды позволяют с одной стороны сохранить некоторые особенности архитектуры процессора и. тем самым, повысить эффективность особенно за счет сокращения числа подготовительных действий. С другой стороны, при компиляции экстракоды позволяют оставаться на достаточно высоком уровне абстракции языка за счет использования более сложных команд (пусть и реализованных через подпрограммы), чем реально существующие процессорные инструкции. При этом генерируемый код остается вполне компактным.

Как-то попалось интересное (для меня), хотя и довольно давнее обсуждение языков программирования, где упоминался и язык 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;

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