[TUHS] A second Unix Patent

[TUHS] A second Unix Patent

[Warner Losh]

[-- Attachment #1.1: Type: text/plain, Size: 303 bytes --]

In looking at the first AUUGN today, I noticed the following at the end of
a letter John Lions sent home when he spent a sabbatical at Bell Labs

[image: image.png]
I've seen the first patent, but not the second one... That's got to be a
joke or inside joke, right? Anybody know anything else about it?

[-- Attachment #1.2: Type: text/html, Size: 422 bytes --]

[-- Attachment #2: image.png --]
[-- Type: image/png, Size: 46129 bytes --]

[TUHS] Re: A second Unix Patent

[Douglas McIlroy]

[-- Attachment #1.1: Type: text/plain, Size: 1730 bytes --]

Typo, in v3 through v6, may be the most creative Unix program to have come
out of Bell Labs. It served as a spell checker before spell(1), though it
knew nothing about spelling beyond a list of the most common words in the
language. This brainchild of Bob Morris would, in his words, work just as
well in Urdu as in English.

The beautiful trick: gather trigram frequencies in the document, then print
out a list of the individual words in increasing order of the likelihood
that they came from the statistical source that those frequencies
characterize. Typos (as distinct from phonetic misspellings) generally
floated toward the beginning of the list and so were easy to spot.

But that's not all that Bob invented. 26^3 16-bit trigram counts didn't fit
in the PDP-11 memory, so he counted them in 8-bit bytes. To do so he
invented the trick of "counting large integers in small registers". Roughly
speaking, when you see a word whose current count is in the range 2^(n-1)
to 2^n-1, you increment the count with probability 1/2^n, thus getting an
approximation to lg n, which serves in estimating the entropy of each word.

This counting method merited a patent and is now recognized as the first of
what is now an active subfield of theoretical computer
science--memory-bounded streaming algorithms.

Doug

On Wed, Mar 1, 2023 at 6:00 PM Warner Losh <imp@bsdimp.com> wrote:

> In looking at the first AUUGN today, I noticed the following at the end of
> a letter John Lions sent home when he spent a sabbatical at Bell Labs
>
> [image: image.png]
> I've seen the first patent, but not the second one... That's got to be a
> joke or inside joke, right? Anybody know anything else about it?
>

[-- Attachment #1.2: Type: text/html, Size: 2127 bytes --]

[-- Attachment #2: image.png --]
[-- Type: image/png, Size: 46129 bytes --]

[TUHS] Re: A second Unix Patent

[David Arnold]

[-- Attachment #1: Type: text/html, Size: 2714 bytes --]

[TUHS] Re: A second Unix Patent

[Steve Mynott]

While poking around I discovered a modern go rewrite by Rob Pike

https://github.com/robpike/typo


On Wed, Mar 01, 2023 at 11:41:17PM -0500, Douglas McIlroy typed:

> Typo, in v3 through v6, may be the most creative Unix program to have come
> out of Bell Labs. It served as a spell checker before spell(1), though it
> knew nothing about spelling beyond a list of the most common words in the
> language. This brainchild of Bob Morris would, in his words, work just as
> well in Urdu as in English.
> 
> The beautiful trick: gather trigram frequencies in the document, then print
> out a list of the individual words in increasing order of the likelihood
> that they came from the statistical source that those frequencies
> characterize. Typos (as distinct from phonetic misspellings) generally
> floated toward the beginning of the list and so were easy to spot.
> 
> But that's not all that Bob invented. 26^3 16-bit trigram counts didn't fit
> in the PDP-11 memory, so he counted them in 8-bit bytes. To do so he
> invented the trick of "counting large integers in small registers". Roughly
> speaking, when you see a word whose current count is in the range 2^(n-1)
> to 2^n-1, you increment the count with probability 1/2^n, thus getting an
> approximation to lg n, which serves in estimating the entropy of each word.
> 
> This counting method merited a patent and is now recognized as the first of
> what is now an active subfield of theoretical computer
> science--memory-bounded streaming algorithms.


-- 
Steve Mynott <steve.mynott@gmail.com>
rsa3072/629FBB91565E591955B5876A79CEFAA4450EBD50

[TUHS] Re: A second Unix Patent

[James Frew]

This qualifies as a true Service to the Profession™.

If you doubt that, take a look at the original C version, completely 
free of pesky comments. (Would've made a great CS PhD exam question: 
"What does this code do?")

/Frew

P.S.: All you cats waiting on the books I promised: they're all boxed up 
on the spare bed behind me, shipping Real Soon Now™.

On 2023-03-03 05:29, Steve Mynott wrote:
> While poking around I discovered a modern go rewrite by Rob Pike
>
> https://github.com/robpike/typo
>
> On Wed, Mar 01, 2023 at 11:41:17PM -0500, Douglas McIlroy typed:
>> Typo, in v3 through v6, may be the most creative Unix program to have come
>> out of Bell Labs.

[TUHS] A second Unix Patent

[Douglas McIlroy]

> This one, perhaps:

> https://patents.google.com/patent/US3964059A/en

Yes, that's the Typo patent. Notice that it features "method and
apparatus". The bizarre idea of doing it in hardware was a figment of
the patent department's imagination. This was a dance to circumvent
the belief at the time that software could not be patented. Software
was smuggled in by stating that it was one way to realize the
apparatus in the patent disclosure.

The now obsolete belief was fallout from Gottsschalk v Benson, in
which the Supreme Court invalidated another Bell Labs patent, on a
trick to save a few cycles in converting integers between BCD and
binary. The grounds for rejection were roughly that software was math
(a "mental step") and therefore not patentable.

The Benson decision, written by William O. Douglas, makes ludicrous
reading: it argues, though the patent does not claim, that a patent on
this narrow method could be enforced against any program that converts
BCD to binary. Apparently Douglas thought that all black-box programs
for a given purpose were the same, although the patent office did not
so conflate different mechanical or electrical apparatuses that have a
common purpose.

Doug