The Unix Heritage Society mailing list
 help / color / mirror / Atom feed
* Re: [TUHS] {TUHS] Interesting Commentary on Unix from Multicians
@ 2022-04-09 11:45 Douglas McIlroy
  2022-04-09 13:09 ` Larry Stewart
                   ` (3 more replies)
  0 siblings, 4 replies; 12+ messages in thread
From: Douglas McIlroy @ 2022-04-09 11:45 UTC (permalink / raw)
  To: TUHS main list

> Single Level Storage is an awesome concept and removes so many ugly
> hacks from algorithms that otherwise have to process data in files.

This was Vic Vyssotsky's signature contribution to Multics, though in typical
Vyssotsky fashion he never sought personal credit for it. Other awesome
Vyssotsky inventions:

BLODI (block diagram), the first data-flow language, for sample-data systems.

Parallel flow analysis (later reinvented and published  by John Cocke). Vic
installed this in Fortran to produce diagnostics such as, "If the
third branch of IF
statement 15 is ever taken, then variable E will be used before being set".

Darwin, the original game of predation and self-reproduction among programs.
Corewars.org keeps a descendant version going 60 years later.

A minimum-spanning-tree algorithm quite different from the well-known methods
due to his colleagues Bob Prim and Joe Kruskal, again unpublished.

Not long ago on TUHS, Andrew Hume told how Vic found the same isolated bug in
dc by mathematically generating hard cases that Andrew stumbled on by accident,

As you may infer, Vic is one of my personal computing heroes.

Doug

^ permalink raw reply	[flat|nested] 12+ messages in thread

* Re: [TUHS] {TUHS] Interesting Commentary on Unix from Multicians
  2022-04-09 11:45 [TUHS] {TUHS] Interesting Commentary on Unix from Multicians Douglas McIlroy
@ 2022-04-09 13:09 ` Larry Stewart
  2022-04-09 18:25 ` Ken Thompson
                   ` (2 subsequent siblings)
  3 siblings, 0 replies; 12+ messages in thread
From: Larry Stewart @ 2022-04-09 13:09 UTC (permalink / raw)
  To: Douglas McIlroy; +Cc: TUHS main list


I worked for Vic at the Digital Cambridge Research Lab. Entirely awesome.  Another Vic story is how he got sent to visit the Pave Paws radar on Cape Cod because the locals were worried that software errors in the phased array controls could zap the populace.
Vic talked to the radar people and found out that there was a hardware stop that prevented beam angles below 3 degrees, so there was no need to worry about bugs.

Vic would always remember what the original problem was, rather than get lost in irrelevant details.

-L

> On Apr 9, 2022, at 7:48 AM, Douglas McIlroy <douglas.mcilroy@dartmouth.edu> wrote:
> 
> 
>> 
>> Single Level Storage is an awesome concept and removes so many ugly
>> hacks from algorithms that otherwise have to process data in files.
> 
> This was Vic Vyssotsky's signature contribution to Multics, though in typical
> Vyssotsky fashion he never sought personal credit for it. Other awesome
> Vyssotsky inventions:
> 
> BLODI (block diagram), the first data-flow language, for sample-data systems.
> 
> Parallel flow analysis (later reinvented and published  by John Cocke). Vic
> installed this in Fortran to produce diagnostics such as, "If the
> third branch of IF
> statement 15 is ever taken, then variable E will be used before being set".
> 
> Darwin, the original game of predation and self-reproduction among programs.
> Corewars.org keeps a descendant version going 60 years later.
> 
> A minimum-spanning-tree algorithm quite different from the well-known methods
> due to his colleagues Bob Prim and Joe Kruskal, again unpublished.
> 
> Not long ago on TUHS, Andrew Hume told how Vic found the same isolated bug in
> dc by mathematically generating hard cases that Andrew stumbled on by accident,
> 
> As you may infer, Vic is one of my personal computing heroes.
> 
> Doug


^ permalink raw reply	[flat|nested] 12+ messages in thread

* Re: [TUHS] {TUHS] Interesting Commentary on Unix from Multicians
  2022-04-09 11:45 [TUHS] {TUHS] Interesting Commentary on Unix from Multicians Douglas McIlroy
  2022-04-09 13:09 ` Larry Stewart
