Compile Quarterstaff to BF

6

2

Quarterstaff repo here with additional quarterbf interpreter: rather bereft of documentation, however, but it does contain the two interpreters

you can go to https://tio.run/#quarterstaff to run quarterstaff programs online. however, the TIO BF implementation seems to have limited cells, according to the documentation


The title is rather descriptive, except that it doesn't describe what Quarterstaff and BF are. For this challenge, I have created two languages: Quarterstaff, and a dialect of BF that probably already existed in its exact form, but I wanted to be certain, especially with the I/O format, that it would work, called QuarterBF. In this challenge, you will compile a program written Quarterstaff to QuarterBF (but the underlying conversion should work for any generic BF dialect with byte cells and an infinite tape and such).

I have created interpreters for both of these. However, should you find the spec for one of them here conflicts with the interpreter, the spec is prioritised for the challenge (the interpreters should just be helping you out here)

First, the QuarterBF spec, since it will be easier to explain some of the Quarterstaff concepts afterwards (I cribbed some of this from the esolangs page for Brainf***):

BF spec

Brainfuck operates on an array of memory cells, also referred to as the tape, each initially set to zero. These memory cells can each hold an integer between 0 and 255, inclusive, and the tape extends infinitely to the right (some implementations will use a limited number of cells, hence I made my own to be sure / make an appropriate interpreter easy to find). There is a pointer, initially pointing to the first memory cell. There are no cells to the left of the first memory cell, and attempting to move further left is undefined behaviour. The commands are:

> : move the pointer to the right
< : move the pointer to the left
+ : increment the cell under the pointer, unless the cell is 255, in which case set cell to 0
- : decrement the cell under the pointer, unless the cell is 0, in which case set cell to 255
, : input a character code into the cell under the pointer (described more below)
. : output the character that the integer in the cell under the pointer represents
[ : Jump past the matching ] if the cell under the pointer is 0 
] : Jump back to the matching [ if the cell under the pointer is nonzero

In QuarterBF input is interactive. The exact mechanism this works by could be gleaned by reading the source if you wanted, but it's not totally necessary. The important points: it sets a cell to the character code of an input character, sets to 0 on EOF, and to 10 for end of line newlines (which is the newline charcode)

Either way, you don't have to worry so much about how input works, because the values of ? and ! translate essentially perfectly to the values , and . anyway.

Quarterstaff spec:

Quarterstaff's memory consists of registers. one of these registers is called "value", and the others are named variables. variables are case sensitive. Variables can be referenced before assignment and are initially zero (alternately, referencing a variable before assignment does nothing, because if it hasn't been assigned yet, it means it has a value of zero, therefore adding zero has no effect).

[a string of digits] : add the number those digits represent to the value
[a string of letters not preceded by >] : add the variable that the name represents to value
[a string of letters preceded by >] : set the variable to the current value, set value to 0
. : set value to zero
- : multiply value by -1
? : add to value the amount that the underlying bf implementation would set a cell to when , is executed
! : output the character with the charcode corresponding to value.
[ : Jump past the matching ] if value is 0
] : Jump back to the matching [ if value is nonzero
([...] is a while loop)
{ : Jump past the matching } if value is nonzero 
} : Jump back to the matching { if value is 0
({...} is a while-not loop)
(, |, ): part of an if else construct...
[any characters not mentioned here] separator between commands; doesn't execute anything, but separates variables or numbers

Explanation of if:

if-style 1:

when coming to this paren, check if value is zero or not
v
(...)
  ^  if value was nonzero, execute the commands within

either way, then continue execution after the )

if-style 2:

when coming to this paren, check if value is zero or not
v
(...|...)
  A   B
if the value is nonzero, execute the subprogram designated A. else execute the one designated B.
then, continue execution after the closing )

(...) is equivalent to (...|)

The challenge

Taking a quarterstaff program as input, compile it to BF; output a program which functions the same, but in BF.

i.e.

  • it halts if and only if the inputted program halts

  • outputs the exact same text as it.

  • if it doesn't halt, it should print the text that the original program prints in finite time, in finite time (it shouldn't put output into a buffer and then print it when it stops executing or something)

Allowances and some restrictions:

  • you may assume that input to the outputted program is always in printable ASCII and ASCII whitespace (and EOF. Basically, no need to worry about any characters >255 overflowing or whatever), and that the quarterstaff program will never try to output anything other than printable ASCII and ASCII whitespace.

  • you may assume the inputted program is only ascii printables and ascii whitespace

  • you may not assume that the variables and values only go up to 255. you need to implement infinite variables and accumulator

  • basically, you don't get to limit anything (except possible i/o characters). your bf spec has infinite cells, you can use them!

  • you may assume that the Quarterstaff program has fully matched brackets, and does not invoke undefined behaviour (e.g. trying to output non-ASCII like I mentioned earlier)

  • you should not invoke undefined behaviour in your outputted bf program. just because I included an interpreter doesn't mean you get to exploit any bugs or lack of exceptions for undefined behaviour. When the spec in this question and implementation differ, follow the question spec. This includes when the interpreter technically could suffer from recursing too deep. doesn't mean you get to assume that a program never recurses that much.

