Pertanyaan Apa alasan untuk sistem tipe lengkap Turing [duplikat]


Pertanyaan ini sudah memiliki jawaban di sini:

Scala dan Haskell memiliki "Turing complete type systems". Biasanya, mengacu pada kelengkapan Turing perhitungan dan bahasa. Apa artinya ini dalam konteks tipe?

Bisakah seseorang memberi contoh bagaimana seorang programmer dapat memperoleh manfaat darinya?

PS Saya tidak ingin membandingkan sistem tipe Haskell vs Scala. Ini lebih tentang istilah secara umum.

PSS Jika mungkin lebih banyak contoh Scala.


21
2017-11-30 15:27


asal


Jawaban:


Apa artinya ini dalam konteks tipe?

Ini berarti sistem jenis memiliki fitur yang cukup di dalamnya untuk mewakili perhitungan yang sewenang-wenang. Sebagai bukti yang sangat singkat, saya menyajikan di bawah implementasi tingkat-jenis SK kalkulus; ada banyak tempat yang membahas kelengkapan turing dari kalkulus ini dan apa artinya, jadi saya tidak akan mengulanginya di sini.

{-# LANGUAGE DataKinds #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE UndecidableInstances #-}
{-# LANGUAGE TypeOperators #-}

infixl 1 `App`
data Term = S | K | App Term Term

type family Reduce t where
    Reduce S = S
    Reduce K = K
    Reduce (S `App` x `App` y `App` z) = Reduce (x `App` z `App` (y `App` z))
    Reduce (K `App` x `App` y) = Reduce x
    Reduce (x `App` y) = Reduce (Reduce x `App` y)

Anda dapat melihat ini dalam aksi pada prompt ghci; misalnya, dalam SK kalkulus, istilahnya SKSK mengurangi (akhirnya) menjadi adil K:

> :kind! Reduce (S `App` K `App` S `App` K)
Reduce (S `App` K `App` S `App` K) :: Term
= 'K

Ini yang menyenangkan untuk dicoba juga:

> type I = S `App` K `App` K
> type Rep = S `App` I `App` I
> :kind! Reduce (Rep `App` Rep)

Saya tidak akan merusak kesenangan - cobalah sendiri. Tetapi tahu bagaimana mengakhiri program dengan prasangka ekstrim terlebih dahulu.

Bisakah seseorang memberi contoh bagaimana seorang programmer dapat memperoleh manfaat darinya?

Komputasi jenis-tingkat yang sewenang-wenang memungkinkan Anda untuk mengekspresikan invarian acak pada jenis Anda, dan meminta compiler memverifikasi (pada saat-saat kompilasi) bahwa mereka diawetkan. Ingin pohon merah-hitam? Bagaimana dengan pohon merah-hitam yang dapat diperiksa oleh compiler mempertahankan invariants merah-hitam-pohon? Itu akan berguna, kan, karena itu mengesampingkan seluruh kelas bug implementasi? Bagaimana dengan tipe untuk nilai-nilai XML yang secara statis dikenal untuk mencocokkan skema tertentu? Bahkan, mengapa tidak melangkah lebih jauh dan tuliskan tipe parameter yang parameternya mewakili skema? Kemudian Anda dapat membaca dalam skema pada saat runtime, dan periksa kompilasi waktu Anda menjamin bahwa nilai parameter Anda hanya dapat mewakili nilai yang terbentuk dengan baik dalam skema itu. Bagus!

Atau, mungkin contoh yang lebih membosankan: bagaimana jika Anda ingin compiler memeriksa bahwa Anda tidak pernah mengindeks kamus Anda dengan kunci yang tidak ada? Dengan sistem tipe yang cukup canggih, Anda bisa.

Tentu saja, selalu ada harga. Di Haskell (dan mungkin Scala?), Harga kompilasi waktu yang sangat menarik menghabiskan banyak waktu dan upaya programmer untuk meyakinkan compiler bahwa hal yang Anda periksa benar - dan ini sering kali keduanya tinggi. biaya di muka serta biaya perawatan berkelanjutan yang tinggi.


27
2017-11-30 16:44