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

91–99 of 99 posts

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

#91

Post by bbatha »

jdmichal wrote: post #90
emmelaich wrote: post #76

Earlier quoted context omitted.

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.

That can be said of every version control system. Restoration of state to any given version is their defining feature. How they achieve that is always an implementation detail, but those details can still be important and interesting.

Git commits are composed of all of the files in the commit, it’s parent and the commit message. This is an important guarantee that each checkout is valid without the rest of the repo. This allows you to have a lot of exotic implementations guarantee consistency between them. Meaning if your GitHub you can distribute commits across many servers. Or your Microsoft and you build partial checkouts for Gvfs. It’s what allows Git LFS to keep many of git’s core guarantees while making tradeoffs to improve areas where git is traditionally weak.

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

#92

Post by bjoli »

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…

Hi arximboldi!

I actually have a half-started emacs-like editor built using Qt that is based on ewig. Not anywhere near usable yet, but my plan is to make a fast editor with fast highlighting and such, and have everything accessible to be scripted in guile. I doubt it will actually materialise, but if I ever get a proof of concept it will be on github.

I love immer! It is friggin excellent.

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

#93

Post by nybble41 »

giesch wrote: post #89
canes123456 wrote: post #64

Earlier quoted context omitted.

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

In a procedural language: x == 3 means: Take the value out of the box x. Is it 3? x = 3 means: x is a box, put 3 in it. The 3 lasts forever, or until someone changes it. In a functional language: x = 3 means: Take the value out of box x. Is it 3? let x = 3 in [...] means: x is a box, put a 3 in it. The 3 lasts for only the [...], but cannot be undone.

Correction: In a functional language (specifically Haskell):

  x = 3 means: x is defined as 3.
  x == 3 means: Is x equal to 3?
  let x = 3 in [...] means: within the scope of [...], x is defined as 3.
There is no specific point where something is "put into the box" or "taken out of the box". In fact, there is no "box". The functional programming concept of "bindings" does not correspond to the imperative concept of "variables", not even the oxymoron known was "constant variables". (If you want variables in Haskell you need IORef or STRef, where the load and store operations are explicit monadic actions.)

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

#94

Post by emmelaich »

jdmichal wrote: post #90
emmelaich wrote: post #76

Earlier quoted context omitted.

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.

That can be said of every version control system. Restoration of state to any given version is their defining feature. How they achieve that is always an implementation detail, but those details can still be important and interesting.

Sorta true but see what bbatha said.

There are people who distinguish changeset oriented and snapshot oriented and will hotly debate that one or the other is better.

But as you say, restoration of state is a necessary and defining feature.

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

#95

Post by erikb »

erikb wrote: post #23
how_gauche wrote: post #19

Earlier quoted context omitted.

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

Since there is even another branch now, I paste it:

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)

#96

Post by arximboldi »

bjoli wrote: post #92
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…

Hi arximboldi! I actually have a half-started emacs-like editor built using Qt that is based on ewig. Not anywhere near usable yet, but my plan is to make a fast editor with fast highlighting and such, and have everything accessible to be scripted in guile. I doubt it will actually materialise, but if I ever get a proof of concept it will be on github. I love immer! It is friggin excellent.

Hey that's awesome! Let me know if you ever would like me to take a look at your code or anything. I'd be happy to link it from the Immer site too when you are ready to promote it :-)

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

#97

Post by ianamartin »

vickychijwani wrote: post #84
ianamartin wrote: post #82

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! There…

> "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 (t…

Thank you that. My understanding is that the unit of work in git—the commit—is not actually immutable. Commits can be changed. Am I wrong about that?

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

#98

Post by ianamartin »

how_gauche wrote: post #88
ianamartin wrote: post #82

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! There…

> some people who are in the know about a very specific paper This stuff isn't obscure just because you don't happen to know about it already. Chris Okasaki's publications have been cited over 1000 times, mostly for his PhD work -- those papers, especially on functional data structures and amortization analysis in lazy languages, are considered foundational for a whole research area in Computer Science. > Is this som…

Okay, so if a program means for an ibject to be immutable but it actually is mutable then it’s still immutable if you explain it in terms of basic CS theory.

Got it. Thanks for the attitude.

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

#99

Post by vickychijwani »

ianamartin wrote: post #97
vickychijwani wrote: post #84

Earlier quoted context omitted.

> "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 (t…

Thank you that. My understanding is that the unit of work in git—the commit—is not actually immutable. Commits can be changed. Am I wrong about that?

> Am I wrong about that?

Sorry, but yes :)

The commit is immutable because when you "amend" a commit, git actually creates a new commit object, assigning it a new SHA1 hash. This means that the original contents from before the amend (i.e., the "old" commit) are still accessible via the old SHA1 hash - proving that an "amended" commit is actually a copy of the old one, not an in-place mutation.

Think of it like this - if I copy a text file and edit the copy, would you say that I've "mutated" the original file? No, right? That's what git does - it never actually mutates a commit :)

EDIT: to clarify further, git identifies each commit with a unique SHA1 hash which is assigned when the commit is created, and that hash depends on the contents of the files + the current timestamp + the SHA1 of its parent commit + some other things. Which means, if you try to edit the contents of the commit in any way at all (or even if you create another commit with the same exact files at a different time, or as a child of a different commit), its SHA1 hash will be different, i.e., it is a new commit by definition.

Post reply on HN