Jenis pengecekan dan tipe rekursif (Menulis kombinator Y di Haskell / Ocaml)

Ketika menjelaskan kombinator Y dalam konteks Haskell, biasanya dicatat bahwa implementasi straight-forward tidak akan mengetik-cek di Haskell karena tipe rekursifnya.

Misalnya, dari Rosettacode :

The obvious definition of the Y combinator in Haskell canot be used
because it contains an infinite recursive type (a = a -> b). Defining
a data type (Mu) allows this recursion to be broken.

newtype Mu a = Roll { unroll :: Mu a -> a }

fix :: (a -> a) -> a
fix = \f -> (\x -> f (unroll x x)) $ Roll (\x -> f (unroll x x))

Dan memang, definisi "jelas" tidak mengetik centang:

λ> let fix f g = (\x -> \a -> f (x x) a) (\x -> \a -> f (x x) a) g

<interactive>:10:33:
    Occurs check: cannot construct the infinite type:
      t2 = t2 -> t0 -> t1
    Expected type: t2 -> t0 -> t1
      Actual type: (t2 -> t0 -> t1) -> t0 -> t1
    In the first argument of `x', namely `x'
    In the first argument of `f', namely `(x x)'
    In the expression: f (x x) a

<interactive>:10:57:
    Occurs check: cannot construct the infinite type:
      t2 = t2 -> t0 -> t1
    In the first argument of `x', namely `x'
    In the first argument of `f', namely `(x x)'
    In the expression: f (x x) a
(0.01 secs, 1033328 bytes)

Batasan yang sama ada di Ocaml:

utop # let fix f g = (fun x a -> f (x x) a) (fun x a -> f (x x) a) g;;
Error: This expression has type 'a -> 'b but an expression was expected of type 'a                                    
       The type variable 'a occurs inside 'a -> 'b

Namun, dalam Ocaml, seseorang dapat memungkinkan tipe rekursif dengan melewati -rectypessaklar:

   -rectypes
          Allow  arbitrary  recursive  types  during type-checking.  By default, only recursive
          types where the recursion goes through an object type are supported.

Dengan menggunakan -rectypes, semuanya berfungsi:

utop # let fix f g = (fun x a -> f (x x) a) (fun x a -> f (x x) a) g;;
val fix : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b = <fun>
utop # let fact_improver partial n = if n = 0 then 1 else n*partial (n-1);;
val fact_improver : (int -> int) -> int -> int = <fun>
utop # (fix fact_improver) 5;;
- : int = 120

Karena penasaran dengan sistem tipe dan inferensi tipe, ini menimbulkan beberapa pertanyaan yang masih belum bisa saya jawab.

• Pertama, bagaimana pemeriksa tipe muncul dengan tipe t2 = t2 -> t0 -> t1? Setelah muncul dengan tipe itu, saya kira masalahnya adalah tipe ( t2) merujuk pada dirinya sendiri di sisi kanan?
• Kedua, dan mungkin yang paling menarik, apa alasan sistem tipe Haskell / Ocaml untuk melarang ini? Saya kira ada adalah alasan yang baik karena Ocaml juga tidak akan membiarkan hal itu secara default bahkan jika itu dapat menangani jenis rekursif jika diberi -rectypesswitch.

Jika ini adalah topik yang sangat besar, saya akan menghargai petunjuk untuk literatur yang relevan.

Pertama, kesalahan GHC,

GHC berusaha menyatukan beberapa kendala dengan x, pertama, kami menggunakannya sebagai fungsi

x :: a -> b

Selanjutnya kita menggunakannya sebagai nilai untuk fungsi itu

x :: a

Dan akhirnya kami menyatukannya dengan ekspresi argumen asli begitu

x :: (a -> b) -> c -> d

Sekarang x xmenjadi upaya untuk menyatukan t2 -> t1 -> t0, namun, Kami tidak dapat menyatukan ini karena akan membutuhkan pemersatu t2, argumen pertama dari x, dengan x. Karena itu pesan kesalahan kami.

Selanjutnya, mengapa bukan tipe rekursif umum. Nah poin pertama yang perlu diperhatikan adalah perbedaan antara tipe rekursif equi dan iso,

• equi-rekursif adalah apa yang Anda harapkan mu X . Typepersis sama dengan memperluas atau melipatnya secara sewenang-wenang.
• tipe iso-rekursif menyediakan sepasang operator, folddan unfoldyang melipat dan membuka definisi tipe rekursif.

Sekarang tipe equi-recursive terdengar ideal, tetapi bukan kepalang sulit untuk mendapatkan yang benar dalam sistem tipe kompleks. Ini benar-benar dapat membuat pengecekan tipe tidak dapat dipastikan. Saya tidak terbiasa dengan setiap detail sistem tipe OCaml tetapi tipe equirecursive sepenuhnya di Haskell dapat menyebabkan typechecker untuk secara acak mencoba menyatukan tipe, secara default, Haskell memastikan bahwa pengecekan tipe berakhir. Lebih jauh lagi, di Haskell, jenis sinonim adalah bodoh, tipe rekursif paling berguna akan didefinisikan seperti type T = T -> (), namun segera diuraikan dalam Haskell, tetapi Anda tidak dapat menyejajarkan jenis rekursif, itu tak terbatas! Oleh karena itu, tipe rekursif dalam Haskell akan menuntut perombakan besar untuk bagaimana sinonim ditangani, mungkin tidak sepadan dengan upaya untuk menempatkan bahkan sebagai ekstensi bahasa.

Jenis iso-rekursif sedikit menyakitkan untuk digunakan, Anda lebih atau kurang harus secara eksplisit memberi tahu pemeriksa jenis cara melipat dan membuka lipatan jenis Anda, membuat program Anda lebih kompleks untuk dibaca dan ditulis.

Namun, ini sangat mirip dengan apa yang Anda lakukan dengan Mutipe Anda . Rolldilipat, dan unrollterbuka. Jadi sebenarnya, kami memang memiliki tipe iso-rekursif yang dipanggang. Namun, tipe equi-rekursif terlalu rumit sehingga sistem seperti OCaml dan Haskell memaksa Anda untuk melewatkan perulangan melalui titik-titik perbaikan tingkat tipe.

Sekarang jika ini menarik bagi Anda, saya akan merekomendasikan Jenis dan Bahasa Pemrograman. Salinan saya duduk terbuka di pangkuan saya saat saya menulis ini untuk memastikan saya mendapatkan terminologi yang tepat :)

Di OCaml, Anda harus meneruskan -rectypessebagai parameter ke kompiler (atau masukkan #rectypes;;di tingkat atas). Secara kasar, ini akan mematikan "terjadi pemeriksaan" selama penyatuan. Situasi The type variable 'a occurs inside 'a -> 'btidak lagi menjadi masalah. Sistem tipe masih akan "benar" (suara, dll.), Pohon tanpa batas yang muncul sebagai jenis kadang-kadang disebut "pohon rasional". Tipe sistem semakin lemah, yaitu menjadi tidak mungkin untuk mendeteksi beberapa kesalahan programmer.

Lihat kuliah saya di lambda-calculus (mulai dari slide 27) untuk informasi lebih lanjut tentang operator fixpoint dengan contoh-contoh di OCaml.