Apa padanan logika kombinasi dari teori tipe intuitionistic?

87

Saya baru-baru ini menyelesaikan kursus universitas yang menampilkan Haskell dan Agda (bahasa pemrograman fungsional jenis dependen), dan bertanya-tanya apakah mungkin untuk mengganti kalkulus lambda dengan logika kombinatori. Dengan Haskell ini tampaknya mungkin menggunakan kombinator S dan K, sehingga membuatnya bebas poin. Saya bertanya-tanya apa padanannya untuk Agda. Yaitu, dapatkah seseorang membuat bahasa pemrograman fungsional yang diketik secara dependen setara dengan Agda tanpa menggunakan variabel apa pun?

Juga, apakah mungkin untuk mengganti kuantifikasi dengan kombinator? Saya tidak tahu apakah ini kebetulan tetapi kuantifikasi universal misalnya membuat tanda tangan tipe terlihat seperti ekspresi lambda. Apakah ada cara untuk menghapus kuantifikasi universal dari tanda tangan tipe tanpa mengubah artinya? Misal dalam:

forall a : Int -> a < 0 -> a + a < a

Bisakah hal yang sama diungkapkan tanpa menggunakan forall?

haskell types functional-programming logic agda grasevski.dll
sumber
21
Mulailah dengan mencari tahu jenis yang paling tergantung untuk K (mudah) dan S (agak berbulu). Menarik untuk memasukkan konstanta untuk Set dan Pi, kemudian mencoba untuk merekonstruksi sistem Set: Set dasar (tidak konsisten). Saya akan berpikir lebih jauh, tapi saya harus mengejar pesawat.
pigworker

Jawaban:

52

Jadi saya memikirkannya sedikit lagi dan membuat beberapa kemajuan. Berikut adalah langkah pertama dalam pengkodean sistem Martin-Löf yang sangat sederhana (tetapi tidak konsisten) Set : Setdalam gaya kombinasi. Ini bukan cara yang baik untuk menyelesaikannya, tetapi ini adalah tempat termudah untuk memulai. Sintaks dari teori tipe ini hanyalah lambda-kalkulus dengan anotasi tipe, tipe-Pi, dan himpunan semesta.

Teori Jenis Target

Demi kelengkapan, saya akan sampaikan aturannya. Validitas konteks hanya mengatakan Anda dapat membangun konteks dari kosong dengan menghubungkan variabel segar yang menempati Sets.

                     G |- valid   G |- S : Set
--------------     ----------------------------- x fresh for G
  . |- valid         G, x:S |- valid

Dan sekarang kita dapat mengatakan bagaimana mensintesis tipe untuk istilah dalam konteks tertentu, dan bagaimana mengubah tipe sesuatu hingga perilaku komputasi dari istilah yang dikandungnya.

  G |- valid             G |- S : Set   G |- T : Pi S \ x:S -> Set
------------------     ---------------------------------------------
  G |- Set : Set         G |- Pi S T : Set

  G |- S : Set   G, x:S |- t : T x         G |- f : Pi S T   G |- s : S
------------------------------------     --------------------------------
  G |- \ x:S -> t : Pi S T                 G |- f s : T s

  G |- valid                  G |- s : S   G |- T : Set
-------------- x:S in G     ----------------------------- S ={beta} T
  G |- x : S                  G |- s : T

Dalam variasi kecil dari aslinya, saya telah menjadikan lambda satu-satunya operator pengikat, jadi argumen kedua Pi harus menjadi fungsi yang menghitung cara tipe pengembalian bergantung pada input. Menurut konvensi (misalnya di Agda, tapi sayangnya tidak di Haskell), cakupan lambda meluas ke kanan sejauh mungkin, jadi Anda sering dapat membiarkan abstraksi tidak dikurung ketika itu adalah argumen terakhir dari operator tingkat tinggi: Anda bisa lihat saya melakukannya itu dengan Pi. Jenis Agda Anda (x : S) -> Tmenjadi Pi S \ x:S -> T.

( Digression . Anotasi jenis pada lambda diperlukan jika Anda ingin dapat mensintesis jenis abstraksi. Jika Anda beralih ke pemeriksaan jenis sebagai modus operandi, Anda masih memerlukan anotasi untuk memeriksa beta-redex seperti (\ x -> t) s, karena Anda tidak punya cara untuk menebak jenis bagian dari keseluruhan. Saya menyarankan perancang modern untuk memeriksa jenis dan mengecualikan beta-redex dari sintaks.)

( Digresi . Sistem ini tidak konsisten karena Set:Setmemungkinkan pengkodean berbagai "paradoks pembohong". Ketika Martin-Löf mengajukan teori ini, Girard mengiriminya pengkodeannya dalam Sistem U miliknya yang tidak konsisten. Paradoks berikutnya yang disebabkan oleh Hurkens adalah konstruksi beracun paling rapi yang kita tahu.)

