Hi @nikomatsakis
I'm assuming you saw my new PR?
(even if you haven't actually looked at the changes)
Since the CanonicalStrand
changes might be less straightforward (or at least, more to think about) than I/we originally thought, I'll probably rebase that branch for master
But, overall I think there are some good changes there (not just that it's now iterative instead of recursive). But also I think it might make implementing the coinduction changes easier (or at least easier to follow)
Would like your input though
@Jack Huey I saw the PR, but I didn't look closely at the commits
I guess that it is removing all recursion and just maintaining the stack manually?
Yes, exactly
The stack was somewhat maintained manually already, I just extended upon that
Reading that PR, I see what I think is a bug -- but a pre-existing one
I have to go back to the source, but
it looks like when a strand returns QuantumExceeded -- oh, never mind
I was going to say "It never gets added back to the table"
but I guess that it does at the point where we return QuantumExceeded
Yeah, so that's one thing that I think changing to iterative vs recursive really helps with, is that it's sometimes more clear what's happening to strands and where
My intention initially was basically.... you pass ownership of strands around, so if you don't get one back, you don't have to worry about it
I just kind of didn't trust myself I guess :)
This is a fair point
I think that worked fine when everything is recursive. But once you start doing things iteratively, it because a little bit more messy
I guess you could pass it in, and then an Option<Strand>
out
Well, I can't argue that it's a bit messy, since I got a bit confused
I don't think you need an Option<Strand>
, though
I mean, we have an existing enum
Oh but I guess you mean when you move to a fully iterative approach
yes
ps @Jack Huey one thing I do think is that we should try to land pieces of this branch, I'm finding this coinductive stuff hard enough to think about without mixing in more than we have to
So, I can try to split apart this branch
I initially tried to make smaller commits
But the change from recursive -> iterative all sort of came at once
I guess with hindsight it might be easier
I saw some commits that seemed separable
it's not the most imp't thing, just thinking that it make sense to land certain commits quickly, ponder the rest :)
The first ~5 or so are
I don't think I would want to land the change to cyclic handling quite yet -- even though I think this is probably good
I was thinking already we should get rid of that vector
I was intending though to use the position in the queue
I hadn't really thought it through very hard
basically partition the vector so you have "cyclic stuff" collected in one part, "candidates" in another
but using the "answer found counter" seems maybe nicer and more obvious
I can split out the first couple commits if you think it's worth just landing those
That's sort of what I had intended to start with
am I correct that the "work" counter is really tracking answers
That wasn't what I had intended it to be. I had originally intended it to match exactly how collecting into a vec worked
But I think tracking answers works also
I think this is the sort of..intention
if we incremented it for every answer that is published anywhere
and then, if there is a cycle, we tag the strand with the number of answers so far
well, I have to go think about it again :)
I want in particular to see if we can do a bit better than the current code
No problem
right now, the current code -- if quantum is exceeded -- will put the cycles back into circulation
but it seems like we should be able to avoid that if we were tracking answers published
but it's a bit tricky
after all, the next time you are invoked, the stack above you is different
so maybe I am wrong -- unless we have a way to check if that has changed
Right
So I'm not sure if you still assume they are cycles
yeah, you can't really
regardless we need a nice comment :)
I think I did make a comment about that somewhere
I think maybe your original branch has it right. I might want to rename it to "clock" from "work"
because for some reason that feels more obvious to me
but basically the goal is to say "this was found to be a cycle in some previous call"
and nothing more than that
"clock" works
Ha, yeah I did make a comment. It just didn't make it in when I refactored the branch: https://github.com/jackh726/chalk/blob/fuel_friendly_old/chalk-engine/src/logic.rs#L293
Though I didn't explicitly say it was because of cycles above us
Anyway, I'll make a comment and change the name.
I am reminded of the clock we use for floundering
I sort of forget how that works
So that does track answers
ah, but it is local to a strand
yes
you might want to use the same TimeStamp
type for the clock (if you didn't already)
I did :)
ok :)
OK @nikomatsakis
ensure_answer
into separate functions (feel free to bikeshed the names).dfn
and work
into a new clock
, which is just a TimeStamp
still. I added some comments about when it gets incremented. With this, we also no longer need DepthFirstNumber
, is was essentially the same as TimeStamp
anyways. (I guess it loses it's parity with the paper, but I think overall it's cleaner)I'm going to let you look it over a bit more before I do any work to split out the smaller changes into a separate PR.