-
Notifications
You must be signed in to change notification settings - Fork 17
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
Type checker plugin #58
Comments
I'm going to see if I can recruit anyone to work on this with me at Hac Boston in a couple of weeks, since I don't understand how to do it myself. The API GHC provides for this has a lot of cryptic abbreviated names that probably make a lot more sense to someone who understands the internals of the type checker. |
+1 |
Objective is to get past problems like this that cripple my attempt at dimensional linear algebra:
It does all the seemingly difficult parts, but then gets tripped up trying to unify |
Good luck! You might be aware of this already, but my uom-plugin (paper) does something like this, though competition is very welcome. I'm on the wrong side of the pond to go to Hac Boston, but feel free to ask questions about the plugins API (or perhaps better ask on |
Hi @adamgundry. Definitely have checked out your work and your paper, which is cool. It looks like you do solve the same type plugin problem that this issue is about, which is awesome. As far as the competition goes, we should think about joining forces. You have this issue kicked. We have more arithmetic, a library that works for almost all use cases without TH, a wide variety of pre-defined units and dimension synonyms. We also have a branch where we are exploring tracking unit names, which is pretty interesting for user interfaces. |
Digging in to the way the uom-plugin solver works and trying to line up Adam's terminology with ours. His Near as I can tell, we don't have an equivalent of his
I don't understand what our analog of his
I am at the phase where I understand the broad outlines of what's going on, just digging deeper into the details. |
Also this is probably an embarrassingly simple question, but I could use help unpacking this comment:
I tried to look up the It's compounded by the fact that I'm not sure what it means to turn the substitution back into constraints, and so I can't guess what information we would need then. |
Well, I thought I understood... If it's true that
... but ours don't include any variables. So it must not be the case that Now I think that our
and that we have a |
Having the implementation as the solver gives @adamgundry's approach a much nicer type for square root than ours. From his paper:
Compared to ours which needs the I think there are going to be some hoops to go through to make a similar solver that can deal with the root type family. In essence it needs to solve |
OK, I think I figured out everything except the Our trick is that applications of the Excerpt from @adamgundry 's code:
The case of a It seems like it would be a fairly major change to extend the grammar in figure 5 of his paper (assuming it's possible?) to allow variables in the position of integers on the RHS of exponents, although having such variables would handle this case and the case of things like Am I missing a subtle reason why this doesn't matter? Or alternatively is it the reason that
|
I'm not completely sure that I'm reading it right, but I think that this paper discusses the problem of allowing variables in the exponents. I think we are case E2 in the second row of table 1 and so that problem is undecidable? But I can't tell for sure if they are discussing the case where there is only one type, which can appear on either side of the exponentiation operator. In our case we have two separate types, one which can only appear on the left and the other which can only appear on the right. They use the same metavariable y in both positions, but in two different axioms, so it is unclear to me. |
Rats. I powered through it and actually got this working! (Thanks to Adam.) ... and it actually fixed the error message that was my reason for initiating this thread, the one about ... but that just got me to a whole bunch of new error messages, related to not being able to solve similar types of things for the Example:
These types logically match, because dividing each element of It couldn't even do this simpler case, which I am slightly confused by because I thought it might:
(The reason I felt this one is simpler is because, if you rewrote There may yet be hope, because we don't really need the integer variables I was discussing above to tackle any of the cases I have seen so far, but we might need either a more complicated solver that is aware of |
@dmcclean, the idea was something like: let's define I haven't looked at Adam's paper or code, but maybe some of the ideas/experience Christan has https://hackage.haskell.org/package/ghc-typelits-natnormalise will help you |
Thanks @aavogt for the reminder. That approach is cool in that it provides bidirectional inference, and it's cool in that I think it would fix this problem, allowing a solver in Adam's style to figure everything out. The big drawback that I see is that I can't figure out how to describe data types with polymorphic shapes. By switching away from the "forwards style" type families, you lose the ability to express types like this one, where there are four matrices with interrelated shapes determined by just a few choices of dimensions (for the independent variable, system states, system outputs, and control inputs respectively):
Do you happen to have any ideas on how to deal with this? Is the right approach to make the data type a totally unconstrained record of four matrices and then apply the constraints only in the functions that deal with it? I'm having trouble picturing exactly how that would work, especially for the construction function. |
I seem to have had some success with "forwards style" type families and making the plugin add wanted constraints that calculate the "backwards": https://github.com/aavogt/HListPlugin. Maybe it's easier to implement, but probably you get worse error messages and slower compile times with that idea. That ContinuousLiSystem might work with ExistentialQuantification/GADT too. I mean translating what you wrote into something like: data CLiSys iv xs ys us e = forall ivxs a b c d.
(MapDiv iv xs ~ ivxs,
DivideVectorLists ivxs xs ~ a,
DivideVectorLists ivxs us ~ b,
DivideVectorLists xs ys ~ c,
DivideVectorLists ys us ~ d) => CLiSys {
a'' :: DimMat a e,
b'' :: DimMat b e,
c'' :: DimMat c e,
d'' :: DimMat d e } and then just replace the |
I will definitely take a look at how that plugin works. The existential/GADT encoding idea is a good one, and I think it would have a good chance of checking everything it needs to check, but I think it might also kind of defeat my purposes because I don't think it would be able to calculate the "forwards" type for documentation purposes, it could only tell you if you were correct. |
@adamgundry, if you have a minute could you answer a question I have about the solver API? The The definition of
The three If I wanted to convert constraints like I hope I am even wording this question in a way that makes sense. |
Or maybe for that scenario I'm meant to ignore the second list in the |
@dmcclean excellent digging, sorry it's taken me a few days to respond to everything. Indeed,
Yes,
When checking the body of The case of "derived" constraints is a bit more interesting. These are constraints that aren't given (i.e. they cannot be assumed to be true) but also aren't wanted (i.e. they are not truly required in order for the program to typecheck). The typical case is with functional dependencies, e.g. suppose we have
Now if GHC has two wanted constraints
You can indeed do this by calling In this case, the new constraints are strong enough to prove the original constraint (assuming an appropriate axiom). If the constraints you were generating were not sufficient to prove the original constraint, another approach would be to leave the original constraint unsolved but return additional "derived" constraints. It might be trickier to avoid loops this way, as you'd need to check you were not emitting the same constraints repeatedly. |
See, that first paragraph is why I am an amateur at this. ;) I sensed that something was impossible but I couldn't put my finger on why, much less explain it. Thanks very much for the rest. I think I know how to proceed with that pretty quickly, hopefully I will get a chance to take a crack at it next weekend. One other worry I have is how does the faking of evidence interact with stuff that converts types to terms, like:
I can see two possibilities, but there might be others.
I'm having trouble knowing how to construct test cases to investigate this, because I might just not be testing the scenario where things explode. Can we discuss, perhaps in another forum, the copyright/licensing issues? I had intended to use your code just for reading and learning, but I was short on time at the hackathon where I had access to some people who could answer questions, so I ended up justifying to myself that I could copy and paste some things to get running, change them enough to understand the gist of how they work, and clean up the mess later. Obviously I didn't and won't release the result, but now I feel badly about it and I am realizing it isn't that easy to clean up later, because know you already know everything you copied, etc. It did hit github because I forgot I wasn't in a private repository, but I can fix that. My personal email is in my github profile. |
Chasing docs from I'm not sure how the So perhaps the faking of the evidence would be more severe if the named-units branch were adopted? Or perhaps not, because I honestly don't understand most of what the GHC note is talking about. |
In any event it seems possible to cook up the "real" evidence with enough effort, or evidence with the right runtime implementation, because it really is a phantom, so even if there is a problem here there is probably a way around it. |
WTH is the meaning of the verb "zonk" in the GHC source? There are all sorts of functions for zonking this or that, and comments about the need to zonk or not to zonk various things at various times, but I can't chase down an explanation of what is being talked about, and I can't puzzle it out from the definitions. 😕 More specifically, why do you |
Stackoverflow was able to answer the zonking question. |
I believe this is the case. GHC's core theory is "proof-irrelevant", which means it doesn't matter how a proof of an equality constraint is constructed, provided the constraint doesn't equate two types that are actually distinguishable. Ultimately nothing is going to look at the proofs, because they are erased at runtime! This is true regardless of roles. The difference roles make is to the consistency requirement: fake evidence at role
I wouldn't read too much into this; it's very possibly not the right thing, because my understanding of how zonking works is very limited. I think that GHC will already have zonked the wanteds, but not the givens, by the time it gives them to the plugin. |
Awesome, thanks. I think that even though according to the current rules our fake evidence is at role |
@adamgundry Do you know if anything changed in 7.10.2 with respect to this? I have 7.10.1 on my windows machine where the draft plugin works, but then I installed a new ubuntu VM with 7.10.2 because hmatrix is easier to install on linux (vast understatement...) and there it doesn't work. It doesn't report any errors, but it also doesn't solve the constraints that it does on windows/7.10.1. I read the release notes and nothing jumped out at me except 10321, which doesn't really seem related. |
@dmcclean I'm not aware of any such changes, but it wouldn't entirely surprise me if minor adjustments to the typechecker were made in 7.10.2, and those might have tripped up the plugin. Unfortunately I don't have much to suggest other than digging through the output of |
Curiously it looks from comparing the Something curious is going on here. I tried to compile your
I will dig further after work. |
That sounds strange; it seems unlikely, but could you be using a stage1 build of 7.10.2 that doesn't support plugins/TH/GHCi? Or perhaps the Thanks for pointing out the error with |
The tests in The I'm also on Ubuntu (32 bit though, in a VirtualBox) with 7.10.2 distribution that I got by cargo culting some instructions that used |
Found it, it has to do with GHCi. Your module gets the plugin because the module is being built by My module didn't get the plugin because I was doing However, on 7.10.1 on windows the Whether it should or shouldn't is above my knowledge, so I don't know if this is a regression or a bug fix. Any thoughts? |
If |
I had |
(Warning, this is a doozy.)
It would be really nice if we had a type checker plugin capable of solving constraints like
d ~ DOne / (DOne / d)
and other "obvious" proof obligations that arise.These sorts of things were crippling to the first attempt at using this for dimensional linear algebra, and especially for dimensional linear algebra as it applies to control theory. (Some of those sketches using dimensional-dk are no longer visible in history at that link.)
It turns out that unification in abelian groups (like the group of dimensions) is decidable, and that unification discharges all of these things that we think are obvious, and a few more besides. The agum package provides a Haskell implementation (unfortunately with GPL licensing) of this that could be used to do "the hard part" of this problem. Of course, the actual hard part is figuring out how the GHC type checker plugin API works. ;)
The text was updated successfully, but these errors were encountered: