Làm thế nào để thực hiện hiệu quả các bao đóng trong LLVM IR?

Question

Tôi bắt đầu thêm các bao đóng (lambdas) vào ngôn ngữ của tôi sử dụng LLVM làm phụ trợ. Tôi đã triển khai chúng cho các trường hợp đơn giản, nơi chúng có thể luôn được gạch chân, tức là mã cho định nghĩa đóng cửa chính nó không cần phải được tạo ra, vì nó được gạch chân ở nơi được sử dụng.

Nhưng cách tạo mã để đóng trong trường hợp đóng không phải lúc nào cũng được gạch chân (ví dụ, nó được chuyển đến một hàm khác không được gạch chân). Tốt hơn là, các trang web cuộc gọi không nên quan tâm liệu chúng có được truyền các chức năng hay đóng cửa thông thường hay không và sẽ gọi chúng là các hàm bình thường.

Tôi có thể tạo hàm có tên tổng hợp, nhưng sẽ phải lấy môi trường tham chiếu làm đối số bổ sung và hàm đó không thể được chuyển cho hàm khác không biết về đối số thừa cần thiết.

Tôi đã nghĩ về một giải pháp có thể sử dụng nội tại trampoline của LLVM, "excise" một tham số duy nhất từ ​​một hàm, trả về một con trỏ tới hàm trampoline có một tham số ít hơn. Trong trường hợp này, nếu hàm được tạo ra cho việc đóng cửa lấy môi trường tham chiếu làm tham số đầu tiên, tôi có thể loại bỏ nó và lấy lại một hàm lấy chính xác nhiều tham số như việc đóng thực sự khai báo. Âm thanh này có thể thực hiện được không? Hiệu quả? Có giải pháp nào tốt hơn không?

Mã dụ:

def applyFunctionTo(value: Int, f: (Int) -> Int) = f(value) 

def main() = { 
    val m := 4; 
    val n := 5; 
    val lambda := { (x: Int) => x + m + n }; 
    applyFunctionTo(3, lambda) 
} 

Bây giờ, cho phép tưởng tượng rằng điều này sẽ không nhận được inlined để def main() = 3 + 4 + 5, và rằng applyFunctionTo sẽ có thể được biên dịch riêng biệt, và chúng ta không thể thay đổi địa điểm cuộc gọi đó. Với trampolining, tôi tưởng tượng mã được tạo ra sẽ giống như thế này (được biểu thị bằng mã giả, * có nghĩa là con trỏ):

def main$lambda$1(env: {m: Int, n: Int}*, x: Int) = x + env.m + env.n 
def main() = { 
    m = 4 
    n = 5 
    env* = allocate-space-for {Int, Int} 
    env = {m, n} 
    tramp* = create-trampoline-for(main$lambda$1*, env*) 
    return applyFunctionTo(3, tramp*) 
    // release memory for env and trampoline if the lambda didn't escape 
} 

Điều này có đúng không?

Answer 1

Âm thanh có thể thực hiện và hiệu quả.

Cách khác, không cần trampolines, là định nghĩa kiểu đóng như một cặp con trỏ hàm và con trỏ trỏ tới môi trường tức là con trỏ ngăn xếp. Trong quy ước gọi C, các đối số thừa sẽ bị bỏ qua vì vậy nếu bạn cung cấp môi trường làm đối số cuối cùng, bạn thậm chí có thể sử dụng (function_ptr, null) làm gọi lại cho hàm thông thường.

Answer 2

Một ý tưởng ngớ ngẩn là đối với mỗi đóng, bạn tạo ra một cấu trúc cục bộ luồng để giữ dữ liệu cần thiết (có thể chỉ là một con trỏ đến một cấu trúc cục bộ hoặc một vài con trỏ).

Tác giả của việc đóng cửa có trách nhiệm thiết lập các biến TLS và "lưu" trạng thái của chúng (để cho phép gọi đệ quy).

Người dùng sau đó gọi hàm này bình thường, nó được thực hiện và sử dụng môi trường.

Sau cuộc gọi, người tạo bản đóng "khôi phục" các giá trị ban đầu vào các biến TLS.