14 ms·

Git is a purely functional data structure (2013)

227 points by eisokant 9y ago

mannykannot 9y ago
I think the author has a point in saying that learning Git by trying to map it to Subversion is not the best way to do it, but I don't think analyzing it as a functional data structure adds much insight. To me, it is easier to understand when you look at its purpose, and how it solves the problems of that domain - and the biggest difficulties of version control are on account of the problem being essentially one of distributed, lockless concurrency, something not mentioned in this article.
icc97 9y ago
I found the explanation from the Immutable JS presentation easier to understand when talking about Immutable data structures [0] [0]: https://youtu.be/I7IdS-PbEgI?t=5m7s https://youtu.be/I7IdS-PbEgI?t=5m7s
fpoling 9y ago
Git is not a purely functional data structure [1] [1] man git-rebase
- 19870213 9y ago
  But git-rebase does not alter existing commits in the commit tree, it simply creates a new branch (meaning new commits) on the tree.
  - Simon_says 9y ago
    Alright wiseguy, git gc.
    - davidcuddeback 9y ago
      I don't understand what point you're trying to make. Unreachable data can be garbage-collected in Haskell, ML, Clojure, Erlang, and many other functional (and non-functional) programming languages. What about GC is supposed to refute that a data structure is functional?
      - Simon_says 9y ago
        19870213's point was that a git rebase is functional because it doesn't change existing commits, rather it only makes new ones and moves branch pointers. This is correct. You can also say that git gc is functional because it's only garbage collecting. But you can't have it both ways. The cumulative effect of rebase followed by gc is to delete commits that have a branch pointing to them.
        dustingetz 9y ago
        hey you're getting downvoted bc you misunderstand so insistently and cockily, maybe try asking a question
        davidcuddeback 9y ago
        > The cumulative effect of rebase followed by gc is to delete commits that have a branch pointing to them. That would be a strictly broken GC if it removes commits that are reachable from branch pointers. Please file a bug report with the git project if you've observed this happening, because it would be inconsistent with the git-gc(1) manpage, which says it only removes unreachable objects.
        rootlocus 9y ago
        > The cumulative effect of rebase followed by gc is to delete commits that have a branch pointing to them. This is both false and irrelevant. It's false because after the rebase, the branch you just rebased won't point to the old commits. Unless you had other branches there, they would be orphaned. Also, according to the "Notes" section of the git-gc documentation [0]: > git gc tries very hard not to delete objects that are referenced anywhere in your repository. In particular, it will keep not only objects referenced by your current set of branches and tags, but also objects referenced by the index, remote-tracking branches, refs saved by git filter-branch in refs/original/, or reflogs (which may reference commits in branches that were later amended or rewound). Since the commit you were on before making the rebase is in the reflog, it will actually not be GCed (yet) even though there are no branches pointing to them. It's irrelevant because, even if it was true, as long as there are no more objects referencing that commit, it's perfectly eligible for gc. I don't understand your argument that "you can't have it both ways". [0] https://git-scm.com/docs/git-gc https://git-scm.com/docs/git-gc
    - dustingetz 9y ago
      gc is actually essential to implementing pure functional programming efficiently on top of imperative hardware (see: structure sharing, an essential optimization that lets functional data structures reuse bits of each other internally for low-cost copy-and-modify, at the cost of making a data structure no longer responsible for freeing its own memory since it overlaps)
- fiatjaf 9y ago
  I don't see that anywhere. A rebase is just a fork.
- klodolph 9y ago
  If Git were purely functional, you would expect rebase not to modify the existing data in any way, and indeed that is exactly what happens. You can create, delete, or modify only the top-level pointers: branch names, reflog, etc. Instead, rebase creates a completely new set of commits, and points the current branch at a new one. This is exactly how functional data structures work in e.g. Haskell, where "inserting" an element into a dictionary means that you get a new copy of the dictionary, and all existing references to the original are unmodified.
  - fpoling 9y ago
    Git rebase alters the structures that are relevant for me, like heads of named branches. In Haskell let bindings are immutable. To reference to the results one has to put them into new bindings. I.e. if Git was purely functional, the rebase would create new names for branches.
    - tathougies 9y ago
      You can easily shadow a name in a let binding in Haskell For example, let x = 5 in let x = 6 in putStrLn (show x) would print 6. Unless you turn on compiler warnings, there is never a need to choose new names for variables if the old version is no longer needed.
      - catnaroek 9y ago
        Shadowing isn't the same thing as redefining. Try evaluating the following expression: let x = 4 ; f y = x + y in let x = 6 in f 10
    - masklinn 9y ago
      > In Haskell let bindings are immutable. Haskell has mutable refs. That's what Git branches are.
      - catnaroek 9y ago
        But the contents of a mutable ref aren't let-bound.
