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

21–30 of 99 posts

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

#21

Post by goialoq »

randomsearch wrote: post #18
rubenbe wrote: post #4

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

This suggests a poor abstraction.

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

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

#22

Post by erikb »

davidcuddeback wrote: post #15
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…

> 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_structu... [2] https://www.amazon.com/Purely-Functional-Structures-Chris-Ok...

I feel like I already said "I understand but I disagree".

A round wheel is more useful for a car than a triangular wheel. That doesn't mean it's a "car wheel". It's just as good on a horse wagon or a bike.

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

#23

Post by erikb »

how_gauche wrote: post #19
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…

> 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. Why is it that whenever functional programming comes up, "real programme…

See the other leaf of this purely functional comment tree for my answer.

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

#24

Post by linschn »

snissn wrote: post #14

Is git a blockchain?

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.

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

#26

Post by Simon_says »

davidcuddeback wrote: post #20
Simon_says wrote: post #16

Earlier quoted context omitted.

Alright wiseguy, git gc.

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.

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

#27

Post by dustingetz »

Simon_says wrote: post #16
19870213 wrote: post #5

Earlier quoted context omitted.

But git-rebase does not alter existing commits in the commit tree, it simply creates a new branch (meaning new commits) on the tree.

Alright wiseguy, git gc.

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)

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

#28

Post by dustingetz »

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.

hey you're getting downvoted bc you misunderstand so insistently and cockily, maybe try asking a question

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

#29

Post by davidcuddeback »

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.

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.

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

#30

Post by rst »

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…

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