Đánh giá chiến lược

Question

Làm thế nào nên một lý do về đánh giá chức năng trong các ví dụ như sau trong Haskell:

let f x = ... 
    x = ... 
in map (g (f x)) xs 

Trong GHC, đôi khi (f x) được đánh giá chỉ một lần, và đôi khi một lần cho mỗi phần tử trong xs, tùy thuộc vào những gì chính xác f và g. Điều này có thể quan trọng khi f x là một tính toán đắt tiền. Nó vừa mới bắt đầu một người mới bắt đầu Haskell tôi đã giúp đỡ và tôi không biết phải nói gì với anh ta ngoài việc nó phụ thuộc vào trình biên dịch. Có một câu chuyện hay hơn không?

Cập nhật

Trong ví dụ sau (f x) sẽ được đánh giá 4 lần:

let f x = trace "!" $ zip x x 
    x = "abc" 
in map (\i -> lookup i (f x)) "abcd" 

Answer 1

Với phần mở rộng ngôn ngữ, chúng ta có thể tạo ra những tình huống mà f xphải được đánh giá lặp đi lặp lại:

{-# LANGUAGE GADTs, Rank2Types #-} 
module MultiEvG where 

data BI where 
    B :: (Bounded b, Integral b) => b -> BI 

foo :: [BI] -> [Integer] 
foo xs = let f :: (Integral c, Bounded c) => c -> c 
      f x = maxBound - x 
      g :: (forall a. (Integral a, Bounded a) => a) -> BI -> Integer 
      g m (B y) = toInteger (m + y) 
      x :: (Integral i) => i 
      x = 3 
     in map (g (f x)) xs 

Điểm mấu chốt là phải có f x đa hình thậm chí như là đối số của g, và chúng ta phải tạo ra một tình huống mà các loại (s) mà tại đó nó là cần thiết không thể được dự đoán (đâm đầu tiên của tôi được sử dụng một Either a b thay vì BI, nhưng khi tối ưu hóa, mà tất nhiên dẫn đến chỉ có hai đánh giá của f x nhiều nhất).

Biểu thức đa hình phải được đánh giá ít nhất một lần cho mỗi loại được sử dụng tại. Đó là một lý do cho sự hạn chế monomorphism. Tuy nhiên, khi phạm vi của các loại nó có thể cần thiết tại bị hạn chế, có thể làm mờ các giá trị ở từng loại, và trong một số trường hợp GHC làm điều đó (cần tối ưu hóa, và tôi mong đợi số lượng các loại liên quan không được quá lớn). Ở đây chúng ta phải đối mặt với những gì cơ bản là một danh sách không đồng nhất, vì vậy trong mỗi yêu cầu g (f x), nó có thể cần thiết theo kiểu tùy ý thỏa mãn các ràng buộc, do đó không thể dỡ bỏ tính toán bên ngoài map (về mặt kỹ thuật, trình biên dịch vẫn có thể xây dựng bộ đệm của các giá trị ở từng loại được sử dụng, do đó, nó sẽ được đánh giá chỉ một lần cho mỗi loại, nhưng GHC không, trong tất cả khả năng nó sẽ không có giá trị rắc rối).

• Biểu thức đơn lẻ chỉ cần đánh giá một lần, chúng có thể được chia sẻ. Cho dù chúng có được thực hiện hay không; bằng sự tinh khiết, nó không thay đổi ngữ nghĩa của chương trình. Nếu biểu thức được gắn kết với một tên, trong thực tế bạn có thể dựa vào nó được chia sẻ, vì nó dễ dàng và rõ ràng là những gì người lập trình muốn. Nếu nó không bị ràng buộc với một cái tên, đó là một câu hỏi tối ưu hóa. Với bộ tạo mã byte hoặc không có sự tối ưu hóa, biểu thức sẽ thường được đánh giá nhiều lần, nhưng với việc tối ưu hóa việc đánh giá lặp đi lặp lại sẽ chỉ ra một lỗi trình biên dịch.
• Biểu thức đa hình phải được đánh giá ít nhất một lần cho mỗi loại mà chúng được sử dụng, nhưng với tối ưu hóa, khi GHC có thể thấy nó có thể được sử dụng nhiều lần cùng loại, nó sẽ (thường) vẫn được chia sẻ cho nhập trong khi tính toán lớn hơn.

Dòng dưới cùng: Luôn biên dịch với tối ưu hóa, giúp trình biên dịch bằng cách ràng buộc các biểu thức bạn muốn chia sẻ với tên và cung cấp chữ ký kiểu đơn khi có thể.

Answer 2

Điều này thực sự phụ thuộc vào tối ưu hóa GHC, như bạn đã có thể để kể.

tốt nhất điều cần làm là nghiên cứu GHC core mà bạn nhận được sau khi tối ưu hóa chương trình. Tôi sẽ xem xét Core được tạo ra và kiểm tra xem f x có tuyên bố let riêng của mình bên ngoài map hay không.

Nếu bạn muốn trở thành chắc chắn, thì bạn nên yếu tố f x ra vào biến riêng của mình được phân công trong một let, nhưng có không thực sự là một cách đảm bảo để con nó ra ngoài đọc qua Core.

Tất cả những gì đã nói, ngoại trừ những thứ như trace sử dụng unsafePerformIO, điều này sẽ không bao giờ thay đổi ngữ nghĩa của chương trình của bạn: cách ứng dụng thực sự hoạt động.

Answer 3

Ví dụ của bạn thực sự khá khác nhau.

Trong ví dụ đầu tiên, đối số cho bản đồ là g (f x) và được chuyển một lần đến map có nhiều khả năng nhất là hàm được áp dụng một phần. Nên g (f x), khi được áp dụng cho đối số trong phạm vi map đánh giá đối số đầu tiên của nó, thì điều này sẽ chỉ được thực hiện một lần và sau đó đoạn thunk (f x) sẽ được cập nhật kết quả.

Do đó, trong ví dụ đầu tiên của bạn, f x sẽ được đánh giá tối đa 1 lần.

Ví dụ thứ hai của bạn yêu cầu phân tích sâu hơn trước khi trình biên dịch có thể đi đến kết luận rằng (f x) luôn luôn là hằng số trong biểu thức lambda. Có lẽ nó sẽ không bao giờ tối ưu hóa nó ở tất cả, bởi vì nó có thể có kiến ​​thức rằng dấu vết không phải là khá kosher. Vì vậy, điều này có thể đánh giá 4 lần khi truy tìm, và 4 lần hoặc 1 lần khi không truy tìm.

Answer 4

Trong GHC không tối ưu hóa, phần thân của hàm được đánh giá mỗi lần hàm được gọi. (A "cuộc gọi" có nghĩa là chức năng được áp dụng cho các đối số và kết quả được đánh giá.) Trong ví dụ sau, f x là bên trong một hàm, do đó, nó sẽ thực thi mỗi khi hàm được gọi. (GHC có thể tối ưu hóa biểu thức này như đã thảo luận trong FAQ [1].)

let f x = trace "!" $ zip x x 
    x = "abc" 
in map (\i -> lookup i (f x)) "abcd" 

Tuy nhiên, nếu chúng ta di chuyển f x ra khỏi chức năng, nó sẽ thực hiện một lần duy nhất.

let f x = trace "!" $ zip x x 
    x = "abc" 
in map ((\f_x i -> lookup i f_x) (f x)) "abcd" 

Điều này có thể được viết lại readably hơn như

let f x = trace "!" $ zip x x 
    x = "abc" 
    g f_x i = lookup i f_x 
in map (g (f x)) "abcd" 

Nguyên tắc chung là, mỗi lần một chức năng được áp dụng cho một cuộc tranh cãi, một "bản sao" mới của cơ quan chức năng được tạo ra. Ứng dụng chức năng là điều duy nhất có thể gây ra một biểu thức để thực hiện lại. Tuy nhiên, được cảnh báo rằng một số hàm và hàm gọi không giống như các hàm cú pháp.

[1] http://www.haskell.org/haskellwiki/GHC/FAQ#Subexpression_Elimination