Eager so với Lazy Haskell. Danh sách vô hạn có thể có trong các ngôn ngữ Eager?

Question

Dường như có thể thực hiện Haskell sao cho nó đánh giá háo hức mà không thay đổi ngữ nghĩa của ngôn ngữ. Nếu điều đó là đúng, thì cấu trúc dữ liệu vô hạn được xử lý như thế nào?

http://csg.csail.mit.edu/pubs/haskell.html

Do đó, rất nhiều thời gian cho việc tạo ra và phá hủy mảnh lơ lửng tính toán (thunks). Tất cả quá thường xuyên, các tính toán này đủ đơn giản để dễ dàng đánh giá chúng thay thế. Faxen và những người khác đã sử dụng phân tích tĩnh để phơi bày những cơ hội như vậy cho sự háo hức. Thay vào đó, chúng tôi đề xuất sử dụng sự háo hức ở khắp mọi nơi, trong khi sử dụng các cơ chế cho phép chúng tôi phục hồi nếu chương trình của chúng tôi quá háo hức.

Điều quan trọng là "chúng tôi có cơ chế khôi phục nếu chương trình của chúng tôi quá háo hức". Cơ chế này là gì? Làm thế nào để họ cho phép cho cấu trúc dữ liệu vô hạn và các khía cạnh khác của đánh giá lười biếng mà tôi đã được dẫn đến tin là không thể trong một ngôn ngữ háo hức?

Answer 1

Điều đó không hoàn toàn đúng: bạn có thể đánh giá các thuật ngữ Haskell háo hức nếu bạn có thể chứng minh rằng chúng sẽ không phân kỳ.

Ví dụ, khi bạn nhìn thấy f x, bạn có thể lần đầu tiên thực hiện lên đến 1.000 bước x (dừng nếu bạn đạt WHNF (đầu yếu hình thức bình thường) hoặc một lỗi), và sau đó vượt qua nó để f - ngữ nghĩa được bảo tồn, nhưng nếu bạn nghĩ rằng x sẽ được đánh giá, thì bạn có thể sắp xếp điều này xảy ra trước khi tối ưu hóa.

Nếu x = fix id, nó sẽ chỉ bỏ sau 1.000 bước không đi đâu cả. Nếu x = undefined, nó sẽ gây ra lỗi và bỏ (khôi phục đoạn gốc và chuyển nó đến f). Và cứ thế.

Nếu x = [1..], sau đó nó có thể sẽ giảm xuống thành 1 : 2 : 3 : ... : 999 : 1000 : [1001..], đạt đến giới hạn và dừng ở đó, chuyển kết quả đến f.

Về cơ bản: Bằng cách chứng minh rằng biểu thức không thể phân tách hoặc giới hạn đánh giá sao cho mọi thứ chấm dứt ngay cả khi có. Không thay đổi ngữ nghĩa, và có thể là một cải tiến lớn đối với hiệu suất.

Tất nhiên, nhược điểm là nếu x hóa ra là một số tính toán thực sự đắt tiền mà f chỉ sử dụng một nửa, bạn sẽ dành 1.000 bước giảm lãng phí thời gian. Và trong trường hợp của [1..], bạn có thể sử dụng rất nhiều bộ nhớ để lưu trữ danh sách; nếu f xử lý danh sách một phần tử tại một thời điểm, hãy vứt bỏ đầu mỗi lần, sau đó bạn sẽ lãng phí bộ nhớ. Đó là lý do tại sao nó phức tạp :)

Trang bạn đã liên kết ban đầu sẽ đi vào chi tiết hơn về các kỹ thuật cụ thể được sử dụng.