Skip to content

New mode constraint solver supporting morphisms#160

Closed
riaqn wants to merge 50 commits intoocaml-flambda:mainfrom
riaqn:new-resolver
Closed

New mode constraint solver supporting morphisms#160
riaqn wants to merge 50 commits intoocaml-flambda:mainfrom
riaqn:new-resolver

Conversation

@riaqn
Copy link
Copy Markdown
Contributor

@riaqn riaqn commented Apr 4, 2023

Based on #138

This PR adds a new mode constraint solver to the type checker. The new solver supports morphisms between mode axes. An example of such morphisms is unique_to_linear :

u2l unique = once
u2l shared = many

The new solver allows us to apply such morphisms to mode variables, and use the resulted variables in submode constraints. All morphisms needs to be monotone and having appropriate left/right adjoint for the solver to work. We slightly extend the solver so that antitone morphisms can also work with some limitations.

Some other notable features/changes:

  • In light of the incoming seven hundred mode axes, and how costy it would be to call submode m0.x m1.x for each axis x, we introduce the product object in the category so that submoding relation can be expressed on the product as a whole. Note that axes of opposite polarities can't be product together. As a result, currently locality and linearity are packed into the product object, while uniqueness (being of negative polarity) is standalone.
  • Previously the 3-valued locality is represented as its image into the 2-valued locality via mappings. It is now natively represented, together with all mappings between 2- and 3-values in a chain of adjunction.
  • After talking to @stedolan , vlower is no longer compressed. It was compressed in the hope for an optimization - but that optimization turned out to be hard to implement in ocaml. Compressing vlower would also cause explosion problem once morphisms are introduced.
  • As before, the lower bound of variables are not precise, but updated on demand. The original update method no longer works with morphisms in circular paths. The update method we adopt is to repreat submode_vc until it succeeds.
  • There was a circular dependency between mode.ml and types.ml. Previously (in the uniqueness PR) it was solved by preceeding type definitions which has became dirtier with bigger types. This is now solved by solver.ml having its own implementation of logging (which is minimalistic).

@riaqn riaqn force-pushed the new-resolver branch 2 times, most recently from 1f1ed32 to 1e7d3db Compare April 5, 2023 12:17
@riaqn riaqn marked this pull request as ready for review April 5, 2023 12:17
@riaqn riaqn mentioned this pull request Apr 17, 2023
@riaqn riaqn force-pushed the new-resolver branch 2 times, most recently from f871e35 to f485c6d Compare April 18, 2023 12:12
@riaqn
Copy link
Copy Markdown
Contributor Author

riaqn commented Jun 15, 2023

This is now rebased and better abstracted (with the *_intf.ml paradigm). It needs to be rebased on the uniqueness PR and cleaned-up before ready for review; I'm turning this into a draft.

@riaqn
Copy link
Copy Markdown
Contributor Author

riaqn commented Jun 28, 2023

Reminder to myself that I should expose the two products, Comonadic and Monadic, and expose content of Value.t as:

'd t = {
 comonadic: 'd Comonadic.t;
 monadic: 'd Monadic.t;
}

and I need to implement what's described in #138 (comment)

@riaqn
Copy link
Copy Markdown
Contributor Author

riaqn commented Jul 13, 2023

Rebased on top of the latest uniqueness PR.

This is functional but will need clean up.

@riaqn
Copy link
Copy Markdown
Contributor Author

riaqn commented Aug 20, 2023

This is superseded by oxcaml/oxcaml#1760.

@riaqn riaqn closed this Aug 20, 2023
@riaqn riaqn deleted the new-resolver branch August 20, 2023 13:18
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

Successfully merging this pull request may close these issues.

2 participants