Sintaks dan Normalisasi Kombinator

Bagaimanapun, kami memiliki dua simbol tambahan, Pi dan Set, jadi kami mungkin mengelola terjemahan kombinasi dengan S, K dan dua simbol tambahan: Saya memilih U untuk alam semesta dan P untuk produk.

Sekarang kita dapat mendefinisikan sintaks kombinatori tanpa tipe (dengan variabel bebas):

data SKUP = S | K | U | P deriving (Show, Eq)

data Unty a
  = C SKUP
  | Unty a :. Unty a
  | V a
  deriving (Functor, Eq)
infixl 4 :.

Perhatikan bahwa saya telah menyertakan sarana untuk memasukkan variabel bebas yang diwakili oleh tipe adalam sintaks ini. Selain sebagai refleks di pihak saya (setiap sintaks yang sesuai dengan namanya adalah monad gratis dengan returnvariabel embedding dan >>=substitusi perfoming), akan berguna untuk mewakili tahap perantara dalam proses mengubah istilah dengan mengikat ke bentuk kombinasinya.

Berikut normalisasi:

norm :: Unty a -> Unty a
norm (f :. a)  = norm f $. a
norm c         = c

($.) :: Unty a -> Unty a -> Unty a        -- requires first arg in normal form
C S :. f :. a $. g  = f $. g $. (a :. g)  -- S f a g = f g (a g)   share environment
C K :. a $. g       = a                   -- K a g = a             drop environment
n $. g              = n :. norm g         -- guarantees output in normal form
infixl 4 $.

(Latihan bagi pembaca adalah untuk menentukan tipe untuk persis bentuk normal dan mempertajam tipe operasi ini.)

Mewakili Teori Jenis

Sekarang kita dapat mendefinisikan sintaks untuk teori tipe kita.

data Tm a
  = Var a
  | Lam (Tm a) (Tm (Su a))    -- Lam is the only place where binding happens
  | Tm a :$ Tm a
  | Pi (Tm a) (Tm a)          -- the second arg of Pi is a function computing a Set
  | Set
  deriving (Show, Functor)
infixl 4 :$

data Ze
magic :: Ze -> a
magic x = x `seq` error "Tragic!"

data Su a = Ze | Su a deriving (Show, Functor, Eq)

Saya menggunakan representasi indeks de Bruijn dengan cara Bellegarde dan Hook (seperti yang dipopulerkan oleh Bird dan Paterson). Tipe Su amemiliki satu elemen lebih dari a, dan kami menggunakannya sebagai tipe variabel bebas di bawah pengikat, dengan Zesebagai variabel terikat baru dan Su xmerupakan representasi bergeser dari variabel bebas lama x.

Menerjemahkan Istilah ke Kombinator

Dan setelah itu selesai, kami memperoleh terjemahan biasa, berdasarkan abstraksi braket .

tm :: Tm a -> Unty a
tm (Var a)    = V a
tm (Lam _ b)  = bra (tm b)
tm (f :$ a)   = tm f :. tm a
tm (Pi a b)   = C P :. tm a :. tm b
tm Set        = C U

bra :: Unty (Su a) -> Unty a               -- binds a variable, building a function
bra (V Ze)      = C S :. C K :. C K        -- the variable itself yields the identity
bra (V (Su x))  = C K :. V x               -- free variables become constants
bra (C c)       = C K :. C c               -- combinators become constant
bra (f :. a)    = C S :. bra f :. bra a    -- S is exactly lifted application

Mengetik Kombinasi

Terjemahan menunjukkan cara kami menggunakan kombinator, yang memberi kami cukup petunjuk tentang jenis seharusnya. Udan Phanya mengatur konstruktor, jadi, menulis jenis yang tidak diterjemahkan dan mengizinkan "notasi Agda" untuk Pi, kita harus memiliki

U : Set
P : (A : Set) -> (B : (a : A) -> Set) -> Set

The Kcombinator digunakan untuk mengangkat nilai dari beberapa jenis Auntuk fungsi konstan selama beberapa jenis lainnya G.

  G : Set   A : Set
-------------------------------
  K : (a : A) -> (g : G) -> A

The Scombinator digunakan untuk aplikasi angkat lebih jenis, di mana semua bagian mungkin tergantung.

  G : Set
  A : (g : G) -> Set
  B : (g : G) -> (a : A g) -> Set
----------------------------------------------------
  S : (f : (g : G) ->    (a : A g) -> B g a   ) ->
      (a : (g : G) ->    A g                  ) ->
           (g : G) ->    B g (a g)

Jika Anda melihat pada tipe S, Anda akan melihat bahwa itu secara tepat menyatakan aturan aplikasi kontekstual dari teori tipe, jadi itulah yang membuatnya cocok untuk mencerminkan konstruksi aplikasi. Itu tugasnya!

