|
|
ru.algorithms- RU.ALGORITHMS ---------------------------------------------------------------- From : Andrew Ezhguroff 2:5020/400 09 Jan 2002 05:21:06 To : Andrey Tarasevich Subject : Re: Гоpодская олимпиада по инфоpматике -------------------------------------------------------------------------------- Привет! "Andrey Tarasevich" <atarasevich@telocity.com> сообщил(а): AT> (Антиоффтопик: тут мы уже говорим об алгоритмах, т.е. это не оффтопик.) AT> Что-то я не вижу в этом никаких сложностей. Точнее, я не вижу никакой AT> разницы в организации кадров стека при наличии и отсутствии рекурсии. Согласен, это я загнул. Проблема не столько в рекурсии, сколько в том, что "расстояние" в стеке между кадром текущей подпрограммы и кадром охватывающей подпрограммы не фиксировано. AT> Зачем вести список активаций (а уж тем более заводить свой стек кадров AT> для каждой функции)? Рекурсивная функция в Паскале имеет доступ только AT> к текущему контексту, т.е. она имеет доступ только к самому позднему AT> своему кадру стека и только к самому позднему кадру стека каждой AT> охватывающей функции. Доступа к предыдущим своим (и чужим) кадрам стека AT> она не имеет и ничего о них не знает. Hаиболее очевидный алгоритм - для каждой подпрограммы существует неявная статическая (в смысле Си) переменная, содержащая указатель на активный кадр своей подпрограммы. При вызове подпрограммы этот указатель сохраняется в стеке и в переменную заносится адрес нового кадра. При этом обеспечивается и рекурсия и удобный доступ к переменным охватывающих функций. Hо это и есть список активаций (в неявной форме). AT> Если F вызывается из E, то вызывающий код кладет в формируемый кадр AT> указатели на кадры стека A...D из текущего кадра стека E (они там, AT> разумеется есть) и затем добавляет туда указатель на текущий кадр стека AT> функции E. AT> Если F вызывается из F' (функция, прямо или опосредованно вложенная в AT> E), то пять первых указателей из кадра стека F' просто копируются в AT> формируемый кадр стека F. Причем допускается, что F' == F или F' AT> вложено в F. ИМХО, вариант со статическими указателями эффективней - не требуется лишних копирований, т.к. в каждый момент времени в этих неявных переменных находятся указатели на активные кадры соответствующих подпрограмм. AT> а есть в AT> стандартном Паскале косвенные вызовы?. Есть. AT> В Борланде почти 100%-ным аналогом С-шных статических переменных, AT> объявленных в локальном scope, являются типизированные "константы". Я AT> не знаю, есть ли они в стандартном Паскале. В стандартном Паскале возможны только константы простых типов и строки. AT> Большая проблема глобальных (и статических) переменных - AT> нереентерабельность кода, использующего эти переменные. В первую AT> очередь поэтому их и избегают на практике. Во первых не очень понятно, где необходим реентерабельный код (плагины?, dos'овские резиденты?), а во вторых частичная реентерабельность (загрузка модуля с любого адреса, но не перемещение его по адресному пространству) может прекрасно совмещаться с абсолютными адресами (коррекция абсолютных адресов производится во время запуска программы на выполнение). С уважением, Андрей. -- Отправлено через сервер Talk.Ru - http://www.talk.ru --- ifmail v.2.15dev5 * Origin: Talk.Ru (2:5020/400) Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
Архивное /ru.algorithms/6488bb92c49d.html, оценка из 5, голосов 10
|