Об одной реализации рекурсии

Первая публикация 29.07.2014 

On a recursion implementation

Введение

Если бы меня не опередил классик, я начал бы статью словами: «любите ли Вы рекурсию так, как люблю ее я? Нет, Вы не можете любить рекурсию так, как я!» Но, во-первых, это плагиат, а, во-вторых, неправда. У меня нет причин любить или не любить рекурсию как один из базовых механизмов в программировании. Да и в предметной области, в которой я работаю (инженерные расчеты), необходимость в рекурсивных алгоритмах встречается не часто. И вообще может показаться, что какая-то специальная «реализация» рекурсии в современной компьютерной архитектуре бессмысленна: если для подпрограммы локальные переменные размещаются в стеке, возможность рекурсивного вызова такой подпрограммы получается «сама собой» и не требует никаких дополнительных действий. Однако такой подход возможен не во всех случаях.

Еще во времена Алгола были сложности с реализацией так называемых «собственных значений процедуры», т.е. локальных переменных, которые должны были сохранять свое значение между вызовами данной процедуры. Очевидно, что для таких переменных нельзя просто выделять место в стеке, поэтому реализация рекурсивного вызова процедур с собственными значениями усложнялась. Есть и менее очевидные трудности. Например, как было показано в [1], при вычислениях выражений транслятору не всегда удается сохранять промежуточные результаты только в регистрах или стеке. В некоторых случаях появляется необходимость использовать служебные переменные в памяти (недоступные программисту), что опять-таки делает невозможной простую организацию рекурсивных вызовов.

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

Определение рекурсивности подпрограммы

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

В используемом мною языке PL/1 данная проблема решается очень просто: вся ответственность возлагается на программиста. Если он не указывает ключевое слово «RECURSIVE» в заголовке подпрограммы, транслятор не выполняет никаких действий для поддержки рекурсивного вызова. Альтернативным такому подходу является или обеспечение рекурсивного вызова для любой подпрограммы или (как в первых поколениях Фортрана) запрет на рекурсивный вызов вообще. Лично меня явное указание возможности рекурсии вполне устраивает. И дело не в том, что не рекурсивные процедуры встречаются чаще и потенциально могут быть проще организованы в части данных. Я считаю, что только программист, как автор алгоритма, может (и обязан) определить, допустима ли в данном случае рекурсия, и приведет ли она к правильным результатам. Никакой транслятор не сможет определить допустимость и правильность рекурсии в конкретном алгоритме, даже если он и обнаружит саму эту рекурсию в вызове подпрограмм.

Реализация рекурсивных вызовов

Итак, в рассматриваемом трансляторе с языка PL/1 подпрограммы делятся на явно рекурсивные и все остальные. В не рекурсивных подпрограммах после вызова начинают непосредственно выполняются команды алгоритма. В явно рекурсивных подпрограммах при входе сначала производится обращение к системной подпрограмме, внутри которой выделяется память из кучи и в выделенный сегмент переписывается все текущее поколение локальных данных в том состоянии, в котором они были на момент вызова рекурсивной подпрограммы.

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

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

Однако в случае PL/1 только этих действий недостаточно. Если происходит выход из подпрограммы не через заключительный оператор, необходимо еще с помощью отдельной системной подпрограммы уничтожить возможные «незакрытые» внутренние вызовы, т.е. убрать из кучи все дальнейшие поколения запомненных локальных данных всех рекурсивных процедур. Для этой цели, кроме памяти под собственно поколение локальных данных, в том же сегменте выделяется еще несколько слов под служебную информацию. За счет этого, во-первых, все выделенные «под рекурсию» сегменты кучи объединяются в связанный список, якорь которого известен системной подпрограмме очистки, а во-вторых, вместе с данными запоминается и текущее значение стека. Подпрограмма очистки идет по связанному списку «рекурсивных» сегментов и возвращает их в свободную память кучи до тех пор, пока текущее значение стека не станет меньше значения стека, указанного в очередном сегменте.

