Birinci sınıf işlev - First-class function

İçinde bilgisayar Bilimi, bir Programlama dili sahip olduğu söyleniyor birinci sınıf işlevler tedavi ederse fonksiyonlar gibi birinci sınıf vatandaşlar. Bu, dilin işlevleri argüman olarak diğer işlevlere iletmeyi desteklediği, bunları diğer işlevlerden değerler olarak döndürdüğü ve bunları değişkenlere atadığı veya veri yapılarında depoladığı anlamına gelir.^[1] Bazı programlama dili teorisyenleri, anonim işlevler (işlev değişmezleri) de.^[2] Birinci sınıf işlevlere sahip dillerde, isimler işlevlerin özel bir durumu yoktur; sıradan gibi muamele görüyorlar değişkenler Birlikte işlev türü.^[3] Terim tarafından icat edildi Christopher Strachey 1960'ların ortalarında "birinci sınıf vatandaş olarak işlev görür" bağlamında.^[4]

Birinci sınıf işlevler, fonksiyonel programlama kullanımının olduğu stil üst düzey işlevler standart bir uygulamadır. Daha yüksek sıralı bir işlevin basit bir örneği, harita işlev, bağımsız değişkenleri olarak bir işlevi ve bir listeyi alır ve listenin her üyesine işlevi uygulayarak oluşturulan listeyi döndürür. Destekleyecek bir dil için harita, bir işlevin bağımsız değişken olarak iletilmesini desteklemelidir.

İşlevleri bağımsız değişken olarak geçirmede veya sonuç olarak döndürmede, özellikle de varlığında belirli uygulama zorlukları vardır. yerel olmayan değişkenler tanıtıldı yuvalanmış ve anonim işlevler. Tarihsel olarak, bunlar Funarg problemleri, "işlev bağımsız değişkeninden" gelen ad.^[5] Erken zorunlu dillerde, sonuç türleri olarak işlevleri desteklemeyerek bu sorunlardan kaçınıldı (örn. ALGOL 60, Pascal ) veya iç içe geçmiş işlevleri ve dolayısıyla yerel olmayan değişkenleri (ör. C ). Erken işlevsel dil Lisp yaklaşımını aldı dinamik kapsam, burada yerel olmayan değişkenler, tanımlandığı yer yerine, işlevin yürütüldüğü noktada o değişkenin en yakın tanımını ifade eder. İçin uygun destek sözcük kapsamlı birinci sınıf işlevler tanıtıldı Şema ve işlevlere referansların işlenmesini gerektirir. kapanışlar çıplak yerine işlev işaretçileri,^[4] hangi sırayla çöp toplama bir gereklilik.

Kavramlar

Bu bölümde, birinci sınıf işlevlerle işlevsel bir dilde belirli programlama deyimlerinin nasıl işlendiğini karşılaştırıyoruz (Haskell ) işlevlerin ikinci sınıf vatandaşlar olduğu zorunlu bir dile kıyasla (C ).

Üst düzey işlevler: işlevleri bağımsız değişken olarak iletme

İşlevlerin birinci sınıf vatandaş olduğu dillerde, işlevler, diğer değerlerle aynı şekilde diğer işlevlere bağımsız değişken olarak aktarılabilir (başka bir işlevi bağımsız değişken olarak alan bir işlev, üst düzey işlev olarak adlandırılır). Dilde Haskell:

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

İşlevlerin birinci sınıf olmadığı diller, çoğu zaman birinin, aşağıdaki gibi özelliklerin kullanımı yoluyla daha yüksek düzey işlevler yazmasına izin verir işlev işaretçileri veya delegeler. Dilde C:

geçersiz harita(int (*f)(int), int x[], size_t n) {    için (int ben = 0; ben < n; ben++)        x[ben] = f(x[ben]);}

İki yaklaşım arasında birkaç fark vardır: değil doğrudan birinci sınıf işlevlerin desteğiyle ilgilidir. Haskell örneği, listeler C örneği çalışırken diziler. Her ikisi de ilgili dillerdeki en doğal bileşik veri yapılarıdır ve C örneğinin bağlantılı listelerde çalışmasını sağlamak, gereksiz yere karmaşık hale getirebilirdi. Bu aynı zamanda C işlevinin ek bir parametreye ihtiyaç duyduğu gerçeğini de açıklar (dizinin boyutunu verir.) C işlevi diziyi günceller. yerinde, değer döndürmezken Haskell veri yapıları kalici (eski olduğu gibi bırakılırken yeni bir liste döndürülür.) Haskell örneği, özyineleme C örneği kullanırken listede gezinmek için yineleme. Yine, bu işlevi her iki dilde ifade etmenin en doğal yolu budur, ancak Haskell örneği kolaylıkla bir terimle ifade edilebilirdi. kat ve C örneği özyineleme açısından. Son olarak, Haskell işlevi bir polimorfik tür, bu C tarafından desteklenmediğinden, tüm tür değişkenlerini tür sabitine sabitledik int.