rubenbe 9y ago
I often recommend people to read "Git Internals". If you know how git works internally, it's much easier to understand how it works and the reasons behind it. https://git-scm.com/book/en/v1/Git-Internals https://git-scm.com/book/en/v1/Git-Internals
- nine_k 9y ago
  Even more enlightening is The git Parable. http://tom.preston-werner.com/2009/05/19/the-git-parable.html http://tom.preston-werner.com/2009/05/19/the-git-parable.htm...
- randomsearch 9y ago
  This suggests a poor abstraction.
  - goialoq 9y ago
    "Internals" is a poor choice of term. "Data structure" is a better term. Git is "plumbing and porcelain". The plumbing is the core of git. Porcelain are shortcuts. In general, Torvalds projects (Linux, Git) aren't big on abstractions that maximize simplicity-of-use, they focus on doing complex things correctly and quickly. Adding abstraction makes it hard to get details correct and run quickly.
    - randomsearch 9y ago
      Agreed. Git seems like a good internal design with a terrible interface.
Edmond 9y ago
Perhaps for those familiar with "functional data structures" such an analogy is helpful but I find it easier to simply explain git for what it is without adding more exotic nomenclature to it. Git lets you do version control via full snapshots as opposed to just tracking diffs (even though it does actually do this too behind the scene). You can think of a full snapshot as saving a copy of your project structure every time you do a commit. The key trick is that git doesn't actually create new copies of the content for each commit but simply maintains a tree structure whose nodes are pointers (via hashing) to the content they represent. The complication from git is not in understanding the core concept but knowing how best to apply them. There are all sorts of crazy workflows you could implement by manipulating git pointers and their associated patches. As with anything that is flexible, difficulty comes in knowing how to constraint yourself when using it.
- nine_k 9y ago
  Exactly. Those familiar with functional data structures would thus point you at git and say: heres a structure from the Okasaki book that you use every day. One more step is to point that futures / promises, and even lists, are monads that a e.g. JS programmer uses every day, too. It reminds me of the old literary character who did not know that he's been speaking prose all his life.
- rst 9y ago
  Particularly since a git repo, as a whole, isn't a functional data structure. The commits (and the graph in which they're embedded) are immutable, but the mapping between branch names and commits gets mutated all the time. (To say nothing of slightly deeper esoterica like the index and stashes.)
  - masklinn 9y ago
    That's pretty functional still, the "branches" are just (in clojure terms) atoms, aka atomically mutable references to a structure (namely a commit which is some metadata + a reference to a tree).
- kazinator 9y ago
erikb 9y ago
A data structure cannot be functional. I understand what he's trying to say, and agree with most of it, but the word "functional" is purely wrong. What he wants to say is "good". But not all "functional programming" is good, nor is all good programming functional by necessity, despite what your local Lambda The Ultimate nerd tries to tell you. The Best, when it comes to data structures is a Directed, Acyclic Graph. For instance your typical linux filesystem is a DAG. But there's one problem with DAGs: When they reach a certain complexity human brains are not fit enough to parse them anymore. (programs still can though) So in many circumstances at least a human programmer needs to take a look at the state of your program and make assumptions about its correctness, which is called debugging. And that's why in Good programs we often use Good data structures instead of The Best. Good data structures are key->value stores (which you may know as "hash tables" or "dictionaries"), trees, and trees in a simplified special form: lists, each of them being somewhat able to represent the other two, if one can accept a performance hit and/or increased complexity in source code. Dictionaries, trees, lists. That's it. And you do that in every programming language that is at least a little bit interested in being Good. So there's nothing special or functional about git's data structures, it's just normal Good programming, and a few programmers who are so good at programming that they don't even need to mention it anymore, they breath good programms. Then of course to the normal bread-earning coder good programs are a rare sight. But the reason is not that they are really rare, the reason is that successful business doesn't really require Good programs to succeed. Mediocre programs are good enough to earn their rent, and most of us spend most of our coding hours to earn our rent. All that being said, if you don't just want to make money, go and spend some time studying git internals. It will teach you a lot more than most of your teachers/professors taught you combined. Sadly the source code is written by Linux gurus, who like to encrypt their source code with a very special key that only people from their tribe can understand. But the Git Book is actually good enough that you can study quite a lot of the internals from that book. I also suggest writing your own git in your favorite programming language once, to really understand it.
- davidcuddeback 9y ago
  > A data structure cannot be functional. I think the author is using the term "purely functional data structure" to mean a data structure that lends itself to an implementation in a purely functional language [1,2]. [1] https://en.wikipedia.org/wiki/Purely_functional_data_structure https://en.wikipedia.org/wiki/Purely_functional_data_structu... [2] https://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504 https://www.amazon.com/Purely-Functional-Structures-Chris-Ok...
