Quantum, Entropic and Entangled computation

[See the new post https://wombatlang.blogspot.com.au/2017/06/no-holes-in-closures-and-case-behaviour.html for fixes to problems in this post.]

In the quantum world every event is reversible. But above that we have the world of everyday experience where entropy always increases, time moves relentlessly forward and events are not reversible.

In computing there is a similar situation. Some functions don't lose any information when run in the normal forward direction, and these should be able to be run backwards to give the inverse function. Factorial is such a lossless function, and it is interesting to run it backwards in Wombat. [Relevant aspects of Wombat are given at the end for newcomers].

`fact = {   $:Nat = `n;

           caseP [

               {n=0; 1}

               {n>?0; n*fact(n-1)}

           ] ()

       };

6 = fact `x; print x

• `x = H1 -- call fact (Holes are given as Hn, as they are created).
• in fact for the 1st time. $=n=H1. `$=6.
• in 1st case n=H1=0, `$=1 fails
• 2nd case. n=H1, 6=H1*fact(H1-1)
• in fact 2nd time. $=n=H2=H1-1. `$=H3. 6=H1*H3.
• in 1st case. H2=0. H1=1. H3=1 -- 6=1*1 fails
• 2nd case. H2>0. H1>1. H3=H2*fact(H2-1).
• in fact 3rd time. $=n=H4=H2-1=H1-2. `$=H5=fact(H2-1). H3=H2*H5. => 6=H1*H2*H5
• 1st case. H2=1. H1=2. H5=1. But 6=H1*H2*H5=2 fails.
• 2nd case. H4>0.H2>1.H1>2. H5=H4*fact(H4-1).
• in fact 4th (and last) time. $=n=H6=H4-1=H2-2=H1-3.
                         `$=H7=fact(H4-1). H5=H4*H7 => 6=H1*H2*H4*H7
• 1st case. H6=0. H4=1. H2=2. H1=3. H7=1. 6=H1*H2*H4*H7 succeeds! The answer (x=H1) is 3.
• 2nd case. Exercise: Prove that result must be greater than 6... fails

As we recurse, we keep creating new holes, and having to remember the relationships between them. This is vaguely reminiscent of thunks in lazy languages. It is also feels like entanglement, though whether it could have anything to do with quantum physics entanglement is left as an exercise for the reader.

---

some relevant features of Wombat are:

• An identifier is preceded by backquote when used for the first time. It starts life as a hole, and like all holes it can only be filled in once. `x:Int; x=3 (Explicit typing is optional.);
• An explicit procedure (closure) is just an expression in braces -- { x+1 } ;
• A closure's input is $ and its output is `$. The input is commonly a tuple which is unpacked immediately, and $ is never mentioned again -- { $ = (`x,`y); x+y } ;
• If `$ isn't explicitly unified, then it is unified with the whole expression: {$+1} means {`$=$+1}.
• For each boolean operator, there is a version with ? (such as >? above) which succeeds or fails, instead of returning true or false. The failure is informational, allowing alternative paths. A double ? would cause a fatal error when false. The ubiquitous = operator is the same as ==?.
• caseP takes a list of procedures, passing the 2nd parameter (just () above) to each. It expects exactly one to succeed, giving its result. Actually more than one can succeed if they give the same or compatible results, but that's another story. The example above would have been easier if I'd used firstCase instead.

P.S. I fixed the formatting in the previous post. Don't ask me how Blogger corrupted it.