GHC có thể không bao giờ bản đồ nội tuyến, scanl, foldr, v.v. không?

Question

Tôi đã nhận thấy rằng GHC manual nói "đối với chức năng tự đệ quy, trình ngắt vòng lặp chỉ có thể là chính chức năng, vì vậy một pragma INLINE luôn bị bỏ qua".

Không này nói mọi ứng dụng của cấu trúc chức năng đệ quy thông thường như map, zip, scan*, fold*, sum, vv có thể không được inlined?

Bạn luôn có thể viết lại tất cả các chức năng này khi bạn sử dụng chúng, thêm thẻ nghiêm ngặt thích hợp hoặc có thể sử dụng các kỹ thuật ưa thích như "hợp nhất luồng" được đề xuất here.

Tuy nhiên, không phải tất cả điều này có hạn chế đáng kể khả năng viết mã của chúng tôi đồng thời nhanh và thanh lịch không?

Answer 1

Thật vậy, GHC không thể thực hiện các hàm đệ quy nội tuyến hiện tại. Tuy nhiên:

• GHC sẽ vẫn chuyên chức năng đệ quy. Ví dụ, cho

  fac :: (Eq a, Num a) => a -> a 
  fac 0 = 1 
  fac n = n * fac (n-1) 
  
  f :: Int -> Int 
  f x = 1 + fac x 
  

  GHC sẽ nhận ra rằng fac được sử dụng ở loại Int -> Int và tạo ra một phiên bản đặc biệt của fac cho loại đó, trong đó sử dụng số nguyên số học nhanh.

  Chuyên môn này diễn ra tự động trong mô-đun (ví dụ: nếu fac và f được định nghĩa trong cùng một mô-đun). Đối với cross-mô-đun chuyên môn (ví dụ nếu f và fac được định nghĩa trong module khác nhau), đánh dấu chức năng to-be-chuyên với an INLINABLE pragma:

  {-# INLINABLE faC#-} 
  fac :: (Eq a, Num a) => a -> a 
  ... 
  

• Có biến đổi thủ công mà làm cho chức năng không đệ quy. Kỹ thuật công suất thấp nhất là static argument transformation, áp dụng cho các hàm đệ quy với các đối số không thay đổi trên các cuộc gọi đệ quy (ví dụ: nhiều hàm bậc cao hơn như map, filter, fold*). Sự biến đổi này biến

  map f []  = [] 
  map f (x:xs) = f x : map f xs 
  

  vào

  map f xs0 = go xs0 
      where 
      go []  = [] 
      go (x:xs) = f x : go xs 
  

  để cho một cuộc gọi như

  g :: [Int] -> [Int] 
  g xs = map (2*) xs 
  

  sẽ có map inlined và trở thành

  g [] = [] 
  g (x:xs) = 2*x : g xs 
  

  transformati này trên đã được áp dụng cho các chức năng Prelude chẳng hạn như foldr và foldl.

• Kỹ thuật kết hợp cũng làm cho nhiều chức năng không phản hồi và mạnh hơn so với phép chuyển đổi đối số tĩnh. Cách tiếp cận chính cho danh sách, được xây dựng trong Prelude, là shortcut fusion. Cách tiếp cận cơ bản là viết càng nhiều hàm càng tốt như các hàm không đệ quy sử dụng foldr và/hoặc build; sau đó tất cả đệ quy được ghi lại trong foldr và có các QUY ĐỊNH đặc biệt để xử lý foldr.

  Lợi dụng sự hợp nhất này về nguyên tắc dễ dàng: tránh đệ quy thủ công, thích các chức năng thư viện như foldr, map, filter và bất kỳ chức năng nào trong this list.Đặc biệt, việc viết mã theo kiểu này tạo ra mã "đồng thời nhanh và thanh lịch".

• Thư viện hiện đại như text và vector sử dụng stream fusion phía sau hậu trường. Don Stewart đã viết một cặp bài đăng trên blog (1, 2) chứng minh điều này đang hoạt động trong thư viện lỗi thời uvector, nhưng các nguyên tắc tương tự áp dụng cho văn bản và vectơ.

  Như với tính năng tổng hợp phím tắt, tận dụng sự hợp nhất luồng trong văn bản và vectơ về nguyên tắc dễ dàng: tránh đệ quy thủ công, thích các chức năng thư viện đã được đánh dấu là "tùy thuộc vào phản ứng tổng hợp".

• Hiện đang tiến hành cải thiện GHC để hỗ trợ nội tuyến các hàm đệ quy. Điều này nằm dưới tiêu đề chung của supercompilation và công việc gần đây về điều này dường như đã được dẫn dắt bởi Max Bolingbroke và Neil Mitchell.

Answer 2

cho chức năng tự đệ quy, trình ngắt vòng lặp chỉ có thể là chính chức năng, do đó, một pragma INLINE luôn bị bỏ qua.

Nếu có điều gì đó đệ quy, để nội tuyến, bạn sẽ phải biết số lần nó được thực hiện tại thời gian biên dịch. Xem xét nó sẽ là một đầu vào chiều dài biến, đó là không thể.

Tuy nhiên, không phải tất cả điều này đều hạn chế khả năng viết mã nhanh và thanh lịch đồng thời của chúng tôi không?

Có một số kỹ thuật nhất định có thể thực hiện các cuộc gọi đệ quy nhiều, nhanh hơn nhiều so với tình huống bình thường của chúng. Ví dụ: tối ưu hóa cuộc gọi đuôi SOWiki

Answer 3

Tóm lại, không thường xuyên như bạn nghĩ. Lý do là "các kỹ thuật ưa thích" như hợp nhất luồng được sử dụng khi các thư viện được triển khai và người dùng thư viện không cần phải lo lắng về chúng.

Cân nhắc Data.List.map. Các gói phần mềm cơ sở xác định map như

map :: (a -> b) -> [a] -> [b] 
map _ []  = [] 
map f (x:xs) = f x : map f xs 

này map là tự đệ quy, vì vậy GHC sẽ không inline nó.

Tuy nhiên, base cũng định nghĩa các quy tắc viết lại như sau:

{-# RULES 
"map"  [~1] forall f xs. map f xs    = build (\c n -> foldr (mapFB c f) n xs) 
"mapList" [1] forall f.  foldr (mapFB (:) f) [] = map f 
"mapFB"  forall c f g.  mapFB (mapFB c f) g  = mapFB c (f.g) 
    #-} 

này thay thế sử dụng của map qua foldr/build fusion, sau đó, nếu chức năng không thể hợp nhất, thay thế nó bằng bản gốc map. Bởi vì phản ứng tổng hợp xảy ra tự động, nó không phụ thuộc vào người dùng đang nhận thức được nó.

Như bằng chứng cho thấy tất cả các công trình này, bạn có thể kiểm tra những gì GHC tạo cho đầu vào cụ thể. Đối với chức năng này:

proc1 = sum . take 10 . map (+1) . map (*2) 

eval1 = proc1 [1..5] 
eval2 = proc1 [1..] 

khi biên soạn với -O2, GHC cầu chì tất cả các proc1 thành một dạng đệ quy đơn (như đã thấy trong đầu ra cốt lõi với -ddump-simpl).

Tất nhiên, có những giới hạn cho những kỹ thuật này có thể thực hiện được.Ví dụ: chức năng trung bình ngây thơ, mean xs = sum xs/length xs có thể dễ dàng được chuyển đổi thành một lần và frameworks exist that can do so automatically, tuy nhiên hiện tại không có cách nào để tự động dịch giữa các hàm chuẩn và khung kết hợp. Vì vậy, trong trường hợp này, người dùng cần phải nhận thức được các hạn chế của mã trình biên dịch tạo ra.

Vì vậy, trong nhiều trường hợp, trình biên dịch đủ nâng cao để tạo mã nhanh và thanh lịch. Biết khi nào họ sẽ làm như vậy, và khi trình biên dịch có khả năng rơi xuống, IMHO là một phần lớn trong việc học cách viết mã Haskell hiệu quả.