New page wikitext, after the edit (new_wikitext) | 'From a quest of pickling lambda functions, [[User:Gilbert189|I]] somehow ended up with a proof of Turing completeness for <code>pickle.loads</code>.
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 <code>next()</code>:
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 <code>next</code> with this as the argument by wrapping it in a custom class that defines <code>__reduce__</code>.
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 <code>program</code> and <code>ip</code> to a dynamic one, taken by calling <code>op.getitem</code> on <code>vars()</code>. This does require you to change the pickle data though.
[[Category:Proofs]]' |
Unified diff of changes made by edit (edit_diff) | '@@ -1,0 +1,144 @@
+From a quest of pickling lambda functions, [[User:Gilbert189|I]] somehow ended up with a proof of Turing completeness for <code>pickle.loads</code>.
+
+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 <code>next()</code>:
+
+ 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 <code>next</code> with this as the argument by wrapping it in a custom class that defines <code>__reduce__</code>.
+
+ 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 <code>program</code> and <code>ip</code> to a dynamic one, taken by calling <code>op.getitem</code> on <code>vars()</code>. This does require you to change the pickle data though.
+
+[[Category:Proofs]]
' |
Lines added in edit (added_lines) | [
0 => 'From a quest of pickling lambda functions, [[User:Gilbert189|I]] somehow ended up with a proof of Turing completeness for <code>pickle.loads</code>.',
1 => '',
2 => 'You can construct an interpreter of [[Tip]], a Turing-complete language, with iterators:',
3 => '',
4 => ' from fractions import Fraction as F',
5 => ' import operator as op',
6 => ' from itertools import repeat, ',
7 => ' ',
8 => ' # The iterator needs these variables:',
9 => ' program: list[F] = [F(1, 4), F(196608), F(16), F(0), F(3), F(16)]',
10 => ' ip: list[int] = [1]',
11 => ' iterator = (',
12 => ' map(',
13 => ' op.setitem,',
14 => ' repeat(ip),',
15 => ' repeat(0),',
16 => ' map(',
17 => ' int,',
18 => ' map(',
19 => ' op.mul,',
20 => ' map(',
21 => ' op.getitem,',
22 => ' repeat(ip),',
23 => ' repeat(0),',
24 => ' ),',
25 => ' map(',
26 => ' op.getitem,',
27 => ' repeat(program),',
28 => ' map(',
29 => ' op.mod,',
30 => ' map(',
31 => ' op.getitem,',
32 => ' repeat(ip),',
33 => ' repeat(0),',
34 => ' ),',
35 => ' repeat(len(program)),',
36 => ' )',
37 => ' )',
38 => ' )',
39 => ' )',
40 => ' )',
41 => ' )',
42 => '',
43 => 'This iterator will do one step of Tip when iterated. It's effectively equivalent to this generator:',
44 => '',
45 => ' @op.call',
46 => ' def iterator():',
47 => ' while True:',
48 => ' ip[0] = int(ip[0] * program[ip[0] % len(program)])',
49 => ' yield',
50 => '',
51 => 'With this construction, we can exhaust this iterator by passing it to <code>next()</code>:',
52 => '',
53 => ' iterator = filterfalse(',
54 => ' op.itemgetter(-1),',
55 => ' zip(',
56 => ' # This is just for debugging',
57 => ' map(',
58 => ' print,',
59 => ' repeat("ip:"),',
60 => ' repeat(ip),',
61 => ' repeat("program[ip]:"),',
62 => ' map(',
63 => ' op.getitem,',
64 => ' repeat(program),',
65 => ' map(',
66 => ' op.mod,',
67 => ' map(',
68 => ' op.getitem,',
69 => ' repeat(ip),',
70 => ' repeat(0),',
71 => ' ),',
72 => ' repeat(len(program)),',
73 => ' )',
74 => ' )',
75 => ' ),',
76 => ' iterator,',
77 => ' map(',
78 => ' op.ne,',
79 => ' map(',
80 => ' op.getitem,',
81 => ' repeat(ip),',
82 => ' repeat(0),',
83 => ' ),',
84 => ' repeat(0),',
85 => ' )',
86 => ' )',
87 => ' )',
88 => '',
89 => 'For some reason, you can pickle this iterator. Here's the pickle:',
90 => '',
91 => ' (b'\x80\x03citertools\nfilterfalse\nq\x00coperator\nitemgetter\nq\x01J\xff'',
92 => ' b'\xff\xff\xff\x85q\x02Rq\x03cbuiltins\nzip\nq\x04cbuiltins\nmap\nq\x05(cbuilt'',
93 => ' b'ins\nprint\nq\x06citertools\nrepeat\nq\x07X\x03\x00\x00\x00ip:q\x08\x85q'',
94 => ' b'\tRq\nh\x07]q\x0bK\x01a\x85q\x0cRq\rh\x07X\x0c\x00\x00\x00program[ip]'',
95 => ' b':q\x0e\x85q\x0fRq\x10h\x05c_operator\ngetitem\nq\x11h\x07]q\x12(cfractions'',
96 => ' b'\nFraction\nq\x13X\x03\x00\x00\x001/4q\x14\x85q\x15Rq\x16h\x13X\x06'',
97 => ' b'\x00\x00\x00196608q\x17\x85q\x18Rq\x19h\x13X\x02\x00\x00\x0016q\x1a'',
98 => ' b'\x85q\x1bRq\x1ch\x13X\x01\x00\x00\x000q\x1d\x85q\x1eRq\x1fh\x13X\x01\x00\x00'',
99 => ' b'\x003q \x85q!Rq"h\x13X\x02\x00\x00\x0016q#\x85q$Rq%e\x85q&Rq\'h\x05c_operat'',
100 => ' b'or\nmod\nq(h\x05h\x11h\x07h\x0b\x85q)Rq*h\x07K\x00\x85q+Rq,\x87q-Rq.h'',
101 => ' b'\x07K\x06\x85q/Rq0\x87q1Rq2\x87q3Rq4tq5Rq6h\x05(c_operator\nsetitem\nq7h'',
102 => ' b'\x07h\x0b\x85q8Rq9h\x07K\x00\x85q:Rq;h\x05cbuiltins\nint\nq<h\x05c_operato'',
103 => ' b'r\nmul\nq=h\x05h\x11h\x07h\x0b\x85q>Rq?h\x07K\x00\x85q@RqA\x87qBRqCh\x05'',
104 => ' b'h\x11h\x07h\x12\x85qDRqEh\x05h(h\x05h\x11h\x07h\x0b\x85qFRqGh\x07K\x00\x85q'',
105 => ' b'HRqI\x87qJRqKh\x07K\x06\x85qLRqM\x87qNRqO\x87qPRqQ\x87qRRqS\x86qTRqUtqVR'',
106 => ' b'qWh\x05c_operator\nne\nqXh\x05h\x11h\x07h\x0b\x85qYRqZh\x07K\x00\x85q[Rq\\'',
107 => ' b'\x87q]Rq^h\x07K\x00\x85q_Rq`\x87qaRqb\x87qcRqd\x86qeRqf.')',
108 => '',
109 => 'We can tell pickle to call <code>next</code> with this as the argument by wrapping it in a custom class that defines <code>__reduce__</code>.',
110 => '',
111 => ' class Reduce:',
112 => ' def __init__(self, func, *args):',
113 => ' self.func = func',
114 => ' self.args = args',
115 => ' def __reduce__(self):',
116 => ' return self.func, self.args',
117 => ' ',
118 => ' pickle.loads(Reduce(next, iterator, None))',
119 => '',
120 => 'And thus we get a pickle that runs Tip:',
121 => '',
122 => ' (b'\x80\x03cbuiltins\nnext\nq\x00citertools\nfilterfalse\nq\x01coperator\nit'',
123 => ' b'emgetter\nq\x02J\xff\xff\xff\xff\x85q\x03Rq\x04cbuiltins\nzip\nq\x05cbuilt'',
124 => ' b'ins\nmap\nq\x06(cbuiltins\nprint\nq\x07citertools\nrepeat\nq\x08X\x03\x00'',
125 => ' b'\x00\x00ip:q\t\x85q\nRq\x0bh\x08]q\x0cK\x01a\x85q\rRq\x0eh\x08X\x0c\x00'',
126 => ' b'\x00\x00program[ip]:q\x0f\x85q\x10Rq\x11h\x06c_operator\ngetitem\nq'',
127 => ' b'\x12h\x08]q\x13(cfractions\nFraction\nq\x14X\x03\x00\x00\x001/4q\x15\x85'',
128 => ' b'q\x16Rq\x17h\x14X\x06\x00\x00\x00196608q\x18\x85q\x19Rq\x1ah\x14'',
129 => ' b'X\x02\x00\x00\x0016q\x1b\x85q\x1cRq\x1dh\x14X\x01\x00\x00\x000q\x1e\x85q\x1f'',
130 => ' b'Rq h\x14X\x01\x00\x00\x003q!\x85q"Rq#h\x14X\x02\x00\x00\x0016q$\x85q%Rq&'',
131 => ' b"e\x85q'Rq(h\x06c_operator\nmod\nq)h\x06h\x12h\x08h\x0c\x85q*Rq+h\x08K\x00"',
132 => ' b'\x85q,Rq-\x87q.Rq/h\x08K\x06\x85q0Rq1\x87q2Rq3\x87q4Rq5tq6Rq7h\x06(c_operato'',
133 => ' b'r\nsetitem\nq8h\x08h\x0c\x85q9Rq:h\x08K\x00\x85q;Rq<h\x06cbuiltins\nint\n'',
134 => ' b'q=h\x06c_operator\nmul\nq>h\x06h\x12h\x08h\x0c\x85q?Rq@h\x08K\x00\x85qARq'',
135 => ' b'B\x87qCRqDh\x06h\x12h\x08h\x13\x85qERqFh\x06h)h\x06h\x12h\x08h\x0c\x85qGRqHh'',
136 => ' b'\x08K\x00\x85qIRqJ\x87qKRqLh\x08K\x06\x85qMRqN\x87qORqP\x87qQRqR\x87qS'',
137 => ' b'RqT\x86qURqVtqWRqXh\x06c_operator\nne\nqYh\x06h\x12h\x08h\x0c\x85qZRq[h'',
138 => ' b'\x08K\x00\x85q\\Rq]\x87q^Rq_h\x08K\x00\x85q`Rqa\x87qbRqc\x87qdRqe\x86qfRqgN'',
139 => ' b'\x86qhRqi.')',
140 => '',
141 => 'If you fancy it, you can replace the static definition of <code>program</code> and <code>ip</code> to a dynamic one, taken by calling <code>op.getitem</code> on <code>vars()</code>. This does require you to change the pickle data though.',
142 => '',
143 => '[[Category:Proofs]]'
] |