5 ms·

I meant that in a different way. The psterm code wasn’t bad or hard to understand (although I only skimmed it, and did see some things I would have done differe

by db48x 3y ago

I meant that in a different way. The psterm code wasn’t bad or hard to understand (although I only skimmed it, and did see some things I would have done differently). What I meant is that it’s literally backwards. It’s going up the down slide.

DonHopkins 3y ago
That's to match impedance with the display drawing and input handling code, which is written in reverse polish notation stack based PostScript, which is going back the forward side. psterm.ps: https://donhopkins.com/home/archive/NeWS/news-tape/applications/psterm/psterm.ps https://donhopkins.com/home/archive/NeWS/news-tape/applicati... tcap.cps: https://donhopkins.com/home/archive/NeWS/news-tape/applications/psterm/tcap.cps https://donhopkins.com/home/archive/NeWS/news-tape/applicati... sampl.user.ps: https://donhopkins.com/home/archive/NeWS/news-tape/applications/psterm/sampl.user.ps https://donhopkins.com/home/archive/NeWS/news-tape/applicati... UsingPSTerm: https://donhopkins.com/home/archive/NeWS/news-tape/applications/psterm/UsingPSTerm https://donhopkins.com/home/archive/NeWS/news-tape/applicati... It's still a much better more flexible approach than xterm, since it can emulate any terminal type, and even if the termcap entry is incorrect and not faithful to the actual terminal, it still works. In fact you can even make up a termcap entry with your own custom sets of fictional/virtual (but efficient) terminal escape sequences, or mix and match different terminals (like adding reverse and bold text, or line/char insert/delete, to a terminal type that doesn't support it), and it still works perfectly. https://donhopkins.com/home/archive/NeWS/news-tape/applications/psterm/psterm.tinfo https://donhopkins.com/home/archive/NeWS/news-tape/applicati... # This is a faster termcap for psterm, Warning: if you use this termcap # some control characters you type will do strange things to the screen # on systems that echo typed control characters to the users terminal. psterm-fast, am, km, hs, cols#80, lines#34, bel=^G, cr=\r, csr=^E%p1%d;%p2%d;, clear=\f, el=^C, ed=^B, cup=^D%p1%d;%p2%d;, cud1=^P, home=^R, cub1=^T, cuf1=^V, ll=^U, cuu1=^Y, dch1=^F, dl1=^K, blink=^Ob, bold=^Od, smcup=^Ot, smir=^Oi, rev=^Or, smso=^Oo, smul=^Ou, sgr0=^N*, rmcup=^Nt, rmir=^Ni, rmso=^No, rmul=^Nu, flash=^Z, fsl=^Nl, is1=^N*, il1=^A, kbs=\b, kcud1=\E[B, kcub1=\E[D, kcuf1=\E[C, kcuu1=\E[A, nel=\r\n, rs1=^N*, rc=^\, sc=^], ind=^W, ri=^X, ht=\t, tsl=^Ol, I don't understand why it's better to emulate only one fixed terminal type (especially the verbose anathema that's vt100), since you might encounter programs or operating systems that don't support vt100 or whatever you chose to emulate, don't respect termcap, and might use any other fixed set of escape sequences, which psterm can easily handle. Even if you encounter a program that requires a totally new terminal you've never seen, you can easily write a termcap entry for it, and psterm will emulate it without any changes. Why rewrite a bunch of other programs, or a bunch of other terminal emulators, when one terminal emulator can easily adapt to them all? In 1988 when psterm was written there were many different programs and operating systems and terminals like that, especially since terminals can talk to other operating systems than unix that don't support termcap, via telnet or serial ports and modems. It wasn't anything like the stagnant linux/xterm/vt100 monoculture we have today. And if you're going to standardize on one terminal, the vt100's one of the worst you could possibly chose! That's kind of the whole point of a terminal emulator: to emulate terminals, so the more the merrier! The idea of virtualizing terminal protocols has been around for a long time, like Marc Crispin's SUPDUP Display Protocol for ITS and Lisp Machines (RFC734 from 1977), and ITS's CRTSTY virtual terminal emulator (kind of like "screen" for translating virtual to actual terminal sequences for many terminal types, adapting dumb terminals without line/char insert/delete, supporting redisplay for low baud rates or congested ARPA connections, and keeping your session and jobs alive if you disconnect, so you can continue after you reconnect, even with a different terminal type, if you got kicked off a nice AAA and forced to use a shitty VT52). http://junk.nocrew.org/pipermail/its/1988-September/002005.html http://junk.nocrew.org/pipermail/its/1988-September/002005.h... https://github.com/PDP-10/its/blob/master/doc/sysdoc/itstty.41 https://github.com/PDP-10/its/blob/master/doc/sysdoc/itstty.... >This file describes just about all there is to know about using and programming TTYs (abbreviation for "Teletypes", for which read "consoles") on the ITS operating system. https://datatracker.ietf.org/doc/rfc734/ https://datatracker.ietf.org/doc/rfc734/ >NWG/RFC# 734 MRC 07-OCT-77 08:46 41953 SUPDUP Display Protocol Page 1 Network Working Group Mark Crispin Request for Comments 734 SU-AI NIC 41953 7 October 1977 >SUPDUP Protocol >This document describes the SUPDUP protocol, a highly efficient display telnet protocol. It originally started as a private protocol between the ITS systems at MIT to allow a user at any one of these systems to use one of the others as a display. At the current writing, SUPDUP user programs also exist for Data Disc and Datamedia displays at SU-AI and for Datamedias at SRI-KL. The author is not aware of any SUPDUP servers other than at the four MIT ITS sites. >The advantage of the SUPDUP protocol over an individual terminal's protocol is that SUPDUP defines a "virtual" or "software" display terminal that implements relevant cursor motion operations. The protocol is not built on any particular display terminal but rather on the set of functions common to all display terminals; hence it is completely device- independent. In addition, the protocol also provides for terminals which cannot handle certain operations, such as line or character insert/delete. In fact, it is more than this. It provides for terminals which are missing any set of features, all the way down to model 33 Teletypes. >The advantage over the TELNET protocol is that SUPDUP takes advantage of the full capabilities of display terminals, although it also has the ability to run printing terminals. https://its.victor.se/wiki/_media/ai_wp_235.pdf https://its.victor.se/wiki/_media/ai_wp_235.pdf >The SUPDUP protocol [Crispin 77] is a highly efficient display telnet protocol. The advantage over the TELNET protocol is that SUPDUP takes advantage of the full capabilities of display terminals, although it also has the ability to run printing terminals. When you use the SUPDUP protocol, you do not need to tell the remote host which you are connecting to what type of terminal you have or what the terminal's capabilities are. The host you are SUPDUPing from handles the actual display support for your terminal. >Additionally, SUPDUP defines a network graphics protpcol [Stallman 78] which makes it easy for network hosts to draw pictures along in addition to text. I even wrote a SUPDUP emulator in FORTH and RPN 6502 assembly, which is about as backwards and upside-down as it gets -- this code also supports the SUPDUP line saving extensions that RMS hacked into ITS Emacs, so it can stash lines on the screen in local memory before overpainting them, then almost instantly pop them back on the screen later, so you can scroll back and forth through text really fast at 300 baud (plus Devon McCullough made ZipMod with Huffman encoding to make it even faster on top of that): https://donhopkins.com/home/archive/forth/supdup.f https://donhopkins.com/home/archive/forth/supdup.f HEX CREATE SETUP-LINE ASSEMBLER BOT LDA, N STA, BOT 1+ LDA, N 1+ STA, BOT 2+ LDY, SCR-LBASES ,Y LDA, N 2+ STA, SCR-HBASES ,Y LDA, N 3 + STA, SCR-WIDTH 1- # LDY, RTS, At 300 baud over a congested ARPA connection, we had a lot of time to think about how to optimize terminal emulation while waiting for the screen to repaint... And just what's wrong with backwards and upside-down algorithms that solve problems in ways that forward and rightside-up algorithms can't? That's how Emacs's infamous screen redisplay algorithm (and many other common algorithms like pathfinding in games and route planning in cars) work: recursively flood filling forward then navigating backwards from the goal to the current position at the minimal cost, through a matrix or maze of different possible alternative escape sequences and drawing operations or roads with different costs, to find the optimal shortest possible route. At 300 baud or even 1200 baud, and even on a busy Vax 11/750, there's a lot of time between each character for Emacs to think about what text and escape sequences to send next. And of course Emacs's screen update algorithm would automatically take into account and use the short optimized custom control codes defined in the psterm-fast termcap entry, to be much more efficient that the verbose inefficient vt100 codes. Read the paper and display.c code I linked to, and see the wikipedia page on dynamic programming: >James Gosling's Emacs screen redisplay algorithm also used similar "dynamic programming techniques" to compute 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). https://en.wikipedia.org/wiki/Gosling_Emacs https://en.wikipedia.org/wiki/Gosling_Emacs >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/skull-and-crossbones.txt https://donhopkins.com/home/archive/emacs/skull-and-crossbon... >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/mw/display.c https://donhopkins.com/home/archive/emacs/mw/display.c /* 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) */ https://donhopkins.com/home/documents/EmacsRedisplayAlgorithm.pdf https://donhopkins.com/home/documents/EmacsRedisplayAlgorith... https://dl.acm.org/doi/10.1145/1159890.806463 https://dl.acm.org/doi/10.1145/1159890.806463 >A redisplay algorithm, by James Gosling. >Abstract >This paper presents an algorithm for updating the image displayed on a conventional video terminal. It assumes that the terminal is capable of doing the usual insert/delete line and insert/delete character operations. It takes as input a description of the image currently on the screen and a description of the new image desired and produces a series of operations to do the desired transformation in a near-optimal manner. The algorithm is interesting because it applies results from the theoretical string-to-string correction problem (a generalization of the problem of finding a longest common subsequence), to a problem that is usually approached with crude ad-hoc techniques. [...] >6. Conclusion >The redisplay algorithm described in this paper is used in an Emacs-like editor for Unix and a structure editor. It's performance has been quite good: to redraw everything on the screen (when everything has changed) takes about 0.12 seconds CPU time on a VAX 11/780 running Unix. Using the standard file typing program, about 0.025 seconds of CPU time are needed to type one screenful of text. Emacs averages about 0.004 CPU seconds per keystroke (with one call on the redisplay per keystroke). >Although in the interests of efficency we have stripped down algorithm 5 to algorithm 6 the result is still an algorithm which has a firm theoretical basis and which is superior to the usual ad-hoc approach. https://en.wikipedia.org/wiki/Dynamic_programming https://en.wikipedia.org/wiki/Dynamic_programming >Dynamic programming >Figure 1. Finding the shortest path in a graph using optimal substructure; a straight line indicates a single edge; a wavy line indicates a shortest path between the two vertices it connects (among other paths, not shown, sharing the same two vertices); the bold line is the overall shortest path from start to goal. >Dynamic programming is both a mathematical optimization method and an algorithmic paradigm. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics. >In both contexts it refers to simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner. While some decision problems cannot be taken apart this way, decisions that span several points in time do often break apart recursively. Likewise, in computer science, if a problem can be solved optimally by breaking it into sub-problems and then recursively finding the optimal solutions to the sub-problems, then it is said to have optimal substructure. >If sub-problems can be nested recursively inside larger problems, so that dynamic programming methods are applicable, then there is a relation between the value of the larger problem and the values of the sub-problems.[1] In the optimization literature this relationship is called the Bellman equation.
- DonHopkins 3y ago
  The comments in this old PDP-10 SUPDUP code [5] are hilarious! SUPDUP on ITS was so smart and opinionated, it had its own ideas about who was a loser and who was a winner, how to figure it out by checking INQUIR entries and relationships, and who it should never or always hassle about net-hopping (hopping through a PDP-10 over the net just to use it as a glorified terminal emulator). It never hassled gumby or cstacy (because they were free to do whatever they wanted to, like flushing whiny annoying over-entitled alcoholic science fiction writers [1] [2] [3] [4]), but always hassled rms (because it was usually an imposter logging in as rms with password rms just to net hop through the system.) [1] http://www.stormtiger.org/bob/humor/pournell/story.html http://www.stormtiger.org/bob/humor/pournell/story.html [2] https://news.ycombinator.com/item?id=15206151 https://news.ycombinator.com/item?id=15206151 [3] https://news.ycombinator.com/item?id=37723853 https://news.ycombinator.com/item?id=37723853 [4] https://news.ycombinator.com/item?id=37780515 https://news.ycombinator.com/item?id=37780515 [5] https://github.com/PDP-10/its/blob/master/src/sysnet/supdup.325#L903 https://github.com/PDP-10/its/blob/master/src/sysnet/supdup.... subttl LSRCHK and LSRWRN -- see if user is loser ;;; This checks to see if the loser is an AI or LCS member or on a ;;; winners list. If not, a warning net-hopping message is printed ;;; and the program offers to kill itself off. ;;; The winner-p check has been extracted so that if at some point in ;;; the future this program is modified to check if it's running from ;;; a CRTSTY, those people may not be warned. ;;; If you mung this you might wish to mung CHTN similarly. ;;; skips unless the luser should be warned. lsrchk: pushj p,winchk ;are they a winner? skipa ;nope jrst popj1 ;yea; so skip ;; check to see if they're in loser table move t,[-loslen,,lostab] ;; winchk left xuname in tt lsloop: camn tt,(t) popj p, ;loser -> don't skip aobjn t,lsloop ;; check inquir entry movei a,filech move b,[-lsrpgs,,hstpag];map lsr where host table will be pushj p,lsrtns"lsrmap jrst lsrlos ;something wrong; print loser message .suset [.rxuname,,b] ;xuname into b pushj p,lsrtns"lsrunm ;find our entry in database jrst lsrlos ;no inquir entry; must be loser .close filech, ;close lsr file movei a,lsrtns"i$grp ;we want to check group pushj p,lsrtns"lsritm popj p, ;none means guest ildb a,a ;get field caie a,"A ; AI lab cain a,"L ; LCS jrst lsloo1 caie a,"V ; NIL group cain a,"Z ; Clinical Decision Making jrst lsloo1 caie a,"C ; Theory of Computation popj p, ;they're not a lab member lsloo1: movei a,lsrtns"i$rel ;Check relationship pushj p,lsrtns"lsritm popj p, ;none means loser ildb a,a ;get field caie a,"X ;some losers put AX when they mean XA ;; These names are for NETWRK popj1: aos (p) ;otherwise skip cpopj: popj p, ;when returning lsrlos: .close filech, ;close lsr file popj p, ;don't skip ;;; Skip means these people know what they're doing; don't hassle them winchk: .suset [.rxuname,,tt] move t,[-winlen,,wintab] wnloop: camn tt,(t) jrst popj1 ;winner; skip aobjn t,wnloop popj p, ;;; these people aren't hassled wintab: irp x,,[gumby,alan,cstacy,cent,devon,dph,oaf,mly,jtw,jnc,klotz,cbf,sra,ed,swa,map,jbvb] sixbit/x/ termin winlen==.-wintab ;;; These people are always hassled lostab: irp x,,[tk,hewitt,rms] sixbit/x/ termin loslen==.-lostab ;;; warn loser that net-hopping is a waste of the machine lsrwrn: movei tt,[asciz/ Using this machine to access another will needlessly drain resources, slowing the system both for you and other users. You'll probably get better response by connecting directly. You should not do this unless you have a good reason to do so. If you have any questions, typing :LUSER to DDT will request a system programmer to assist you. Are you sure you want to net-hop?/] pushj p,outstr $call iot,[#ttyich,a],[#%tinwt] ;Wait for character .lose %lssys caie a,"y cain a,"Y popj p, ;it was a Y caie a,40 ;maybe it was a space? .logout 1, popj p,

by db48x 3y ago

DonHopkins 3y ago

That's to match impedance with the display drawing and input handling code, which is written in reverse polish notation stack based PostScript, which is going back the forward side. psterm.ps: https://donhopkins.com/home/archive/NeWS/news-tape/applications/psterm/psterm.ps https://donhopkins.com/home/archive/NeWS/news-tape/applicati... tcap.cps: https://donhopkins.com/home/archive/NeWS/news-tape/applications/psterm/tcap.cps https://donhopkins.com/home/archive/NeWS/news-tape/applicati... sampl.user.ps: https://donhopkins.com/home/archive/NeWS/news-tape/applications/psterm/sampl.user.ps https://donhopkins.com/home/archive/NeWS/news-tape/applicati... UsingPSTerm: https://donhopkins.com/home/archive/NeWS/news-tape/applications/psterm/UsingPSTerm https://donhopkins.com/home/archive/NeWS/news-tape/applicati... It's still a much better more flexible approach than xterm, since it can emulate any terminal type, and even if the termcap entry is incorrect and not faithful to the actual terminal, it still works. In fact you can even make up a termcap entry with your own custom sets of fictional/virtual (but efficient) terminal escape sequences, or mix and match different terminals (like adding reverse and bold text, or line/char insert/delete, to a terminal type that doesn't support it), and it still works perfectly. https://donhopkins.com/home/archive/NeWS/news-tape/applications/psterm/psterm.tinfo https://donhopkins.com/home/archive/NeWS/news-tape/applicati... # This is a faster termcap for psterm, Warning: if you use this termcap # some control characters you type will do strange things to the screen # on systems that echo typed control characters to the users terminal. psterm-fast, am, km, hs, cols#80, lines#34, bel=^G, cr=\r, csr=^E%p1%d;%p2%d;, clear=\f, el=^C, ed=^B, cup=^D%p1%d;%p2%d;, cud1=^P, home=^R, cub1=^T, cuf1=^V, ll=^U, cuu1=^Y, dch1=^F, dl1=^K, blink=^Ob, bold=^Od, smcup=^Ot, smir=^Oi, rev=^Or, smso=^Oo, smul=^Ou, sgr0=^N*, rmcup=^Nt, rmir=^Ni, rmso=^No, rmul=^Nu, flash=^Z, fsl=^Nl, is1=^N*, il1=^A, kbs=\b, kcud1=\E[B, kcub1=\E[D, kcuf1=\E[C, kcuu1=\E[A, nel=\r\n, rs1=^N*, rc=^\, sc=^], ind=^W, ri=^X, ht=\t, tsl=^Ol, I don't understand why it's better to emulate only one fixed terminal type (especially the verbose anathema that's vt100), since you might encounter programs or operating systems that don't support vt100 or whatever you chose to emulate, don't respect termcap, and might use any other fixed set of escape sequences, which psterm can easily handle. Even if you encounter a program that requires a totally new terminal you've never seen, you can easily write a termcap entry for it, and psterm will emulate it without any changes. Why rewrite a bunch of other programs, or a bunch of other terminal emulators, when one terminal emulator can easily adapt to them all? In 1988 when psterm was written there were many different programs and operating systems and terminals like that, especially since terminals can talk to other operating systems than unix that don't support termcap, via telnet or serial ports and modems. It wasn't anything like the stagnant linux/xterm/vt100 monoculture we have today. And if you're going to standardize on one terminal, the vt100's one of the worst you could possibly chose! That's kind of the whole point of a terminal emulator: to emulate terminals, so the more the merrier! The idea of virtualizing terminal protocols has been around for a long time, like Marc Crispin's SUPDUP Display Protocol for ITS and Lisp Machines (RFC734 from 1977), and ITS's CRTSTY virtual terminal emulator (kind of like "screen" for translating virtual to actual terminal sequences for many terminal types, adapting dumb terminals without line/char insert/delete, supporting redisplay for low baud rates or congested ARPA connections, and keeping your session and jobs alive if you disconnect, so you can continue after you reconnect, even with a different terminal type, if you got kicked off a nice AAA and forced to use a shitty VT52). http://junk.nocrew.org/pipermail/its/1988-September/002005.html http://junk.nocrew.org/pipermail/its/1988-September/002005.h... https://github.com/PDP-10/its/blob/master/doc/sysdoc/itstty.41 https://github.com/PDP-10/its/blob/master/doc/sysdoc/itstty.... >This file describes just about all there is to know about using and programming TTYs (abbreviation for "Teletypes", for which read "consoles") on the ITS operating system. https://datatracker.ietf.org/doc/rfc734/ https://datatracker.ietf.org/doc/rfc734/ >NWG/RFC# 734 MRC 07-OCT-77 08:46 41953 SUPDUP Display Protocol Page 1 Network Working Group Mark Crispin Request for Comments 734 SU-AI NIC 41953 7 October 1977 >SUPDUP Protocol >This document describes the SUPDUP protocol, a highly efficient display telnet protocol. It originally started as a private protocol between the ITS systems at MIT to allow a user at any one of these systems to use one of the others as a display. At the current writing, SUPDUP user programs also exist for Data Disc and Datamedia displays at SU-AI and for Datamedias at SRI-KL. The author is not aware of any SUPDUP servers other than at the four MIT ITS sites. >The advantage of the SUPDUP protocol over an individual terminal's protocol is that SUPDUP defines a "virtual" or "software" display terminal that implements relevant cursor motion operations. The protocol is not built on any particular display terminal but rather on the set of functions common to all display terminals; hence it is completely device- independent. In addition, the protocol also provides for terminals which cannot handle certain operations, such as line or character insert/delete. In fact, it is more than this. It provides for terminals which are missing any set of features, all the way down to model 33 Teletypes. >The advantage over the TELNET protocol is that SUPDUP takes advantage of the full capabilities of display terminals, although it also has the ability to run printing terminals. https://its.victor.se/wiki/_media/ai_wp_235.pdf https://its.victor.se/wiki/_media/ai_wp_235.pdf >The SUPDUP protocol [Crispin 77] is a highly efficient display telnet protocol. The advantage over the TELNET protocol is that SUPDUP takes advantage of the full capabilities of display terminals, although it also has the ability to run printing terminals. When you use the SUPDUP protocol, you do not need to tell the remote host which you are connecting to what type of terminal you have or what the terminal's capabilities are. The host you are SUPDUPing from handles the actual display support for your terminal. >Additionally, SUPDUP defines a network graphics protpcol [Stallman 78] which makes it easy for network hosts to draw pictures along in addition to text. I even wrote a SUPDUP emulator in FORTH and RPN 6502 assembly, which is about as backwards and upside-down as it gets -- this code also supports the SUPDUP line saving extensions that RMS hacked into ITS Emacs, so it can stash lines on the screen in local memory before overpainting them, then almost instantly pop them back on the screen later, so you can scroll back and forth through text really fast at 300 baud (plus Devon McCullough made ZipMod with Huffman encoding to make it even faster on top of that): https://donhopkins.com/home/archive/forth/supdup.f https://donhopkins.com/home/archive/forth/supdup.f HEX CREATE SETUP-LINE ASSEMBLER BOT LDA, N STA, BOT 1+ LDA, N 1+ STA, BOT 2+ LDY, SCR-LBASES ,Y LDA, N 2+ STA, SCR-HBASES ,Y LDA, N 3 + STA, SCR-WIDTH 1- # LDY, RTS, At 300 baud over a congested ARPA connection, we had a lot of time to think about how to optimize terminal emulation while waiting for the screen to repaint... And just what's wrong with backwards and upside-down algorithms that solve problems in ways that forward and rightside-up algorithms can't? That's how Emacs's infamous screen redisplay algorithm (and many other common algorithms like pathfinding in games and route planning in cars) work: recursively flood filling forward then navigating backwards from the goal to the current position at the minimal cost, through a matrix or maze of different possible alternative escape sequences and drawing operations or roads with different costs, to find the optimal shortest possible route. At 300 baud or even 1200 baud, and even on a busy Vax 11/750, there's a lot of time between each character for Emacs to think about what text and escape sequences to send next. And of course Emacs's screen update algorithm would automatically take into account and use the short optimized custom control codes defined in the psterm-fast termcap entry, to be much more efficient that the verbose inefficient vt100 codes. Read the paper and display.c code I linked to, and see the wikipedia page on dynamic programming: >James Gosling's Emacs screen redisplay algorithm also used similar "dynamic programming techniques" to compute 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). https://en.wikipedia.org/wiki/Gosling_Emacs https://en.wikipedia.org/wiki/Gosling_Emacs >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/skull-and-crossbones.txt https://donhopkins.com/home/archive/emacs/skull-and-crossbon... >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/mw/display.c https://donhopkins.com/home/archive/emacs/mw/display.c /* 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) */ https://donhopkins.com/home/documents/EmacsRedisplayAlgorithm.pdf https://donhopkins.com/home/documents/EmacsRedisplayAlgorith... https://dl.acm.org/doi/10.1145/1159890.806463 https://dl.acm.org/doi/10.1145/1159890.806463 >A redisplay algorithm, by James Gosling. >Abstract >This paper presents an algorithm for updating the image displayed on a conventional video terminal. It assumes that the terminal is capable of doing the usual insert/delete line and insert/delete character operations. It takes as input a description of the image currently on the screen and a description of the new image desired and produces a series of operations to do the desired transformation in a near-optimal manner. The algorithm is interesting because it applies results from the theoretical string-to-string correction problem (a generalization of the problem of finding a longest common subsequence), to a problem that is usually approached with crude ad-hoc techniques. [...] >6. Conclusion >The redisplay algorithm described in this paper is used in an Emacs-like editor for Unix and a structure editor. It's performance has been quite good: to redraw everything on the screen (when everything has changed) takes about 0.12 seconds CPU time on a VAX 11/780 running Unix. Using the standard file typing program, about 0.025 seconds of CPU time are needed to type one screenful of text. Emacs averages about 0.004 CPU seconds per keystroke (with one call on the redisplay per keystroke). >Although in the interests of efficency we have stripped down algorithm 5 to algorithm 6 the result is still an algorithm which has a firm theoretical basis and which is superior to the usual ad-hoc approach. https://en.wikipedia.org/wiki/Dynamic_programming https://en.wikipedia.org/wiki/Dynamic_programming >Dynamic programming >Figure 1. Finding the shortest path in a graph using optimal substructure; a straight line indicates a single edge; a wavy line indicates a shortest path between the two vertices it connects (among other paths, not shown, sharing the same two vertices); the bold line is the overall shortest path from start to goal. >Dynamic programming is both a mathematical optimization method and an algorithmic paradigm. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics. >In both contexts it refers to simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner. While some decision problems cannot be taken apart this way, decisions that span several points in time do often break apart recursively. Likewise, in computer science, if a problem can be solved optimally by breaking it into sub-problems and then recursively finding the optimal solutions to the sub-problems, then it is said to have optimal substructure. >If sub-problems can be nested recursively inside larger problems, so that dynamic programming methods are applicable, then there is a relation between the value of the larger problem and the values of the sub-problems.[1] In the optimization literature this relationship is called the Bellman equation.

DonHopkins 3y ago
The comments in this old PDP-10 SUPDUP code [5] are hilarious! SUPDUP on ITS was so smart and opinionated, it had its own ideas about who was a loser and who was a winner, how to figure it out by checking INQUIR entries and relationships, and who it should never or always hassle about net-hopping (hopping through a PDP-10 over the net just to use it as a glorified terminal emulator). It never hassled gumby or cstacy (because they were free to do whatever they wanted to, like flushing whiny annoying over-entitled alcoholic science fiction writers [1] [2] [3] [4]), but always hassled rms (because it was usually an imposter logging in as rms with password rms just to net hop through the system.) [1] http://www.stormtiger.org/bob/humor/pournell/story.html http://www.stormtiger.org/bob/humor/pournell/story.html [2] https://news.ycombinator.com/item?id=15206151 https://news.ycombinator.com/item?id=15206151 [3] https://news.ycombinator.com/item?id=37723853 https://news.ycombinator.com/item?id=37723853 [4] https://news.ycombinator.com/item?id=37780515 https://news.ycombinator.com/item?id=37780515 [5] https://github.com/PDP-10/its/blob/master/src/sysnet/supdup.325#L903 https://github.com/PDP-10/its/blob/master/src/sysnet/supdup.... subttl LSRCHK and LSRWRN -- see if user is loser ;;; This checks to see if the loser is an AI or LCS member or on a ;;; winners list. If not, a warning net-hopping message is printed ;;; and the program offers to kill itself off. ;;; The winner-p check has been extracted so that if at some point in ;;; the future this program is modified to check if it's running from ;;; a CRTSTY, those people may not be warned. ;;; If you mung this you might wish to mung CHTN similarly. ;;; skips unless the luser should be warned. lsrchk: pushj p,winchk ;are they a winner? skipa ;nope jrst popj1 ;yea; so skip ;; check to see if they're in loser table move t,[-loslen,,lostab] ;; winchk left xuname in tt lsloop: camn tt,(t) popj p, ;loser -> don't skip aobjn t,lsloop ;; check inquir entry movei a,filech move b,[-lsrpgs,,hstpag];map lsr where host table will be pushj p,lsrtns"lsrmap jrst lsrlos ;something wrong; print loser message .suset [.rxuname,,b] ;xuname into b pushj p,lsrtns"lsrunm ;find our entry in database jrst lsrlos ;no inquir entry; must be loser .close filech, ;close lsr file movei a,lsrtns"i$grp ;we want to check group pushj p,lsrtns"lsritm popj p, ;none means guest ildb a,a ;get field caie a,"A ; AI lab cain a,"L ; LCS jrst lsloo1 caie a,"V ; NIL group cain a,"Z ; Clinical Decision Making jrst lsloo1 caie a,"C ; Theory of Computation popj p, ;they're not a lab member lsloo1: movei a,lsrtns"i$rel ;Check relationship pushj p,lsrtns"lsritm popj p, ;none means loser ildb a,a ;get field caie a,"X ;some losers put AX when they mean XA ;; These names are for NETWRK popj1: aos (p) ;otherwise skip cpopj: popj p, ;when returning lsrlos: .close filech, ;close lsr file popj p, ;don't skip ;;; Skip means these people know what they're doing; don't hassle them winchk: .suset [.rxuname,,tt] move t,[-winlen,,wintab] wnloop: camn tt,(t) jrst popj1 ;winner; skip aobjn t,wnloop popj p, ;;; these people aren't hassled wintab: irp x,,[gumby,alan,cstacy,cent,devon,dph,oaf,mly,jtw,jnc,klotz,cbf,sra,ed,swa,map,jbvb] sixbit/x/ termin winlen==.-wintab ;;; These people are always hassled lostab: irp x,,[tk,hewitt,rms] sixbit/x/ termin loslen==.-lostab ;;; warn loser that net-hopping is a waste of the machine lsrwrn: movei tt,[asciz/ Using this machine to access another will needlessly drain resources, slowing the system both for you and other users. You'll probably get better response by connecting directly. You should not do this unless you have a good reason to do so. If you have any questions, typing :LUSER to DDT will request a system programmer to assist you. Are you sure you want to net-hop?/] pushj p,outstr $call iot,[#ttyich,a],[#%tinwt] ;Wait for character .lose %lssys caie a,"y cain a,"Y popj p, ;it was a Y caie a,40 ;maybe it was a space? .logout 1, popj p,