jaccokrijnen / plutus-cert

0 stars 2 forks source link

Big-step: support non-strict let bindings #11

Open jaccokrijnen opened 1 year ago

jaccokrijnen commented 1 year ago

Currently:

with eval_bindings_nonrec : Term -> Term -> nat -> Prop :=
  ...
  | E_Let_TermBind : forall s x T t1 j1 v1 j2 v2 bs t0,                                                                                                                                                            
      t1 =[j1]=> v1 ->
      ~ is_error v1 ->         
      <{ [v1 / x] ({Let NonRec bs t0}) }> =[j2]=>nr v2 ->
      Let NonRec ((TermBind s (VarDecl x T) t1) :: bs) t0 =[j1 + 1 + j2]=>nr v2 
  ...
jaccokrijnen commented 1 year ago

This will also impact the definition of RG:

(** RG = Interpretation of type contexts as logically related term environments *)
Inductive RG (rho : tymapping) (k : nat) : tass -> env -> env -> Prop :=
  | RG_nil :
      RG rho k nil nil nil
  | RG_cons : forall x T v1 v2 c e1 e2,
      RV k T rho v1 v2 ->
      normal_Ty T ->
      RG rho k c e1 e2 ->
      RG rho k ((x, T) :: c) ((x, v1) :: e1) ((x, v2) :: e2).

The dead-code proof needs to construct related gamma substitutions, in the case of strict we know from the big-step rule that the bound term terminates with a value, and use that to construct related gamma substitutions. In this case we don't know that, but we still want to construct related substitutions. Would it be enough to change the RV argument to RC? What would break?