Talk:SMATINY

A few questions

Hi. This language is quite interesting I think, and I was wondering whether there is any way to access memory or perhaps some way to store values within the program structure. However my head is already spinning after trying to think in this language, without any success to product such programs. But then again, I'm not intelligent at least. So, is that possible? And, is there any way to do any if-stuff? Is this language actually suitable for writing programs such as '99 bottles of beer'? And what happens if some of the lines doesn't exist (say, your program is "1. Swap 1 with 5000.")? It probably just terminates then, I guess. --Keymaker (unsigned)

Just like SMETANA, you have to scramble instructions around in order to store data, and execute them to know what they contain. I'd say any unspecified steps are automatically "Do nothing.", but if you're ever greater than the highest specified step, you're considered outside the program, so the program ends. It should be possible to write programs that actually do something in SMATINY, even if they're kludges. Here's a "Hello, world!" that I probably made a mistake on somewhere:

1. Swap 1 with 120. ; out of harm's way

121. Swap 187 with 72. ; gets that ready to output 'H'
122. Swap 174 with 73. ; adds a jump back to step 123
123. Swap 123 with 71. ; let's go!
124. Do nothing. ; jump target

125. Swap 72 with 101. ; 'e'
126. Swap 175 with 102.
127. Swap 127 with 100.
128. Do nothing.

129. Swap 101 with 108. ; 'l'
130. Swap 176 with 109.
131. Swap 131 with 107.
132. Do nothing.

133. Swap 108 with 108. ; 'l', and I know this won't do anything
134. Swap 177 with 109.
135. Swap 135 with 107.
136. Do nothing.

137. Swap 108 with 111. ; 'o'
138. Swap 178 with 112.
139. Swap 139 with 110.
140. Do nothing.

141. Swap 111 with 44. ; ','
142. Swap 179 with 45.
143. Swap 143 with 43.
144. Do nothing.

145. Swap 44 with 32. ; ' '
146. Swap 180 with 33.
147. Swap 147 with 31.
148. Do nothing.

149. Swap 32 with 119. ; 'w'
150. Swap 181 with 120.
151. Swap 151 with 118.
152. Do nothing.

153. Swap 119 with 111. ; 'o'
154. Swap 182 with 112.
155. Swap 155 with 110.
156. Do nothing.

157. Swap 111 with 114. ; 'r'
158. Swap 183 with 115.
159. Swap 159 with 113.
160. Do nothing.

161. Swap 114 with 108. ; 'l'
162. Swap 184 with 109.
163. Swap 163 with 107.
164. Do nothing.

165. Swap 108 with 100. ; 'd'
166. Swap 185 with 101.
167. Swap 167 with 99.
168. Do nothing.

169. Swap 100 with 33. ; '!'
170. Swap 186 with 34.
171. Swap 171 with 32.
172. Do nothing.

173. Swap 173 with 187. ; end of program!

174. Swap 73 with 124.
175. Swap 102 with 128.
176. Swap 109 with 132.
177. Swap 109 with 136.
178. Swap 112 with 140.
179. Swap 45 with 144.
180. Swap 33 with 148.
181. Swap 120 with 152.
182. Swap 112 with 156.
183. Swap 115 with 160.
184. Swap 109 with 164.
185. Swap 101 with 168.
186. Swap 34 with 172.

187. Output this block's position.

(ouch!) --Ihope127 00:03, 18 May 2006 (UTC)

Aaargh, my head! Thanks, I'll try to decipher that sometime! There's probably no interpreter (yet)? I could try writing one if I were home.. Do you know about the computational class of this lang? --Keymaker 03:18, 18 May 2006 (UTC)

It has only finite memory, so it sounds like it should be billed as a finite-state automaton thingy. :-) --Ihope127 13:35, 18 May 2006 (UTC)

Lost in translation

Keymaker: I noticed that this bit got "lost in translation":

X. Swap X with Y.

Note the fact that both the step number and the first "swap this" are the same--if they aren't, no jump is performed. --Ihope127 13:32, 18 May 2006 (UTC)