snissn 9y ago
Is git a blockchain?
- linschn 9y ago
  Short answer, yes. The current commit includes the hash of its parent(s), so its own hash reflects the whole history, and one can not change the history without also changing the current hash. Just like a block contains the hash of the previous block.
  - sparkie 9y ago
    That's a Merkle Tree. A blockchain is an application of a Merkle tree in which each node contains transaction data, and a majority of clients agree that the longest chain of blocks is the correct one. Git also uses a Merkle-DAG, but it is not a blockchain.
    - mbrock 9y ago
      a majority of clients agree that the longest chain of blocks is the correct one If you squint, that's kind of true for Git repositories, too. The version with the most "proof of work" on it is likely the master branch. Of course the incentives are very different... but still, the similarity is somewhat illuminating, I think.
    - misnome 9y ago
      But this ‘definition’ seems to needlessly tie the definition to the kind of data you are transmitting. And if that were the case, couldn’t a software diff be considered a kind of transaction?
- icebraining 9y ago
  They both use Merkle/Hash trees: Hash trees are used in the IPFS, Btrfs and ZFS file systems, BitTorrent protocol, Dat protocol, Apache Wave protocol, Git and Mercurial distributed revision control systems, the Tahoe-LAFS backup system, the Bitcoin and Ethereum peer-to-peer networks, the Certificate Transparency framework, and a number of NoSQL systems like Apache Cassandra, Riak and Dynamo. https://en.wikipedia.org/wiki/Merkle_tree https://en.wikipedia.org/wiki/Merkle_tree
BenoitEssiambre 9y ago
I sometimes like to explain things the other way around. Immutability being version control for program state. I rarely use functional programming but I certainly see its appeal for certain things. I think the concept of immutability confuses people. It really clicked for me when I stopped thinking of it in terms of things not being able to change and started instead to think of it in terms of each version of things having different names, somewhat like commits in version control. Functional programming makes explicit, not only which variables you are accessing, but which version of it. It may seem like you are copying variables every time you want to modify them but really you are just giving different mutations, different names. This doesn't mean things are actually copied in memory. The compiler doesn't need to keep every versions. If it sees that you are not going to reference a particular mutation, it might just physically overwrite it with the next mutation. In the background "var a=i, var b=a+j", might compile as something like "var b = i; b+=j";
- macintux 9y ago
  That's an interesting way to describe it. I've talked a lot about immutability at conferences, but I've never thought about it in those terms. Thanks.
  - masklinn 9y ago
    That realisation has been used by environments like Elm's Reactor[0] or its (sadly defunct) Time Traveling debugger. I think Om also had something like that. Basically, if you use persistent data structures and a unified application state, you can keep a list of all previous application states and you can browse it or ship it for debugging, it's not that expensive. [0] in debug mode, you get a list of all events having occurred in your application and can instantly move back to that state, and you can import/export that state history: http://elm-lang.org/blog/the-perfect-bug-report http://elm-lang.org/blog/the-perfect-bug-report
    - arximboldi 9y ago
      I am working on something like that for C++, a library + debugger called Lager. Quite experimental yet, but been using it to write apps with SDL and Ncurses and I am happy with how it is going... In the end it is a very simple architecture, implementable in any language. Good immutable data-structures are important for big programs though. Library: https://github.com/arximboldi/lager https://github.com/arximboldi/lager Ncurses example (full text-editor): https://github.com/arximboldi/ewig https://github.com/arximboldi/ewig SDL example: https://twitter.com/sinusoidalen/status/939539173584916480 https://twitter.com/sinusoidalen/status/939539173584916480 Immutable data: https://github.com/arximboldi/immer https://github.com/arximboldi/immer (There was a talk about Lager at MeetingCpp this year, still waiting for it to be published online...)
dustingetz 9y ago
for a real database that works like git, see http://www.datomic.com http://www.datomic.com if git killed svn, datomic kills postgres
- macintux 9y ago
  As much as I appreciate datomic, that's a poor conclusion to draw. git is objectively better than svn. Postgres is not objectively worse than datomic; there are things that datomic simply can't do efficiently.
  - dustingetz 9y ago
    if you go back and read the git vs svn flame wars back when it first came out, people said the same thing. it happens every time there is a paradigm shift technology. the reactjs flame wars of 2013/4 were particularly brutal as everyone and their mom felt qualified to comment. the key idea here is that, at scale, immutability is just better, at nearly everything