К сожалению, даже всего перечисленного опять недостаточно для организации рекурсивного вызова в PL/1 во всех возможных случаях. Хотя оставшаяся проблема связана не столько с рекурсией, сколько с организацией транслятора. Когда транслятор генерирует системный вызов запоминания локальных данных, он знает их размер и начальный адрес еще до начала генерации команд рекурсивной подпрограммы потому, что это, так сказать, «рекурсивные данные пользователя». Они явно описаны в программе, их анализ транслятором уже проведен и их размер уже известен и не изменится. А вот размер «рекурсивных служебных данных», которые могут появиться при разборе выражений и генерации команд подпрограммы, в этой точке еще неизвестен и не известно, потребуются ли такие данные вообще. Транслятор «узнает» об этом только в конце генерации команд подпрограммы, а не в точке входа в подпрограмму, где он уже поставил системный вызов. Чтобы обойти эту сложность и не обрабатывать каждую рекурсивную подпрограмму два раза только для того, чтобы узнать о необходимости дополнительных данных, транслятор генерирует сразу два разных системных вызова запоминания локальных данных: отдельно для «рекурсивных данных пользователя» и отдельно для «рекурсивных служебных данных». В первом случае размер данных определяется командой загрузки константы, во втором случае – загрузкой служебной переменной, значение которой транслятор определяет в конце генерации команд рекурсивной подпрограммы и записывает в объектный модуль формата OMF 8086/8087 как дополнительную настройку данных, аналогично тому, как производится начальная инициализация статических переменных. Т.е. собственно запись размера данных в служебную переменную осуществляет уже не транслятор, а редактор связей.

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

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

В результате, в 32-х разрядной системе если присутствуют только «рекурсивные данные пользователя», то накладные расходы на каждый рекурсивный вызов с учетом организации кучи [3] составляют 28 байт плюс размер самих локальных данных. Если же присутствуют и «рекурсивные служебные данные», то накладные расходы возрастают до 44 байт плюс общая длина всех данных.

Пример генерации системных вызовов рекурсии

Ниже приведены фрагменты служебного вывода работы транслятора вместе с получившимися командами.

В главной программе TEST описана рекурсивная подпрограмма F1. При начале работы программы TEST в служебной переменной @000007F8H запоминается текущее значение стека (т.е. регистра ESP).

1   000000 TEST:PROC MAIN;

000000 B88C9B4002……………mov….eax,37788556
000005 E800000000……………call……?START
00000A 8925F8070000………..mov….@000007F8h,esp
000010 E900000000……………jmp….@1

Затем транслятор обрабатывает вход в подпрограмму F1. Он загружает в регистр ECX размер всех локальных данных F1 (в примере 64 байта), а в регистр EDX начальный адрес этих данных. Затем следует вызов системной подпрограммы ?SVBLK, которая и запоминает эти 64 байта, начиная с указанного адреса, в памяти, выделенной из кучи.

Затем следует загрузка в ECX значения служебной переменной @00000828H, в которой будет размер дополнительных данных или ноль. В регистр EDX загружается начальный адрес дополнительных данных, если бы они появились. Этот адрес просто следующий за служебной переменной.

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

3   000015 F1:PROC(I,J,K,L,M) RECURSIVE;

4   000015 DCL (I,J,K,L,M) FIXED(31);

000015 6A40…………………………push…..64
000017 59……………………………..pop…….ecx
000018 BA28080000…………….mov……edx,offset @000000828h
00001D E800000000……………call……..?SVBLK
000022 8B0D70080000………..mov…….ecx,@0000000870h
000028 BA74080000…………….mov…….edx,offset @000000874h
00002D E800000000……………call………?SVBLS
…

В конце подпрограммы F1 транслятор генерирует вызов системной подпрограммы ?RSBLK, которая переписывает запомненные байты обратно из сегментов в программу. Поскольку все адреса и размеры хранятся внутри выделенной памяти, никаких параметров для этого системного вызова не требуется.

17  0002D5 END F1;

0002D5 E800000000……….call ?RSBLK
0002DA C3……………………….ret

Внутри подпрограммы F1 стоит также выход наружу прямо с помощью оператора GOTO. Хотя это может показаться нарушением всяких правил, в данном случае это  имеет практический смысл. Например, если по ходу рекурсивного алгоритма обнаружена ошибка, бывает затруднительно вернуться через много поколений «старших» рекурсивных вызовов. В этом случае прямой оператор GOTO и проще и понятней. В примере метка перехода M1 стоит в главной программе. В этой точке, во-первых, восстанавливается исходное значение стека, а во-вторых, вызывается системная подпрограмма ?RECOV, которая и освобождает память в куче от «рекурсивных» сегментов, ориентируясь по текущему значению стека и значению стека, запомненному в каждом сегменте.

…
11 00028E IF I>0 THEN GOTO M1;
…….00028E 833D3C08000000………cmp…..I,0
…….000295 7E02……………………………jle…….@3
…….000297 EB6A…………………………..jmps….M1
…….000299…………………………………..@3:
…
…….000303…………………………………..M1:
…….000303 8B25F8070000…………..mov…….esp,@000007F8h
…….000309 E800000000………………call……..?RECOV

