Làm cách nào để triển khai tiếp tục?

Question

Tôi đang làm việc trên một trình thông dịch Đề án được viết bằng C. Hiện tại nó sử dụng ngăn xếp thời gian chạy C làm ngăn xếp riêng của nó, trình bày một vấn đề nhỏ với việc triển khai tiếp tục. Giải pháp hiện tại của tôi là sao chép thủ công ngăn xếp C lên heap rồi sao chép nó trở lại khi cần. Ngoài việc không đạt tiêu chuẩn C, giải pháp này hầu như không lý tưởng.

Cách đơn giản nhất để triển khai tiếp tục cho Đề án trong C là gì?

Answer 1

Tôi nhớ đọc một bài báo mà bạn có thể giúp đỡ cho bạn: Cheney on the M.T.A. :-)

Một số triển khai của Đề án tôi biết, chẳng hạn như SISC, phân bổ khung cuộc gọi của họ trên heap.

@ollie: Bạn không cần phải làm cẩu nếu tất cả các khung cuộc gọi của bạn nằm trên vùng heap. Có một sự cân bằng trong hiệu suất, tất nhiên: thời gian để nâng, so với chi phí cần thiết để phân bổ tất cả các khung hình trên heap. Có lẽ nó phải là một tham số thời gian chạy có thể điều chỉnh được trong trình thông dịch. :-P

Answer 2

Sử dụng ngăn xếp rõ ràng thay thế.

Answer 3

Patrick là chính xác, cách duy nhất bạn có thể thực hiện việc này là sử dụng ngăn xếp rõ ràng trong trình thông dịch và đưa phân đoạn thích hợp vào ngăn xếp khi bạn cần chuyển sang tiếp tục.

Điều này về cơ bản giống như những gì cần thiết để hỗ trợ đóng cửa bằng các ngôn ngữ hỗ trợ chúng (đóng cửa và tiếp tục có liên quan phần nào).

Answer 4

Cách truyền thống là sử dụng setjmp và longjmp, mặc dù có sự cẩn trọng.

Dưới đây là một reasonably good explanation

Answer 5

Một bản tóm tắt tốt có sẵn trong Implementation Strategies for First-Class Continuations, một bài viết của Clinger, Hartheimer, và Ost. Tôi khuyên bạn nên xem xét triển khai thực hiện của Chez Scheme.

Sao chép ngăn xếp không phức tạp và có một số kỹ thuật được hiểu rõ có sẵn để cải thiện hiệu suất. Sử dụng khung phân bổ heap cũng khá đơn giản, nhưng bạn thực hiện một sự cân bằng tạo ra chi phí cho tình huống "bình thường" mà bạn không sử dụng các tiếp tục rõ ràng.

Nếu bạn chuyển đổi mã đầu vào thành kiểu chuyển tiếp liên tục (CPS) thì bạn có thể loại bỏ hoàn toàn ngăn xếp ngăn xếp. Tuy nhiên, trong khi CPS là thanh lịch, nó thêm một bước xử lý khác trong giao diện người dùng và yêu cầu tối ưu hóa bổ sung để khắc phục các tác động hiệu suất nhất định.

Answer 6

Ví dụ bạn có thể xem là: Chicken (thực hiện Đề án, được viết bằng C có hỗ trợ tính năng tiếp tục); Paul Graham của On Lisp - nơi ông tạo ra một biến áp CPS để thực hiện một tập hợp con của sự tiếp tục trong Common Lisp; và Weblocks - một khung công tác dựa trên web tiếp tục, cũng thực hiện một dạng tiếp tục giới hạn trong Common Lisp.

Answer 7

Nếu bạn đang bắt đầu từ đầu, bạn thực sự nên xem xét để chuyển đổi kiểu chuyển tiếp liên tục (CPS).

Các nguồn tốt bao gồm "LISP thành từng miếng nhỏ" và Marc Feeley's Scheme in 90 minutes presentation.

Answer 8

Tiếp tục không phải là vấn đề: bạn có thể triển khai các tính năng có chức năng đặt hàng thường xuyên cao hơn bằng CPS.Vấn đề với phân bổ stack ngây thơ là các cuộc gọi đuôi không bao giờ được tối ưu hóa, có nghĩa là bạn không thể được đề án.

Cách tiếp cận hiện tại tốt nhất để xếp chồng Spaghetti của bản đồ lên ngăn xếp là sử dụng trampolines: cơ bản là cơ sở hạ tầng bổ sung để xử lý các cuộc gọi và thoát khỏi các thủ tục. Xem Trampolined Style (ps).

Có some code minh họa cả hai ý tưởng này.

Answer 9

Tiếp tục về cơ bản bao gồm trạng thái đã lưu của ngăn xếp và thanh ghi CPU tại điểm chuyển ngữ cảnh. Ít nhất bạn không phải sao chép toàn bộ ngăn xếp vào heap khi chuyển đổi, bạn chỉ có thể chuyển hướng con trỏ ngăn xếp.

