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 B1 B10,IADD _ B11,PRINT _,

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 decrwhere 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.