- xj9 9y ago
  if it were open source maybe, but i'm definitely not going to switch (even though i might want to) for licensing reasons. in fact, i have more motivation to write an libre datomic clone than to pay cognitect anything for their proprietary db.
  - dustingetz 9y ago
    do it!
    - greghendershott 9y ago
      Depending on the definition of "it", someone has: https://github.com/tonsky/datascript https://github.com/tonsky/datascript
      - dustingetz 9y ago
kazinator 9y ago
Git is a purely functional data structure, except for the mutating head pointers, rewriting of tags, various state in the repo related to things like on-going rebases, cherry picks, bisects, ... oh and the index which is one object changing in-place (not to mention working tree, of course).
- vickychijwani 9y ago
  While what you say is technically accurate, I think you're missing the bigger picture here. The author's point still stands: git's commit history (arguably the most important part of a version-control system) can be viewed as a purely-functional data structure, and that view has practical benefits too. I tried to explain more here: https://news.ycombinator.com/item?id=15892013 https://news.ycombinator.com/item?id=15892013
  - deleted 9y ago
    [deleted]
ioquatix 9y ago
.... and one day I had the crazy idea to make a database on top of it: https://github.com/ioquatix/relaxo https://github.com/ioquatix/relaxo because the underlying immutable data structure makes this quite feasible.
shurcooL 9y ago
Even after 4 years, this remains my favorite, most influential article that helped me understand and feel comfortable with git. It's just a very good analogy.
doug1001 9y ago
well the top-level git data structure is pretty close to eg, Scala's Vector, which is an immutable container implemented as a tree with a high branching factor of 32. Modification to such a vector, rebound to a new variable, relies on structural sharing of the original (http://www.codecommit.com/blog/scala/implementing-persistent-vectors-in-scala http://www.codecommit.com/blog/scala/implementing-persistent...)
ianamartin 9y ago
I find this conversation fascinating because there is so much disagreement on the meaning of "functional" and "immutable" What I've gathered so far from reading the article and the comments is that some people who are in the know about a very specific paper agree that Git is a purely functional data structure. And that others look at the ways you can use Git and point a finger and say, "Look! It can be mutated! Therefore it cannot be functional!" And the response to that is, "Don't be so technical about how you define functional. Or immutable. You know it when you see it." Is this some kind of Obi-wan Kenobi from a certain point of view stuff? Why is this so difficult to get a handle on? If a thing says immutable on the tin, and it's mutable, how is that purely functional? I know, read the paper. I know. But still, it's a legit question. It seems to me that a data structure so amazing as being purely functional shouldn't be so easy to misunderstand as what we're seeing here. And it's clearly being misunderstood. And not only by me.
- vickychijwani 9y ago
  > "Look! It can be mutated! Therefore it cannot be functional!" And the response to that is, "Don't be so technical about how you define functional. Or immutable. You know it when you see it." I think I can offer something to the discussion here, as I'm straddling the 2 camps - having a fairly intricate understanding of git (I've held training seminars at my company about it), and basic familiarity with functional (technically "persistent") data structures thanks to a long-standing interest in Clojure. What the functional camp is talking about, when they refer to git as a "purely functional data structure", is the core of git's implementation - commits are immutable snapshots of the repository arranged in a directed acyclic graph (or a tree, if there are no merge commits), and branches are "just" movable pointers to some commit. In this view, everything other than this core model of history as a graph is extra details layered on top. The other camp (let's call them the "git camp") looks at git in its entirety, including branches, tags, the index, the working tree, stashes, and so on, and they can't help but come to the conclusion you mentioned - "Branches are mutable references! The index is mutable! The working tree is mutable! How can git possibly be called a functional data structure?" While this 2nd perspective is understandable and technically correct, I think it misses the point the other camp is trying to make: that the immutable commit is the "fundamental unit of git" so to speak, that we interact with everyday, and that most of git's history-manipulating commands (git commit, git commit --amend, git rebase, git merge, git cherry-pick) can be described in terms of purely-functional operations on the commit graph. Once you understand this, many complex git scenarios become easier to understand (rebase, and filter-branch, for example), so this view does have practical value. Then branches, tags, the index, stashes, etc can indeed be understood separately. In fact, this perspective of git as a data structure is so useful, that I rarely use "git log" as it is, preferring these additional flags to view the entire graph instead: git log --graph --all --decorate --oneline I hope that helps, cheers!

