# Translate Prelude to Befunge

This is Weekly Challenge #2. Theme: Translation

Write a program or function that takes in source code for a program in Prelude and outputs code for an equivalent program in Befunge-93. For the program to be equivalent, it should, for any given input, produce the same output as the Prelude program, and halt if and only if the Prelude program halts.

## Input language: Prelude

Python interpreter:

#!/usr/bin/python

import sys

NUMERIC_OUTPUT = True
NUMERIC_INPUT = True

try:
filename = sys.argv[1]
except:
print "Usage:", sys.argv[0], "<filename>"
raise SystemExit

try:
inFile = file(filename)
except:
print "Error when opening", filename
raise SystemExit

# code is kept as a list of voices, each voice a string

code = []
firstLine = True
eof = False
while not eof:
batch = []
while 1:
if line == '': eof = True
if line == '' or line.rstrip() == '*':
break
batch.append(line.rstrip())
maxLen = max([len(b) for b in batch])
batch = [b + ' '*(maxLen - len(b)) for b in batch]
if firstLine:
code = batch
firstLine = False
else:
if len(batch) != len(code):
print "Error in the program: number of voices changes"
raise SystemExit
for i in range(len(batch)):
code[i] += batch[i]

class Stack:
def __init__(self):
self.data = []
def push(self, value):
if self.data or value != 0: self.data.append(value)
def drop(self):
if self.data: self.data.pop()
def top(self):
if self.data: return self.data[-1]
return 0
def pop(self):
value = self.top()
self.drop()
return value

numVoices = len(code)
numInstructions = len(code[0])
stacks = [Stack() for x in range(numVoices)]
topValues = [0 for x in range(numVoices)]
# establish loop couplings
loopStack = []
loops = {}
for cp in range(numInstructions):
curr = [voice[cp] for voice in code]
if curr.count('(') + curr.count(')') > 1:
print "Error in the program: More than one bracket; position", cp
raise SystemExit
if '(' in curr:
loopStack.append((cp, curr.index('(')))
if ')' in curr:
if not loopStack:
print "Error in the program: extraneous closing bracket; position", cp
raise SystemExit
openingPosition, openingVoice = loopStack.pop()
loops[openingPosition] = cp
loops[cp] = openingPosition, openingVoice

if loopStack:
print "Error in the program: not enough closing brackets"
raise SystemExit

# now, actually execute the program
cp = 0 # code pointer
while cp < numInstructions:
# technically we're supposed to shuffle our voices to make sure to perform IO
# in random order, but screw that for now
next_cp = cp+1 # can be modified by ( )
for voice in range(numVoices):
i = code[voice][cp] # current instruction
if i == '^':
stacks[voice].push(topValues[(voice-1) % numVoices])
elif i == 'v' or i == 'V':
stacks[voice].push(topValues[(voice+1) % numVoices])
elif i == '+':
stacks[voice].push(stacks[voice].pop() + stacks[voice].pop())
elif i == '-':
b = stacks[voice].pop()
a = stacks[voice].pop()
stacks[voice].push(a-b)
elif i == '#':
stacks[voice].drop()
elif i == '?':
if NUMERIC_INPUT:
try: num = int(raw_input())
except ValueError: num = 0
stacks[voice].push(num)
else:
if not char: char = '\0'
stacks[voice].push(ord(char))
elif i == '!':
if NUMERIC_OUTPUT:
print stacks[voice].pop()
else:
sys.stdout.write(chr(stacks[voice].pop()))
elif i == '(':
if stacks[voice].top() == 0:
next_cp = loops[cp] + 1
elif i == ')':
openingPosition, openingVoice = loops[cp]
if topValues[openingVoice] != 0:
next_cp = openingPosition + 1
elif i in '0123456789':
stacks[voice].push(int(i))
topValues = [stacks[i].top() for i in range(numVoices)]
cp = next_cp

