Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Git is a purely functional data structure (2013)

blog.jayway.com

Post reply on HN
Print view View original

51–60 of 99 posts

Re: Git is a purely functional data structure (2013)

#51

Post by malkia »

arximboldi wrote: post #42
masklinn wrote: post #39

Earlier quoted context omitted.

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 havi…

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 Ncurses example (full text-editor…

Thank you Juan for the talks (I watched both the CppNow, and CppCon, though the latter one is even better). Also for the wonderful libs, and the real-life example (your text editor).

At work, we are pondering on a new way to split our game levels editing code, and persistent data structures came to me as one idea, in order to handle UNDO in generic way, and they by diff, or other means visualize the changes. I've read Okasaki's book long time ago, but seeing this implemented in a imperative language is really helpful.

Also pretty much enjoyed the post-modern talk too :) - hehehe

Thank you!

Re: Git is a purely functional data structure (2013)

#52

Post by arximboldi »

malkia wrote: post #51
arximboldi wrote: post #42

Earlier quoted context omitted.

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 Ncurses example (full text-editor…

Thank you Juan for the talks (I watched both the CppNow, and CppCon, though the latter one is even better). Also for the wonderful libs, and the real-life example (your text editor). At work, we are pondering on a new way to split our game levels editing code, and persistent data structures came to me as one idea, in order to handle UNDO in generic way, and they by diff, or other means visualize the changes. I've rea…

Thanks a lot Malkia, that is super encouraging!

Editing code for game levels seems to me like a quite good use-case for this. "Editing" software with rich hierarchical documents is the itch I originally wanted to scratch with this work, even though there are many other use-cases too. Feel free to send me an email if you move further with that idea or if you want to discuss any of these topics with me :-)

Re: Git is a purely functional data structure (2013)

#54

Post by erikb »

LukeShu wrote: post #36
erikb wrote: post #9

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. F…

As others have said, "purely functional data structure" is a jargon term with a precise meaning--that fact that this is true indicates that data structures can, in fact, be functional in this sense. To claim that "the word 'functional' is purely wrong" is, well, purely wrong; the data structure in Git being described is purely functional. Beyond that, you seem to have shown misunderstanding of what that means (despit…

Yes, I didn't accept that part of the logic. Neither do I believe that immutability is something good, nor do I believe that git is very immutable, nor that git gains from immutability.

I believe mutability is a trade off. You can make objects more immutable by being less efficient in terms of storage size, search time, source code simplicity. In exchange for these negative attributes you get source code you can proof more easily. It's good when that attribute is needed, but not most of the time.

Git is only immutable on that meta level where we talk about the object key-value store. The implementation uses mutable files though, and even steps away from that immutable key-value store when the size gets too big and needs to store more efficiently.

And on the user level you can amend, edit, squash and delete commits easily, which is actually a strength of git not a weakness. People love it for being more mutable than SVN.

Re: Git is a purely functional data structure (2013)

#55

Post by rootlocus »

Simon_says wrote: post #26
davidcuddeback wrote: post #20

Earlier quoted context omitted.

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?

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.

> 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

Re: Git is a purely functional data structure (2013)

#56

Post by rootlocus »

_0w8t wrote: post #13
klodolph wrote: post #10

Earlier quoted context omitted.

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…

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.

If you want immutable branches, you can use tags https://git-scm.com/book/en/v2/Git-Basics-Tagging

Re: Git is a purely functional data structure (2013)

#57

Post by fiatjaf »

_0w8t wrote: post #13
klodolph wrote: post #10

Earlier quoted context omitted.

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…

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.

So your entire point amounts to naming?

Re: Git is a purely functional data structure (2013)

#58

Post by misnome »

kazinator wrote: post #33
Edmond wrote: post #6

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…

> Git lets you do version control via full snapshots as opposed to just tracking diffs. That's completely orthogonal to whether the version history is immutable with each branch being like singly linked list where we "cons" new things onto the front.

That’s the point; because sentences like

> the version history is immutable with each branch being like a singly linked list where we “cons” new things onto the front

Just contributes to the general confusion around git where people decide it’s too complicated to learn.

(Apologies if my sarcasm detector is just broken today)

Re: Git is a purely functional data structure (2013)

#59

Post by mbrock »

sparkie wrote: post #43
linschn wrote: post #24

Earlier quoted context omitted.

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.

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.

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.

Re: Git is a purely functional data structure (2013)

#60

Post by misnome »

sparkie wrote: post #43
linschn wrote: post #24

Earlier quoted context omitted.

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.

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.

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?
Post reply on HN