From mboxrd@z Thu Jan 1 00:00:00 1970 From: clemc@ccc.com (Clem Cole) Date: Mon, 9 Nov 2015 20:09:18 -0500 Subject: [TUHS] About SCCS (and PWB) In-Reply-To: References: <20151109230509.GC24474@mcvoy.com> Message-ID: Outstanding. I love it. You can use emoji's today and have the scatological references inline. Clem On Mon, Nov 9, 2015 at 6:49 PM, Marc Rochkind wrote: > Since you asked, here's the true story of how I came up with the delta > encoding, a story never before told. > > I was living in a garden apartment in Sayreville, NJ, and at night would > walk my girlfriend's dog along a hillside just outside our front door. It > was usually cold, I didn't like the dog (still don't like dogs), and hated > dodging the piles of dog shit while he tugged on the leash. So, as a coping > mechanism, I used to let my mind wander, and one evening it was wandering > and wondering about a problem I was struggling with, which was how to store > the source and the deltas all in the same file. (It was a "data set," on > the IBM OS/360 system we were using--we weren't on UNIX yet.) > > Anyway, no doubt simultaneously with this unpleasant animal taking a shit, > I came up with idea of surrounding pieces of text with markers. (The > algorithm itself is documented in my original 1975 paper, which you can > read about here: http://basepath.com/aup/talks/SCCS-Slideshow.pdf.) > > (Wouldn't this be an even better story if I said that the little piles of > dog poop on the hillside looked like markers in the soft glow of a full > moon? It's not true, but perhaps I'll tell it that way if the occasion > arises in the future.) > > When I got inside, I started to sketch out how the markers might work, and > came up with interesting observation that insertion start/end markers > obviously nested, but deletion start/end markers did not nest with insert > start/end markers. This is obvious if you think about it the right way: > When you delete, the text you're deleting could have been added at various > times, but when you insert, the inserted text is always added at the same > time. > > I didn't have replacement markers; insert and delete were enough, I > thought. > > I kept fooling around with the idea until I had an algorithm that I > thought would work to retrieve any version with a single pass. (It's in the > paper, referenced above.) > > To prove the algorithm to be correct, I enumerated all possible cases of > insertions mixed in with deletions. I don't recall how many cases I had, > but I think it was around 20 or 30. Then I painstakingly went though every > case, making sure the algorithm produced the right answer. This was a rare > example of me doing actual work. > > Coding it up, as I remember, was very easy, as the scheme is pretty > simple. I'm sure I had it running in SNOBOL4 in a day or two. Redesigning > SCCS in C for UNIX came maybe a year or so later, but the algorithm > remained the same. > > Larry very kindly says: "SCCS has interleaved deltas. It's a brilliant > design that has far far better performance than anything else out there." > > Maybe it was brilliant, but I can tell you that I was just trying to pass > the time while that stupid dog did his business. > > --Marc > > On Mon, Nov 9, 2015 at 4:05 PM, Larry McVoy wrote: > >> On Mon, Nov 09, 2015 at 04:02:44PM -0700, Marc Rochkind wrote: >> > I just got on this list today, and I see that Larry McVoy asks: >> > >> > "I wish Marc was on this list, be fun to chat." >> > >> > I'd be happy to chime in on SCCS or early PWB questions, to the extent I >> > remember anything. >> >> Awesome! How about a start of how you came up with the SCCS design, >> in particular the interleaved delta format (we internally call it >> "the weave")? >> > > > _______________________________________________ > TUHS mailing list > TUHS at minnie.tuhs.org > https://minnie.tuhs.org/mailman/listinfo/tuhs > > -------------- next part -------------- An HTML attachment was scrubbed... URL: