12
$\begingroup$

I don't know whether it was a joke, but once I read what was referred to as a formal definition of a file in a versioning system such as git, hg or svn. It was something like a mathematical object like a homeomorphism. Was that a joke or is there really computer science theory about versioning systems and the mathematics of VCS?

$\endgroup$
  • 2
    $\begingroup$ I changed homemorphism to homeomorphism, however I have no clue, where to search for topology in this context. Did you mean homomorphism? $\endgroup$ – frafl Jun 13 '13 at 10:23
  • 3
    $\begingroup$ Something like en.wikibooks.org/wiki/Understanding_Darcs/Patch_theory or projects.haskell.org/camp ? It's always a good idea to search for haskell when it comes to theory and programming. I can turn this into an answer, but I think there are people with a better knowledge of this area. $\endgroup$ – frafl Jun 13 '13 at 10:25
  • 1
    $\begingroup$ Persistent data structure? $\endgroup$ – JeffE Jun 14 '13 at 4:13
  • $\begingroup$ You do not build something as complex and critical as a versioning system without a strong formalization of what you are doing. People who hack they way may sometimes be geniuses, but usually they are fools. $\endgroup$ – babou Aug 18 '15 at 14:00
11
+50
$\begingroup$

You're thinking of a tweet by Isaac Wolkerstorfer (‏@agnoster):

git gets easier once you get the basic idea that branches are homeomorphic endofunctors mapping submanifolds of a Hilbert space.

Unfortunately, it's a joke. As the author wrote on Quora:

It was intended as firmly tongue-in-cheek. I actually love git, and I think its complexity is greatly overblown. At the same time, I'm sympathetic to the fact that advice from git gurus to novices can end up sounding like inscrutable gibberish.

It's not intended to have any deeper meaning. Attempts to analyze it in this fashion should be futile, but due to a bug in reality, you can actually make any sufficiently hand-wavy statement fit if you try hard enough.

This has been discussed on Programmers Stack Exchange and on Mathematics Stack Exchange.


Joke aside, there has been work of formalizing version control. One effort that allies theory and practice is the work on patch theory by David Roundy on Darcs. The main objective of the theory is to model merging and, in particular, conflict resolution. The Darcs wiki has an introduction to the theory and a few pointers as well as a bibliography (unmaintained so outdated if you want a recent view on the subject, but it does list a 2009 survey paper by Petr Baudiš) and a list of talks (which includes more recent material). There's also a wikibook. One seminal paper is A Principled Approach to Version Control by Andres Löh, Wouter Swierstra and Daan Leijen3.

Patch theory does lead to a categorical model, which has been more recently explored in A Categorical Theory of Patches by Samuel Mimram and Cinzia Di Giusto and Homotopical Patch Theory by Carlo Angiuli, Ed Morehouse, Daniel R. Licata and Robert Harper. In Mimram and Di Giusto's work, the model has files as objects and patches as morphisms. I think that makes merging a branch a functor — an endofunctor if you're working in a single repository. “Homeomorphic endofunctor” doesn't make sense to me. With homotopy theory involved, submanifolds of a Hilbert space might not be so far out...

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

Of course there is a mathematical formalism for version control systems. There is a mathematical formalism for virtually every algorithm in CS. There are multiple formalisms for many. There is not a 1-1 relationship between formalisms and the systems they model. The models can range from simple to complex. Here is an example for VCS/SCM also by Swierstra, not cited yet.

SCM also has a lot of similarities to the concept of "parallel universes/ timelines" and time travel sometimes used in science fiction. It captures the state of the evolving system at different times or "snapshots". There are "branches" and "merges". See also timelines.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.