Sử dụng tham chiếu-minh bạch để sẵn tính toán giá trị trong Haskell

Question

Hãy nói rằng chúng tôi có một chương trình như thế này:

list = [1..10000000] 

main = print $ sum list 

Tôi muốn điều này được biên soạn như vậy mà thực thi chỉ in 50000005000000, mà không cần dùng nhiều thời gian và cố gắng. Về cơ bản, bất kỳ biểu thức nào chắc chắn sẽ được tính toán (có thể phân tích nghiêm ngặt có thể giúp ở đây) có thể là được tính trước trong thời gian biên dịch (tức là chúng tôi sử dụng tính minh bạch tham chiếu để nói rằng nó không thực sự quan trọng khi chúng tôi tính toán giá trị).

Nói tóm lại: "phải được tính toán" + tham chiếu-minh bạch = có thể được tính toán trước

này sẽ như thế nào chạy chương trình cho đến khi chúng ta đạt cái gì đó phụ thuộc vào đầu vào (tức là cốt lõi của chương trình, vốn phổ biến trên tất cả các yếu tố đầu vào, sẽ được tính trước)

Có cơ chế hiện tại để đạt được điều này hiện tại (bằng Haskell hoặc bất kỳ ngôn ngữ nào khác) không? [Vui lòng không trỏ tới nội dung nào đó như mẫu trong C++ vì nó không có tính minh bạch tham chiếu ngay từ đầu.]

Nếu không, vấn đề này khó khăn như thế nào? [Các vấn đề kỹ thuật (và lý thuyết) kèm theo là gì?]

Answer 1

Câu trả lời có mục đích chung để tính toán thời gian biên dịch là sử dụng Mẫu Haskell. Nhưng đối với trường hợp sử dụng cụ thể này, bạn có thể sử dụng gói vector và chương trình phụ trợ LLVM và GHC sẽ tối ưu hóa số tiền này.

sorghum:~% cat >test.hs 
import Data.Vector.Unboxed as V 
main = print (V.sum $ V.enumFromN (1 :: Int) 10000000) 
sorghum:~% ghc --make -O2 -fllvm test.hs 
[1 of 1] Compiling Main    (test.hs, test.o) 
Linking test ... 
sorghum:~% time ./test 
50000005000000 
./test 0.00s user 0.00s system 0% cpu 0.002 total 
sorghum:~% objdump -d test | grep 2d7988896b40 
    40653d: 48 bb 40 6b 89 88 79 movabs $0x2d7988896b40,%rbx 
    406547: 49 be 40 6b 89 88 79 movabs $0x2d7988896b40,%r14 

(Trong trường hợp nó không phải là ngay lập tức rõ ràng, 0x2d79888896b40 là 50000005000000.)

Answer 2

Đây không phải là an toàn trong trường hợp tổng quát. Lý do là biểu thức Haskell có thể là thuần túy, nhưng chúng cũng có thể không chấm dứt. Trình biên dịch nên luôn luôn chấm dứt, do đó, tốt nhất bạn có thể làm sẽ là "đánh giá 1.000 bước của kết quả này". Nhưng nếu bạn thêm một giới hạn như vậy, nếu bạn đang biên soạn một chương trình để chạy trên một cụm siêu máy tính với terabyte RAM, và trình biên dịch hết bộ nhớ?

Bạn có thể thêm rất nhiều giới hạn, nhưng cuối cùng bạn sẽ giảm tối ưu hóa thành dạng gấp liên tục chậm (đặc biệt là đối với phần lớn các chương trình có tính toán phụ thuộc vào đầu vào người dùng thời gian chạy). Và kể từ khi sum [1..10000000] mất nửa giây ở đây, nó không chắc nó sẽ rơi theo bất kỳ giới hạn hợp lý nào.

Tất nhiên, các trường hợp cụ thể như trường hợp này thường có thể được tối ưu hóa và GHC thường tối ưu hóa các biểu thức phức tạp như thế này. Nhưng trình biên dịch không thể chỉ đánh giá bất kỳ biểu thức nào tại thời gian biên dịch một cách an toàn; nó sẽ phải rất hạn chế, và có thể lập luận rằng nó sẽ hữu ích như thế nào dưới những ràng buộc đó. Đó là một trình biên dịch, không phải là một thông dịch viên :)

nào ồ ạt sẽ làm chậm việc biên soạn của bất kỳ chương trình mà không chứa rất nhiều vòng lặp vô hạn - mà, vì Haskell là không chặt chẽ, có nhiều khả năng hơn bạn có thể nghĩ). Hoặc, phổ biến hơn, bất kỳ chương trình nào chứa nhiều tính toán dài hạn.

Answer 3

Nghe giống như một công việc cho Supercompilation! Câu hỏi này nghe có vẻ giống như mô tả về nó và thảo luận về các gương không phân tích các vấn đề mà các nhà phát triển siêu máy tính phải đối mặt. Tôi đã thấy trên wiki của GHC rằng ai đó đang làm việc trên một siêu máy tính sản xuất cho nó nhưng không có gì trở thành điều đó.