Apa jenis eksistensial?

Saya membaca artikel Wikipedia jenis Eksistensial . Saya mengetahui bahwa mereka disebut tipe eksistensial karena operator eksistensial (∃). Saya tidak yakin apa gunanya itu. Apa bedanya

T = ∃X { X a; int f(X); }

dan

T = ∀x { X a; int f(X); }

?

Ketika seseorang mendefinisikan tipe universal yang ∀Xmereka katakan: Anda dapat memasukkan tipe apa pun yang Anda inginkan, saya tidak perlu tahu apa-apa tentang tipe itu untuk melakukan pekerjaan saya, saya hanya akan merujuknya secara tidak jelasX .

Ketika seseorang mendefinisikan tipe eksistensial yang ∃Xmereka katakan: Saya akan menggunakan tipe apa pun yang saya inginkan di sini; Anda tidak akan tahu apa-apa tentang jenisnya, jadi Anda hanya dapat menyebutnya secara tidak jelasX .

Tipe universal memungkinkan Anda menulis hal-hal seperti:

void copy<T>(List<T> source, List<T> dest) {
   ...
}

The copyFungsi tidak tahu apa Tsebenarnya akan, tetapi tidak perlu.

Jenis eksistensial memungkinkan Anda menulis hal-hal seperti:

interface VirtualMachine<B> {
   B compile(String source);
   void run(B bytecode);
}

// Now, if you had a list of VMs you wanted to run on the same input:
void runAllCompilers(List<∃B:VirtualMachine<B>> vms, String source) {
   for (∃B:VirtualMachine<B> vm : vms) {
      B bytecode = vm.compile(source);
      vm.run(bytecode);
   }
}

Setiap implementasi mesin virtual dalam daftar dapat memiliki tipe bytecode yang berbeda. The runAllCompilersFungsi tidak tahu apa jenis bytecode, tapi itu tidak perlu; semua yang dilakukannya adalah menyampaikan bytecode dari VirtualMachine.compileke VirtualMachine.run.

Wildcard tipe Java (ex:) List<?>adalah bentuk yang sangat terbatas dari tipe eksistensial.

Pembaruan: Lupa menyebutkan bahwa Anda dapat menyortir jenis eksistensial dengan tipe universal. Pertama, bungkus tipe universal Anda untuk menyembunyikan parameter tipe. Kedua, kontrol terbalik (ini secara efektif menukar bagian "Anda" dan "Saya" dalam definisi di atas, yang merupakan perbedaan utama antara eksistensial dan universal).

// A wrapper that hides the type parameter 'B'
interface VMWrapper {
   void unwrap(VMHandler handler);
}

// A callback (control inversion)
interface VMHandler {
   <B> void handle(VirtualMachine<B> vm);
}

Sekarang kita dapat memiliki VMWrapperpanggilan kita sendiri VMHandleryang memiliki handlefungsi yang diketik secara universal . Efek bersihnya sama, kode kita harus diperlakukan Bsebagai buram.

void runWithAll(List<VMWrapper> vms, final String input)
{
   for (VMWrapper vm : vms) {
      vm.unwrap(new VMHandler() {
         public <B> void handle(VirtualMachine<B> vm) {
            B bytecode = vm.compile(input);
            vm.run(bytecode);
         }
      });
   }
}

Contoh implementasi VM:

class MyVM implements VirtualMachine<byte[]>, VMWrapper {
   public byte[] compile(String input) {
      return null; // TODO: somehow compile the input
   }
   public void run(byte[] bytecode) {
      // TODO: Somehow evaluate 'bytecode'
   }
   public void unwrap(VMHandler handler) {
      handler.handle(this);
   }
}

Nilai sejenis seperti eksistensial ∃x. F(x) adalah pasangan yang mengandung beberapa jenis x dan nilai jenis F(x). Sedangkan nilai sejenis polimorfik ∀x. F(x)adalah fungsi yang mengambil beberapa jenis xdan menghasilkan nilai jenis F(x). Dalam kedua kasus, tipe menutup beberapa konstruktor tipe F.