Oh, sorry! I didn't know that! You should've said it more clearly, as it didn't say anything about jump not being performed if they aren't same! Or perhaps I should've figure that out by the fact both were X, but I thought that was some typo as there was nothing to indicate such thing. :P Anyways, glad to know now! And good to notice someone fixed the programs to follow this rule. I really had no idea about it being so! --Keymaker 14:27, 18 May 2006 (UTC)

Well, it's fixied now. How about if I add this "swap, then jump past the destination" to the article as another experimental instruction? --Ihope127 15:21, 18 May 2006 (UTC)

This is also essential to preserve the reversible control flow of the language. I have reedited the article, including modifying the example programs. However I had to remove the infinite loop examples because SMATINY programs always terminate. --Ørjan 13:57, 18 May 2006 (UTC)

Reversible IO

(split section inside my message)

I think it would be interesting to add I/O instructions that allow reversible dataflow as well. Then it might be possible to compile Kayak into the language, although with limited memory. --Ørjan 13:57, 18 May 2006 (UTC)

How's this:

X. Input a character, then swap Y with it.

--Ihope127 14:03, 18 May 2006 (UTC)

I don't think that works. After performing that instruction, the program could very well be in a state where it could not tell what has been input. If Y = X, it would work once, but then there would be a problem the next time around.

After I made the suggestion, I realized there may be problems making such an instruction because SMATINY's program state has fixed size, and reversible input must somehow grow the memory size. --Ørjan 18:58, 18 May 2006 (UTC)

What if the reverse-interpreter could simply demand the forward-interpreter's output? --Ihope127 19:06, 18 May 2006 (UTC)

Don't you mean input? That seems like a solution. Treat input as a read-only stream, that needs to be consulted both forwards and backwards. And output as a write-only stream, which does not affect program flow at all, which means your original instruction works fine.

When reversible computers are dealing with read-only data they copy it by XORing or adding the data to a location whose contents are predetermined to be zero. Something similar might work.

But, this would make it impossible to run a whole program in reverse, like in Kayak. --Ørjan 19:36, 18 May 2006 (UTC)

I don't really understand this. Do we accept a number as input then perform a swap with the input and Y? Or something else? DavidHouse 16:45, 25 May 2006 (UTC)

If it works similarly to the output command, then it means

X. Input a character, then swap step Y with the step corresponding to the character's
code number.

--Ørjan 21:25, 25 May 2006 (UTC)

Yep. --Ihope127 21:58, 25 May 2006 (UTC)

Hello World impossible?

I may be totally wrong about this, but i guess we'll see. In the string "Hello, World!" you have characters with consecutive ASCII values, making their steps right after each other. The problem is the characters arn't right after each other in the string. So in the program you would need this:

32. Output this block's position. ( )
33. Output this block's position. (!)

Then to output the space you would need a:

X. Swap X with 32.

somewhere in the program. But once you swap to 32 it will output the space, then move onto 33 printing the ! after it. Also I dont think there is any way to output a character 2 times without creating an infinite loop.
Edit: I just noticed that the Swap command isn't just a goto but actually Swaps the 2 commands. So im not sure if what I said above is right or not anymore.
Poiuyqwert 14:53, 18 May 2006 (UTC)

Remember that SMATINY is self-modifying. The way my above "Hello, world!" works is by swapping the "Output this block's position." into the correct place, then running it, then jumping back to the main program, which then moves the output block somewhere else. There's no need to have output blocks pre-set, as my first attempt did (it failed for pretty much the reason you stated). --Ihope127 15:14, 18 May 2006 (UTC)

Infinite memory

Maybe you could add new commands for infinite memory:

X. Push this line's position onto stack number Y
X. Pop and discard an entry from stack number Y
X. Pop an entry from stack number Y and swap step Z with that instruction
X. Add Y to the number on top of stack Z
X. Push Y onto the stack of the number of this line

--Zzo38 (unsigned)

Those don't look reversible. I'll add them to the interpreter, though, once I finish with the rest of it :-) --Ihope127 19:02, 18 May 2006 (UTC)

Kayak implements IO using stacks so the two problems may be similar. --Ørjan 19:09, 18 May 2006 (UTC)

Infinite loops

What makes the following not infinite loop?

1. Swap 2 with 1.
2. Swap 2 with 1.

