Pickle.loads is Turing complete

From a quest of pickling lambda functions, I (User:Gilbert189) somehow ended up with a proof of Turing completeness for pickle.loads.

You can construct an interpreter of Tip, a Turing-complete language, with iterators:

from fractions import Fraction as F
import operator as op
from itertools import repeat, 

# The iterator needs these variables:
program: list[F] = [F(1, 4), F(196608), F(16), F(0), F(3), F(16)]
ip: list[int] = [1]
iterator = (
    map(
        op.setitem,
        repeat(ip),
        repeat(0),
        map(
            int,
            map(
                op.mul,
                map(
                    op.getitem,
                    repeat(ip),
                    repeat(0),
                ),
                map(
                    op.getitem,
                    repeat(program),
                    map(
                        op.mod,
                        map(
                            op.getitem,
                            repeat(ip),
                            repeat(0),
                        ),
                        repeat(len(program)),
                    )
                )
            )
        )
    )
)

This iterator will do one step of Tip when iterated. It's effectively equivalent to this generator:

@op.call
def iterator():
    while True:
        ip[0] = int(ip[0] * program[ip[0] % len(program)])
        yield

With this construction, we can exhaust this iterator by passing it to next():

iterator = filterfalse(
    op.itemgetter(-1),
    zip(
        # This is just for debugging
        map(
            print,
            repeat("ip:"),
            repeat(ip),
            repeat("program[ip]:"),
            map(
                op.getitem,
                repeat(program),
                map(
                    op.mod,
                    map(
                        op.getitem,
                        repeat(ip),
                        repeat(0),
                    ),
                    repeat(len(program)),
                )
            )
        ),
        iterator,
        map(
            op.ne,
            map(
                op.getitem,
                repeat(ip),
                repeat(0),
            ),
            repeat(0),
        )
    )
)

For some reason, you can pickle this iterator. Here's the pickle:

(b'\x80\x03citertools\nfilterfalse\nq\x00coperator\nitemgetter\nq\x01J\xff'
 b'\xff\xff\xff\x85q\x02Rq\x03cbuiltins\nzip\nq\x04cbuiltins\nmap\nq\x05(cbuilt'
 b'ins\nprint\nq\x06citertools\nrepeat\nq\x07X\x03\x00\x00\x00ip:q\x08\x85q'
 b'\tRq\nh\x07]q\x0bK\x01a\x85q\x0cRq\rh\x07X\x0c\x00\x00\x00program[ip]'
 b':q\x0e\x85q\x0fRq\x10h\x05c_operator\ngetitem\nq\x11h\x07]q\x12(cfractions'
 b'\nFraction\nq\x13X\x03\x00\x00\x001/4q\x14\x85q\x15Rq\x16h\x13X\x06'
 b'\x00\x00\x00196608q\x17\x85q\x18Rq\x19h\x13X\x02\x00\x00\x0016q\x1a'
 b'\x85q\x1bRq\x1ch\x13X\x01\x00\x00\x000q\x1d\x85q\x1eRq\x1fh\x13X\x01\x00\x00'
 b'\x003q \x85q!Rq"h\x13X\x02\x00\x00\x0016q#\x85q$Rq%e\x85q&Rq\'h\x05c_operat'
 b'or\nmod\nq(h\x05h\x11h\x07h\x0b\x85q)Rq*h\x07K\x00\x85q+Rq,\x87q-Rq.h'
 b'\x07K\x06\x85q/Rq0\x87q1Rq2\x87q3Rq4tq5Rq6h\x05(c_operator\nsetitem\nq7h'
 b'\x07h\x0b\x85q8Rq9h\x07K\x00\x85q:Rq;h\x05cbuiltins\nint\nq<h\x05c_operato'
 b'r\nmul\nq=h\x05h\x11h\x07h\x0b\x85q>Rq?h\x07K\x00\x85q@RqA\x87qBRqCh\x05'
 b'h\x11h\x07h\x12\x85qDRqEh\x05h(h\x05h\x11h\x07h\x0b\x85qFRqGh\x07K\x00\x85q'
 b'HRqI\x87qJRqKh\x07K\x06\x85qLRqM\x87qNRqO\x87qPRqQ\x87qRRqS\x86qTRqUtqVR'
 b'qWh\x05c_operator\nne\nqXh\x05h\x11h\x07h\x0b\x85qYRqZh\x07K\x00\x85q[Rq\\'
 b'\x87q]Rq^h\x07K\x00\x85q_Rq`\x87qaRqb\x87qcRqd\x86qeRqf.')

