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

61–70 of 99 posts

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

#61

Post by Dylan16807 »

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…

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

Functional languages are only immutable on that meta level where we talk about objects in memory. The implementation uses mutable RAM though, and even garbage collects when the size gets too big and needs to store more efficiently.

Unless you want to narrow the term 'functional' so much it describes nothing at all, Git is a functional data structure.

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

#62

Post by runeks »

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…

> I think the concept of immutability confuses people.

I think it confuses people because it’s framed oddly. Immutability isn’t about being unable to mutate state, it’s about no longer using containers (registers) as variables, such that the equal operator actually means “equals” as opposed to “store”.

In most programming languages, the equal operator works as a “store” operation, which stores a value in a named container/register. In “immutable by default” languages like Haskell, the equal operator actually means “equals”, as in “is synonymous with”.

The essence of immutability is referencing values directly, through synonyms, as opposed to storing them in named registers for later retrieval. When it’s done this way, immutability no longer makes sense: is the number 3 mutable? Can the number 3 be mutated into 4, or are they just two distinct numbers?

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

#63

Post by pdonis »

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 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 one, plus the other 99 blobs that store the contents of files you didn't change; the new commit object then references the new tree object (plus the message and metadata). But git never stores diffs between old and new content; it just creates a new blob every time the content of a file changes.

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

#64

Post by canes123456 »

runeks wrote: post #62
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…

> I think the concept of immutability confuses people. I think it confuses people because it’s framed oddly. Immutability isn’t about being unable to mutate state, it’s about no longer using containers (registers) as variables, such that the equal operator actually means “equals” as opposed to “store”. In most programming languages, the equal operator works as a “store” operation, which stores a value in a named cont…

I think I understand the point you are making but this is way more confusing for me. Partly this can be blamed on imperative lanuages and = vs ==.

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

#65

Post by erikb »

Dylan16807 wrote: post #61
erikb wrote: post #54

Earlier quoted context omitted.

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…

> 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. Functional languages are only immutable on that meta level where we talk about objects in memory. The implementation uses mutable RAM though, and even garbage coll…

It seems like you say that with the goal of proofing me wrong with an example. But what you say is

(a) an argument helping my thesis by showing that you can program functional languages quite well by using mutable recourses

(b) the biggest users of what you write there are also the biggest enemies of the status quo you describe. Functional programmers really hate that computers are so unlike what they love.

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

#67

Post by Dylan16807 »

erikb wrote: post #65
Dylan16807 wrote: post #61

Earlier quoted context omitted.

> 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. Functional languages are only immutable on that meta level where we talk about objects in memory. The implementation uses mutable RAM though, and even garbage coll…

It seems like you say that with the goal of proofing me wrong with an example. But what you say is (a) an argument helping my thesis by showing that you can program functional languages quite well by using mutable recourses (b) the biggest users of what you write there are also the biggest enemies of the status quo you describe. Functional programmers really hate that computers are so unlike what they love.

> (a) an argument helping my thesis by showing that you can program functional languages quite well by using mutable recourses

You can implement a functional language with mutable resources, and you can implement a functional data structure like git with mutable resources. How does it help your thesis that git isn't a functional data structure?

> (b) the biggest users of what you write there are also the biggest enemies of the status quo you describe. Functional programmers really hate that computers are so unlike what they love.

Whatever, something that is purely functional all the way down to the wires is impossible.

Any definition of "functional" the rejects every single functional language is an objectively failed definition. A usable definition will go ahead and permit the git data structure to be called functional.

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

#68

Post by jdmichal »

pdonis wrote: post #63
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 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-Packfiles

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

#69

Post by runT1ME »

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…

Nice, good explanation. And one way to look at the State Monad is when you always want the 'latest version' of an immutable 'value' that keeps getting new versions. :)

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

#70

Post by greghendershott »

dustingetz wrote: post #47
xj9 wrote: post #41

Earlier quoted context omitted.

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.

do it!

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