Related to AoC2017 Day 18, Part 2. (Anyone want to add Duet to esolangs?)
Duet is an assembly-like language that involves two processes running the same program simultaneously. Each process of Duet operates with 26 registers named
z, all initialized to zero, except for the register
p which contains the process ID (0 or 1).
Individual instructions in Duet are as follows.
X is a register, and
Z can be a register or a constant. A constant is an integer which can be positive, negative, or zero, and is written in base 10 with optional
set X Ysets register X to the value of Y.
add X Yincreases register X by the value of Y.
mul X Ysets register X to the result of multiplying the value contained in register X by the value of Y.
mod X Ysets register X to the remainder of dividing the value contained in register X by the value of Y (that is, it sets X to the result of X modulo Y).
- X may be assumed to be strictly non-negative and Y may be assumed to be strictly positive in this challenge.
jgz Y Zjumps with an offset of the value of Z, but only if the value of Y is greater than zero. (An offset of 2 skips the next instruction, an offset of -1 jumps to the previous instruction, and so on.)
snd Ysends the value of Y to the other program. These values wait in a queue until that program is ready to receive them. Each program has its own message queue, so a program can never receive a message it sent.
rcv Xreceives the next value and stores it in register X. If no values are in the queue, the program waits for a value to be sent to it. Programs do not continue to the next instruction until they have received a value. Values are received in the order they are sent.
jgz instruction, the program continues with the instruction to which the jump jumped. After any other instruction, the program continues with the next instruction. Continuing (or jumping) off either end of the program in either process terminates the entire program (i.e. both processes), as well as being stuck in a deadlock (both programs waiting at a
Duet does not have any I/O facility. The only observable behavior of a program is that either it terminates, or it doesn't.
Both of these programs below should terminate by a deadlock:
snd 1 snd 2 snd p rcv a rcv b rcv c rcv d
set i 31 set a 1 mul p 17 jgz p p mul a 2 add i -1 jgz i -2 add a -1 set i 127 set p 680 mul p 8505 mod p a mul p 129749 add p 12345 mod p a set b p mod b 10000 snd b add i -1 jgz i -9 jgz a 3 rcv b jgz b -1 set f 0 set i 126 rcv a rcv b set p a mul p -1 add p b jgz p 4 snd a set a b jgz 1 3 snd b set f 1 add i -1 jgz i -11 snd a jgz f -16 jgz a -19
Write an interpreter for Duet, which takes a valid source code as input (list of lines is OK), and runs it until the program terminates. Your interpreter should terminate if and only if the input Duet program terminates.
Standard code-golf rules apply. The shortest code in bytes wins.
Some examples that halt because one process exits early:
- Process 0 waits but Process 1 exits early by jumping over the end
mul p 10 jgz p p rcv x
- Process 1 loops indefinitely but Process 0 halts by jumping before the start
jgz p 0 jgz 1 -2
- Process 0 loops indefinitely but Process 1 runs through the program and exits
add p 1 mod p 2 jgz p 0
Some examples that never halt:
- Both processes run an infinite loop that passes some values around
set a 10 snd 1 snd 2 rcv x rcv y jgz a -4
- Both processes run a tight loop
jgz 1 0