@ 2022-04-09 18:25 ` Ken Thompson
  2022-04-11 19:24   ` Dan Cross
  2022-04-28 21:05 ` Alan Glasser
  2022-05-11 12:47 ` [TUHS] {TUHS] Interesting Commentary on Unix from Multicians Joe
  3 siblings, 1 reply; 12+ messages in thread
From: Ken Thompson @ 2022-04-09 18:25 UTC (permalink / raw)
  To: Douglas McIlroy; +Cc: TUHS main list

[-- Attachment #1: Type: text/plain, Size: 1551 bytes --]

vic was my department head upon my arrival at
bell labs (june 1966). i went to my assigned office
and found vic, in combat boots, in a lotus position
on top of my filing cabinet. it is a vision that i will
never forget. he had just come to introduce himself.


On Sat, Apr 9, 2022 at 4:48 AM Douglas McIlroy <
douglas.mcilroy@dartmouth.edu> wrote:

> > Single Level Storage is an awesome concept and removes so many ugly
> > hacks from algorithms that otherwise have to process data in files.
>
> This was Vic Vyssotsky's signature contribution to Multics, though in
> typical
> Vyssotsky fashion he never sought personal credit for it. Other awesome
> Vyssotsky inventions:
>
> BLODI (block diagram), the first data-flow language, for sample-data
> systems.
>
> Parallel flow analysis (later reinvented and published  by John Cocke). Vic
> installed this in Fortran to produce diagnostics such as, "If the
> third branch of IF
> statement 15 is ever taken, then variable E will be used before being set".
>
> Darwin, the original game of predation and self-reproduction among
> programs.
> Corewars.org keeps a descendant version going 60 years later.
>
> A minimum-spanning-tree algorithm quite different from the well-known
> methods
> due to his colleagues Bob Prim and Joe Kruskal, again unpublished.
>
> Not long ago on TUHS, Andrew Hume told how Vic found the same isolated bug
> in
> dc by mathematically generating hard cases that Andrew stumbled on by
> accident,
>
> As you may infer, Vic is one of my personal computing heroes.
>
> Doug
>

[-- Attachment #2: Type: text/html, Size: 2181 bytes --]

^ permalink raw reply	[flat|nested] 12+ messages in thread

* Re: [TUHS] {TUHS] Interesting Commentary on Unix from Multicians
  2022-04-09 18:25 ` Ken Thompson
@ 2022-04-11 19:24   ` Dan Cross
  0 siblings, 0 replies; 12+ messages in thread
From: Dan Cross @ 2022-04-11 19:24 UTC (permalink / raw)
  To: Ken Thompson; +Cc: TUHS main list, Douglas McIlroy

[-- Attachment #1: Type: text/plain, Size: 2144 bytes --]

On Sat, Apr 9, 2022 at 2:29 PM Ken Thompson <kenbob@gmail.com> wrote:

> vic was my department head upon my arrival at
> bell labs (june 1966). i went to my assigned office
> and found vic, in combat boots, in a lotus position
> on top of my filing cabinet. it is a vision that i will
> never forget. he had just come to introduce himself.
>

This is a great story, though I confess that the thought of sitting like
that sounds rather uncomfortable.

I wonder if either or both of you, Ken, and Doug, could talk a little about
the Bell Labs withdrawal from Multics from your perspectives? What was that
like, and what was your relationship with the folks at MIT still at Project
MAC like afterwards? I gather it was friendly; was there any collaboration
there beyond casual correspondence?

        - Dan C.


On Sat, Apr 9, 2022 at 4:48 AM Douglas McIlroy <
> douglas.mcilroy@dartmouth.edu> wrote:
>
>> > Single Level Storage is an awesome concept and removes so many ugly
>> > hacks from algorithms that otherwise have to process data in files.
>>
>> This was Vic Vyssotsky's signature contribution to Multics, though in
>> typical
>> Vyssotsky fashion he never sought personal credit for it. Other awesome
>> Vyssotsky inventions:
>>
>> BLODI (block diagram), the first data-flow language, for sample-data
>> systems.
>>
>> Parallel flow analysis (later reinvented and published  by John Cocke).
>> Vic
>> installed this in Fortran to produce diagnostics such as, "If the
>> third branch of IF
>> statement 15 is ever taken, then variable E will be used before being
>> set".
>>
>> Darwin, the original game of predation and self-reproduction among
>> programs.
>> Corewars.org keeps a descendant version going 60 years later.
>>
>> A minimum-spanning-tree algorithm quite different from the well-known
>> methods
>> due to his colleagues Bob Prim and Joe Kruskal, again unpublished.
>>
>> Not long ago on TUHS, Andrew Hume told how Vic found the same isolated
>> bug in
>> dc by mathematically generating hard cases that Andrew stumbled on by
>> accident,
>>
>> As you may infer, Vic is one of my personal computing heroes.
>>
>> Doug
>>
>

[-- Attachment #2: Type: text/html, Size: 3024 bytes --]

^ permalink raw reply	[flat|nested] 12+ messages in thread

* Re: [TUHS] {TUHS] Interesting Commentary on Unix from Multicians
  2022-04-09 11:45 [TUHS] {TUHS] Interesting Commentary on Unix from Multicians Douglas McIlroy
  2022-04-09 13:09 ` Larry Stewart
  2022-04-09 18:25 ` Ken Thompson
@ 2022-04-28 21:05 ` Alan Glasser
  2022-04-30 10:45   ` [TUHS] Aleph Null in Software Practice & Experience Ralph Corderoy
  2022-05-11 12:47 ` [TUHS] {TUHS] Interesting Commentary on Unix from Multicians Joe
  3 siblings, 1 reply; 12+ messages in thread
From: Alan Glasser @ 2022-04-28 21:05 UTC (permalink / raw)
  To: Douglas McIlroy; +Cc: TUHS main list

[-- Attachment #1: Type: text/plain, Size: 1778 bytes --]

As the labs folks all probably know, Vic became the Executive Director of
division 91(two levels beyond department head).
This was after Research and Multics and, I think, Safeguard.
One of the early things he asked after quizzing various folks about what
was going on in the division was "Where is your source code control
system?".
The question fell to Rudd Canaday (then a department head under Vic).
And SCCS was thus born.

And who doesn't remember SP&E Aleph Null articles?

Alan


On Sat, Apr 9, 2022 at 7:47 AM Douglas McIlroy <
douglas.mcilroy@dartmouth.edu> wrote:

> > Single Level Storage is an awesome concept and removes so many ugly
> > hacks from algorithms that otherwise have to process data in files.
>
> This was Vic Vyssotsky's signature contribution to Multics, though in
> typical
> Vyssotsky fashion he never sought personal credit for it. Other awesome
> Vyssotsky inventions:
>
> BLODI (block diagram), the first data-flow language, for sample-data
> systems.
>
> Parallel flow analysis (later reinvented and published  by John Cocke). Vic
> installed this in Fortran to produce diagnostics such as, "If the
> third branch of IF
> statement 15 is ever taken, then variable E will be used before being set".
>
> Darwin, the original game of predation and self-reproduction among
> programs.
> Corewars.org keeps a descendant version going 60 years later.
>
> A minimum-spanning-tree algorithm quite different from the well-known
> methods
> due to his colleagues Bob Prim and Joe Kruskal, again unpublished.
>
> Not long ago on TUHS, Andrew Hume told how Vic found the same isolated bug
> in
> dc by mathematically generating hard cases that Andrew stumbled on by
> accident,
>
> As you may infer, Vic is one of my personal computing heroes.
>
> Doug
>

[-- Attachment #2: Type: text/html, Size: 2326 bytes --]

^ permalink raw reply	[flat|nested] 12+ messages in thread

* [TUHS] Aleph Null in Software Practice & Experience.
  2022-04-28 21:05 ` Alan Glasser
@ 2022-04-30 10:45   ` Ralph Corderoy
  2022-04-30 15:42     ` John Cowan
  0 siblings, 1 reply; 12+ messages in thread
From: Ralph Corderoy @ 2022-04-30 10:45 UTC (permalink / raw)
  To: tuhs

Hi,

Alan Glasser wrote:
> > Darwin, the original game of predation and self-reproduction among
> > programs.
...
> And who doesn't remember SP&E Aleph Null articles?

Doug has made the letter from him, Bob Morris, and Vic Vyssotsky to
Software Practice & Experience which introduces Darwin available at
https://www.cs.dartmouth.edu/~doug/darwin.pdf.  The letter is addressed
to C. A. Lang but accompanied by a note that Lang isn't א₀.

http://bit-player.org/2013/who-was-aleph-null wonders if א₀ and
side-kick Archimedes ‘might have been members of the Bell Labs gang that
was so lively and prolific in the late 60s and early 70s’ before
acknowledging the Darwin article rules it out.  After a false start
suspecting Lang, foiled by Doug's PDF of the letter, it goes on to
finally identify א₀ as Brit Richard Parkins who explains how it came
about on his own page at http://www.zen224037.zen.co.uk/SPE.shtml.

Reading the front page of Parkins' site, http://www.zen224037.zen.co.uk,
I see he ‘learnt his craft’ by programming assembler when at Cambridge,
on the country's first PDP-7 which he was allowed to use by Lang and
Neil Wiseman.  Unusually, it had a separate graphics processor driving a
1024²-pixel monochrome display.

Soon after, Parkins went on to build a graphics card for the Data
General Nova which drove a flat screen storage tube before Tektronix
released the 4010.  The story is buried in
http://www.zen224037.zen.co.uk/History.shtml.

-- 
Cheers, Ralph.

^ permalink raw reply	[flat|nested] 12+ messages in thread

* Re: [TUHS] Aleph Null in Software Practice & Experience.
  2022-04-30 15:42     ` John Cowan
@ 2022-04-30 12:52       ` Ralph Corderoy
  2022-04-30 13:33         ` Rob Pike
  0 siblings, 1 reply; 12+ messages in thread
From: Ralph Corderoy @ 2022-04-30 12:52 UTC (permalink / raw)
  To: tuhs

Hi John,

> Note that on correct Unicode renderers this is being shown as
> null-aleph instead of aleph-null.

Thanks for explaining.  I'm clearly using incorrect Unicode renderers.
:-)

-- 
Cheers, Ralph.

^ permalink raw reply	[flat|nested] 12+ messages in thread

* Re: [TUHS] Aleph Null in Software Practice & Experience.
  2022-04-30 12:52       ` Ralph Corderoy
@ 2022-04-30 13:33         ` Rob Pike
  2022-05-02  9:55           ` Ralph Corderoy
  0 siblings, 1 reply; 12+ messages in thread
From: Rob Pike @ 2022-04-30 13:33 UTC (permalink / raw)
  To: Ralph Corderoy; +Cc: TUHS main list

The output of  "unicode 5d0-5e7" (robpike.io/cmd/unicode has the
command) is fun.


05d0 א 05d1 ב 05d2 ג 05d3 ד
05d4 ה 05d5 ו 05d6 ז 05d7 ח
05d8 ט 05d9 י 05da ך 05db כ
05dc ל 05dd ם 05de מ 05df ן
05e0 נ 05e1 ס 05e2 ע 05e3 ף
05e4 פ 05e5 ץ 05e6 צ 05e7 ק

For comparison, here is "unicode 3d0-3e7". It will be fun to watch how
it's rendered.

03d0 ϐ 03d1 ϑ 03d2 ϒ 03d3 ϓ
03d4 ϔ 03d5 ϕ 03d6 ϖ 03d7 ϗ
03d8 Ϙ 03d9 ϙ 03da Ϛ 03db ϛ
03dc Ϝ 03dd ϝ 03de Ϟ 03df ϟ
03e0 Ϡ 03e1 ϡ 03e2 Ϣ 03e3 ϣ
03e4 Ϥ 03e5 ϥ 03e6 Ϧ 03e7 ϧ

-rob

^ permalink raw reply	[flat|nested] 12+ messages in thread

* Re: [TUHS] Aleph Null in Software Practice & Experience.
  2022-04-30 10:45   ` [TUHS] Aleph Null in Software Practice & Experience Ralph Corderoy
@ 2022-04-30 15:42     ` John Cowan
  2022-04-30 12:52       ` Ralph Corderoy
  0 siblings, 1 reply; 12+ messages in thread
From: John Cowan @ 2022-04-30 15:42 UTC (permalink / raw)
  To: Ralph Corderoy; +Cc: TUHS main list

[-- Attachment #1: Type: text/plain, Size: 555 bytes --]

On Sat, Apr 30, 2022 at 3:53 AM Ralph Corderoy <ralph@inputplus.co.uk>
wrote:

accompanied by a note that Lang isn't א₀.
>

Note that on correct Unicode renderers this is being shown as null-aleph
instead of aleph-null.  The reason for that is that you are using the
Hebrew letter, which is right-to-left and makes the neutral subscript zero
character rendered right-to-left as well.  So instead of א U+05D0 HEBREW
LETTER ALEF, you need the identical-looking but left-to-right character ℵ
U+2113 ALEF SYMBOL, which will give you ℵ₀.

[-- Attachment #2: Type: text/html, Size: 1553 bytes --]

^ permalink raw reply	[flat|nested] 12+ messages in thread

* Re: [TUHS] Aleph Null in Software Practice & Experience.
  2022-04-30 13:33         ` Rob Pike
@ 2022-05-02  9:55           ` Ralph Corderoy
  2022-05-02 10:03             ` Rob Pike
  0 siblings, 1 reply; 12+ messages in thread
From: Ralph Corderoy @ 2022-05-02  9:55 UTC (permalink / raw)
  To: tuhs

Hi Rob,

> The output of  "unicode 5d0-5e7" (robpike.io/cmd/unicode has the
> command) is fun.
>
> 05d0 א 05d1 ב 05d2 ג 05d3 ד
> 05d4 ה 05d5 ו 05d6 ז 05d7 ח
> 05d8 ט 05d9 י 05da ך 05db כ
> 05dc ל 05dd ם 05de מ 05df ן
> 05e0 נ 05e1 ס 05e2 ע 05e3 ף
> 05e4 פ 05e5 ץ 05e6 צ 05e7 ק
>
> For comparison, here is "unicode 3d0-3e7". It will be fun to watch how
> it's rendered.
>
> 03d0 ϐ 03d1 ϑ 03d2 ϒ 03d3 ϓ
> 03d4 ϔ 03d5 ϕ 03d6 ϖ 03d7 ϗ
> 03d8 Ϙ 03d9 ϙ 03da Ϛ 03db ϛ
> 03dc Ϝ 03dd ϝ 03de Ϟ 03df ϟ
> 03e0 Ϡ 03e1 ϡ 03e2 Ϣ 03e3 ϣ
> 03e4 Ϥ 03e5 ϥ 03e6 Ϧ 03e7 ϧ

In the terminal where I read and write email, they're all as if ‘0041 A’.
But save the email's text/plain to foo.txt and foo.html, add a little HTML
to foo.html, and the browser, here Firefox, presents the Hebrew in both as

    05d0 05 אd1 05 בd2 05 גd3 ד
    05d4 05 הd5 05 וd6 05 זd7 ח
    05d8 05 טd9 05 יda 05 ךdb כ
    05dc 05 לdd 05 םde 05 מdf ן
    05e0 05 נe1 05 סe2 05 עe3 ף
    05e4 05 פe5 05 ץe6 05 צe7 ק

due to the mix of Unicode's strong, weak, and neutral bi-directional
character types.

To see what I intend above needs a ‘broken’ renderer, like a terminal.
For those with more intelligent renderers, it's as if runes normally
drawn as

    00c0 À 00c1 Á 00c2 Â 00c3 Ã

became

    00c0 00 Àc1 00 Ác2 00 Âc3 Ã

Wrapping each of the Hebrew characters in the text and HTML files in
LRI...PDI,

    LRI  U+2066  Left-to-right isolate 
    PDI  U+2069  Pop directional isolate

so the first row becomes

    0030 0035 0064 0030  0020  2066 05d0 2069  0020
    0030 0035 0064 0031  0020  2066 05d1 2069  0020
    0030 0035 0064 0032  0020  2066 05d2 2069  0020
    0030 0035 0064 0033  0020  2066 05d3 2069  000a

has Firefox display the tables as intended.  Perhaps the unicode command
should do this to ensure correct display, especially if some terminals
ever start to improve?

I note that vim(1) here doesn't realise LRI and PDI are zero width
so the cursor position drifts past the end of the visible line.
ed(1) copes without a murmur.

-- 
Cheers, Ralph.

^ permalink raw reply	[flat|nested] 12+ messages in thread

* Re: [TUHS] Aleph Null in Software Practice & Experience.
  2022-05-02  9:55           ` Ralph Corderoy
@ 2022-05-02 10:03             ` Rob Pike
  0 siblings, 0 replies; 12+ messages in thread
From: Rob Pike @ 2022-05-02 10:03 UTC (permalink / raw)
  To: Ralph Corderoy; +Cc: TUHS main list

Under option, maybe. I'm not a fan of putting invisible characters
into a program designed to translate numbers into cut-and-pasteable
text. Plus, as you said, it just makes other things break, although
perhaps they should be encouraged not to.

-rob

On Mon, May 2, 2022 at 7:56 PM Ralph Corderoy <ralph@inputplus.co.uk> wrote:
>
> Hi Rob,
>
> > The output of  "unicode 5d0-5e7" (robpike.io/cmd/unicode has the
> > command) is fun.
> >
> > 05d0 א 05d1 ב 05d2 ג 05d3 ד
> > 05d4 ה 05d5 ו 05d6 ז 05d7 ח
> > 05d8 ט 05d9 י 05da ך 05db כ
> > 05dc ל 05dd ם 05de מ 05df ן
> > 05e0 נ 05e1 ס 05e2 ע 05e3 ף
> > 05e4 פ 05e5 ץ 05e6 צ 05e7 ק
> >
> > For comparison, here is "unicode 3d0-3e7". It will be fun to watch how
> > it's rendered.
> >
> > 03d0 ϐ 03d1 ϑ 03d2 ϒ 03d3 ϓ
> > 03d4 ϔ 03d5 ϕ 03d6 ϖ 03d7 ϗ
> > 03d8 Ϙ 03d9 ϙ 03da Ϛ 03db ϛ
> > 03dc Ϝ 03dd ϝ 03de Ϟ 03df ϟ
> > 03e0 Ϡ 03e1 ϡ 03e2 Ϣ 03e3 ϣ
> > 03e4 Ϥ 03e5 ϥ 03e6 Ϧ 03e7 ϧ
>
> In the terminal where I read and write email, they're all as if ‘0041 A’.
> But save the email's text/plain to foo.txt and foo.html, add a little HTML
> to foo.html, and the browser, here Firefox, presents the Hebrew in both as
>
>     05d0 05 אd1 05 בd2 05 גd3 ד
>     05d4 05 הd5 05 וd6 05 זd7 ח
>     05d8 05 טd9 05 יda 05 ךdb כ
>     05dc 05 לdd 05 םde 05 מdf ן
>     05e0 05 נe1 05 סe2 05 עe3 ף
>     05e4 05 פe5 05 ץe6 05 צe7 ק
>
> due to the mix of Unicode's strong, weak, and neutral bi-directional
> character types.
>
> To see what I intend above needs a ‘broken’ renderer, like a terminal.
> For those with more intelligent renderers, it's as if runes normally
> drawn as
>
>     00c0 À 00c1 Á 00c2 Â 00c3 Ã
>
> became
>
>     00c0 00 Àc1 00 Ác2 00 Âc3 Ã
>
> Wrapping each of the Hebrew characters in the text and HTML files in
> LRI...PDI,
>
>     LRI  U+2066  Left-to-right isolate
>     PDI  U+2069  Pop directional isolate
>
> so the first row becomes
>
>     0030 0035 0064 0030  0020  2066 05d0 2069  0020
>     0030 0035 0064 0031  0020  2066 05d1 2069  0020
>     0030 0035 0064 0032  0020  2066 05d2 2069  0020
>     0030 0035 0064 0033  0020  2066 05d3 2069  000a
>
> has Firefox display the tables as intended.  Perhaps the unicode command
> should do this to ensure correct display, especially if some terminals
> ever start to improve?
>
> I note that vim(1) here doesn't realise LRI and PDI are zero width
> so the cursor position drifts past the end of the visible line.
> ed(1) copes without a murmur.
>
> --
> Cheers, Ralph.

^ permalink raw reply	[flat|nested] 12+ messages in thread

* Re: [TUHS] {TUHS] Interesting Commentary on Unix from Multicians
  2022-04-09 11:45 [TUHS] {TUHS] Interesting Commentary on Unix from Multicians Douglas McIlroy
                   ` (2 preceding siblings ...)
  2022-04-28 21:05 ` Alan Glasser
@ 2022-05-11 12:47 ` Joe
  3 siblings, 0 replies; 12+ messages in thread
From: Joe @ 2022-05-11 12:47 UTC (permalink / raw)
  To: tuhs

On 4/9/22 13:45, Douglas McIlroy wrote:
>> Single Level Storage is an awesome concept and removes so many ugly
>> hacks from algorithms that otherwise have to process data in files.
> 
> This was Vic Vyssotsky's signature contribution to Multics, though in typical
> Vyssotsky fashion he never sought personal credit for it. Other awesome
> Vyssotsky inventions:
> 
> [..]
> A minimum-spanning-tree algorithm quite different from the well-known methods
> due to his colleagues Bob Prim and Joe Kruskal, again unpublished.
> 

Interesting, I had not heard about this before, and an internet search 
turned up:

(some copy of "Algorithms in C++", by Robert Sedgewick)
https://apprize.best/science/algorithms_2/3.html
paragraph 4.3.23: graphs(4) -> mst(3) -> vyssotsky(23)
https://github.com/reneargento/algorithms-sedgewick-wayne/blob/master/src/chapter4/section3/Exercise23_VyssotskyAlgorithm.java
(an implementation of this by Rene Argento?)

Algorithms in Java, 3rd edition (2003) R. Sedgewick
20.72: Exercises:
[V. Vyssotsky] Develop an implementation of the algorithm discussed in
Section 20.2 that builds the MST by adding edges one at a time and 
deleting the longest edges on the cycle formed (see Exercise 20.34). Use 
a parent-link representation of a forest of MST subtrees. Hint: Reverse 
links when traversing paths in trees.

I was unable to fetch this slide deck
https://web.archive.org/web/20081205054614/https://www.cs.princeton.edu/~rs/cs226/2002/lectures/19mst.pdf
which also appears to mention it at least in passing: "Other MST 
algorithms VYSSOTSKY (1960s) add edges one at a time delete longest on 
cycle formed"

Does anyone know of a more complete source on this topic?

It is not mentioned on Wikipedia, these seem like appropriate places to 
place a reference:
https://en.wikipedia.org/wiki/Minimum_spanning_tree
https://en.wikipedia.org/wiki/Victor_A._Vyssotsky


^ permalink raw reply	[flat|nested] 12+ messages in thread

end of thread, other threads:[~2022-05-11 12:55 UTC | newest]

Thread overview: 12+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-04-09 11:45 [TUHS] {TUHS] Interesting Commentary on Unix from Multicians Douglas McIlroy
2022-04-09 13:09 ` Larry Stewart
2022-04-09 18:25 ` Ken Thompson
2022-04-11 19:24   ` Dan Cross
2022-04-28 21:05 ` Alan Glasser
2022-04-30 10:45   ` [TUHS] Aleph Null in Software Practice & Experience Ralph Corderoy
2022-04-30 15:42     ` John Cowan
2022-04-30 12:52       ` Ralph Corderoy
2022-04-30 13:33         ` Rob Pike
2022-05-02  9:55           ` Ralph Corderoy
2022-05-02 10:03             ` Rob Pike
2022-05-11 12:47 ` [TUHS] {TUHS] Interesting Commentary on Unix from Multicians Joe

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).