Given a truth table, output a Stackylogic program that satisfies it

Question

Stackylogic is a programming language I made up in a previous challenge: Run Stackylogic. Read that post for full details and examples, but here is how it works paraphrased:

Stackylogic takes 0's and 1's for input and outputs a single 0 or 1 upon completion.

A program consists of lines that only contain the characters 01? as well as exactly one < at the end of one of the lines. Lines may not be empty and the line with the < must have at least one 0, 1, or ? before it.

Here's a sample program that computes the NAND of two bits:

1
?<
11
?
0

Every line in a program is considered a stack, with the bottom on the left and the top on the right. Implicitly, there is an empty stack (i.e. empty line) before the first line in a program and after the last line.

The <, called the cursor, marks the stack to start on when a program is run. Execution proceeds as follows:

1. Pop the top character off the stack the cursor is currently pointing to.

   • If the character is ?, prompt the user for a 0 or a 1 and act as if that was the character.
   • If the character is 0, move the cursor one stack up (to the line above the current line).
   • If the character is 1, move the cursor one stack down (to the line below the current line).

2. If the stack the cursor moves to is empty, output the last value that was popped off a stack (always a 0 or 1), and end the program.

3. Else, if the stack the cursor moves to is not empty, go back to step 1 and repeat the process.

The key thing to realize for this challenge is that all Stackylogic programs equate to a truth table. Some predetermined number of boolean values are input and exactly one boolean is deterministically output.

So your task is to produce a Stackylogic program that satisfies or simulates, i.e. has the same output as any given truth table. But it's not obvious that Stackylogic can simulate any truth table, so here's a proof by induction:

Base Case

The two 0-input truth tables are the tables that always output 0 or 1. The Stackylogic equivalents of these tables are 0< and 1< respectively.

Inductive Step

Assume Stackylogic can simulate any N-input truth table. Let M = N + 1.

An M-input table, T, can be expressed as two N-input tables, T₀ and T₁, plus the additional input bit B. When B is 0, the result of T₀ is used. When B is 1, the result of T₁ is used.

For example, the 3-input truth table corresponding to the pseudocode

if B:
    result = x OR y
else:
    result = x NAND y

is

B x y | result
0 0 0 | 1
0 0 1 | 1
0 1 0 | 1
0 1 1 | 0
1 0 0 | 0
1 0 1 | 1
1 1 0 | 1
1 1 1 | 1

which is really the two 2-input truth tables for NAND and OR stacked atop each other with the muxing bit B.

Let S₀ and S₁ be the Stackylogic programs that satisfy T₀ and T₁ respectively (we know these exist based on the first assumption). Program S that satisfies T can then be constructed as:

[lines of S0 excluding the cursor, with 0 appended to all lines below the cursor]
?<
[lines of S1 excluding the cursor, with 1 appended to all lines above the cursor]

This arrangement effectively muxes between S₀ and S₁ based on the first input bit (from line ?<). If it is 0, the cursor will ride the appended 0's up to the original cursor position of S₀, which will then be bordered top and bottom by empty stacks, and thus run exactly identical to the original S₀. Likewise, if 1 is input, the cursor will ride the 1's down to S₁'s cursor position and proceed to execute it as if it were alone.

For example, Stackylogic programs for OR and NAND are

?
?<

and

1
?<
11
?
0

They can be combined to simulate

if B:
    result = x OR y
else:
    result = x NAND y

like so:

1
?
110
?0
00
0
?<
?1
?

Thus, any truth table can be simulated by a Stackylogic program.

Challenge

Write a program or function that takes in an N input truth table (N > 0) in the form of a list of 2^N boolean values that represent the outputs of the table in ascending binary order.

Any reasonable input format is alright. e.g. for an OR truth table

x y | OR
0 0 | 0
0 1 | 1
1 0 | 1
1 1 | 1

any of these styles of inputs would be fine:

0111

0, 1, 1, 1

0
1
1
1

[False, True, True, True]

Print or return a Stackylogic program that satisfies the truth table, i.e. has the exact same output given the same input. Any finite program that satisfies that table is valid output. You do not need to follow the inductive proof's method of construction. The Stackylogic programs do not need to be optimally short.

For example, if the input were 11100111, one valid output would be

