Git is a purely functional data structure (2013) • Hacker News Board

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

#71

Post by pqh » Sat, Dec 09, 2017, 11:09 PM UTC

erikb wrote: post #54

LukeShu wrote: post #36

Earlier quoted context omitted.

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

And yet, thankfully, the old versions of those commits are still present in the reflog for some time. Making it easy to recover from finger slips.

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

#72

Post by dustingetz » Sat, Dec 09, 2017, 11:09 PM UTC

greghendershott wrote: post #70

dustingetz wrote: post #47

Earlier quoted context omitted.

do it!

Depending on the definition of "it", someone has: https://github.com/tonsky/datascript

datomic is a distributed system, datascript is an in memory data structure (it is very cool though, i use it)

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

#73

Post by shurcooL » Sun, Dec 10, 2017, 12:11 AM UTC

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.

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

#74

Post by no_wizard » Sun, Dec 10, 2017, 12:18 AM UTC

masklinn wrote: post #49

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…

> Good immutable data-structures are important for big programs though. I'm guessing you mean good in the sense of well-implemented (performant), but I think good in terms of interface is also very important For instance in my experience & opinion Immutable.JS is not very fun to use regardless of its implementation, because the interface does not feel natural for the language (not that the designers can really be fau…

Python however does provide some immutable constructs as part of it’s core language (Tuples)

It also has the ability to really take any object and attach states to it at whim, including immutability.

I think that’s a better trade off than JS

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

#75

Post by sobellian » Sun, Dec 10, 2017, 1:13 AM UTC

BenoitEssiambre wrote: post #17

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…

> In the background "var a=i, var b=a+j", might compile as something like "var b = i; b+=j";

Believe it or not, many compilers internally represent mutable variables as a sequence of immutable variables: https://en.wikipedia.org/wiki/Static_single_assignment_form

Edit: I should clarify that I mean "immutable" in the context of primitive values like integers.

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

#76

Post by emmelaich » Sun, Dec 10, 2017, 3:19 AM UTC

jdmichal wrote: post #68

pdonis wrote: post #63

Earlier quoted context omitted.

> git doesn't actually create new copies of the content for each commit More precisely, it doesn't create new copies of content that you didn't change. For example, if you have 100 files in your repo and you change one of them and then commit, git creates a new copy of the content of the file you changed--a new blob storing the new file content--and a new tree object that references the new blob instead of the old on…

> But git never stores diffs between old and new content; it just creates a new blob every time the content of a file changes. Git pack files compress objects by storing them as diff files going backwards. That is, it stores the most recent state in full, then uses patches to go backwards. Because you're more likely to need a recent version in full than an older one. https://git-scm.com/book/en/v2/Git-Internals-Packf…

This is true but packfiles are an implementation detail.

It's still useful and more accurate conceptually to consider every commit as a complete snapshot of the state of code that point.

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

#77

Post by catnaroek » Sun, Dec 10, 2017, 4:12 AM UTC

tathougies wrote: post #35

_0w8t wrote: post #13

Earlier quoted context omitted.

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.

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.

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

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

#78

Post by catnaroek » Sun, Dec 10, 2017, 4:13 AM UTC

masklinn wrote: post #50

_0w8t wrote: post #13

Earlier quoted context omitted.

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.

> In Haskell let bindings are immutable. Haskell has mutable refs. That's what Git branches are.

But the contents of a mutable ref aren't let-bound.

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

#79

Post by masklinn » Sun, Dec 10, 2017, 9:50 AM UTC

no_wizard wrote: post #74

masklinn wrote: post #49

Earlier quoted context omitted.

> Good immutable data-structures are important for big programs though. I'm guessing you mean good in the sense of well-implemented (performant), but I think good in terms of interface is also very important For instance in my experience & opinion Immutable.JS is not very fun to use regardless of its implementation, because the interface does not feel natural for the language (not that the designers can really be fau…

Python however does provide some immutable constructs as part of it’s core language (Tuples) It also has the ability to really take any object and attach states to it at whim, including immutability. I think that’s a better trade off than JS

I think you completely missed my point. That aside,

> Python however does provide some immutable constructs as part of it’s core language (Tuples)

That doesn't really help when you're looking for persistent datastructures.

> It also has the ability to really take any object and attach states to it at whim, including immutability.

No, and if it did that would not be an advantage in this context.

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

#80

Post by doug1001 » Sun, Dec 10, 2017, 10:51 AM UTC

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...)