Penunjuk fungsi, Penutupan, dan Lambda

Saya baru saja belajar tentang fungsi pointer dan, saat saya membaca bab K&R tentang subjek tersebut, hal pertama yang membuat saya tersadar adalah, "Hei, ini seperti penutupan." Saya tahu asumsi ini pada dasarnya salah dan setelah melakukan pencarian online saya tidak menemukan analisis apa pun dari perbandingan ini.

Jadi mengapa penunjuk fungsi gaya-C pada dasarnya berbeda dari closure atau lambda? Sejauh yang saya tahu itu ada hubungannya dengan fakta bahwa penunjuk fungsi masih menunjuk ke fungsi yang ditentukan (bernama) sebagai lawan dari praktik mendefinisikan fungsi secara anonim.

Mengapa meneruskan fungsi ke suatu fungsi dipandang lebih kuat dalam kasus kedua, di mana ia tidak disebutkan namanya, daripada yang pertama yang hanya merupakan fungsi normal sehari-hari yang sedang diteruskan?

Tolong beritahu saya bagaimana dan mengapa saya salah membandingkan keduanya begitu dekat.

Terima kasih.

Lambda (atau closure ) merangkum penunjuk fungsi dan variabel. Inilah sebabnya, di C #, Anda dapat melakukan:

int lessThan = 100;
Func<int, bool> lessThanTest = delegate(int i) {
   return i < lessThan;
};

Saya menggunakan delegasi anonim di sana sebagai closure (sintaksnya sedikit lebih jelas dan lebih dekat ke C daripada lambda yang setara), yang menangkap lessThan (variabel stack) ke dalam closure. Saat penutupan dievaluasi, lessThan (yang bingkai tumpukannya mungkin telah dihancurkan) akan terus direferensikan. Jika saya mengubah lebih sedikit dari, maka saya mengubah perbandingan:

int lessThan = 100;
Func<int, bool> lessThanTest = delegate(int i) {
   return i < lessThan;
};

lessThanTest(99); // returns true
lessThan = 10;
lessThanTest(99); // returns false

Di C, ini ilegal:

BOOL (*lessThanTest)(int);
int lessThan = 100;

lessThanTest = &LessThan;

BOOL LessThan(int i) {
   return i < lessThan; // compile error - lessThan is not in scope
}

meskipun saya bisa mendefinisikan penunjuk fungsi yang membutuhkan 2 argumen:

int lessThan = 100;
BOOL (*lessThanTest)(int, int);

lessThanTest = &LessThan;
lessThanTest(99, lessThan); // returns true
lessThan = 10;
lessThanTest(100, lessThan); // returns false

BOOL LessThan(int i, int lessThan) {
   return i < lessThan;
}

Tapi, sekarang saya harus melewatkan 2 argumen ketika saya mengevaluasinya. Jika saya ingin meneruskan penunjuk fungsi ini ke fungsi lain di mana lessThan tidak ada dalam cakupan, saya harus menjaganya tetap hidup secara manual dengan meneruskannya ke setiap fungsi dalam rantai, atau dengan mempromosikannya ke global.

Meskipun sebagian besar bahasa utama yang mendukung penutupan menggunakan fungsi anonim, tidak ada persyaratan untuk itu. Anda dapat memiliki penutupan tanpa fungsi anonim, dan fungsi anonim tanpa penutupan.

Ringkasan: closure adalah kombinasi dari function pointer + variabel yang ditangkap.

Sebagai seseorang yang telah menulis kompiler untuk bahasa dengan dan tanpa penutupan 'nyata', saya dengan hormat tidak setuju dengan beberapa jawaban di atas. Penutupan Lisp, Skema, ML, atau Haskell tidak membuat fungsi baru secara dinamis . Sebagai gantinya, ia menggunakan kembali fungsi yang ada tetapi melakukannya dengan variabel bebas baru . Kumpulan variabel bebas sering disebut lingkungan , setidaknya oleh ahli teori bahasa pemrograman.

Penutupan hanyalah agregat yang berisi fungsi dan lingkungan. Dalam compiler ML Standar New Jersey, kami menampilkan satu sebagai record; satu bidang berisi penunjuk ke kode, dan bidang lainnya berisi nilai variabel bebas. Kompilator membuat closure baru (bukan fungsi) secara dinamis dengan mengalokasikan record baru yang berisi pointer ke kode yang sama , tetapi dengan nilai berbeda untuk variabel bebas.

Anda dapat mensimulasikan semua ini di C, tetapi itu menyebalkan. Dua teknik populer:

1. Meneruskan pointer ke fungsi (kode) dan pointer terpisah ke variabel bebas, sehingga closure dibagi menjadi dua variabel C.