A Prelude program consists of a number of "voices" which execute instructions simultaneously. The instructions for each voice are on a separate line. Each voice has a separate stack, which is initialized with an infinite amount of zeroes. Execution begins at the leftmost column, and advances one column to the right each tick, except when influenced by ) or ( instructions. The program terminates when the last column is reached.

Prelude spec for this challenge:

Digits 0-9      Push onto the stack a number from 0 to 9. Only single-digit
numeric literals can be used.
^               Push onto the stack the top value of the stack of the above
voice.
v               Push onto the stack the top value of the stack of the below
voice.
#               Remove the top value from the stack.
+               Pop the top two integers from the stack and push their sum.
-               Pop the top two integers from the stack, subtract the topmost
from the second, and push the result.
(               If the top of the stack is 0, jump to the column after the
matching ) after the current column executes.
)               If the top of the stack is not 0, jump to the column after
the matching ( after the current column executes.
?               Read an integer from STDIN.
!               Pop one value from the stack and print it to STDOUT as an
integer.
<space>         No-op


Notes

• v and ^ act cyclically, so the v on the bottom voice will copy the stack element of the top voice, and ^ on the top voice will copy from the bottom voice. Corollary: Both v and ^ duplicate the top of the stack in a single-voice program.
• A ( and its matching ) may be located on different lines. However, a ) will always look at the stack of the voice where the corresponding ( was placed, not the stack where the ) itself is placed.
• The values produced by the ^ and v instructions operate on the values present prior to the completion of any other operations in the same column.
• ? and ! operate differently from the specification found on esolangs.org, so be be sure to test with the slightly modified interpreter provided in this post.

Input is guaranteed to have:

• Matching parentheses
• No more than one parenthesis in a column
• Same number of characters on each line
• At least one line
• No column with more than one I/O (! or ?) instruction
• One linefeed character after the instructions for each voice
• No characters other than the ones mentioned above

## Output language: Befunge-93

Befunge is a stack-based language whose program counter (PC; a pointer to the current instruction) moves freely on a two-dimensional grid. It start in the top left corner, moving to the right. The playfield is toroidal, i.e. PC movement wraps around both edges. Befunge also has a stack which is initialised to an infinite number of zeroes. Befunge has the following operations:

Digits 0-9      Push onto the stack a number from 0 to 9. Only single-digit
numeric literals can be used.
+               Pop the top two integers from the stack and push their sum.
-               Pop the top two integers from the stack, subtract the topmost
from the second, and push the result.
*               Pop the top two integers from the stack and push their product.
/               Pop the top two integers from the stack, divide the second by
the topmost, and push the result. Rounds down.
%               Pop the top two integers from the stack, divide the second by
the topmost, and push the remainder.
!               Pop a value, push 1 if it's zero, push 0 otherwise.
               Pop the top two integers from the stack, push 1 if the second