According to the information on SMATINY's page, "If X = Y, this will jump to the step below step Z, in addition to performing the swap as normal (and similarly for X = Z). If the current step is not one of those swapped, no jump is performed.", (which is not written by me, just to note,) this program should be infinite loop, as:

• In step 1 step 2 is swapped with step 1, and as X=Z in this case, a jump is performed to step 2.
• In step 2 step 2 is swapped with step 1, and both the step 1 and 2 are identical for their data. As X=Y in this case a jump is performed to step 2.
• In step 2 again, as the step's data is exactly same than in the case I just described above, the same stuff is done.
• And again and again and again..

That, of course, unless I didn't mess up something OR the language has been changed without someone updating the Wiki. :p --Keymaker 00:57, 19 May 2006 (UTC)

Infinite loops aren't impossible in reversible languages with finite data storage and no input. It's just that they must return exactly to the starting position, which can't happen in SMATINY because it's impossible to jump to line 1 (just as BackFlip can't go into an infinite loop because it starts in a location that causes program termination if it's reached again). The program above starts by swapping line 1 and line 2, and jumping to line 3, exiting immediately. If it somehow started on line 2, it would be an infinite loop. So the following would be an infinite loop, if it were legal:

0. Swap 0 with 2.
1. Do nothing.
2. Swap 0 with 2.

but this relies on having a line 0 but the program starting on line 1. --ais523 09:40, 19 May 2006 (UTC)

Hmmm.. So the information on wiki page is wrong and/or old? I thought a jump is performed whenever X=Y or X=Z. If not, what does this part mean ".. (and similarly for X = Z). If the current step is not one of those swapped, no jump is performed."? I thought it stated that either Y or Z should be the same than X. My infinite loop relied on that.. But perhaps the wiki page is outdated again, or has false information, or the problem is me. Besides, I don't think your infinite loop would work either (if it were valid), as it relies on the same thing as my did, that the jump will be performed also if X=Z. However, if the jump is performed if X=Y or X=Z, then my loop is working. --Keymaker 10:25, 19 May 2006 (UTC)

It doesn't jump to Z, but to the step below Z. Or equivalently, the instruction pointer is incremented between instructions, after the swap has been performed. --Ørjan 11:23, 19 May 2006 (UTC)

If X = Y, then it jumps to the step below Z. If X = Z, then it jumps to the step below Y. --Ihope127 13:18, 19 May 2006 (UTC)

Ah, finally exactly what I wanted to hear. The wiki was really confusing on this, and should be cleared (in case it isn't already, haven't looked yet). Would've posted nothing about infinite loops if it had been clear to me what that "(and similarly for X = Y)" meant. --Keymaker 09:51, 21 May 2006 (UTC)

Interpreter

Hi all. I've implemented an interpreter for smatiny. You'll need a haskell compiler to build it, try GHC. Have a play, let me know of any bugs. It has already found two bugs in ihope's Hello World program :) Add any comments here. Cheers. David House <dmhouse@gmail.com>.

More infinite memory

X. Move the tape head left.
X. Move the tape head right.
X. Increment the number under the tape head.
X. Decrement the number under the tape head.
X. Take the number under the tape head and swap Y with it.

Does this look reversible? --Ihope127 14:33, 23 May 2006 (UTC)

