Skip to content

Local rewrites#2384

Merged
facundominguez merged 39 commits into
ucsd-progsys:developfrom
AlecsFerra:develop
Oct 18, 2024
Merged

Local rewrites#2384
facundominguez merged 39 commits into
ucsd-progsys:developfrom
AlecsFerra:develop

Conversation

@AlecsFerra

@AlecsFerra AlecsFerra commented Oct 11, 2024

Copy link
Copy Markdown
Contributor

@AlecsFerra

Copy link
Copy Markdown
Contributor Author

For some reason the test SKIDC.hs works locally but hangs on circleci

@AlecsFerra AlecsFerra force-pushed the develop branch 2 times, most recently from 3103d16 to 1648898 Compare October 15, 2024 12:06
@AlecsFerra AlecsFerra marked this pull request as ready for review October 15, 2024 13:31
Comment thread liquidhaskell-boot/src/Language/Haskell/Liquid/Constraint/Env.hs
@AlecsFerra

Copy link
Copy Markdown
Contributor Author

I think there might be a bug in the contruction of the DAG.

Where?

@AlecsFerra

Copy link
Copy Markdown
Contributor Author

I forgot to add, all the calls of HashSet.toList are making the code non-deterministic because the order in which the elements are returned might vary from one machine to another. It will depend on what the hash of a particular expression is in that machine.

Makes sense this could explain the different behavior on the CI

@facundominguez

facundominguez commented Oct 16, 2024

Copy link
Copy Markdown
Collaborator

I think there might be a bug in the contruction of the DAG.

Where?

You already merged the suggestion for a fix here.

@AlecsFerra

Copy link
Copy Markdown
Contributor Author

I think there might be a bug in the contruction of the DAG.

Where?

You already merged the suggestion for a fix here.

Ah you're right and indeed it was a bug

Comment thread liquidhaskell-boot/src/Language/Haskell/Liquid/Constraint/Env.hs Outdated
AlecsFerra and others added 2 commits October 16, 2024 22:47
@AlecsFerra

Copy link
Copy Markdown
Contributor Author

🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉

@AlecsFerra

Copy link
Copy Markdown
Contributor Author

The only open question is the optimization in the DFS

@facundominguez facundominguez left a comment

Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thanks @AlecsFerra. I left some comments. Let me know what you think.

Also, some user documentation would be deserved for this PR and the --etabeta flag.

Comment thread .circleci/config.yml Outdated
sudo cp z3-4.13.3-x64-glibc-2.35/bin/libz3.a /usr/local/lib
sudo cp z3-4.13.3-x64-glibc-2.35/bin/z3 /usr/local/bin
sudo cp z3-4.13.3-x64-glibc-2.35/include/* /usr/local/include
rm -rf z3-4.13.3-x64-glibc-2.35

Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

We should add some check for this version of Z3. Otherwise, tests are going to fail for some users, and they will be clueless about why. Liquid.Fixpoint.Smt.Interface does version checks already.

Then it would be fine to skip the version check with a flag --skip-smt-version-check if the user wants to run an older version anyway.

Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I believe that was just a z3 bug so i don't know if it makes sense signaling to the user, and if we decide to do that we should probably check exactly from which version it's not going to loop forever, on Niki's pc the version was just slightly older than the CI's one

Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I'm assuming it is a z3 bug, indeed. I think you can drop this if you prefer. We can have an issue specifically for checking the z3 version.

My local version of z3 is 4.8.17.

Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I think an issue would be better

Comment thread liquidhaskell-boot/src/Language/Haskell/Liquid/Constraint/RewriteCase.hs Outdated
Comment thread liquidhaskell-boot/src/Language/Haskell/Liquid/Constraint/RewriteCase.hs Outdated
Comment thread liquidhaskell-boot/src/Language/Haskell/Liquid/Constraint/RewriteCase.hs Outdated
in unloop
$ concatMap (uncurry $ unify ctors globals)
$ groupUnifiableEqualities
$ getEqualities refinement

@facundominguez facundominguez Oct 17, 2024

Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I'm realizing that if the pipeline is fed a single equality f = \x -> x with f local, it is not going to generate a rewrite for f. While I realize this is not the purpose of getCaseRewrites, I'm left wondering how to make a rewrite for it. Is this future work?

Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

We could add that case is not going to create any problem in principle, it's the same thing as get equality being right biased it was thought as a way to extract equalities when performing dependant pattern matching on dependant inductive indexed types and in LH we generate constraint for those in a standard format (prop e = T e1 ... en) but I believe that in spirit of making the code more general as we did by removing the right bias we could also handle those cases

Comment thread liquidhaskell-boot/src/Language/Haskell/Liquid/Constraint/RewriteCase.hs Outdated
Comment thread .circleci/config.yml Outdated
Comment thread docs/mkDocs/docs/options.md Outdated
Comment on lines +181 to +182
Note: The eta-expansion rule subsumes the `--extensionality` flag. To save time
during typechecking, you can disable `--extensionality` when using `--etabeta`.

@facundominguez facundominguez Oct 18, 2024

Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I checked if enabling --etabeta would have the effect of enabling extensionality, but this is not the case since there is one place in LH where the extensionality flag is used and etabeta is ignored.

I don't know what it is meant by the first sentence: "The eta-expansion rule subsumes the --extensionality flag".

To save time during typechecking,

Do you mean that extensionality makes etabeta noticeably slower?

Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

It's meant as any theorem that is proved automatically by extensionality should also be automatically proved by eta beta, in practice the extensionality flag works this way:

If there is some proof { e1 = e2 } where e1 and e2 have type T_1 -> ... -> T_n -> T the extensionality flag rewrites the goal of the proof as { e1 x1 ... xn = e2 x1 ... xn } adding some "ghost" variables x1 ... xn to give a chance to ple to unfold any partially applied function in e1 and e2.

But now the unfolding of partially applied functions is also triggered by eta-expansion, actually is a more general mechanism as eta it works also when functions are used as an argument to some other function/constructor as eta expansion is type preserving but extensionality is not as adding the variables will change the type of the expression so adding the ghost variables there will create an ill typed term.

The suggestion to disable the extensionality flag is meant as: the extensionality flag is not going to automate any proof that is not already automated by etabeta so by enabling extensionality you are executing more code for nothing, is also not going to make PLE faster as we eta-expand everything also fully applied functions.

Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

But we can easily not mention this if you think is only going to confuse the users

@facundominguez facundominguez Oct 18, 2024

Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I made the note more explicit in e6dc9ac.

What do you think of that use of the extensionality flag in LH?

Should that place take into account etabeta as well?

Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I think that code is needed to take into account the fact that extensionality flag is changing the type of some expressions, thing that is not done by doing eta expansion, also the eta expansion is totally transparent to LH as it's actually done completely in LF so it shouldn't require any modification in LH

@facundominguez facundominguez left a comment

Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Hey, it seems to me we are good to merge! 🎉

@facundominguez facundominguez merged commit 561c5f7 into ucsd-progsys:develop Oct 18, 2024
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