Pertanyaan Dapatkah monumen `ST` seperti dieksekusi murni (tanpa pustaka` ST`)?


Posting ini melek huruf Haskell. Cukup masukkan file seperti "pad.lhs" dan ghci akan dapat menjalankannya.

> {-# LANGUAGE GADTs, Rank2Types #-}
> import Control.Monad
> import Control.Monad.ST
> import Data.STRef

Oke, jadi saya bisa memikirkan cara mewakili ST monad dalam kode murni. Pertama kita mulai dengan tipe referensi kami. Nilai spesifiknya tidak terlalu penting. Yang paling penting adalah itu PT s a tidak boleh isomorfik ke jenis lainnya forall s. (Khususnya, seharusnya isomorfik bukan keduanya () maupun Void.)

> newtype PTRef s a = Ref {unref :: s a} -- This is defined liked this to make `toST'` work. It may be given a different definition.

Jenis untuk s aku s *->*, tapi itu tidak terlalu penting sekarang. Bisa jadi polykind, untuk semua yang kami peduli.

> data PT s a where
>     MkRef   :: a -> PT s (PTRef s a)
>     GetRef  :: PTRef s a -> PT s a
>     PutRef  :: a -> PTRef s a -> PT s ()
>     AndThen :: PT s a -> (a -> PT s b) -> PT s b

Cukup lurus ke depan. AndThen memungkinkan kami untuk menggunakan ini sebagai Monad. Anda mungkin bertanya-tanya bagaimana caranya return diimplementasikan. Berikut adalah contoh monadnya (hanya menghormati hukum monad dengan hormat runPF, untuk didefinisikan nanti):

> instance Monad (PT s) where
>     (>>=)    = AndThen
>     return a = AndThen (MkRef a) GetRef --Sorry. I like minimalism.
> instance Functor (PT s) where
>     fmap = liftM
> instance Applicative (PT s) where
>     pure  = return
>     (<*>) = ap

Sekarang kita bisa mendefinisikan fib sebagai test case.

> fib :: Int -> PT s Integer
> fib n = do
>     rold <- MkRef 0
>     rnew <- MkRef 1
>     replicateM_ n $ do
>         old <- GetRef rold
>         new <- GetRef rnew
>         PutRef      new  rold
>         PutRef (old+new) rnew
>     GetRef rold

Dan itu mengetik cek. Hore! Sekarang, saya dapat mengonversi ini menjadi ST (sekarang kita melihat mengapa s harus * -> *)

> toST :: PT (STRef s) a -> ST s a
> toST (MkRef  a        ) = fmap Ref $ newSTRef a
> toST (GetRef   (Ref r)) = readSTRef r
> toST (PutRef a (Ref r)) = writeSTRef r a
> toST (pa `AndThen` apb) = (toST pa) >>= (toST . apb)

Sekarang kita dapat mendefinisikan fungsi untuk dijalankan PT tanpa referensi ST sama sekali:

> runPF :: (forall s. PT s a) -> a
> runPF p = runST $ toST p

runPF $ fib 7 memberi 13, yang mana yang benar.


Pertanyaan saya adalah apakah kita bisa mendefinisikannya runPF tanpa referensi menggunakan ST sama sekali?

Apakah ada cara murni untuk mendefinisikan runPF? PTRefDefinisi benar-benar tidak penting; itu hanya jenis placeholder saja. Ini dapat didefinisikan ulang untuk apa pun yang membuatnya bekerja.

Jika kamu tidak bisa menetapkan runPF murni, berikan bukti bahwa itu tidak bisa.

Kinerja bukan masalah (jika itu, saya tidak akan membuat semuanya return punya ref sendiri).

Saya berpikir bahwa tipe eksistensial mungkin berguna.

Catatan: Ini sepele jika kita berasumsi demikian a bersifat dinamis atau sesuatu. Saya mencari jawaban yang cocok untuk semua orang a.

Catatan: Sebenarnya, jawaban tidak perlu banyak berhubungan PT. Itu hanya perlu sekuat ST tanpa menggunakan sihir. (Konversi dari (forall s. PT s) adalah semacam ujian jika jawaban valid atau tidak.)


32
2017-11-28 19:04


asal


Jawaban:


tl; dr: Itu tidak mungkin tanpa penyesuaian dengan definisi PT. Inilah masalah intinya: Anda akan menjalankan komputasi stateful Anda dalam konteks semacam media penyimpanan, tetapi media penyimpanan harus tahu cara menyimpan sewenang-wenang jenis. Ini tidak mungkin tanpa mengemas semacam bukti ke dalam MkRef konstruktor - baik yang dibungkus eksistensial Typeable kamus seperti yang orang lain sarankan, atau bukti bahwa nilai milik salah satu set tipe terbatas yang diketahui.

Untuk upaya pertama, mari coba gunakan daftar sebagai media penyimpanan dan bilangan bulat untuk merujuk ke elemen daftar.

newtype Ix a = MkIx Int  -- the index of an element in a list

interp :: PT Ix a -> State [b] a
interp (MkRef x) = modify (++ [x]) >> gets (Ref . MkIx . length)
-- ...

Saat menyimpan item baru di lingkungan, kami pastikan untuk menambahkannya ke bagian akhir daftar, sehingga RefKami sebelumnya diberikan tinggal menunjuk pada elemen yang benar.

Ini tidak benar. Saya bisa membuat referensi apa saja mengetik a, tetapi jenis interp mengatakan bahwa media penyimpanan adalah daftar yang homogen bs. GHC meminta kami memberikan hak ketika menolak tanda tangan jenis ini, mengeluh bahwa itu tidak cocok b dengan jenis barang di dalamnya MkRef.


Tidak terpengaruh, mari kita mulai menggunakan heterogen daftar sebagai lingkungan untuk State monad di mana kita akan menafsirkan PT.

infixr 4 :>
data Tuple as where
    E :: Tuple '[]
    (:>) :: a -> Tuple as -> Tuple (a ': as)

Ini adalah salah satu tipe data Haskell favorit pribadi saya. Itu adalah extensible tuple diindeks oleh daftar jenis hal-hal di dalamnya. Tuples adalah daftar terkait heterogen dengan informasi tingkat-tipe tentang jenis hal-hal di dalamnya. (Sering disebut HList berikut Kertas Kiselyov tapi saya lebih suka Tuple.) Ketika Anda menambahkan sesuatu ke depan tuple, Anda menambahkan jenisnya ke depan daftar jenis. Dalam suasana hati yang puitis, Saya pernah mengatakannya seperti ini: "Tupel dan jenisnya tumbuh bersama, seperti sulur merambat tanaman bambu."

Contoh dari Tuples:

ghci> :t 'x' :> E
'x' :> E :: Tuple '[Char]
ghci> :t "hello" :> True :> E
"hello" :> True :> E :: Tuple '[[Char], Bool]

Apa yang dimaksud dengan referensi ke nilai di dalam tupel? Kita harus membuktikan kepada GHC bahwa jenis barang yang kita dapatkan dari tupel memang tipe yang kita harapkan.

data Elem as a where  -- order of indices arranged for convenient partial application
    Here :: Elem (a ': as) a
    There :: Elem as a -> Elem (b ': as) a

Definisi dari Elem secara struktural dari angka-angka alam (Elem nilai-nilai seperti There (There Here) terlihat mirip dengan bilangan asli seperti S (S Z)) tetapi dengan tipe tambahan - dalam hal ini, membuktikan bahwa tipenya a ada di daftar level-level as. Saya menyebutkan ini karena itu sugestif: Nats membuat daftar indeks yang bagus, dan juga Elem berguna untuk mengindeks ke tuple. Dalam hal ini akan berguna sebagai pengganti untuk Int di dalam tipe referensi kami.

(!) :: Tuple as -> Elem as a -> a
(x :> xs) ! Here = x
(x :> xs) ! (There ix) = xs ! ix

Kami membutuhkan beberapa fungsi untuk bekerja dengan tupel dan indeks.

type family as :++: bs where
    '[] :++: bs = bs
    (a ': as) :++: bs = a ': (as :++: bs)

appendT :: a -> Tuple as -> (Tuple (as :++: '[a]), Elem (as :++: '[a]) a)
appendT x E = (x :> E, Here)
appendT x (y :> ys) = let (t, ix) = appendT x ys
                      in (y :> t, There ix)

Mari mencoba dan menulis juru bahasa untuk PT di sebuah Tuple lingkungan Hidup.

interp :: PT (Elem as) a -> State (Tuple as) a
interp (MkRef x) = do
    t <- get
    let (newT, el) = appendT x t
    put newT
    return el
-- ...

Tidak bisa, buster. Masalahnya adalah jenisnya Tuple di lingkungan berubah ketika kami memperoleh referensi baru. Seperti yang saya sebutkan sebelumnya, menambahkan sesuatu ke tuple menambah jenisnya ke tipe tuple, sebuah fakta yang dibantah oleh tipe State (Tuple as) a. GHC tidak tertipu oleh akal-akalan yang dicoba ini: Could not deduce (as ~ (as :++: '[a1])).


Di sinilah roda terlepas, sejauh yang saya tahu. Apa yang Anda benar-benar ingin lakukan adalah menjaga ukuran tupel konstan sepanjang PT komputasi. Ini akan mengharuskan Anda untuk mengindeks PT sendiri dengan daftar jenis yang dapat Anda peroleh referensi, membuktikan setiap kali Anda melakukannya sehingga Anda diizinkan untuk (dengan memberikan suatu Elem nilai). Lingkungan kemudian akan terlihat seperti daftar tupel, dan referensi akan terdiri dari Elem (untuk memilih daftar yang benar) dan sebuah Int (untuk menemukan item tertentu dalam daftar).

Rencana ini melanggar aturan, tentu saja (Anda perlu mengubah definisi PT), tetapi juga memiliki masalah teknik. Ketika saya menelepon MkRef, tanggung jawab ada pada saya untuk memberi Elem untuk nilai yang saya jadikan referensi, yang cukup membosankan. (Dikatakan, Anda biasanya dapat meyakinkan GHC untuk menemukan Elemnilai dengan pencarian bukti menggunakan kelas jenis peretasan.)

Hal lain: menulis PTs menjadi sulit. Semua bagian dari perhitungan Anda harus diindeks oleh sama daftar tipe. Anda dapat mencoba memperkenalkan kombinator atau kelas yang memungkinkan Anda menumbuhkan lingkungan a PT, tetapi Anda juga harus memperbarui semua referensi ketika Anda melakukannya. Menggunakan monad akan sangat sulit.

Implementasi yang mungkin lebih bersih akan memungkinkan daftar tipe dalam a PT bervariasi saat Anda berjalan di sekitar datatype: setiap kali Anda menghadapi MkRef tipe mendapatkan satu lagi. Karena jenis perhitungan berubah seiring berjalannya waktu, Anda tidak dapat menggunakan monad biasa - Anda harus menggunakan IxMonad  . Jika Anda ingin tahu seperti apa program itu, lihat saya jawaban lainnya.

Pada akhirnya, titik lengket adalah bahwa jenis tupel ditentukan oleh nilai dari PT permintaan. Lingkungan aku s apa permintaan yang diberikan memutuskan untuk menyimpannya. interp tidak bisa memilih apa yang ada di tupel, itu harus berasal dari indeks PT. Setiap upaya untuk menipu persyaratan itu akan crash dan membakar. Sekarang, dalam sistem yang benar-benar bergantung-ketikan kita bisa memeriksa PT nilai kami diberikan dan mencari tahu apa as seharusnya. Sayangnya, Haskell bukan sistem yang diketikkan secara dependen.


14
2017-11-28 23:54



Solusi sederhana adalah membungkus State monad dan tampilkan API yang sama dengan ST. Dalam hal ini tidak perlu menyimpan informasi jenis runtime, karena dapat ditentukan dari jenis STRef-s, dan biasa ST s Kuantifikasi trik memungkinkan kita mencegah pengguna mengacaukan wadah menyimpan referensi.

Kami menyimpan ref-s dalam suatu IntMap dan menambah konter setiap kali kami mengalokasikan ref baru. Membaca dan menulis hanya memodifikasi IntMap dengan beberapa unsafeCoerce ditaburkan di atas.

{-# LANGUAGE DeriveFunctor, GeneralizedNewtypeDeriving, RankNTypes, RoleAnnotations #-}

module PureST (ST, STRef, newSTRef, readSTRef, modifySTRef, runST) where

import Data.IntMap (IntMap, (!))
import qualified Data.IntMap as M

import Control.Monad
import Control.Applicative
import Control.Monad.Trans.State
import GHC.Prim (Any)
import Unsafe.Coerce (unsafeCoerce)

type role ST nominal representational
type role STRef nominal representational
newtype ST s a = ST (State (IntMap Any, Int) a) deriving (Functor, Applicative, Monad)
newtype STRef s a = STRef Int deriving Show

newSTRef :: a -> ST s (STRef s a)
newSTRef a = ST $ do
  (m, i) <- get
  put (M.insert i (unsafeCoerce a) m, i + 1)
  pure (STRef i)

readSTRef :: STRef s a -> ST s a
readSTRef (STRef i) = ST $ do
  (m, _) <- get
  pure (unsafeCoerce (m ! i))

writeSTRef :: STRef s a -> a -> ST s ()
writeSTRef (STRef i) a = ST $ 
  modify $ \(m, i') -> (M.insert i (unsafeCoerce a) m, i')

modifySTRef :: STRef s a -> (a -> a) -> ST s ()
modifySTRef (STRef i) f = ST $
  modify $ \(m, i') -> (M.adjust (unsafeCoerce f) i m, i')                      

runST :: (forall s. ST s a) -> a
runST (ST s) = evalState s (M.empty, 0)

foo :: Num a => ST s (a, Bool)
foo = do
  a <- newSTRef 0 
  modifySTRef a (+100)
  b <- newSTRef False
  modifySTRef b not
  (,) <$> readSTRef a <*> readSTRef b

Sekarang kita bisa melakukan:

> runST foo
(100, True)

Tetapi hal berikut gagal dengan biasanya ST kesalahan jenis:

> runST (newSTRef True)

Tentu saja, skema di atas tidak pernah mengumpulkan sampah referensi, melainkan membebaskan semuanya pada masing-masing runST panggilan. Saya pikir sistem yang lebih kompleks dapat mengimplementasikan beberapa wilayah berbeda, masing-masing ditandai oleh parameter jenis, dan mengalokasikan / sumber daya gratis dengan cara yang lebih halus.

Juga, penggunaan unsafeCoerce Berarti di sini bahwa menggunakan internal secara langsung sama bahayanya dengan menggunakan GHC.ST internal dan State# secara langsung, jadi kita harus memastikan untuk menyajikan API yang aman, dan juga menguji internal kami secara menyeluruh (atau kita bisa mendapatkan segfault di Haskell, dosa besar).


11
2017-11-28 22:51



Sejak saya memposting saya jawaban sebelumnya, Anda telah mengindikasikan bahwa Anda tidak keberatan membuat perubahan pada definisi Anda PT. Saya senang melaporkan: bersantai bahwa pembatasan mengubah jawaban atas pertanyaan Anda dari tidak untuk iya nih! Saya sudah berpendapat bahwa Anda perlu mengindeks monad Anda dengan set jenis di media penyimpanan Anda, jadi inilah beberapa kode kerja yang menunjukkan bagaimana melakukan itu. (Awalnya saya memiliki ini sebagai pengeditan untuk jawaban saya sebelumnya tetapi terlalu panjang, jadi di sinilah kami.)

{-# LANGUAGE DataKinds #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE PatternSynonyms #-}
{-# LANGUAGE PolyKinds #-}
{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE RebindableSyntax #-}
{-# LANGUAGE TypeOperators #-}

import Prelude

Kami akan membutuhkan yang lebih pintar Monad kelas dari yang ada di Prelude: bahwa dari hal-hal seperti monad yang diindeks menjelaskan jalur melalui grafik yang diarahkan. Untuk alasan yang seharusnya menjadi jelas, saya akan mendefinisikan fungsi terindeks juga.

class FunctorIx f where
    imap :: (a -> b) -> f i j a -> f i j b

class FunctorIx m => MonadIx m where
    ireturn :: a -> m i i a
    (>>>=) :: m i j a -> (a -> m j k b) -> m i k b

(>>>) :: MonadIx m => m i j a -> m j k b -> m i k b
ma >>> mb = ma >>>= \_ -> mb

replicateM_ :: MonadIx m => Int -> m i i a -> m i i ()
replicateM_ 0 _ = ireturn ()
replicateM_ n m = m >>> replicateM_ (n - 1) m

Monad yang diindeks menggunakan sistem jenis untuk melacak kemajuan perhitungan stateful. m i j a adalah komputasi monadik yang membutuhkan status masukan i, mengubah status menjadi j, dan menghasilkan nilai tipe a. Mengurutkan monad diindeks dengan >>>= seperti bermain domino. Anda dapat memberi makan perhitungan yang mengambil negara dari i untuk j ke dalam perhitungan yang dimulai j untuk k, dan dapatkan perhitungan yang lebih besar dari i untuk k. (Ada versi lebih kaya dari monad diindeks ini yang dijelaskan di Kleisli Arrows of Outrageous Fortune (dan di tempat lain) tapi yang ini cukup untuk tujuan kita.)

Satu kemungkinan dengan MonadIx adalah File monad yang melacak status penanganan file, memastikan Anda tidak lupa untuk membebaskan sumber daya. fOpen :: File Closed Open () dimulai dengan file yang tertutup dan membukanya, fRead :: File Open Open String mengembalikan isi file yang dibuka, dan fClose :: File Open Closed () mengambil file dari terbuka ke tertutup. Itu run Operasi membutuhkan perhitungan tipe File Closed Closed a, yang memastikan bahwa file Anda menangani selalu dibersihkan.

Tapi saya ngelantur: di sini kita tidak peduli dengan menangani file tetapi dengan satu set "lokasi memori" diketik; jenis hal-hal di bank memori mesin virtual adalah apa yang akan kita gunakan untuk indeks monad. Saya suka mendapatkan mons "program / penerjemah" saya gratis karena ia mengungkapkan fakta bahwa hasilnya hidup di daun perhitungan, dan mempromosikan komposabilitas dan penggunaan kembali kode, jadi inilah functor yang akan menghasilkan PT saat kami memasukkannya FreeIx di bawah:

data PTF ref as bs r where
    MkRef_ :: a -> (ref (a ': as) a -> r) -> PTF ref as (a ': as) r
    GetRef_ :: ref as a -> (a -> r) -> PTF ref as as r
    PutRef_ :: a -> ref as a -> r -> PTF ref as as r

instance FunctorIx (PTF ref) where
    imap f (MkRef_ x next) = MkRef_ x (f . next)
    imap f (GetRef_ ref next) = GetRef_ ref (f . next)
    imap f (PutRef_ x ref next) = PutRef_ x ref (f next)

PTF parameterised oleh jenis referensi ref :: [*] -> * -> * - referensi diizinkan untuk mengetahui jenis apa yang ada dalam sistem - dan diindeks oleh daftar jenis yang disimpan dalam "memori" interpreter. Kasus yang menarik adalah MkRef_: membuat referensi baru menambah nilai jenis a ke memori, mengambil as untuk a ': as; kelanjutan mengharapkan a ref di lingkungan yang diperpanjang. Operasi lainnya tidak mengubah daftar jenis dalam sistem.

Ketika saya membuat referensi secara berurutan (x <- mkRef 1; y <- mkRef 2), mereka akan memiliki tipe yang berbeda: yang pertama akan menjadi a ref (a ': as) a dan yang kedua adalah a ref (b ': a ': as) b. Untuk membuat jenis-jenis tersebut berbaris, saya memerlukan suatu cara untuk menggunakan referensi dalam lingkungan yang lebih besar daripada yang dibuat. Dalam umumnya, operasi ini tergantung pada jenis referensi, jadi saya akan memasukkannya ke dalam kelas.

class Expand ref where
    expand :: ref as a -> ref (b ': as) a

Satu generalisasi yang mungkin dari kelas ini akan membungkus pola aplikasi berulang expand, dengan tipe suka inflate :: ref as a -> ref (bs :++: as) a.

Berikut ini adalah infrastruktur lain yang dapat digunakan kembali, monad gratis yang diindeks Saya sebutkan sebelumnya. FreeIx mengubah fungsi terindeks menjadi monad diindeks dengan menyediakan operasi penggabungan tipe-rata Free, yang menghubungkan simpul rekursif dalam parameter functor, dan operasi tidak melakukan apa-apa Pure.

data FreeIx f i j a where
    Pure :: a -> FreeIx f i i a
    Free :: f i j (FreeIx f j k a) -> FreeIx f i k a

lift :: FunctorIx f => f i j a -> FreeIx f i j a
lift f = Free (imap Pure f)

instance FunctorIx f => MonadIx (FreeIx f) where
    ireturn = Pure
    Pure x >>>= f = f x
    Free love {- , man -} >>>= f = Free $ imap (>>>= f) love

instance FunctorIx f => FunctorIx (FreeIx f) where
    imap f x = x >>>= (ireturn . f)

Salah satu kelemahan dari monads gratis adalah boilerplate yang harus Anda tulis untuk membuatnya Free dan Pure lebih mudah digunakan. Berikut adalah beberapa aksi tunggal PTs yang membentuk dasar dari API monad, dan beberapa pola sinonim untuk menyembunyikan Free konstruktor ketika kita membongkar PT nilai-nilai.

type PT ref = FreeIx (PTF ref)

mkRef :: a -> PT ref as (a ': as) (ref (a ': as) a)
mkRef x = lift $ MkRef_ x id

getRef :: ref as a -> PT ref as as a
getRef ref = lift $ GetRef_ ref id

putRef :: a -> ref as a -> PT ref as as ()
putRef x ref = lift $ PutRef_ x ref ()

pattern MkRef x next = Free (MkRef_ x next)
pattern GetRef ref next = Free (GetRef_ ref next)
pattern PutRef x ref next = Free (PutRef_ x ref next)

Itu semua yang kita butuhkan untuk bisa menulis PT perhitungan. Ini punyamu fib contoh. saya menggunakan RebindableSyntax dan mendefinisikan kembali operator monad secara lokal (ke ekuivalen indeksnya) sehingga saya dapat menggunakannya do notasi pada monad terindeks saya.

-- fib adds two Ints to an arbitrary environment
fib :: Expand ref => Int -> PT ref as (Int ': Int ': as) Int
fib n = do
    rold' <- mkRef 0
    rnew <- mkRef 1
    let rold = expand rold'
    replicateM_ n $ do
        old <- getRef rold
        new <- getRef rnew
        putRef new rold
        putRef (old+new) rnew
    getRef rold
        where (>>=) = (>>>=)
              (>>) = (>>>)
              return :: MonadIx m => a -> m i i a
              return = ireturn
              fail :: MonadIx m => String -> m i j a
              fail = error

Versi ini dari fib terlihat seperti yang Anda ingin tulis dalam pertanyaan aslinya. Satu-satunya perbedaan (terlepas dari bindings lokal >>= dan seterusnya) adalah panggilan untuk expand. Setiap kali Anda membuat referensi baru, Anda harus expand semua yang lama, yang agak membosankan.

Akhirnya kita bisa menyelesaikan pekerjaan yang kita lakukan dan buat PT-mesin yang menggunakan Tuple sebagai media penyimpanan dan Elem sebagai tipe referensi.

infixr 5 :>
data Tuple as where
    E :: Tuple '[]
    (:>) :: a -> Tuple as -> Tuple (a ': as)

data Elem as a where
    Here :: Elem (a ': as) a
    There :: Elem as a -> Elem (b ': as) a

(!) :: Tuple as -> Elem as a -> a
(x :> xs) ! Here = x
(x :> xs) ! There ix = xs ! ix

updateT :: Elem as a -> a -> Tuple as -> Tuple as
updateT Here x (y :> ys) = x :> ys
updateT (There ix) x (y :> ys) = y :> updateT ix x ys

Untuk menggunakan Elem dalam tupel yang lebih besar dari yang Anda buat, Anda hanya perlu membuatnya lebih jauh ke bawah daftar.

instance Expand Elem where
    expand = There

Perhatikan bahwa penyebaran ini Elem agak seperti indeks de Bruijn: variabel yang lebih baru-terikat memiliki indeks yang lebih kecil.

interp :: PT Elem as bs a -> Tuple as -> a
interp (MkRef x next) tup = let newTup = x :> tup
                            in interp (next $ Here) newTup
interp (GetRef ix next) tup = let x = tup ! ix
                              in interp (next x) tup
interp (PutRef x ix next) tup = let newTup = updateT ix x tup
                                in interp next newTup
interp (Pure x) tup = x

Ketika interpreter menemui a MkRef permintaan, itu meningkatkan ukuran memori dengan menambahkan x ke depan. Pemeriksa jenis akan mengingatkan Anda bahwa ada refs dari sebelum MkRef harus benar expanded, sehingga referensi yang ada tidak bisa rusak ketika tupel mengubah ukuran. Kami membayar penerjemah tanpa gips yang tidak aman, tetapi kami mendapat referensial integritas untuk boot.

Berlari dari awal yang berdiri mengharuskan PT perhitungan mengharapkan untuk memulai dengan bank memori kosong, tetapi kami mengizinkannya berakhir di negara bagian mana pun.

run :: (forall ref. Expand ref => PT ref '[] bs a) -> a
run x = interp x E

Itu typecheck, tetapi apakah itu berfungsi?

ghci> run (fib 5)
5
ghci> run (fib 3)
2

9
2017-12-01 11:32