Anonim ve iç içe geçmiş işlevler

Anonim işlevleri destekleyen dillerde, böyle bir işlevi argüman olarak daha yüksek dereceli bir işleve geçirebiliriz:

ana = harita (\x -> 3 * x + 1) [1, 2, 3, 4, 5]

Anonim işlevleri desteklemeyen bir dilde, bunun yerine onu bir isme bağlamamız gerekir:

int f(int x) {    dönüş 3 * x + 1;}int ana() {    int liste[] = {1, 2, 3, 4, 5};    harita(f, liste, 5);}

Yerel olmayan değişkenler ve kapanışlar

Anonim veya iç içe işlevlere sahip olduğumuzda, vücutlarının dışındaki değişkenlere atıfta bulunmaları doğal hale gelir ( yerel olmayan değişkenler):

ana = İzin Vermek a = 3           b = 1        içinde harita (\x -> a * x + b) [1, 2, 3, 4, 5]

Fonksiyonlar çıplak fonksiyon işaretçileriyle temsil ediliyorsa, fonksiyon gövdesi dışındaki değerin ona nasıl aktarılması gerektiğini artık bilemeyiz ve bu nedenle manuel olarak bir kapama yapılması gerekir. Bu nedenle burada "birinci sınıf" işlevlerden söz edemeyiz.

typedef yapı {    int (*f)(int, int, int);    int *a;    int *b;} closure_t;geçersiz harita(closure_t *kapatma, int x[], size_t n) {    için (int ben = 0; ben < n; ++ben)        x[ben] = (*kapatma->f)(*kapatma->a, *kapatma->b, x[ben]);}int f(int a, int b, int x) {    dönüş a * x + b;}geçersiz ana() {    int l[] = {1, 2, 3, 4, 5};    int a = 3;    int b = 1;    closure_t kapatma = {f, &a, &b};    harita(&kapatma, l, 5);}

Ayrıca unutmayın harita artık ikiye atıfta bulunan işlevler için uzmanlaşmıştır intçevrelerinin dışında. Bu daha genel olarak kurulabilir ancak daha fazlasını gerektirir Genelge kodu. Eğer f olabilirdi iç içe geçmiş işlev Yine de aynı problemle karşılaşırdık ve bu yüzden C'de desteklenmiyorlar.^[6]

Üst düzey işlevler: işlevleri sonuç olarak döndürme

Bir işlevi döndürürken, aslında onun kapanışını döndürüyoruz. C örneğinde, kapanış tarafından yakalanan herhangi bir yerel değişken, kapanışı oluşturan işlevden döndüğümüzde kapsam dışına çıkacaktır. Daha sonraki bir noktada kapatmaya zorlamak, muhtemelen yığını bozan tanımlanmamış davranışa neden olacaktır. Bu, yukarı doğru funarg problemi.

Değişkenlere fonksiyon atama

Atama fonksiyonları değişkenler ve bunları (küresel) veri yapıları içinde depolamak, potansiyel olarak geri dönen işlevlerle aynı zorluklardan muzdariptir.

f :: [[Tamsayı] -> [Tamsayı]]f = İzin Vermek a = 3        b = 1     içinde [harita (\x -> a * x + b), harita (\x -> b * x + a)]

İşlevlerin eşitliği

Çoğu değişmez değeri ve değeri eşitlik için test edebileceğinden, bir programlama dilinin eşitlik için test işlevlerini destekleyip desteklemediğini sormak doğaldır. Daha ayrıntılı bir incelemede, bu soru daha zor görünmektedir ve çeşitli fonksiyon eşitliği türleri arasında ayrım yapılması gerekir:^[7]

Kapsamlı eşitlik