Scoring is by the length of the program, shorter is better; (this is not metagolf, the length of your bf programs does not matter, as long as they work)

test cases:

prime tester (slightly different from my answer on the prime challenge; a space was replaced with a newline):

10-?[-38a a a a a a a a a a>a10-?]a>b
b[>b>d a>c c[1>c1d>d b d(.>e|>d1>e)c]e f>f1b]2-f(.|1)48!

cat (prints each line after you input it, then exits on EOF)

?[!?]

prints a newline

10!

also prints a newline

5 5!

truth machine:

49-?{49!}49! 

Destructible Lemon

Posted 2018-03-23T10:06:23.030

Reputation: 5 908

I think you forgot to mention that ! resets the value to 0. – wastl – 2019-04-03T17:52:44.673

Answers

2

Python 3.8 (pre-release), 769 bytes

import base64,zlib
exec(zlib.decompress(base64.b85decode('c$|e(O>dkq5WVv&NG^sQ59(GuRK#}Fdv=dG)b#;{MMCnD$WWA)xWB#6EcrN8>cx!5<2TRq9{u_0F--aRYn0)X-RUJ}NBuc_(1O`p??iUc`>fZ(TQ;OzP-HE8guxkB&RDAgS--{(feY*i#mIVtV^(BvOJt)Kq%1RAA_5p7)CPe{;BX-10FW+u3dSkV4A4M;_<vo>uMN==IgxdbA%B*$9OOCghdi9Bt{>XQ`$81vwk&MJzrXQ!N99ZLqfM)IHZH|WS>0Z-D}}^Zs&Q)jp$ey_Ey}Xa^1jRG`l!#%b8(b=D&|_>RpV)DPhIoVPsJ>cWm(?L@?HxicC!=)>rJC)>V)OxK7#!+M<?k1rq!JYc4?xqYUv}=lnU5kyj%8?N^e3|;i1bIFUlk;&-Df|N6Ri1VzjS!oB_%|4=~YpjG;cP&pF7U*8MOQ1Ng77OTQbU1<1#i=ep787@UHXD@-ty#%}E@Dq{~_p%Bzk7vh0jD%eza$i3<01$tQk;y4jbpI3TP1jWW08<M3Q-oHABlXH?2E)Y0O^P-diDbU*b(AEcAmvB`wp8@s<7csy4$ir*tl6z}j880LTVI*oG5cqx=hipi=w+Ptp@%k$OA{iXS2pkfF4fs-I)5cj*@zt$c;!7!3gBIt~W%&c?HhT(5j!u~6I?(m*5D^$cbd1YG6x9@(Vf4*(Dwh4HuQmTU?%+AO-+#HpM#QrG3m~&3+y')))

Try it online! Test suite (also executes brainfuck)

OK, so this is a version following the specifications, but the rules seem to be missing that ! resets the value to 0. So, at a cost of two bytes, here is a fixed version:

Python 3.8 (pre-release), 771 bytes

import base64,zlib
exec(zlib.decompress(base64.b85decode('c$|e(O>dkq5WVv&NG^sQ59(GuRK#}Fdv=dG)b#;{MMCnD$WWA)xWB#6EcrN8>cx!5<2TRq9{u_0F--aRYn0)X-RUJ}NBuc_(1O`p??iUc`>fZ(TQ;OzP-HE8guxkB&RDAgS--{(feY*i#mIVtV^(BvOJt)Kq%1RAA_5p7)CPe{;BX-10FW+u3dSkV4A4M;_<vo>uMN==IgxdbA%B*$9OOCghdi9Bt{>XQ`$81vwk&MJzrXQ!N99ZLqfM)IHZH|WS>0Z-D}}^Zs&Q)jp$ey_Ey}Xa^1jRG`l!#%b8(b=D&|_>RpV)DPhIoVPsJ>cWm(?L@?HxicC!=)>rJC)>V)OxK7#!+M<?k1rq!JYc4?xqYUv}=lnU5kyj%8?N^e3|;i1bIFUlk;&-Df|N6Ri1VzjS!oB_%|4=~YpjG;cP&pF7U*8MOQ1Ng77OTQbU1<1#i=ep787@UHXD@-ty#%}E@Dq{~_p%Bzk7vh0jD%eza$i3<01$tQk;y4jbpI3TP1jWW08<M3Q-oHABlXH?2E)Y0O^P-diDbU*b(AEcAmvB`wp8@s<7csy4$ir*tl6z}jB~D&Q%)&^NK_gK9FcI01aBmUd-{bXf07~*WxDjY15*zlV$fk|6qT;Jtx5SrHtR5}SrOWaM(rxw>k|Lcj%XOgZ-60|{gy<NThbXEkG{fkd=~OKHPhV^PbKJppa=-s_iH(S5nf(R5Kqbo')))

Try it online! Test suite (also executes brainfuck)

wastl

Posted 2018-03-23T10:06:23.030

Reputation: 3 089