Реализация лямбд на языке сценариев

Question

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

comp(threshold)
{
    return lambda(x)
    {
        return x < threshold;
    };
}

main()
{
    a = comp(10);

    lib::print( a(5) );
}

Анонимные функции не должны быть слишком сложными для добавления в мой язык сценариев.Это просто случай добавления кода функции обычным способом, за исключением того, что единственный способ получить доступ к этой функции - через переменную, которой она назначена.

Проблема с примером закрытия вышезаключается в том, что тело функции для анонимной функции ссылается (в общем смысле) на область памяти, которая недопустима (или будет) во время вызова замыкания.

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

Answer 1

Я не знаю о наиболее разумном способе, но вы можете прочитать о том, как Lua реализует замыкания в Реализация Lua 5.0 . Смотрите также слайды .

Основным моментом в реализации Lua замыканий является эффективная обработка значений или внешних локальных переменных. Это позволило Lua поддерживать полный лексический обзор. Для описания того, как эта поддержка развивалась в дизайне Lua, см. Документ HOPL III, Эволюция Lua .

Answer 2

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

Во-первых, нам нужно определить проблемное пространство.

Ваш язык сценариев имеет локальные переменные (используятермин Lua): переменные, которые не являются глобальными.Это переменные, которые теоретически могут быть захвачены лямбдой.

Теперь давайте предположим, что ваш язык сценариев не имеет возможности динамически выбирать локальные переменные.Это означает, что, просто просматривая синтаксическое дерево, можно увидеть следующее:

1. Какие локальные переменные фиксируются функцией.
2. Какие локальные переменные не захвачено функцией.
3. Какие функции захватывают локальные переменные вне их области видимости.
4. Какие функции не захватывают локальные переменные вне своей области видимости.

Учитывая эту информацию, локальные переменные теперь разделены на две группы: pure локальные переменные и захваченные локальные переменные.Я буду называть их "чистыми местными жителями" и "захваченными местными жителями".

Чистые местные жители, из-за отсутствия лучшего термина, регистрируются.Когда вы компилируете в свой байт-код, чистые локальные данные проще всего обрабатывать.Это конкретные индексы стека или конкретные имена регистров.Как бы вы ни занимались управлением стека, чистым местным жителям назначаются фиксированные местоположения в определенной области.Если вы обладаете силой JIT, то они станут регистрами или наиболее близкими к этому.

Самое первое, что вам нужно понять о захваченных местных жителях, это: онидолжен управляться менеджером памяти. Они существуют независимо от текущего стека вызовов и области видимости, и, следовательно, они должны быть автономными объектами, на которые ссылаются функции, которые их захватывают.Это позволяет нескольким функциям захватывать одни и те же локальные данные и, следовательно, ссылаться на личные данные друг друга.

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

comp(threshold)
{
    local data;
    return lambda(x)
    {
        return x < (threshold + data);
    };
}

В корневой области функции comp есть две локальные переменные.Оба они захвачены в плен.Следовательно, число захваченных локальных элементов равно 2, а число чистых локальных элементов равно нулю.

Поэтому ваш компилятор (для байтового кода) выделит 0 регистров / переменных стека для чистых локальных элементов и выделит свободнуюпостоянный объект, который содержит две переменные.Предполагая, что вы используете сборщик мусора, вам нужно что-то, чтобы ссылаться на него, чтобы оно продолжало жить.Это легко: вы ссылаетесь на него в регистре / стеке, который не доступен напрямую скрипту.Так что на самом деле вы выделяете переменную register / stack, но скрипт не может напрямую к ней прикоснуться.

Теперь давайте посмотрим, что делает lambda.Это создает функцию.Опять же, мы знаем, что эта функция захватывает некоторые переменные за пределами своей области видимости.И мы знаем , какие переменные он захватывает.Мы видим, что он захватывает две переменные, но мы также видим, что эти две переменные происходят из одного и того же автономного блока памяти.

Итак, что lambda делает, это создает функциональный объект, который имеет ссылку на некоторыеБайт-код и ссылка на переменные, с которыми он связан.Байт-код будет использовать эту ссылку для получения захваченных переменных.Ваш компилятор знает, какие переменные являются чисто локальными для функции (например, аргумент x), а какие являются внешне захваченными (например, порогом).Таким образом, он может выяснить, как получить доступ к каждой переменной.

Теперь, когда lambda завершается, он возвращает функциональный объект.На этом этапе на захваченные переменные ссылаются две вещи: лямбда-функция и стек : текущая область действия функции.Однако, когда return заканчивается, текущая область действия уничтожается, и на все ранее упоминавшиеся объекты больше нет ссылок.Поэтому, когда он возвращает объект функции, только лямбда-функция имеет ссылку на захваченные переменные.

Это все довольно сложно, хотя.Гораздо более простая реализация состояла бы в том, чтобы просто эффективно захватывать все локальные переменные; все локальные переменные являются захваченными локальными переменными.Если вы сделаете это, то ваш компилятор может быть намного проще (и, вероятно, быстрее).Когда вводится новая область, все локальные элементы для этой области выделяются в блоке памяти.Когда функция создается, она ссылается на все используемые ею внешние области (если есть).И когда выход из области видимости, он удаляет ссылку на локальные ресурсы, которые он выделил.Если никто не ссылается на него, память может быть освобождена.

Это очень просто и понятно.

Answer 3

Если бы я перевел это на C ++ (без лямбды), это выглядело бы так:

struct comp_lamda_1 {
    int threshold;
    comp_lamda_1(int t) :threshold(t) {}
    bool operator()(int x) {
        return x < threshold;
    };
};

comp_lambda_1 comp(int threshold)
{
    return comp_lamda_1(threshold);
}

int main()
{
    auto a = comp(10);
    std::cout << a(5);
}

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

(Для ясности, смысл в том, что comp_lamda_1 - это объект-функция, и я понимаю, что вы не былине спрашиваю о переводе C ++ приведенного выше кода)

Answer 4

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

function()
{
    a = 6, b;

    {
        local c = 5;

        b = lambda() { return a*c; };

        // close c in closure;
    }

    b();

    // close a in closure
}