İki fonksiyon f ve g tüm girdiler için çıktıları üzerinde mutabık kalırlarsa uzantı olarak eşit kabul edilirler (∀x. f(x) = g(x)). Bu eşitlik tanımına göre, örneğin, herhangi iki uygulama kararlı sıralama algoritması, gibi ekleme sıralaması ve sıralamayı birleştir, eşit kabul edilecektir. Genişleme eşitliğine karar vermek karar verilemez genel olarak ve hatta sonlu alanlara sahip fonksiyonlar için bile çoğu zaman inatçı değildir. Bu nedenle, hiçbir programlama dili genişleme eşitliği olarak işlev eşitliğini uygulamaz.

İçsel eşitlik

İçsel eşitlik altında iki işlev f ve g aynı "iç yapıya" sahiplerse eşit kabul edilir. Bu tür bir eşitlik, yorumlanmış diller karşılaştırarak kaynak kodu fonksiyon gövdelerinin (Yorumlanmış Lisp 1.5 gibi) veya nesne kodu içinde derlenmiş diller. İçsel eşitlik, genişleme eşitliği anlamına gelir (işlevlerin deterministik olduğunu ve gizli girdileri olmadığını varsayarsak, program sayıcı veya değişebilir küresel değişken.)

Referans eşitliği

Genişletme ve içsel eşitliği uygulamanın pratik olmadığı düşünüldüğünde, eşitlik için test işlevlerini destekleyen çoğu dil referans eşitliği kullanır. Tüm işlevlere veya kapanışlara benzersiz bir tanımlayıcı (genellikle işlev gövdesinin veya kapanışın adresi) atanır ve eşitlik, tanımlayıcının eşitliğine göre belirlenir. Ayrı ayrı tanımlanmış, ancak aksi takdirde aynı işlev tanımları eşit olmayan olarak kabul edilecektir. Referans eşitliği, içsel ve kapsamlı eşitliği ifade eder. Referans eşitliği kırılmaları referans şeffaflık ve bu nedenle de desteklenmez saf Haskell gibi diller.

Tip teorisi

İçinde tip teorisi tür değerlerini kabul eden işlevlerin türü Bir ve türdeki değerleri döndürmek B olarak yazılabilir Bir → B veya B^Bir. İçinde Curry-Howard yazışmaları, fonksiyon türleri ile ilgilidir mantıksal çıkarım; lambda soyutlaması, varsayımsal varsayımları boşa çıkarmaya karşılık gelir ve işlev uygulaması, modus ponens çıkarım kuralı. Tip teorisi, programlama fonksiyonlarının genel durumunun yanı sıra, modellemek için birinci sınıf fonksiyonları da kullanır. ilişkilendirilebilir diziler ve benzeri veri yapıları.

İçinde kategori-teorik programlama hesapları, birinci sınıf fonksiyonların kullanılabilirliği, kapalı kategori Varsayım. Örneğin, basit yazılan lambda hesabı iç diline karşılık gelir Kartezyen kapalı kategoriler.

Dil desteği

Gibi fonksiyonel programlama dilleri Şema, ML, Haskell, F #, ve Scala hepsi birinci sınıf işlevlere sahiptir. Ne zaman Lisp en eski işlevsel dillerden biri olan, tasarlandı, birinci sınıf işlevlerin tüm yönleri daha sonra tam olarak anlaşılmadı, bu da işlevlerin dinamik olarak kapsamlanmasına neden oldu. Sonra Şema ve Ortak Lisp lehçeler sözcüksel olarak birinci sınıf işlevlere sahiptir.

Dahil olmak üzere birçok komut dosyası dili Perl, Python, PHP, Lua, Tcl / Tk, JavaScript ve Io, birinci sınıf işlevlere sahiptir.

Zorunlu diller için Algol ve onun soyundan gelen Pascal, geleneksel C ailesi ve modern çöp toplama varyantları arasında bir ayrım yapılmalıdır. Algol ailesi, iç içe geçmiş işlevlere ve bağımsız değişken olarak daha yüksek sıralı alma işlevine izin verdi, ancak sonuç olarak işlevler döndüren daha yüksek düzey işlevlere izin vermedi (buna izin veren Algol 68 hariç). Bunun nedeni, sonuç olarak iç içe geçmiş bir işlev döndürülürse yerel olmayan değişkenlerle nasıl başa çıkılacağının bilinmemesiydi (ve Algol 68 bu gibi durumlarda çalışma zamanı hataları üretir).

