"Strictosamente positivo" in AGDA

Question

Sto cercando di codificare alcune semantiche denotazionali nell'AGDA sulla base di un programma che ho scritto in Haskell.

data Value = FunVal (Value -> Value)
           | PriVal Int
           | ConVal Id [Value]
           | Error  String

In AGDA, la traduzione diretta sarebbe;

data Value : Set where
    FunVal : (Value -> Value) -> Value
    PriVal : ℕ -> Value
    ConVal : String -> List Value -> Value
    Error  : String -> Value

Ma ricevo un errore relativo al funvalo perché;

Il valore non è strettamente positivo, perché si verifica a sinistra di una freccia nel tipo di funvale del costruttore nella definizione di valore.

Cosa significa questo? Posso codificare questo in AGDA? Lo sto andando nel modo sbagliato?

Grazie.

Answer 1

Hoas Non funziona in AGDA, per questo:

apply : Value -> Value -> Value
apply (FunVal f) x = f x
apply _ x = Error "Applying non-function"

w : Value
w = FunVal (\x -> apply x x)

Ora, nota che valutare apply w w ti dà apply w w di nuovo indietro. Il termine apply w w non ha una forma normale, che è un no-no in AGDA. Usando questa idea e il tipo:

data P : Set where
    MkP : (P -> Set) -> P

Possiamo derivare una contraddizione.

Uno dei modi fuori da questi paradossi è solo per consentire tipi ricorsivi strettamente positivi, che è ciò che scelgono AGDA e CoQ. Ciò significa che se dichiari:

data X : Set where
    MkX : F X -> X

Quella F deve essere un funtore strettamente positivo, il che significa X non può mai verificarsi a sinistra di nessuna freccia. Quindi questi tipi sono strettamente positivi in X:

X * X
Nat -> X
X * (Nat -> X)

Ma questi non lo sono:

X -> Bool
(X -> Nat) -> Nat  -- this one is "positive", but not strictly
(X * Nat) -> X

Quindi, in breve, no non puoi rappresentare il tuo tipo di dati in AGDA. È possibile utilizzare la codifica de Bruijn per ottenere un tipo di termine con cui puoi lavorare, ma di solito la funzione di valutazione richiede una sorta di "timeout" (generalmente chiamato "carburante"), ad esempio un numero massimo di passaggi da valutare, perché AGDA richiede tutte le funzioni essere totale. Ecco un esempio A causa di @gallais che utilizza un tipo di parzialità coinduttivo per raggiungere questo obiettivo.