Biên dịch các ngôn ngữ chức năng thành C

Question

Giả sử bạn đang biên dịch một ngôn ngữ chức năng sang C di động, và giả sử cũng vì nhiều lý do bạn muốn thu thập rác chính xác hơn là bảo quản rác. Không có cách di động (có lẽ không có cách nào cả trong trường hợp chung) cho bộ thu gom rác để tìm ra cái gì và không phải là một con trỏ trên ngăn xếp C. Dường như với tôi có hai giải pháp cho vấn đề này:

1. Ngăn xếp bóng. Làm cho mỗi chức năng C duy trì thông tin sổ kế toán về những gì là và không phải là một con trỏ. Đây là phương pháp được đề xuất bởi ví dụ: LLVM.

2. Tận dụng lợi thế của việc bạn đang biên dịch ngôn ngữ chức năng, có nghĩa là mã mainline không có tác dụng phụ. Khi bộ cấp phát phát hiện ra khỏi bộ nhớ, thay vì gọi bộ thu gom rác, nó hủy bỏ hoạt động hiện tại với một longjmp quay trở lại vòng lặp chính, gọi trình thu gom rác (trong một ngữ cảnh nơi tập hợp các biến có thể chứa con trỏ trước) sau đó khởi động lại hoạt động.

Dường như với tôi rằng, nếu bạn đang đối phó với một ngôn ngữ chức năng thuần túy nơi tiếp cận thứ hai được áp dụng, nó phải có hiệu quả hơn so với phương pháp đầu tiên, cũng như dễ dàng hơn để trộn với viết tay C.

Có vấn đề gì tôi đang xem không? Bất kỳ tham chiếu đến thảo luận hiện có hoặc thực hiện các kỹ thuật này?

Answer 1

Tôi nghĩ điều rõ ràng nhất mà bạn chưa mô tả là cách xử lý hết bộ nhớ ngoài. Như bạn đã mô tả nó, giả sử tôi có một hoạt động sử dụng nhiều bộ nhớ hơn là có sẵn. Cuối cùng tôi đạt được:

1. Bắt đầu bất kỳ giai đoạn nào của hoạt động sẽ đưa chúng tôi vượt quá giới hạn.
2. Chạy một lúc.
3. Hết bộ nhớ.
4. Miễn phí tất cả bộ nhớ được phân bổ theo giai đoạn này (không có gì khác để giải phóng).
5. Đi tới 1.

Tức là, vòng lặp vô hạn.Vì vậy, ít nhất bạn muốn một số loại bộ sưu tập rác thế hệ sẽ cho phép bạn phát hiện vòng lặp và thoát.

Answer 2

Có thể thiết kế một ngôn ngữ FP tinh khiết sử dụng một cấu trúc dữ liệu duy nhất:

typedef enum record_type { RT_SYMBOL, RT_NUMBER, RT_PAIR }; 

struct record 
{ 
    record_type type; 
    void *value; 
}; 

Programs and dữ liệu có thể được biểu diễn bằng pairs của records:

struct pair 
{ 
    record *car; 
    record *cdr; 
}; 

Sau đây là cách một biểu thức đơn giản - 2 * 3 - có thể được thể hiện bằng cách sử dụng records:

record r1; 
r1.type = RT_NUMBER; 
r1.value = &two; 

record r2; 
r1.type = RT_NUMBER; 
r1.value = &three; 

record opr1; 
opr1.type = RT_NUMBER; 
opr1.value = &OP_MULT; /* A machine op-code for multiplication. */ 

pair p_oprnds; 
p_oprnds.car = &r1; 
p_oprnds.cdr = &r2; 

pair p; 
p.car = opr1; 
p.cdr = p_oprnds; 

Điều này giống với biểu thức Lisp: (* 2 3). Bây giờ bạn có thể xác định một máy hoạt động trên pairs, xử lý car làm toán tử và cdr làm toán hạng. Khi chúng ta chỉ xử lý một cấu trúc dữ liệu, GC chính xác là có thể. Xem Lispkit Lisp cho kiến ​​trúc của một máy ảo như vậy.

Đồng thời đọc Lisp in Small Pieces trước khi bắt đầu với một nỗ lực nghiêm túc để viết trình biên dịch FP -> C.