Extensible Dependency Grammar (XDG) is new, modular grammar formalism for natural language. An XDG analysis is a multi-dimensional dependency graph, where each dimension represents a different aspect of natural language, e.g. syntactic function, predicate-argument structure, information structure etc. Thus, XDG brings together two recent trends in computational linguistics: the increased application of ideas from dependency grammar and the idea of multi-layered linguistic description. In this paper, we tackle one of the stumbling blocks of XDG so far - its incomplete formalization. We present the first complete formalization of XDG, as a description language for multigraphs based on simply typed lambda calculus.