Re:Dynamic Programming: The Name (1984)
by DonHopkins on Monday September 12, 2016 @06:25AM
(#12478478)
James Gosling published a 1981 SIGPLAN paper titled "A Redisplay Algorithm" [1], that used dynamic programming to solve the string to string correction problem [2], which he implemented in Gosling Emacs [3].
>Wikipedia: "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 [4], warning would-be improver that even if they thought they understood how the display code worked, they probably did not."
>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."
In essence, it finds the shortest path through a twisty little maze of text and terminal escape code sequences (so different terminals would have different optimal routes to updating the display, depending on what was already on the screen, the length of their escape sequences, if they supported features like character/line insert/delete, cleol, extra padding for slow terminals and commands, etc).
>Wikipedia: "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 [4], warning would-be improver that even if they thought they understood how the display code worked, they probably did not."
>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."
In essence, it finds the shortest path through a twisty little maze of text and terminal escape code sequences (so different terminals would have different optimal routes to updating the display, depending on what was already on the screen, the length of their escape sequences, if they supported features like character/line insert/delete, cleol, extra padding for slow terminals and commands, etc).
[1] http://dl.acm.org/citation.cfm?id=806463
[2] https://en.wikipedia.org/wiki/String-to-string_correction_pr...
[3] https://en.wikipedia.org/wiki/Gosling_Emacs
[4] http://donhopkins.com/home/archive/emacs/skull-and-crossbone...