Perhatikan bahwa tampilan ini memadukan jenis dan nilai. Bukti eksistensial adalah satu jenis dan satu nilai. Bukti universal adalah seluruh keluarga nilai yang diindeks berdasarkan tipe (atau pemetaan dari tipe ke nilai).

Jadi perbedaan antara dua jenis yang Anda tentukan adalah sebagai berikut:

T = ∃X { X a; int f(X); }

Ini berarti: Nilai tipe Tberisi tipe yang disebut X, nilai a:X, dan fungsi f:X->int. Produser nilai tipe Tdapat memilih tipe apa punX dan konsumen tidak dapat mengetahui apa pun tentangnya X. Kecuali bahwa ada satu contoh yang dipanggil adan nilai ini dapat diubah menjadi intdengan memberikannya kepada f. Dengan kata lain, nilai tipe Ttahu cara menghasilkan intentah bagaimana. Yah, kita bisa menghilangkan jenis perantara Xdan hanya mengatakan:

T = int

Yang dikuantifikasi secara universal sedikit berbeda.

T = ∀X { X a; int f(X); }

Ini berarti: Nilai tipe Tdapat diberikan tipe apa pun X, dan itu akan menghasilkan nilai a:X, dan fungsi f:X->int apa pun yang Xada . Dengan kata lain: konsumen nilai tipe Tdapat memilih tipe apa pun X. Dan penghasil nilai tipe Ttidak dapat mengetahui apa pun tentangnya X, tetapi harus dapat menghasilkan nilai auntuk pilihan apa pun X, dan dapat mengubah nilai tersebut menjadi int.

Jelas menerapkan jenis ini tidak mungkin, karena tidak ada program yang dapat menghasilkan nilai dari setiap jenis yang bisa dibayangkan. Kecuali Anda mengizinkan absurditas seperti nullatau pantat.

Karena eksistensial adalah pasangan, argumen eksistensial dapat dikonversi menjadi argumen universal melalui currying .

(∃b. F(b)) -> Int

sama dengan:

∀b. (F(b) -> Int)

Yang pertama adalah eksistensial peringkat-2 . Ini mengarah ke properti bermanfaat berikut:

Setiap jenis peringkat yang terukur secara eksistensial adalah jenis peringkat n+1yang diukur secara universal n.

Ada algoritma standar untuk mengubah eksistensi menjadi universal, yang disebut Skolemization .

Saya pikir masuk akal untuk menjelaskan tipe-tipe eksistensial bersama-sama dengan tipe universal, karena kedua konsep tersebut saling melengkapi, yaitu satu adalah "lawan" dari yang lain.

Saya tidak bisa menjawab setiap detail tentang tipe eksistensial (seperti memberikan definisi yang tepat, daftar semua kemungkinan penggunaan, hubungannya dengan tipe data abstrak, dll.) Karena saya tidak cukup berpengetahuan untuk itu. Saya hanya akan menunjukkan (menggunakan Java) apa yang dinyatakan oleh artikel HaskellWiki ini sebagai efek utama dari tipe eksistensial:

Jenis eksistensial dapat digunakan untuk beberapa tujuan berbeda. Tetapi apa yang mereka lakukan adalah 'menyembunyikan' variabel tipe di sisi kanan. Biasanya, semua jenis variabel yang muncul di sebelah kanan juga harus muncul di sebelah kiri [...]

Pengaturan contoh:

Pseudo-code berikut ini bukan Java yang cukup valid, meskipun akan cukup mudah untuk memperbaikinya. Sebenarnya, itulah tepatnya yang akan saya lakukan dalam jawaban ini!

class Tree<α>
{
    α       value;
    Tree<α> left;
    Tree<α> right;
}

int height(Tree<α> t)
{
    return (t != null)  ?  1 + max( height(t.left), height(t.right) )
                        :  0;
}

Biarkan saya menguraikan ini secara singkat untuk Anda. Kami mendefinisikan ...

• tipe rekursif Tree<α>yang mewakili node dalam pohon biner. Setiap node menyimpan a valuedari beberapa tipe α dan memiliki referensi ke opsional leftdan rightsubtree dari tipe yang sama.

