{"action":"opened","issue":{"url":"https://api.github.com/repos/m-labs/artiq/issues/193","labels_url":"https://api.github.com/repos/m-labs/artiq/issues/193/labels{/name}","comments_url":"https://api.github.com/repos/m-labs/artiq/issues/193/comments","events_url":"https://api.github.com/repos/m-labs/artiq/issues/193/events","html_url":"https://github.com/m-labs/artiq/issues/193","id":122791452,"number":193,"title":"Following data dependencies while unrolling loops ","user":{"login":"whitequark","id":54771,"avatar_url":"https://avatars.githubusercontent.com/u/54771?v=3","gravatar_id":"","url":"https://api.github.com/users/whitequark","html_url":"https://github.com/whitequark","followers_url":"https://api.github.com/users/whitequark/followers","following_url":"https://api.github.com/users/whitequark/following{/other_user}","gists_url":"https://api.github.com/users/whitequark/gists{/gist_id}","starred_url":"https://api.github.com/users/whitequark/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/whitequark/subscriptions","organizations_url":"https://api.github.com/users/whitequark/orgs","repos_url":"https://api.github.com/users/whitequark/repos","events_url":"https://api.github.com/users/whitequark/events{/privacy}","received_events_url":"https://api.github.com/users/whitequark/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":0,"created_at":"2015-12-17T18:10:36Z","updated_at":"2015-12-17T18:10:36Z","closed_at":null,"body":"A feature has been requested (e.g. in https://github.com/m-labs/artiq/issues/42) to unroll loops where the trip count or I/O delay caused by the loop body are dependent on variables outside of the loop. Such as in:\r\n```python\r\n@kernel\r\ndef run(self):\r\n    for t in range(10):        \r\n        t2 = t*100\r\n        with parallel:\r\n            self.ttl0.pulse(t2)\r\n```\r\n\r\nThere are several language design issues with this proposal. To recap, my goal as a language designer is to create a system that is easy to reason about, and easy to form a mental model of. Specifically, someone implementing a process in ARTIQ must be able to follow a small set of straightforward rules that tell whether a given ARTIQ Python construct is legal (accepted by compiler) or not. Conversely, when the ARTIQ compiler encounters an illegal construct, it has to explain to the programmer why the entire class of these constructs is illegal.\r\n\r\nTo handle the code in the example above 'as one could expect', the compiler has to rely on many assumptions:\r\n  * It must be able to look through assignments and variable references. This is not in general possible, e.g. when closures or control flow is involved.\r\n  * It must be able to look through expressions. This is not in general possible, e.g. when functions are involved.\r\n  * It must be able to unroll loops. This is not in general possible, e.g. when control flow is involved.\r\n  * It must be able to look outside `with parallel:` blocks.\r\n\r\nRight now, I believe we have the aforementioned small set of straightforward rules for the interleaving transformation:\r\n  * the only recognized expressions are binary expressions with `+`, `-`, `*`, `/` and `//`, and arguments which are never assigned to;\r\n  * the only recognized statements are statements without I/O delay, or statements without control flow, or loops iterating over an expression which is syntactically a `range(...)` with the arguments specified above;\r\n  * all of these restrictions are only applied within a `with parallel:` block.\r\n\r\nIt is easy to design code so that it is conforming, in particular, you do not have to guess (by running the compiler) whether given code is valid. The rules above also allow the compiler to express the I/O delay caused by a function as an algebraic expression whose free variables only rely on the function arguments, which means that, no matter how deep the `with parallel:` blocks are composed, it is never necessary to look at more than one function at once.\r\n\r\nIf we begin handling assignments, things become complicated. If there's only one assignment to a given variable in the entire function, sure, it's just an alias. If there are two consecutive assignments, we can also handle this. What if there's control flow? Arguably `if True:` is as good as no control flow at all. Is `if 1 == 1:`? Is `if 1 == x` when the value of x is known? What if x is assigned in a loop? etc. Handling control flow would make it impossible to express the I/O delay incurred by a function as an algebraic expression, which means that we have to look arbitrarily deep down the call stack to understand an error.\r\n\r\nIf, apart from the above, we allow `with parallel:` blocks to affect code outside them, things become even more complicated, now we may have to look arbitrarily deep *up* call stack to understand an error.\r\n\r\nIn other words, the specific set of rules for abstract evaluation of code is complex, requires considering a potentially unlimited scope, prone to change when some corner case has to be addressed, and will inevitably contain omissions simply because some particular cases are not handled due to lack of time to implement or perceived unimportance.\r\n\r\nAs a result, to answer to the question \"will this code be accepted by the compiler?\", the programmer essentially has to write the code and try to compile it. Moreover, when it is inevitably rejected, there is no easy way to know what parts to refactor to make it acceptable, and no easy way to display a sensible diagnostic. Consider the case if `if 1 == x:`: a purported diagnostic would have to go something like this:\r\n  * Cannot interleave the code, because...\r\n  * The code has control flow, because...\r\n  * We cannot prove that `1 == x:` always has the same value, because...\r\n  * We cannot prove that `x` always has the same value, because...\r\n  * (for example) `x` could have been assigned a value in a branch we do not always take, because...\r\n  * repeat all of the above for that branch.\r\n  * (another example) `x` is assigned a value from an attribute, which is out of scope for our analysis.\r\n\r\nWith inlining, the diagnostic would gain context from an unlimited number of functions, which are implicitly called with some arguments that are not immediately visible from the source (because they come from abstractly evaluated expressions), including several invocations of the same function.\r\n\r\nWhile it is technically possible, if somewhat laborous, to implement this scheme as I describe it above, I do not believe that it comprises good language design or makes writing complex programs in ARTIQ Python easier.\r\n\r\nTo concentrate on the example above again, what's wrong with reformulating it as...\r\n```python\r\n@kernel\r\ndef run(self):\r\n    with parallel:\r\n        for t in range(10):\r\n            self.ttl0.pulse(t*100)\r\n```\r\n?\r\n\r\nI am assuming that the idea behind allowing that example is to allow `with parallel:` statements to be embedded in some more complex code. The point I am making is that naive implementation of such embedding, while possible, is not actually desirable, and whatever goals it might be trying to achieve, are worth achieving by different means.\r\n\r\nI am now asking to clarify what those goals are, so that I can implement them in a way that does not make writing ARTIQ Python programs meaninglessly painful."}}