vm #8

abergeron · 2018-01-15T21:17:07Z

In the spirit of early PRs, here is my code for the VM.

What I'm trying to do here is to execute the graph directly to make easier to convert into a debugger. I'm still handling tail calls correctly so that we don't need an infinite amount of memory.

This is currently very inefficient for temporary storage of the computed values (as in all values are kept until the function returns, with the exception that tail calls are not considered returns). There can also be situations where we will recompute values more than once when they are used across internal functions. The results should always be good though.

bartvm · 2018-01-16T21:58:31Z

myia/vm.py

+                if isinstance(fn, Add):
+                    args = [self.get_value(i) for i in node.inputs[1:]]
+                    self.values[node] = sum(args[1:], args[0])
+                    raise


What's this raise for?

I belive that is a mistake that I left in.

bartvm · 2018-01-16T21:59:27Z

Awesome, looks good! Did you try it on the graphs that the parser spits out? If not, I'll try it and use it to write the first few integration tests.

breuleux

These are the comments I have so far, pending being able to meaningfully test it (parser doesn't handle function calls).

breuleux · 2018-01-16T21:51:35Z

myia/vm.py

+    Virtual Machine interface.
+
+    Attributes:
+        env: evaluation environement (currently unused)


*environment

breuleux · 2018-01-16T21:56:43Z

myia/vm.py

+
+    def tail(self):
+        """Are we in a tail call?."""
+        return self.todo[-2] is self.graph.return_


Can we guarantee len(self.todo) >= 2 whenever we call this?

More or less since the last node on the list should always be a Return and the code that handles it doesn't call this.

breuleux · 2018-01-16T21:59:04Z

myia/vm.py

+
+    def done(self):
+        """Are we done?."""
+        return self.graph.return_ in self.values


I don't know if this is going to be relevant, but because of the way closures are represented, it's possible that some nodes in a graph will get evaluated after return_.

Not with the current design, since we put the return node as the last one on the todo list.

If you have an example of a graph that could need to evaluate some other nodes after the return, please show me an example.

I'm thinking of something like this:

def f(x): a = x * x def g(): return a return g def h(): g = f(9) return g() + g()

There is no direct path from f.return_ to the node for a: it is the graph for g that has a pointer to a which belongs to f. Nonetheless, it needs to be evaluated in f's environment, at most once per g closure, and should reuse anything computed when evaluating f. However, both calls to g happen after f is done evaluating, so unless we walk g to find a and add it to the todo list immediately (i.e. closure conversion), a is going to be found after the frame for f exited.

Oh yeah, I see the problem. It will attempt to recompute a, but the parameters will no longer be available so it will fail or produce bad results.

breuleux · 2018-01-16T22:08:21Z

myia/vm.py

+        This will handle tail calls correctly by reusing the current VMFrame.
+        """
+        if self.tail():
+            self.reset(graph, args)


Because (of course) of these damned closures, I don't think you can actually do that: whenever you encounter a Constant that contains a Graph, and that this graph has the current graph as a parent, you need to attach the frame to it somehow (as an env), so that it can look up its closure variables. This will sometimes entail further computation in this frame, so you can't reuse it for a different graph.

I don't have any form of variable mapping in the frame, so I fail to see how that would help closures.

Also, if we can't reuse frames, then we can't do tail calls.

Closures here are graphs that have pointers to nodes that belong to other graphs. The semantics at execution is that if, when evaluating graph G, you encounter graph H such that H.parent is G, then you must construct a closure for H that lets it access the values for G's nodes. Each execution of G produces a fresh closure for H which is a first class value that can be passed around, and as long as that closure lives, so does G's frame or whatever structure holds these values.

A tail call just means that the current frame can be popped from the stack immediately. It can still be kept alive by a closure. If no closure points to it, then the GC will eliminate it.

I see what you mean, and I will reorganize the inner workings so that this can actually support closures correctly. As a bonus it should waste less memory when there are no closures.

breuleux · 2018-01-16T22:11:05Z

myia/vm.py

+            idx = self.graph.parameters.index(node)
+            self.values[node] = self.args[idx]
+        elif isinstance(node, Apply):
+            fn = self.get_value(node.inputs[0])


Since no primitive is lazy or short-circuiting with respect to its arguments, you can safely do

fn, *args = [self.get_value(x) for x in node.inputs]

Which will simplify the code below, and will make it easier to implement a generic system for primitives.

Right I did it this way to make sure that If didn't trigger any computing on the branch not taken, but since the branches are functions, then I could do as you say.

breuleux · 2018-01-16T22:15:00Z

myia/vm.py

+                if isinstance(fn, Add):
+                    args = [self.get_value(i) for i in node.inputs[1:]]
+                    self.values[node] = sum(args[1:], args[0])
+                    raise


raise what? Is that supposed to be there?

abergeron · 2018-01-16T22:18:03Z

I haven't run any tests yet. I'll do that tomorrow, while writing integration tests. If you find some problems before then, don't hesitate to tell me.

abergeron · 2018-01-18T04:39:47Z

I've made some major changes to the internals following @breuleux's comments.

Also I've started on some tests, but I'm currently blocked on some expressions that make the parse choke.

abergeron · 2018-01-18T08:28:27Z

I've rebased once again and added a bunch of tests.

While adding tests I've discovered problem when mixing closures and tail calls which are now fixed. This should be solid now, so I consider it ready for an in-detail review.

breuleux

I'm still a bit confused how this works, but as long as it works, I'm content.

breuleux · 2018-01-18T17:15:45Z

myia/vm.py

+
+        This will handle tail calls and closures.
+
+        """


You should check that there are exactly as many arguments as the graph takes parameters. This would have caught the bug in #4 (comment) immediately, and it is virtually certain that it will catch other similar bugs in the future.

breuleux · 2018-01-18T17:25:07Z

myia/vm.py

+        elif isinstance(node, Apply):
+            fn = self.get_value(node.inputs[0])
+            args = [self.get_value(i) for i in node.inputs[1:]]
+            if isinstance(fn, Primitive):


We need to figure out where to put primitive implementations. I'd suggest a dictionary mapping primitives to functions, so that we can easily experiment with different implementations. One slight complication is that the implementation for if, as it stands, requires the VM.

We can special case If and have a dict or something for the rest. I've implemented add inline for now, but I'll move it when we have more.

breuleux · 2018-01-18T22:16:17Z

This crashes with AttributeError: 'NoneType' object has no attribute 'values':

def f(x):
    def g():
        def h():
            return x
        return h
    return g()()

The graph looks correct to me, so maybe the deep nesting is throwing the VM off.

breuleux · 2018-01-18T22:28:41Z

myia/vm.py

+        """Wrap graphs that are closures."""
+        if isinstance(value, Graph):
+            if any(n.graph and n.graph is not value
+                   for n in dfs(value.return_)):


Pretty sure this is causing the issue with #8 (comment). In short, this will miss free variables: if this is graph G, another graph H is nested inside G, and H accesses a variable that's outside the scope of both G and H, then that variable is a free variable of both graphs. But you're not looking inside the graphs encountered in the dfs, so you will miss it.

I think that for this interpreter it's best not to try to be clever: create a closure all the time.

If we don't have a reliable way to detect closures, this is the safest choice, yes. However I fear it will keep all the stacks around for loops and cost a lot of memory.

It's not the stack per se it's supposed to save, just the environment, so a closure should never keep more "frames" alive than the lexical nesting depth. I think it'd be safe to set a frame's parent to None once it returns, so that the GC can reclaim it.

Or maybe it'd be better to split functionality into Environment (containing values and a parent environment) and Frame (containing a return_node, an environment and a todo), and have closures store the environment only. I think it'd be a bit clearer, and then you can safely reuse Frame objects in tail calls and whatnot.

It's not safe to set the parent to None, because some nodes can be left unevaluated and be referred to in a closure. We will need to evaluate those nodes at that point and we'll need the full environment to do that (unless we're sure that the current graph and all of its subgraphs are not closures that refer to things outside).

The more I think about it, the more I realize that we probably need to do a pass to mark which graphs are closures and up to where do we need to preserve the environment to capture everything they need.

So, I'll do something like that, either at runtime, or as a pre-pass.

Sorry, I was being loose with notation. You get the env from the frame when you create a closure, and from the closure when you call it. I mean something like this:

def call(fn, args): graph = fn.graph if isinstance(fn, Closure) else fn parent_env = fn.env if isinstance(fn, Closure) else None env = Environment(parent_env=parent_env, graph=graph) for param, arg in zip(graph.parameters, args): env[param] = arg frame = Frame(env=env, ret=graph.return_) exec_frame(frame) def wrap_closure(current_frame, graph): return Closure(current_frame.env, graph) def eval_node(current_frame, node): if node.graph is not current_frame.graph: env = current_frame.env while env.graph is not node.graph: env = env.parent_env frame = Frame(env=env, ret=node) exec_frame(frame) ...

Is that any clearer? It's a bit difficult to explain, but I think the idea of saving "frames" muddied the waters. It's a red herring, it's just environments that you need to save.

I see what you are getting at. I'll try to rework the code to follow that pattern.

Actually, I thought about it more, and I think this won't work, but for a different reason than I thought. Basically, consider:

def f(x): def g(z): return h(z + x) def h(z): return g(z * x) return g(3)

This doesn't terminate, but that's besides the point -- the calls are tail calls, so this should loop forever without growing memory.

However, when you call g and you encounter h, the code I gave will naively give it g as its environment, so it'll have environment chain [f, g]. This is wrong, of course, because h is not nested in g, but this isn't written anywhere in the representation. Nonetheless, when h is called, it will see g, and it will naturally assume that g is nested in h, so it will create the environment [f, g, h]. Then [f, g, h, g], and so on. The stack won't grow, but the chain of environments will, because both functions think they are nested in each other.

Maybe it'd kinda-work if the closures are cached, but honestly I think we should forget about evaluating this representation directly and preprocess with closure conversion. Then it'll be way more straightforward. I'm already working on that because of grad, it's a bit more complicated I thought it'd be, but I think it should be done by next meeting.

Yes, it would be much easier to work on a closure-converted version where everything is passed around explicitly. If it is required for grad to work properly, then we can also make it a requirement for the vm, but I would prefer if it wasn't.

We can talk about it before the next meeting, yes.

If possible, I agree it would be nice not to have to rely on closure conversion (debugging closure conversion and the parser would be easier that way).

bartvm · 2018-01-22T18:37:59Z

@abergeron Maybe you were aware of this already, but I wasn't: It looks like what this VM does is called a "spaghetti stack"

abergeron · 2018-01-22T19:28:03Z

I wasn't aware of that, but thanks for the reference.

- Now properly handles closures - Will never compute a value more than once - Does tail calls efficiently - Never save uneeded frames (that are not captured in a closure). - Other minor improvements

abergeron · 2018-01-22T19:47:55Z

I did one last rebase and changed the target branch. This should be mostly good to go.

bartvm · 2018-01-22T19:53:08Z

Awesome. For some reason the webhooks didn't trigger, but looks like Travis and Codecov are both happy.

bartvm reviewed Jan 16, 2018

View reviewed changes

breuleux reviewed Jan 16, 2018

View reviewed changes

abergeron force-pushed the vm branch 2 times, most recently from 70d0ab4 to 745f5b8 Compare January 18, 2018 08:26

bartvm force-pushed the parser branch 2 times, most recently from fa3db13 to 7d5f771 Compare January 18, 2018 16:37

breuleux reviewed Jan 18, 2018

View reviewed changes

abergeron force-pushed the vm branch 2 times, most recently from b498d02 to 34d06d7 Compare January 19, 2018 13:36

bartvm force-pushed the parser branch from a91fd59 to b47911e Compare January 20, 2018 19:08

abergeron force-pushed the vm branch 2 times, most recently from 584f231 to 6c550d4 Compare January 22, 2018 16:18

abergeron force-pushed the vm branch 2 times, most recently from 7d9d8e9 to 62e97da Compare January 22, 2018 19:27

abergeron force-pushed the vm branch from 62e97da to 12bbbbe Compare January 22, 2018 19:29

abergeron added 7 commits January 22, 2018 14:46

Code for the type-less VM.

542461a

Rework of the VM internals.

a36fdbd

- Now properly handles closures - Will never compute a value more than once - Does tail calls efficiently - Never save uneeded frames (that are not captured in a closure). - Other minor improvements

Add an API function to invoke the VM.

0bc516d

Some tests for the VM and the parser.

d02e834

Add failing test to help debugging.

f0508de

Fix some problems with closures and tail calls.

e22d198

Add more tests to cover all the code.

0157c30

abergeron and others added 5 commits January 22, 2018 14:46

Check the number of arguments.

d93f31c

Wrap closures based on their needs.

2255587

Added documentation.

f7b1a72

Add a self-recursive function to the tests and fix a bug it found.

d810b0c

Fix some brain damage in wrap_closure.

099d1b8

abergeron force-pushed the vm branch from 12bbbbe to 099d1b8 Compare January 22, 2018 19:46

abergeron changed the base branch from parser to clean January 22, 2018 19:47

bartvm merged commit a8251a1 into mila-iqia:clean Jan 22, 2018

abergeron deleted the vm branch March 8, 2018 17:16

vm #8

vm #8

Conversation

abergeron commented Jan 15, 2018

Choose a reason for hiding this comment

Choose a reason for hiding this comment

bartvm commented Jan 16, 2018

breuleux left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

breuleux Jan 16, 2018 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

breuleux Jan 16, 2018 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

abergeron commented Jan 16, 2018

abergeron commented Jan 18, 2018

abergeron commented Jan 18, 2018

breuleux left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

breuleux commented Jan 18, 2018 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

bartvm commented Jan 22, 2018

abergeron commented Jan 22, 2018

abergeron commented Jan 22, 2018

bartvm commented Jan 22, 2018

breuleux Jan 16, 2018 •

edited

breuleux Jan 16, 2018 •

edited

breuleux commented Jan 18, 2018 •

edited