Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #403298

Re: Editor design & Buffer Gap

Cross-posted to 2 groups.

Show all headers | View raw

In article <11b25hh$11ann$1@dont-email.me>,
Anthony Howe  <achowe@snert.com> wrote:
>On 2026-10-12 17:42, steve g wrote:
>> Anthony Howe <achowe@snert.com> writes:
>>> The designing the edit engine is what fascinates me, regardless of UI.  Pity
>>> there are few discussions any more around this topic.
>> 
>> I agree. I would love to play with a redisplay engine. let alone read
>> more about them. I usually just read some old pascal books from the
>> 1990s. I would love to reimplement lotus style menus !
>
>Redisplay in text, you thinking Curses/NCurses?
>
>Curses was designed to abstract the assorted video terminals of the day (now 
>everything is an VT100/ANSI derivative) and to optimise the sending of minimal 
>sequences of escape codes to a **serial terminal** (or terminal emulator) to 
>update the screen.
>
>There used to be BSD Curses, Solaris Curses, System V Curses, pdcurses, (and 
>Mortice Kern Systems (MKS) Curses).  X/Open (now SUS) created a standard for 
>Curses that brought together the minor difference into one.  NCurses (written in 
>C++) was starting around the time of POSIX.2, X/Open, and Unicode standards and 
>hasn't change much since and is stable.  SUS has Curses Issue 7 which clarifies 
>the text.

Eh?  I'm pretty sure `ncurses` is in C.

>Terminal Difference algorithms are related to Edit Distance / Longest Common 
>Subsequence algorithms - think `diff(1)`.  There is a paper from Bill Joy on 
>Curses and some other papers related to terminal Edit Distance/LCS I obtained 
>when working on MKS Curses (buried on my book shelf).

Really?  I know James Gosling wrote a paper on optimizing edit
distances applied to screen updates where he presented a dynamic
programming algorithm that ran in O(n^2) time.  It was pretty
nifty, and caused a kerfuffle when Stallman put it into GNU
emacs.  https://dl.acm.org/doi/abs/10.1145/800209.806463

Ken Arnold wrote the paper on Curses, but didn't really get into
the details of the implementation; he does credit Joy with the
display code, which he ripped out of `vi`.  Mary Ann Horton did
a better algorithm at AT&T, and left a description of it on a
park bench on day, from where it subsequently made it into
pcurses.

>There are books "Software Tools in PASCAL" by Kernigan & Plauger ISBN 
>0-201-103342-7 and "A Software Tools Sampler" by Web Miller ISBN 0-13-822305-X 
>that cover editors.  The latter also covers terminal updating for an editor 
>(Edit Distance/LCS).  See also `diff(1)` and my IOCCC 2015 `npdif(1)` also cover 
>Edit Distance/LCS (I supply several References in the documentation to papers).

Webb Miller wrote several papers on this, which are interesting;
he observed that Gosling's algorithm breaks down because it
assumes all editing commands have a uniform cost, but reality is
more nuanced, and the cost of each command is proprotional to
the _length_ of the command; going to position (23, 78) is more
expensive than going to (2,4); etc.  He presented a dynamic
programming algorithms that addressed this efficiently for the
row-replacement problem, and implemented them in his `s` editor
as a proof of concept; I don't think that version made it into
the Software Tools Sampler, though, nor to any of the versions
of S that are online. https://dl.acm.org/doi/10.5555/52187.52188
and https://dl.acm.org/doi/abs/10.1145/59287.59290 are links;
the text of the first paper is online.

>Frankly I think terminal updates is a well solved problem - worth learning and 
>studying since the topic of Edit Distance/LCS relates to other subject areas 
>like gene sequencing, but not worth a new library IMO.

+1.

Sadly, in recent years it seems that people have largely given
up on this, however.  Our systems are so blindingly fast now
that lots of programmers just repaint the whole display canvas
on each change.

> > UI is influenced by the history of interface hardware: teletype printers,
> > serial cable terminals, block-mode terminals, PC, PDAs + stylus, fondle slabs
> > (tablets/smart phones), voice, "mind control"/direct human interface.  These
> > are all interesting too, but they rely on the edit engine to do the work.
>
>An editor's edit engine covers the storage and its manipulation of the text. 
>The terminal update display algorithm for an editor would be part of the 
>UI/hardware interface and as has been mentioned else where GUI for desktop 
>paradigms.

It may be worth mentioning that similar editing distance
minimization techniques can be useful for e.g., updating a
bitmapped display (also a solved problem, however).

	- Dan C

Back to comp.lang.c | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

z-ed Zayd Mohammed <zaydm@172.24.208.1> - 2026-08-16 21:29 +0000
  Re: z-ed Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-08-16 16:20 -0700
    Re: z-ed Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> - 2026-08-17 21:46 +0800
      Editor design & Buffer Gap Anthony Howe <achowe@snert.com> - 2026-10-11 09:05 -0400
        Re: Editor design & Buffer Gap ram@zedat.fu-berlin.de (Stefan Ram) - 2026-10-11 13:42 +0000
        Re: Editor design & Buffer Gap Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-10-11 21:00 +0000
          Re: Editor design & Buffer Gap Anthony Howe <achowe@snert.com> - 2026-10-11 20:50 -0400
            Re: Editor design & Buffer Gap Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-10-12 06:11 +0000
        Re: Editor design & Buffer Gap steve g <Sgonedes1977@gmail.com> - 2026-10-12 17:42 -0400
          Re: Editor design & Buffer Gap Anthony Howe <achowe@snert.com> - 2026-10-18 06:03 -0400
            Re: Editor design & Buffer Gap cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-18 23:26 +0000

csiph-web