We can tell pickle to call next with this as the argument by wrapping it in a custom class that defines __reduce__.

class Reduce:
    def __init__(self, func, *args):
        self.func = func
        self.args = args
    def __reduce__(self):
        return self.func, self.args

pickle.loads(Reduce(next, iterator, None))

And thus we get a pickle that runs Tip:

(b'\x80\x03cbuiltins\nnext\nq\x00citertools\nfilterfalse\nq\x01coperator\nit'
 b'emgetter\nq\x02J\xff\xff\xff\xff\x85q\x03Rq\x04cbuiltins\nzip\nq\x05cbuilt'
 b'ins\nmap\nq\x06(cbuiltins\nprint\nq\x07citertools\nrepeat\nq\x08X\x03\x00'
 b'\x00\x00ip:q\t\x85q\nRq\x0bh\x08]q\x0cK\x01a\x85q\rRq\x0eh\x08X\x0c\x00'
 b'\x00\x00program[ip]:q\x0f\x85q\x10Rq\x11h\x06c_operator\ngetitem\nq'
 b'\x12h\x08]q\x13(cfractions\nFraction\nq\x14X\x03\x00\x00\x001/4q\x15\x85'
 b'q\x16Rq\x17h\x14X\x06\x00\x00\x00196608q\x18\x85q\x19Rq\x1ah\x14'
 b'X\x02\x00\x00\x0016q\x1b\x85q\x1cRq\x1dh\x14X\x01\x00\x00\x000q\x1e\x85q\x1f'
 b'Rq h\x14X\x01\x00\x00\x003q!\x85q"Rq#h\x14X\x02\x00\x00\x0016q$\x85q%Rq&'
 b"e\x85q'Rq(h\x06c_operator\nmod\nq)h\x06h\x12h\x08h\x0c\x85q*Rq+h\x08K\x00"
 b'\x85q,Rq-\x87q.Rq/h\x08K\x06\x85q0Rq1\x87q2Rq3\x87q4Rq5tq6Rq7h\x06(c_operato'
 b'r\nsetitem\nq8h\x08h\x0c\x85q9Rq:h\x08K\x00\x85q;Rq<h\x06cbuiltins\nint\n'
 b'q=h\x06c_operator\nmul\nq>h\x06h\x12h\x08h\x0c\x85q?Rq@h\x08K\x00\x85qARq'
 b'B\x87qCRqDh\x06h\x12h\x08h\x13\x85qERqFh\x06h)h\x06h\x12h\x08h\x0c\x85qGRqHh'
 b'\x08K\x00\x85qIRqJ\x87qKRqLh\x08K\x06\x85qMRqN\x87qORqP\x87qQRqR\x87qS'
 b'RqT\x86qURqVtqWRqXh\x06c_operator\nne\nqYh\x06h\x12h\x08h\x0c\x85qZRq[h'
 b'\x08K\x00\x85q\\Rq]\x87q^Rq_h\x08K\x00\x85q`Rqa\x87qbRqc\x87qdRqe\x86qfRqgN'
 b'\x86qhRqi.')

If you fancy it, you can replace the static definition of program and ip to a dynamic one, taken by calling op.getitem on vars(). This does require you to change the pickle data though.