Saturday, June 29, 2013

The Turing completeness of WARP

While not essential, I thought it might be amusing to be able to state that WARP is Turing complete. Not wishing to appeal to deeper theory, like Turing computable or mu recursive  functions, and not wanting to rely on mere personal belief,  the easiest mechanism to achieve this noble (!) goal was to write a WARP program that could interpret a language known to be Turing complete.

The best candidate was our old Turing tarpit, brainfuck. And thus the hideousness below - but it works...sure, glacial performance, but working. Because the eso interpreters I write are simple C# console apps, I employ the pipe mechanism of the command line to provide the brainfuck source to the WARP bf interpreter; as an example, "Hello world" is shown below (excuse the clumsy line breaks for formatting):

 echo "+++++ +++++[> +++++ ++ > +++++ +++++> +++> +   
 <<<< - ]> ++ .> + .+++++ ++ ..+++ .> ++ .<< +++++ +++++   
 +++++ .> .+++ .----- -.----- --- .> +.> ." | warp brainf.warp  

And the WARP source for the interpreter:
1:  =psN5D=pcps  
2:  @s,l=bs!:bs:0?0?^.p%bs@m}pc>pc1^_m|^.s  
3:  @p=espc=bf0=pcps@r{pc=cc!:"]":cc?0?^.l=ad0:"+":cc  
4:  ?0?=ad1:"-":cc?0?=ad-1:">":cc?0?>bf1  
5:  :"<":cc?0?<bf1:".":cc?0?^.o:bf:0?-1?=bf0{bf>!ad  
6:  }bf@n>pc1:es:pc?0?^.e^.r@o{bf(!^.n@l{bf:0:!?0?^.n=xx0@g<pc1{pc=cp!  
7:  :cp:"]"?0?<xx1:cp:"["?0?>xx1:xx:1?0?^.n^.g@e  

It is a cheat; the source is read (line 2) and placed into WARP's random access stack starting at index N5D, which is one greater than the standard brainfuck cell count. It does not implement the bf , operator, but that would be a simple matter to address. And that in (the released version) just over 300 bytes.

I'm inordinately pleased with it.

No comments: