Stream: wg-traits

Topic: non-recursive ensure_answer


Jack Huey (Nov 11 2019 at 15:31, on Zulip):

Hi @nikomatsakis

Jack Huey (Nov 11 2019 at 15:31, on Zulip):

I'm assuming you saw my new PR?

Jack Huey (Nov 11 2019 at 15:31, on Zulip):

(even if you haven't actually looked at the changes)

Jack Huey (Nov 11 2019 at 15:36, on Zulip):

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

Jack Huey (Nov 11 2019 at 15:38, on Zulip):

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)

Jack Huey (Nov 11 2019 at 15:38, on Zulip):

Would like your input though

nikomatsakis (Nov 11 2019 at 18:18, on Zulip):

@Jack Huey I saw the PR, but I didn't look closely at the commits

nikomatsakis (Nov 11 2019 at 18:18, on Zulip):

I guess that it is removing all recursion and just maintaining the stack manually?

Jack Huey (Nov 11 2019 at 18:21, on Zulip):

Yes, exactly

Jack Huey (Nov 11 2019 at 18:21, on Zulip):

The stack was somewhat maintained manually already, I just extended upon that

nikomatsakis (Nov 11 2019 at 18:24, on Zulip):

Reading that PR, I see what I think is a bug -- but a pre-existing one

nikomatsakis (Nov 11 2019 at 18:24, on Zulip):

I have to go back to the source, but

nikomatsakis (Nov 11 2019 at 18:24, on Zulip):

it looks like when a strand returns QuantumExceeded -- oh, never mind

nikomatsakis (Nov 11 2019 at 18:25, on Zulip):

I was going to say "It never gets added back to the table"

nikomatsakis (Nov 11 2019 at 18:25, on Zulip):

but I guess that it does at the point where we return QuantumExceeded

Jack Huey (Nov 11 2019 at 18:26, on Zulip):

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

nikomatsakis (Nov 11 2019 at 18:40, on Zulip):

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

nikomatsakis (Nov 11 2019 at 18:40, on Zulip):

I just kind of didn't trust myself I guess :)

Jack Huey (Nov 11 2019 at 18:41, on Zulip):

This is a fair point

Jack Huey (Nov 11 2019 at 18:43, on Zulip):

I think that worked fine when everything is recursive. But once you start doing things iteratively, it because a little bit more messy

Jack Huey (Nov 11 2019 at 18:43, on Zulip):

I guess you could pass it in, and then an Option<Strand> out

nikomatsakis (Nov 11 2019 at 19:00, on Zulip):

Well, I can't argue that it's a bit messy, since I got a bit confused

nikomatsakis (Nov 11 2019 at 19:00, on Zulip):

I don't think you need an Option<Strand>, though

nikomatsakis (Nov 11 2019 at 19:00, on Zulip):

I mean, we have an existing enum

nikomatsakis (Nov 11 2019 at 19:01, on Zulip):

Oh but I guess you mean when you move to a fully iterative approach

Jack Huey (Nov 11 2019 at 19:01, on Zulip):

yes

nikomatsakis (Nov 11 2019 at 19:45, on Zulip):

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

Jack Huey (Nov 11 2019 at 19:53, on Zulip):

So, I can try to split apart this branch

Jack Huey (Nov 11 2019 at 19:54, on Zulip):

I initially tried to make smaller commits

Jack Huey (Nov 11 2019 at 19:54, on Zulip):

But the change from recursive -> iterative all sort of came at once

Jack Huey (Nov 11 2019 at 19:54, on Zulip):

I guess with hindsight it might be easier

nikomatsakis (Nov 11 2019 at 19:55, on Zulip):

I saw some commits that seemed separable

nikomatsakis (Nov 11 2019 at 19:55, on Zulip):

it's not the most imp't thing, just thinking that it make sense to land certain commits quickly, ponder the rest :)

Jack Huey (Nov 11 2019 at 19:55, on Zulip):

The first ~5 or so are

nikomatsakis (Nov 11 2019 at 19:56, on Zulip):

I don't think I would want to land the change to cyclic handling quite yet -- even though I think this is probably good

nikomatsakis (Nov 11 2019 at 19:56, on Zulip):

I was thinking already we should get rid of that vector

nikomatsakis (Nov 11 2019 at 19:56, on Zulip):

I was intending though to use the position in the queue

nikomatsakis (Nov 11 2019 at 19:56, on Zulip):

I hadn't really thought it through very hard

nikomatsakis (Nov 11 2019 at 19:57, on Zulip):

basically partition the vector so you have "cyclic stuff" collected in one part, "candidates" in another