Kami kemudian memiliki aplikasi hanya untuk hal-hal tertutup

  f : Pi A B
  a : A
--------------
  f a : B a

Tapi ada halangan. Saya telah menulis tipe-tipe kombinator dalam teori tipe biasa, bukan teori tipe kombinatoris. Untungnya, saya memiliki mesin yang akan menerjemahkan.

Sistem Jenis Kombinasi

---------
  U : U

---------------------------------------------------------
  P : PU(S(S(KP)(S(S(KP)(SKK))(S(KK)(KU))))(S(KK)(KU)))

  G : U
  A : U
-----------------------------------------
  K : P[A](S(S(KP)(K[G]))(S(KK)(K[A])))

  G : U
  A : P[G](KU)
  B : P[G](S(S(KP)(S(K[A])(SKK)))(S(KK)(KU)))
--------------------------------------------------------------------------------------
  S : P(P[G](S(S(KP)(S(K[A])(SKK)))(S(S(KS)(S(S(KS)(S(KK)(K[B])))(S(KK)(SKK))))
      (S(S(KS)(KK))(KK)))))(S(S(KP)(S(S(KP)(K[G]))(S(S(KS)(S(KK)(K[A])))
      (S(S(KS)(KK))(KK)))))(S(S(KS)(S(S(KS)(S(KK)(KP)))(S(KK)(K[G]))))
      (S(S(KS)(S(S(KS)(S(KK)(KS)))(S(S(KS)(S(S(KS)(S(KK)(KS)))
      (S(S(KS)(S(KK)(KK)))(S(KK)(K[B])))))(S(S(KS)(S(S(KS)(S(KK)(KS)))(S(KK)(KK))))
      (S(KK)(KK))))))(S(S(KS)(S(S(KS)(S(KK)(KS)))(S(S(KS)(S(KK)(KK)))
      (S(S(KS)(KK))(KK)))))(S(S(KS)(S(S(KS)(S(KK)(KS)))(S(KK)(KK))))(S(KK)(KK)))))))

  M : A   B : U
----------------- A ={norm} B
  M : B

Jadi begitulah, dalam semua kemuliaan yang tak terbaca: presentasi kombinasi dari Set:Set!

Masih ada sedikit masalah. Sintaks sistem tidak memberi Anda cara untuk menebak G, Adan Bparameter untuk Sdan yang serupa K, hanya dari istilah. Sejalan dengan itu, kami dapat memverifikasi derivasi pengetikan secara algoritme, tetapi kami tidak bisa hanya memeriksa istilah kombinator seperti yang kami bisa dengan sistem aslinya. Apa yang mungkin berhasil adalah meminta masukan kepada pemeriksa mesin untuk memuat penjelasan jenis pada penggunaan S dan K, yang secara efektif mencatat penurunan. Tapi itu cacing kaleng lainnya ...

Ini adalah tempat yang bagus untuk berhenti, jika Anda sudah cukup bersemangat untuk memulai. Sisanya adalah masalah "di balik layar".

Menghasilkan Jenis Combinator

Saya menghasilkan tipe kombinatoris tersebut menggunakan terjemahan abstraksi braket dari istilah teori tipe yang relevan. Untuk menunjukkan bagaimana saya melakukannya, dan membuat posting ini tidak sepenuhnya sia-sia, izinkan saya menawarkan peralatan saya.

Saya dapat menulis jenis kombinator, yang sepenuhnya diabstraksi atas parameternya, sebagai berikut. Saya menggunakan pilfungsi praktis saya , yang menggabungkan Pi dan lambda untuk menghindari pengulangan tipe domain, dan cukup membantu memungkinkan saya menggunakan ruang fungsi Haskell untuk mengikat variabel. Mungkin Anda hampir bisa membaca yang berikut ini!

pTy :: Tm a
pTy = fmap magic $
  pil Set $ \ _A -> pil (pil _A $ \ _ -> Set) $ \ _B -> Set

kTy :: Tm a
kTy = fmap magic $
  pil Set $ \ _G -> pil Set $ \ _A -> pil _A $ \ a -> pil _G $ \ g -> _A

sTy :: Tm a
sTy = fmap magic $
  pil Set $ \ _G ->
  pil (pil _G $ \ g -> Set) $ \ _A ->
  pil (pil _G $ \ g -> pil (_A :$ g) $ \ _ -> Set) $ \ _B ->
  pil (pil _G $ \ g -> pil (_A :$ g) $ \ a -> _B :$ g :$ a) $ \ f ->
  pil (pil _G $ \ g -> _A :$ g) $ \ a ->
  pil _G $ \ g -> _B :$ g :$ (a :$ g)

Dengan ini didefinisikan, saya mengekstrak subterm terbuka yang relevan dan menjalankannya melalui terjemahan.

