<html><head><meta http-equiv="Content-Type" content="text/html; charset=us-ascii"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class="">This has been a most interesting thread of conversation indeed.<div class=""><br class=""></div><div class="">As a relative newcomer to the Mercury language (almost 2 years of daily use now), I initially found the determinism / mode / inst compiler messages the most frustrating part of the system but I have come to understand what they mean, what the compiler is trying to do and, running on a ten year old iMac I truly appreciate the sheer speed of the compiler to not only do its determinism analysis but also the conversion of the internal form to C (my chosen output grade) and to build the executable.</div><div class=""><br class=""></div><div class="">Having read the arguments for and against, for me, as a novice user, I don't think the current compiler could really add more than it has to offer without slowing down its overall execution time. I chose Mercury because I had heard it was designed for 'large applications' that needed to be robust. It hasn't let me down.</div><div class=""><br class=""></div><div class="">On another slightly tangential note, your comment Zoltan,</div><div class=""><br class=""></div><div class=""><font face="CourierNewPSMT" size="3" class="">The "code" in this case consists mainly of a set of machine learning systems<br class="">that were not written by humans at all, so you can't understand it by asking its<br class="">authors.</font></div><div class=""><font face="CourierNewPSMT" size="3" class=""><br class=""></font></div><div class="">...this beautifully sums up why I believe that</div><div class=""><span class="Apple-tab-span" style="white-space:pre"> </span>(a) there will always be the need for human developers and</div><div class=""><span class="Apple-tab-span" style="white-space: pre;"> </span>(b) I will never trust any code I can't see, examine and --understand--.</div><div class=""><br class=""></div><div class=""><div>And I am with Roger Penrose who says that until we understand what we mean by 'understand', that building a true fully-sentient artificial intelligence isn't something achievable. Yet. Maybe? Who knows?!</div><div><br class=""></div><div>Sean.</div><div><br class=""><blockquote type="cite" class=""><div class="">On 19 Mar 2022, at 17:07, Zoltan Somogyi <<a href="mailto:zoltan.somogyi@runbox.com" class="">zoltan.somogyi@runbox.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div class=""><br class="">2022-03-20 03:12 GMT+11:00 "Philip White" <<a href="mailto:philip@pswhite.org" class="">philip@pswhite.org</a>>:<br class=""><blockquote type="cite" class="">I've been working in my spare time on a compiler for a relational<br class="">programming language heavily inspired by mercury - it has strong and<br class="">statically checked types, modes, and determinism.<br class=""></blockquote><br class="">That is nice to hear.<br class=""><br class=""><blockquote type="cite" class="">The determinism checking approach of this language is totally different<br class="">than Mercury's approach, and I believe it yields much more precise<br class="">results, albeit via a more expensive algorithm. I'm curious if the<br class="">compiler writers ever considered something like this. If not, would you<br class="">every consider using it in the current mercury compiler?<br class=""></blockquote><br class="">No, and no.<br class=""><br class="">We the implementors of the Mercury compiler consider that compilation<br class="">speed is very important in making a language practical. If, after changing<br class="">the code of a module, the process of rebuilding the executable takes long enough<br class="">for you to lose your focus, your productivity will suffer, and we don't want that.<br class=""><br class="">The Mercury determinism analysis algorithm was purposely designed to be simple.<br class="">Its simplicity does not only make it fast, it also makes it *easily understandable*.<br class="">From time to time, we get proposals to extend it, e.g. by teaching it that if the<br class="">type of X contains only the function symbols f, g and h, then in the else case<br class="">of an if-then-else of the form "( if X = f then ... else ...)", X can only be g or h,<br class="">so a switch on X with only those two arms should be considered "det".<br class="">We have always turned such proposals down, not because of the impact<br class="">on compiler speed (which would probably be small), but because it would make<br class="">the rules of determinism analysis both harder to learn and harder to predict<br class="">even once learned.<br class=""><br class=""><blockquote type="cite" class="">Predicates written in this language go through a mode-resolution phase<br class="">in which clauses in a conjunction are re-ordered so that variables are<br class="">properly instantiated for each predicate that needs to be invoked; this<br class="">phase also selects the mode to use at each invocation. It's after this<br class="">phase that I run the determinism checker. I imagine the Mercury<br class="">compiler does something pretty similar.<br class=""></blockquote><br class="">Yes, it does. You can see it yourself by invoking mmc with the -v (verbose)<br class="">option, which tells the compiler to print a line for each phase of compilation.<br class="">You will see that type and mode analysis are followed by two passes<br class="">that gather information for determinism analysis, and then determinism<br class="">analysis itself.<br class=""><br class=""><blockquote type="cite" class="">Naively, we "execute" the predicate with each combination of<br class="">constructors that each variable can have. This guarantees that we will<br class="">hit every possible code-path of the predicate. The result of each<br class="">execution is a determinism. For example, if the predicate finishes<br class="">twice, then the result of that execution is "multi". The final<br class="">determinism of the predicate is the join of all the execution results<br class="">(i.e. the join operation of the determinism lattice). For example, if<br class="">one path yields "multi" and another yields "failure", then the final<br class="">determinism is "nondet".<br class=""><br class="">This naive approach would be prohibitively expensive for predicates<br class="">with lots variables, especially if those variables have types with many<br class="">constructors.<br class=""></blockquote><br class="">And some types, such as integers and floats, have billions of constructors,<br class="">and strings even more.<br class=""><br class=""><blockquote type="cite" class="">We can improve it by initially treating every variable as<br class="">abstract; every time the predicate attempts to pattern match a<br class="">variable, we restart execution once for each of that variable's<br class="">constructors. The algorithm is roughly the same, but we only end up<br class="">running variable combinations on-demand, so we save a lot of work<br class="">for variables that are merely moved around and never inspected.<br class=""></blockquote><br class="">This approach multiplies the amount of work you have to do by *many*<br class="">orders of magnitude. Using techniques from areas such as model checking<br class="">or concolic testing, you may be able to get most of those orders of magnitude<br class="">back, but you would have to do a *lot* of work to achieve even 1% of the<br class="">speed of the Mercury determinism analysis algorithm.<br class=""><br class=""><blockquote type="cite" class="">There are a few details that I've glossed over, but this is the general<br class="">idea. It's definitely a more expensive algorithm than something that is<br class="">more syntax directed, but I think it will notice switch statements more<br class="">often than Mercury does, and it will also determine that a set of<br class="">variables is exhaustive more often than the Mercury compiler. (I make<br class="">this claim mostly based on my understanding of the Mercury compiler<br class="">from the documentation, rather than from experience; I bet I can<br class="">furnish examples if you would like to see any, though)<br class=""></blockquote><br class="">I believe the claim that you could get more precise determinisms<br class="">than the Mercury compiler. I don't believe that the effort will be worth it,<br class="">for a simple reason: the current Mercury determinism analysis algorithm,<br class="">simple as it is, is *already* smart enough in practice. It is very rare for me<br class="">to get an error message from the compiler about a determinism error<br class="">where that error is caused by the compiler not being smart enough to see<br class="">the actual determinism of the code. In virtually all cases, when the error<br class="">message says that the inferred determinism of this predicate is e.g. semidet,<br class="">then that will be the actual determinism of the code, because of a bug<br class="">in the actual code, such as a missing case in a switch. Very rarely, the cause<br class="">is a bug in the mode declaration; I forgot to tell the compiler that e.g.<br class="">this predicate expects its caller to specify a value for an argument<br class="">that makes unreachable the "missing" case in that switch. Having the cause of the<br class="">error message be a limitation in determinism analysis is even rarer,<br class="">and the only such limitation that I bump into more than about once a year<br class="">is that switch detection does not look into disjunctions deep enough.<br class="">That is a problem so rare you probably don't even know what I am talking about :-(<br class=""><br class=""><blockquote type="cite" class="">I'd love to hear what people think of this approach. I haven't yet<br class="">tested it at large scale with huge predicates, so my biggest concern is<br class="">that it will be really, really slow.<br class=""></blockquote><br class="">I can tell you right away that I don't believe anyone can make your approach<br class="">fast enough for people to accept, simply because the threshold of how long<br class="">people are willing to wait for compilation is so low nowadays. Look at the<br class="">Rust community, which is struggling to make the speed of the Rust compiler acceptable,<br class="">despite the fact that they are using algorithms with much lower complexities<br class="">than what you are proposing.<br class=""><br class="">Sorry to be the bearer of bad news, but you did ask ...<br class=""><br class="">Zoltan.<br class="">_______________________________________________<br class="">users mailing list<br class=""><a href="mailto:users@lists.mercurylang.org" class="">users@lists.mercurylang.org</a><br class="">https://lists.mercurylang.org/listinfo/users<br class=""></div></div></blockquote></div><br class=""></div></body></html>