227 points by eisokant 9y ago

I think the author has a point in saying that learning Git by trying to map it to Subversion is not the best way to do it, but I don't think analyzing it as a functional data structure adds much insight. To me, it is easier to understand when you look at its purpose, and how it solves the problems of that domain - and the biggest difficulties of version control are on account of the problem being essentially one of distributed, lockless concurrency, something not mentioned in this article.

icc97 9y ago

I found the explanation from the Immutable JS presentation easier to understand when talking about Immutable data structures [0] [0]: https://youtu.be/I7IdS-PbEgI?t=5m7s https://youtu.be/I7IdS-PbEgI?t=5m7s

fpoling 9y ago

Git is not a purely functional data structure [1] [1] man git-rebase

19870213 9y ago
But git-rebase does not alter existing commits in the commit tree, it simply creates a new branch (meaning new commits) on the tree.
- Simon_says 9y ago
  Alright wiseguy, git gc.
  - davidcuddeback 9y ago
    I don't understand what point you're trying to make. Unreachable data can be garbage-collected in Haskell, ML, Clojure, Erlang, and many other functional (and non-functional) programming languages. What about GC is supposed to refute that a data structure is functional?
    - Simon_says 9y ago
      19870213's point was that a git rebase is functional because it doesn't change existing commits, rather it only makes new ones and moves branch pointers. This is correct. You can also say that git gc is functional because it's only garbage collecting. But you can't have it both ways. The cumulative effect of rebase followed by gc is to delete commits that have a branch pointing to them.
      - dustingetz 9y ago
        hey you're getting downvoted bc you misunderstand so insistently and cockily, maybe try asking a question
      - davidcuddeback 9y ago
        > The cumulative effect of rebase followed by gc is to delete commits that have a branch pointing to them. That would be a strictly broken GC if it removes commits that are reachable from branch pointers. Please file a bug report with the git project if you've observed this happening, because it would be inconsistent with the git-gc(1) manpage, which says it only removes unreachable objects.
      - rootlocus 9y ago
        > The cumulative effect of rebase followed by gc is to delete commits that have a branch pointing to them. This is both false and irrelevant. It's false because after the rebase, the branch you just rebased won't point to the old commits. Unless you had other branches there, they would be orphaned. Also, according to the "Notes" section of the git-gc documentation [0]: > git gc tries very hard not to delete objects that are referenced anywhere in your repository. In particular, it will keep not only objects referenced by your current set of branches and tags, but also objects referenced by the index, remote-tracking branches, refs saved by git filter-branch in refs/original/, or reflogs (which may reference commits in branches that were later amended or rewound). Since the commit you were on before making the rebase is in the reflog, it will actually not be GCed (yet) even though there are no branches pointing to them. It's irrelevant because, even if it was true, as long as there are no more objects referencing that commit, it's perfectly eligible for gc. I don't understand your argument that "you can't have it both ways". [0] https://git-scm.com/docs/git-gc https://git-scm.com/docs/git-gc
  - dustingetz 9y ago
    gc is actually essential to implementing pure functional programming efficiently on top of imperative hardware (see: structure sharing, an essential optimization that lets functional data structures reuse bits of each other internally for low-cost copy-and-modify, at the cost of making a data structure no longer responsible for freeing its own memory since it overlaps)
fiatjaf 9y ago
I don't see that anywhere. A rebase is just a fork.
klodolph 9y ago
If Git were purely functional, you would expect rebase not to modify the existing data in any way, and indeed that is exactly what happens. You can create, delete, or modify only the top-level pointers: branch names, reflog, etc. Instead, rebase creates a completely new set of commits, and points the current branch at a new one. This is exactly how functional data structures work in e.g. Haskell, where "inserting" an element into a dictionary means that you get a new copy of the dictionary, and all existing references to the original are unmodified.
- fpoling 9y ago
  Git rebase alters the structures that are relevant for me, like heads of named branches. In Haskell let bindings are immutable. To reference to the results one has to put them into new bindings. I.e. if Git was purely functional, the rebase would create new names for branches.
  - tathougies 9y ago
    You can easily shadow a name in a let binding in Haskell For example, let x = 5 in let x = 6 in putStrLn (show x) would print 6. Unless you turn on compiler warnings, there is never a need to choose new names for variables if the old version is no longer needed.
    - catnaroek 9y ago
      Shadowing isn't the same thing as redefining. Try evaluating the following expression: let x = 4 ; f y = x + y in let x = 6 in f 10
  - masklinn 9y ago
    > In Haskell let bindings are immutable. Haskell has mutable refs. That's what Git branches are.
    - catnaroek 9y ago
      But the contents of a mutable ref aren't let-bound.

