Soru Değerlendirme stratejisi


Haskell'de aşağıdaki gibi örneklerde işlev değerlendirmesinin bir nedeni nasıl olmalıdır:

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

GHC’de bazen (f x) yalnızca bir kez değerlendirilir ve bazen her bir öğe için bir kez xstam olarak ne bağlı olarak f ve g vardır. Bu önemli olabilir f x pahalı bir hesaplamadır. Sadece bir Haskell acemi yardımcı oldum ve ona anlatmaktan başka ne olduğunu söylemedim. Daha iyi bir hikaye var mı?

Güncelleştirme

Aşağıdaki örnekte (f x) 4 kez değerlendirilecek:

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

21
2018-02-24 23:23


Menşei


Bir örneğiniz var mı f x bir kereden fazla değerlendiriliyor? - hammar
@hammar: Ben böyle bir örnek ekledim. - Grzegorz Chrupała
@Grzegorz Sadece optimize etmediğinizde bunun geçerli olduğunu belirtmelisiniz. Daha yüksek sıralama türlerine izin verirseniz, optimizasyonun tekrarlanan değerlendirmeyi kaldıramadığı bir örnek verebilirim. Ilgilenen? - Daniel Fischer
Bunu yapmak ghci almak oldukça kolaydır, bunu deneyin hpaste.org/64300 - daha karmaşık bir durumda, derleme ile olsa da, çıkarsama yapmaz. (Gzegorz'un bunu yaparken bir örnek eklediğini görüyorum.) - applicative
@DanielFischer Elbette. - Grzegorz Chrupała


Cevaplar:


Dil uzantıları ile, durumları oluşturabiliriz. f x  şart tekrar tekrar değerlendirilmelidir:

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

Crux sahip olmaktır f x argüman olarak bile polimorfik gve gerekli olan tür (ler) in önceden tahmin edilemediği bir durum yaratmalıyız (ilk bıçak benim Either a b yerine BIAncak, optimizasyon yaparken, elbette ki sadece iki değerlendirmeye yol açtı. f x en fazla).

Bir polimorfik ifade, kullanıldığı her tip için en az bir kez değerlendirilmelidir. Monomorfizm kısıtlaması için tek sebep budur. Bununla birlikte, ihtiyaç duyulabilecek türlerin kapsamı kısıtlandığında, her türdeki değerleri not etmek mümkündür ve bazı durumlarda GHC bunu yapar (optimizasyon gerektirir ve ilgili türlerin sayısının da olmaması gerekir). büyük). Burada temel olarak homojen olmayan bir liste ile karşı karşıyayız, böylece her bir g (f x)Bu, kısıtlamaları karşılayan keyfi bir tipte gerekli olabilir, bu nedenle hesaplama dışarıda kaldırılamaz. map (teknik olarak, derleyici hala kullanılan her türdeki değerlerin bir önbelleğini oluşturabilirdi, bu nedenle tür başına yalnızca bir kez değerlendirilecekti, ancak GHC hiçbir şekilde problem olmayacaktı).

  • Monomorfik ifadeler sadece bir kez değerlendirilmeli, paylaşılabilir. Onlar olup olmadığı uygulamaya kadar; saflık tarafından, programın anlamlarını değiştirmez. İfade bir isme bağlıysa, pratikte, paylaşıldığından emin olabilirsiniz, çünkü programcının istediği kolay ve açıktır. Bir isme bağlı değilse, optimizasyon meselesidir. Bayt kodu üreteci ile veya optimizasyonlar olmadan, ifade genellikle tekrar tekrar değerlendirilir, ancak optimizasyonların tekrarlanmasıyla birlikte derleyici bir hataya işaret eder.
  • Polimorfik ifadeler, en az bir kez kullanıldıkları her tip için değerlendirilmelidir, ancak en iyi duruma getirme ile, GHC, aynı türde birden çok kez kullanılabildiğini görebiliyorsa, (genellikle) bu tip için yine de daha büyük hesaplama.

