işlevsizleştirme - Defunctionalization

In programlama dilleri , defunctionalization bir olan derleme zamanı ortadan kaldırır dönüşüm yüksek sıralı fonksiyonlarını tek bir birinci emriyle bunların yerine, geçerli fonksiyonu. Teknik ilk olarak John C. Reynolds tarafından 1972 tarihli "Yüksek Dereceli Programlama Dilleri için Tanımlayıcı Tercümanlar" başlıklı makalesinde tanımlanmıştır . Reynolds'ın gözlemi, belirli bir programın yalnızca sonlu sayıda işlev soyutlaması içerdiği, böylece her birinin benzersiz bir tanımlayıcı ile atanabileceği ve değiştirilebileceğiydi. Program içindeki her işlev uygulaması daha sonra ilk argüman olarak işlev tanımlayıcısı olan Apply işlevine yapılan bir çağrı ile değiştirilir . Uygulamak işlevin tek iş bu ilk argüman üzerinde sevk etmektir ve ardından kalan argümanlar fonksiyon tanımlayıcı ile gösterilir talimatları gerçekleştirin.

Bu temel fikrin bir komplikasyonu, fonksiyon soyutlamalarının serbest değişkenlere başvurabilmesidir . Bu gibi durumlarda, işlevsizleştirmeden önce kapatma dönüşümü (lambda kaldırma) gelmelidir , böylece bir işlev soyutlamasının herhangi bir serbest değişkeni, uygulanacak ek argümanlar olarak iletilir . Ayrıca, kapanışlar birinci sınıf değerler olarak destekleniyorsa , bu yakalanan bağlamaları veri yapıları oluşturarak temsil etmek gerekli hale gelir.

Bir programdaki tüm işlev soyutlamalarında tek bir uygulama işlevi göndermek yerine , her bir işlev uygulamasında hangi işlevlerin çağrılabileceğini belirlemek için çeşitli türlerde kontrol akışı analizi ( arity veya tip imzasına dayalı basit ayrımlar dahil ) kullanılabilir. site ve bunun yerine özel bir uygulama işlevine başvurulabilir. Alternatif olarak, hedef dil, gönderme tabanlı bir yaklaşımdan daha verimli ve genişletilebilir olabilen işlev işaretçileri aracılığıyla dolaylı çağrıları destekleyebilir .

Üst düzey işlevsel diller için bir derleme tekniği olarak kullanımının yanı sıra , işlevsizleştirme (özellikle Olivier Danvy ve ortak çalışanlar tarafından) yorumlayıcıları mekanik olarak soyut makinelere dönüştürmenin bir yolu olarak incelenmiştir . İşlevsizleştirme aynı zamanda , işlevleri işlev nesneleri (kapatmalara alternatif olarak) ile temsil eden nesne yönelimli programlama tekniğiyle de ilgilidir .

Misal

Bu, Olivier Danvy tarafından Haskell'e çevrilmiş bir örnektir :

Ağaç veri türü göz önüne alındığında: 

data Tree a = Leaf a
            | Node (Tree a) (Tree a)

Aşağıdaki programı devre dışı bırakacağız: 

cons :: a -> [a] -> [a]
cons x xs = x : xs

o :: (b -> c) -> (a -> b) -> a -> c
o f g x = f (g x)

flatten :: Tree t -> [t]
flatten t = walk t []

walk :: Tree t -> [t] -> [t]
walk (Leaf x)     = cons x
walk (Node t1 t2) = o (walk t1) (walk t2)

Tüm yüksek dereceli işlevleri (bu durumda, otek yüksek dereceli işlevdir) Lamveri türünün bir değeriyle değiştirerek işlevsizleştiririz ve bunları doğrudan çağırmak yerine apply, veri türünü yorumlayan bir işlev sunarız: 

data Lam a = LamCons a
           | LamO (Lam a) (Lam a)

apply :: Lam a -> [a] -> [a]
apply (LamCons x)  xs = x : xs
apply (LamO f1 f2) xs = apply f1 (apply f2 xs)

cons_def :: a -> Lam a
cons_def x  = LamCons x

o_def :: Lam a -> Lam a -> Lam a
o_def f1 f2 = LamO f1 f2

flatten_def :: Tree t -> [t]
flatten_def t = apply (walk_def t) []

walk_def :: Tree t -> Lam t
walk_def (Leaf x)     = cons_def x
walk_def (Node t1 t2) = o_def (walk_def t1) (walk_def t2)

Ayrıca bakınız

Referanslar

  • Reynolds, John (Ağustos 1972). "Yüksek Dereceli Programlama Dilleri için Tanımlayıcı Tercümanlar". ACM Yıllık Konferansı Tutanakları . Boston, Massachusetts. s. 717-740. doi : 10.1145/800194.805852 .
  • Danvy, Olivier ; Nielsen, Lasse R. (2001). "İş Yerinde İşlevsizleştirme" (PDF) . ACM SIGPLAN Bildirisel Programlamanın İlkeleri ve Uygulaması Konferansı Tutanakları . s. 162-174. doi : 10.1145/773184.773202 .(Daha kapsamlı versiyon: Teknik Rapor BRICS-RS-01-23 )
  • Danvy, Olivier ; Millikin, Kevin R. (Haziran 2009). "İş Yerinde Yeniden İşlevselleştirme" . Bilgisayar Programlama Bilimi . 74 (8): 534-549. doi : 10.1016/j.scico.2007.10.007 .( Teknik Rapor BRICS-RS-07-7 olarak da mevcuttur )

Dış bağlantılar