1 (*********************************************************************************************************************************)
4 (* This module is the "top level" for extraction *)
6 (*********************************************************************************************************************************)
8 Require Import Coq.Strings.Ascii.
9 Require Import Coq.Strings.String.
10 Require Import Coq.Lists.List.
12 Require Import Preamble.
13 Require Import General.
15 Require Import NaturalDeduction.
17 Require Import HaskKinds.
18 Require Import HaskLiterals.
19 Require Import HaskTyCons.
20 Require Import HaskCoreVars.
21 Require Import HaskCoreTypes.
22 Require Import HaskCore.
23 Require Import HaskWeakVars.
24 Require Import HaskWeakTypes.
25 Require Import HaskWeak.
26 Require Import HaskStrongTypes.
27 Require Import HaskStrong.
28 Require Import HaskProof.
29 Require Import HaskCoreToWeak.
30 Require Import HaskWeakToStrong.
31 Require Import HaskStrongToProof.
32 Require Import HaskProofToLatex.
33 Require Import HaskStrongToWeak.
34 Require Import HaskWeakToCore.
35 Require Import HaskProofToStrong.
37 Require Import HaskFlattener.
39 Open Scope string_scope.
40 Extraction Language Haskell.
42 (*Extract Inductive vec => "([])" [ "([])" "(:)" ].*)
43 (*Extract Inductive Tree => "([])" [ "([])" "(:)" ].*)
44 (*Extract Inlined Constant map => "Prelude.map".*)
46 (* I try to reuse Haskell types mostly to get the "deriving Show" aspect *)
47 Extract Inductive option => "Prelude.Maybe" [ "Prelude.Just" "Prelude.Nothing" ].
48 Extract Inductive list => "([])" [ "([])" "(:)" ].
49 Extract Inductive string => "Prelude.String" [ "[]" "(:)" ].
50 Extract Inductive prod => "(,)" [ "(,)" ].
51 Extract Inductive sum => "Prelude.Either" [ "Prelude.Left" "Prelude.Right" ].
52 Extract Inductive sumbool => "Prelude.Bool" [ "Prelude.True" "Prelude.False" ].
53 Extract Inductive bool => "Prelude.Bool" [ "Prelude.True" "Prelude.False" ].
54 Extract Inductive unit => "()" [ "()" ].
55 Extract Inlined Constant string_dec => "(==)".
56 Extract Inlined Constant ascii_dec => "(==)".
58 Extract Inductive ascii => "Char" [ "you_forgot_to_patch_coq" ] "you_forgot_to_patch_coq".
59 Extract Constant zero => "'\000'".
60 Extract Constant one => "'\001'".
61 Extract Constant shift => "shiftAscii".
63 Unset Extraction Optimize.
64 Unset Extraction AutoInline.
66 Variable Name : Type. Extract Inlined Constant Name => "Name.Name".
67 Variable mkSystemName : Unique -> string -> nat -> Name.
68 Extract Inlined Constant mkSystemName =>
69 "(\u s d -> Name.mkSystemName u (OccName.mkOccName (OccName.varNameDepth (nat2int d)) s))".
70 Variable mkTyVar : Name -> Kind -> CoreVar.
71 Extract Inlined Constant mkTyVar => "(\n k -> Var.mkTyVar n (kindToCoreKind k))".
72 Variable mkCoVar : Name -> CoreType -> CoreType -> CoreVar.
73 Extract Inlined Constant mkCoVar => "(\n t1 t2 -> Var.mkCoVar n (Coercion.mkCoKind t1 t2))".
74 Variable mkExVar : Name -> CoreType -> CoreVar.
75 Extract Inlined Constant mkExVar => "Id.mkLocalId".
78 Context (ce:@CoreExpr CoreVar).
80 Definition Γ : TypeEnv := nil.
82 Definition Δ : CoercionEnv Γ := nil.
84 Definition φ : TyVarResolver Γ :=
85 fun cv => Error ("unbound tyvar: " +++ toString (cv:CoreVar)).
86 (*fun tv => error ("tried to get the representative of an unbound tyvar:" +++ (getCoreVarOccString tv)).*)
88 Definition ψ : CoVarResolver Γ Δ :=
89 fun cv => Error ("tried to get the representative of an unbound covar!" (*+++ (getTypeVarOccString cv)*)).
91 (* We need to be able to resolve unbound exprvars, but we can be sure their types will have no
92 * free tyvars in them *)
93 Definition ξ (cv:CoreVar) : LeveledHaskType Γ ★ :=
94 match coreVarToWeakVar cv with
95 | WExprVar wev => match weakTypeToTypeOfKind φ wev ★ with
96 | Error s => Prelude_error ("Error converting weakType of top-level variable "+++
97 toString cv+++": " +++ s)
100 | WTypeVar _ => Prelude_error "top-level xi got a type variable"
101 | WCoerVar _ => Prelude_error "top-level xi got a coercion variable"
104 Definition header : string :=
105 "\documentclass{article}"+++eol+++
106 "\usepackage{amsmath}"+++eol+++
107 "\usepackage{amssymb}"+++eol+++
108 "\usepackage{proof}"+++eol+++
109 "\usepackage{trfrac} % http://www.utdallas.edu/~hamlen/trfrac.sty"+++eol+++
110 "\def\code#1#2{\Box_{#1} #2}"+++eol+++
111 "\usepackage[paperwidth=\maxdimen,paperheight=\maxdimen]{geometry}"+++eol+++
112 "\usepackage[tightpage,active]{preview}"+++eol+++
113 "\begin{document}"+++eol+++
114 "\setlength\PreviewBorder{5pt}"+++eol.
116 Definition footer : string :=
117 eol+++"\end{document}"+++
120 (* core-to-string (-dcoqpass) *)
121 Definition coreToStringExpr' (ce:@CoreExpr CoreVar) : ???string :=
122 addErrorMessage ("input CoreSyn: " +++ toString ce)
123 (addErrorMessage ("input CoreType: " +++ toString (coreTypeOfCoreExpr ce)) (
124 coreExprToWeakExpr ce >>= fun we =>
125 addErrorMessage ("WeakExpr: " +++ toString we)
126 ((addErrorMessage ("CoreType of WeakExpr: " +++ toString (coreTypeOfCoreExpr (weakExprToCoreExpr we)))
127 ((weakTypeOfWeakExpr we) >>= fun t =>
128 (addErrorMessage ("WeakType: " +++ toString t)
129 ((weakTypeToTypeOfKind φ t ★) >>= fun τ =>
130 addErrorMessage ("HaskType: " +++ toString τ)
131 ((weakExprToStrongExpr Γ Δ φ ψ ξ (fun _ => false) τ nil we) >>= fun e =>
132 OK (eol+++eol+++eol+++
133 "\begin{preview}"+++eol+++
135 toString (nd_ml_toLatexMath (@expr2proof _ _ _ _ _ _ e))+++
137 "\end{preview}"+++eol+++eol+++eol)
140 Definition coreToStringExpr (ce:@CoreExpr CoreVar) : string :=
141 match coreToStringExpr' ce with
143 | Error s => Prelude_error s
146 Definition coreToStringBind (binds:@CoreBind CoreVar) : string :=
148 | CoreNonRec _ e => coreToStringExpr e
149 | CoreRec lbe => fold_left (fun x y => x+++eol+++eol+++y) (map (fun x => coreToStringExpr (snd x)) lbe) ""
152 Definition coqPassCoreToString (lbinds:list (@CoreBind CoreVar)) : string :=
154 (fold_left (fun x y => x+++eol+++eol+++y) (map coreToStringBind lbinds) "")
158 (* core-to-core (-fcoqpass) *)
161 Definition mkWeakTypeVar (u:Unique)(k:Kind) : WeakTypeVar :=
162 weakTypeVar (mkTyVar (mkSystemName u "tv" O) k) k.
163 Definition mkWeakCoerVar (u:Unique)(k:Kind)(t1 t2:WeakType) : WeakCoerVar :=
164 weakCoerVar (mkCoVar (mkSystemName u "cv" O) (weakTypeToCoreType t1) (weakTypeToCoreType t2)) k t1 t2.
165 Definition mkWeakExprVar (u:Unique)(t:WeakType) : WeakExprVar :=
166 weakExprVar (mkExVar (mkSystemName u "ev" O) (weakTypeToCoreType t)) t.
168 Context (hetmet_brak : WeakExprVar).
169 Context (hetmet_esc : WeakExprVar).
170 Context (hetmet_flatten : WeakExprVar).
171 Context (hetmet_unflatten : WeakExprVar).
172 Context (hetmet_flattened_id : WeakExprVar).
173 Context (uniqueSupply : UniqSupply).
175 Definition useUniqueSupply {T}(ut:UniqM T) : ???T :=
178 f uniqueSupply >>= fun x => OK (snd x)
181 Definition larger : forall ln:list nat, { n:nat & forall n', In n' ln -> gt n n' }.
187 destruct IHln as [n pf].
188 exists (plus (S n) a).
192 fold (@In _ n' ln) in H.
197 Definition FreshNat : @FreshMonad nat.
198 refine {| FMT := fun T => nat -> prod nat T
204 set (larger tl) as q.
205 destruct q as [n' pf].
211 refine {| returnM := fun a (v:a) => _ |}.
212 intro n. exact (n,v).
215 destruct q as [n' v].
220 Definition unFresh {T} : @FreshM _ FreshNat T -> T.
229 Definition coreVarToWeakExprVarOrError cv :=
230 match coreVarToWeakVar cv with
232 | _ => Prelude_error "IMPOSSIBLE"
235 Definition curry {Γ}{Δ}{a}{s}{Σ}{lev} :
237 [ Γ > Δ > Σ |- [a ---> s @@ lev ] ]
238 [ Γ > Δ > Σ,,[a @@ lev] |- [ s @@ lev ] ].
239 eapply nd_comp; [ idtac | eapply nd_rule; apply (@RApp Γ Δ Σ [a@@lev] a s lev) ].
240 eapply nd_comp; [ apply nd_rlecnac | idtac ].
247 Definition fToC1 {Γ}{Δ}{a}{s}{lev} :
248 ND Rule [] [ Γ > Δ > [ ] |- [a ---> s @@ lev ] ] ->
249 ND Rule [] [ Γ > Δ > [a @@ lev] |- [ s @@ lev ] ].
253 eapply nd_comp; [ idtac | eapply nd_rule; eapply RArrange; apply RCanL ].
257 Definition fToC2 {Γ}{Δ}{a1}{a2}{s}{lev} :
258 ND Rule [] [ Γ > Δ > [] |- [a1 ---> (a2 ---> s) @@ lev ] ] ->
259 ND Rule [] [ Γ > Δ > [a1 @@ lev],,[a2 @@ lev] |- [ s @@ lev ] ].
273 Section coqPassCoreToCore.
275 (hetmet_brak : CoreVar)
276 (hetmet_esc : CoreVar)
277 (hetmet_flatten : CoreVar)
278 (hetmet_unflatten : CoreVar)
279 (hetmet_flattened_id : CoreVar)
280 (uniqueSupply : UniqSupply)
281 (lbinds:list (@CoreBind CoreVar))
282 (hetmet_PGArrowTyCon : TyFun)
283 (hetmet_pga_id : CoreVar)
284 (hetmet_pga_comp : CoreVar)
285 (hetmet_pga_first : CoreVar)
286 (hetmet_pga_second : CoreVar)
287 (hetmet_pga_cancell : CoreVar)
288 (hetmet_pga_cancelr : CoreVar)
289 (hetmet_pga_uncancell : CoreVar)
290 (hetmet_pga_uncancelr : CoreVar)
291 (hetmet_pga_assoc : CoreVar)
292 (hetmet_pga_unassoc : CoreVar)
293 (hetmet_pga_copy : CoreVar)
294 (hetmet_pga_drop : CoreVar)
295 (hetmet_pga_swap : CoreVar)
296 (hetmet_pga_applyl : CoreVar)
297 (hetmet_pga_applyr : CoreVar)
298 (hetmet_pga_curryl : CoreVar)
299 (hetmet_pga_curryr : CoreVar)
302 Definition ga_unit TV : RawHaskType TV ★ := @TyFunApp TV UnitTyCon nil ★ TyFunApp_nil.
303 Definition ga_prod TV (a b:RawHaskType TV ★) : RawHaskType TV ★ :=
304 TApp (TApp (@TyFunApp TV PairTyCon nil _ TyFunApp_nil) a) b.
305 Definition ga_type {TV}(a:RawHaskType TV ECKind)(b c:RawHaskType TV ★) : RawHaskType TV ★ :=
306 TApp (TApp (TApp (@TyFunApp TV
308 nil _ TyFunApp_nil) a) b) c.
309 Definition ga := @ga_mk ga_unit ga_prod (@ga_type).
311 Definition ga_type' {Γ}(a:HaskType Γ ECKind)(b c:HaskType Γ ★) : HaskType Γ ★ :=
312 fun TV ite => TApp (TApp (TApp (@TyFunApp TV
314 nil _ TyFunApp_nil) (a TV ite)) (b TV ite)) (c TV ite).
316 Definition mkGlob2' {Γ}{κ₁}{κ₂}(f:HaskType Γ κ₁ -> HaskType Γ κ₂ -> HaskType Γ ★) :
317 IList Kind (fun κ : Kind => HaskType Γ κ) (κ₁::κ₂::nil) -> HaskType Γ ★.
324 Definition mkGlob2 {Γ}{Δ}{l}{κ₁}{κ₂}(cv:CoreVar)(f:HaskType Γ κ₁ -> HaskType Γ κ₂ -> HaskType Γ ★) x y
325 : ND Rule [] [ Γ > Δ > [] |- [f x y @@ l] ].
327 refine (@RGlobal Γ Δ l
328 {| glob_wv := coreVarToWeakExprVarOrError cv
329 ; glob_kinds := κ₁ :: κ₂ :: nil
330 ; glob_tf := mkGlob2'(Γ:=Γ) f
331 |} (ICons _ _ x (ICons _ _ y INil))).
334 Definition mkGlob3' {Γ}{κ₁}{κ₂}{κ₃}(f:HaskType Γ κ₁ -> HaskType Γ κ₂ -> HaskType Γ κ₃ -> HaskType Γ ★) :
335 IList Kind (fun κ : Kind => HaskType Γ κ) (κ₁::κ₂::κ₃::nil) -> HaskType Γ ★.
343 Definition mkGlob3 {Γ}{Δ}{l}{κ₁}{κ₂}{κ₃}(cv:CoreVar)(f:HaskType Γ κ₁ -> HaskType Γ κ₂ -> HaskType Γ κ₃ -> HaskType Γ ★) x y z
344 : ND Rule [] [ Γ > Δ > [] |- [f x y z @@ l] ].
346 refine (@RGlobal Γ Δ l
347 {| glob_wv := coreVarToWeakExprVarOrError cv
348 ; glob_kinds := κ₁ :: κ₂ :: κ₃ :: nil
349 ; glob_tf := mkGlob3'(Γ:=Γ) f
350 |} (ICons _ _ x (ICons _ _ y (ICons _ _ z INil)))).
353 Definition mkGlob4' {Γ}{κ₁}{κ₂}{κ₃}{κ₄}(f:HaskType Γ κ₁ -> HaskType Γ κ₂ -> HaskType Γ κ₃ -> HaskType Γ κ₄ -> HaskType Γ ★) :
354 IList Kind (fun κ : Kind => HaskType Γ κ) (κ₁::κ₂::κ₃::κ₄::nil) -> HaskType Γ ★.
363 Definition mkGlob4 {Γ}{Δ}{l}{κ₁}{κ₂}{κ₃}{κ₄}(cv:CoreVar)(f:HaskType Γ κ₁ -> HaskType Γ κ₂ -> HaskType Γ κ₃ -> HaskType Γ κ₄ -> HaskType Γ ★) x y z q
364 : ND Rule [] [ Γ > Δ > [] |- [f x y z q @@ l] ].
366 refine (@RGlobal Γ Δ l
367 {| glob_wv := coreVarToWeakExprVarOrError cv
368 ; glob_kinds := κ₁ :: κ₂ :: κ₃ :: κ₄ :: nil
369 ; glob_tf := mkGlob4'(Γ:=Γ) f
370 |} (ICons _ _ x (ICons _ _ y (ICons _ _ z (ICons _ _ q INil))))).
373 Definition gat {Γ}(x:Tree ??(HaskType Γ ★)) := @ga_mk_tree ga_unit ga_prod _ x.
375 Instance my_ga : garrow ga_unit ga_prod (@ga_type) :=
376 { ga_id := fun Γ Δ ec l a => mkGlob2 hetmet_pga_id (fun ec a => ga_type' ec a a) ec (gat a)
377 ; ga_cancelr := fun Γ Δ ec l a => mkGlob2 hetmet_pga_cancelr (fun ec a => ga_type' ec _ a) ec (gat a)
378 ; ga_cancell := fun Γ Δ ec l a => mkGlob2 hetmet_pga_cancell (fun ec a => ga_type' ec _ a) ec (gat a)
379 ; ga_uncancelr := fun Γ Δ ec l a => mkGlob2 hetmet_pga_uncancelr (fun ec a => ga_type' ec a _) ec (gat a)
380 ; ga_uncancell := fun Γ Δ ec l a => mkGlob2 hetmet_pga_uncancell (fun ec a => ga_type' ec a _) ec (gat a)
381 ; ga_assoc := fun Γ Δ ec l a b c => mkGlob4 hetmet_pga_assoc (fun ec a b c => ga_type' ec _ _) ec (gat a) (gat b) (gat c)
382 ; ga_unassoc := fun Γ Δ ec l a b c => mkGlob4 hetmet_pga_unassoc (fun ec a b c => ga_type' ec _ _) ec (gat a) (gat b) (gat c)
383 ; ga_swap := fun Γ Δ ec l a b => mkGlob3 hetmet_pga_swap (fun ec a b => ga_type' ec _ _) ec (gat a) (gat b)
384 ; ga_drop := fun Γ Δ ec l a => mkGlob2 hetmet_pga_drop (fun ec a => ga_type' ec _ _) ec (gat a)
385 ; ga_copy := fun Γ Δ ec l a => mkGlob2 hetmet_pga_copy (fun ec a => ga_type' ec _ _) ec (gat a)
386 ; ga_first := fun Γ Δ ec l a b x => fToC1 (mkGlob4 hetmet_pga_first (fun ec a b c => _) ec (gat a) (gat b) (gat x))
387 ; ga_second := fun Γ Δ ec l a b x => fToC1 (mkGlob4 hetmet_pga_second (fun ec a b c => _) ec (gat a) (gat b) (gat x))
388 ; ga_comp := fun Γ Δ ec l a b c => fToC2 (mkGlob4 hetmet_pga_comp (fun ec a b c => _) ec (gat a) (gat b) (gat c))
389 (* ; ga_lit := fun Γ Δ ec l a => nd_rule (RGlobal _ _ _ _ (coreVarToWeakExprVarOrError hetmet_pga_lit))*)
390 (* ; ga_curry := fun Γ Δ ec l a => nd_rule (RGlobal _ _ _ _ (coreVarToWeakExprVarOrError hetmet_pga_curry))*)
391 (* ; ga_apply := fun Γ Δ ec l a => nd_rule (RGlobal _ _ _ _ (coreVarToWeakExprVarOrError hetmet_pga_apply))*)
392 (* ; ga_kappa := fun Γ Δ ec l a => fToC1 (nd_rule (RGlobal _ _ _ _ (coreVarToWeakExprVarOrError hetmet_pga_kappa)))*)
393 ; ga_lit := fun Γ Δ ec l a => Prelude_error "ga_lit"
394 ; ga_curry := fun Γ Δ ec l a b c => Prelude_error "ga_curry"
395 ; ga_apply := fun Γ Δ ec l a b c => Prelude_error "ga_apply"
396 ; ga_kappa := fun Γ Δ ec l a => Prelude_error "ga_kappa"
399 Definition hetmet_brak' := coreVarToWeakExprVarOrError hetmet_brak.
400 Definition hetmet_esc' := coreVarToWeakExprVarOrError hetmet_esc.
401 Definition hetmet_flatten' := coreVarToWeakExprVarOrError hetmet_flatten.
402 Definition hetmet_unflatten' := coreVarToWeakExprVarOrError hetmet_unflatten.
403 Definition hetmet_flattened_id' := coreVarToWeakExprVarOrError hetmet_flattened_id.
405 Definition coreToCoreExpr' (ce:@CoreExpr CoreVar) : ???(@CoreExpr CoreVar) :=
406 addErrorMessage ("input CoreSyn: " +++ toString ce)
407 (addErrorMessage ("input CoreType: " +++ toString (coreTypeOfCoreExpr ce)) (
408 coreExprToWeakExpr ce >>= fun we =>
409 addErrorMessage ("WeakExpr: " +++ toString we)
410 ((addErrorMessage ("CoreType of WeakExpr: " +++ toString (coreTypeOfCoreExpr (weakExprToCoreExpr we)))
411 ((weakTypeOfWeakExpr we) >>= fun t =>
412 (addErrorMessage ("WeakType: " +++ toString t)
413 ((weakTypeToTypeOfKind φ t ★) >>= fun τ =>
415 ((weakExprToStrongExpr Γ Δ φ ψ ξ (fun _ => true) τ nil we) >>= fun e =>
417 (addErrorMessage ("HaskStrong...")
418 (let haskProof := flatten_proof hetmet_flatten' hetmet_unflatten'
419 hetmet_flattened_id' my_ga (@expr2proof _ _ _ _ _ _ e)
420 in (* insert HaskProof-to-HaskProof manipulations here *)
421 OK ((@proof2expr nat _ FreshNat _ _ _ _ (fun _ => Prelude_error "unbound unique") _ haskProof) O)
423 (snd e') >>= fun e'' =>
424 strongExprToWeakExpr hetmet_brak' hetmet_esc'
425 mkWeakTypeVar mkWeakCoerVar mkWeakExprVar uniqueSupply
428 OK (weakExprToCoreExpr q)
431 Definition coreToCoreExpr (ce:@CoreExpr CoreVar) : (@CoreExpr CoreVar) :=
432 match coreToCoreExpr' ce with
434 | Error s => Prelude_error s
437 Definition coreToCoreBind (binds:@CoreBind CoreVar) : @CoreBind CoreVar :=
439 | CoreNonRec v e => let e' := coreToCoreExpr e in CoreNonRec (setVarType v (coreTypeOfCoreExpr e')) e'
441 | CoreRec lbe => CoreRec (map (fun ve => match ve with (v,e) => (v,coreToCoreExpr e) end) lbe)
442 (* FIXME: doesn't deal with the case where top level recursive binds change type *)
444 match coreToCoreExpr (CoreELet lbe) (CoreELit HaskMachNullAddr) with
445 | CoreELet (CoreRec lbe') => lbe'
447 ("coreToCoreExpr was given a letrec, " +++
448 "but returned something that wasn't a letrec: " +++ toString x)
453 Definition coqPassCoreToCore' (lbinds:list (@CoreBind CoreVar)) : list (@CoreBind CoreVar) :=
454 map coreToCoreBind lbinds.
456 End coqPassCoreToCore.
458 Definition coqPassCoreToCore
459 (hetmet_brak : CoreVar)
460 (hetmet_esc : CoreVar)
461 (hetmet_flatten : CoreVar)
462 (hetmet_unflatten : CoreVar)
463 (hetmet_flattened_id : CoreVar)
464 (uniqueSupply : UniqSupply)
465 (lbinds:list (@CoreBind CoreVar))
466 (hetmet_PGArrowTyCon : TyFun)
467 (hetmet_pga_id : CoreVar)
468 (hetmet_pga_comp : CoreVar)
469 (hetmet_pga_first : CoreVar)
470 (hetmet_pga_second : CoreVar)
471 (hetmet_pga_cancell : CoreVar)
472 (hetmet_pga_cancelr : CoreVar)
473 (hetmet_pga_uncancell : CoreVar)
474 (hetmet_pga_uncancelr : CoreVar)
475 (hetmet_pga_assoc : CoreVar)
476 (hetmet_pga_unassoc : CoreVar)
477 (hetmet_pga_copy : CoreVar)
478 (hetmet_pga_drop : CoreVar)
479 (hetmet_pga_swap : CoreVar)
480 (hetmet_pga_applyl : CoreVar)
481 (hetmet_pga_applyr : CoreVar)
482 (hetmet_pga_curryl : CoreVar)
483 (hetmet_pga_curryr : CoreVar) : list (@CoreBind CoreVar) :=