Alt satır: Her zaman optimizasyonlarla derleyin, bir isimle paylaşılmasını istediğiniz ifadeleri birleştirerek derleyiciye yardımcı olun ve mümkün olduğunda monomorfik imzalar verin.


9
2018-02-25 02:05





Örneklerin gerçekten çok farklı.

İlk örnekte, haritanın argümanı g (f x) ve bir kez geçer mapbüyük olasılıkla kısmen uygulanan işlev olarak. Meli g (f x)içinde bir argümana uygulandığında map ilk argümanını değerlendirir, sonra bu sadece bir kez yapılır ve daha sonra thunk (fx) sonuç ile güncellenecektir.

Dolayısıyla, ilk örneğinizde, f xdeğerlendirilecek en fazla 1 kez.

İkinci örneğiniz, derleyicinin (f x) lambda ifadesinde her zaman sabit olduğu sonucuna varmadan önce daha derin bir analiz gerektirir. Belki de onu hiç bir zaman optimize etmeyecektir, çünkü izlerin oldukça fazla olmadığı bilgisi olabilir. koşer. Bu nedenle, izleme sırasında 4 kez ve izlemediğinde 4 veya 1 kez değerlendirilebilir.


8
2018-02-25 00:49



İyi nokta, ilk örneği çok basitleştirdim. Yeniden izleme: eğer f xpahalıdır, kullanmadan da yeniden değerlendirildiğini görmek kolaydır trace. - Grzegorz Chrupała
Evet. Ancak asıl nokta, ikinci örnekte bazı kod dönüşümleri gerektirmesidir (ör. let xxx = f x in map (\i -> lookup i xxx) "abcd") f x gibi pahalı sabitleri dışlamak için, ilk örnekte, herhangi bir optimizasyon olmaksızın bile en dürüst derleyici bile, sonuçta ortaya çıkan kod üretecek ne olursa olsun (çünkü katı olmayan thunk değerlendirme ve güncelleme zaten RTS'de gerçekleşir). - Ingo


Bu, söyleyebildiğiniz üzere GHC'nin optimizasyonlarına gerçekten bağlı.

en iyi yapılacak şey çalışmaktır GHC çekirdeği Programı optimize ettikten sonra alırsınız. Oluşturulan Çekirdeğe bakıp f x kendi vardı let dışında ifade map ya da değil.

Eğer olmak istersen emin, o zaman faktörü f x kendi değişkenine atanan letAncak, Core ile okumaktan başka bir şey anlamanın gerçekten garantili bir yolu yoktur.

Bütün söylediklerim gibi şeyler hariç trace bu kullan unsafePerformIOBu, programınızın anlamını asla değiştirmeyecek: aslında nasıl davrandığını.


6
2018-02-25 00:31





Optimizasyon yapmadan GHC'de, fonksiyonun gövdesi her fonksiyon çağrıldığında değerlendirilir. (Bir "çağrı", işlevin argümanlara uygulandığı ve sonucun değerlendirildiği anlamına gelir.) Aşağıdaki örnekte, f x bir fonksiyonun içinde yer alır, böylece fonksiyon her çağrıldığında çalışır. (GHC, bu ifadeyi SSS [1] 'de tartışıldığı gibi optimize edebilir.)

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

Ancak, hareket edersek f x işlev dışı, sadece bir kez yürütecek.

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

Bu daha kolay okunabilir şekilde yeniden yazılabilir

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

Genel kural, her defasında bir argümana bir fonksiyonun uygulandığı zaman, fonksiyon gövdesinin yeni bir "kopyası" oluşturulur. İşlev uygulaması, bir ifadenin yeniden çalıştırılmasına neden olabilecek tek şeydir. Ancak, bazı işlevlerin ve işlev çağrılarının sözdizimsel işlevler gibi görünmediği konusunda uyarılmalıdır.

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


6
2018-02-25 03:36