Talk:Jolverine
Could you be more specific about how the wheel and the example program work? The way I understand it, the first * executes "left", the second star executes "right", and then the instruction pointer continue to the right until it's out of the picture, and the program terminates; I don't see how the IP can know it's supposed to follow the southeast \ path. --Koen (talk) 23:06, 11 September 2012 (UTC)
- In the example program, the first instruction executed is "rot", because the two hyphens in front of the star have caused the wheel to rotate two positions. I added an example of what happens to the wheel when some non-stars and stars are executed; hopefully that will clarify the behaviour. (And you can run the reference interpreter with the -d flag to watch a trace of the program, if it needs even more clarification.) Chris Pressey (talk) 01:07, 12 September 2012 (UTC)
The term "mod 3 - 1" is still ambiguous to me. Does adding 0 and 0 result in 0 or in -1 ? (The former I would in mathematical terminology call (mod 3), including the parentheses.) --Ørjan (talk) 06:19, 12 September 2012 (UTC)
- Wasn't quite sure what to call it, which is why I put it in scare quotes. It acts kind of like (mod 3), but where the result of (mod 3) is always 0, 1, or 2, here the result is always -1, 0, or 1. At any rate, I replaced that weird phrase with just the rules for addition. If you know an accepted mathematical term for it, feel free to add it to the page. Chris Pressey (talk) 12:15, 12 September 2012 (UTC)
- As far as I am concerned, working "mod 3" means you consider -1, +2, +5, etc. to be equivalent. Whether you choose to use -1 or +2 to represent that equivalency class is up to you; as long as you make it clear that dx and dy can only hold values in the set {-1, 0, +1}, I don't see a problem with "addition on these values is defined modulo 3". The precision "it wraps around if the value exceed the range -1..1" is always good in case the reader doesn't know what modulo means, though. --Koen (talk) 13:37, 12 September 2012 (UTC)
- OK, fuzzy memories from that coding theory class I took are coming back to me :) Yes, I suppose it is just (mod 3), I'm just saying -1 instead of 2. But there's a justification for this: dx and dy really do need to be negative at some point. (And trying to explain that by saying "dx=2 makes the IP move in the opposite direction as dx=1" is probably too convoluted.) I'll leave it as it is for now. Chris Pressey (talk) 13:56, 12 September 2012 (UTC)
- As far as I am concerned, working "mod 3" means you consider -1, +2, +5, etc. to be equivalent. Whether you choose to use -1 or +2 to represent that equivalency class is up to you; as long as you make it clear that dx and dy can only hold values in the set {-1, 0, +1}, I don't see a problem with "addition on these values is defined modulo 3". The precision "it wraps around if the value exceed the range -1..1" is always good in case the reader doesn't know what modulo means, though. --Koen (talk) 13:37, 12 September 2012 (UTC)
Trying to write a loop
I still haven't been able to write a loop in this language, but the more I think about it, the more I am convinced it is possible, just difficult. I noted the two programming techniques I've been using, on the page, but there are two other ideas that might be useful for anyone trying this. One is to define a variant of the language (call it Jolverine Super Wimp Mode or something) which has no wheel at all, but the symbols <>+xyio execute the instructions left, right, rot, adddx, adddy, input, and output directly. It should be possible to write a loop in this variant, or even show that it is Turing-complete; of course, if it is not possible in this variant, it's not possible in Jolverine either. The other idea is to find, through reasoning, trial and error, and sufficient scratch space on the tape, program fragments (ideally, ones which form only straight lines in the program) which perform some desired operation then bring the wheel back to where it was when it started. This would mean executing most of the available instructions "gratuitously", for no purpose other than the rearrange them on the wheel (thus the need for scratch space). But another difficulty here is that you probably don't want to go executing output and input "gratuitously" -- especially input. (But you may not need to, if they always end up in the middle of the wheel.) Chris Pressey (talk) 12:54, 12 September 2012 (UTC)
- I forgot to add: that's not enough. Like Gemooy there is the problem of re-entering a loop, although it seems more likely to be solvable here than in Gemooy. You need to make one of the stars do something different on the second time through the loop. For instance, in
A B
...------*---...---*
/ \
...loop... ...loop...
...loop...
you need to make the star at A not change dy the first time, but do change dy the second time. An adddy with a 0 on the tape the first time, but a 1 on the tape the second time, will do the trick. The problem is really making sure that, on the second iteration, the wheel configuration at A-B is the same as (or compatible with) the wheel configuration that was used there on the first iteration. (And of course, combining this with caring about what you leave on the tape makes it even trickier.) Chris Pressey (talk) 14:22, 12 September 2012 (UTC)
- Maybe things would be easier with the addition of a no-op instruction in the wheel? --Koen (talk) 15:54, 12 September 2012 (UTC)
Some buildings blocks based on your two ideas that I hope you can use: The init sequence of comands below rearranges the wheel order to
left adddx input output adddy rot right
Then, you can emulate something like your direct version commands by the other sequences, which all rearrange the wheel back to this form with the same parity of top/bottom. Note that left and right are emulated as moving _two_ steps; that way there are always 0 valued cells between the data ones, which are used to be able to move the adddx and adddy commands on the wheel without effect. Apart from (naturally) the adddx and adddy emulations, these should all work in a straight line.
init: left adddy right rot rot rot left right left(*2): left left left right right(*2): left right right right rot: rot rot rot rot left right adddx: adddx rot rot rot left right adddy: rot rot rot adddy rot rot rot rot rot rot left right input: input right adddx left left right output: rot rot rot output right adddy left rot rot rot left right
--Ørjan (talk) 20:27, 12 September 2012 (UTC)
- I just got a hunch that you might want the adddx and adddy emulations to do their actual turning at the same spot in the 7-cycle. To achieve this you can use the following for adddx instead:
adddx: left adddx right rot rot rot adddx rot rot rot left right
I converted the above to strings of stars and dots:
init: *...*...**...***......*..... left(*2): *......*.....*......* right(*2): *.....*......**...... rot: .....*.*.....**......*....*. adddx: **...*......***....**......**.*......*.... adddy: .....*.*.....*.....*.*......*.....**.....**......*...*.. input: ..*...*..*......*...*......* output: .....*.*.....*....**......*...*......*...**......**.....
I used the below Haskell program:
{-# LANGUAGE RecordWildCards #-}
import Data.Functor((<$>))
data Status token = Status { nextTop :: Bool, pos :: Int, wheel :: [token] }
deriving (Show)
startWheel = words "left right rot adddx adddy input output"
startStatus = Status True 0 startWheel
workingWheel = words "left adddx input output adddy rot right"
workingStatus = Status True 0 workingWheel
replacements = [
("init", startStatus, "left adddy right rot rot rot left right"),
("left(*2)", workingStatus, "left left left right"),
("right(*2)", workingStatus, "left right right right"),
("rot", workingStatus, "rot rot rot rot left right"),
("adddx", workingStatus, "left adddx right rot rot rot adddx rot rot rot left right"),
("adddy", workingStatus, "rot rot rot adddy rot rot rot rot rot rot left right"),
("input", workingStatus, "input right adddx left left right"),
("output", workingStatus, "rot rot rot output right adddy left rot rot rot left right") ]
encodeTokens :: (Eq token) => Status token -> [token] -> String
encodeTokens Status{..} []
| pos == 0
= ""
encodeTokens s@Status{..} ts
| t:_ <- ts, wheel !! pos == t
= '*' : encodeTokens (stepChar s '*') (drop 1 ts)
| otherwise
= '.' : encodeTokens (stepChar s '.') ts
stepChar :: (Eq token) => Status token -> Char -> Status token
stepChar s@Status{..} c
| c == '*' = Status (not nextTop) pos' wheel'
| otherwise = s { pos = pos' }
where
pos' = (pos+1) `mod` length wheel
wheel' = [curTok | nextTop] ++ before ++ after ++ [curTok | not nextTop]
(before, curTok : after) = splitAt pos wheel
main = mapM_ (putStrLn . displayEncoding) replacements
where
displayEncoding (desc, st, is) = desc ++ ": " ++
encodeTokens st (words is)
--Ørjan (talk) 10:38, 13 September 2012 (UTC)
Duh. I tried finding out how to remerge paths, and realized why it's impossible to do so cleanly: Jolverine is reversible. :P
This doesn't mean it cannot be TC, but it means a direct embedding of flow control like brainfuck's isn't going to work. Reversible Brainfuck (which I suspect is TC, although it hasn't been proven) might still be doable in a relatively direct way. --Ørjan (talk) 17:58, 13 September 2012 (UTC)
- Impressive analysis, and I thank you for it. It is reversible, isn't it? That was totally not intentional. And not really desired.
- I had a realization of my own (which you probably already saw): the wheel has 70560 possible configurations (7! arrangements of instructions, times 7 wheel positions, times 2 possibilities for where to reinsert an executed instruction), and you can think it as a rather large state machine, with 70560 states, where each state can transition to two other states (depending on whether it executed an instruction, or not.)
- To answer Koen's question, I don't think adding a nop will help much, or at all, really. However, I did leave in an "escape hatch" by leaving "output -1" undefined. It could be defined to do something irreversible. My working proposal is that it delete the current tape cell entirely, removing it from the tape. Of course, when that happens, the tape head has to move either to the left or the right of the now-missing cell. The first time a cell is deleted, the head moves right; the second time, left; the third time, right, and so forth, alternating like this.
- I think this is quite squarely in the spirit of Jolverine, and certainly it's irreversible. Whether it helps or not is, uh, not my primary concern. Chris Pressey (talk) 02:36, 14 September 2012 (UTC)
- To that proposal I must say "Argh!" It might work I guess. If you do that operation in the middle of the tape data it is going to require a lot of reshuffling to fix things; if you do it at the end you have to move back and forth, but then you have to do that in the former case anyway. I guess the latter is easier. --Ørjan (talk) 03:19, 14 September 2012 (UTC)
- Yes, it's evil, I know, I apologize... :) (Especially considering that doing it at one end of the tape would require a loop to traverse the tape in the first place.) Also, I just realized that it's not as irreversible as I thought -- assuming you know a tape cell was deleted, you also know it must have contained a -1. Probably better to affect one of the adjacent cells, and probably better to affect it by just overwriting it, rather than deleting it entirely and messing up your nicely-arranged tape. Although, I'm also OK with the language being isomorphic to Reversible Brainfuck (if it is), for now, until I think about it a bit more. (I actually suspect RBf is not TC right now, but that's entirely a hunch.) Chris Pressey (talk) 04:28, 14 September 2012 (UTC)
- To that proposal I must say "Argh!" It might work I guess. If you do that operation in the middle of the tape data it is going to require a lot of reshuffling to fix things; if you do it at the end you have to move back and forth, but then you have to do that in the former case anyway. I guess the latter is easier. --Ørjan (talk) 03:19, 14 September 2012 (UTC)
Here is an inverted Truth-machine in Jolverine Super Wimp Mode:
iyy>o+y
xo +
x x
+
+ x
y y
By "inverted" I just mean the roles of 0 and 1 are swapped. The loop which outputs the infinite number of 0's also leaks tape, to get around the reversibility problem. Anyway, by combining this with Ørjan's mapping to stars and dots (and some patience) it ought to be possible to write an inverted truth-machine in Jolverine. Chris Pressey (talk) 21:38, 15 September 2012 (UTC)
- Uninverting...
+y o
i +
+ +
y>+oy
x +
x x
+
+ x
y y
More building blocks
I made a few more building blocks, and a table which should give enough information to put them together:
(EDIT: Added a column giving 7 -> 1 character wimpmode abbreviations. EDIT2: Added a couple more; fixed serious bugs in incdx and decdx --Ørjan (talk) 12:22, 22 September 2012 (UTC))
init: left adddy right rot rot rot left right
$... *...*...**...***......*.....
initskew: rot adddy rot rot left right
..*.*'.*......*......**.....
left(*2): left left left right
<.. *......*.....*......*
right(*2): left right right right
>.. *.....*......**......
rot: rot rot rot rot left right
+... .....*.*.....**......*....*.
rot rot: rot rot left right
-.. .....*.*......*....*.
adddx: left adddx right rot rot rot adddx rot rot rot left right
..x... **...*......***...|**......**.*......*....
adddy: rot rot rot adddy rot rot rot rot rot rot left right
..y..... .....*.*.....*....|*|*......*.....**.....**......*...*..
input: input right adddx left left right
i... ..*...*..*......*...*......*
output: rot rot rot output right adddy left rot rot rot left right
o....... .....*.*.....*....**......*...*......*...**......**.....
incdy: right rot adddy rot rot adddy left rot rot rot left right
..v..... ......*......*....|**......*.**.....*....**......**.....
decdy: left rot rot adddy rot adddy right rot rot rot left right
.^..... *....**....|*|*.....*.....*..*....***......*.....
incdx: left adddx adddy rot adddx rot rot adddy right rot rot rot left right
...)... **.****......*..*..*..*....**.*.....*.....
decdx: right adddx rot rot adddx rot left rot rot rot left right
..(.... ......*..*..*.*...|**..*...*......**......*.*....
All of the Jolverine fragments are a multiple of 7 long, and have an even number of *'s, so should be self synchronizing if you concatenate them.
For all those which can change direction, the * which changes direction is shown by bordering it with one or more |s (EDIT: actually there wasn't room in the incdx code --Ørjan (talk) 12:22, 22 September 2012 (UTC)). These all occur at the same position in the 7-cycle, in order to ensure that everything automatically stays in phase in the program at large. If several possible IP paths cross at such a direction-changing spot, they all need to be using the same fragment, both before and after.
The new building blocks are incdx, decdx, incdy and decdy, which adjust dx or dy *unconditionally* in the obvious way, something which should help with moving the IP around.
--Ørjan (talk) 20:32, 16 September 2012 (UTC)
Adding ^ and v as wimpmode characters for decdy and incdy respectively, I made the following construction: (EDIT: Use accurate 7 -> 1 scaling.)
^
. .
, .
. . .
. . .
. . .
. . . .
. . . .
y.....,,,,,,,,..y
. .
. .
. ,
. ,
. ,
, ,
, ,
,
, ,
, ,
. ,
. ,
. ,
. .
. .
y.....,,,,,,,,..y
. . . .
. . . .
. . .
. . .
. . .
. .
. .
v
IPs coming from upper left or lower left will leave to the upper right or lower right respectively, except when the current tape is 0, when they will cross over. I believe this is just the building block needed to make a reversible "tritfuck" [ ]. --Ørjan (talk) 16:11, 17 September 2012 (UTC)
So here is the basic layout for a [] loop. If you think this is large, just imagine the 1 -> 7 expansion to non-wimpmode Jolverine:
B
E
F
O
R
E ^
. . ^
L , . . .
O . . . .
O . . . .
P . . . .
. . . . .
. . . . ,
y.....,,,,,,,,..y ,
. . ,
. . ,
. , ,
. , ,
. , ,
, , ,
, , ,
, ,
, , ,
, , ,
. , ,
. , ,
. , ,
. . ,
. . ,
y.....,,,,,,,,..y ,
. . . . ,
. . . . ,
. . . . ,
. . . . ,
. . . . ,
) . . I ,
. . . N ,
. v S .
. I .
, D .
. E )
. .
. L .
. O .
. O ,
^ P ,
. ,
, C ,
, O ,
, D ,
, E ,
, . ,
, . ,
, . .
, ) .
, . (
, . .
, . .
, , .
, , .
, , A
, , F
, , T
, , E
, , R
, ,
, , L
, , O
. , O
. , P
. ,
. ,
. .
^
--Ørjan (talk) 18:25, 17 September 2012 (UTC)
Implementation does not seem to handle input as specified
By my reading of the implementation, input is actually added to the current cell rather than stored in it. Is this intentional? --Ørjan (talk) 13:29, 18 September 2012 (UTC)