microsoft / microsoft/z3guide

Probably wrong definition of subtyping

Open
#175 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
JavaScript
Stars
123
Forks
34
Avg merge
3h 48m
Merged PRs (30d)
4

Description

I think = should be => in the following three lines.

https://github.com/microsoft/z3guide/blob/4333097e04327dff31664884ec20b1ee1f85cd7b/website/docs-smtlib/01%20-%20logic/05%20-%20Quantifiers.md?plain=1#L21

https://github.com/microsoft/z3guide/blob/4333097e04327dff31664884ec20b1ee1f85cd7b/website/docs-smtlib/01%20-%20logic/05%20-%20Quantifiers.md?plain=1#L27

https://github.com/microsoft/z3guide/blob/4333097e04327dff31664884ec20b1ee1f85cd7b/website/docs-smtlib/01%20-%20logic/05%20-%20Quantifiers.md?plain=1#L30

Otherwise, the specification prohibits the existence of non-root types. Specifically, the following program (where the only interesting lines are the last three lines) prints sat unsat.

(declare-sort Type)
(declare-fun subtype (Type Type) Bool)
(declare-fun array-of (Type) Type)
(assert (forall ((x Type)) (subtype x x)))
(assert (forall ((x Type) (y Type) (z Type))
          (= (and (subtype x y) (subtype y z)) 
              (subtype x z)))) 
(assert (forall ((x Type) (y Type))
          (= (and (subtype x y) (subtype y x)) 
              (= x y))))
(assert (forall ((x Type) (y Type) (z Type))
          (= (and (subtype x y) (subtype x z)) 
              (or (subtype y z) (subtype z y))))) 
(assert (forall ((x Type) (y Type))
          (= (subtype x y) 
              (subtype (array-of x) (array-of y)))))
(declare-const root-type Type)
(assert (forall ((x Type)) (subtype x root-type)))
(check-sat)
(declare-const another-type Type)
(assert (not (= root-type another-type)))
(check-sat)

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Open website/docs-smtlib/01 - logic/05 - Quantifiers.md at the three linked lines and compare the subtype definitions with the SMT-LIB example in the issue. Verify the example's satisfiability results, then update the notation and confirm the rendered documentation matches the intended subtype axioms.

Written by the indexing model from the issue text.

Assessment

Domain
documentation
Issue type
Documentation
Difficulty
1/5
Estimated time
Under an hour
Activity status
Stale
Clarity
Clearly specified
Newbie friendliness
50/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.