is greater than the topmost, push 0 otherwise.
>               Set PC direction to right.
<               Set PC direction to left.
^               Set PC direction to up.
v               Set PC direction to down.
?               Set PC direction randomly.
_               Pop a value, if it's 0 set PC direction to right, left otherwise.
|               Pop a value, if it's 0 set PC direction to down, up otherwise.
"               Toggle string mode. While in string mode, push each character's
ASCII value instead of executing it.
:               Duplicate top stack element.
\               Swap top two stack elements.
$Pop and discard top stack element. . Pop a value and output it as an integer. Whitespace not included. , Pop a value and output the corresponding ASCII character. # Jump over the next instruction. g Pop y, pop x, push the character at coordinate (x,y). p Pop y, pop x, pop v, set character at coordinate (x,y) to v. & Read an integer from STDIN and push it. ~ Read a character from STDIN and push it ASCII value. @ End program. You may assume the following characteristics of the Befunge-93 compiler/interpreter: • Integers are unlimited-precision. • It allows grids of any size. • Grid coordinates (for g and p) are 0-based. ## Scoring In order to prevent submissions which simply produce a Prelude interpreter in Befunge and hardcode the Prelude source into it, the goal will be to minimise the size of the resulting Befunge source code. Below are provided a number of Prelude programs. Your translator will be run on all of these. Your score is the sum of the sizes of the Befunge programs, provided all of them are valid. Your translator should not be optimised specifically towards these test cases (e.g. by hardcoding handwritten Befunge programs for them). If I suspect any answer of doing so, I reserve the right to change inputs or create additional ones. ## Sample Inputs Print n-1 down to 0: ?(1-^!)  Logical AND: ? (0) ?(0 ) 1 !  Logical OR:  ? (0) ? (0) 1 1 !  Check parity of input (i.e. modulo 2) of nonnegative number: ?(1-) ^ v v1-^^-!  Square the input:  ^ ^+ ! ?(1-)  Print the nth Fibonacci number, where n = 0 corresponds to 0 and n = 1 corresponds to 1: 0 v+v! 1 ^ ?(1-)  Signum:  1) v # - ! vv (##^v^+) ?(# ^ ##  Division for non-negative inputs: 1 (# 1) v # - 1+) vv (##^v^+) ? v-(0 # ^ # ? 1+ 1-!  Of course, your program must exhibit the same behavior for all cases, even if the sample program's behavior for negative numbers is not specified. Finally, your translator should not be unreasonably long: • It must be contained inside a Stack Exchange post • It should process the sample inputs in under 10 minutes on a typical desktop computer. Note that a numeric input for Prelude or Befunge is given as an optional minus sign followed by one or more decimal digits, followed by a newline. Other input is undefined behavior. You may write your translator in any language. Shortest translated Befunge code wins. ## Leaderboard • Sp3000: 16430 bytes • I don't understand: "Push onto the stack the top value on the stack of the above voice." Doesn't it has to be: "Push onto the stack the top value of the stack of the above voice." – Def Jan 11 '15 at 7:59 • It says prelude executes voices simultaneously, does that mean they're really executed on a separate thread or can I just executed the first commands on all the voices (top to bottom) then the second commands and so on. – Def Jan 11 '15 at 8:08 • @Deformyer I changed it from "on" to "of", but I thought "top value on the stack" wasn't wrong either. As for simultaneity, no you don't need to actually interpret them in parallel. What's important is that they all act on the previous state of the stacks, and no operation in a given column can affect any other operation in that column. – Martin Ender Jan 11 '15 at 11:35 • Don't several of the test cases violate "No column with more than one I/O (! or ?) instruction?" – Fuwjax Jan 14 '15 at 0:06 • @proudhaskeller The 1 is inside a loop, so it may not be pushed. A 0 can come from the infinite amount of 0s that start out on the stacks. – feersum Jan 14 '15 at 2:45 ## 1 Answer # Python 3, will score later from collections import defaultdict from functools import lru_cache import sys NUMERIC_OUTPUT = True @lru_cache(maxsize=1024) def to_befunge_num(n): # Convert number to Befunge number, using base 9 encoding (non-optimal, # but something simple is good for now) assert isinstance(n, int) and n >= 0 if n == 0: return "0" digits = [] while n: digits.append(n%9) n //= 9 output = [str(digits.pop())] while digits: output.append("9*") d = digits.pop() if d: output.append(str(d)) output.append("+") output = "".join(output) if output.startswith("19*"): return "9" + output[3:] return output def translate(program_str): if program_str.count("(") != program_str.count(")"): exit("Error: number of opening and closing parentheses do not match") program = program_str.splitlines() row_len = max(len(row) for row in program) program = [row.ljust(row_len) for row in program] num_stacks = len(program) loop_offset = 3 stack_len_offset = program_str.count("(")*2 + loop_offset stack_offset = stack_len_offset + 1 output = [[1, ["v"]], [1, [">"]]] # (len, [strings]) for each row max_len = 1 # Maximum row length so far HEADER_ROW = 0 MAIN_ROW = 1 FOOTER_ROW = 2 # Then stack lengths, then loop rows, then stacks # Match closing parens with opening parens loop_map = {} # {column: (loop num, stack number to check, is_start)} loop_stack = [] loop_num = 0 for col in range(row_len): col_str = "".join(program[stack][col] for stack in range(num_stacks)) if col_str.count("(") + col_str.count(")") >= 2: exit("Error: more than one parenthesis in a column") if "(" in col_str: stack_num = col_str.index("(") loop_map[col] = (loop_num, stack_num, True) loop_stack.append((loop_num, stack_num, False)) loop_num += 1 elif ")" in col_str: if loop_stack: loop_map[col] = loop_stack.pop() else: exit("Error: mismatched parentheses") def pad_max(row): nonlocal max_len, output while len(output) - 1 < row: output.append([0, []]) if output[row][0] < max_len: output[row][1].append(" "*(max_len - output[row][0])) output[row][0] = max_len def write(string, row): nonlocal max_len, output output[row][1].append(string) output[row][0] += len(string) max_len = max(output[row][0], max_len) def stack_len(stack, put=False): return (to_befunge_num(stack) + # x str(stack_len_offset) + # y "gp"[put]) def get(stack, offset=0): assert offset in [0, 1] # 1 needed for 2-arity ops # Check stack length write(stack_len(stack) + "1-"*(offset == 1) + ":0", MAIN_ROW) pad_max(HEADER_ROW) pad_max(MAIN_ROW) pad_max(FOOTER_ROW) write(">" + to_befunge_num(stack + stack_offset) + "g", HEADER_ROW) write("|", MAIN_ROW) write(">$0", FOOTER_ROW)

write(">", MAIN_ROW)
write("^", FOOTER_ROW)

def put(stack, value=""):
put_inst = (value +
stack_len(stack) +
to_befunge_num(stack + stack_offset) +
"p")

post_insts.append(put_inst)

def pop(stack):
put(stack, "0")

def inc_stack_len(stack):
post_insts.append(stack_len(stack) + "1+")
post_insts.append(stack_len(stack, put=True))

def dec_stack_len(stack):
post_insts.append(stack_len(stack) + ":0-") # Ensure nonnegativity
post_insts.append(stack_len(stack, put=True))

# Technically not necessary to initialise stack lengths per spec, but it makes it
# more portable and easier to test against other Befunge interpreters

for stack in range(num_stacks):
write("0" + stack_len(stack, put=True), MAIN_ROW)

for col in range(row_len):
post_insts_all = []

loop_start = False
loop_end = False

if col in loop_map:
if loop_map[col][2]:
loop_start = True
else:
loop_end = True

if loop_start:
loop_row = loop_offset + 2*loop_map[col][0]
get(loop_map[col][1])

elif loop_end:
get(loop_map[col][1])
write("!", MAIN_ROW)

for stack in range(num_stacks-1, -1, -1):
char = program[stack][col]
post_insts = [] # Executed after the gets in reverse order, i.e. last added first

if char in " ()":
continue

# Pre-inc, post-dec
elif char.isdigit():
inc_stack_len(stack)
put(stack, char)

elif char == "?":
inc_stack_len(stack)
put(stack, "&")

elif char == "!":
get(stack)
post_insts.append(".91+," if NUMERIC_OUTPUT else ",")
pop(stack)
dec_stack_len(stack)

elif char == "#":
pop(stack)
dec_stack_len(stack)

elif char in "+-":
get(stack, 1)
get(stack)
post_insts.append(char)
pop(stack) # This one first in case of ! or 1!
post_insts.append(stack_len(stack) + ":1-:1\\+") # Ensure >= 1
post_insts.append(stack_len(stack, put=True))
put(stack)

elif char in "^v":
offset = -1 if char == "^" else 1

get((stack + offset) % num_stacks)
inc_stack_len(stack)
put(stack)

else:
exit("Error: invalid character " + char)

post_insts_all.append(post_insts)

while post_insts_all:
write("".join(post_insts_all.pop()), MAIN_ROW)

if loop_start or loop_end:
loop_row = loop_offset + 2*loop_map[col][0]

write("|>", MAIN_ROW)

if loop_start:
write(" ^", loop_row)
write(">", loop_row + 1)

else:
write("<", loop_row)
write(" ^", loop_row + 1)

write("@", MAIN_ROW)
return "\n".join("".join(row) for row_len, row in output)

if __name__ == '__main__':
if len(sys.argv) < 3:
exit("Usage: py -3 prefunge.py <input filename> <output filename>")

with open(sys.argv[1]) as infile:
with open(sys.argv[2], "w") as outfile:


Run like py -3 prefunge.py <input filename> <output filename>.

It's been a slow week for me, so I was finally bored enough to tackle this six-month old question. I'd ask why nobody else tried, but I'm still feeling the pain from debugging (and there's probably still bugs remaining for all I know).

The question doesn't provide a Befunge-93 interpreter, so I used this one, which is slightly different from the spec. The two key differences are:

• If a char doesn't exist in a given row of the program, then you can't write to that row. This means you'll need to hit Enter several times to introduce enough newlines at the end. If you see NaNs in the output, this is the most likely cause.

• Grid cells aren't preinitialised to zero - for convenience I've included some preinitialisation in the Befunge outputs, but since it's not necessary I might take it away when I start scoring.

The core layout of the output programs is this:

v [header row]
> [main row]
[footer row]
---
|
| rows for loops (2 per loop)
|
---
[stack length row]
---
|
| rows for stack space (1 per voice)
|
---


The stack space is outside the program, hence the newline Enter-spamming comment from earlier.

The core idea is to assign each voice a row which serves as its stack. To maintain these stacks, we also have a special stack length row where the length of each stack is recorded in a cell along the row. The program is then a lot of gets and puts, e.g. for printing the process is:

• Get the cell at y = stack_row[stack], x = stack_length[stack]
• Perform .91+,, i.e. print as integer then print a newline
• Replace the cell at the above coords with 0 (to simulate popping)
• Decrement stack_length[stack]

To perform the simultaneous evaluation of a column, all necessary cells are read and their values are kept on the stack before any cells are written to (e.g. for the printing example, there may be more instructions in between the first and second steps).

, which is greater than, is employed to make sure the stack lengths never go negative, and for pushing 0s when the stack is empty. This is where the clearly visible branching comes from, but I've got an idea that'll remove the branching, which should remove a great deal of whitespace from the first and third rows.