Tiếp tục được thực hiện một cách trivially bằng cách sử dụng sợi. http://en.wikipedia.org/wiki/Fiber_%28computer_science%29 . Những thứ duy nhất cần đóng gói cẩn thận là tham số truyền và trả về giá trị.

Trong các xơ Windows được thực hiện bằng cách sử dụng các cuộc gọi của CreateFiber/SwitchToFiber. trong các hệ thống tuân thủ Posix, nó có thể được thực hiện với makecontext/swapcontext.

boost :: coroutine có triển khai thực hiện coroutines cho C++ có thể đóng vai trò là điểm tham chiếu để triển khai.

Answer 10

Ngoài những câu trả lời hay mà bạn đã có cho đến nay, tôi khuyên bạn nên sử dụng số điện thoại Compiling with Continuations của Andrew Appel. Nó rất tốt bằng văn bản và trong khi không giao dịch trực tiếp với C, nó là một nguồn ý tưởng thực sự tốt đẹp cho các nhà văn biên dịch.

Wiki gà cũng có các trang mà bạn sẽ thấy rất thú vị, chẳng hạn như internal structure và compilation process (trong đó CPS được giải thích với một ví dụ thực tế về biên dịch).

Answer 11

Dường như luận án của Dybvig chưa được đề cập đến. Đó là một niềm vui để đọc. Mô hình dựa trên heap là dễ nhất để thực hiện, nhưng ngăn xếp dựa trên là hiệu quả hơn. Bỏ qua mô hình dựa trên chuỗi.

R. Kent Dybvig. "Ba mô hình triển khai cho Đề án". http://www.cs.indiana.edu/~dyb/papers/3imp.pdf

Ngoài ra, hãy xem các tài liệu triển khai trên ReadScheme.org. http://library.readscheme.org/page8.html

Bản tóm tắt như sau:

luận án này trình bày ba mô hình thực hiện cho Đề án theo chương trình ming Ngôn ngữ. Rst là một mô hình dựa trên heap được sử dụng trong một số mẫu trong hầu hết các triển khai Đề án cho đến nay; thứ hai là một mô hình dựa trên ngăn xếp mới có ý nghĩa hơn so với mô hình dựa trên heap khi thực hiện hầu hết các chương trình; và thứ ba là một mô hình mới dựa trên chuỗi nhằm mục đích sử dụng trong việc triển khai thực hiện nhiều bộ xử lý.

Mô hình dựa trên heap phân bổ một số cấu trúc dữ liệu quan trọng trong một đống , bao gồm danh sách tham số thực, môi trường ràng buộc và gọi khung.

Mô hình dựa trên ngăn xếp phân bổ các cấu trúc giống nhau này trên một ngăn xếp bất cứ khi nào có thể.Điều này dẫn đến phân bổ ít heap hơn, ít tài liệu tham khảo hơn , chuỗi hướng dẫn ngắn hơn, thu gom rác ít hơn, và sử dụng nhiều bộ nhớ hơn.

Mô hình dựa trên chuỗi phân bổ phiên bản của các cấu trúc này ngay trong văn bản chương trình, được biểu diễn dưới dạng chuỗi ký hiệu. Trong mô hình dựa trên chuỗi, các chương trình Đề án được dịch sang ngôn ngữ FFP được thiết kế đặc biệt để hỗ trợ Đề án. Các chương trình trong ngôn ngữ này được thực thi trực tiếp bởi máy FFP, một máy tính giảm chuỗi nhiều bộ xử lý .

Mô hình dựa trên ngăn xếp là nguyên lý thực tiễn ngay lập tức; nó là mô hình được hệ thống Chez Scheme của tác giả sử dụng, thực hiện Đề án hiệu suất cao. Mô hình dựa trên chuỗi sẽ hữu ích cho cung cấp Đề án như là một thay thế cấp cao cho FFP trên máy FFP khi máy được thực hiện.

Answer 12

Như soegaard chỉ ra, các tài liệu tham khảo chính vẫn this one

Ý tưởng là, một sự tiếp nối là một đóng cửa mà giữ chồng kiểm soát đánh giá của nó. Ngăn xếp điều khiển là bắt buộc để tiếp tục đánh giá từ thời điểm tiếp tục được tạo bằng cách sử dụng call/cc.

Thường gọi việc tiếp tục thực hiện thời gian thực hiện lâu dài và lấp đầy bộ nhớ với ngăn xếp trùng lặp. Tôi đã viết mã ngu ngốc này để chứng minh rằng, trong chương trình giảm thiểu nó làm cho sơ đồ bị hỏng,

Mã tổng 1000 số đầu tiên 1+2+3+...+1000.

(call-with-current-continuation 
(lambda (break) 
    ((lambda (s) (s s 1000 break)) 
    (lambda (s n cc) 
     (if (= 0 n) 
      (cc 0) 
      (+ n 
      ;; non-tail-recursive, 
      ;; the stack grows at each recursive call 
      (call-with-current-continuation 
       (lambda (__) 
       (s s (- n 1) __))))))))) 

Nếu bạn chuyển từ 1000 đến 100 000 mã sẽ mất 2 giây và nếu bạn tăng số đầu vào, mã sẽ bị lỗi.