Advanced Self-Aware ed(1)

By Artyom Bologov A bright thumbnail with calligraphy on it. In the middle, diagonal and slightly skewed “ADVANCED” is written. Off of its “ED” end, an echo of “ED” spreads across the canvas. There’s attribution to “aartaka.me” and “Artyom Bologov” in the corner. Along the side of the thumbnail, there runs an ed(1) script. I won’t describe it here, look for it at the end of the post. Sorry.

I won’t shut up about ed(1), don’t even ask. Because it’s a good text editor and IDE. And a perfect text computation playground. Bare regex acting on lines of text. What else could one want?

Oh, right. Turing completeness. That’s a hard one. It’s a text editor (I say with an indecypherable smile.) Not supposed to be Turing-complete, right?

Wrong. ed(1) is Turing complete. Because:

  1. It can fall through to the shell, and shell is (awkwardly) Turing-complete.
  2. But shell is boring. ed(1) can call itself instead!
  3. And w-rite commands to its own standard input.
  4. Thus allowing buffer data to turn into executable commands.

So meta. Infinite potential.

Conditionals and Early Returns #

Now wait, we know that Turing-completeness requires branching. if-s and else-s. There’s no such thing in ed(1). Not in the conventional sense. But! there’s g-lobal command.

g goes through every line, matching it with a regex. If the regex does match, it performs the provided actions. A sequence of them, in fact. And moves on to the next matching line.

So g is closer to loops or maps from conventional programming language. But still, there’s conditionality in it, so why not?

In case you need something more… conventional than this weird regex mapping. You can do early escapes/returns. If you consider every ed(1) script a function of its own, it starts making sense. Doing an action until the data is ready. Two techniques there:

The perfect ed(1) script terminates when reaching the desired state of text. Because that’s easy enough to encode. And it plays well with recursion and self-calls. Say what?

Self Calls #

One task I had that seemingly didn’t fit ed(1) was file inclusion. I use ed(1) to build my website. Naturally, I need a way to include/expand templates. Usually represented by separate files with variables in them. I used an imaginary HTML tag <include "filename">. Here’s a script that did the dirty work of including the necessary files from these tags: 

g/<include "*\([^">]*[^"> -]\{3\}\)"*\/*>/s//&\
H\
/<include/d\
-1r \3\
wq\
/
g/<include "*\([^">]*\)"*\/*>/d\
.,+4w !ed %
E
A hack for arbitrary file inclusion using ed(1) self-call

The logic is:

  1. Take lines with these include instructions.
  2. Insert commands processing them into the buffer. Including the r command using the template file name captured by regex.
  3. Go through each instruction and call ed(1) with these commands.
  4. Read the toplevel file back in after the instructions are done.

So the pattern is clear: process the anchor line/instruction into a set of commands. Make these commands act on the arguments substituted from the instruction. And call ed(1) on that set of commands.

Same technique is used in my shell execution instructions. Basically tags of a form <exec "ls -l">. Execute a shell command and read its output back into the buffer. 

g/<exec "*([^">]*[^"> -]{3})"*/*>/s//&\
H\
/<exec/d\
-1r !\3\
wq\
/
g/<exec "*([^">]*)"*/*>/d\
.,+4w !ed %
E
Shell command execution via recursive call to ed(1), itself calling shell

Same technique, except it’s r !\3 (read output of command X) instead of r \3 (read file X.)

Iter... Recursion! #

Now that we learned to call ed(1) from inside ed(1)… Why not call is some more? Many times. Maybe even infinite number of times! Yes, I’m talking recursion.

Recursive scripts combine both conditionals and self-calls. Conditionals are particularly important: they allow to bail out from recursion. Instead of recurring indefinitely.

Here’s an example script that modifies itself until it has the necessary number of ɩ (iota.) 

H
$g/ɩ\{70\}/q
$s/$/ɩ
w
,w !cat % | ed -s %
Q
ɩ
Useless yet exemplary recursive script: add iotas one by one until there are seventy

I know, not the most practical script. But hey, ed(1) was powerful enough for me to have no need for recursion! Yet.

ed Is (Turing) Complete #

So yeah, ed(1) is a powerful enough programming system, supporting

I mean, even BASIC can’t do some of these. And they used BASIC in eighties for Real Programming™. They might’ve used ed(1) and end up better for that.

Don’t commit their mistakes. Use ed(1).

P.S. I know that ed(1) Turing-completeness was already proven. The difference of the proof there and my post is that I’m actually using ed for practical things. Most of the hacks here are the ones I made for my nefarious needs. Enjoy.

P.P.S. Just for fun, here’s a super meta script: 

!echo "HELLO" > hello.txt
E hello.txt
p
s/.*/p\
s|.*|p\\\
s;.*;p\\\\\\\
Q\\\\\\\
;\\\
,w !ed %\\\
Q\\\
|\
,w !ed %\
Q\
/
,w !ed %
Q
Run it with ed < script.ed

P.P.P.S. There’s a whole treasure trove in my ed(1) entries on RosettaCode, but I leave reverse-engineering them to a more capable person. Have a good time watching me dissolve in the madness!

Leave feedback! (via email)