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.

Further WARP programs

I've been busy trying to stabilise the WARP interpreter, and have a few test programs that 'validate' the 1.7 version:

Collatz Conjecture (from 99,000)

 =se24E0)"Hailstone sequence for ")se@a)se(D(A*se#!2:!:0  
 ?1?^.o$se2^.r@o&se3>se1@r:se:1?1?^.a  

Prime number finder
This program uses decimal (+A) instead of hexatrigesimal, and leans heavily on the stack, the ? operator and the new # operator. It misses out 3 and 2 on output, as it uses integral division to ameliorate it's otherwise O(n) behaviour. Of course, halving the search space is still regarded as having O(n) characteristics, but you can notice the difference in performance!

 +A)"Enter start: ",=cu!)"Primes <= ")cu(13(10  
 @o*cu$!2=ca!  
 @i*cu#!ca?0?^.n<ca1:ca:1?1?^.i)cu)" "  
 @n<cu1*cu<!1^!o  

Simple calculator
A very simple integral calculator.

 +A)"WARP simple calculator: Enter q (as operator) to quit, c (as operator) to clear "(13(10  
 =ac0@l)"Enter operator: ",=op!:op:"q"?0?^.e:op:"c"?0?^.c  
 )"Enter operand: ",=nu!:op:"+"?0?>acnu:op:"-"?0?<acnu:op:"*"?0?&acnu:op:"/"?0?$acnu  
 ^.p@c=ac0@p)ac(13(10^.l@e  

Reverse an entered string
This example uses a feature not present in the 1.7 release - stack rotation using the ' operator.

 )"Enter a string to reverse: ",=st!%st@r=ch!'*ch'^_r'@p)!^_p  

Specification here: http://esolangs.org/wiki/WARP
Mostly complete interpreter: http://esotericinterpreters.codeplex.com/

The WARP esoteric language

I thought I'd add my own esoteric language to the considerable pantheon - it's called WARP (a rather poor recursive acronym, WARP and run programming - because the full interpreter should randomize ("warp") the source as it executes). Added it also as a way of cheering myself, as I have been terribly sick over the last week. It has a variable radix system, but starts in hexatridecimal (c.f. hexatrigesimal) mode.

Below is a full WARP program that outputs the first 71 numbers in the Fibonacci sequence.

 *1=na1=li1Z@z;)!)" ">!na;<!na=na!<li1^liz  

Specification here: http://esolangs.org/wiki/WARP
Mostly complete interpreter: https://esotericinterpreters.codeplex.com/

C-INTERCAL

Following on from the amazing success and uptake of the esoteric language interpreter suite (a bandwidth busting  total of 49 downloads!), I've commenced searching  for other languages ripe for my unwelcome code attentions. And after reading this prolix and circular prose, C-INTERCAL is indeed worthy of consideration.

"The last part of a statement is an optional ONCE or AGAIN. ONCE specifies that the statement is self-abstaining or self-reinstating (this will be explained below); AGAIN specifies that the statement should behave like it has already self-reinstated or self-abstained. Whether the behaviour is self-abstention or self-reinstatement depends on whether the statement was initially abstained or not; a ONCE on an initially reinstated statement or AGAIN on an initially abstained statement indicates a self-abstention, and a ONCE on an initially abstained statement or AGAIN on an initially reinstated statement indicates a self-reinstatement."

Excerpted from: http://www.catb.org/~esr/intercal/ick.htm#Syntax

FALSE, Befunge-93 and BrainF**k

The 'Hardy' work continues on the now rather grandly named 'esoteric interpreter suite'. The BrainF**k interpreter did not take long at all to implement (no surprise there I suppose) but required some refactoring of the 'core' interpreter abstractions; this continues as the focus has now shifted to Befunge-93. I thought I'd ease myself into the 'funge' language family - Nefunge is the ultimate goal :-)

Agile vs DDD: A microcosm

I've been carrying on with some refactoring to support simple eso-language interpreters generally, building on the False language work. Next target is Befunge-93, and that led me to a few thoughts as the dog and I meandered along.

Bear with me. False has a simplistic notion of a program counter (PC); in fact, a rather standard one, that we can think of as a uni dimensional object - a number, if you will. Befunge-93 by way of contrast, has a program counter that is a point in a finite cartesian space along with an implied vector of movement.

This is why I pondered agile approaches today. When I commenced this amusing side project to create some eso-language interpreters, I was aware of the Funge style languages, and therefore cannot maintain that I had no  idea that  the classical representation of a PC was going to be flawed.

Thus, any base abstractions I implemented that 'enjoyed' this representation would likewise be limited in scope, and would not advance me towards the goal of a more generalized interpreter framework for the esoteric family of languages. However, I did want to release my False language interpreter sooner rather than later - not because of any latent demand you understand, just for personal pleasure.

My own trivial undertaking therefore, and perhaps unsurprisingly, encapsulates a microcosm of the issues we face in a business sphere during software development:

• Time to market: I wanted the False interpreter released more than I wanted the generalized framework in place. I was content to trade off releasing sooner against the predicted cost of refactoring
• YAGNI or TALIA: As I wasn't sure that I would continue, it seemed that YAGNI would apply here, instead of TALIA (previous post) 
• DDD: This eso-language idea falls uncomfortably in the middle of a domain driven design/simple exercise. The entire sphere of eso-languages shows great variety, but little real complexity of domain. For example, Funge-98 describes the existence of possible large n dimensional spaces for program execution - but that is more an implementation difficulty detail, as the model implied does not impose a significant cognitive load for most people.

Simplistic notions simply presented.

False Interpreter 0.94

Been steadily working on the False interpreter, lambda support fully operational and tested on a number of examples from Rosetta Code. All relatively straightforward, and now making the hideous mistake of extending the command set, starting with stacking timers, used for coarse performance measurement, example below:

1:  { Ethiopian multiplication }  
2:  )stEM)[2/]h:[2*]d:[1&]o:[0[@$][$o;![@@\$@+@]?h;!@d;!@]#%\%]m:  
3:  "  
4:  Ethiopian, 17 and 34: "  
5:  17 34m;!.{578}  
6:  "  
7:  ")ct)  

Line 2 uses the start timer command ")st" and execution time is dumped to the console at Line 7 with )ct.

[$1=$[\%1\]?~[$1-f;!*]?]f:

I've nearly finished a C# 4 interpreter for the FALSE language (http://strlen.com/false/false.txt) - current source code at: http://falseinterpreter.codeplex.com/ - a few more operators to go, but the Lambda support appears stable. It's not optimised at all as of yet, and could do with some serious efforts in that area!


FALSE code.....


Factorial: [$1=$[\%1\]?~[$1-f;!*]?]f:
Primes < 100:  99 9[1-$][\$@$@$@$@\/*=[1-$$[%\1-$@]?0=[\$.' ,\]?]?]#


Work inspired by G H Hardy:
"I have never done anything 'useful'. No discovery of mine has made, or is likely to make, directly or indirectly, for good or ill, the least difference to the amenity of the world."