Seems like an interesting idea, although it ruins the language a bit in my opinion. Mainly because then the language will not be that simple and minimalistic anymore, and this memory model is quite common (not that I don't like it anyways). The way to get values from memory and place them is nice.. What does this reversible actually mean? That if you have the final memory state and you run the program backwards it goes to the initial state or something? --Keymaker 08:33, 24 May 2006 (UTC)

Pretty much. It means your automaton must be able to be run in reverse from any point in time to get to previous points in time.

What about this:

X. Increment the temporary number.
X. Decrement the temporary number.
X. Swap the temporary number with Y.

I've reduce the tape length to 1. This leaves one unbounded integer for temporary storage; although this is 'infinite memory', I'm not sure if this is enough for Turing-completeness. --ais523 12:22, 25 May 2006 (UTC)

Good idea! Hmmm.. An infinite register/variable should be ok for Turing-completeness, at least according to wikipedia -- however, in that case it should do its "computations by manipulating Gödel numbers in its register", which may be really difficult in this one, if even possible. I don't have the slightest idea how such thing can be written. Of course there might be some other way than Gödel numbers, but not sure if it has been invented yet. :) --Keymaker 14:08, 25 May 2006 (UTC)

I think this relates to the discussion in Minsky machines. I was going to say that we have too few operations to make do with just one register, but then I realized that the above operations may be enough to simulate an arbitrary fixed number of registers by changing step numbers in the program to arbitrary large numbers. Since with just two registers it is enough to have increment, decrement and test for zero, I guess this can be Turing-complete. Assuming that reversibility does not cause much extra problems (reversible Turing-machines are well-known to be Turing-complete) --Ørjan 15:15, 25 May 2006 (UTC)

For that to be enough for Turing-completeness, you'd probably need a different way of accessing the number. Here, you can only access it if it's within program bounds. --Ihope127 15:22, 25 May 2006 (UTC)

Hello world!

Here's a fairly optimized hello world (along with an unix new-line) program in 22 lines. Haven't ran ihope's version but someone said there were a few bugs. My interpreter was finished after this program.. I found a few bugs while trying to run the program I thought surely was valid but still didn't work for some reason -- it appeared the interpreter had a few serious bugs. Here. I'll upload the interpreter to my site soon. --Keymaker 13:56, 25 May 2006 (UTC)

Thanks to the interpreter, the bugs in my program have been fixed. But your program is... wow. :-) --Ihope127 15:22, 25 May 2006 (UTC)

If you're refering to my interpreter, then please post examples of what doesn't work! Your program seems to run perfectly on my system. Cheers. DavidHouse 16:28, 25 May 2006 (UTC)

I was talking about my own interpreter, in case you asked me that question. :) And cheers ihope. --Keymaker 16:39, 25 May 2006 (UTC)

Computational class

The categories on this page list it both as Unknown computational class and as a Finite state automaton. As these are inconsistent, one of them probably ought to be removed. (I was reverted when I tried to remove the 'Unknown' class.) Any opinions? --ais523 07:24, 26 Jun 2006 (UTC)

I reverted it because I don't think they are actually inconsistent. The computational class of SMATINY is a subset of finite state automata, indeed a subset of the reversible ones, but it has not been determined exactly which subset it can emulate. I suspect that it is indeed all the reversible ones, but this requires an argument. For now it is in almost the same situation as BackFlip, which means I am tempted to add Finite state automata to the latter as well. --Ørjan 14:27, 26 Jun 2006 (UTC)

I've actually suspected for a while that SMATINY and BackFlip are in the same computational class, and have tried to think up ways to compile between them (no success yet). --ais523 15:17, 26 Jun 2006 (UTC)

Would SMATINY be able to simulate more FSA's if it did something "special" on an infinite loop, then halted? --Ihope127 14:57, 26 Jun 2006 (UTC)

I don't understand the question because SMATINY never enters an infinite loop, as a consequence of each program being a reversible FSA. --Ørjan 18:22, 26 Jun 2006 (UTC)

I mean it would have an infinite loop checker built in, that would keep it from entering an infinite loop. --Ihope127 16:26, 29 Jun 2006 (UTC)

Assuming you mean an infinite loop in the original FSA to be compiled: Well, such an algorithm is simple for an FSA, just graph reachability. But it would make more sense to implement it in a compiler, rather than in the final SMATINY program. Of course you could probably write a compiler of some sort in SMATINY, but unless the conversion was describable as an (R)FSA recoding (unlikely except perhaps between something like the closest Brainfuck derivatives), it would have a size limit. And an interpreter is even worse: it would have to have room for the entire program, as well as for any irreversible "garbage" the program produces. That "garbage" by the way is a more serious problem than infinite loops when you want to compile an irreversible FSA into SMATINY. Removing infinite loops is easy by comparison. --Ørjan 17:46, 29 Jun 2006 (UTC)

BackFlip mirror in SMATINY

I had a go at this, making things simple but rather verbose. For readability I have used a "structured" label format. The flipping code is duplicated before each exit so I "defined" a macro for it. Note that every jumping swap is supposed to be between steps with identical contents. It should be easy to turn this into a program generating proper SMATINY code.