nikomatsakis (Nov 11 2019 at 19:57, on Zulip):

but using the "answer found counter" seems maybe nicer and more obvious

Jack Huey (Nov 11 2019 at 19:58, on Zulip):

I can split out the first couple commits if you think it's worth just landing those

Jack Huey (Nov 11 2019 at 19:58, on Zulip):

That's sort of what I had intended to start with

nikomatsakis (Nov 11 2019 at 20:00, on Zulip):

am I correct that the "work" counter is really tracking answers

Jack Huey (Nov 11 2019 at 20:01, on Zulip):

That wasn't what I had intended it to be. I had originally intended it to match exactly how collecting into a vec worked

Jack Huey (Nov 11 2019 at 20:01, on Zulip):

But I think tracking answers works also

nikomatsakis (Nov 11 2019 at 20:01, on Zulip):

I think this is the sort of..intention

nikomatsakis (Nov 11 2019 at 20:02, on Zulip):

if we incremented it for every answer that is published anywhere

nikomatsakis (Nov 11 2019 at 20:02, on Zulip):

and then, if there is a cycle, we tag the strand with the number of answers so far

nikomatsakis (Nov 11 2019 at 20:02, on Zulip):

well, I have to go think about it again :)

nikomatsakis (Nov 11 2019 at 20:03, on Zulip):

I want in particular to see if we can do a bit better than the current code

Jack Huey (Nov 11 2019 at 20:03, on Zulip):

No problem

nikomatsakis (Nov 11 2019 at 20:03, on Zulip):

right now, the current code -- if quantum is exceeded -- will put the cycles back into circulation

nikomatsakis (Nov 11 2019 at 20:03, on Zulip):

but it seems like we should be able to avoid that if we were tracking answers published

nikomatsakis (Nov 11 2019 at 20:04, on Zulip):

but it's a bit tricky

nikomatsakis (Nov 11 2019 at 20:04, on Zulip):

after all, the next time you are invoked, the stack above you is different

nikomatsakis (Nov 11 2019 at 20:04, on Zulip):

so maybe I am wrong -- unless we have a way to check if that has changed

Jack Huey (Nov 11 2019 at 20:04, on Zulip):

Right

Jack Huey (Nov 11 2019 at 20:04, on Zulip):

So I'm not sure if you still assume they are cycles

nikomatsakis (Nov 11 2019 at 20:04, on Zulip):

yeah, you can't really

nikomatsakis (Nov 11 2019 at 20:04, on Zulip):

regardless we need a nice comment :)

Jack Huey (Nov 11 2019 at 20:05, on Zulip):

I think I did make a comment about that somewhere

nikomatsakis (Nov 11 2019 at 20:05, on Zulip):

I think maybe your original branch has it right. I might want to rename it to "clock" from "work"

nikomatsakis (Nov 11 2019 at 20:05, on Zulip):

because for some reason that feels more obvious to me

nikomatsakis (Nov 11 2019 at 20:06, on Zulip):

but basically the goal is to say "this was found to be a cycle in some previous call"

nikomatsakis (Nov 11 2019 at 20:06, on Zulip):

and nothing more than that

Jack Huey (Nov 11 2019 at 20:06, on Zulip):

"clock" works

Jack Huey (Nov 11 2019 at 20:08, on Zulip):

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

Jack Huey (Nov 11 2019 at 20:09, on Zulip):

Though I didn't explicitly say it was because of cycles above us

Jack Huey (Nov 11 2019 at 20:09, on Zulip):

Anyway, I'll make a comment and change the name.

nikomatsakis (Nov 11 2019 at 20:12, on Zulip):

I am reminded of the clock we use for floundering

nikomatsakis (Nov 11 2019 at 20:13, on Zulip):

I sort of forget how that works

Jack Huey (Nov 11 2019 at 20:13, on Zulip):

So that does track answers

nikomatsakis (Nov 11 2019 at 20:13, on Zulip):

ah, but it is local to a strand

Jack Huey (Nov 11 2019 at 20:13, on Zulip):

yes

nikomatsakis (Nov 11 2019 at 20:13, on Zulip):

you might want to use the same TimeStamp type for the clock (if you didn't already)

Jack Huey (Nov 11 2019 at 20:13, on Zulip):

I did :)

nikomatsakis (Nov 11 2019 at 20:13, on Zulip):

ok :)

Jack Huey (Nov 12 2019 at 03:45, on Zulip):

OK @nikomatsakis

Jack Huey (Nov 12 2019 at 03:50, on Zulip):

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.

Last update: Dec 12 2019 at 00:55UTC