45
7
Stackylogic is a logic-based programming language I made up that take in 0
's and 1
's for input and outputs a single 0
or 1
upon completion.
A Stackylogic program consists of lines that can only contain the three 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 (as I'll explain) computes the NAND of two bits:
1
?<
11
?
0
Every line in a Stackylogic program is considered a stack, with the bottom on the left and the top on the right. Implicitly, there is an empty stack (empty line) before the first line in a program and after the last line.
The <
, which we'll call the cursor, marks the stack to start on when a Stackylogic program is run. Execution of a Stackylogic program proceeds as follows:
Pop the top character off the stack the cursor is currently pointing to.
- If the character is
?
, prompt the user for a0
or a1
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).
- If the character is
If the stack the cursor moves to is empty, output the last value that was popped off a stack (always a
0
or1
), and end the program.Else, if the stack the cursor moves to is not empty, go back to step 1 and repeat the process.
Notice that Stackylogic programs always end because they must eventually deplete their stacks.
NAND Example
In the NAND program the cursor starts on a ?
:
1
?<
11
?
0
We'll assume the user inputs a 1
once the ?
is popped, which means the cursor will move down, making the program look like this:
1
11<
?
0
Now a plain 1
is at the top of the cursor stack. It is duly popped and the cursor moves again:
1
1
?<
0
Now assume the user inputs 0
for the ?
, which means the cursor will move up:
1
1<
0
Again, a 1
is on the cursor stack so the cursor pops and moves down:
1
<
0
Finally the cursor stack is empty, so the last value popped, the 1
, is output and the program ends.
This is accurate for a NAND gate because 1 NAND 0
is 1
. This of course works for the other three two-bit inputs if you care to check.
OR Example
This Stackylogic program simulates an OR gate:
?
?<
It's easy to see that an initial input of 1
will push the cursor to the implicit empty stack below the last line, ending the program and outputting the 1
that was just input.
For an input of 00
on the other hand, the cursor will make its way to the implicit empty stack at the top, ending the program and outputting the last 0
to be input.
Challenge
Write a program or function that takes in a Stackylogic program as a string and runs it, printing or returning the resulting 0
or 1
.
Upon ?
's, you may prompt the user for a 0
or 1
input, or read the value from a preset string of 0
's and 1
's that you also take as input. (This could be another string input to your program/function or you could just assume the first or last line of the program string will be the input stream).
You may assume the program and the input are always well formed. You may optionally assume input programs come with a single trailing newline (though remember there is always an implicit empty stack at the end).
The shortest code in bytes wins.
More Sample Programs
ZERO
0<
ONE
1<
BUFFER
?<
NOT
1
?<
0
AND
?<
?
NAND
1
?<
11
?
0
OR
?
?<
NOR
1
?
00
?<
0
XOR(v1)
?
0
1?<
?
0
XOR(v2)
?
?<
11
?
0
XNOR(v1)
1
?
0?<
1
?
XNOR(v2)
1
?
00
?<
?
MEDIAN(v1)
1
???<
0
MEDIAN(v2)
?
1?<
??
If you want to add a 3-input function, here's one way to implement median:
?\1?<\??
. Alternatively, here's a symmetric 5-line implementation:?\?0\?<\?1\?
– Martin Ender – 2016-07-08T07:26:51.287Oh, I found an even neater implementation:
1\???<\0
. – Martin Ender – 2016-07-08T08:50:00.2172@MartinEnder's neater implementation of the 3-input median function (equivalently, the majority-rules function) generalizes nicely. For example, the 7-input majority-rules function is
111\???????<\000
. – Greg Martin – 2016-07-09T17:35:58.890Let the "bizarro" of a Stackylogic program $P$ be the program $BP$ formed by reversing the order of the lines of the original programs, and changing all 1s to 0s and vice verse (but leaving ?s and < alone). It seems that the output of $BP$ on inputs $b_1,b_2,\dots$ is the NOT of the output of $P$ on inputs $!b_1,!b_2,\dots$. Notice that the given implementations of AND and OR are bizarro-related in this way, as are NAND and NOR, and the two versions of XOR/XNOR. Some programs are their own bizarro (BUFFER, NOT, MEDIAN(v1)). – Greg Martin – 2016-07-09T17:43:40.667
Anyway, those thoughts came up while I was finding the following implementation of the 3-input "sum the bits mod 2" function:
?\0\1?\?0\00\?<\11\?1\0?\1\?
(Note how it splices together XOR(v1) above the starting cursor and XNOR(v1) below it.) – Greg Martin – 2016-07-09T17:46:00.2101
@GregMartin Yep. I believe the technical term is duality.
– Calvin's Hobbies – 2016-07-09T18:12:47.243Can input be an array of strings instead of a multiline string? – Luis Mendo – 2016-07-10T09:35:28.383
@HelkaHomba I lurked around this question for a while, and I kinda want to make Stackylogic a thing (add new functions and stuff). Can I do that? – clismique – 2016-07-24T01:59:28.367
@DerpfacePython Sure. – Calvin's Hobbies – 2016-07-24T02:35:38.663