User:Ian/Underload.sed

I have written an Underload interpreter in sed. It is a REPL-style interpreter and is capable of running all of the examples listed on the page including the "99 Bottles of Beer" program. It goes into an infinite loop on undefined behavior like invalid commands or stack underflow. The D (debug) operator can be used to print the NUL-separated stack and 0xFF-delimited continuation. Programs run in this interpreter cannot contain NUL (0x00) or 0xFF.

#n
#0x00 = stack item separator
#0xff = stack/code separator
s/^/\xff/ #Initialize pattern space
:main
s/\xff\n/\xff/ #Remove newline(s) if necessary
#s/"\(.\)/\1/g #Unquote double-quoted items
s/\(\x00[^\x0]*\)\(\x00[^\x0]*\)\xff~/\2\1\xff/ #Swap
s/\(\x00[^\x0]*\)\xff:/\1\1\xff/ #Dup
s/\x00[^\x0]*\xff!/\xff/ #Discard
s/\(\x00[^\x0]*\)\x00\([^\x0]*\)\xff\*/\1\2\xff/ #Cons/Concat
s/\xff(\([^()]*\))/\x00\1\xff/ #Simple Lambda/String
/\xff(/{ #Nested Lambda/String
	s//\x00\xff/
	x;s/^/!\x00/ #Initialize counter
	:rloop
	x
		/\xff$/N #Next line iff EOL
		/\xff(/{x;s/^/!/;x} #Increment counter
		/\xff)/{x;s/^!//;x} #Decrement counter
		s/\xff\(.\)/\1\xff/ #Move character
	x;/^!/brloop
	s/^\x00//;x #Remove counter separator
	s/)\xff/\xff/
}
s/\x00\([^\x0]*\)\xffa/\x00(\1)\xff/ #Quotify
s/\x00\([^\x0]*\)\xff^/\xff\1/ #Execute/Uncons/Unquote
/\x00\([^\x0]*\)\xffS/{ #Print
	x;G #Copy pattern space
	s/^\([^\x0]*\)\n.*\x00\([^\x0]*\)\xffS.*/\1\2/ #Concatenate buffer
	:pline;/\n/{P;s/^[^\n]*\n//;bpline}
	#Cut long lines to 79 characters:
	#/.\{79\}/{p;s///}
	x #Restore pattern space
	s/\xffS/\xff!/ #Push a Discard operator
}
/\xffD/s//\xff/p #Debug
/\xff$/{x;p;s/.*//;x;N} #Read a new line (and finish partial print)
bmain