On second thought a "subroutine" is nearly as easy as a macro and avoids the duplication in the final code. --Ørjan 01:15, 27 Jun 2006 (UTC)

The mirror is at position (x,y), initially in the / state.

    (x,y,Flip-1). Swap (x,y,Flip-1) with (x,y,Flip+9).
  (x,y,Flip). Do nothing.
      (x,y,Flip+1). Swap (x,y,FromUp+1) with (x,y,FromUp+2).
      (x,y,Flip+2). Swap (x,y,FromLeft+1) with (x,y,FromLeft+2).
      (x,y,Flip+3). Swap (x,y,FromRight+1) with (x,y,FromRight+2).
      (x,y,Flip+4). Swap (x,y,FromDown+1) with (x,y,FromDown+2).
      (x,y,Flip+5). Swap (x,y,ToUp-2) with (x,y,ToUp-3).
      (x,y,Flip+6). Swap (x,y,ToLeft-2) with (x,y,ToLeft-3).
      (x,y,Flip+7). Swap (x,y,ToRight-2) with (x,y,ToRight-3).
      (x,y,Flip+8). Swap (x,y,ToDown-2) with (x,y,ToDown-3).
    (x,y,Flip+9). Swap (x,y,Flip+9) with (x,y,Flip-1).

  (x,y,FromUp). Swap (x,y,FromUp) with (x,y-1,ToDown).
    (x,y,FromUp+1). Swap (x,y,FromUp+1) with (x,y,ToLeft-2).
    (x,y,FromUp+2). Swap (x,y,FromUp+1) with (x,y,ToRight-2).
  (x,y,FromLeft). Swap (x,y,FromLeft) with (x-1,y,ToRight).
    (x,y,FromLeft+1). Swap (x,y,FromLeft+1) with (x,y,ToUp-2).
    (x,y,FromLeft+2). Swap (x,y,FromLeft+1) with (x,y,ToDown-2).
  (x,y,FromRight). Swap (x,y,FromRight) with (x+1,y,ToLeft).
    (x,y,FromRight+1). Swap (x,y,FromRight+1) with (x,y,ToDown-2).
    (x,y,FromRight+2). Swap (x,y,FromRight+1) with (x,y,ToUp-2).
  (x,y,FromDown). Swap (x,y,FromDown) with (x,y+1,ToUp).
    (x,y,FromDown+1). Swap (x,y,FromDown+1) with (x,y,ToRight-2).
    (x,y,FromDown+2). Swap (x,y,FromDown+1) with (x,y,ToLeft-2).

    (x,y,ToUp-3). Swap(x,y,ToUp-2) with (x,y,FromRight+1).
    (x,y,ToUp-2). Swap(x,y,ToUp-2) with (x,y,FromLeft+1).
    (x,y,ToUp-1). Swap(x,y,ToUp-1) with (x,y,Flip).
  (x,y,ToUp). Swap (x,y,ToUp) with (x,y-1,FromDown).
    (x,y,ToLeft-3). Swap(x,y,ToLeft-2) with (x,y,FromDown+1).
    (x,y,ToLeft-2). Swap(x,y,ToLeft-2) with (x,y,FromUp+1).
    (x,y,ToLeft-1). Swap(x,y,ToLeft-1) with (x,y,Flip).
  (x,y,ToLeft). Swap (x,y,ToLeft) with (x-1,y,FromRight).
    (x,y,ToRight-3). Swap(x,y,ToRight-2) with (x,y,FromUp+1).
    (x,y,ToRight-2). Swap(x,y,ToRight-2) with (x,y,FromDown+1).
    (x,y,ToRight-1). Swap(x,y,ToRight-1) with (x,y,Flip).
  (x,y,ToRight). Swap (x,y,ToRight) with (x+1,y,FromLeft).
    (x,y,ToDown-3). Swap(x,y,ToDown-2) with (x,y,FromLeft+1).
    (x,y,ToDown-2). Swap(x,y,ToDown-2) with (x,y,FromRight+1).
    (x,y,ToDown-1). Swap(x,y,ToDown-1) with (x,y,Flip).
  (x,y,ToDown). Swap (x,y,ToDown) with (x,y+1,FromUp).

