While I agree with him in theory, I doubt this will work in practice.
I very much doubt that a compiler will be able to choose appropriate parallelization schemes at runtime without hints from the user, Big-O approximation will probably be insufficient in an annoying number of cases and very hard for the compiler to implement. IO will require monads or that DAG turns into a linked list. I also find it very telling that he doesn't show what that DAG looks like for loops or recursive functions.
Right, a loop is a morphism (or sub-lattice) from the state of loop variables at the beginning of a loop iteration to the state of loop variables in the next iteration. Iteration represents unrolling copies of the loop body sub-lattice in a linear string until termination. Recursion represents expanding sub-lattices inside sub-lattices until termination.