Arti "posisi positif" dan "posisi negatif" dalam teori tipe?

10

Apa arti "dalam posisi positif" dan "dalam posisi negatif" dalam konteks teori tipe?

Satu-satunya hal yang saya mengerti dari posting blog Bob Harper pada topik adalah bahwa ada hubungan antara polaritas dalam pengertian ini dalam teori tipe dan polaritas dalam logika, tetapi saya tidak tahu apa hubungan itu.

type-theory Robin Green
sumber

Jawaban:

9

Sayangnya "polaritas" adalah konsep yang agak kelebihan dalam teori tipe. "Posisi positif" dan "posisi negatif" merujuk pada gagasan polaritas yang berbeda dari yang dibicarakan Bob dengan fokus / polarisasi.

Makna Anda

Saat Anda mendefinisikan jenis induktif Anda memberikan serangkaian aturan yang sesuai dengan operasi untuk jenis yang Anda tetapkan. Misalnya Anda mungkin mengatakan Natsesuatu dengan

  • sebuah nilai zero : Nat
  • sebuah fungsi suc : Nat -> Nat

Dan kemudian berharap itu Natberisi semua nilai yang dapat dihasilkan dari penerapan berulang kali sucke yang lain Natdan termasuk zero. Sejalan dengan konstruksi induktif ini kita mendapatkan prinsip rekursi Natyang bekerja berdasarkan fakta bahwa ada Natyang dihasilkan oleh konstruktor tersebut.

rec : A -> (A -> A) -> Nat -> A

maka

rec Z S zero = zero
rec Z S (suc n) = S (rec Z S n)

Namun, ada beberapa batasan pada apa yang bisa kita tulis sebagai aturan. Kalau tidak, kita bisa menulis serangkaian aturan yang prinsip rekursi tidak bisa dibenarkan. Pertimbangkan "tipe induktif" Ddengan satu konstruktor

  • d : (D -> D) -> D

Di sini tidak ada prinsip rekursi yang waras di sini. dan untuk alasan yang bagus! Jika kita memiliki beberapa prinsip rekursi, kita dapat menggunakannya untuk menyandikan versi aplikasi diri dan dengannya, nonterminasi. Ini berarti Dtidak dapat disebut "induktif" karena tipe induktif adalah konstruksi terbatas yang dihasilkan dari penerapan konstruktor berulang kali!

Untuk mengatasi ini, kami membatasi bagaimana tipe induktif dapat bersifat rekursif dalam teori tipe. Secara khusus, kami menghentikan mereka agar tidak muncul di "tempat negatif". Ini adalah gagasan tentang polaritas yang sedang Anda bicarakan. Polaritas suatu posisi ditentukan dengan demikian,

  1. Argumen dimulai pada posisi positif
  2. Setiap kali kita pergi ke kiri panah, polaritasnya terbalik

Jadi Xpositif di dua yang pertama dan negatif di dua yang kedua

X
Int -> X
X -> Int
(Unit -> X) -> Int

Gagasan ini dibenarkan dengan bantuan teori kategori di mana tipe induktif dengan satu-satunya rekurensi yang positif menimbulkan fungsi kovarian. Rincian cara kerjanya dan mengapa ini menarik agak lama.

Arti Bob Harper

Di blogpost-nya Harper berbicara tentang arti polaritas yang berbeda. Polaritas ini merujuk pada bagaimana berbagai penghubung dalam logika diberi makna. Secara khusus, kita dapat mengklasifikasikan konektivitas dalam dua cara

  • Penghubung positif dapat didefinisikan dengan mendefinisikan cara memperkenalkan mereka (aturan pengenalan mereka)
  • Konektif negatif dapat didefinisikan dengan mendefinisikan cara menggunakannya (aturan eliminasi mereka)

Dalam istilah bahasa pemrograman, ini dengan baik menangkap perbedaan antara tipe malas dan ketat. Tipe ketat ditentukan oleh nilainya. Yang malas didefinisikan oleh bagaimana pola dapat cocok dengan mereka. Untuk menangani ini dengan benar, kami mendefinisikan bahasa dengan 2 konstruksi utama, cara untuk membangun tipe positif dan "duri" untuk menguraikan jenis negatif. Kita dapat menggunakan ini untuk memasukkan perhitungan yang ketat dan malas ke dalam satu bahasa.

Untuk memahami ini lebih baik, saya merujuk Anda ke bab 38 dari buku Bob Harper .

Daniel Gratzer
sumber
Maaf, @ jozefg, saya mengerti konsepnya tetapi saya tidak mengerti bagaimana melihat apakah suatu tipe hanya muncul di posisi positif. Bisakah Anda menentukan lebih banyak, dan memberikan beberapa contoh lagi?
paulotorrens