--Ørjan 00:35, 27 Jun 2006 (UTC)

I believe the below shows how to define an arrow, initially up (^). To shorten the description, I left out the following labels without increment: FromUp, FromLeft, FromRight, FromDown, ToUp, ToLeft, ToRight and ToDown. These are identical to those in the mirror example. These are also the only steps which use labels from more than one cell, so I can therefore also leave out the "(x,y," part. Lastly I left out the entire Right and Down part which is exactly similar to Left. Up is special because it is the current direction of the arrow.

 FromUp+1. Swap NextUp with Next+1.
 FromUp+2. Swap FromUp+2 with Switch.
 NextUp. Swap NextUp with Next+1.
 NextUp+1. Swap NextUp with Next+1.
 NextUp+2. Swap FromUp+2 with Switch.
 NextUp+3. Swap NextUp+5 with Switch+1.
 NextUp+4. Do nothing.
 NextUp+5. Do nothing.
 ToUp-4. Do nothing.
 ToUp-3. Swap ToUp-4 with NextUp+5.
 ToUp-2. Swap NextUp+4 with Next-1.
 ToUp-1. Swap ToUp-1 with Next.

 FromLeft+1. Swap NextLeft with Next+1.
 FromLeft+2. Swap FromLeft+2 with Switch.
 NextLeft. Swap NextLeft with Next+1.
 NextLeft+1. Swap NextLeft with Next+1.
 NextLeft+2. Swap FromLeft+2 with Switch.
 NextLeft+3. Swap NextLeft+5 with Switch+1.
 NextLeft+4. Swap NextLeft+4 with Next-1.
 NextLeft+5. Swap Switch+1 with ToLeft-4.
 ToLeft-4. Do nothing.
 ToLeft-3. Swap ToLeft-4 with NextLeft+5.
 ToLeft-2. Swap NextLeft+4 with Next-1.
 ToLeft-1. Swap ToLeft-1 with Next.

 /* Right and Down are exactly similar to Left. */

 Switch. Do nothing.
 Switch+1. Swap Switch+1 with ToUp-4.

 Next-1. Swap NextUp+4 with Next-1.
 Next. Do nothing.
 Next+1. Do nothing.

A pattern for an empty cell could also be defined, but it would be more efficient for a compiler to shortcut by letting intercell labels go directly to the first non-empty cell in the proper direction. Using this, a compiler from Backflip to SMATINY should be "easy" to write.

Oh, and all this is completely untested. --Ørjan 22:11, 27 Jun 2006 (UTC)

Simulating an arbitrary reversible FSA

In the same "structured label" style as above, here is how to simulate an arbitrary reversible FSA; this should answer the question of the computational class. I am not sure whether this belongs in the article proper in this form.

A is the alphabet of symbols, a an arbitrary one, |A| the number of them. S is the set of states, s an arbitrary one.

t:AxS -> AxS is the one-to-one transition function.

To set the initial state, call Toggle(s) once.

 From(a)+1. Do nothing.

 Before(a,s). Swap From(a)+1 with Before(a,s).
 Before(a,s)+1. Swap From(a)+1 with Before(a,s).
 Before(a,s)+2. Swap Before(a,s)+2 with Toggle(s).
 Before(a,s)+3. Swap Before(a,s)+3 with After(t(a,s))-3.

 Toggle(s)-|A|-1. Swap Toggle(s)+|A|+1 with Toggle(s)-|A|-1.
 Toggle(s)-a. Swap From(a)+1 with Before(a,s).
 Toggle(s). Do nothing.
 Toggle(s)+a. Swap To(a)-1 with After(a,s).
 Toggle(s)+|A|+1. Swap Toggle(s)-|A|-1 with Toggle(s)+|A|+1.

 After(t(a,s))-3. Swap Before(a,s)+3 with After(t(a,s))-3.
 After(a,s)-2. Swap Before(a,s)-2 with Toggle(s).
 After(a,s)-1. Swap To(a)-1 with After(a,s).
 After(a,s). Swap To(a)-1 with After(a,s).

 To(a)-1. Do nothing.

--Ørjan 14:00, 29 Jun 2006 (UTC)