[TUHS] About SCCS (and PWB)

[TUHS] About SCCS (and PWB)

[Marc Rochkind]

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.

I did see a thread about PWB contributions in which people are trying to
sort out what came from research and what from the PWB group (under Evan
Ivie). As I recall, PWB was always based on research. Dick Haight would
install the latest research system from time-to-time, and then the
so-called "PWB UNIX" was whatever he had taken from research plus stuff we
were developing, such as SCCS. Unlike, say, Columbus UNIX, our kernel
always matched research at the system call level, so there never was such a
thing as a PWB-kernel dependency.

(I think the USG system was run quite differently: They had their own
system, and would merge improvements from research into it. I could be
wrong about this, as I never worked in the USG group.)

--Marc
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://minnie.tuhs.org/pipermail/tuhs/attachments/20151109/fdb8db68/attachment.html>

[TUHS] About SCCS (and PWB)

[Larry McVoy]

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] About SCCS (and PWB)

[Marc Rochkind]

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")?
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://minnie.tuhs.org/pipermail/tuhs/attachments/20151109/48873390/attachment.html>

[TUHS] About SCCS (and PWB)

[Clem Cole]

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/89afb3f1/attachment.html>

[TUHS] About SCCS (and PWB)

[Marc Rochkind]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 4061 bytes --]

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