mandag 3. mai 2021 kl. 23:12:03 UTC+2 skrev Øyvind Teig:
> mandag 3. mai 2021 kl. 21:44:49 UTC+2 skrev axel.wa...@googlemail.com: > >> On Mon, May 3, 2021 at 9:16 PM Øyvind Teig <oyvin...@teigfam.net> wrote: >> >>> I don't see where hi and lo are being sent to? >>> >> >> They are being `close`d. Reading from a closed channel immediately >> succeeds, yielding the zero value. >> I chose to use `close` because it's a non-blocking way to make a channel >> readable. You could get the same demonstration by making the channels >> buffered and writing to them <https://play.golang.org/p/zeZzZ7p4HqX>. >> > I have played with that code at https://play.golang.org/p/U17AbmGBZUY. Instead of starting and starting lots of tasks, I just start 3. Sender (two configs: one with two tasks in parallel and one config with one task sending in sequence, and one with zero or 1 dim of the chans. However, I am just as wise. I don't see how any of the test cod" examples based on this proves that a hi is *always* taken if there is a lo lurking. I hope it's not my cognitive bias that I just cant' see it! I only see code that terminates if lo is taken after hi has been polled as not active some time before, but it says nothing about hi at the time lo is taken. It *might* have become active. If you see what any flawed thinking in the example above is, I'd be happy to know. *Here is my cognitive test case. It is not 100% realistic, but it's just to convey my point:* *hiPri is a disconnect message of a smoke detetector. loPri is a fire alarm. If the disconnect hiPri is activated before (1 sec to 1 ns) or simulatenously (same polling of "hw pins") as the alarm loPri there should be no alarm being sent to the fire department. No emergency fire trucks. Not ever. There should not be any case of some low probability where this may happen. However, if the hiPri disconnect message was activated after the alarm, then it was too late, and the alarm will go off. (Disconnect was because we knew that there was going to be an alarm since we were doing something, and we explicitly did not want the fire trucks to come)* But then, "happens before" is "within a single gorotine". When it comes to >>> several and concurrent goroutines there is no other order than those forced >>> on them by synchronisation over nonbuffered channels (or the join you had >>> in the code example). >>> >> >> Exactly. It is only *because* we use a single goroutine and we thus know >> that there is a happens-before edge. >> For example, this program <https://play.golang.org/p/nkPnsnFahHs> *also* >> exits (i.e. line 16 is executed), but you can no longer conclude that `hi` >> was ready when it does. >> >> This is how most practical cases would likely happen. >> >> I think my question was flawed, because really, the issue isn't about how >>>> the `select` with `default` construct we showed works - the question is >>>> how >>>> a priority `select` could work. That is, could we implement a priority >>>> `select` such that this code terminates: >>>> https://play.golang.org/p/4G8CY36L0Qy >>>> >>> >>> But wouldn't this be 50% on each, like in >>> https://play.golang.org/INacl7a-BU >>> <https://play.golang.org/p/INacl7a-BU>? (Taken from my note >>> https://www.teigfam.net/oyvind/home/technology/049-nondeterminism/#go_or_go_or_golang >>> ) >>> >> >> I don't understand this question. Though I also see that my question is >> wrong - it should be "could we implement a priority `select` such that this >> code *never* terminates. >> > You used *close* which I didn't understand then. Thanks. > If we suppose a perfect priority select, which never chooses the `lo` case >> if the `hi` case is ready, the program I linked would never terminate. >> > Fair enough. But termination is not a requirement. That was just for the test code. The whole idea with a perfect priority select would, if we had it, to build the "fair algorithm" ourselves. For the disconnect and alarm cases there is only one message of each within some large time. The random select as in go *might* in case have caused the fire trucks to arrive when we had explicitly told not to. The fair select (other than the random select of go, which I know the Go designers meant was "fair enough", or maybe even "fair" as they saw it) is when we have a pri select and can use it to make our own fair algorithm. No jamming, no starving. To repeat myself, the fair algorithm here would be to use a pri select and swap the order in the pri list. > Because `lo` is never ready unless `hi` is ready too. This, AIUI, is the >> priority `select` you'd want. Note, in particular, the made up `pri` >> keyword in the example. >> > Oh, if I could follow you on this one. I don't seem able to. > So, no, in that scenario we wouldn't have a pseudo-random choice. The >> question I was begging is if we could actually implement a select like you >> want. If you can write this program in another language, and that program >> ends up not terminating, that would demonstrate that it's indeed possible >> to write a `select` as you are requesting. >> > Commented the other day. > I don't *think* we can - and based on that assumption I extrapolated how >>>> a priority select would actually behave - but I have to admit that I >>>> really >>>> don't understand `select` or the underlying hardware primitives enough to >>>> make a solid case either way here. Maybe you can provide an equivalent >>>> program in a language of your choice that terminates - that would >>>> certainly >>>> prove that it's at least possible (though to be clear: I don't understand >>>> your xC code, so I can't promise that I'd understand whatever you send >>>> here, personally :) ). >>>> >>>> All of that being said: I really think that in the cases where a >>>> priority select is needed, this construct is good enough to hold up. >>>> >>> >>> Hmm.. I must admit I smile here. I kind of like that we come to >>> different conclusions. Would you you send your daughter with a fly by wire >>> airplane that has some "good enough" sw? >>> >> >> This is… a strange question. I'm not saying "the software might be buggy, >> but it will be buggy software that is good enough". I'm saying "the >> construct is good enough to implement non-buggy software with it". Of >> course you need to know what the construct does and take it into account >> when writing your code - if you assume it works differently than it does, >> you'll introduce bugs, yes. That is true in any language. >> > Great. If expanded to "the construct is good enough to implement buggy-enough (per specification) software with it". Risk = probability * connsequence is never zero. Which is an argument against my alarm scenario. But it's the formally proven "never lo if hi" I am after. > There is a rather good explanation of PRI ALT (=pri select) of occam, >>> where the TRUE & SKIP (=default) is also seen at page 72 of >>> http://www.transputer.net/obooks/isbn-013629312-3/oc20refman.pdf. >>> >> >> Can you translate the example <https://play.golang.org/p/pbcL8uYp8Vm> >> into that language? And demonstrate that it doesn't terminate? >> > If I were convinced that this is it, I could do it in xC. Would have been fun. But that would have to be in the course of this summer. But I must be convinced that it does what it should. My mentioned playing at https://play.golang.org/p/U17AbmGBZUY didn't make it easier for me. Øyvind > It's not practical for me to learn a different language and scour its >> reference manual, to try and figure out how their select works, if that is >> compatible with how Go's select works and thus if and how lessons learned >> from that language are transferable to Go. >> >> You seem to be convinced that their priority select is superior to Go's >> select construct and can map semantics that Go can't. >> > > This is the only point I'll respond to tonight (with the possibility of > being impolite since your response is so thorough). No, I am not saying > that occam's PRI ALT or xC's [[ordered]] select are *superior* to Go's > select (or Promela's :: for that sake: > https://en.wikipedia.org/wiki/Promela#Executability). What I could say is > that occam (and probably xC) nondeterministic choice (select without pri) > is inferior to the Go select, since Go select is indeed pseudo random. I > like it. My eager in telling about occam and xC prioritised choice may have > mislead. I am simply saying that a select and a pri select are different, > and I still don't understand why Go doesn't have pri select, and I started > with asking about whether that had changed over the previous years. > Compared with the letters "pri" the reflection case example is > *complicated*, and the select default select.. special case for a small > number of channels is simple to read, but in my opinion it stops there. I > do want to be convinced that it is elegant (even if you promise *it works*, > compared to "pri"), but I am not. About the case below. I like Go because > it is so expressive, by the looks of it. When Go came with channels, you > wont' believe what a relief if was to us who had used them and loved them > for years. They were not dying. I don't have time to dig up an occam > compiler (yes, they exist, there is some on comp.sys.transputer group, they > even make FPGA transputers these days, for those who need them..) but doing > what you suggest would have been fun. The semantics of an occam PRI ALT is > simple and I programmed it for ten years, and I hope some of that > understanding has remained.) > > Øyvind > > >> I'm willing to believe that, but I'd prefer a demonstration. The example >> should, in a loop >> • create two channels `hi` and `lo` >> • In a concurrent routine, write first to `hi` and then to `lo` (to >> establish a happens-before edge) >> • use a priority-select >> • prioritizing reading from `hi` >> • exiting the program if it reads from `lo` >> • never exit, when run >> If you can make this translation, I'm convinced that it's possible >> implementing a `select` statement using the semantics you suggest. Without >> that - no offense - I must consider the possibility that you are >> misunderstanding how Occam's select statement works. >> >> This is occam, where much of Limbo and later Go came from, with regards >>> to concurrency (CSP). The Go designers made their own choices. However, in >>> knowing more than we think we need to know it may be an ok ref. There also >>> is a manual in how to write compilers for this, but the PRI par is not >>> mentioned I think, simply because I think that the transputer in fact only >>> had PRI PAR: http://www.transputer.net/iset/pdf/tis-acwg.pdf >>> >>> Øyvind >>> >>>> >>>> and in fact need to do a random select, and select a lower when a >>>>> higher is present (or became present). Plus, if I try to synchronise >>>>> clients and send over sequence counts, the scheduling pattern could >>>>> become >>>>> so repetitive that no such situation would occur. >>>>> >>>>> Is there a way to inspect the built code and do it from code >>>>> inspection? (I guess so?) >>>>> >>>>> But for all this, I would need even more help... >>>>> >>>>> (Maybe I'll try to trigger a student since I have so much xC ahead of >>>>> me..) >>>>> >>>>> Øyvind >>>>> >>>>> >>>>>> *rog* wrote above (where I had indicated that occam (and also xC, >>>>>>> said here) has a looping channel construct): "To start with, if you've >>>>>>> got >>>>>>> N clients where N isn't known in advance, it's not possible to use Go's >>>>>>> select statement directly because it doesn't provide support for >>>>>>> reading >>>>>>> from a slice." Does this mean that aside from reflection ( >>>>>>> https://go2goplay.golang.org/p/S_5WFkpqMP_H - which still does not >>>>>>> serve "client 2", shouldn't it?) then idiomatic Go for a small number >>>>>>> of >>>>>>> priorities is the one with default case(s), and it works 100% as >>>>>>> intended, >>>>>>> with no cognitive (?) reliance on Go's inner working under the hood? (I >>>>>>> mean: "WYSIWYG semantics" kind of.) >>>>>>> >>>>>>> I am at a point now that if the answer to the above is *yes*, I'll >>>>>>> just say thank you for your help, and I will be a Go-wise wiser person. >>>>>>> With my cognitive bias I will then have to accept that this is Go, >>>>>>> nothing >>>>>>> more to say. Just accept it. Anyhow, in case, thank you! >>>>>>> >>>>>>> Øyvind >>>>>>> >>>>>>> fredag 30. april 2021 kl. 10:42:47 UTC+2 skrev >>>>>>> axel.wa...@googlemail.com: >>>>>>> >>>>>>>> On Fri, Apr 30, 2021 at 9:53 AM Øyvind Teig <oyvin...@teigfam.net> >>>>>>>> wrote: >>>>>>>> >>>>>>>>> If there is no notion of simultaneity why all the effort to >>>>>>>>> describe the random distribution? >>>>>>>>> >>>>>>>> >>>>>>>> While it's not possible for two cases to become ready at the same >>>>>>>> time, it's definitely possible for two cases to be ready when entering >>>>>>>> a >>>>>>>> select. That's where the random selection comes in. >>>>>>>> >>>>>>>> There's also the notable difference between a select with a default >>>>>>>> and one without. A select with a default never blocks, so which branch >>>>>>>> is >>>>>>>> taken is *only* determined by what's ready when entering the select, >>>>>>>> whereas a select without can block and then gets woken up by the first >>>>>>>> communication that's ready - and there'll always be a "first". >>>>>>>> >>>>>>>> In a sense, the nested select uses that: The outer select handles >>>>>>>> the "what's currently ready" case and the inner select handles the >>>>>>>> "what >>>>>>>> becomes ready in the future". >>>>>>>> >>>>>>>> The priority select would use the same basic logic: >>>>>>>> - Is the high priority case ready? If so, do that >>>>>>>> - If not, block until one of the cases become ready - do the first >>>>>>>> that becomes ready >>>>>>>> >>>>>>>> The crux here is exactly that we can't have two cases "becoming >>>>>>>> ready" at the same time, so we really *have* to "take the first one >>>>>>>> that >>>>>>>> becomes ready". >>>>>>>> >>>>>>>> The select is first set up, at which time the code decides on which >>>>>>>>> one to take if more than one guard is ready. If the clients were only >>>>>>>>> sending, then nowhere in the system is this noted on "the other" side >>>>>>>>> of >>>>>>>>> the channel (in the server) before it enters the select. The channel >>>>>>>>> would >>>>>>>>> have noted the first contender, yes, but the servre have yet no idea. >>>>>>>>> If >>>>>>>>> none is ready, then the server was first on all the ends, and when a >>>>>>>>> sender >>>>>>>>> arrives it will match the guard set in the server and tear down the >>>>>>>>> select. >>>>>>>>> In due time the server is scheduled with that one event. >>>>>>>>> >>>>>>>>> This is how I have seen it in several systems. I wonder what might >>>>>>>>> be so different with go. >>>>>>>>> >>>>>>>> >>>>>>>> I don't think I understand this exposition. But on first glance, >>>>>>>> your description doesn't sound terribly different from what's >>>>>>>> happening in >>>>>>>> Go. >>>>>>>> >>>>>>>> To be clear: No one is claiming it would be impossible to implement >>>>>>>> a priority select in Go. Obviously we could replace the pseudo-random >>>>>>>> choice by something else. We are just saying that it would be >>>>>>>> equivalent to >>>>>>>> the nested select code. >>>>>>>> >>>>>>>> Ok, so this is a pattern that Go people would use if they needed to >>>>>>>>> do pri select. Then, why go to the lengths of the other code shown >>>>>>>>> above? >>>>>>>>> Is it because I have kind of "pressed" you to come up with code and >>>>>>>>> then of >>>>>>>>> course, one thing may be solved several ways? >>>>>>>>> >>>>>>>> >>>>>>>> I think the first code you where shown by Jan (which is the same as >>>>>>>> Ian's) is correct and I believe it's likely that your insistence that >>>>>>>> it >>>>>>>> isn't is what prompted people to come up with more and more >>>>>>>> complicated >>>>>>>> code. >>>>>>>> >>>>>>>> Will your Go code examples stand the test of formal verification? >>>>>>>>> Of course, when it's not formally verified you probaby could not >>>>>>>>> answer >>>>>>>>> such a question. But the stomach feeling? >>>>>>>>> >>>>>>>> >>>>>>>> I'm not very familiar with formal methods for this, or what the >>>>>>>> invariant is that would be verified. >>>>>>>> I do feel quite confident about the statement that the shown >>>>>>>> snippet is equivalent to how I'd think a priority select would work. >>>>>>>> >>>>>>>> Another angle: Go does not have the expression before the select >>>>>>>>> that evaluates to true or false. Nothing like >>>>>>>>> >>>>>>>>> select { >>>>>>>>> case (do_this) => val1 <-c1: >>>>>>>>> case val2 <-c2: >>>>>>>>> } >>>>>>>>> >>>>>>>>> Instead, the chan is set to nil to exclude it from the set. What >>>>>>>>> might happen if we had a set of 100 clients and they were switched on >>>>>>>>> and >>>>>>>>> off internally in the server (that's their purpose) - when will the >>>>>>>>> uniform >>>>>>>>> distribution be reset? What's the life span of the distribution? With >>>>>>>>> a >>>>>>>>> psudorandom sequence any one value is only visited once on a round. >>>>>>>>> >>>>>>>> >>>>>>>> I'm not sure what you mean here. Is what you call a "round" the >>>>>>>> cycle of the PRNG? In that case, this statement isn't true, the cycle >>>>>>>> is >>>>>>>> likely significantly longer than the number of cases. So we definitely >>>>>>>> chose at least one case multiple times per cycle. >>>>>>>> >>>>>>>> AFAIK this is the PRNG used by the select >>>>>>>> <https://github.com/golang/go/blob/9c7207891c16951121d8b3f19f49ec72f87da9fe/src/runtime/stubs.go#L124>, >>>>>>>> >>>>>>>> FWIW. I assume it simply calls into it (or likely `fastrandn` directly >>>>>>>> below) when entering a select with multiple available cases. >>>>>>>> >>>>>>>> We still want this to be fair. Could those having been served be >>>>>>>>> served again (before the others) after a reset of the distribution, >>>>>>>>> and >>>>>>>>> this introduce a notion of unfairness? >>>>>>>>> >>>>>>>> >>>>>>>> It can definitely happen, but I'm not sure that "unfairness" is a >>>>>>>> meaningful term here. AIUI the process is "if the runtime enters a >>>>>>>> select >>>>>>>> and multiple cases are ready, it chooses one uniformly at random" >>>>>>>> (within >>>>>>>> the limits of the PRNG). Yes, as an outcome this can mean that one >>>>>>>> case is >>>>>>>> hit more often than the others. But all cases are equally likely to be >>>>>>>> hit >>>>>>>> more often. And by the law of large numbers, you'd expect the >>>>>>>> distribution >>>>>>>> to flatten over time. >>>>>>>> >>>>>>>> (I gues that jamming is that only one client alone gets to the >>>>>>>>> server, whereas starving is that a client never gets to the server). >>>>>>>>> >>>>>>>> >>>>>>>> Both are statistically unlikely, if we assume the PRNG is >>>>>>>> reasonably good - which I think we can, it has been subjected to >>>>>>>> reasonable >>>>>>>> statistical tests. >>>>>>>> >>>>>>>> >>>>>>>>> >>>>>>>>> Øyvind >>>>>>>>> >>>>>>>>> >>>>>>>>>> >>>>>>>>>> Ian >>>>>>>>>> >>>>>>>>> -- >>>>>>>>> You received this message because you are subscribed to the Google >>>>>>>>> Groups "golang-nuts" group. >>>>>>>>> To unsubscribe from this group and stop receiving emails from it, >>>>>>>>> send an email to golang-nuts...@googlegroups.com. >>>>>>>>> >>>>>>>> To view this discussion on the web visit >>>>>>>>> https://groups.google.com/d/msgid/golang-nuts/ec5e5c0f-c5bf-4efb-b1c4-dc056720ba5cn%40googlegroups.com >>>>>>>>> >>>>>>>>> <https://groups.google.com/d/msgid/golang-nuts/ec5e5c0f-c5bf-4efb-b1c4-dc056720ba5cn%40googlegroups.com?utm_medium=email&utm_source=footer> >>>>>>>>> . >>>>>>>>> >>>>>>>> -- >>>>>>> You received this message because you are subscribed to the Google >>>>>>> Groups "golang-nuts" group. >>>>>>> To unsubscribe from this group and stop receiving emails from it, >>>>>>> send an email to golang-nuts...@googlegroups.com. >>>>>>> >>>>>> To view this discussion on the web visit >>>>>>> https://groups.google.com/d/msgid/golang-nuts/9186c34b-1088-4ae0-8076-6c5cd0cdde38n%40googlegroups.com >>>>>>> >>>>>>> <https://groups.google.com/d/msgid/golang-nuts/9186c34b-1088-4ae0-8076-6c5cd0cdde38n%40googlegroups.com?utm_medium=email&utm_source=footer> >>>>>>> . >>>>>>> >>>>>> >>>>>>> -- >>>>> You received this message because you are subscribed to the Google >>>>> Groups "golang-nuts" group. >>>>> To unsubscribe from this group and stop receiving emails from it, send >>>>> an email to golang-nuts...@googlegroups.com. >>>>> >>>> To view this discussion on the web visit >>>>> https://groups.google.com/d/msgid/golang-nuts/cda2055a-8024-4ab1-87ca-18a177aa1cb2n%40googlegroups.com >>>>> >>>>> <https://groups.google.com/d/msgid/golang-nuts/cda2055a-8024-4ab1-87ca-18a177aa1cb2n%40googlegroups.com?utm_medium=email&utm_source=footer> >>>>> . >>>>> >>>> -- >>> You received this message because you are subscribed to the Google >>> Groups "golang-nuts" group. >>> To unsubscribe from this group and stop receiving emails from it, send >>> an email to golang-nuts...@googlegroups.com. >>> >> To view this discussion on the web visit >>> https://groups.google.com/d/msgid/golang-nuts/944ccecd-6a70-46de-a09f-7742eab9e2a1n%40googlegroups.com >>> >>> <https://groups.google.com/d/msgid/golang-nuts/944ccecd-6a70-46de-a09f-7742eab9e2a1n%40googlegroups.com?utm_medium=email&utm_source=footer> >>> . >>> >> -- You received this message because you are subscribed to the Google Groups "golang-nuts" group. To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/b1345b82-ab11-418d-95ea-7e11541bfcabn%40googlegroups.com.