rubenbe 9y ago

I often recommend people to read "Git Internals". If you know how git works internally, it's much easier to understand how it works and the reasons behind it. https://git-scm.com/book/en/v1/Git-Internals https://git-scm.com/book/en/v1/Git-Internals

nine_k 9y ago
Even more enlightening is The git Parable. http://tom.preston-werner.com/2009/05/19/the-git-parable.html http://tom.preston-werner.com/2009/05/19/the-git-parable.htm...
randomsearch 9y ago
This suggests a poor abstraction.
- goialoq 9y ago
  "Internals" is a poor choice of term. "Data structure" is a better term. Git is "plumbing and porcelain". The plumbing is the core of git. Porcelain are shortcuts. In general, Torvalds projects (Linux, Git) aren't big on abstractions that maximize simplicity-of-use, they focus on doing complex things correctly and quickly. Adding abstraction makes it hard to get details correct and run quickly.
  - randomsearch 9y ago
    Agreed. Git seems like a good internal design with a terrible interface.

Edmond 9y ago

Perhaps for those familiar with "functional data structures" such an analogy is helpful but I find it easier to simply explain git for what it is without adding more exotic nomenclature to it. Git lets you do version control via full snapshots as opposed to just tracking diffs (even though it does actually do this too behind the scene). You can think of a full snapshot as saving a copy of your project structure every time you do a commit. The key trick is that git doesn't actually create new copies of the content for each commit but simply maintains a tree structure whose nodes are pointers (via hashing) to the content they represent. The complication from git is not in understanding the core concept but knowing how best to apply them. There are all sorts of crazy workflows you could implement by manipulating git pointers and their associated patches. As with anything that is flexible, difficulty comes in knowing how to constraint yourself when using it.

nine_k 9y ago
Exactly. Those familiar with functional data structures would thus point you at git and say: heres a structure from the Okasaki book that you use every day. One more step is to point that futures / promises, and even lists, are monads that a e.g. JS programmer uses every day, too. It reminds me of the old literary character who did not know that he's been speaking prose all his life.
rst 9y ago
Particularly since a git repo, as a whole, isn't a functional data structure. The commits (and the graph in which they're embedded) are immutable, but the mapping between branch names and commits gets mutated all the time. (To say nothing of slightly deeper esoterica like the index and stashes.)
- masklinn 9y ago
  That's pretty functional still, the "branches" are just (in clojure terms) atoms, aka atomically mutable references to a structure (namely a commit which is some metadata + a reference to a tree).
kazinator 9y ago

erikb 9y ago

A data structure cannot be functional. I understand what he's trying to say, and agree with most of it, but the word "functional" is purely wrong. What he wants to say is "good". But not all "functional programming" is good, nor is all good programming functional by necessity, despite what your local Lambda The Ultimate nerd tries to tell you. The Best, when it comes to data structures is a Directed, Acyclic Graph. For instance your typical linux filesystem is a DAG. But there's one problem with DAGs: When they reach a certain complexity human brains are not fit enough to parse them anymore. (programs still can though) So in many circumstances at least a human programmer needs to take a look at the state of your program and make assumptions about its correctness, which is called debugging. And that's why in Good programs we often use Good data structures instead of The Best. Good data structures are key->value stores (which you may know as "hash tables" or "dictionaries"), trees, and trees in a simplified special form: lists, each of them being somewhat able to represent the other two, if one can accept a performance hit and/or increased complexity in source code. Dictionaries, trees, lists. That's it. And you do that in every programming language that is at least a little bit interested in being Good. So there's nothing special or functional about git's data structures, it's just normal Good programming, and a few programmers who are so good at programming that they don't even need to mention it anymore, they breath good programms. Then of course to the normal bread-earning coder good programs are a rare sight. But the reason is not that they are really rare, the reason is that successful business doesn't really require Good programs to succeed. Mediocre programs are good enough to earn their rent, and most of us spend most of our coding hours to earn our rent. All that being said, if you don't just want to make money, go and spend some time studying git internals. It will teach you a lot more than most of your teachers/professors taught you combined. Sadly the source code is written by Linux gurus, who like to encrypt their source code with a very special key that only people from their tribe can understand. But the Git Book is actually good enough that you can study quite a lot of the internals from that book. I also suggest writing your own git in your favorite programming language once, to really understand it.

