{"action":"created","comment":{"url":"https://api.github.com/repos/mila-udem/myia/pulls/comments/181238259","pull_request_review_id":111816312,"id":181238259,"diff_hunk":"@@ -0,0 +1,205 @@\n+\"\"\"Graph optimization routines.\"\"\"\n+\n+\n+from myia.unify import Var, Unification, expandlist\n+from myia.graph_utils import toposort\n+from myia.anf_ir import ANFNode, Graph, Apply, Constant, Special\n+from myia.anf_ir_utils import \\\n+    succ_incoming, freevars_boundary, replace, \\\n+    is_apply, is_constant, is_parameter\n+\n+\n+class VarNode(Special):\n+    \"\"\"Graph node that represents a variable.\"\"\"\n+\n+    def __var__(self):\n+        return self.special\n+\n+\n+def sexp_to_node(sexp, graph, multigraph=False):\n+    \"\"\"Convert an s-expression (tuple) to a subgraph.\n+\n+    Args:\n+        sexp: A nested tuple that represents an expression.\n+        graph: The graph in which to place the created nodes.\n+        multigraph: If multigraph is True and graph is a Var, then\n+            every child node will have a fresh Var as its Graph.\n+            In short, use multigraph=True to get a subgraph where\n+            each node can be in a different graph. Otherwise, all\n+            nodes are required to belong to the same graph.\n+\n+    Returns:\n+        An ANFNode equivalent to the given s-expression.\n+\n+    \"\"\"\n+    if isinstance(sexp, tuple):\n+        if multigraph and isinstance(graph, Var):\n+            return Apply([sexp_to_node(x, Var('G'), True)  # type: ignore\n+                          for x in sexp], graph)  # type: ignore\n+        else:\n+            return Apply([sexp_to_node(x, graph, multigraph)\n+                          for x in sexp], graph)\n+    elif isinstance(sexp, Var):\n+        return VarNode(sexp, graph)\n+    elif isinstance(sexp, ANFNode):\n+        return sexp\n+    else:\n+        return Constant(sexp)\n+\n+\n+def sexp_to_graph(sexp):\n+    \"\"\"Convert an s-expression to a Graph.\n+\n+    This converts the s-expression to a subgraph of ANFNodes and then sets that\n+    subgraph as the output of a new Graph.\n+    \"\"\"\n+    g = Graph()\n+    g.output = sexp_to_node(sexp, g)\n+    return g\n+\n+\n+class GraphUnification(Unification):\n+    \"\"\"Unification subclass that can unify subgraphs.\"\"\"\n+\n+    def visit(self, fn, node):\n+        \"\"\"Visit a node and apply fn to all children.\"\"\"\n+        if is_apply(node):\n+            new_inputs = expandlist(map(fn, node.inputs))\n+            g = fn(node.graph)\n+            return Apply(new_inputs, g)  # type: ignore\n+        elif is_parameter(node):\n+            g = fn(node.graph)\n+            if not isinstance(g, Graph) or g is not node.graph:\n+                # Note: this condition will be triggered if e.g. there is a\n+                # Parameter in a pattern to reify. It's not clear what that's\n+                # supposed to mean unless the Parameter already exists in a\n+                # concrete graph, so we raise an Exception just in case.\n+                raise Exception('Unification cannot create new Parameters.') \\\n+                    # pragma: no cover","path":"myia/opt.py","position":78,"original_position":78,"commit_id":"78e1da333c0c6dec5e1826881c486e1d5131f95e","original_commit_id":"78e1da333c0c6dec5e1826881c486e1d5131f95e","user":{"login":"breuleux","id":599820,"avatar_url":"https://avatars3.githubusercontent.com/u/599820?v=4","gravatar_id":"","url":"https://api.github.com/users/breuleux","html_url":"https://github.com/breuleux","followers_url":"https://api.github.com/users/breuleux/followers","following_url":"https://api.github.com/users/breuleux/following{/other_user}","gists_url":"https://api.github.com/users/breuleux/gists{/gist_id}","starred_url":"https://api.github.com/users/breuleux/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/breuleux/subscriptions","organizations_url":"https://api.github.com/users/breuleux/orgs","repos_url":"https://api.github.com/users/breuleux/repos","events_url":"https://api.github.com/users/breuleux/events{/privacy}","received_events_url":"https://api.github.com/users/breuleux/received_events","type":"User","site_admin":false},"body":"Because when I was testing things, I carelessly made a pattern that had a parameter, and it took me a while to realize why matching didn't work. I think I prefer to keep an Exception (maybe TypeError would be more appropriate), in case this (constructing patterns) gets exposed to more developers in the future.","created_at":"2018-04-12T22:17:49Z","updated_at":"2018-04-12T22:17:49Z","html_url":"https://github.com/mila-udem/myia/pull/52#discussion_r181238259","pull_request_url":"https://api.github.com/repos/mila-udem/myia/pulls/52","author_association":"COLLABORATOR","_links":{"self":{"href":"https://api.github.com/repos/mila-udem/myia/pulls/comments/181238259"},"html":{"href":"https://github.com/mila-udem/myia/pull/52#discussion_r181238259"},"pull_request":{"href":"https://api.github.com/repos/mila-udem/myia/pulls/52"}},"in_reply_to_id":181224564},"pull_request":{"url":"https://api.github.com/repos/mila-udem/myia/pulls/52","id":180071648,"html_url":"https://github.com/mila-udem/myia/pull/52","diff_url":"https://github.com/mila-udem/myia/pull/52.diff","patch_url":"https://github.com/mila-udem/myia/pull/52.patch","issue_url":"https://api.github.com/repos/mila-udem/myia/issues/52","number":52,"state":"open","locked":false,"title":"Pattern-based optimization","user":{"login":"breuleux","id":599820,"avatar_url":"https://avatars3.githubusercontent.com/u/599820?v=4","gravatar_id":"","url":"https://api.github.com/users/breuleux","html_url":"https://github.com/breuleux","followers_url":"https://api.github.com/users/breuleux/followers","following_url":"https://api.github.com/users/breuleux/following{/other_user}","gists_url":"https://api.github.com/users/breuleux/gists{/gist_id}","starred_url":"https://api.github.com/users/breuleux/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/breuleux/subscriptions","organizations_url":"https://api.github.com/users/breuleux/orgs","repos_url":"https://api.github.com/users/breuleux/repos","events_url":"https://api.github.com/users/breuleux/events{/privacy}","received_events_url":"https://api.github.com/users/breuleux/received_events","type":"User","site_admin":false},"body":"This adds a simple mechanism to define and apply pattern-based optimizations. A pattern and its replacement can be defined as nested tuples (s-expressions of sorts) in which primitives, constants and variables (Var instances) can figure. For example, to define `x+0 -> x`, you can define `X = Var('X'); PatternSubstitutionOptimization((primops.add, X, 0), X)`\r\n\r\n`PatternOptimizerSinglePass` and `PatternOptimizerEquilibrium` can be used to respectively apply a set of patterns to every node in a graph, and to apply the patterns on a set of graphs repeatedly until there are no changes. The implementation is straightforward for now: it toposorts the graph, applies patterns, rinse, repeat. If a smarter process is needed we can deal with that another time.\r\n\r\n<s>This includes PR #46, which is required for inlining, although that's pointless right now because inlining is not included or tested in this branch at the moment (it'll come soon enough).</s>\r\n","created_at":"2018-04-06T22:59:37Z","updated_at":"2018-04-12T22:17:49Z","closed_at":null,"merged_at":null,"merge_commit_sha":"1be7988fc617e1e34f872f0c5f93a79fe6410c8c","assignee":null,"assignees":[],"requested_reviewers":[],"requested_teams":[],"labels":[],"milestone":null,"commits_url":"https://api.github.com/repos/mila-udem/myia/pulls/52/commits","review_comments_url":"https://api.github.com/repos/mila-udem/myia/pulls/52/comments","review_comment_url":"https://api.github.com/repos/mila-udem/myia/pulls/comments{/number}","comments_url":"https://api.github.com/repos/mila-udem/myia/issues/52/comments","statuses_url":"https://api.github.com/repos/mila-udem/myia/statuses/78e1da333c0c6dec5e1826881c486e1d5131f95e","head":{"label":"breuleux:opt","ref":"opt","sha":"78e1da333c0c6dec5e1826881c486e1d5131f95e","user":{"login":"breuleux","id":599820,"avatar_url":"https://avatars3.githubusercontent.com/u/599820?v=4","gravatar_id":"","url":"https://api.github.com/users/breuleux","html_url":"https://github.com/breuleux","followers_url":"https://api.github.com/users/breuleux/followers","following_url":"https://api.github.com/users/breuleux/following{/other_user}","gists_url":"https://api.github.com/users/breuleux/gists{/gist_id}","starred_url":"https://api.github.com/users/breuleux/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/breuleux/subscriptions","organizations_url":"https://api.github.com/users/breuleux/orgs","repos_url":"https://api.github.com/users/breuleux/repos","events_url":"https://api.github.com/users/breuleux/events{/privacy}","received_events_url":"https://api.github.com/users/breuleux/received_events","type":"User","site_admin":false},"repo":{"id":120800538,"name":"myia","full_name":"breuleux/myia","owner":{"login":"breuleux","id":599820,"avatar_url":"https://avatars3.githubusercontent.com/u/599820?v=4","gravatar_id":"","url":"https://api.github.com/users/breuleux","html_url":"https://github.com/breuleux","followers_url":"https://api.github.com/users/breuleux/followers","following_url":"https://api.github.com/users/breuleux/following{/other_user}","gists_url":"https://api.github.com/users/breuleux/gists{/gist_id}","starred_url":"https://api.github.com/users/breuleux/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/breuleux/subscriptions","organizations_url":"https://api.github.com/users/breuleux/orgs","repos_url":"https://api.github.com/users/breuleux/repos","events_url":"https://api.github.com/users/breuleux/events{/privacy}","received_events_url":"https://api.github.com/users/breuleux/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/breuleux/myia","description":"Myia prototyping","fork":true,"url":"https://api.github.com/repos/breuleux/myia","forks_url":"https://api.github.com/repos/breuleux/myia/forks","keys_url":"https://api.github.com/repos/breuleux/myia/keys{/key_id}","collaborators_url":"https://api.github.com/repos/breuleux/myia/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/breuleux/myia/teams","hooks_url":"https://api.github.com/repos/breuleux/myia/hooks","issue_events_url":"https://api.github.com/repos/breuleux/myia/issues/events{/number}","events_url":"https://api.github.com/repos/breuleux/myia/events","assignees_url":"https://api.github.com/repos/breuleux/myia/assignees{/user}","branches_url":"https://api.github.com/repos/breuleux/myia/branches{/branch}","tags_url":"https://api.github.com/repos/breuleux/myia/tags","blobs_url":"https://api.github.com/repos/breuleux/myia/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/breuleux/myia/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/breuleux/myia/git/refs{/sha}","trees_url":"https://api.github.com/repos/breuleux/myia/git/trees{/sha}","statuses_url":"https://api.github.com/repos/breuleux/myia/statuses/{sha}","languages_url":"https://api.github.com/repos/breuleux/myia/languages","stargazers_url":"https://api.github.com/repos/breuleux/myia/stargazers","contributors_url":"https://api.github.com/repos/breuleux/myia/contributors","subscribers_url":"https://api.github.com/repos/breuleux/myia/subscribers","subscription_url":"https://api.github.com/repos/breuleux/myia/subscription","commits_url":"https://api.github.com/repos/breuleux/myia/commits{/sha}","git_commits_url":"https://api.github.com/repos/breuleux/myia/git/commits{/sha}","comments_url":"https://api.github.com/repos/breuleux/myia/comments{/number}","issue_comment_url":"https://api.github.com/repos/breuleux/myia/issues/comments{/number}","contents_url":"https://api.github.com/repos/breuleux/myia/contents/{+path}","compare_url":"https://api.github.com/repos/breuleux/myia/compare/{base}...{head}","merges_url":"https://api.github.com/repos/breuleux/myia/merges","archive_url":"https://api.github.com/repos/breuleux/myia/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/breuleux/myia/downloads","issues_url":"https://api.github.com/repos/breuleux/myia/issues{/number}","pulls_url":"https://api.github.com/repos/breuleux/myia/pulls{/number}","milestones_url":"https://api.github.com/repos/breuleux/myia/milestones{/number}","notifications_url":"https://api.github.com/repos/breuleux/myia/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/breuleux/myia/labels{/name}","releases_url":"https://api.github.com/repos/breuleux/myia/releases{/id}","deployments_url":"https://api.github.com/repos/breuleux/myia/deployments","created_at":"2018-02-08T18:27:29Z","updated_at":"2018-03-16T04:56:32Z","pushed_at":"2018-04-12T19:28:23Z","git_url":"git://github.com/breuleux/myia.git","ssh_url":"git@github.com:breuleux/myia.git","clone_url":"https://github.com/breuleux/myia.git","svn_url":"https://github.com/breuleux/myia","homepage":null,"size":770,"stargazers_count":0,"watchers_count":0,"language":"Python","has_issues":false,"has_projects":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"archived":false,"open_issues_count":0,"license":null,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"mila-udem:clean","ref":"clean","sha":"ae1c92f66eb0aaadb9dbc0bd6953ce72b567e83e","user":{"login":"mila-udem","id":11724251,"avatar_url":"https://avatars0.githubusercontent.com/u/11724251?v=4","gravatar_id":"","url":"https://api.github.com/users/mila-udem","html_url":"https://github.com/mila-udem","followers_url":"https://api.github.com/users/mila-udem/followers","following_url":"https://api.github.com/users/mila-udem/following{/other_user}","gists_url":"https://api.github.com/users/mila-udem/gists{/gist_id}","starred_url":"https://api.github.com/users/mila-udem/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mila-udem/subscriptions","organizations_url":"https://api.github.com/users/mila-udem/orgs","repos_url":"https://api.github.com/users/mila-udem/repos","events_url":"https://api.github.com/users/mila-udem/events{/privacy}","received_events_url":"https://api.github.com/users/mila-udem/received_events","type":"Organization","site_admin":false},"repo":{"id":104973687,"name":"myia","full_name":"mila-udem/myia","owner":{"login":"mila-udem","id":11724251,"avatar_url":"https://avatars0.githubusercontent.com/u/11724251?v=4","gravatar_id":"","url":"https://api.github.com/users/mila-udem","html_url":"https://github.com/mila-udem","followers_url":"https://api.github.com/users/mila-udem/followers","following_url":"https://api.github.com/users/mila-udem/following{/other_user}","gists_url":"https://api.github.com/users/mila-udem/gists{/gist_id}","starred_url":"https://api.github.com/users/mila-udem/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mila-udem/subscriptions","organizations_url":"https://api.github.com/users/mila-udem/orgs","repos_url":"https://api.github.com/users/mila-udem/repos","events_url":"https://api.github.com/users/mila-udem/events{/privacy}","received_events_url":"https://api.github.com/users/mila-udem/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/mila-udem/myia","description":"Myia prototyping","fork":false,"url":"https://api.github.com/repos/mila-udem/myia","forks_url":"https://api.github.com/repos/mila-udem/myia/forks","keys_url":"https://api.github.com/repos/mila-udem/myia/keys{/key_id}","collaborators_url":"https://api.github.com/repos/mila-udem/myia/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/mila-udem/myia/teams","hooks_url":"https://api.github.com/repos/mila-udem/myia/hooks","issue_events_url":"https://api.github.com/repos/mila-udem/myia/issues/events{/number}","events_url":"https://api.github.com/repos/mila-udem/myia/events","assignees_url":"https://api.github.com/repos/mila-udem/myia/assignees{/user}","branches_url":"https://api.github.com/repos/mila-udem/myia/branches{/branch}","tags_url":"https://api.github.com/repos/mila-udem/myia/tags","blobs_url":"https://api.github.com/repos/mila-udem/myia/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/mila-udem/myia/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/mila-udem/myia/git/refs{/sha}","trees_url":"https://api.github.com/repos/mila-udem/myia/git/trees{/sha}","statuses_url":"https://api.github.com/repos/mila-udem/myia/statuses/{sha}","languages_url":"https://api.github.com/repos/mila-udem/myia/languages","stargazers_url":"https://api.github.com/repos/mila-udem/myia/stargazers","contributors_url":"https://api.github.com/repos/mila-udem/myia/contributors","subscribers_url":"https://api.github.com/repos/mila-udem/myia/subscribers","subscription_url":"https://api.github.com/repos/mila-udem/myia/subscription","commits_url":"https://api.github.com/repos/mila-udem/myia/commits{/sha}","git_commits_url":"https://api.github.com/repos/mila-udem/myia/git/commits{/sha}","comments_url":"https://api.github.com/repos/mila-udem/myia/comments{/number}","issue_comment_url":"https://api.github.com/repos/mila-udem/myia/issues/comments{/number}","contents_url":"https://api.github.com/repos/mila-udem/myia/contents/{+path}","compare_url":"https://api.github.com/repos/mila-udem/myia/compare/{base}...{head}","merges_url":"https://api.github.com/repos/mila-udem/myia/merges","archive_url":"https://api.github.com/repos/mila-udem/myia/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/mila-udem/myia/downloads","issues_url":"https://api.github.com/repos/mila-udem/myia/issues{/number}","pulls_url":"https://api.github.com/repos/mila-udem/myia/pulls{/number}","milestones_url":"https://api.github.com/repos/mila-udem/myia/milestones{/number}","notifications_url":"https://api.github.com/repos/mila-udem/myia/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/mila-udem/myia/labels{/name}","releases_url":"https://api.github.com/repos/mila-udem/myia/releases{/id}","deployments_url":"https://api.github.com/repos/mila-udem/myia/deployments","created_at":"2017-09-27T04:56:56Z","updated_at":"2018-04-12T03:20:11Z","pushed_at":"2018-04-12T19:28:25Z","git_url":"git://github.com/mila-udem/myia.git","ssh_url":"git@github.com:mila-udem/myia.git","clone_url":"https://github.com/mila-udem/myia.git","svn_url":"https://github.com/mila-udem/myia","homepage":null,"size":675,"stargazers_count":126,"watchers_count":126,"language":"Python","has_issues":true,"has_projects":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":20,"mirror_url":null,"archived":false,"open_issues_count":17,"license":{"key":"mit","name":"MIT License","spdx_id":"MIT","url":"https://api.github.com/licenses/mit"},"forks":20,"open_issues":17,"watchers":126,"default_branch":"clean"}},"_links":{"self":{"href":"https://api.github.com/repos/mila-udem/myia/pulls/52"},"html":{"href":"https://github.com/mila-udem/myia/pull/52"},"issue":{"href":"https://api.github.com/repos/mila-udem/myia/issues/52"},"comments":{"href":"https://api.github.com/repos/mila-udem/myia/issues/52/comments"},"review_comments":{"href":"https://api.github.com/repos/mila-udem/myia/pulls/52/comments"},"review_comment":{"href":"https://api.github.com/repos/mila-udem/myia/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/mila-udem/myia/pulls/52/commits"},"statuses":{"href":"https://api.github.com/repos/mila-udem/myia/statuses/78e1da333c0c6dec5e1826881c486e1d5131f95e"}},"author_association":"COLLABORATOR"}}
{"actor":{"display_login":"breuleux"}}