2. Meneruskan pointer ke struct, di mana struct berisi nilai-nilai variabel bebas dan juga pointer ke kode.

Teknik # 1 sangat ideal ketika Anda mencoba untuk mensimulasikan semacam polimorfisme dalam C dan Anda tidak ingin mengungkapkan jenis lingkungan --- Anda menggunakan penunjuk void * untuk mewakili lingkungan. Misalnya, lihat Antarmuka dan Penerapan C Dave Hanson . Teknik # 2, yang lebih mirip dengan apa yang terjadi pada kompiler kode asli untuk bahasa fungsional, juga mirip dengan teknik lain yang sudah dikenal ... Objek C ++ dengan fungsi anggota virtual. Implementasinya hampir sama.

Pengamatan ini membawa ke bijak dari Henry Baker:

Orang-orang di dunia Algol / Fortran mengeluh selama bertahun-tahun bahwa mereka tidak memahami kemungkinan penutupan fungsi penggunaan dalam pemrograman yang efisien di masa depan. Kemudian revolusi `pemrograman berorientasi objek 'terjadi, dan sekarang semua program menggunakan penutupan fungsi, kecuali bahwa mereka masih menolak untuk menyebutnya demikian.

Di C Anda tidak bisa mendefinisikan fungsi sebaris, jadi Anda tidak bisa benar-benar membuat penutupan. Yang Anda lakukan hanyalah membagikan referensi ke beberapa metode yang telah ditentukan sebelumnya. Dalam bahasa yang mendukung metode / penutupan anonim, definisi metode jauh lebih fleksibel.

Dalam istilah yang paling sederhana, pointer fungsi tidak memiliki cakupan yang terkait dengannya (kecuali Anda menghitung cakupan global), sedangkan closure menyertakan cakupan metode yang mendefinisikannya. Dengan lambda, Anda dapat menulis metode yang menulis metode. Closure memungkinkan Anda mengikat "beberapa argumen ke suatu fungsi dan mendapatkan fungsi dengan aritas rendah sebagai hasilnya". (diambil dari komentar Thomas). Anda tidak dapat melakukan itu di C.

EDIT: Menambahkan contoh (Saya akan menggunakan sintaks Actionscript-ish karena itulah yang ada di pikiran saya saat ini):

Katakanlah Anda memiliki beberapa metode yang menggunakan metode lain sebagai argumennya, tetapi tidak menyediakan cara untuk meneruskan parameter apa pun ke metode itu saat dipanggil? Seperti, katakanlah, beberapa metode yang menyebabkan penundaan sebelum menjalankan metode yang Anda lewati (contoh bodoh, tapi saya ingin membuatnya tetap sederhana).

function runLater(f:Function):Void {
  sleep(100);
  f();
}

Sekarang katakanlah Anda ingin menggunakan runLater () untuk menunda beberapa pemrosesan objek:

function objectProcessor(o:Object):Void {
  /* Do something cool with the object! */
}

function process(o:Object):Void {
  runLater(function() { objectProcessor(o); });
}

Fungsi yang Anda teruskan ke proses () bukan lagi fungsi yang didefinisikan secara statis. Ini dibuat secara dinamis, dan dapat menyertakan referensi ke variabel yang ada dalam cakupan saat metode itu ditentukan. Jadi, ia dapat mengakses 'o' dan 'objectProcessor', meskipun keduanya tidak berada dalam cakupan global.

Saya harap itu masuk akal.

Penutupan = logika + lingkungan.

Misalnya, pertimbangkan metode C # 3 ini:

public Person FindPerson(IEnumerable<Person> people, string name)
{
    return people.Where(person => person.Name == name);
}

Ekspresi lambda tidak hanya merangkum logika ("bandingkan nama") tetapi juga lingkungan, termasuk parameter (yaitu variabel lokal) "nama".

Untuk lebih lanjut tentang ini, lihat artikel saya tentang closure yang membawa Anda melalui C # 1, 2 dan 3, menunjukkan bagaimana closure membuat segalanya lebih mudah.

Di C, pointer fungsi bisa diteruskan sebagai argumen ke fungsi dan dikembalikan sebagai nilai dari fungsi, tetapi fungsi hanya ada di tingkat atas: Anda tidak bisa menumpuk definisi fungsi di dalam satu sama lain. Pikirkan tentang apa yang diperlukan C untuk mendukung fungsi bertingkat yang dapat mengakses variabel dari fungsi luar, sambil tetap dapat mengirim pointer fungsi ke atas dan ke bawah tumpukan panggilan. (Untuk mengikuti penjelasan ini, Anda harus mengetahui dasar-dasar bagaimana panggilan fungsi diimplementasikan dalam C dan bahasa yang paling mirip: telusuri entri tumpukan panggilan di Wikipedia.)

Jenis objek apa yang merupakan penunjuk ke fungsi bersarang? Itu tidak bisa hanya menjadi alamat kode, karena jika Anda memanggilnya, bagaimana cara mengakses variabel dari fungsi luar? (Ingat bahwa karena rekursi, mungkin ada beberapa panggilan berbeda dari fungsi luar yang aktif pada satu waktu.) Ini disebut masalah funarg , dan ada dua submasalah: masalah funarg ke bawah dan masalah funarg ke atas.

Masalah funarg ke bawah, yaitu, mengirim penunjuk fungsi "ke bawah tumpukan" sebagai argumen ke fungsi yang Anda panggil, sebenarnya tidak kompatibel dengan C, dan GCC mendukung fungsi bertingkat sebagai funarg ke bawah. Di GCC, saat Anda membuat penunjuk ke fungsi bersarang, Anda benar-benar mendapatkan penunjuk ke trampolin , bagian kode yang dibuat secara dinamis yang menyiapkan penunjuk tautan statis dan kemudian memanggil fungsi sebenarnya, yang menggunakan penunjuk tautan statis untuk mengakses variabel dari fungsi luar.

Masalah funarg ke atas lebih sulit. GCC tidak mencegah Anda membiarkan penunjuk trampolin ada setelah fungsi luar tidak lagi aktif (tidak memiliki catatan di tumpukan panggilan), kemudian penunjuk tautan statis dapat mengarah ke sampah. Rekaman aktivasi tidak lagi dapat dialokasikan di tumpukan. Solusi yang biasa adalah mengalokasikannya di heap, dan biarkan objek fungsi yang mewakili fungsi bertingkat menunjuk ke rekaman aktivasi dari fungsi luar. Objek seperti itu disebut penutupan . Kemudian bahasa tersebut biasanya harus mendukung pengumpulan sampah sehingga catatan dapat dibebaskan setelah tidak ada lagi petunjuk yang mengarah ke sana.

Lambdas ( fungsi anonim ) benar-benar merupakan masalah terpisah, tetapi biasanya bahasa yang memungkinkan Anda menentukan fungsi anonim dengan cepat juga akan memungkinkan Anda mengembalikannya sebagai nilai fungsi, sehingga akhirnya menjadi closure.

Lambda adalah fungsi anonim, yang didefinisikan secara dinamis . Anda tidak bisa melakukan itu di C ... seperti untuk closure (atau konvinasi dari keduanya), contoh cadel akan terlihat seperti berikut:

(defun get-counter (n-start +-number)
     "Returns a function that returns a number incremented
      by +-number every time it is called"
    (lambda () (setf n-start (+ +-number n-start))))

Dalam istilah C, Anda dapat mengatakan bahwa lingkungan leksikal (tumpukan) get-counterditangkap oleh fungsi anonim, dan dimodifikasi secara internal seperti yang ditunjukkan contoh berikut:

[1]> (defun get-counter (n-start +-number)
         "Returns a function that returns a number incremented
          by +-number every time it is called"
        (lambda () (setf n-start (+ +-number n-start))))
GET-COUNTER
[2]> (defvar x (get-counter 2 3))
X
[3]> (funcall x)
5
[4]> (funcall x)
8
[5]> (funcall x)
11
[6]> (funcall x)
14
[7]> (funcall x)
17
[8]> (funcall x)
20
[9]> 

Penutupan menyiratkan beberapa variabel dari titik definisi fungsi terikat bersama dengan logika fungsi, seperti dapat mendeklarasikan objek mini dengan cepat.

Satu masalah penting dengan C dan closure adalah variabel yang dialokasikan pada stack akan dihancurkan saat meninggalkan cakupan saat ini, terlepas dari apakah closure mengarah ke mereka. Ini akan mengarah pada jenis bug yang didapat orang ketika mereka dengan sembarangan mengembalikan pointer ke variabel lokal. Penutupan pada dasarnya menyiratkan bahwa semua variabel yang relevan dihitung ulang atau item yang dikumpulkan sampah di heap.

Saya tidak nyaman menyamakan lambda dengan closure karena saya tidak yakin bahwa lambda dalam semua bahasa adalah closure, terkadang saya pikir lambda baru saja didefinisikan secara lokal sebagai fungsi anonim tanpa pengikatan variabel (Python pre 2.1?).

Di GCC, dimungkinkan untuk mensimulasikan fungsi lambda menggunakan makro berikut:

#define lambda(l_ret_type, l_arguments, l_body)       \
({                                                    \
    l_ret_type l_anonymous_functions_name l_arguments \
    l_body                                            \
    &l_anonymous_functions_name;                      \
})

Contoh dari sumber :

qsort (array, sizeof (array) / sizeof (array[0]), sizeof (array[0]),
     lambda (int, (const void *a, const void *b),
             {
               dump ();
               printf ("Comparison %d: %d and %d\n",
                       ++ comparison, *(const int *) a, *(const int *) b);
               return *(const int *) a - *(const int *) b;
             }));

Menggunakan teknik ini tentu saja menghilangkan kemungkinan aplikasi Anda bekerja dengan kompiler lain dan tampaknya perilaku "tidak ditentukan" jadi YMMV.

The penutupan menangkap variabel bebas dalam lingkungan . Lingkungan akan tetap ada, meskipun kode di sekitarnya mungkin tidak lagi aktif.

Contoh di Common Lisp, di mana MAKE-ADDERmengembalikan penutupan baru.

CL-USER 53 > (defun make-adder (start delta) (lambda () (incf start delta)))
MAKE-ADDER

CL-USER 54 > (compile *)
MAKE-ADDER
NIL
NIL

Menggunakan fungsi di atas:

CL-USER 55 > (let ((adder1 (make-adder 0 10))
                   (adder2 (make-adder 17 20)))
               (print (funcall adder1))
               (print (funcall adder1))
               (print (funcall adder1))
               (print (funcall adder1))
               (print (funcall adder2))
               (print (funcall adder2))
               (print (funcall adder2))
               (print (funcall adder1))
               (print (funcall adder1))
               (describe adder1)
               (describe adder2)
               (values))

10 
20 
30 
40 
37 
57 
77 
50 
60 
#<Closure 1 subfunction of MAKE-ADDER 4060001ED4> is a CLOSURE
Function         #<Function 1 subfunction of MAKE-ADDER 4060001CAC>
Environment      #(60 10)
#<Closure 1 subfunction of MAKE-ADDER 4060001EFC> is a CLOSURE
Function         #<Function 1 subfunction of MAKE-ADDER 4060001CAC>
Environment      #(77 20)

Perhatikan bahwa DESCRIBEfungsi tersebut menunjukkan bahwa objek fungsi untuk kedua closure adalah sama, tetapi lingkungannya berbeda.

Common Lisp membuat closure dan objek fungsi murni (yang tidak memiliki lingkungan) keduanya menjadi fungsi dan seseorang dapat memanggil keduanya dengan cara yang sama, disini menggunakan FUNCALL.

Perbedaan utama muncul dari kurangnya cakupan leksikal dalam C.

Fungsi penunjuk hanya itu, penunjuk ke blok kode. Variabel non-stack yang direferensikan bersifat global, statis, atau serupa.

Sebuah closure, OTOH, memiliki statusnya sendiri dalam bentuk 'variabel luar', atau 'nilai naik'. mereka bisa menjadi pribadi atau dibagikan sesuai keinginan Anda, menggunakan lexical scoping. Anda dapat membuat banyak penutupan dengan kode fungsi yang sama, tetapi contoh variabel yang berbeda.

Beberapa closure dapat membagi beberapa variabel, dan juga bisa menjadi antarmuka dari sebuah objek (dalam pengertian OOP). untuk membuatnya di C Anda harus mengaitkan struktur dengan tabel pointer fungsi (itulah yang dilakukan C ++, dengan kelas vtable).

singkatnya, closure adalah fungsi penunjuk PLUS beberapa keadaan. itu adalah konstruksi tingkat yang lebih tinggi

Sebagian besar respons menunjukkan bahwa closure memerlukan penunjuk fungsi, mungkin ke fungsi anonim, tetapi seperti yang ditulis Mark, closure bisa ada dengan fungsi bernama. Berikut adalah contoh di Perl:

{
    my $count;
    sub increment { return $count++ }
}

Closure adalah lingkungan yang mendefinisikan $countvariabel. Ini hanya tersedia untuk incrementsubrutin dan tetap ada di antara panggilan.

Di C, penunjuk fungsi adalah penunjuk yang akan memanggil fungsi saat Anda mendereferensi, closure adalah nilai yang berisi logika fungsi dan lingkungan (variabel dan nilai yang mengikatnya) dan lambda biasanya merujuk ke nilai yang sebenarnya adalah fungsi yang tidak disebutkan namanya. Di C, sebuah fungsi bukanlah nilai kelas satu sehingga tidak dapat diedarkan sehingga Anda harus meneruskan pointer ke sana, namun dalam bahasa fungsional (seperti Skema) Anda dapat meneruskan fungsi dengan cara yang sama seperti Anda meneruskan nilai lainnya.