• fungsi heightyang mengembalikan jarak terjauh dari simpul daun ke simpul akar t.

Sekarang, mari kita ubah pseudo-code di atas heightmenjadi sintaksis Java yang tepat! (Saya akan terus menghilangkan beberapa pelat ketel untuk kepentingan singkatnya, seperti pengubah orientasi objek dan aksesibilitas.) Saya akan menunjukkan dua solusi yang mungkin.

1. Solusi tipe universal:

Perbaikan yang paling jelas adalah dengan membuat heightgenerik dengan memasukkan parameter tipe α ke dalam tanda tangannya:

<α> int height(Tree<α> t)
{
    return (t != null)  ?  1 + max( height(t.left), height(t.right) )
                        :  0;
}

Ini akan memungkinkan Anda untuk mendeklarasikan variabel dan membuat ekspresi tipe α di dalam fungsi itu, jika Anda mau. Tapi...

2. Solusi tipe eksistensial:

Jika Anda melihat tubuh metode kami, Anda akan melihat bahwa kami tidak benar-benar mengakses, atau bekerja dengan, apa pun dari tipe α ! Tidak ada ekspresi yang memiliki tipe itu, juga tidak ada variabel yang dideklarasikan dengan tipe itu ... jadi, mengapa kita harus membuat heightgenerik sama sekali? Mengapa kita tidak bisa melupakan α saja ? Ternyata, kita dapat:

int height(Tree<?> t)
{
    return (t != null)  ?  1 + max( height(t.left), height(t.right) )
                        :  0;
}

Seperti yang saya tulis di awal jawaban ini, tipe eksistensial dan universal bersifat komplementer / ganda. Jadi, jika solusi tipe universal adalah membuat height lebih umum, maka kita harus berharap bahwa tipe eksistensial memiliki efek sebaliknya: menjadikannya kurang generik, yaitu dengan menyembunyikan / menghapus parameter tipe α .

Sebagai konsekuensinya, Anda tidak bisa lagi merujuk pada tipe t.valuedalam metode ini atau memanipulasi ekspresi apa pun dari tipe itu, karena tidak ada pengidentifikasi yang terikat padanya. ( ?Wildcard adalah token khusus, bukan pengenal yang "menangkap" suatu tipe.) Secara t.valueefektif menjadi buram; mungkin satu-satunya hal yang masih bisa Anda lakukan adalah mengetikkannya Object.

Ringkasan:

===========================================================
                     |    universally       existentially
                     |  quantified type    quantified type
---------------------+-------------------------------------
 calling method      |                  
 needs to know       |        yes                no
 the type argument   |                 
---------------------+-------------------------------------
 called method       |                  
 can use / refer to  |        yes                no  
 the type argument   |                  
=====================+=====================================

Ini semua adalah contoh yang baik, tetapi saya memilih untuk menjawabnya sedikit berbeda. Ingat dari matematika, ∀x itu. P (x) berarti "untuk semua x, saya dapat membuktikan bahwa P (x)". Dengan kata lain, ini adalah semacam fungsi, Anda memberi saya x dan saya punya metode untuk membuktikannya untuk Anda.

Dalam teori tipe, kita tidak berbicara tentang bukti, tetapi tentang tipe. Jadi dalam ruang ini yang kami maksud "untuk semua tipe X yang Anda berikan kepada saya, saya akan memberikan Anda tipe P tertentu". Sekarang, karena kami tidak memberikan P banyak informasi tentang X selain fakta bahwa itu adalah tipe, P tidak bisa berbuat banyak dengannya, tetapi ada beberapa contoh. P dapat membuat jenis "semua pasangan dari jenis yang sama": P<X> = Pair<X, X> = (X, X). Atau kita dapat membuat jenis opsi P<X> = Option<X> = X | Nil:, di mana Nil adalah jenis pointer nol. Kita bisa membuat daftar dari itu: List<X> = (X, List<X>) | Nil. Perhatikan bahwa yang terakhir adalah rekursif, nilai-nilai List<X>adalah pasangan mana elemen pertama adalah X dan elemen kedua adalah a List<X>atau yang lain itu adalah pointer nol.

