Định nghĩa chức năng Haskell và mảng bộ nhớ đệm

Question

Tôi có câu hỏi về việc triển khai bộ nhớ đệm (ghi nhớ) sử dụng mảng trong Haskell. Các mô hình sau đây hoạt động:

f = (fA !) 
    where fA = listArray... 

Nhưng điều này không (tốc độ của chương trình gợi ý rằng mảng là nhận được tái tạo mỗi cuộc gọi hoặc một cái gì đó):

f n = (fA ! n) 
    where fA = listArray... 

Xác định fA bên ngoài của một mệnh đề where (trong "phạm vi toàn cầu") cũng hoạt động với cả hai mẫu.

Tôi đã hy vọng rằng ai đó có thể chỉ cho tôi hướng tới giải thích kỹ thuật về sự khác biệt giữa hai mẫu trên.

Lưu ý rằng tôi đang sử dụng GHC mới nhất và tôi không chắc liệu đây có phải là tính riêng biệt của trình biên dịch hay một phần của chính ngôn ngữ đó hay không.

EDIT:! được sử dụng để truy cập mảng, vì vậy fA! 5 có nghĩa là fA [5] trong cú pháp C++. Sự hiểu biết của tôi về Haskell là (fA!) N sẽ giống như (fA! N) ... cũng có lẽ thông thường tôi đã viết "f n = fA! N" (không có dấu ngoặc đơn). Dù sao, tôi nhận được cùng một hành vi không có vấn đề làm thế nào tôi ngoặc.

Answer 1

Cách tốt nhất để tìm những gì đang diễn ra là yêu cầu trình biên dịch xuất bản trình bày trung gian của nó bằng -v4. Đầu ra là đồ sộ và một chút khó đọc, nhưng nên cho phép bạn tìm ra chính xác sự khác biệt trong mã được sinh ra là gì và cách trình biên dịch đến đó.

Có thể bạn sẽ nhận thấy rằng fA đang được di chuyển bên ngoài chức năng (tới "phạm vi toàn cầu") trong ví dụ đầu tiên của bạn. Trên ví dụ thứ hai của bạn, nó có thể không phải là (có nghĩa là nó sẽ được tái tạo trên mỗi cuộc gọi).

Một lý do có thể cho nó không được di chuyển bên ngoài chức năng là vì trình biên dịch nghĩ rằng nó phụ thuộc vào giá trị của n. Trong ví dụ hoạt động của bạn, không có n cho fA phụ thuộc vào.

Nhưng lý do tôi nghĩ trình biên dịch tránh di chuyển fA bên ngoài trên ví dụ thứ hai của bạn là vì nó đang cố gắng tránh rò rỉ không gian. Hãy xem xét điều gì sẽ xảy ra nếu fA, thay vì mảng của bạn, là danh sách vô hạn (mà bạn đã sử dụng toán tử !!). Hãy tưởng tượng bạn gọi nó một lần với một số lượng lớn (ví dụ f 10000), và sau đó chỉ gọi nó với số lượng nhỏ (f 2, f 3, f 12 ...). 10000 yếu tố từ cuộc gọi trước đó vẫn còn trên bộ nhớ, lãng phí không gian. Vì vậy, để tránh điều này, trình biên dịch tạo lại fA mỗi lần bạn gọi hàm của mình.

Việc tránh rò rỉ không gian có thể không xảy ra trong ví dụ đầu tiên của bạn vì trong trường hợp đó, f thực tế chỉ được gọi một lần, trả lại kết thúc (hiện tại chúng tôi đang ở biên giới của chức năng thuần túy và thế giới bắt buộc) một chút tinh tế hơn). Việc đóng này thay thế hàm ban đầu, sẽ không bao giờ được gọi lại, vì vậy fA chỉ được gọi một lần (và do đó trình tối ưu hóa cảm thấy tự do di chuyển nó bên ngoài hàm). Trong ví dụ thứ hai của bạn, f không được thay thế bằng một đóng (vì giá trị của nó phụ thuộc vào đối số) và do đó sẽ được gọi lại.

Nếu bạn muốn tìm hiểu thêm về điều này (sẽ giúp đọc đầu ra -v4), bạn có thể xem qua giấy Spineless Tagless G-Machine (citeseer link).

Đối với câu hỏi cuối cùng của bạn, tôi nghĩ rằng đó là tính đặc thù của trình biên dịch (nhưng tôi có thể sai). Tuy nhiên, nó sẽ không làm tôi ngạc nhiên nếu tất cả các trình biên dịch đã làm điều tương tự, ngay cả khi nó không phải là một phần của ngôn ngữ.

Answer 2

Sự khác biệt về hành vi không được chỉ định theo tiêu chuẩn Haskell. Tất cả những gì cần nói là các hàm đều giống nhau (sẽ dẫn đến cùng một đầu ra cho cùng một đầu vào).

Tuy nhiên trong trường hợp này, có một cách đơn giản để dự đoán hiệu suất thời gian và bộ nhớ mà hầu hết các trình biên dịch tuân theo. Một lần nữa tôi nhấn mạnh rằng điều này là không cần thiết, chỉ có hầu hết các trình biên dịch làm điều đó.

đầu tiên viết lại hai ví dụ của bạn như biểu thức lambda tinh khiết, mở rộng phần:

f = let fA = listArray ... in \n -> fA ! n 
f' = \n -> let fA = listArray ... in fA ! n 

Trình biên dịch sử dụng để ràng buộc để chỉ chia sẻ. Việc bảo đảm là trong một môi trường nhất định (tập hợp các biến cục bộ, thân lambda, một cái gì đó tương tự), bên phải của một lệnh ràng buộc không có tham số nào sẽ được đánh giá nhiều nhất một lần. Môi trường của FA ở trước đây là toàn bộ chương trình vì nó không thuộc bất kỳ lambda nào, nhưng môi trường của cái sau là nhỏ hơn vì nó nằm dưới một lambda.

Điều này có nghĩa là sau này, fA có thể được đánh giá một lần cho mỗi n khác nhau, trong khi trước đây bị cấm.

Chúng ta có thể thấy mô hình này có hiệu lực ngay cả với chức năng đa đối số:

g x y = (a ! y) where a = [ x^y' | y' <- [0..] ] 
g' x = (\y -> a ! y) where a = [ x^y' | y' <- [0..] ] 

Sau đó, trong:

let k = g 2 in k 100 + k 100 

Chúng ta có thể tính toán hơn 2^100 hơn một lần, nhưng trong:

let k = g' 2 in k 100 + k 100 

Chúng tôi sẽ chỉ tính toán nó một lần.

Nếu bạn đang làm việc với ghi nhớ, tôi khuyên bạn nên dữ liệu-memocombinators trên Hackage, mà là một thư viện bảng ghi nhớ có hình dạng khác nhau, vì vậy bạn không cần phải cuộn của riêng bạn.

Answer 3

Thật tuyệt, cảm ơn câu trả lời của bạn đã giúp ích rất nhiều và tôi chắc chắn sẽ kiểm tra các bộ ghi nhớ dữ liệu trên Hackage. Đến từ một nền tảng C++ - nặng, tôi đã đấu tranh với sự hiểu biết chính xác những gì Haskell sẽ làm (chủ yếu là về mặt phức tạp) với một chương trình cụ thể, những hướng dẫn nào dường như không có được.