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

Question

Предположим, у меня есть простой C-подобный язык программирования:

int foo() {
    int x = 10;
    int bar(y int) {
        return y * 2
    }
    return bar() + x
}

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

Стек-машина имеет два регистра, аккумулятор и временный регистр.
Каждый кадр содержит: [arguments, local variables, return address, caller frame and stack pointer, temporaries and data operations]и я использую один и тот же стек для фреймов вызовов и для оценки операций. Может быть, мне следует разделить его на два стека: один для кадров вызовов, а второй для оценки операций.

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

Answer 1

Статическая ссылка требует O(k) времени для доступа к промежуточной переменной, в то время как отображение требует O(k) времени для копирования его в каждом кадре, но всегда делает доступ к переменной за O(2) времени. на практике статические ссылки на самом деле немного быстрее и работают лучше с замыканиями, чем с дисплеем.