Sekarang, dalam matematika ∃x. P (x) berarti "Saya dapat membuktikan bahwa ada x tertentu sehingga P (x) benar". Mungkin ada banyak x, tetapi untuk membuktikannya, satu sudah cukup. Cara lain untuk memikirkannya adalah bahwa harus ada set pasangan bukti-dan-bukti yang tidak kosong {(x, P (x))}.

Diterjemahkan ke teori tipe: Tipe dalam keluarga ∃X.P<X>adalah tipe X dan tipe yang sesuai P<X>. Perhatikan bahwa ketika sebelum kita memberikan X ke P, (sehingga kita tahu segalanya tentang X tetapi sangat sedikit P) bahwa kebalikannya benar sekarang. P<X>tidak berjanji untuk memberikan informasi apa pun tentang X, hanya ada satu, dan itu memang tipe.

Bagaimana ini berguna? Nah, P bisa menjadi tipe yang memiliki cara mengekspos tipe internal X. Contohnya adalah objek yang menyembunyikan representasi internal negara X. Meskipun kita tidak memiliki cara memanipulasi secara langsung, kita dapat mengamati efeknya dengan menyodok di P. Mungkin ada banyak implementasi jenis ini, tetapi Anda bisa menggunakan semua jenis ini tidak peduli mana yang dipilih.

Untuk langsung menjawab pertanyaan Anda:

Dengan tipe universal, penggunaan Tharus menyertakan parameter tipe X. Misalnya T<String>atau T<Integer>. Untuk penggunaan tipe eksistensial Tjangan sertakan parameter tipe itu karena tidak diketahui atau tidak relevan - cukup gunakan T(atau di Jawa T<?>).

Informasi lebih lanjut:

Tipe universal / abstrak dan tipe eksistensial adalah dualitas perspektif antara konsumen / klien dari suatu objek / fungsi dan produsen / implementasi itu. Ketika satu sisi melihat tipe universal, yang lain melihat tipe eksistensial.

Di Jawa, Anda dapat menentukan kelas generik:

public class MyClass<T> {
   // T is existential in here
   T whatever; 
   public MyClass(T w) { this.whatever = w; }

   public static MyClass<?> secretMessage() { return new MyClass("bazzlebleeb"); }
}

// T is universal from out here
MyClass<String> mc1 = new MyClass("foo");
MyClass<Integer> mc2 = new MyClass(123);
MyClass<?> mc3 = MyClass.secretMessage();

• Dari perspektif klien dari MyClass, Tadalah universal karena Anda dapat mengganti jenis untuk Tketika Anda menggunakan kelas itu dan Anda harus mengetahui jenis sebenarnya dari T setiap kali Anda menggunakan sebuah instance dariMyClass
• Dari perspektif metode instance MyClassitu sendiri, Teksistensial karena tidak tahu jenis sebenarnyaT
• Di Jawa, ?mewakili tipe eksistensial - jadi ketika Anda berada di dalam kelas, Tpada dasarnya ?. Jika Anda ingin menangani instance MyClassdengan Texistential, Anda dapat mendeklarasikan MyClass<?>seperti pada secretMessage()contoh di atas.

Jenis eksistensial kadang-kadang digunakan untuk menyembunyikan detail implementasi sesuatu, seperti yang dibahas di tempat lain. Versi Java ini mungkin terlihat seperti:

