Repository navigation
Unify CanonicalVar and DebruijnIndex #49887
Description
From #49810:
The plan is to generalize the existing
CanonicalVarso that it represents a "bound" thing -- probably it just gets unified withDebruijnIndex.
General instructions:
The canonical var is a "new type index" declared here:
Line 1107 in 3242880
We would basically just want to remove it completely and replace uses of it with DebruijnIndex. There are a few complications to be overcome. One is that debruijn indices are currently 1-based (that is #49813), so indexing with them will require some tweaks. Another related problem is that DebruijnIndex does not implement the Idx trait, so we can't presently have a IndexVec<DebruijnIndex>, as we do in the CanonicalVarValues struct:
rust/src/librustc/infer/canonical.rs
Lines 76 to 78 in 3242880
This is not that big a deal -- we can just use a plain vector -- although if we make debruijn indices 0-based we could then generate it with the newtype_index! macro, which would be nice.
Activity
sgrif commentedon Apr 11, 2018
Can we pick some better names while we're at it?
nikomatsakis commentedon Apr 11, 2018
Which names are you thinking we should change?
sgrif commentedon Apr 11, 2018
DebruijnIndexin particular is one I find extremely opaque. I get that it's a math term and there's a wikipedia article, but I don't think we should require that sort of reading to understand a term in a codebase (I argue forMappableoverFunctorfor the same reason).CanonicalVaris better in context, but I also think it's the sort of name that unless you see it specifically in the context of canonicalization there's no reason you'd know what it means.nikomatsakis commentedon Apr 11, 2018
Hmm. I suppose we could call it
BinderIndexor something maybe? That said, I sort of likeDebruijnIndexbecause it has a very unique, instant meaning, and I'm not sure that there exists a non-mathemetical term for this thing. Still, ordinarily I agree we should strive for "accessible and memorable" terminology.varkor commentedon Apr 11, 2018
If there is a very precise technical term for something, it's least ambiguous if you give that something the name. Giving something a more friendly, and less descriptive name, means that people who know the term won't be immediately familiar with it, whereas people who aren't familiar with the concept still need to look it up anyway. Plus, technical terms are more memorable. I'd prefer to stick with
DeBruijnIndexhere.sgrif commentedon Apr 11, 2018
Even though DeMorgan Machine is generally a more precise technical term for computers today, we use the term computer, since it had a more generally understandable meaning for those involved, even if that term was nonsense when applied to a machine at the time. I don't think "math calls it X" is a great argument in a code base meant to be read by programmers, who may or may not have a degree in mathematics.
varkor commentedon Apr 11, 2018
This might be a reasonable argument about technical terms (e.g.
Functor) in user-facing libraries, but I'd argue the internals of a compiler are technical enough that one should expect some compiler / programming language theory terminology (e.g.DeBruijnIndex).(Although now that I've just noticed, I would be in favour of changing the capitalisation on the name ;) )
eddyb commentedon Apr 11, 2018
BinderDepthorBinderDistancemight work out as alternatives?Although I'm not sure I like
Bindereither, but there I have no suggestions.(Using
BinderandBinderSomethingwould make it easier to connect the two though)Also, aren't many canonical vars bound at the same binder? How would that work?
Ixrec commentedon Apr 12, 2018
This does seem like a case where a vague, non-"scary" term might be more obfuscating in practice than the technically correct, unambiguous term.
imo, if
DeBruijnIndexusually appears in close proximity to aBinder, then renaming it toBinderIndexis probably a net win. But ifDeBruijnIndexis mostly operated on/passed around independently of whatever type it is an index for, then it's probably better to keep it the way it is.eddyb commentedon Apr 12, 2018
@Ixrec AIUI, it's specifically "how many
Binders do I have to pass through to get to theBinderthat introduces this parameter?" - "index" can be confusing because there is a separate notion of "which parameter" within aBinder- and the anonymous ones are distinguished by... an index.nikomatsakis commentedon Apr 30, 2018
@fabric-and-ink yeah this is sort of a "meta issue"
nikomatsakis commentedon Apr 30, 2018
but I'll try to comment here or ping you once we get #49813 resolved
nikomatsakis commentedon May 29, 2018
cc @fabric-and-ink — still interested in giving this a shot? #49813 is finally closed.
nikomatsakis commentedon May 29, 2018
I guess a good first step would be to convert
DebruijnIndexto support theIdxtrait. The idea would be to declare it via thenewtype_index!macro.Auto merge of #51248 - fabric-and-ink:newtype_index_debrujin, r=nikom…
nikomatsakis commentedon Jul 2, 2018
@fabric-and-ink argh sorry for missing your update! probably yes! Let me give a look
Auto merge of #52984 - fabric-and-ink:remove-canonical-var, r=scalexm