It computed the minimal cost path through a cost matrix of string edit operations (the costs depended i.e. on the number of characters to draw, length of the escape codes to insert/delete lines/characters, padding for slow terminals, etc).
The algorithm used is a dynamic programming one, where
Each terminal type would configure the display driver according to its supported escape codes and screen update times (some terminals were REALLY SLOW inserting and deleting lines or even scrolling, and you had to send null padding to wait for it to finish).
It's infamous both for its skull-and-crossbones warning comment [designed by Brian Reed] and correspondingly poisonous complex code, and also RMS's battle with UniPress software, incorporating it into Gnu Emacs, getting threatened by UniPress, then rewriting it from scratch.
>RMS: I can't remember all the hacks that I was proud of, so I can't pick the best. But here's something I remember fondly. The last piece of Gosmacs code that I replaced was the serial terminal scrolling optimizer, a few pages of Gosling's code which was proceeded by a comment with a skull and crossbones, meaning that it was so hard to understand that it was poison. I had to replace it, but worried that the job would be hard. I found a simpler algorithm and got it to work in a few hours, producing code that was shorter, faster, clearer, and more extensible. Then I made it use the terminal commands to insert or delete multiple lines as a single operation, which made screen updating far more efficient.
There's some more discussion about it here that ended up being pretty accurate once all was said and done:
Emacs's infamous "Ultra-hot screen management package" with its "Skull and Crossbones" warning was definitely black magic!
The algorithm worked great and was well worth it over a 300 / 1200 / 2400 baud connection to a Vax 780 / 750 / etc, and as modems and computers got faster it was still useful, but at today's network bandwidths and cpu speeds it's thunderous overkill.
>7. Acknowledgements: The people who did the real work behind this paper are Mike Kazar, Charles Liescrson and Craig Everhart; all from CMU.
>Bibliography: 1. Kevin Q. Brown. Dynamic Programming in Computer Science. CMU, February, 1979.
That code was also used in Maryland Windows (a text based overlapping/tiled window system developed at the University of Maryland by Chris Torek, like Emacs - Text Editor + Window System, kind of like "screen" or "mux" or "mgr").
>Gosling Emacs was especially noteworthy because of the effective redisplay code, which used a dynamic programming technique to solve the classical string-to-string correction problem. The algorithm was quite sophisticated; that section of the source was headed by a skull-and-crossbones in ASCII art, warning any would-be improver that even if they thought they understood how the display code worked, they probably did not.
/* 1 2 3 4 .... Each Mij represents the minumum cost of
+---+---+---+---+----- rearranging the first i lines to map onto
1 | | | | | the first j lines (the j direction
+---+---+---+---+----- represents the desired contents of a line,
2 | | \| ^ | | i the current contents). The algorithm
+---+---\-|-+---+----- used is a dynamic programming one, where
3 | | <-+Mij| | M[i,j] = min( M[i-1,j],
+---+---+---+---+----- M[i,j-1]+redraw cost for j,2
4 | | | | | M[i-1,j-1]+the cost of
+---+---+---+---+----- converting line i to line j);
. | | | | | Line i can be converted to line j by either
. just drawing j, or if they match, by moving
. line i to line j (with insert/delete line)
*/
Trivia: That "Skull and Crossbones" ASCII art is originally from Brian Reid's Scribe program, and is not copyrighted.
/-------------\
/ \
/ \
/ \
| XXXX XXXX |
| XXXX XXXX |
| XXX XXX |
\ X /
--\ XXX /--
| | XXX | |
| | | |
| I I I I I I I |
| I I I I I I |
\ /
-- --
\-------/
XXX XXX
XXXXX XXXXX
XXXXXXXXX XXXXXXXXXX
XXXXX XXXXX
XXXXXXX
XXXXX XXXXX
XXXXXXXXX XXXXXXXXXX
XXXXX XXXXX
XXX XXX
**************
* BEWARE!! *
**************
All ye who enter here:
Most of the code in this module
is twisted beyond belief!
Tread carefully.
If you think you understand it,
You Don't,
So Look Again.
But if you're not trying to support old terminals (but might still have a slow "thin wire" network connection), there is an orders of magnitude better approach: The Emacs NeWS display driver (for both UniPress and Gnu Emacs) downloaded PostScript code to define an efficient application specific network protocol with instantaneous local input tracking and feedback (unlike how X-Windows uses a fixed protocol, but like how AJAX uses JavaScript).
The source code to Gosling's UniPress Emacs 2.20 just recently surfaced, and the display code is well commented (still including the skull and crossbones and ascii art diagrams):
The NeWS terminal drivers I worked on for UniPress and Gnu Emacs were layered on top of that dynamic programming screen update code. But instead of sending escape codes to a dumb terminal, it downloaded PostScript code into the NeWS server to implement drawing, mouse tracking, text selection feedback, pie menus, tabbed windows, etc, and sent binary PostScript tokens back and forth (a practice now called "AJAX" for X = XML or JSON text instead of binary PostScript data and code):
Here's a brochure from February 1988 about UniPress Emacs 2.20 and "SoftWire" (NeWS without graphics, kind of like Node with PostScript instead of JavaScript).
Makes sense as the most widely known algorithm for finding the minimal edit distance between two strings also relies on DP. It was invented around 1968.
https://en.wikipedia.org/wiki/Gosling_Emacs
It computed the minimal cost path through a cost matrix of string edit operations (the costs depended i.e. on the number of characters to draw, length of the escape codes to insert/delete lines/characters, padding for slow terminals, etc).
The algorithm used is a dynamic programming one, where
Each terminal type would configure the display driver according to its supported escape codes and screen update times (some terminals were REALLY SLOW inserting and deleting lines or even scrolling, and you had to send null padding to wait for it to finish).It's infamous both for its skull-and-crossbones warning comment [designed by Brian Reed] and correspondingly poisonous complex code, and also RMS's battle with UniPress software, incorporating it into Gnu Emacs, getting threatened by UniPress, then rewriting it from scratch.
https://features.slashdot.org/story/13/01/06/163248/richard-...
>Q: Give me your best hack. [...]
>RMS: I can't remember all the hacks that I was proud of, so I can't pick the best. But here's something I remember fondly. The last piece of Gosmacs code that I replaced was the serial terminal scrolling optimizer, a few pages of Gosling's code which was proceeded by a comment with a skull and crossbones, meaning that it was so hard to understand that it was poison. I had to replace it, but worried that the job would be hard. I found a simpler algorithm and got it to work in a few hours, producing code that was shorter, faster, clearer, and more extensible. Then I made it use the terminal commands to insert or delete multiple lines as a single operation, which made screen updating far more efficient.
There's some more discussion about it here that ended up being pretty accurate once all was said and done:
https://www.reddit.com/r/emacs/comments/bek5b2/til_emacs_was...
Emacs's infamous "Ultra-hot screen management package" with its "Skull and Crossbones" warning was definitely black magic!
The algorithm worked great and was well worth it over a 300 / 1200 / 2400 baud connection to a Vax 780 / 750 / etc, and as modems and computers got faster it was still useful, but at today's network bandwidths and cpu speeds it's thunderous overkill.
https://news.ycombinator.com/item?id=38996713
A redisplay algorithm, by James Gosling (ACM SIGPLAN Notices, April 1981):
https://donhopkins.com/home/documents/EmacsRedisplayAlgorith...
>7. Acknowledgements: The people who did the real work behind this paper are Mike Kazar, Charles Liescrson and Craig Everhart; all from CMU.
>Bibliography: 1. Kevin Q. Brown. Dynamic Programming in Computer Science. CMU, February, 1979.
That code was also used in Maryland Windows (a text based overlapping/tiled window system developed at the University of Maryland by Chris Torek, like Emacs - Text Editor + Window System, kind of like "screen" or "mux" or "mgr").
https://donhopkins.com/home/archive/emacs/mw/display.c
https://en.wikipedia.org/wiki/Dynamic_programming
https://wiki.c2.com/?DynamicProgramming
https://en.wikipedia.org/wiki/ManaGeR
https://news.ycombinator.com/item?id=22849522
>Gosling Emacs was especially noteworthy because of the effective redisplay code, which used a dynamic programming technique to solve the classical string-to-string correction problem. The algorithm was quite sophisticated; that section of the source was headed by a skull-and-crossbones in ASCII art, warning any would-be improver that even if they thought they understood how the display code worked, they probably did not.
https://donhopkins.com/home/archive/emacs/mw/display.c
Trivia: That "Skull and Crossbones" ASCII art is originally from Brian Reid's Scribe program, and is not copyrighted.https://donhopkins.com/home/archive/emacs/skull-and-crossbon...
But if you're not trying to support old terminals (but might still have a slow "thin wire" network connection), there is an orders of magnitude better approach: The Emacs NeWS display driver (for both UniPress and Gnu Emacs) downloaded PostScript code to define an efficient application specific network protocol with instantaneous local input tracking and feedback (unlike how X-Windows uses a fixed protocol, but like how AJAX uses JavaScript).The source code to Gosling's UniPress Emacs 2.20 just recently surfaced, and the display code is well commented (still including the skull and crossbones and ascii art diagrams):
https://github.com/SimHacker/NeMACS/blob/main/src/DspVScreen...
And the lower level terminal driver layer:
https://github.com/SimHacker/NeMACS/blob/main/src/DspTrm.c
The NeWS terminal drivers I worked on for UniPress and Gnu Emacs were layered on top of that dynamic programming screen update code. But instead of sending escape codes to a dumb terminal, it downloaded PostScript code into the NeWS server to implement drawing, mouse tracking, text selection feedback, pie menus, tabbed windows, etc, and sent binary PostScript tokens back and forth (a practice now called "AJAX" for X = XML or JSON text instead of binary PostScript data and code):
TrmPS.c: https://github.com/SimHacker/NeMACS/blob/main/src/D.term/Trm...
TrmPS.cps: https://github.com/SimHacker/NeMACS/blob/main/src/D.term/Trm...
PostScript stuff for Emacs: https://github.com/SimHacker/NeMACS/tree/main/ps
Emacs 2.20 Demo (NeWS, multiple frames, tabbed windows, pie menus, hypermedia authoring):
https://www.youtube.com/watch?v=hhmU2B79EDU
Here's a brochure from February 1988 about UniPress Emacs 2.20 and "SoftWire" (NeWS without graphics, kind of like Node with PostScript instead of JavaScript).
What is Emacs: https://www.donhopkins.com/home/ties/scans/WhatIsEmacs.pdf
I also worked on the Gnu Emacs 18 NeWS display driver (supporting a single tabbed windows and pie menus in The NeWS Toolkit 2.0):
tnt.ps: https://www.donhopkins.com/home/code/emacs18/src/tnt.ps
tnt.cps: https://www.donhopkins.com/home/code/emacs18/src/tnt_cps.cps
tnt.c: https://www.donhopkins.com/home/code/emacs18/src/tnt.c
tnt-win.el: https://www.donhopkins.com/home/code/emacs18/lisp/term/tnt-w...
More on the NeWS versions of Emacs with links to code here:
https://news.ycombinator.com/item?id=26113192