davidcuddeback 9y ago
> A data structure cannot be functional. I think the author is using the term "purely functional data structure" to mean a data structure that lends itself to an implementation in a purely functional language [1,2]. [1] https://en.wikipedia.org/wiki/Purely_functional_data_structure https://en.wikipedia.org/wiki/Purely_functional_data_structu... [2] https://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504 https://www.amazon.com/Purely-Functional-Structures-Chris-Ok...

snissn 9y ago

Is git a blockchain?

linschn 9y ago
Short answer, yes. The current commit includes the hash of its parent(s), so its own hash reflects the whole history, and one can not change the history without also changing the current hash. Just like a block contains the hash of the previous block.
- sparkie 9y ago
  That's a Merkle Tree. A blockchain is an application of a Merkle tree in which each node contains transaction data, and a majority of clients agree that the longest chain of blocks is the correct one. Git also uses a Merkle-DAG, but it is not a blockchain.
  - mbrock 9y ago
    a majority of clients agree that the longest chain of blocks is the correct one If you squint, that's kind of true for Git repositories, too. The version with the most "proof of work" on it is likely the master branch. Of course the incentives are very different... but still, the similarity is somewhat illuminating, I think.
  - misnome 9y ago
    But this ‘definition’ seems to needlessly tie the definition to the kind of data you are transmitting. And if that were the case, couldn’t a software diff be considered a kind of transaction?
icebraining 9y ago
They both use Merkle/Hash trees: Hash trees are used in the IPFS, Btrfs and ZFS file systems, BitTorrent protocol, Dat protocol, Apache Wave protocol, Git and Mercurial distributed revision control systems, the Tahoe-LAFS backup system, the Bitcoin and Ethereum peer-to-peer networks, the Certificate Transparency framework, and a number of NoSQL systems like Apache Cassandra, Riak and Dynamo. https://en.wikipedia.org/wiki/Merkle_tree https://en.wikipedia.org/wiki/Merkle_tree

BenoitEssiambre 9y ago

I sometimes like to explain things the other way around. Immutability being version control for program state. I rarely use functional programming but I certainly see its appeal for certain things. I think the concept of immutability confuses people. It really clicked for me when I stopped thinking of it in terms of things not being able to change and started instead to think of it in terms of each version of things having different names, somewhat like commits in version control. Functional programming makes explicit, not only which variables you are accessing, but which version of it. It may seem like you are copying variables every time you want to modify them but really you are just giving different mutations, different names. This doesn't mean things are actually copied in memory. The compiler doesn't need to keep every versions. If it sees that you are not going to reference a particular mutation, it might just physically overwrite it with the next mutation. In the background "var a=i, var b=a+j", might compile as something like "var b = i; b+=j";

macintux 9y ago
That's an interesting way to describe it. I've talked a lot about immutability at conferences, but I've never thought about it in those terms. Thanks.
- masklinn 9y ago
  That realisation has been used by environments like Elm's Reactor[0] or its (sadly defunct) Time Traveling debugger. I think Om also had something like that. Basically, if you use persistent data structures and a unified application state, you can keep a list of all previous application states and you can browse it or ship it for debugging, it's not that expensive. [0] in debug mode, you get a list of all events having occurred in your application and can instantly move back to that state, and you can import/export that state history: http://elm-lang.org/blog/the-perfect-bug-report http://elm-lang.org/blog/the-perfect-bug-report
  - arximboldi 9y ago
    I am working on something like that for C++, a library + debugger called Lager. Quite experimental yet, but been using it to write apps with SDL and Ncurses and I am happy with how it is going... In the end it is a very simple architecture, implementable in any language. Good immutable data-structures are important for big programs though. Library: https://github.com/arximboldi/lager https://github.com/arximboldi/lager Ncurses example (full text-editor): https://github.com/arximboldi/ewig https://github.com/arximboldi/ewig SDL example: https://twitter.com/sinusoidalen/status/939539173584916480 https://twitter.com/sinusoidalen/status/939539173584916480 Immutable data: https://github.com/arximboldi/immer https://github.com/arximboldi/immer (There was a talk about Lager at MeetingCpp this year, still waiting for it to be published online...)

dustingetz 9y ago

for a real database that works like git, see http://www.datomic.com http://www.datomic.com if git killed svn, datomic kills postgres

macintux 9y ago
As much as I appreciate datomic, that's a poor conclusion to draw. git is objectively better than svn. Postgres is not objectively worse than datomic; there are things that datomic simply can't do efficiently.
- dustingetz 9y ago
  if you go back and read the git vs svn flame wars back when it first came out, people said the same thing. it happens every time there is a paradigm shift technology. the reactjs flame wars of 2013/4 were particularly brutal as everyone and their mom felt qualified to comment. the key idea here is that, at scale, immutability is just better, at nearly everything