C ailesi, hem işlevlerin bağımsız değişken olarak aktarılmasına hem de sonuç olarak döndürülmesine izin verdi, ancak iç içe geçmiş işlevleri desteklemeyerek herhangi bir sorundan kaçındı. (Gcc derleyicisi bunlara bir uzantı olarak izin verir.) İşlevleri döndürmenin faydası, esas olarak, üst düzey işlevler yerine yerel olmayan değişkenleri yakalayan yuvalanmış işlevleri döndürme becerisinde yattığından, bu diller genellikle ilk önce -sınıf fonksiyonları.

Modern zorunlu diller genellikle çöp toplamayı destekler ve birinci sınıf işlevlerin uygulanmasını mümkün kılar. Birinci sınıf işlevler, genellikle yalnızca C # 2.0 ve Apple'ın C, C ++ ve Objective-C'ye yönelik Bloklar uzantısı dahil olmak üzere dilin sonraki revizyonlarında desteklenmiştir. C ++ 11, dile anonim işlevler ve kapanmalar için destek ekledi, ancak dilin çöp toplama olmayan doğası nedeniyle, sonuç olarak döndürülecek işlevlerdeki yerel olmayan değişkenlere özel dikkat gösterilmesi gerekir (aşağıya bakın) ).

C ++

C ++ 11 kapanışlar yerel olmayan değişkenleri referansla (ömürlerini uzatmadan), kopya oluşturma yoluyla veya hareket inşaatı (değişken kapanış olduğu sürece yaşar). İlki, potansiyel olarak pahalı bir kopyayı önler ve orijinal değişkeni değiştirmeye izin verir, ancak kapanışın geri dönmesi durumunda güvensizdir (bkz. sarkan referanslar ). İkincisi, kapanış döndürülürse ancak bir kopya gerektirirse ve orijinal değişkeni değiştirmek için kullanılamazsa güvenlidir (bu, kapanma çağrıldığı sırada artık mevcut olmayabilir). İkincisi, kapanış döndürülürse güvenlidir ve bir kopya gerektirmez, ancak orijinal değişkeni değiştirmek için de kullanılamaz.

Java

Java 8 kapanışlar yalnızca nihai veya "etkili bir şekilde nihai" yerel olmayan değişkenleri yakalayabilir. Java's fonksiyon türleri Sınıflar olarak temsil edilir. Anonim işlevler, bağlamdan çıkarılan türü alır. Yöntem referansları sınırlıdır. Daha fazla ayrıntı için bkz. Anonim işlev § Java sınırlamaları.

Lisp

Sözcüksel kapsamlı Lisp çeşitleri kapanışları destekler. Dinamik olarak kapsamlı varyantlar, kapakları desteklemez veya kapaklar oluşturmak için özel bir yapıya ihtiyaç duyar.^[22]

İçinde Ortak Lisp, işlev ad alanındaki bir işlevin tanımlayıcısı, birinci sınıf bir değere başvuru olarak kullanılamaz. Özel operatör işlevi işlevi bir değer olarak almak için kullanılmalıdır: (işlev foo) bir işlev nesnesi olarak değerlendirilir. # 'foo bir stenografi notasyonu olarak mevcuttur. Böyle bir işlev nesnesini uygulamak için, kişinin funcall işlev: (funcall # 'foo bar baz).

Python

İle açık kısmi uygulama functools.partial 2.5 sürümünden beri ve operator.methodcaller 2.6 sürümünden beri.

Yakut

Ruby'deki normal bir "fonksiyon" un tanımlayıcısı (gerçekten bir yöntemdir) bir değer olarak kullanılamaz veya geçirilemez. Önce bir Yöntem veya Proc birinci sınıf veri olarak kullanılacak nesne. Böyle bir işlev nesnesini çağırmanın sözdizimi, normal yöntemleri çağırmaktan farklıdır.

İç içe geçmiş yöntem tanımları aslında kapsamı iç içe geçirmez.

Açıkça körleme [1].

Ayrıca bakınız

• İşlevsizleştirme
• değerlendirme
• Birinci sınıf mesaj
• Kappa hesabı - birinci sınıf işlevleri dışlayan bir biçimcilik
• Erkek mi erkek mi testi
• Kısmi uygulama

Notlar

Referanslar

• Leonidas Fegaras. "İşlevsel Diller ve Üst Düzey İşlevler". CSE5317 / CSE4305: Derleyicilerin Tasarımı ve Yapısı. Arlington'daki Texas Üniversitesi.

Dış bağlantılar

• Birinci sınıf işlevler açık Rosetta Kodu.
• Daha yüksek dereceli fonksiyonlar -de IBM developerWorks