For the loops, because Prelude loops can jump both ways, we use two rows per loop in a configuration like this:

       >v                     >v
(cond) |>  (program)  (cond) !|>

^                     <
>                       ^


These loops currently make up the majority of the bytes, but can easily be golfed down by placing them into the codebox with p, which I plan to do after I'm happy that the translator is working correctly.

Here's some example output for ?(1-^!), i.e. print n-1 down to 0:

v                        >6gv>v                      >6gv      >6gv                                 >6gv                   >6gv                           >6gv >v
>005p05g1+05p&05g6p05g:0|  >|>05g1+05p105g6p05g1-:0|  >05g:0|  >-005g6p05g:1-:1\+05p05g6p05g:0|  >05g1+05p05g6p05g:0|  >.91+,005g6p05g:0-05p05g:0|  >!|>@
>$0^ >$0^      >$0^ >$0^                   >$0^ >$0^
^                                                                                                                                <
>                                                                                                                                  ^


Square-the-input:

v                                >8gv      >8gv             >v      >6gv                                   >8gv      >8gv        >7gv      >7gv                                                            >8gv >v      >7gv
>005p015p025p25g1+25p&25g8p25g:0|  >25g:0|  >05g1+05p05g6p|>05g:0|  >15g1+15p15g7p25g1+25p125g8p25g1-:0|  >25g:0|  >15g1-:0|  >15g:0|  >+015g7p15g:1-:1\+15p15g7p-025g8p25g:1-:1\+25p25g8p25g:0|  >!|>15g:0|  >.91+,015g7p15g:0-15p@
>$0^ >$0^                     >$0^ >$0^      >$0^ >$0^      >$0^ >$0^         >$0^ ^ < > ^  Division (small inputs are recommended): v >91+gv>v >94+gv >95+gv >95+gv >93+gv >93+gv >93+gv >93+gv >v >93+gv >93+gv >v >92+gv >v >92+gv >92+gv >91+gv >93+gv >91+gv >92+gv >92+gv >91+gv >91+gv >92+gv >v >91+gv >91+gv >91+gv >v >95+gv >95+gv >95+gv >009p019p029p039p049p09g1+09p109g91+p29g1+29p&29g93+p39g1+39p&39g94+p09g:0| >|>39g:0| >009g91+p09g:0-09p29g1+29p29g93+p49g1+49p149g95+p49g1-:0| >49g:0| >29g1-:0| >29g:0| >-029g93+p29g:1-:1\+29p29g93+p+049g95+p49g:1-:1\+49p49g95+p29g:0| >29g:0| >19g1+19p19g92+p|>29g:0| >09g1+09p109g91+p19g1+19p19g92+p29g1+29p029g93+p29g:0| >!|>19g:0| >029g93+p29g:0-29p|>19g:0| >09g1+09p09g91+p019g92+p19g:0-19p19g:0| >019g92+p19g:0-19p29g1+29p29g93+p09g:0| >009g91+p09g:0-09p19g1+19p19g92+p29g:0| >19g1+19p19g92+p09g:0| >19g1+19p19g92+p19g1-:0| >19g:0| >09g1-:0| >09g:0| >-009g91+p09g:1-:1\+09p09g91+p+019g92+p19g:1-:1\+19p19g92+p029g93+p29g:0-29p19g:0| >!|>09g1+09p109g91+p09g1-:0| >09g:0| >+009g91+p09g:1-:1\+09p09g91+p09g:0| >!|>49g1+49p149g95+p49g1-:0| >49g:0| >-049g95+p49g:1-:1\+49p49g95+p49g:0| >.91+,049g95+p49g:0-49p@ >$0  ^        >$0 ^ >$0  ^      >$0 ^ >$0  ^      >$0 ^ >$0  ^      >$0 ^ >$0  ^                                                     >$0 ^ >$0  ^                          >$0 ^ >$0  ^                                       >$0 ^ >$0  ^                     >$0 ^ >$0  ^      >$0 ^ >$0  ^      >$0 ^ >$0  ^                           >$0 ^ >$0  ^                                     >$0 ^ >$0  ^      >$0 ^ >$0  ^
^                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        <
>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          ^
^                                                                        <
>                                                                          ^
^                                                                                                                                                                                                                                                                                                                                              <
>                                                                                                                                                                                                                                                                                                                                                ^


There's also a bunch of other minor optimisations that come to mind, like replacing 07p07g with :07p, but I'm taking this one step at a time :)

• So. Much. Free. Time. – Optimizer Jul 7 '15 at 15:37
• Will score later` 2 years and counting! :) – HyperNeutrino Sep 15 '17 at 19:07