Sed is turing complete. It has two character buffers and looping. I find that every year or two, I get the urge to code little algorithms in sed. Lately I've been writing a ray-tracer in sed.
Consider a simple program: PRINT 1+2+3. In sed, as I have coded it, this is written:
IADD is integer addition, and I've chosen to use binary numbers since it makes the code simpler. This string is the pattern space and is equivalent to the stack. Each stack frame ends in a comma. The first IADD computes its result and executes RETURN B11 and B11 replaces the underscore in the next frame.
Consider the Fibonacci Sequence (0,1,1,2,3,5,...), where fib(0)=0; fib(1)=1; and fib(x)=(fib(x-1)+fib(x-2)). Coded in sed, I have the following function body:
s/^FIB B0,/RETURN B0,/
s/^FIB B1,/RETURN B1,/
t return
DECR B\1,SUBST X1 _,FIB {X1},SUBST T _,DECR {X1},FIB _,IADD {T} _,!,
t decr
where B\1 is the first argument to FIB.
Please excuse the very long line, but the whole function is as follows:
:fib
# fib(0) => 0
# fib(1) => 1
# fib(x) => fib(x-2) + fib(x-1) => x1=x-1; t=fib(x1); iadd(t,fib(x1-1))
s/^FIB B0,/RETURN B0,/
s/^FIB B1,/RETURN B1,/
t return
s/^FIB B\([01]\+\),/DECR B\1,SUBST X1 _,FIB {X1},SUBST T _,DECR {X1},FIB _,IADD {T} _,!,/
t decr
b loop-error
SUBST takes an identifier and a thing as arguments and replaces all occurrences of {identifier} with thing up to the first ! stack frame. If we come to this function but the pattern space fails to match any possibilities defined in FIB, it is a loop-error and computation halts.
Fib.sed contains definitions for FIB, IADD, ISUB, INCR, DECR, RETURN, SUBST, and PRINT along with some other infrastructure.
My ray-tracer contains a more extensive integer and floating point library, global variables, and other useful additions.