Разумеется, если бы в описании подпрограммы F1 не было бы слова «RECURSIVE», и внутри нее не использовался бы GOTO, всех этих системных вызовов и переменных транслятор бы не создавал.

Исходный текст служебных подпрограмм

Ниже приведен исходный текст служебных подпрограмм запоминания и восстановления локальных данных при рекурсивных вызовах. Якорь связанного списка хранится в переменной ?RECLST. Также используются системные подпрограммы захвата и освобождения памяти в куче.

В тексте команда «THR» является не командой процессора, а макроопределением захвата и проверки семафора для возможной работы параллельных потоков. Сам семафор хранится в переменной ?THREAD_REC. Возможность работы параллельных потоков приходится учитывать и при анализе значения стека в подпрограмме восстановления ?RSBLK. «Рекурсивные» сегменты от других потоков будут «сильно» отличаться значением стека, в то время как сегменты одного потока будут иметь близкие значения стека.

;========= СОХРАНИТЬ СОДЕРЖИМОЕ ДАННЫХ РЕКУРСИВНОЙ ПРОЦЕДУРЫ =========
EXTRN ?ALLOA:NEAR……………;ВЫДЕЛЕНИЕ ПАМЯТИ ИЗ КУЧИ
EXTRN ?FREOP:NEAR.…………..;ОСВОБОЖДЕНИЕ ПАМЯТИ И ВОЗВРАТ В КУЧУ
;—————— ЗАПОМИНАНИЕ ДАННЫХ ПОЛЬЗОВАТЕЛЯ ——————
PUBLIC ?SVBLK:……………………..;ВЫЗЫВАЕТСЯ ИЗ PL/1
…….PUSH…….EBX,EDX,ECX………….;ЗАПОМНИЛИ РЕГИСТРЫ
…….LEA……….EBX,[ECX]+20…………;ЧИСЛО БАЙТ И СЛУЖЕБНОЙ ИНФОРМАЦИИ
;—- ЖДЕМ ОСВОБОЖДЕНИЯ ПОТОКА ПО РЕКУРСИИ —-
THR ?THREAD_REC
;—- ВЫДЕЛИЛИ ПАМЯТЬ ИЗ КУЧИ ДЛЯ ЗАПОМИНАНИЯ —-
CALL ?ALLOA…………………………..;ВЫДЕЛИЛИ ПАМЯТЬ ИЗ КУЧИ
;—- ВСТАВЛЯЕМ В СВЯЗАННЫЙ СПИСОК ЗАПОМНЕННЫХ ДАННЫХ —-
MOV…………EAX,EBX………………..;НАЧАЛО ВЫДЕЛЕННОЙ ПАМЯТИ
LEA…………..EDX,[ESP]+4+3*4….;ЗНАЧЕНИЕ СТЕКА
XCHG………..EAX,?RECLST……….;НОВОЕ ЗНАЧЕНИЕ ВЕРШИНЫ СПИСКА
AND…………..D PTR [EBX]+16,0…;ПОКА НЕТ СЛУЖЕБНЫХ ДАННЫХ
MOV…………..[EBX]+00,EAX……..;ПРЕДЫДУЩЕЕ ЗНАЧЕНИЕ ВЕРШИНЫ СПИСКА
;—- ЗАПОМИНАЕМ ТЕКУЩЕЕ ЗНАЧЕНИЕ СТЕКА —-
MOV…………[EBX]+04,EDX………………….;ЗАПОМНИЛИ СТЕК
;—- ЗАПОМИНАЕМ НАЧАЛО И ОБЪЕМ ДАННЫХ В ПРОГРАММЕ —-
POP………….ECX,EDX
MOV…………[EBX]+08,EDX……….;АДРЕС ДАННЫХ БЛОКА
MOV…………[EBX]+12,ECX………..;ЧИСЛО БАЙТ ДАННЫХ БЛОКА
JECXZ………M1………………………….;ВООБЩЕ НЕТ ДАННЫХ ПОЛЬЗОВАТЕЛЯ
;—- ПЕРЕПИСЫВАЕМ ЭКЗЕМПЛЯР ДАННЫХ ИЗ ПРОГРАММЫ И ЗАПОМИНАЕМ ИХ —-
LEA………….EDI,[EBX]+20………..;КУДА СОХРАНЯЮТСЯ
MOV…………ESI,EDX………………..;ОТКУДА БЕРУТСЯ ДАННЫЕ
SHR………….ECX,1
JNC       @
MOVSB
@:          SHR ECX,1
JNC       @
MOVSW
@: REP MOVSD……………………..;СОХРАНЕНИЕ ДАННЫХ
;—- ВОССТАНАВЛИВАЕМ СОСТОЯНИЕ EBX И ВЫХОДИМ —-
M1: POP EBX
RET
;—————– ЗАПОМИНАНИЕ СЛУЖЕБНЫХ ДАННЫХ ———————
PUBLIC ?SVBLS:………………;ВЫЗЫВАЕТСЯ ИЗ PL/1
…….JECXZ……..M2……………;ВООБЩЕ НЕТ СЛУЖЕБНЫХ ДАННЫХ
…….PUSH……….EBX,EDX,ECX……………..;ЗАПОМНИЛИ РЕГИСТРЫ
;—- ВЫДЕЛИЛИ ПАМЯТЬ В КУЧЕ ДЛЯ ЗАПОМИНАНИЯ —-
LEA EBX,[ECX]+8 ;ЧИСЛО БАЙТ ДАННЫХ, АДРЕС И ДЛИНА
CALL ?ALLOA………………………………;ВЫДЕЛИЛИ ПАМЯТЬ
;—- ВСТАВЛЯЕМ В СВЯЗАННЫЙ СПИСОК ЗАПОМНЕННЫХ ДАННЫХ —-
MOV…………EAX,?RECLST………….;ВЕРШИНА СПИСКА
POP………….ECX,EDX
LEA…………..EDI,[EBX]+8……………;МЕСТО ЗАПОМИНАНИЯ ДАННЫХ
MOV………….[EBX]+00,EDX………..;АДРЕС ДАННЫХ БЛОКА
MOV………….[EBX]+04,ECX…………;ЧИСЛО БАЙТ СЛУЖЕБНЫХ ДАННЫХ
MOV………….[EAX]+16,EBX…………;МЕСТО ДЛЯ ЗАПОМИНАНИЯ
MOV………….ESI,EDX………………….;ОТКУДА БЕРУТСЯ ДАННЫЕ
;—- ПЕРЕПИСЫВАЕМ СЛУЖЕБНЫЕ ДАННЫЕ В ВЫДЕЛЕННУЮ ПАМЯТЬ —
SHR ECX,1
JNC @
MOVSB
@: SHR ECX,1
JNC @
MOVSW
@: REP MOVSD……………………………….;СОХРАНЕНИЕ СЛУЖЕБНЫХ ДАННЫХ
;—- ВОССТАНАВЛИВАЕМ СОСТОЯНИЕ EBX И ВЫХОДИМ —-
POP EBX
M2: MOV ?THREAD_REC,CL.…………..;ОСВОБОДИЛИ СЕМАФОР ПО РЕКУРСИИ
RET
;== ВОССТАНОВИТЬ СОДЕРЖИМОЕ ДАННЫХ РЕКУРСИВНОЙ ПРОЦЕДУРЫ ========
PUBLIC ?RSBLK:……………………;ВЫЗЫВАЕТСЯ ИЗ PL/1
PUSH EAX,EBX……………………..;ЗАПОМНИЛИ ВОЗМОЖНЫЙ ОТВЕТ
MOV ECX,OFFSET ?RECLST
;—- ЖДЕМ ОСВОБОЖДЕНИЯ ПОТОКА ПО РЕКУРСИИ —-
THR ?THREAD_REC
;—- ДОСТАЕМ ИЗ ВЕРШИНЫ СВЯЗАННОГО СПИСКА —-
M3: MOV EBX,[ECX]
OR EBX,EBX……………………………………..;НИЧЕГО НЕТ ?
JZ M6………………………………………………..;ВООБЩЕ НЕ БЫЛО ЗАПОМНЕННЫХ ДАННЫХ
;—- ПРОВЕРКА ПО ЗНАЧЕНИЮ СТЕКА, ЧТО ЭТО НАШ ПОТОК —-
MOV EAX,ESP
SUB EAX,[EBX]+4………………………………;РАЗНОСТЬ СТЕКОВ
JNS @
NEG EAX…………………………………………….;АБСОЛЮТНАЯ РАЗНОСТЬ СТЕКОВ
@: CMP EAX,0FFFFH…………………………..;ЭТО НАШ ПОТОК ?
JB @…………………………………………………….;ДА, НАШЛИ СВОЙ ПОТОК
;—- ПРОПУСКАЕМ ЭЛЕМЕНТ ДРУГОГО ПОТОКА —-
MOV ECX,EBX………………………………………;ПРОПУСКАЕМЫЙ ЭЛЕМЕНТ
JMPS M3……………………………………………….;БЕРЕМ СЛЕДУЮЩИЙ ЭЛЕМЕНТ
;—- СДЕЛАЛИ ВЕРШИНОЙ СЛЕДУЮЩИЙ ЭЛЕМЕНТ В СПИСКЕ —-
@: MOV EAX,[EBX]………………………………..;АДРЕС СЛЕДУЮЩЕГО БЛОКА
XOR EDX,EDX………………………………………..;ПОКА НЕТ СЛУЖЕБНЫХ ДАННЫХ
MOV [ECX],EAX……………………………………..;ЗАПИСАЛИ ЕЕ КАК ВЕРШИНУ СПИСКА
;—- ПЕРЕПИСЫВАЕМ ДАННЫЕ ПОЛЬЗОВАТЕЛЯ ОБРАТНО В ПРОГРАММУ —-
MOV ECX,[EBX]+12…………………………………;СКОЛЬКО БАЙТ ВОССТАНАВЛИВАТЬ
MOV EDI,[EBX]+08…………………………………;АДРЕС КУДА ВОССТАНАВЛИВАТЬ
JECXZ М5………………………………………………..;НЕТ ВООБЩЕ ДАННЫХ ПОЛЬЗОВАТЕЛЯ
LEA ESI,[EBX]+20……………………………………;АДРЕС ОТКУДА ВОССТАНАВЛИВАТЬ
M4: SHR ECX,1
JNC @
MOVSB
@: SHR ECX,1
JNC @
MOVSW
@:    REP MOVSD………………………………………..;ВОССТАНОВЛЕНИЕ ДАННЫХ
;—- ПЕРЕПИСЫВАЕМ СЛУЖЕБНЫЕ ДАННЫЕ ОБРАТНО В ПРОГРАММУ —-
M5: XCHG ECX,[EBX]+16…………………………;АДРЕС СЛУЖЕБНЫХ ДАННЫХ
JECXZ @………………………………………………….;УЖЕ НЕЧЕГО ПЕРЕПИСЫВАТЬ
LEA ESI,[ECX]+08……………………………………;ОТКУДА
MOV EDI,[ECX]+00………………………………….;КУДА
MOV EDX,[ECX]+04…………………………………;СКОЛЬКО
XCHG EDX,ECX………………………………………..;ЕСТЬ СЛУЖЕБНЫЕ ДАННЫЕ
JMPS M4
;—- ОСВОБОЖДАЕМ КУЧУ ОТ СЛУЖЕБНЫХ ДАННЫХ —-
@: OR EDX,EDX……………………………………….;БЫЛИ СЛУЖЕБНЫЕ ДАННЫЕ ВООБЩЕ ?
JZ @…………………………………………………………;НЕ БЫЛО
PUSH EBX
MOV EBX,EDX
CALL ?FREOP
POP EBX
;—- ОСВОБОЖДАЕМ КУЧУ ОТ ДАННЫХ ПОЛЬЗОВАТЕЛЯ —-
@: CALL ?FREOP………………………………………;ОСВОБОДИЛИ ПАМЯТЬ ОТ БЛОКА
;—- ВОССТАНАВЛИВАЕМ СОСТОЯНИЕ EAX/EBX И ВЫХОДИМ —-
M6: POP EBX,EAX
MOV ?THREAD_REC,0……………………………..;ОСВОБОДИЛИ СЕМАФОР ПО РЕКУРСИИ
    RET
    DSEG
EXTRN ?RECLST:D,?THREAD_REC:B

Заключение

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

Использование для рекурсии не только аппаратного стека, но и памяти кучи (которая в 32-х разрядной среде Windows может превышать 3 Гбайта [4]) позволяет увеличить максимально допустимую «глубину» рекурсивных вызовов.

Литература

1. Караваев Д.Ю. О реализации метода распределения регистров при компиляции. RSDN Magazine #1, 2012
2. Караваев Д.Ю. К вопросу о совершенствовании языка программирования. RSDN Magazine #4, 2011
3. Караваев Д.Ю. О реализации контроля целостности структуры «кучи» при выделении памяти. RSDN Magazine #4, 2012
4. Караваев Д.Ю. О распределении памяти при выполнении теста Кнута. RSDN Magazine #2, 2012