1
?
110
?0
00
0
?<
?1
?

but there are many others.

The shortest code in bytes wins.

See the original Stackylogic challenge if you need an interpreter.

Answer 1

Pyth, 53 bytes

L?tb,lehJyMc2bsX0.e.e+W>_Wk-Yhb0ZkebJ\?,0]`hbjXF+yQ\<

Try online

This is an exact implementation of the system described in the challenge for how to implement arbitrary truth tables in Stackylogic. We simply cut the truth table in half, implement it recursively, and then append 0 and 1 as appropriate.

This defines a recursive function, whose return value is [1, ['0', '?', '1']], where the first number is the location of the pointer, and the rest is a stackylogic program.

L?tb,lehJyMc2bsX0.e.e+W>_Wk-Yhb0ZkebJ\?,0]`hbjXF+yQ\<
                                                         Q = eval(input())
L?tb,lehJyMc2bsX0.e.e+W>_Wk-Yhb0ZkebJ\?,0]`hb
L                                                 def y(b): return
 ?tb                                              if b[1:] (base case on false)
                                      ,0]`hb      else: [0, str([0])]
                                                  then:
           c2b                                    Cut the input in half
         yM                                       Map y over the halves
        J                                         Store that in J
    ,leh                                          The cursor position is the length 
                                                  of the body of the first function
                 .e                 J             enum-map, where k is the index
                                                  and b is the value, over J
                   .e             eb              enum-map, Y is the index and
                                                  Z is the value, over body of b
                     +W         Zk                Add to Z (line) k (the overall 
                                                  index, 0 or 1) conditional on
                          -Yhb                    Y (line index) - cursor
                       _Wk                        Negated if k
                      >       0                   > 0
               X0                    \?           Add '?' to the first element
              s                                   Concatenate, giving the body

jXF+yQ\<
    yQ      Call the above on the input
   +  \<    Append a '<'
 XF         Splat the 3 element list into the 'append-at' function,
            adding the curson in the right place
j           Join on newlines and print.

Answer 2

Python 3, 352 208 205 bytes

This is still very ungolfed, and I will try to add an explanation later. After some modifications, I managed to remove 144 147 bytes.

f=lambda x,l=len,r=range:'\n'.join(*x)if l(x)<2 else f([[x[i][j]+['0',''][j<=l(x[i])//2]for j in r(l(x[i]))]+[['?','?<'][l(x)<3]]+[x[i+1][j]+['1',''][j>=l(x[i])//2]for j in r(l(x[i]))]for i in r(0,l(x),2)])

A function f that takes input of the truth table values as a list of Booleans of the form ['1','1','1','0','0','1'...], where '1' is truthy and '0' is falsey, and returns a Stackylogic program.

Try it on Ideone

If you want to test a produced program, you can use GamrCorps's Convex interpreter here.

How it works

This is a recursive function and uses the inductive method described in the question.

At the zero-indexed recursion level a, the function creates n/2 a+1-input Stackylogic programs from the n a-input programs in the list. This is done by joining all adjacent pairs of two programs in the list with ?; since the cursor is always at the middle element of each constituent program, the required appending of 0 or 1 can be performed by iterating over each line of the programs being joined, and appending if the index of the current line is less than or equal to/greater than or equal to the middle index as appropriate. If the list contains only two programs, the next recursive call will give the final program; since this requires a cursor, joining instead occurs on ?<.

When the list has length 1, the list must contain just one element containing the full program. Hence, all lines in the program are joined on a newline, and then returned.

An example helps to illustrate this:

Take the input ['1', '1', '1', '0', '0', '1', '1', '1'].

Level  Return value

0  [['1', '?', '1'], ['1', '?', '0'], ['0', '?', '1'], ['1', '?', '1']]
1  [['1', '?', '10', '?', '11', '?', '0'], ['0', '?', '10', '?', '11', '?', '1']]
2  [['1', '?', '10', '?', '110', '?0', '00', '?<', '01', '?1', '101', '?', '11', '?', '1']]
3  '1\n?\n10\n?\n110\n?0\n00\n?<\n01\n?1\n101\n?\n11\n?\n1'

which when printed gives:

1
?
10
?
110
?0
00
?<
01
?1
101
?
11
?
1