Translate Prelude to Befunge

Question

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:
    # read batch of lines
    batch = []
    while 1:
        line = inFile.readline()
        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:
                char = sys.stdin.read(1)
                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

Answer 1

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)

        pad_max(HEADER_ROW)
        pad_max(MAIN_ROW)
        pad_max(FOOTER_ROW)

        write("v", HEADER_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]

            pad_max(HEADER_ROW)
            pad_max(MAIN_ROW)
            pad_max(loop_row)
            pad_max(loop_row + 1)

            write(">v", HEADER_ROW)
            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:
            outfile.write(translate(infile.read()))

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 :)