Реализация lambdas на языке сценариев

Question

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

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

main() 
{ 
    a = comp(10); 

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

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

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

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

Answer 1

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

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

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

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

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

С учетом этой информации, локальные переменные теперь разделены на две группы: чистых локальных переменных, и захватили локальные переменные. Я буду называть этих «чистых местных жителей» и «захваченных местных жителей».

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

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

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

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

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

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

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

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

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

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

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

Answer 2

Я не знаю о наиболее разумный путь, но вы можете прочитать о том, как Lua реализует затворы в The implementation of Lua 5.0. См. Также slides.

Главное в реализации замыканий Lua - эффективная обработка upvalues ​​ или внешних локальных переменных. Это позволило Lua поддерживать полный лексический охват. За информацией о том, как эта поддержка развивалась в дизайне Lua, см. Документ HOPL III, The Evolution of Lua.

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); 
} 

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

(Чтобы было ясно, дело в том, что 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 
}