xj9 9y ago
if it were open source maybe, but i'm definitely not going to switch (even though i might want to) for licensing reasons. in fact, i have more motivation to write an libre datomic clone than to pay cognitect anything for their proprietary db.
- dustingetz 9y ago
  do it!
  - greghendershott 9y ago
    Depending on the definition of "it", someone has: https://github.com/tonsky/datascript https://github.com/tonsky/datascript
    - dustingetz 9y ago

kazinator 9y ago

Git is a purely functional data structure, except for the mutating head pointers, rewriting of tags, various state in the repo related to things like on-going rebases, cherry picks, bisects, ... oh and the index which is one object changing in-place (not to mention working tree, of course).

vickychijwani 9y ago
While what you say is technically accurate, I think you're missing the bigger picture here. The author's point still stands: git's commit history (arguably the most important part of a version-control system) can be viewed as a purely-functional data structure, and that view has practical benefits too. I tried to explain more here: https://news.ycombinator.com/item?id=15892013 https://news.ycombinator.com/item?id=15892013
- deleted 9y ago
  [deleted]

ioquatix 9y ago

.... and one day I had the crazy idea to make a database on top of it: https://github.com/ioquatix/relaxo https://github.com/ioquatix/relaxo because the underlying immutable data structure makes this quite feasible.

shurcooL 9y ago

Even after 4 years, this remains my favorite, most influential article that helped me understand and feel comfortable with git. It's just a very good analogy.

doug1001 9y ago

well the top-level git data structure is pretty close to eg, Scala's Vector, which is an immutable container implemented as a tree with a high branching factor of 32. Modification to such a vector, rebound to a new variable, relies on structural sharing of the original (http://www.codecommit.com/blog/scala/implementing-persistent-vectors-in-scala http://www.codecommit.com/blog/scala/implementing-persistent...)

ianamartin 9y ago

I find this conversation fascinating because there is so much disagreement on the meaning of "functional" and "immutable" What I've gathered so far from reading the article and the comments is that some people who are in the know about a very specific paper agree that Git is a purely functional data structure. And that others look at the ways you can use Git and point a finger and say, "Look! It can be mutated! Therefore it cannot be functional!" And the response to that is, "Don't be so technical about how you define functional. Or immutable. You know it when you see it." Is this some kind of Obi-wan Kenobi from a certain point of view stuff? Why is this so difficult to get a handle on? If a thing says immutable on the tin, and it's mutable, how is that purely functional? I know, read the paper. I know. But still, it's a legit question. It seems to me that a data structure so amazing as being purely functional shouldn't be so easy to misunderstand as what we're seeing here. And it's clearly being misunderstood. And not only by me.

vickychijwani 9y ago
> "Look! It can be mutated! Therefore it cannot be functional!" And the response to that is, "Don't be so technical about how you define functional. Or immutable. You know it when you see it." I think I can offer something to the discussion here, as I'm straddling the 2 camps - having a fairly intricate understanding of git (I've held training seminars at my company about it), and basic familiarity with functional (technically "persistent") data structures thanks to a long-standing interest in Clojure. What the functional camp is talking about, when they refer to git as a "purely functional data structure", is the core of git's implementation - commits are immutable snapshots of the repository arranged in a directed acyclic graph (or a tree, if there are no merge commits), and branches are "just" movable pointers to some commit. In this view, everything other than this core model of history as a graph is extra details layered on top. The other camp (let's call them the "git camp") looks at git in its entirety, including branches, tags, the index, the working tree, stashes, and so on, and they can't help but come to the conclusion you mentioned - "Branches are mutable references! The index is mutable! The working tree is mutable! How can git possibly be called a functional data structure?" While this 2nd perspective is understandable and technically correct, I think it misses the point the other camp is trying to make: that the immutable commit is the "fundamental unit of git" so to speak, that we interact with everyday, and that most of git's history-manipulating commands (git commit, git commit --amend, git rebase, git merge, git cherry-pick) can be described in terms of purely-functional operations on the commit graph. Once you understand this, many complex git scenarios become easier to understand (rebase, and filter-branch, for example), so this view does have practical value. Then branches, tags, the index, stashes, etc can indeed be understood separately. In fact, this perspective of git as a data structure is so useful, that I rarely use "git log" as it is, preferring these additional flags to view the entire graph instead: git log --graph --all --decorate --oneline I hope that helps, cheers!