<div dir="ltr"><div class="gmail_default" style="font-family:monospace,monospace">Oh dear. NEVER defer to experts. Listen to experts,</div><div class="gmail_default" style="font-family:monospace,monospace">use your own judgement, and measure, measure, measure.</div><div class="gmail_default" style="font-family:monospace,monospace"><br></div><div class="gmail_default" style="font-family:monospace,monospace">Consider some like (Prolog):</div><div class="gmail_default" style="font-family:monospace,monospace"> :- p(X, a, Z),</div><div class="gmail_default" style="font-family:monospace,monospace"> q(Z, W),</div><div class="gmail_default" style="font-family:monospace,monospace"> r(W, X, Z).</div><div class="gmail_default" style="font-family:monospace,monospace"><br></div><div class="gmail_default" style="font-family:monospace,monospace">This, I take it, is what you mean when you refer to</div><div class="gmail_default" style="font-family:monospace,monospace">"non-determinism". It appears to be a three-nested-</div><div class="gmail_default" style="font-family:monospace,monospace">loop search. But it might not be! It depends on</div><div class="gmail_default" style="font-family:monospace,monospace">what level of indexing the Prolog system offers.</div><div class="gmail_default" style="font-family:monospace,monospace">The call to p/3 *might* be a simple lookup;</div><div class="gmail_default" style="font-family:monospace,monospace">the call to q/2 *might* also be a simple lookup</div><div class="gmail_default" style="font-family:monospace,monospace">(given Z), and then the call to r/3 might be a search.</div><div class="gmail_default" style="font-family:monospace,monospace">It's exactly the same with joins in SQL. A join</div><div class="gmail_default" style="font-family:monospace,monospace">*might* be a big search, it *might* be a merge, it</div><div class="gmail_default" style="font-family:monospace,monospace">*might* be a linear time hashed join, or it might</div><div class="gmail_default" style="font-family:monospace,monospace">even about to a single lookup. That's actually the</div><div class="gmail_default" style="font-family:monospace,monospace">basic point of SQL. Divide data base design into</div><div class="gmail_default" style="font-family:monospace,monospace">(a) setting up a "language" in which every query</div><div class="gmail_default" style="font-family:monospace,monospace">you might need is expressible, then (b) choosing an</div><div class="gmail_default" style="font-family:monospace,monospace">indexing structure in which the queries you DO turn</div><div class="gmail_default" style="font-family:monospace,monospace">out to need are acceptably efficient.</div><div class="gmail_default" style="font-family:monospace,monospace"><br></div><div class="gmail_default" style="font-family:monospace,monospace">This is a "separation of concerns". First worry</div><div class="gmail_default" style="font-family:monospace,monospace">about correctness, then worry about efficiency.</div><div class="gmail_default" style="font-family:monospace,monospace">This has implications for language design (it has</div><div class="gmail_default" style="font-family:monospace,monospace">to be POSSIBLE to add appropriate indexing support)</div><div class="gmail_default" style="font-family:monospace,monospace">and sad to say, this is one area where many Prolog</div><div class="gmail_default" style="font-family:monospace,monospace">systems did not do well. It also has implications</div><div class="gmail_default" style="font-family:monospace,monospace">for readability, both good and bad. The good</div><div class="gmail_default" style="font-family:monospace,monospace">implication is that if you are trying to see what</div><div class="gmail_default" style="font-family:monospace,monospace">a code fragment computes, it isn't cluttered up with</div><div class="gmail_default" style="font-family:monospace,monospace">implementation detail. The bad implication is that</div><div class="gmail_default" style="font-family:monospace,monospace">the design work to make the code efficient is not</div><div class="gmail_default" style="font-family:monospace,monospace">*there* in the code, it's somewhere else in the</div><div class="gmail_default" style="font-family:monospace,monospace">index declarations, so if you want to understand HOW</div><div class="gmail_default" style="font-family:monospace,monospace">the code performs acceptably, you have more reading</div><div class="gmail_default" style="font-family:monospace,monospace">work to do.</div><div class="gmail_default" style="font-family:monospace,monospace"><br></div><div class="gmail_default" style="font-family:monospace,monospace">I'll skip to the final point.</div><div class="gmail_default" style="font-family:monospace,monospace">"When is the elegance of a non-deterministic solution acceptable given its inefficiency?" <br></div><div class="gmail_default" style="font-family:monospace,monospace">Answer 1: WHEN YOU ACCEPT IT. That's really the only</div><div class="gmail_default" style="font-family:monospace,monospace">answer there is. It's acceptable when it satisfies YOUR</div><div class="gmail_default" style="font-family:monospace,monospace">criteria for acceptability. It depends on what you need</div><div class="gmail_default" style="font-family:monospace,monospace">that code to be/do. Fast enough is fast enough.</div><div class="gmail_default" style="font-family:monospace,monospace"><br></div><div class="gmail_default" style="font-family:monospace,monospace">Answer 2: THERE IS A FALSE PRESUPPOSITION IN THE QUESTION.</div><div class="gmail_default" style="font-family:monospace,monospace">"given its inefficiency"? I've just explained that the</div><div class="gmail_default" style="font-family:monospace,monospace">efficiency of a query in Prolog or SQL depends on what the</div><div class="gmail_default" style="font-family:monospace,monospace">indexing support is. The very same query might be very</div><div class="gmail_default" style="font-family:monospace,monospace">efficient or very inefficient. In the case of Mercury,</div><div class="gmail_default" style="font-family:monospace,monospace">the compiler tries to reorder your code -- much like an</div><div class="gmail_default" style="font-family:monospace,monospace">SQL optimiser would -- to improve its efficiency.</div><div class="gmail_default" style="font-family:monospace,monospace">DEC-10 Prolog and its faithful successors came with a</div><div class="gmail_default" style="font-family:monospace,monospace">source code rewriting feature you could use (admittedly</div><div class="gmail_default" style="font-family:monospace,monospace">with much effort) to replace a clear but inefficient</div><div class="gmail_default" style="font-family:monospace,monospace">subquery with whatever you thought would be better.</div><div class="gmail_default" style="font-family:monospace,monospace">(InterLISP had, no, has, Medley is open source now, a</div><div class="gmail_default" style="font-family:monospace,monospace">similar feature. Erlang has a similar feature which IS</div><div class="gmail_default" style="font-family:monospace,monospace">used for query optimisation.) For that matter, there</div><div class="gmail_default" style="font-family:monospace,monospace">seems to be a presupposition in the question that</div><div class="gmail_default" style="font-family:monospace,monospace">deterministic code is efficient. That is not necessarily</div><div class="gmail_default" style="font-family:monospace,monospace">the case. Consider the classic example of computing</div><div class="gmail_default" style="font-family:monospace,monospace">Fibonacci numbers. The obvious algorithm for F(n) takes</div><div class="gmail_default" style="font-family:monospace,monospace">O(2**n) time. A straightforward algorithm takes O(n)</div><div class="gmail_default" style="font-family:monospace,monospace">time. A matrix algorithm (which is perfectly obvious once</div><div class="gmail_default" style="font-family:monospace,monospace">it has been explained to you) takes O(log n) time. All</div><div class="gmail_default" style="font-family:monospace,monospace">three algorithms are deterministic.</div><div class="gmail_default" style="font-family:monospace,monospace"><br></div><div class="gmail_default" style="font-family:monospace,monospace">So:</div><div class="gmail_default" style="font-family:monospace,monospace">- be clear about what your problem is and how efficient</div><div class="gmail_default" style="font-family:monospace,monospace"> it needs to be</div><div class="gmail_default" style="font-family:monospace,monospace">- write a simple program to solve the problem and play</div><div class="gmail_default" style="font-family:monospace,monospace"> with some test cases to make sure that your solution</div><div class="gmail_default" style="font-family:monospace,monospace"> is correct</div><div class="gmail_default" style="font-family:monospace,monospace">- profile the program on larger examples to see where</div><div class="gmail_default" style="font-family:monospace,monospace"> the shoe pinches</div><div class="gmail_default" style="font-family:monospace,monospace">- add declarations to help the compiler do better ...</div><div class="gmail_default" style="font-family:monospace,monospace">- add supporting indices or other data structures as</div><div class="gmail_default" style="font-family:monospace,monospace"> needed</div><div class="gmail_default" style="font-family:monospace,monospace">- keep checking that your improvements don't break anything</div><div class="gmail_default" style="font-family:monospace,monospace">- it's acceptable when you accept it.</div><div class="gmail_default" style="font-family:monospace,monospace"><br></div><div class="gmail_default" style="font-family:monospace,monospace">Just today I read this post</div><div class="gmail_default" style="font-family:monospace,monospace"><a href="https://cohost.org/mononcqc/post/1128460-on-the-hunt-for-a-bu">https://cohost.org/mononcqc/post/1128460-on-the-hunt-for-a-bu</a></div><div class="gmail_default" style="font-family:monospace,monospace">about a small change to some code improving the throughput</div><div class="gmail_default" style="font-family:monospace,monospace">of the program from 50 kB/sec to 30 MB/sec (in Erlang).</div><div class="gmail_default" style="font-family:monospace,monospace">At a general level, we can say that the author</div><div class="gmail_default" style="font-family:monospace,monospace">- Recognised a performance problem</div><div class="gmail_default" style="font-family:monospace,monospace">- Used profiling tools to characterise it better</div><div class="gmail_default" style="font-family:monospace,monospace">- Understood his (functional!) language well enough</div><div class="gmail_default" style="font-family:monospace,monospace"> to understand what might be causing it</div><div class="gmail_default" style="font-family:monospace,monospace">- did an experiment to check the hypothesis.</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Sun, 5 Mar 2023 at 04:26, Mark Clements <<a href="mailto:mark.clements@ki.se">mark.clements@ki.se</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div class="msg2775592494991704595"> <div dir="ltr"> <div style="font-family:Calibri,Arial,Helvetica,sans-serif;font-size:12pt;color:rgb(0,0,0);background-color:rgb(255,255,255)"> Zoltan and Richard, <div><br> </div> <div>I drafted a response a few months ago that I never sent: given that my main field is not computer science, I deferred to you. </div> <div><br> </div> <div>As a follow-up: when should one use non-determinism and when should one use Mercury? To motivate my questions: I came to Mercury because I was looking for a typed "Prolog" that allowed for elegant joins between relationships (essentially to replace SQL:). Zoltan's implementation for the CSV example is canonical and efficient code - but it is also comparatively long and uses several data structures that could be replaced by less efficient non-determinism. When is the elegance of a non-deterministic solution acceptable given its inefficiency?</div> <div><br> </div> <div>Sincerely, Mark.</div> <br> </div> <div id="m_2775592494991704595appendonsend"></div> <hr style="display:inline-block;width:98%"> <div id="m_2775592494991704595divRplyFwdMsg" dir="ltr"><font style="font-size:11pt" face="Calibri, sans-serif" color="#000000"><b>From:</b> Richard O'Keefe <<a href="mailto:raoknz@gmail.com" target="_blank">raoknz@gmail.com</a>><br> <b>Sent:</b> 31 December 2022 04:57<br> <b>To:</b> <a href="mailto:zoltan.somogyi@runbox.com" target="_blank">zoltan.somogyi@runbox.com</a> <<a href="mailto:zoltan.somogyi@runbox.com" target="_blank">zoltan.somogyi@runbox.com</a>><br> <b>Cc:</b> Mark Clements <<a href="mailto:mark.clements@ki.se" target="_blank">mark.clements@ki.se</a>>; users <<a href="mailto:users@lists.mercurylang.org" target="_blank">users@lists.mercurylang.org</a>><br> <b>Subject:</b> Re: [m-users.] Announcement (aggregates module) + questions (window functions)</font> <div> </div> </div> <div> <table style="border:0px none;display:table;width:100%;table-layout:fixed;float:none" width="100%" cellspacing="0" cellpadding="0" border="0" align="left"> <tbody style="display:block"> <tr> <td cellpadding="7px 2px 7px 2px" style="padding:7px 2px;background-color:rgb(166,166,166)" width="1px" valign="middle" bgcolor="#A6A6A6"> </td> <td cellpadding="7px 5px 7px 15px" color="#212121" style="width:100%;background-color:rgb(234,234,234);padding:7px 5px 7px 15px;font-family:wf_segoe-ui_normal,Segoe UI,Segoe WP,Tahoma,Arial,sans-serif;font-size:12px;font-weight:normal;color:rgb(33,33,33);text-align:left" width="100%" valign="middle" bgcolor="#EAEAEA"> <div>You don't often get email from <a href="mailto:raoknz@gmail.com" target="_blank">raoknz@gmail.com</a>. <a href="https://aka.ms/LearnAboutSenderIdentification" target="_blank"> Learn why this is important</a></div> </td> <td cellpadding="7px 5px 7px 5px" color="#212121" style="width:75px;background-color:rgb(234,234,234);padding:7px 5px;font-family:wf_segoe-ui_normal,Segoe UI,Segoe WP,Tahoma,Arial,sans-serif;font-size:12px;font-weight:normal;color:rgb(33,33,33);text-align:left" width="75px" valign="middle" bgcolor="#EAEAEA" align="left"> </td> </tr> </tbody> </table> <div> <div dir="ltr"> <div style="font-family:monospace,monospace">I'd like to second Zoltan's point.</div> <div style="font-family:monospace,monospace">I've solved that particular Rosetta Code problem in two different</div> <div style="font-family:monospace,monospace">programming languages, using an imperative style with hash tables,</div> <div style="font-family:monospace,monospace">and modulo the usual hand-waving about hash-tables being "O(1)"</div> <div style="font-family:monospace,monospace">-- which is fair enough in this case -- the code is obviously</div> <div style="font-family:monospace,monospace">linear in the size of the two CSV files the program has to read.</div> <div style="font-family:monospace,monospace"><br> </div> <div style="font-family:monospace,monospace">I'm reminded of my experience with XPath, XQuery, and XSLT, that</div> <div style="font-family:monospace,monospace">sometimes it is simpler and more readable NOT to use a specialised</div> <div style="font-family:monospace,monospace">query language but to use plain high level code in a language with</div> <div style="font-family:monospace,monospace">decent facilities. (Such as Mercury.) Not coincidentally, XPath,</div> <div style="font-family:monospace,monospace">XQuery, and XSLT hide practically everything you need to understand</div> <div style="font-family:monospace,monospace">performance.</div> <div style="font-family:monospace,monospace"><br> </div> </div> <br> <div> <div dir="ltr">On Sat, 31 Dec 2022 at 08:35, Zoltan Somogyi <<a href="mailto:zoltan.somogyi@runbox.com" target="_blank">zoltan.somogyi@runbox.com</a>> wrote:<br> </div> <blockquote style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"> <br> 2022-12-30 00:27 GMT+11:00 "Mark Clements" <<a href="mailto:mark.clements@ki.se" target="_blank">mark.clements@ki.se</a>>:<br> > %% patient and visit are nondet predicates<br> > main(!IO) :-<br> > print_line("{Id, RowNumber, Date, Score, CumScore}", !IO),<br> > aggregate((pred({Id,RowNumber,Datei,Scorei,CumScorei}::out) is nondet :-<br> > patient(Id,_),<br> > Combined = (pred(Date::out,Score::out) is nondet :- visit(Id,Date,Score)),<br> > Combined(Datei,Scorei),<br> > bag_cum_sum(Combined)(Datei,CumScorei),<br> > Dates = (pred(Date::out) is nondet :- Combined(Date,_)),<br> > bag_row_number(Dates)(Datei,RowNumber)),<br> > print_line,<br> > !IO).<br> > <br> > Third, I have sought to stay with nondet predicates, with the implementation internally using lists -- is there a better approach?<br> <br> I think that getting your data from nondet predicates is fundamentally a bad idea.<br> The reason is simple: it bakes the data into the program. If you want to run<br> the same task on a different data set, you have to modify the program and recompile it.<br> This is much less convenient than a program that you can run on a different data set<br> simply by invoking it with different file names.<br> <br> The attached code is my solution to the same task on <a href="https://eur01.safelinks.protection.outlook.com/?url=http%3A%2F%2Frosettacode.org%2F&data=05%7C01%7Cmark.clements%40ki.se%7C585dbab45ec34f7f25ef08daeae32777%7Cbff7eef1cf4b4f32be3da1dda043c05d%7C0%7C0%7C638080559250227740%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C2000%7C%7C%7C&sdata=tHDpCagECzIIv%2FsnHGSobrwGJS4wgMOfxMwkUswQ%2BBo%3D&reserved=0" rel="noreferrer" target="_blank"> rosettacode.org</a>.<br> You will note that its operative part is longer than your code above,<br> but it is also much simpler, and therefore easier to read and to<br> understand. It is also easier to reason about its performance.<br> For example,<br> <br> - the main operation loops over all visits,<br> - the non-constant-time part of each iteration consists of lookup and update operations<br> on its main data structure, VisitDataMap,<br> - VisitDataMap is a map, and is therefore implemented using balanced trees.<br> <br> This makes it clear that its complexity is O(N log N), where N is the number of visits.<br> (Technically, it is O(N log M), where M is the number of unique patients, but the<br> difference is negligible.) By contrast, I cannot tell anything about the performance<br> of the aggregate-using code above, because all the relevant details are hidden<br> behind abstraction boundaries, whose documentation is silent about performance.<br> Note that in the SQL programs from which you draw your inspiration, selecting<br> the right set of indexes for each relation is usually an important design concern.<br> <br> Zoltan._______________________________________________<br> users mailing list<br> <a href="mailto:users@lists.mercurylang.org" target="_blank">users@lists.mercurylang.org</a><br> <a href="https://eur01.safelinks.protection.outlook.com/?url=https%3A%2F%2Flists.mercurylang.org%2Flistinfo%2Fusers&data=05%7C01%7Cmark.clements%40ki.se%7C585dbab45ec34f7f25ef08daeae32777%7Cbff7eef1cf4b4f32be3da1dda043c05d%7C0%7C0%7C638080559250227740%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C2000%7C%7C%7C&sdata=ifg5Y1A2bX92Y5sjcVVwesIHjFXY42k0fKIydxoUXZs%3D&reserved=0" rel="noreferrer" target="_blank">https://lists.mercurylang.org/listinfo/users</a><br> </blockquote> </div> </div> </div> <u></u> <p><span></span><br> </p> <p><span></span><br> </p> <p><span><i>När du skickar e-post till Karolinska Institutet (KI) innebär detta att KI kommer att behandla dina personuppgifter. </i><a href="https://ki.se/medarbetare/integritetsskyddspolicy" target="_blank"><span>Här finns information om hur KI behandlar personuppgifter</span></a>.<span> </span></span></p> <p><span></span><br> </p> <p><span><i>Sending email to Karolinska Institutet (KI) will result in KI processing your personal data.</i> <a href="https://ki.se/en/staff/data-protection-policy" target="_blank"><span>You can read more about KI’s processing of personal data here</span></a>.<span> </span></span></p> </div> </div></blockquote></div>