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

Support for Any-length BitVectors #334

Open
shingarov opened this issue Jul 16, 2024 · 0 comments
Open

Support for Any-length BitVectors #334

shingarov opened this issue Jul 16, 2024 · 0 comments
Assignees

Comments

@shingarov
Copy link
Owner

PR #231 introduced initial support for BitVector sorts. This has allowed us to conduct first successful experiments in formalization of Tinyrossa.

Large-scale application of this code to complete refinement-type formalization of Isla, is limited by two problems.

  1. Isla uses many more lengths (almost every length from 1 to 128?) than the predefined small set in PR 231. The problem is even quadratic, O²(128) because of ops like Z3_mk_concat and Z3_mk_extract.
  2. With things like Z3_mk_extract you don't even know the resulting length (or at least it's not explicit in the static type declaration; so it's like "dependent sorts"). Isla makes heavy use of "any-length bitvector" sort. In fact even when some x is trivially known to be, say, %bv32, most often it's declared as %bv, relying on type inference. This is true also for function types (both of "fun defs" and "externs"), resulting in extensive type-instantiation.

The present Issue calls to implement these Any-Length BitVectors. The core machinery is already in place (MA already has fully-general Hindley–Milner sorts and polymorphism-as-naturality); but we rely on #332 so we (and downstream Isla code) can regard it as stable API. My estimation is that the changes needed here, can stay local to Sprite and not affect Fixpoint at all.

@shingarov shingarov self-assigned this Jul 16, 2024
shingarov added a commit to shingarov/ISA that referenced this issue Jul 16, 2024
…it elaborateIn:

We are trying to abandon this approach in view of
shingarov/MachineArithmetic#334
shingarov added a commit to shingarov/ISA that referenced this issue Aug 14, 2024
We are trying to abandon this approach in view of
shingarov/MachineArithmetic#334
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant