привет всем. я здесь новичёк.
в университете поставили задачу создать простейшийинтерпретатор языка программирования. почти что все уже я реализовал, но вот у меня сейчас встал вопрос касаемо реализации вызова ф-ций самих из себя. видимо, я что-то здесь пропустил и недореализовал, т.к. рекурсивные версии ф-ций не всеработают корректно в моем ЯП.
скажем, если описать ф-цию фиббоначчи на моем языке:
int fibbonachi(int n){
print("n=");print(n); ##debug
if (n<=0){print("BUG");} ##debug
if (n<=2){return 1;}
return fib(n-1)+fib(n-2);
}
а ежели ф-цию по вычислению факториала числа, то получу верный дебаг вывод и результат
int fact(int x){
if (x==0){return 1;}
return x*fact(x-1);
}
***n=5n=4n=3n=2n=1n=0
результат равен 120. (здесь не указал просто)
я так понимаю, я не предусмотрел создание при кажд вызове ф-ции её фрейма, чтобы при кажд новом её вызове аргументы ф-ции были бы независимы от аргументов которые были переданы в ф-цию в её предыдущем вызове.
сейчас у меня при кажд вызове ф-ции используются одни и те же аргументы (переменные лежащие в таблице), и ,после первого прогона ф-ции fib(n-1) в n заносится 0, и далее в вызов fib(n-2) заносится уже нуль, а не значение вычисленное относительно оригинального значения параметра n. отсюда и баг.
вопрос -- правильно ли я догадываюсь, что мне надо реализовать копирование значений аргументов при каждом рекурс. вызове ф-ции в свою область, "фрейм", чтобы они были независимы между др др??
(так досадно, все реализовал, а вот с функциями недогоняю...а на лекциях эти тонкости не разобрали мы, потому не знаю что и предприняыть).
большое всем спасибо.
Re: вызов ф-ций: нужен ли фрейм?? (пишу интерпретатор)
Здравствуйте, sinmaster, Вы писали:
S>вопрос -- правильно ли я догадываюсь, что мне надо реализовать копирование значений аргументов при каждом рекурс. вызове ф-ции в свою область, "фрейм", чтобы они были независимы между др др??
Правильно.
Другой подход: просто объявить, что в твоем языке рекурсия не поддерживается (вроде как, в Паскале она не поддерживалась, не помню уже точно), и предложить всем сводить рекурсию к циклам — это всегда возможно, есть теорема на этот счет.
Попробуй хранить аргументы функции на вершине std::stack; вершина и есть фрейм.
People who are more than casually interested in computers should have at least some idea of what the underlying hardware is like. Otherwise the programs they write will be pretty weird (c) D.Knuth
Re: вызов ф-ций: нужен ли фрейм?? (пишу интерпретатор)
Ну ты все правильно понимаешь. Для упрощения управления локальными переменными можно иметь стековую стркутуру (как, собственно, и сделано в жизни) и, соответственно, при кажлм входе в функцию добавлять в стек, а при выходе — удалять.
Да здравствует мыло душистое и веревка пушистая.
Re[2]: вызов ф-ций: нужен ли фрейм?? (пишу интерпретатор)
Здравствуйте, gear nuke, Вы писали:
GN>Здравствуйте, sinmaster,
GN>Попробуй хранить аргументы функции на вершине std::stack; вершина и есть фрейм.
хм. сейчас у меня класс "функция" содержит вектор переданных аргументов. фактически это вектор содержащий индексы переменных, которые лежат все в одной глобальной таблице. а на стадии синтаксич. разбора я пробежался по прототипу определенной пользователем ф-ции, создал в таблице переменные. и далее при синтаксич. разборе тела этой ф-ции я проверяю каждое использование переменной на наличие ее в этой таблице. если нету — выдаю ошибку "undefined identifier".
я это к тому что void f(int x){ if (x==1){...} ... } вот здесь у меня в теле ф-ции переменная "x" и переменная "x" объяваленная в параметрах этой ф-ции имеют один и тот же индекс в таблице переменных...
если я сейчас прикручу использование вышеописанного "фрейма/стека" для вызова ф-ции, то получается что мне каким-то образом нужно будет в теле ф-ции ту же переменную "x" пересослать на др индекс, чтобы она брала свое значение не из моей таблицы а из фрейма ф-ции. как бы вот этот шаг безболезненно сделать..?
спасибо кстати за подсказки
Re[3]: вызов ф-ций: нужен ли фрейм?? (пишу интерпретатор)
sinmaster пишет:
> я так понимаю, я не предусмотрел создание при кажд вызове ф-ции её > фрейма, чтобы при кажд новом её вызове аргументы ф-ции были бы > независимы от аргументов которые были переданы в ф-цию в её предыдущем > вызове.
Конечно. Нужны фреймы. Не понятно только, что ты спрашиваешь, если
сам же всё и знаешь.
> вопрос -- правильно ли я догадываюсь, что мне надо реализовать > копирование значений аргументов при каждом рекурс. вызове ф-ции в свою > область, "фрейм", чтобы они были независимы между др др??
На самом деле не обязательно всё копировать, если что-то не меняется,
можно просто увеличивать "счётчик ссылок" и не копировать.
Кроме этого, если ты ещё сделаешь оптимизацию хвостовой рекурсии,
будет вообще очень здорово.
Здравствуйте, sinmaster, Вы писали:
S>хм. сейчас у меня класс "функция" содержит вектор переданных аргументов.
Значит стек будет состоять из векторов (фреймов). Кажется, зря аргументы инкапсулированы в класс "функция", стек данных — отдельная сущность. А функция принимает ссылку (или указатель) на соотв. фрейм.
S> фактически это вектор содержащий индексы переменных, которые лежат все в одной глобальной таблице. а на стадии синтаксич. разбора я пробежался по прототипу определенной пользователем ф-ции, создал в таблице переменные.
Выходит, что все переменные — глобальные, независимо от того, где они объявлены? Что бы сильно не передалывать, можно попробовать простой трюк — префиксировать имена локальных переменных именем (или индекс, что у тебя) функции.
S>я это к тому что void f(int x){ if (x==1){...} ... } вот здесь у меня в теле ф-ции переменная "x" и переменная "x" объяваленная в параметрах этой ф-ции имеют один и тот же индекс в таблице переменных...
Да, аргумент функции — локальная переменная для неё.
S>если я сейчас прикручу использование вышеописанного "фрейма/стека" для вызова ф-ции, то получается что мне каким-то образом нужно будет в теле ф-ции ту же переменную "x" пересослать на др индекс, чтобы она брала свое значение не из моей таблицы а из фрейма ф-ции. как бы вот этот шаг безболезненно сделать..?
По идее, перед вызовом функции создается новый фрейм на вершине стека, туда копируются либо значения, либо ссылки на переменные (в зависимости от того, передаются ли переменные по значению, или нет) и функции передаём ссылку на фрейм. После возврата фрейм снимается со стека. Стек он и нужен, что бы избежать копирования, которое в любом случае должно эмулировать стек.
People who are more than casually interested in computers should have at least some idea of what the underlying hardware is like. Otherwise the programs they write will be pretty weird (c) D.Knuth
Re[2]: вызов ф-ций: нужен ли фрейм?? (пишу интерпретатор)
Здравствуйте, jazzer, Вы писали:
J>Здравствуйте, sinmaster, Вы писали:
S>>вопрос -- правильно ли я догадываюсь, что мне надо реализовать копирование значений аргументов при каждом рекурс. вызове ф-ции в свою область, "фрейм", чтобы они были независимы между др др??
J>Правильно.
J>Другой подход: просто объявить, что в твоем языке рекурсия не поддерживается (вроде как, в Паскале она не поддерживалась, не помню уже точно), и предложить всем сводить рекурсию к циклам — это всегда возможно, есть теорема на этот счет.
Поддерживалась
Re[2]: вызов ф-ций: нужен ли фрейм?? (пишу интерпретатор)
спасибо за содержательный пост. за эти неск дней я разобрался с проблемкой. сейчас смотрю в сторону оптимизации хвостовой рекурсии, как вы и посоветовали. изучаю.
MZ>Где учишься -то ?
в провинции. прикладная математика и информатика
Re[4]: вызов ф-ций: нужен ли фрейм?? (пишу интерпретатор)
Здравствуйте, gear nuke, Вы писали:
GN>По идее, перед вызовом функции создается новый фрейм на вершине стека, туда копируются либо значения, либо ссылки на переменные (в зависимости от того, передаются ли переменные по значению, или нет) и функции передаём ссылку на фрейм. После возврата фрейм снимается со стека. Стек он и нужен, что бы избежать копирования, которое в любом случае должно эмулировать стек.
скажите, плз, а как можно сделать что-то подобное? стек, принимающий как значения, так и ссылки на переменные..?
Re[5]: вызов ф-ций: нужен ли фрейм?? (пишу интерпретатор)
Здравствуйте, sinmaster, Вы писали:
S>как можно сделать что-то подобное? стек, принимающий как значения, так и ссылки на переменные..?
Написав "либо", я имел ввиду что-то одно из двух (что в задании, скорее всего там один тип int, который передаётся только по значению?). Если же нужна поддержка разных типов, то см. в сторону variant. Хотя, тип передаваемого значения виден в сигнатуре функции, можно передавать
union int_or_refint{ int int_value; int * refint};
People who are more than casually interested in computers should have at least some idea of what the underlying hardware is like. Otherwise the programs they write will be pretty weird (c) D.Knuth
Re[6]: вызов ф-ций: нужен ли фрейм?? (пишу интерпретатор)
