GHC non può mai realmente mappare, scanl, foldr, ecc.?

Question

Ho notato che lo GHC manual dice "per una funzione auto-ricorsiva, l'interruttore di loop può essere solo la funzione stessa, quindi un pragma INLINE viene sempre ignorato."

non dice questo ogni applicazione di costrutti funzionali ricorsive comuni come map, zip, scan*, fold*, sum, ecc non può essere inline?

È sempre possibile riscrivere tutte queste funzioni quando le si utilizza, aggiungendo tag di rigore appropriati, o magari impiegare tecniche di fantasia come la "stream fusion" consigliata here.

Tuttavia, tutto questo non limita drammaticamente la nostra capacità di scrivere codice che sia allo stesso tempo veloce ed elegante?

Answer 1

Infatti, GHC non può attualmente funzioni in linea ricorsive. Tuttavia:

• GHC sarà ancora specializzarsi funzioni ricorsive. Per esempio, dato

  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 sarà posto che fac viene utilizzato al tipo Int -> Int e generare una versione specializzata di fac per quel tipo, che utilizza veloce aritmetica intera.

  Questa specializzazione avviene automaticamente all'interno di un modulo (ad esempio se fac e f sono definiti nello stesso modulo). Cross-modulo specialistico (ad esempio, se f e fac sono definiti in diversi moduli), contrassegnare la funzione a-essere specializzati con an INLINABLE pragma:

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

• Ci sono trasformazioni manuali che rendono funzioni ricorsiva. La tecnica a potenza più bassa è static argument transformation, che si applica alle funzioni ricorsive con argomenti che non cambiano sulle chiamate ricorsive (ad esempio, molte funzioni di ordine superiore come map, filter, fold*). Questa trasformazione trasforma

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

  in

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

  modo che una chiamata come

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

  avrà map inlined e diventare

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

  questo transformati on è stato applicato a funzioni di prelettura come foldr e foldl.

• Le tecniche di fusione rendono anche molte funzioni non ricorsive e sono più potenti della trasformazione degli argomenti statici. L'approccio principale per gli elenchi, che è incorporato nel Preludio, è shortcut fusion. L'approccio di base è scrivere quante più funzioni possibili come funzioni non ricorsive che usano foldr e/o build; quindi tutta la ricorsione viene catturata in foldr e ci sono REGOLE speciali per trattare con foldr.

  Sfruttando questa fusione è in linea di principio semplice: evitare ricorsione manuale, preferendo funzioni di libreria come foldr, map, filter, e tutte le funzioni in this list.In particolare, scrivere codice in questo stile produce codice che è "simultaneamente veloce ed elegante".

• Le biblioteche moderne come text e vector utilizzano stream fusion dietro le quinte. Don Stewart ha scritto un paio di post sul blog (1, 2) dimostrando questo in azione nella libreria ora obsoleta uvector, ma gli stessi principi si applicano al testo e al vettore.

  Come per la fusione di scorciatoie, sfruttare la fusione del flusso in testo e vettoriale è in linea di principio semplice: evitare la ricorsione manuale, preferendo le funzioni di libreria contrassegnate come "soggette a fusione".

• È in corso un lavoro per migliorare GHC per supportare l'inlining delle funzioni ricorsive. Questo rientra nella rubrica generale supercompilation e recenti lavori su questo sembrano essere stati guidati da Max Bolingbroke e Neil Mitchell.

Answer 2

per una funzione auto-ricorsiva, l'interruttore di loop può essere solo la funzione stessa, quindi un prgma INLINE viene sempre ignorato.

Se qualcosa è ricorsivo, per indicarlo, è necessario sapere quante volte viene eseguito in fase di compilazione. Considerando che sarà un input di lunghezza variabile, ciò non è possibile.

Tuttavia, tutto questo non riduce drasticamente la nostra capacità di scrivere codice che sia contemporaneamente veloce ed elegante?

Esistono tuttavia alcune tecniche che possono effettuare chiamate ricorsive molto, molto più rapidamente rispetto alla loro situazione normale. Ad esempio, ottimizzazione chiamata coda SOWiki

Answer 3

In breve, non tutte le volte che si potrebbe pensare. La ragione è che le "tecniche di fantasia" come la fusione del flusso vengono impiegate quando le librerie sono implementate e gli utenti delle librerie non devono preoccuparsi di esse.

Considerare Data.List.map. Il pacchetto di base definisce map come

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

Questo map è auto-ricorsivo, quindi GHC non inline esso.

Tuttavia, base definisce anche le seguenti regole di riscrittura:

{-# 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) 
    #-} 

Questo sostituisce usi di map via foldr/build fusion, quindi, se la funzione non può essere fuso, lo sostituisce con l'originale map. Poiché la fusione avviene automaticamente, non dipende dall'essere a conoscenza dell'utente.

A dimostrazione che tutto funziona, è possibile esaminare ciò che GHC produce per specifici input. Per questa funzione:

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

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

se compilato con -O2, GHC fonde tutti proc1 in un'unica forma ricorsiva (come visto nell'output core con -ddump-simpl).

Ovviamente ci sono dei limiti a ciò che queste tecniche possono realizzare.Ad esempio, la funzione media ingenua, mean xs = sum xs/length xs, può essere trasformata manualmente in una singola piega e frameworks exist that can do so automatically, tuttavia al momento non esiste un modo noto per tradurre automaticamente tra le funzioni standard e il framework di fusione. Quindi, in questo caso, l'utente deve essere consapevole delle limitazioni del codice prodotto dal compilatore.

Quindi in molti casi i compilatori sono sufficientemente avanzati per creare codice rapido ed elegante. Sapendo quando lo faranno, e quando il compilatore rischia di cadere, IMHO è una grande parte dell'apprendimento su come scrivere codice Haskell efficiente.