Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Desugaring Galois connection #52

Closed
20 tasks done
rolyp opened this issue Sep 19, 2020 · 2 comments
Closed
20 tasks done

Desugaring Galois connection #52

rolyp opened this issue Sep 19, 2020 · 2 comments

Comments

@rolyp
Copy link
Collaborator

rolyp commented Sep 19, 2020

Show how the fwd and bwd desugaring slicing rules form a Galois connection (for a given program). Tasks:

Done/dropped:

  • sanity-check “ambient computation” in desugarBwd – needs further thought, but basically ok
  • helper macros for things like totaliseGeq
  • consolidate list-comp-gen proofs using new list-gen lemma
  • roll out macros to proofs
  • purge superfluous x-refs
  • simplify list comprehension proofs to remove done and list-comp-last
  • macroise desugaring overloads
  • check list-comp-gen bwd – can this be made more symmetric with fwd rule?
  • define functions desugarFwd_s, desugarBwd_s in terms of the corresponding relations, similar to eval
  • theorem stating that the two functions form a Galois connection
  • drop done sentinel in list comprehension syntax and allow [s | ε] instead
  • ensure eq rather than geq used for (meta-) “pattern-matching”
  • trace analogues as subscripts in backward desugaring relations
  • new symbol for desugaring relations that have expression or continuation on the left
  • define Galois connection notation f ⊣ g in terms of composites (f after g) and (g after f) – see def:core-language:gc
  • define \Below{v} notation using
  • prove “part 1” (fwd after bwd is increasing)
  • prove “part 2” (bwd after fwd is increasing)
  • identify any other theorems we need as go along, e.g. monotonicity
  • state GC theorems for:
    • desugar for list rest
    • totalise
    • desugar for clauses
    • desugar for single clause (judgements p, κ \desugar σ and \vec{p}, e \desugar σ)

Other useful points of reference:

  • “set of paths in a term” exposition in 3.2 of FPTETW
  • methodology summarised in 2.3 of IFPTETW
@rolyp
Copy link
Collaborator Author

rolyp commented Nov 30, 2020

@min-nguyen Notes from Friday. Will add some tasks above. Suggest referring to our ICFP 2017 paper to look at how we set up the Galois connections there.

Lattices; in the finite case, can always understand in terms of a powerset:
Untitled 34
Partial order (actually lattice) of slices of a fixed expression:
Untitled 32
Functions eval_fwd and eval_bwd defined as forward and backwards slicing relations, domain-restricted to slices of a fixed expression:
Untitled 33

@rolyp
Copy link
Collaborator Author

rolyp commented Apr 7, 2021

@min-nguyen I’ve defined some of the notation we discussed yesterday (see bullet list above). That should be enough to get you started.

@rolyp rolyp self-assigned this Apr 10, 2021
@rolyp rolyp closed this as completed Apr 10, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants