[TUHS] About SCCS (and PWB)

[Marc Rochkind]

💩
On Nov 9, 2015 6:09 PM, "Clem Cole" <clemc at ccc.com> wrote:

> 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 <rochkind at basepath.com>
> 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 <lm at mcvoy.com> 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: <http://minnie.tuhs.org/pipermail/tuhs/attachments/20151109/6acd29fd/attachment.html>