public class ToDraw<T> {
    T obj;
    Function<Pair<T,Graphics>, Void> draw;
    ToDraw(T obj, Function<Pair<T,Graphics>, Void>
    static void draw(ToDraw<?> d, Graphics g) { d.draw.apply(new Pair(d.obj, g)); }
}

// Now you can put these in a list and draw them like so:
List<ToDraw<?>> drawList = ... ;
for(td in drawList) ToDraw.draw(td);

Agak sulit untuk menangkap ini dengan benar karena saya berpura-pura berada dalam semacam bahasa pemrograman fungsional, yang Java tidak. Tetapi intinya di sini adalah bahwa Anda menangkap semacam negara ditambah daftar fungsi yang beroperasi pada negara itu dan Anda tidak tahu jenis sebenarnya dari bagian negara, tetapi fungsi lakukan karena mereka sudah cocok dengan jenis yang sudah .

Sekarang, di Jawa semua tipe non-primitif non-final sebagian eksistensial. Ini mungkin terdengar aneh, tetapi karena variabel yang dinyatakan Objectberpotensi menjadi subkelas Object, Anda tidak dapat mendeklarasikan tipe spesifik, hanya "tipe ini atau subkelas". Jadi, objek direpresentasikan sebagai sedikit status ditambah daftar fungsi yang beroperasi pada kondisi tersebut - fungsi mana yang akan dipanggil ditentukan saat runtime oleh pencarian. Ini sangat mirip dengan penggunaan tipe eksistensial di atas di mana Anda memiliki bagian kondisi eksistensial dan fungsi yang beroperasi pada kondisi itu.

Dalam bahasa pemrograman yang diketik secara statis tanpa subtyping dan gips, tipe eksistensial memungkinkan seseorang untuk mengelola daftar objek yang diketik berbeda. Daftar T<Int>tidak dapat berisi a T<Long>. Namun, daftar T<?>dapat berisi variasi apa pun T, yang memungkinkan seseorang untuk memasukkan berbagai jenis data ke dalam daftar dan mengubahnya semuanya menjadi int (atau melakukan operasi apa pun yang disediakan di dalam struktur data) sesuai permintaan.

Seseorang dapat hampir selalu mengubah catatan dengan tipe eksistensial menjadi catatan tanpa menggunakan penutupan. Penutupan juga diketik secara eksistensial, karena variabel bebas yang ditutupinya disembunyikan dari pemanggil. Dengan demikian bahasa yang mendukung penutupan tetapi bukan tipe eksistensial dapat memungkinkan Anda untuk membuat penutupan yang berbagi keadaan tersembunyi yang sama dengan yang Anda masukkan ke bagian eksistensial suatu objek.

Jenis eksistensial adalah jenis buram.

Pikirkan pegangan file di Unix. Anda tahu tipenya int, sehingga Anda dapat dengan mudah memalsunya. Anda dapat, misalnya, mencoba membaca dari pegangan 43. Jika kebetulan program memiliki file terbuka dengan pegangan khusus ini, Anda akan membacanya. Kode Anda tidak harus berbahaya, cukup ceroboh (mis., Pegangan bisa menjadi variabel yang tidak diinisialisasi).

Jenis eksistensial disembunyikan dari program Anda. Jika fopenmengembalikan tipe eksistensial, yang bisa Anda lakukan dengannya adalah menggunakannya dengan beberapa fungsi pustaka yang menerima tipe eksistensial ini. Sebagai contoh, pseudo-code berikut akan dikompilasi:

let exfile = fopen("foo.txt"); // No type for exfile!
read(exfile, buf, size);

Antarmuka "baca" dinyatakan sebagai:

Ada tipe T sedemikian rupa sehingga:

size_t read(T exfile, char* buf, size_t size);

Exfile variabel bukan int, bukan a char*, bukan File struct — tidak ada yang dapat Anda ekspresikan dalam sistem tipe. Anda tidak bisa mendeklarasikan variabel yang tipenya tidak diketahui dan Anda tidak bisa melemparkan, katakanlah, sebuah pointer ke tipe yang tidak dikenal itu. Bahasa tidak akan membiarkan Anda.

Sepertinya saya datang agak terlambat, tetapi bagaimanapun, dokumen ini menambahkan pandangan lain tentang apa tipe-tipe eksistensial, walaupun tidak secara khusus agnostik-bahasa, seharusnya lebih mudah untuk memahami tipe-tipe eksistensial: http: //www.cs.uu .nl / groups / ST / Proyek / ehc / ehc-book.pdf (bab 8)

Perbedaan antara tipe terkuantifikasi secara universal dan eksistensial dapat dikarakteristikkan dengan pengamatan berikut:

• Penggunaan nilai dengan tipe ∀ kuantitatif menentukan tipe yang akan dipilih untuk instantiasi variabel tipe terkuantifikasi. Misalnya, penelepon fungsi identitas "id :: ∀aa → a" menentukan tipe yang akan dipilih untuk variabel tipe a untuk aplikasi id tertentu ini. Untuk aplikasi fungsi "id 3" jenis ini sama dengan Int.

• Penciptaan nilai dengan tipe ∃ terkuantifikasi menentukan, dan menyembunyikan, tipe variabel tipe terkuantifikasi. Misalnya, pencipta "∃a. (A, a → Int)" mungkin telah membangun nilai jenis itu dari "(3, λx → x)"; pembuat lain telah membuat nilai dengan tipe yang sama dari “('x', λx → ord x)”. Dari sudut pandang pengguna, kedua nilai memiliki tipe yang sama dan karenanya dapat dipertukarkan. Nilai memiliki tipe spesifik yang dipilih untuk variabel tipe a, tetapi kami tidak tahu tipe mana, sehingga informasi ini tidak dapat lagi dieksploitasi. Informasi tipe spesifik nilai ini telah 'dilupakan'; kita hanya tahu itu ada.

Tipe universal ada untuk semua nilai parameter tipe (s). Tipe eksistensial hanya ada untuk nilai parameter tipe yang memenuhi batasan tipe eksistensial.

Sebagai contoh dalam Scala salah satu cara untuk mengekspresikan tipe eksistensial adalah tipe abstrak yang dibatasi pada beberapa batas atas atau bawah.

trait Existential {
  type Parameter <: Interface
}

Secara ekuivalen tipe universal yang dibatasi adalah tipe eksistensial seperti pada contoh berikut.

trait Existential[Parameter <: Interface]

Setiap situs penggunaan dapat menggunakan Interfacekarena setiap subtipe instantiable Existentialharus mendefinisikan type Parameteryang harus menerapkan Interface.

Sebuah kasus degenerasi dari jenis eksistensial di Scala adalah tipe abstrak yang tidak pernah disebut dan dengan demikian tidak perlu didefinisikan oleh subtipe apapun. Ini secara efektif memiliki notasi singkatan List[_] di Scala dan List<?>di Jawa.

Jawaban saya terinspirasi oleh proposal Martin Odersky untuk menyatukan tipe abstrak dan eksistensial. Alat bantu slide yang menyertainya memahami.

Penelitian terhadap tipe data abstrak dan penyembunyian informasi membawa tipe eksistensial ke dalam bahasa pemrograman. Membuat abstrak tipe data menyembunyikan informasi tentang jenis itu, jadi klien jenis itu tidak dapat menyalahgunakannya. Katakanlah Anda memiliki referensi ke suatu objek ... beberapa bahasa memungkinkan Anda untuk memberikan referensi itu ke referensi ke byte dan melakukan apa pun yang Anda inginkan pada sepotong memori itu. Untuk tujuan menjamin perilaku suatu program, berguna bagi suatu bahasa untuk memastikan bahwa Anda hanya bertindak berdasarkan referensi ke objek melalui metode yang disediakan oleh perancang objek tersebut. Anda tahu jenisnya ada, tetapi tidak lebih.

Lihat:

Tipe Abstrak Memiliki Tipe Eksistensial, MITCHEL & PLOTKIN

http://theory.stanford.edu/~jcm/papers/mitch-plotkin-88.pdf

Saya membuat diagram ini. Saya tidak tahu apakah ini keras. Tetapi jika itu membantu, saya senang.

Seperti yang saya mengerti itu adalah cara matematika untuk menggambarkan antarmuka / kelas abstrak.

Adapun T = ∃X {X a; int f (X); }

Untuk C # itu akan menerjemahkan ke tipe abstrak umum:

abstract class MyType<T>{
    private T a;

    public abstract int f(T x);
}

"Eksistensial" hanya berarti bahwa ada beberapa jenis yang mematuhi aturan yang ditetapkan di sini.