Re: [TUHS] About SCCS (and PWB)

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 <lm(a)mcvoy.com> wrote: _______________________________________________ TUHS mailing list TUHS(a)minnie.tuhs.org https://minnie.tuhs.org/mailman/listinfo/tuhs