Каким должен быть язык программирования? Анализ и критика Описание языка Компилятор
Отечественные разработки Cтатьи на компьютерные темы Компьютерный юмор Новости и прочее

О размещении переменных в стеке

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

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

  • точность решения сформулированной задачи;
  • эффективность кода (по требуемой памяти и скорости работы);
  • простота её реализации на данном языке;
  • понятность алгоритма при минимуме комментариев;
  • читабельность кода;
  • краткость кода.
Для языка PL/1 был предложен следующий вариант:
PL1_EXAMPLE: PROCEDURE OPTIONS(MAIN);
DECLARE I FIXED CONTROLLED;

ON ENDFILE(SYSIN) GOTO L2;

L1: ALLOCATE I;
    GET LIST(I);
    IF MOD(I,2)=0 THEN FREE I;
GOTO L1;

L2: FREE I;
DO WHILE(ALLOCATION(I));
    PUT LIST(I);
    FREE I;
END;
END PL1_EXAMPLE;
            На мой взгляд, можно было бы ещё укоротить текст. Поставив метку L2 прямо внутрь цикла DO WHILE и сократив, тем самым, один оператор FREE. Но согласен, это не лучший стиль программирования — входить в цикл не через заголовок.

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

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

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

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

            Для x86-64 эти дополнительные коды будут выглядеть так (учитывая, что в «куче» есть двунаправленный связанный список и восьмью байтами «ранее» в «куче» находится адрес следующего участка выделяемой памяти):

для ALLOCATE
E800000000                  call   ?ALLOA
488BCB                      mov    rcx,rbx
F048871D20000000            xchg   ?P0001,rbx
488B49F8                    mov    rcx,0FFFFFFF8h[rcx]
488959F8                    mov    0FFFFFFF8h[rcx],rbx
для FREE
BB20000000                  mov  q rbx,offset ?P0001
488B0B                      mov  q rcx,[rbx]
488B49F8                    mov  q rcx,0FFFFFFF8h[rcx]
488B49F8                    mov  q rcx,0FFFFFFF8h[rcx]
F048870B                    xchg q rcx,[rbx]
488BD9                      mov  q rbx,rcx
E800000000                  call   ?FREOP
            Однако даже в такой простой реализации оказался свой подводный камень – число служебных указателей (?P0001,?P0002…) становится известным только после полного разбора исходного текста, а проще всего заводить их как раз в начале разбора, просто дописывая в таблицу стандартных объектов. Чтобы не переусложнять разбор, число служебных указателей я сделал настраиваемым через реестр (как и ключи компилятора). Небольшое число таких указателей компилятор имеет, на всякий случай, всегда, а если требуется большое число controlled-переменных, тогда их число всегда можно увеличить через реестр, не меняя компилятор.

            Также для упрощения функции ALLOCATION её пришлось сделать с параметром «адрес», что потребовало ещё обращаться к имеющейся встроенной функции ADDR. Т.е. вместо обращения типа:
IF ALLOCATION(X) THEN… 
применяется более громоздкое обращение:
IF ALLOCATION(ADDR(X)) THEN…
Которое зато позволяет вообще не менять компилятор, а лишь дописать в его таблицу стандартных функций новое имя и тип параметра. Таким образом, у меня тест принял следующий вид:
TEST:PROC MAIN;

DCL I FIXED(31) STACK;

ON ENDFILE(SYSIN) GO L1;

DO REPEAT;
   ALLOCATE I;  
   GET LIST(I);
   IF MOD(I,2)=0 THEN FREE I;
END REPEAT;

L1:FREE I;

DO WHILE(ALLOCATION(ADDR(I)));
   PUT LIST(I); 
   FREE I;
END WHILE;

END TEST;
Или то же самое с русскими ключевыми словами:
ТЕСТ:ПРОЦ ГЛАВНАЯ;

ОПС I ТОЧНОЕ(31) СТЕК;

КОГДА КОНЕЦ_ФАЙЛА(СТД_ВВОД) ИДТИ L1;

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

L1:ВЕРНУТЬ_ПАМЯТЬ I;

ЦИКЛ ПОКА(ЕСТЬ_В_СТЕКЕ(АДРЕС(I)));
   ПЕЧАТАТЬ В_ВИДЕ(I);
   ВЕРНУТЬ_ПАМЯТЬ I;
КОНЕЦ ПОКА;

КОНЕЦ TEСT;
            Легко проверить, что если запустить такой тест и вводить с клавиатуры, например, 1 2 3 4 5 6 7 8 9 Ctrl+Z (последний символ сигнализирует о конце ввода), то на экран выдается требуемая последовательность: 9 7 5 3 1.

            Поскольку я считаю название «controlled» неинформативным, на русский язык я перевел его все-таки как «СТЕК» и приравнял атрибуты памяти CONTROLLED и STACK, подчеркивая, тем самым, организацию памяти в виде стека (пусть фактически и в виде связанного списка), а функцию ALLOCATION соответственно как ЕСТЬ_В_СТЕКЕ.

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

            Что касается предложенного теста, то, скорее всего, изначально он задумывался для демонстрации рекурсии, например, на том же PL/1 такой текст даже короче (не нужно явно выделять и освобождать память), хотя делает то же самое:
TEST:PROC MAIN;

F;

F:PROC RECURSIVE;
DCL I FIXED;

ON ENDFILE(SYSIN) GO L1;

GET LIST(I);
F;
IF MOD(I,2)^=0 THEN PUT LIST(I);

L1:
END F;

END TEST;
            Однако лично я все же присудил бы победу первому варианту с controlled-переменными, особенно по критерию эффективности. Так как при рекурсии для запоминания всего лишь одной переменной приходится запоминать все состояние рекурсивной процедуры. Кроме этого, «стековые» переменные могут существовать и после выхода из подпрограммы, что в некоторых случаях может оказаться практически удобным свойством.

Автор: Д.Ю.Караваев.

Опубликовано: 2018.12.03, последняя правка: 2019.01.28    20:51

ОценитеОценки посетителей
   ████████████ 5 (27.7%)
   ████████████ 5 (27.7%)
   ████████████ 5 (27.7%)
   ███████ 3 (16.6%)

Добавить свой отзыв

Написать автору можно на электронную почту
mail(аt)compiler.su

Авторизация

Регистрация

Выслать пароль

Карта сайта


Содержание

Каким должен быть язык программирования?

Анализ и критика

Описание языка

Компилятор

Отечественные разработки

Cтатьи на компьютерные темы

●  О превращении кибернетики в шаманство

●  Про лебедей, раков и щук

●  О замысле и воплощении

●  О русском ассемблере

●  Арифметика синтаксиса-3

●  Концепция владения в Rust на примерах

●●  Концепция владения в Rust на примерах, часть 2

●●  Концепция владения в Rust на примерах, часть 3

●  Суть побочных эффектов в чисто функциональных языках

●  О неулучшаемой архитектуре процессоров

●  Двадцать тысяч строк кода, которые потрясут мир?

●  Почему владение/заимствование в Rust такое сложное?

●  Масштабируемые архитектуры программ

●  О создании языков

●●  Джоэл Спольски о функциональном программировании

●  Почему Хаскелл так мало используется в отрасли?

●  Программирование исчезнет. Будет дрессировка нейронных сетей

●  О глупости «программирования на естественном языке»

●  Десятка худших фич C#

●  Бесплатный софт в мышеловке

●  Исповедь правового нигилиста

●  ЕС ЭВМ — это измена, трусость и обман?

●  Русской операционной системой должна стать ReactOS

●  Почему обречён язык Форт

●  Программирование без программистов — это медицина без врачей

●  Электроника без электронщиков

●  Программисты-профессионалы и программирующие инженеры

●  Статьи Дмитрия Караваева

●●  Идеальный транслятор

●●  В защиту PL/1

●●  К вопросу о совершенствовании языка программирования

●●  Опыт самостоятельного развития средства программирования в РКК «Энергия»

●●  О реализации метода оптимизации при компиляции

●●  О реализации метода распределения регистров при компиляции

●●  О распределении памяти при выполнении теста Кнута

●●  Опыты со стеком или «чемпионат по выполнению теста Кнута»

●●  О размещении переменных в стеке

●●  Сколько проходов должно быть у транслятора?

●●  Чтение лексем

●●  Экстракоды при синтезе программ

●●  Об исключенных командах или за что «списали» инструкцию INTO?

●●  Типы в инженерных задачах

●●  Непрерывное компилирование

●●  Об одной реализации специализированных операторов ввода-вывода

●●  Особенности реализации структурной обработки исключений в Win64

●●  О русском языке в программировании

●●  Формула расчета точности для умножения

●●  Права доступа к переменным

●●  Заметки о выходе из функции без значения и зеркальности get и put

●●  Модификация исполняемого кода как способ реализации массивов с изменяемыми границами

●●  Ошибка при отсутствии выполняемых действий

●●  О PL/1 и почему в нём не зарезервированы ключевые слова

●●  Не поминайте всуе PL/1

●●  Скорость в попугаях

●●  Крах операции «Инкогнито»

●●  Предопределённый результат

●●  Поддержка профилирования кода программы на низком уровне

●●  К вопросу о парадигмах

●  Следующие 7000 языков программирования

●●  Что нового с 1966 года?

●●  Наблюдаемая эволюция языка программирования

●●  Ряд важных языков в 2017 году

●●  Слоны в комнате

●●  Следующие 7000 языков программирования: заключение

Компьютерный юмор

Новости и прочее




Последние отзывы

2024/12/07 20:54 ••• Клихальт
Переключатель

2024/12/06 18:44 ••• Анкнав
Русский язык и программирование

2024/12/01 00:00 ••• alextretyak
Продолжение цикла и выход из него

2024/11/29 23:08 ••• Вежливый Лис
О русском ассемблере

2024/11/26 23:53 ••• Бурановский дедушка
ЕС ЭВМ — это измена, трусость и обман?

2024/11/25 18:31 ••• Деньги на WWWетер
Ресурсы, посвящённые созданию языков программирования и компиляторов

2024/11/12 20:24 ••• Вежливый Лис
Правила языка: строки, комментарии

2024/11/12 13:10 ••• Вежливый Лис
Новости и прочее

2024/11/12 00:32 ••• Автор сайта
Оценка надёжности функции с несколькими реализациями

2024/11/06 02:50 ••• Иван
Энтузиасты-разработчики компиляторов и их проекты

2024/11/05 23:51 ••• Борис К.
Изменение приоритетов операций

2024/11/05 23:38 ••• Борис К.
Шестнадцатиричные и двоичные константы

2024/11/01 12:11 ••• ИванАс
Русской операционной системой должна стать ReactOS