VerifiedCompilation.UntypedViews

Predicates and View Types for Untyped Terms

module VerifiedCompilation.UntypedViews where

open import Untyped using (_⊢; `; ƛ; case; constr; _·_; force; delay; con; builtin; error)
open import Relation.Unary as Unary using (Decidable)
open import Relation.Nullary using (Dec; yes; no; ¬_)
open import Utils as U using (Maybe; nothing; just; Either)
open import Relation.Nullary using (_×-dec_)
open import Data.Product using (_,_)
open import RawU using (TmCon)
open import Builtin using (Builtin)
open import VerifiedCompilation.Equality using (decEq-⊢)
open import Data.List using (List; [_])
open import Data.Nat using ()
open import Function using (_∋_)

Pattern Views for Terms

Because many of the translations only run on a very specific AST pattern, we need a View to recognise that pattern and extract the variables.

Following suggestions from Philip Wadler: creating Views for each Term type and then allowing them to accept arbitrary sub-views should make this reusable. We can create patterns using nested calls to these views, and decide them with nested calls to the decision procedures.

Pred : Set₁
Pred = {X : Set}  (X )  Set

ListPred : Set₁
ListPred = {X : Set}  List (X )  Set

data isVar { X : Set } : (X )  Set where
  isvar : (v : X)  isVar (` v)
isVar? : {X : Set}  Decidable (isVar {X})
isVar? (` x) = yes (isvar x)
isVar? (ƛ x) = no λ ()
isVar? (x · x₁) = no  ())
isVar? (force x) = no  ())
isVar? (delay x) = no  ())
isVar? (con x) = no  ())
isVar? (constr i xs) = no  ())
isVar? (case x ts) = no  ())
isVar? (builtin b) = no  ())
isVar? error = no  ())

data isLambda (P : Pred) { X : Set } : (X )  Set where
  islambda : {t : ((Maybe X) )}  P t  isLambda P (ƛ t)
isLambda? : {X : Set} {P : Pred}  ({X : Set}  Decidable (P {X}))  Decidable (isLambda P {X})
isLambda? isP? (` x) = no λ ()
isLambda? isP? (ƛ t) with isP? t
...                                | no ¬p = no λ { (islambda x)  ¬p x}
...                                | yes p = yes (islambda p)
isLambda? isP? (t _⊢.· t₁) = no  ())
isLambda? isP? (_⊢.force t) = no  ())
isLambda? isP? (_⊢.delay t) = no  ())
isLambda? isP? (_⊢.con x) = no  ())
isLambda? isP? (constr i xs) = no  ())
isLambda? isP? (case t ts) = no  ())
isLambda? isP? (_⊢.builtin b) = no  ())
isLambda? isP? _⊢.error = no  ())

data isApp (P Q : Pred) {X : Set}  : (X )  Set where
  isapp : {l r : (X )}  P l  Q r  isApp P Q (l · r)
isApp? : {X : Set}  {P Q : Pred}  ({X : Set}  Decidable (P {X}))  ({X : Set}  Decidable (Q {X}))  Decidable (isApp P Q {X})
isApp? isP? isQ? (` x) = no  ())
isApp? isP? isQ? (ƛ t) = no  ())
isApp? isP? isQ? (t · t₁) with (isP? t) ×-dec (isQ? t₁)
...                                    | no ¬p = no λ { (isapp x x₁)  ¬p (x , x₁)}
...                                    | yes (p , q) = yes (isapp p q)
isApp? isP? isQ? (force t) = no  ())
isApp? isP? isQ? (delay t) = no  ())
isApp? isP? isQ? (con x) = no  ())
isApp? isP? isQ? (constr i xs) = no  ())
isApp? isP? isQ? (case t ts) = no  ())
isApp? isP? isQ? (builtin b) = no  ())
isApp? isP? isQ? error = no  ())

data isForce (P : Pred) {X : Set} : (X )  Set where
  isforce : {t : (X )}  P t  isForce P (force t)
isForce? : {X : Set}  {P : Pred}  ({X : Set}  Decidable (P {X}))  Decidable (isForce P {X})
isForce? isP? (` x) = no  ())
isForce? isP? (ƛ t) = no  ())
isForce? isP? (t · t₁) = no  ())
isForce? isP? (force t) with isP? t
...                                  | no ¬p = no λ { (isforce x)  ¬p x}
...                                  | yes p = yes (isforce p)
isForce? isP? (delay t) = no  ())
isForce? isP? (con x) = no  ())
isForce? isP? (constr i xs) = no  ())
isForce? isP? (case t ts) = no  ())
isForce? isP? (builtin b) = no  ())
isForce? isP? error = no  ())


data isDelay (P : Pred) {X : Set} : (X )  Set where
  isdelay : {t : (X )}  P t  isDelay P (delay t)