Perangkat Pengkodean de Bruijn

Berikut cara membangunnya pil. Pertama, saya mendefinisikan kelas Finset ite, yang digunakan untuk variabel. Setiap set tersebut memiliki embedding yang menjaga konstruktor ke dalam set di atas, ditambah topelemen baru , dan Anda dapat membedakannya: embdfungsi tersebut memberi tahu Anda jika suatu nilai ada dalam gambar emb.

class Fin x where
  top :: Su x
  emb :: x -> Su x
  embd :: Su x -> Maybe x

Kita dapat, tentu saja, membuat contoh Finuntuk ZedanSuc

instance Fin Ze where
  top = Ze              -- Ze is the only, so the highest
  emb = magic
  embd _ = Nothing      -- there was nothing to embed

instance Fin x => Fin (Su x) where
  top = Su top          -- the highest is one higher
  emb Ze     = Ze            -- emb preserves Ze
  emb (Su x) = Su (emb x)    -- and Su
  embd Ze      = Just Ze           -- Ze is definitely embedded
  embd (Su x)  = fmap Su (embd x)  -- otherwise, wait and see

Sekarang saya bisa mendefinisikan kurang atau sama, dengan operasi yang melemah .

class (Fin x, Fin y) => Le x y where
  wk :: x -> y

The wkFungsi harus menanamkan unsur-unsur xsebagai terbesar unsur y, sehingga hal-hal ekstra dalam ylebih kecil, dan dengan demikian di de hal indeks Bruijn, terikat lebih lokal.

instance Fin y => Le Ze y where
  wk = magic    -- nothing to embed

instance Le x y => Le (Su x) (Su y) where
  wk x = case embd x of
    Nothing  -> top          -- top maps to top
    Just y   -> emb (wk y)   -- embedded gets weakened and embedded

Dan setelah Anda menyelesaikannya, sedikit penipuan kelas atas melakukan sisanya.

lam :: forall x. Tm x -> ((forall y. Le (Su x) y => Tm y) -> Tm (Su x)) -> Tm x
lam s f = Lam s (f (Var (wk (Ze :: Su x))))
pil :: forall x. Tm x -> ((forall y . Le (Su x) y => Tm y) -> Tm (Su x)) -> Tm x
pil s f = Pi s (lam s f)

Fungsi tingkat tinggi tidak hanya memberi Anda istilah yang mewakili variabel, ini memberi Anda hal yang kelebihan beban yang menjadi representasi yang benar dari variabel dalam lingkup mana pun di mana variabel tersebut terlihat. Artinya, fakta bahwa saya mengalami kesulitan dalam membedakan cakupan yang berbeda berdasarkan jenisnya memberikan informasi yang cukup kepada pemeriksa mesin ketik Haskell untuk menghitung pergeseran yang diperlukan untuk terjemahan ke representasi de Bruijn. Mengapa memelihara anjing dan menggonggong sendiri?

pekerja babi
sumber
ini mungkin sangat konyol tetapi bagaimana gambar ini berubah jika Anda menambahkan Fkombinator? Fbertindak berbeda bergantung pada argumen pertamanya: If Aadalah atom, Mdan Nadalah suku-suku dan PQmerupakan komposit, maka FAMN -> Mdan F(PQ)MN -> NPQ. Ini tidak dapat direpresentasikan dalam SK(I)kalkulus tetapi Kdapat direpresentasikan sebagai FF. Apakah mungkin untuk memperpanjang MLTT poin Anda dengan ini?
kram1032
Saya cukup yakin ada masalah dengan prosedur abstraksi braket ini, khususnya bagian "kombinator menjadi konstan", yang menerjemahkan λx.c ke Kc untuk kombinator c ∈ {S, K, U, P}. Masalahnya adalah bahwa kombinator ini polimorfik, dan dapat digunakan pada tipe yang bergantung pada x; jenis seperti itu tidak dapat dipertahankan oleh terjemahan ini. Sebagai contoh konkret, istilah λ (A : Set) → λ (a : A) → atipe (A : Set) → (a : A) → Aditerjemahkan S(S(KS)(KK))(KK), yang tidak dapat digunakan pada tipe di mana tipe argumen kedua bergantung pada argumen pertama.
Anders Kaseorg
8

Saya rasa "Abstraksi Braket" juga berfungsi untuk tipe dependen dalam beberapa keadaan. Di bagian 5 kertas berikut, Anda menemukan beberapa jenis K dan S:

Kebetulan yang Memalukan tapi Bermakna
Sintaks dan evaluasi tipe-aman yang bergantung
Conor McBride, University of Strathclyde, 2010

Mengubah ekspresi lambda menjadi ekspresi kombinatorial kira-kira sama dengan mengubah bukti deduksi alami menjadi bukti gaya Hilbert.

Mostowski runtuh
sumber