isDelay? : {X : Set}  {P : Pred}  ({X : Set}  Decidable (P {X}))  Decidable (isDelay P {X})
isDelay? isP? (` x) = no  ())
isDelay? isP? (ƛ t) = no  ())
isDelay? isP? (t · t₁) = no  ())
isDelay? isP? (force t) = no  ())
isDelay? isP? (delay t) with isP? t
...                                  | yes p = yes (isdelay p)
...                                  | no ¬p = no λ { (isdelay x)  ¬p x }
isDelay? isP? (con x) = no  ())
isDelay? isP? (constr i xs) = no  ())
isDelay? isP? (case t ts) = no  ())
isDelay? isP? (builtin b) = no  ())
isDelay? isP? error = no  ())

data isCon {X : Set} : (X )  Set where
  iscon : (t : TmCon)   isCon {X} (con t)
isCon? : {X : Set}  Decidable (isCon {X})
isCon? (` x) = no  ())
isCon? (ƛ t) = no  ())
isCon? (t · t₁) = no  ())
isCon? (force t) = no  ())
isCon? (delay t) = no  ())
isCon? (con c) = yes (iscon c)
isCon? (constr i xs) = no  ())
isCon? (case t ts) = no  ())
isCon? (builtin b) = no  ())
isCon? error = no  ())

data isConstr (Qs : ListPred) {X : Set} : (X )  Set where
  isconstr : (i : )  {xs : List (X )}  Qs xs  isConstr Qs (constr i xs)
isConstr? : {X : Set}  {Qs : ListPred}  ({X : Set}  Decidable (Qs {X}))  Decidable (isConstr Qs {X})
isConstr? isQs? (` x) = no (λ())
isConstr? isQs? (ƛ t) = no (λ())
isConstr? isQs? (t · t₁) = no (λ())
isConstr? isQs? (force t) = no (λ())
isConstr? isQs? (delay t) = no (λ())
isConstr? isQs? (con x) = no (λ())
isConstr? isQs? (constr i xs) with isQs? xs
...                                           | no ¬q = no λ { (isconstr i₁ q)  ¬q q }
...                                           | yes q = yes (isconstr i q)
isConstr? isQs? (case t ts) = no (λ())
isConstr? isQs? (builtin b) = no (λ())
isConstr? isQs? error = no (λ())

data isCase (P : Pred) (Qs : ListPred) { X : Set } : (X )  Set where
  iscase : {t : (X )}  {ts : List (X )}  P t  Qs ts  isCase P Qs (case t ts)
isCase? : {X : Set}  {P : Pred}  {Qs : ListPred}  ({X : Set}  Decidable (P {X}))  ({X : Set}  Decidable (Qs {X}))  Decidable (isCase P Qs {X})
isCase? isP? isQs? (` x) = no  ())
isCase? isP? isQs? (ƛ t) = no  ())
isCase? isP? isQs? (t · t₁) = no  ())
isCase? isP? isQs? (force t) = no  ())
isCase? isP? isQs? (delay t) = no  ())
isCase? isP? isQs? (con x) = no  ())
isCase? isP? isQs? (constr i xs) = no  ())
isCase? isP? isQs? (case t ts) with (isP? t) ×-dec (isQs? ts)
...                                            | no ¬pqs = no λ { (iscase p qs)  ¬pqs (p , qs)}
...                                            | yes (p , qs) = yes (iscase p qs)
isCase? isP? isQs? (builtin b) = no  ())
isCase? isP? isQs? error = no  ())

data isBuiltin {X : Set} : (X )  Set where
  isbuiltin : (b : Builtin)  isBuiltin {X} (builtin b)
isBuiltin? : {X : Set}  Decidable (isBuiltin {X})
isBuiltin? (` x) = no  ())
isBuiltin? (ƛ t) = no  ())
isBuiltin? (t · t₁) = no  ())
isBuiltin? (force t) = no  ())
isBuiltin? (delay t) = no  ())
isBuiltin? (con x) = no  ())
isBuiltin? (constr i xs) = no  ())
isBuiltin? (case t ts) = no  ())
isBuiltin? (builtin b) = yes (isbuiltin b)
isBuiltin? error = no  ())

data isError {X : Set} : (X )  Set where
  iserror : isError {X} error
isError? : {X : Set}  Decidable (isError {X})
isError? (` x) = no  ())
isError? (ƛ t) = no  ())
isError? (t · t₁) = no  ())
isError? (force t) = no  ())
isError? (delay t) = no  ())
isError? (con x) = no  ())
isError? (constr i xs) = no  ())
isError? (case t ts) = no  ())
isError? (builtin b) = no  ())
isError? error = yes iserror

Some basic views that will match any Term, to be used for “wildcard” parts of the pattern.

data isTerm { X : Set } : (X )  Set where
  isterm : (t : X )  isTerm t
isTerm? : {X : Set}  Decidable (isTerm {X})
isTerm? t = yes (isterm t)

data allTerms { X : Set } : List (X )  Set where
  allterms : (ts : List (X ))  allTerms ts
allTerms? : {X : Set}  Decidable (allTerms {X})
allTerms? ts = yes (allterms ts)

An Example

data TestPat {X : Set} : (X )  Set where
  tp : (t : X ) (ts ts₂ : List (X ))  TestPat {X} (case (case t ts) ts₂)
isTestPat? : {X : Set}  Decidable (TestPat {X})
isTestPat? v with isCase? (isCase? isTerm? allTerms?) allTerms? v
... | yes (iscase (iscase (isterm t) (allterms ts)) (allterms ts₁)) = yes (tp t ts ts₁)
... | no ¬tp = no λ { (tp t ts ts₂)  ¬tp (iscase (iscase (isterm t) (allterms ts)) (allterms ts₂)) }