Mercurial > repo

comparison bin/gs2.py @ 9075:c989a1669243

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
<fizzie> revert 58b9ee8f97a7
author HackBot
date Sun, 25 Sep 2016 20:31:46 +0000
parents
children
comparison
equal deleted inserted replaced
9074:560a73f4f0a4 9075:c989a1669243
1 # gs2 interpreter (version 0.2)
2 # (c) nooodl 2014
3
4 import copy
5 import inspect
6 import itertools as it
7 import math
8 import operator
9 import os
10 import random
11 import re
12 import string
13 import struct
14 import sys
15 import traceback
16
17 from collections import namedtuple
18 from fractions import gcd
19
20 Block = namedtuple('Block', 'code')
21 STRING_ENDS = '\x05\x06' + ''.join(map(chr, range(0x9b, 0xa0)))
22
23 DEBUG = False
24
25 def log(x):
26 if not DEBUG: return
27 line, name = inspect.stack()[1][2:4]
28 sys.stderr.write('\x1b[36m%s:%d\x1b[34m: %r\x1b[0m\n' % (name, line, x))
29
30 def lcm(a, b):
31 if (a, b) == (0, 0): return 0
32 return abs(a * b) // gcd(a, b)
33
34 def product(xs):
35 p = 1
36 for x in xs:
37 p *= x
38 return p
39
40 def split(a, b, clean=False):
41 res = [[]]
42 lb = len(b)
43
44 i = 0
45 while i < len(a):
46 if a[i:i + lb] == b:
47 res.append([])
48 i += lb
49 else:
50 res[-1].append(a[i])
51 i += 1
52
53 return filter(None, res) if clean else res
54
55 def join(a, b):
56 res = []
57 for i, x in enumerate(a):
58 if i > 0:
59 res.extend(b)
60 res.extend(x if is_list(x) else [x])
61 return res
62
63 def set_diff(a, b):
64 res = []
65 for i in a:
66 if i not in b:
67 res.append(i)
68 return res
69
70 def set_and(a, b):
71 res = []
72 for i in a:
73 if i in b:
74 res.append(i)
75 return res
76
77 def set_or(a, b):
78 return a + set_diff(b, a)
79
80 def set_xor(a, b):
81 return set_diff(a, b) + set_diff(b, a)
82
83 # prime number functions
84 prime_list = []
85 sieved = 2
86 composite = set([1])
87
88 def sieve(limit):
89 global prime_list
90 global sieved
91 global composite
92 if limit <= sieved: return
93
94 prime_list = []
95 for i in range(2, limit):
96 if i in composite: continue
97 for j in range(i*i, limit, i):
98 composite.add(j)
99 prime_list.append(i)
100 sieved = limit
101
102 sieve(1000)
103
104 def is_prime(n):
105 global prime_list
106 sieve(n+1)
107 return n not in composite
108
109 def nth_prime(n):
110 global prime_list
111 sieve(int(math.log(n) * n) + 100)
112 return prime_list[n-1]
113
114 def n_primes(n):
115 global prime_list
116 sieve(int(math.log(n) * n) + 100)
117 return prime_list[:n]
118
119 def primes_below(n):
120 global prime_list
121 sieve(n+1)
122 return list(it.takewhile(lambda x: x < n, prime_list))
123
124 def next_prime(n):
125 n += 1
126 while not is_prime(n): n += 1
127 return n
128
129 def totient(n):
130 count = 0
131 for i in xrange(1, n+1):
132 if gcd(n, i) == 1: count += 1
133 return count
134
135 def factor(n, exps=False):
136 if is_num(n):
137 p = 2
138 res = []
139 while n > 1:
140 while n % p == 0:
141 res.append(p)
142 n //= p
143 p = next_prime(p)
144 if exps:
145 res = [[k, len(list(g))] for k, g in it.groupby(res)]
146 return res
147 elif is_list(n):
148 if n and is_num(n[0]):
149 n = zip(n[0::2], n[1::2])
150 p = 1
151 for b, e in n: p *= b ** e
152 return p
153 else:
154 raise TypeError('factor')
155
156 def chunks(x, y):
157 # chunks(range(12), 3) ==> [[0, 1, 2], [3, 4, 5], ...]
158 while x:
159 yield x[:y]
160 x = x[y:]
161
162 def tokenize(prog):
163 # string hack
164 cs = STRING_ENDS
165 if re.match('^[^\x04]*[%s]' % cs, prog):
166 prog = '\x04' + prog
167
168 mode = None
169 if prog[0] in '\x30\x31\x32': # set mode
170 mode = prog[0]
171 prog = prog[1:]
172
173 token_re = [
174 '\x04[^%s]*[%s]' % (cs, cs), # string (array)
175 '\x01.', # unsigned byte
176 '\x02..', # signed short
177 '\x03....', # signed long
178 '\x07.', # 1 char string
179 '.', # regular token
180 ]
181
182 tokens = re.findall('|'.join(token_re), prog, re.DOTALL)
183
184 final = []
185 blocks = [Block([])]
186 i = 0
187 while i < len(tokens):
188 t = tokens[i]
189 log(tokens[i:])
190 if t == '\x08': #= {
191 blocks.append(Block([]))
192 final.append('\x00')
193 elif t == '\x09': #= }
194 blocks[-2].code.append(blocks.pop())
195 blocks[-1].code.append(final.pop())
196 elif '\xe0' <= t <= '\xff' and ord(t) & 7 < 6:
197 # quick block
198 # 0b111XXYYY -- Y+1 is number of tokens, X is end token:
199 # 0 = nop (0x00) 2 = filter (0x35)
200 # 1 = map (0x34) 3 = both (0x38)
201 # but 0xfe and 0xff are special (see below.)
202 num = (ord(t) & 7) + 1
203 ts = blocks[-1].code[-num:]
204 del blocks[-1].code[-num:]
205 blocks[-1].code.append(Block(ts))
206 blocks[-1].code.append('\x00\x34\x35\x38'[(ord(t) >> 3) & 3])
207 elif t in '\xee\xef': #= z1 zipwith1, z2 zipwith2
208 # zipwith (1/2 tokens)
209 num = (ord(t) & 1) + 1
210 ts = blocks[-1].code[-num:]
211 del blocks[-1].code[-num:]
212 blocks[-1].code.append(Block(ts))
213 blocks[-1].code.append('\xb1')
214 elif t in '\xf6\xf7': #= dm1 dump-map1, df1 dump-filter1
215 # like m1/f1 with dump prepended to block
216 # useful with transpose, pairwise, cartesian-product, etc.
217 f = {'\xf6': '\x34', '\xf7': '\x35'}[t]
218 x = blocks[-1].code.pop()
219 blocks[-1].code.extend([Block(['\x0e', x]), f])
220 elif t == '\xfe': #= m:
221 blocks.append(Block([]))
222 final.append('\x34')
223 elif t == '\xff': #= f:
224 blocks.append(Block([]))
225 final.append('\x35')
226 else:
227 blocks[-1].code.append(t)
228 i += 1
229
230 while final:
231 blocks[-2].code.append(blocks.pop())
232 blocks[-1].code.append(final.pop())
233
234 assert len(blocks) == 1
235 main = blocks[0]
236
237 if mode == '\x30': #= line-mode
238 main = Block(['\x2a', main, '\x34', '\x54'])
239 elif mode == '\x31': #= word-mode
240 main = Block(['\x2c', main, '\x34', '\x55'])
241 elif mode == '\x32': #= line-mode-skip-first
242 main = Block(['\x2a', '\x22', main, '\x34', '\x54'])
243
244 main.code.extend(final)
245 return main
246
247 is_num = lambda v: isinstance(v, (int, long))
248 is_list = lambda v: isinstance(v, list)
249 is_block = lambda v: isinstance(v, Block)
250
251 def to_gs(ps): return map(ord, ps)
252
253 def to_ps(gs):
254 if is_list(gs): return ''.join(map(chr, gs))
255 else: return chr(gs)
256
257 def regex_count(pattern):
258 c = 0
259 if pattern[0] == ']':
260 c = 1
261 pattern = pattern[1:]
262 elif pattern[0] == '}':
263 c = ord(pattern[1])
264 pattern = pattern[2:]
265 return (c, pattern)
266
267 def show(value, nest=False):
268 if is_list(value):
269 return ''.join(show(x, nest=True) for x in value)
270 elif nest and is_num(value):
271 return chr(value)
272 else:
273 return str(value)
274
275 class Stack(list):
276 def __init__(self, *args):
277 list.__init__(self, *args)
278 self.junk = []
279 def pop(self, i=-1, junk=True):
280 x = list.pop(self, i)
281 if junk: self.junk.append(x)
282 return x
283
284 class GS2(object):
285 def __init__(self, code, stdin=''):
286 self.code = code
287 self.stdin = to_gs(stdin)
288 self.stack = Stack([self.stdin])
289 self.regs = {
290 0: to_gs(stdin), # A
291 1: len(stdin), # B
292 2: to_gs(code), # C
293 3: random.randint(0, 2), # D
294 }
295 self.counter = 1
296
297 def run(self):
298 try:
299 self.evaluate(tokenize(self.code))
300 sys.stdout.write(''.join(map(show, self.stack)))
301 except Exception:
302 # If the code fails, print something meaningful to stderr,
303 # but quine on stdout: this allows GS2 to good at simple
304 # "print this string" programs -- just upload a plaintext
305 # file, it's unlikely to be valid GS2 code.
306 traceback.print_exc()
307 if not DEBUG: sys.stdout.write(self.code)
308
309 def evaluate(self, block):
310 log(block)
311 for t in block.code:
312 if is_block(t):
313 self.stack.append(t)
314 elif t[0] == '\x00': #= nop
315 pass
316 elif t[0] == '\x01': # push unsigned byte
317 self.stack.append(struct.unpack('<B', t[1:])[0])
318 elif t[0] == '\x02': # push signed short
319 self.stack.append(struct.unpack('<h', t[1:])[0])
320 elif t[0] == '\x03': # push signed long
321 self.stack.append(struct.unpack('<l', t[1:])[0])
322
323 elif t[0] == '\x04': # string
324 assert len(t) >= 2
325 assert t[-1] in STRING_ENDS
326 strings = t[1:-1].split('\x07')
327 strings = map(to_gs, strings)
328 if t[-1] == '\x05': # regular
329 self.stack += strings
330 elif t[-1] == '\x06': # array
331 self.stack.append(strings)
332 elif t[-1] == '\x9b': # printf
333 f = to_ps(strings.pop())
334 n = f.count('%') - f.count('%%') * 2
335 x = tuple(map(to_ps, self.stack[-n:]))
336 del self.stack[-n:]
337 self.stack.append(to_gs(f % x))
338 elif t[-1] == '\x9c': # regex match
339 pattern = to_ps(strings.pop())
340 c, pattern = regex_count(pattern)
341 s = to_ps(self.stack.pop())
342 f = re.match if c else re.search
343 self.stack.append(1 if f(pattern, s) else 0)
344 elif t[-1] == '\x9d': # regex sub
345 repl = to_ps(strings.pop())
346 pattern = to_ps(strings.pop())
347 c, pattern = regex_count(pattern)
348 s = to_ps(self.stack.pop())
349 m = re.sub(pattern, repl, s, count=c)
350 self.stack.append(to_gs(m))
351 elif t[-1] == '\x9e': # regex find
352 pattern = to_ps(strings.pop())
353 c, pattern = regex_count(pattern)
354 s = to_ps(self.stack.pop())
355 ms = re.findall(pattern, s)
356 if c > 0: ms = ms[0] if ms else []
357 self.stack.append(map(to_gs, ms))
358 elif t[-1] == '\x9f': # regex split
359 pattern = to_ps(strings.pop())
360 c, pattern = regex_count(pattern)
361 s = to_ps(self.stack.pop())
362 m = re.split(pattern, s, maxsplit=c)
363 self.stack.append(map(to_gs, m))
364
365 elif t[0] == '\x07': # single char string
366 self.stack.append([ord(t[1])])
367
368 # \x08 and \x09 are block syntax
369 elif t == '\x0a': #= new-line
370 self.stack.append([ord('\n')])
371 elif t == '\x0b': #= empty-list
372 self.stack.append([])
373 elif t == '\x0c': #= empty-block
374 self.stack.append(Block([]))
375 elif t == '\x0d': #= space
376 self.stack.append([ord(' ')])
377 elif t == '\x0e': #= make-array extract-array dump
378 x = self.stack.pop()
379 if is_num(x):
380 self.stack[-x:] = [self.stack[-x:]]
381 elif is_list(x):
382 for i in x:
383 self.stack.append(i)
384 else:
385 raise TypeError('make-array / extract-array')
386
387 elif t == '\x0f': #= exit
388 break
389
390 elif 0x10 <= ord(t[0]) <= 0x1a: # push small number
391 self.stack.append(ord(t[0]) - 0x10)
392 elif t == '\x1b': self.stack.append(100)
393 elif t == '\x1c': self.stack.append(1000)
394 elif t == '\x1d': self.stack.append(16)
395 elif t == '\x1e': self.stack.append(64)
396 elif t == '\x1f': self.stack.append(256)
397
398 elif t == '\x20': #= negate reverse eval
399 x = self.stack.pop()
400 if is_num(x):
401 self.stack.append(-x)
402 elif is_list(x):
403 self.stack.append(x[::-1])
404 elif is_block(x):
405 self.evaluate(x)
406 else:
407 raise TypeError('negate / reverse')
408
409 elif t == '\x21': #= bnot head
410 x = self.stack.pop()
411 if is_num(x):
412 self.stack.append(~x)
413 elif is_list(x):
414 self.stack.append(x[0])
415 else:
416 raise TypeError('bitwise not / head')
417
418 elif t == '\x22': #= not tail
419 x = self.stack.pop()
420 if is_num(x):
421 self.stack.append(0 if x else 1)
422 elif is_list(x):
423 self.stack.append(x[1:])
424 else:
425 raise TypeError('not / tail')
426
427 elif t == '\x23': #= abs init
428 x = self.stack.pop()
429 if is_num(x):
430 self.stack.append(abs(x))
431 elif is_list(x):
432 self.stack.append(x[:-1])
433 else:
434 raise TypeError('abs / init')
435
436 elif t == '\x24': #= digits last
437 x = self.stack.pop()
438 if is_num(x):
439 self.stack.append(map(int, str(abs(x))))
440 elif is_list(x):
441 self.stack.append(x[-1])
442 else:
443 raise ValueError('digits / last')
444
445 elif t == '\x25': #= random
446 x = self.stack.pop()
447 if is_num(x):
448 self.stack.append(random.randrange(x))
449 elif is_list(x):
450 self.stack.append(random.choice(x))
451 else:
452 raise TypeError('random')
453
454 elif t == '\x26': #= dec left-uncons
455 x = self.stack.pop()
456 if is_num(x):
457 self.stack.append(x - 1)
458 elif is_list(x):
459 self.stack.append(x[1:])
460 self.stack.append(x[0])
461 else:
462 raise TypeError('deincrement / left uncons')
463
464 elif t == '\x27': #= inc right-uncons
465 x = self.stack.pop()
466 if is_num(x):
467 self.stack.append(x + 1)
468 elif is_list(x):
469 self.stack.append(x[:-1])
470 self.stack.append(x[-1])
471 else:
472 raise TypeError('increment / right uncons')
473
474 elif t == '\x28': #= sign min
475 x = self.stack.pop()
476 if is_num(x):
477 self.stack.append(cmp(x, 0))
478 elif is_list(x):
479 self.stack.append(min(x))
480 else:
481 raise TypeError('sign / min')
482
483 elif t == '\x29': #= thousand max
484 x = self.stack.pop()
485 if is_num(x):
486 self.stack.append(x * 1000)
487 elif is_list(x):
488 self.stack.append(max(x))
489 else:
490 raise TypeError('thousand / max')
491
492 elif t == '\x2a': #= double lines
493 x = self.stack.pop()
494 if is_num(x):
495 self.stack.append(x * 2)
496 elif is_list(x):
497 if x and x[-1] == ord('\n'):
498 x.pop()
499 self.stack.append(split(x, to_gs('\n')))
500 else:
501 raise TypeError('double / line')
502
503 elif t == '\x2b': #= half unlines
504 x = self.stack.pop()
505 if is_num(x):
506 self.stack.append(x // 2)
507 elif is_list(x):
508 x = [to_gs(show(i)) for i in x]
509 self.stack.append(join(x, to_gs('\n')))
510 else:
511 raise TypeError('half / unlines')
512
513 elif t == '\x2c': #= square words
514 x = self.stack.pop()
515 if is_num(x):
516 self.stack.append(x * x)
517 elif is_list(x):
518 self.stack.append(map(to_gs, to_ps(x).split()))
519 else:
520 raise TypeError('square / words')
521
522 elif t == '\x2d': #= sqrt unwords
523 x = self.stack.pop()
524 if is_num(x):
525 self.stack.append(int(math.sqrt(x)))
526 elif is_list(x):
527 x = [to_gs(show(i)) for i in x]
528 self.stack.append(join(x, to_gs(' ')))
529 else:
530 raise TypeError('sqrt / unwords')
531
532 elif t == '\x2e': #= range length
533 x = self.stack.pop()
534 if is_num(x):
535 self.stack.append(range(x))
536 elif is_list(x):
537 self.stack.append(len(x))
538 else:
539 raise TypeError('range / length')
540
541 elif t == '\x2f': #= range1 sort
542 x = self.stack.pop()
543 if is_num(x):
544 self.stack.append(range(1, x + 1))
545 elif is_list(x):
546 self.stack.append(list(sorted(x)))
547 elif is_block(x):
548 l = self.stack.pop()
549 def f(z):
550 self.stack.append(z)
551 self.evaluate(x)
552 return self.stack.pop(junk=False)
553 self.stack.append(list(sorted(l, key=f)))
554 else:
555 raise TypeError('range1 / sort')
556
557 elif t == '\x30': #= + add catenate
558 y = self.stack.pop()
559 x = self.stack.pop()
560 if is_num(x) and is_num(y):
561 self.stack.append(x + y)
562 elif is_list(x) and is_list(y):
563 self.stack.append(x + y)
564 elif is_block(x) and is_block(y):
565 self.stack.append(Block(x.code + y.code))
566 elif is_list(x) and not is_list(y):
567 self.stack.append(x + [y])
568 elif not is_list(x) and is_list(y):
569 self.stack.append([x] + y)
570 else:
571 raise TypeError('add / catenate')
572
573 elif t == '\x31': #= - sub diff
574 y = self.stack.pop()
575 x = self.stack.pop()
576 if is_num(x) and is_num(y):
577 self.stack.append(x - y)
578 elif is_list(x) and is_list(y):
579 self.stack.append(set_diff(x, y))
580 elif is_list(x) and not is_list(y):
581 self.stack.append(set_diff(x, [y]))
582 elif not is_list(x) and is_list(y):
583 self.stack.append(set_diff(y, [x]))
584 else:
585 raise TypeError('subtract / set diff')
586
587 elif t == '\x32': #= * mul join times fold
588 y = self.stack.pop()
589 x = self.stack.pop()
590 if is_num(x) and (is_block(y) or is_list(y)):
591 x, y = y, x
592 if is_block(x) and is_list(y):
593 x, y = y, x
594
595 if is_num(x) and is_num(y):
596 self.stack.append(x * y)
597 elif is_list(x) and is_list(y):
598 self.stack.append(join(x, y))
599 elif is_list(x) and is_num(y):
600 self.stack.append(x * y)
601 elif is_block(x) and is_num(y):
602 for i in xrange(y):
603 self.evaluate(x)
604 elif is_list(x) and is_block(y):
605 self.stack.append(x[0])
606 for i in x[1:]:
607 self.stack.append(i)
608 self.evaluate(y)
609 else:
610 raise TypeError('multiply / join / times / fold')
611
612 elif t == '\x33': #= / div chunks split each
613 y = self.stack.pop()
614 x = self.stack.pop()
615
616 if not is_list(x) and is_list(y):
617 x, y = y, x
618
619 if is_num(x) and is_num(y):
620 self.stack.append(x // y)
621 elif is_list(x) and is_num(y):
622 self.stack.append(list(chunks(x, y)))
623 elif is_list(x) and is_list(y):
624 self.stack.append(split(x, y))
625 elif is_list(x) and is_block(y):
626 for i in x:
627 self.stack.append(i)
628 self.evaluate(y)
629 else:
630 raise TypeError('divide / chunks / split / each')
631
632 elif t == '\x34': #= % mod step clean-split map
633 y = self.stack.pop()
634 x = self.stack.pop()
635
636 if not is_list(x) and is_list(y):
637 x, y = y, x
638
639 if is_num(x) and is_num(y):
640 self.stack.append(x % y)
641 elif is_list(x) and is_num(y):
642 self.stack.append(x[::y])
643 elif is_list(x) and is_list(y):
644 self.stack.append(split(x, y, clean=True))
645 elif is_list(x) and is_block(y):
646 self.eval_map(y, x)
647 else:
648 raise TypeError('modulo / step / split\' / map')
649
650 elif t == '\x35': #= & and get when filter
651 y = self.stack.pop()
652 x = self.stack.pop()
653
654 if is_block(x) and is_num(y):
655 x, y = y, x
656 if is_num(x) and is_list(y):
657 x, y = y, x
658 if is_block(x) and is_list(y):
659 x, y = y, x
660
661 if is_num(x) and is_num(y):
662 self.stack.append(x & y)
663 elif is_list(x) and is_list(y):
664 self.stack.append(set_and(x, y))
665 elif is_list(x) and is_num(y):
666 self.stack.append(x[y])
667 elif is_num(x) and is_block(y):
668 if x: self.evaluate(y)
669 elif is_list(x) and is_block(y):
670 self.eval_filter(y, x)
671 else:
672 raise TypeError('and / get / when / filter')
673
674 elif t == '\x36': #= | or unless
675 y = self.stack.pop()
676 x = self.stack.pop()
677
678 if is_block(x) and is_num(y):
679 x, y = y, x
680
681 if is_num(x) and is_num(y):
682 self.stack.append(x | y)
683 elif is_list(x) and is_list(y):
684 self.stack.append(set_or(x, y))
685 elif is_num(x) and is_block(y):
686 if not x: self.evaluate(y)
687 else:
688 raise TypeError('bor / unless')
689
690 elif t == '\x37': #= ^ xor concatmap
691 y = self.stack.pop()
692 x = self.stack.pop()
693
694 if is_block(x) and is_list(y):
695 x, y = y, x
696
697 if is_num(x) and is_num(y):
698 self.stack.append(x ^ y)
699 elif is_list(x) and is_list(y):
700 self.stack.append(set_xor(x, y))
701 elif is_list(x) and is_block(y):
702 res = []
703 for i in x:
704 self.stack.append(i)
705 self.evaluate(y)
706 res.extend(self.stack.pop(junk=False))
707 self.stack.append(res)
708 else:
709 raise TypeError('xor / concatmap')
710
711 elif t == '\x38': #= smallest both
712 y = self.stack.pop()
713 if is_block(y):
714 x = self.stack.pop()
715 self.evaluate(y)
716 self.stack.append(x)
717 self.evaluate(y)
718 else:
719 x = self.stack.pop()
720 self.stack.append(min(x, y))
721
722 elif t == '\x39': #= biggest
723 y = self.stack.pop()
724 x = self.stack.pop()
725 self.stack.append(max(x, y))
726
727 elif t == '\x3a': #= clamp
728 z = self.stack.pop()
729 y = self.stack.pop()
730 x = self.stack.pop()
731 self.stack.append(min(max(x, y), z))
732
733 elif t == '\x3c': #= gcd take
734 y = self.stack.pop()
735 x = self.stack.pop()
736
737 if is_num(x) and is_list(y):
738 x, y = y, x
739
740 if is_num(x) and is_num(y):
741 self.stack.append(gcd(x, y))
742 elif is_list(x) and is_num(y):
743 self.stack.append(x[:y])
744 else:
745 raise TypeError('gcd / take')
746
747 elif t == '\x3d': #= lcm drop
748 y = self.stack.pop()
749 x = self.stack.pop()
750
751 if is_num(x) and is_list(y):
752 x, y = y, x
753
754 if is_num(x) and is_num(y):
755 self.stack.append(lcm(x, y))
756 elif is_list(x) and is_num(y):
757 self.stack.append(x[y:])
758 else:
759 raise TypeError('lcm / drop')
760
761 elif t == '\x3e': #= pow index
762 y = self.stack.pop()
763 x = self.stack.pop()
764
765 if is_num(x) and is_list(y):
766 x, y = y, x
767
768 if is_num(x) and is_num(y):
769 self.stack.append(x ** y)
770 elif is_list(x) and is_num(y):
771 self.stack.append(x.index(y) if y in x else -1)
772 else:
773 raise TypeError('power / index')
774
775 elif t == '\x3f': #= log member
776 y = self.stack.pop()
777 x = self.stack.pop()
778
779 if is_list(y):
780 x, y = y, x
781
782 if is_num(x) and is_num(y):
783 self.stack.append(int(math.log(x, y)))
784 elif is_list(x):
785 self.stack.append(1 if y in x else 0)
786 else:
787 raise TypeError('log / member')
788
789 elif t == '\x40': #= dup
790 self.stack.append(self.stack[-1])
791 elif t == '\x41': #= dup2
792 self.stack.append(self.stack[-1])
793 self.stack.append(self.stack[-1])
794 elif t == '\x42': #= swap
795 self.stack.append(self.stack.pop(-2))
796 elif t == '\x43': #= rot
797 self.stack.append(self.stack.pop(-3))
798 elif t == '\x44': #= rrot
799 self.stack.append(self.stack.pop(-3))
800 self.stack.append(self.stack.pop(-3))
801 elif t == '\x45': #= over
802 self.stack.append(self.stack[-2])
803 elif t == '\x46': #= nip
804 self.stack.pop(-2)
805 elif t == '\x47': #= tuck
806 self.stack.insert(-2, self.stack[-1])
807 elif t == '\x48': #= 2dup
808 self.stack.append(self.stack[-2])
809 self.stack.append(self.stack[-2])
810 elif t == '\x49': #= pick
811 n = self.stack.pop()
812 self.stack.append(self.stack[-n])
813 elif t == '\x4a': #= roll
814 n = self.stack.pop()
815 self.stack.append(self.stack.pop(-n))
816 elif t == '\x4b': #= wrap-stack
817 self.stack = [copy.deepcopy(self.stack)]
818 elif t == '\x4c': #= leave-top
819 del self.stack[:-1]
820 elif t == '\x4d': #= itemize
821 self.stack.append([self.stack.pop()])
822 elif t == '\x4e': #= rrange
823 x = self.stack.pop()
824 self.stack.append(range(x)[::-1])
825 elif t == '\x4f': #= crange
826 y = self.stack.pop()
827 x = self.stack.pop()
828 if x > y: x, y = y, x
829 self.stack.append(range(x, y))
830 elif t == '\x50': #= pop
831 self.stack.pop()
832 elif t == '\x51': #= pop2
833 self.stack.pop()
834 self.stack.pop()
835 elif t == '\x52': #= show
836 x = self.stack.pop()
837 self.stack.append(to_gs(show(x)))
838 elif t == '\x53': #= map-show
839 x = self.stack.pop()
840 self.stack.append(map(to_gs, map(show, x)))
841 elif t == '\x54': #= show-lines
842 x = self.stack.pop()
843 self.stack.append(to_gs('\n'.join(map(show, x))))
844 elif t == '\x55': #= show-words
845 x = self.stack.pop()
846 self.stack.append(to_gs(' '.join(map(show, x))))
847 elif t in '\x56\x57': #= read-num, read-nums
848 x = to_ps(self.stack.pop())
849 nums = map(int, re.findall(r'-?\d+', x))
850 self.stack.append(nums[0] if t == '\x56' else nums)
851 elif t == '\x58': #= show-line
852 x = self.stack.pop()
853 self.stack.append(to_gs(show(x) + '\n'))
854 elif t == '\x59': #= show-space
855 x = self.stack.pop()
856 self.stack.append(to_gs(show(x) + ' '))
857 elif t == '\x5a': #= show-comma
858 x = self.stack.pop()
859 self.stack.append(to_gs(', '.join(map(show, x))))
860 elif t == '\x5b': #= show-python
861 x = self.stack.pop()
862 self.stack.append(to_gs(', '.join(map(show, x)).join('[]')))
863 elif t in '\x5c\x5d\x5e': #= ljust, center, rjust
864 fill = ' '
865 if is_num(self.stack[-2]):
866 fill = chr(self.stack.pop())
867 width = self.stack.pop()
868 s = self.stack.pop()
869 if t == '\x5c': g = show(s).ljust(width, fill)
870 if t == '\x5d': g = show(s).center(width, fill)
871 if t == '\x5e': g = show(s).rjust(width, fill)
872 self.stack.append(to_gs(g))
873 elif t == '\x5f': #= inspect
874 self.stack.append(to_gs(repr(self.stack.pop())))
875 elif t == '\x60': #= logical-and
876 y = self.stack.pop()
877 x = self.stack.pop()
878 self.stack.append(x and y)
879 elif t == '\x61': #= logical-or
880 y = self.stack.pop()
881 x = self.stack.pop()
882 self.stack.append(x or y)
883 elif t == '\x62': #= divides left-cons
884 y = self.stack.pop()
885 x = self.stack.pop()
886 if is_num(x):
887 self.stack.append(0 if x % y else 1)
888 elif is_list(x):
889 self.stack.append([y] + x)
890 else:
891 raise TypeError('divides / left-cons')
892 elif t == '\x63': #= divmod group
893 y = self.stack.pop()
894 if is_num(y):
895 x = self.stack.pop()
896 self.stack.append(x // y)
897 self.stack.append(x % y)
898 elif is_list(y):
899 gb = [list(g) for k, g in it.groupby(y)]
900 self.stack.append(list(gb))
901 else:
902 raise TypeError('divmod / group')
903 elif t == '\x64': #= sum even
904 x = self.stack.pop()
905 if is_num(x):
906 self.stack.append(1 if x % 2 == 0 else 0)
907 elif is_list(x):
908 self.stack.append(sum(x))
909 elif t == '\x65': #= product odd
910 x = self.stack.pop()
911 if is_num(x):
912 self.stack.append(1 if x % 2 == 1 else 0)
913 elif is_list(x):
914 self.stack.append(product(x))
915 elif t == '\x66': #= fizzbuzz
916 fizzbuzz = []
917 for i in range(1, 101):
918 s = ("Fizz" if i % 3 == 0 else "") + \
919 ("Buzz" if i % 5 == 0 else "")
920 fizzbuzz.append(s or str(i))
921 self.stack.append(to_gs('\n'.join(fizzbuzz)))
922 elif t == '\x67': #= popcnt right-cons
923 x = self.stack.pop()
924 if is_num(x):
925 x = abs(x)
926 p = 0
927 while x:
928 p += (x & 1)
929 x >>= 1
930 self.stack.append(p)
931 elif is_list(x):
932 y = self.stack.pop()
933 self.stack.append(x + [y])
934 elif t == '\x68': #= hello
935 x = 0
936 if len(self.stack) >= 1 and is_num(self.stack[-1]):
937 x = self.stack.pop()
938 x = (range(0, 11) + [100, 1000, 16, 64, 256]).index(x)
939 s1 = 'h' if x & 1 else 'H'
940 s2 = 'W' if x & 2 else 'w'
941 s3 = ['!', '', '.', '...'][((x & 4) >> 2) | ((x & 16) >> 3)]
942 s4 = '' if x & 8 else ','
943 f = '%sello%s %sorld%s' % (s1, s4, s2, s3)
944 self.stack.append(to_gs(f))
945 elif t in '\x69\x6a': #= base, binary
946 b = 2 if t == '\x6a' else self.stack.pop()
947 x = self.stack.pop()
948 if is_num(x):
949 x = abs(x)
950 res = []
951 while x:
952 res.append(x % b)
953 x //= b
954 self.stack.append(res[::-1])
955 elif is_list(x):
956 res = 0
957 for i in x:
958 res = res * b + i
959 self.stack.append(res)
960 else:
961 raise TypeError('base / binary')
962 elif t == '\x6b': #= is-prime
963 x = self.stack.pop()
964 if is_num(x):
965 self.stack.append(1 if is_prime(x) else 0)
966 elif is_list(x):
967 self.stack.append(filter(is_prime, x))
968 else:
969 raise TypeError('is-prime')
970 elif t == '\x6c': #= primes
971 op = self.stack.pop()
972 x = self.stack.pop()
973 if op == 0: self.stack.append(n_primes(x))
974 elif op == 1: self.stack.append(primes_below(x))
975 elif op == 2: self.stack.append(next_prime(x))
976 elif op == 3: self.stack.append(totient(x))
977 elif op == 4: self.stack.append(factor(x, exps=False))
978 elif op == 5: self.stack.append(factor(x, exps=True))
979 elif t == '\x6d': #= scan
980 f = self.stack.pop()
981 def call_f(x, y):
982 self.stack.append(x)
983 self.stack.append(y)
984 self.evaluate(f)
985 return self.stack.pop()
986 xs = self.stack.pop()
987 res = [xs.pop(0)]
988 while xs:
989 res.append(call_f(res[-1], xs.pop(0)))
990 self.stack.append(res)
991 elif t in '\x70\x71\x72\x73\x74\x75': #= lt <, eq =, gt >, ge >=, ne !=, le <=
992 y = self.stack.pop()
993 x = self.stack.pop()
994 ops = {
995 '\x70': operator.lt,
996 '\x71': operator.eq,
997 '\x72': operator.gt,
998 '\x73': operator.ge,
999 '\x74': operator.ne,
1000 '\x75': operator.le,
1001 }
1002 self.stack.append(1 if ops[t](x, y) else 0)
1003 elif t == '\x76': #= cmp
1004 y = self.stack.pop()
1005 x = self.stack.pop()
1006 self.stack.append(cmp(x, y))
1007 elif t == '\x77': #= is-sorted
1008 x = self.stack.pop()
1009 if is_list(x):
1010 self.stack.append(1 if x == list(sorted(x)) else 0)
1011 elif is_block(x):
1012 l = self.stack.pop()
1013 def f(z):
1014 self.stack.append(z)
1015 self.evaluate(x)
1016 return self.stack.pop()
1017 sorted_l = list(sorted(l, key=f))
1018 self.stack.append(1 if l == sorted_l else 0)
1019 else:
1020 raise TypeError('sorted')
1021 elif t == '\x78': #= shift-left inits
1022 y = self.stack.pop()
1023 if is_list(y):
1024 inits = []
1025 for i in xrange(len(y) + 1):
1026 inits.append(y[:i])
1027 self.stack.append(inits)
1028 else:
1029 x = self.stack.pop()
1030 self.stack.append(x << y)
1031 elif t == '\x79': #= shift-right tails
1032 y = self.stack.pop()
1033 if is_list(y):
1034 tails = []
1035 for i in xrange(len(y) + 1):
1036 tails.append(y[len(y)-i:])
1037 self.stack.append(tails)
1038 else:
1039 x = self.stack.pop()
1040 self.stack.append(x >> y)
1041 elif t == '\x7a': #= digit-left enumerate
1042 y = self.stack.pop()
1043 if is_list(y):
1044 self.stack.append(list(map(list, enumerate(y))))
1045 else:
1046 x = self.stack.pop()
1047 self.stack.append(x * (10 ** y))
1048 elif t == '\x7b': #= digit-right
1049 y = self.stack.pop()
1050 x = self.stack.pop()
1051 self.stack.append(x // (10 ** y))
1052 elif t == '\x7c': #= power-of-2
1053 self.stack.append(2 ** self.stack.pop())
1054 elif t == '\x7d': #= power-of-10
1055 self.stack.append(10 ** self.stack.pop())
1056 elif t == '\x7e': #= sub-power-of-2
1057 self.stack.append(2 ** self.stack.pop() - 1)
1058 elif t == '\x7f': #= sub-power-of-10
1059 self.stack.append(10 ** self.stack.pop() - 1)
1060
1061 elif t == '\x80': #= pair
1062 y = self.stack.pop()
1063 x = self.stack.pop()
1064 self.stack.append([x, y])
1065 elif t == '\x81': #= copies
1066 n = self.stack.pop()
1067 x = self.stack.pop()
1068 self.stack.append([x for _ in xrange(n)])
1069 elif t == '\x82': #= take-end
1070 y = self.stack.pop()
1071 x = self.stack.pop()
1072 if is_num(x) and is_list(y):
1073 x, y = y, x
1074 self.stack.append(x[-y:])
1075 elif t == '\x83': #= cartesian-product
1076 y = self.stack.pop()
1077 x = self.stack.pop()
1078 p = it.product(x, y)
1079 self.stack.append(list(map(list, p)))
1080 elif t == '\x84': #= uppercase-alphabet
1081 self.stack.append(range(ord('A'), ord('Z') + 1))
1082 elif t == '\x85': #= lowercase-alphabet
1083 self.stack.append(range(ord('a'), ord('z') + 1))
1084 elif t == '\x86': #= ascii-digits
1085 self.stack.append(range(ord('0'), ord('9') + 1))
1086 elif t == '\x87': #= printable-ascii
1087 self.stack.append(range(32, 127))
1088 elif t in '\x88\x89\x8a\x8b\x8c\x8d\x8e\x8f': #= is-alnum, is-alpha, is-digit, is-lower, is-space, is-upper, is-printable, is-hexdigit
1089 m = [str.isalnum, str.isalpha, str.isdigit,
1090 str.islower, str.isspace, str.isupper,
1091 lambda x: all(32 <= ord(c) <= 126 for c in x),
1092 lambda x: x in '0123456789abcdefABCDEF']
1093 p = m[ord(t) - 0x88]
1094 x = to_ps(self.stack.pop())
1095 self.stack.append(1 if p(x) else 0)
1096 elif t == '\x90': #= uniq nub
1097 xs = self.stack.pop()
1098 uniq = []
1099 for x in xs:
1100 if x not in uniq:
1101 uniq.append(x)
1102 self.stack.append(uniq)
1103 elif t == '\x91': #= compress
1104 ns = self.stack.pop()
1105 xs = self.stack.pop()
1106 new = []
1107 for n, x in zip(ns, xs):
1108 new += [x for _ in xrange(n)]
1109 self.stack.append(new)
1110 elif t == '\x92': #= select
1111 xs = self.stack.pop()
1112 iis = self.stack.pop()
1113 new = []
1114 for i in iis:
1115 new.append(xs[i])
1116 self.stack.append(new)
1117 elif t == '\x93': #= permutations
1118 xs = self.stack.pop()
1119 if is_num(xs):
1120 n = xs
1121 xs = self.stack.pop()
1122 else:
1123 n = None
1124 ps = list(map(list, it.permutations(xs, n)))
1125 self.stack.append(ps)
1126 elif t == '\x94': #= fold-product
1127 xss = self.stack.pop()
1128 ys = list(map(list, it.product(*xss)))
1129 self.stack.append(ys)
1130 elif t == '\x95': #= repeat-product
1131 n = self.stack.pop()
1132 xs = self.stack.pop()
1133 ys = list(map(list, it.product(xs, repeat=n)))
1134 self.stack.append(ys)
1135 elif t == '\x96': #= combinations
1136 n = self.stack.pop()
1137 xs = self.stack.pop()
1138 ys = list(map(list, it.combinations(xs, n)))
1139 self.stack.append(ys)
1140 elif t == '\x97': #= combinations-with-replacement
1141 n = self.stack.pop()
1142 xs = self.stack.pop()
1143 ys = list(map(list, it.combinations_with_replacement(xs, n)))
1144 self.stack.append(ys)
1145 elif t == '\x98': #= pairwise
1146 xs = self.stack.pop()
1147 ys = map(list, zip(xs, xs[1:]))
1148 self.stack.append(ys)
1149 elif t == '\x99': #= flatten
1150 def flatten(xs):
1151 acc = []
1152 for x in xs:
1153 if is_list(x):
1154 acc += flatten(x)
1155 else:
1156 acc.append(x)
1157 return acc
1158 xs = self.stack.pop()
1159 self.stack.append(flatten(xs))
1160 elif t == '\x9a': #= transpose
1161 xs = self.stack.pop()
1162 self.stack.append(map(list, zip(*xs)))
1163 elif '\xa0' <= t <= '\xaf': # junk (recently popped items)
1164 self.stack.append(self.stack.junk[-1 - (ord(t) & 15)])
1165 elif t == '\xb0': #= zip
1166 ys = self.stack.pop()
1167 xs = self.stack.pop()
1168 self.stack.append(map(list, zip(xs, ys)))
1169 elif t == '\xb1': #= zipwith
1170 f = self.stack.pop()
1171 ys = self.stack.pop()
1172 xs = self.stack.pop()
1173 l0 = len(self.stack)
1174 for x, y in zip(xs, ys):
1175 self.stack.append(x)
1176 self.stack.append(y)
1177 self.evaluate(f)
1178 self.stack[l0:] = [self.stack[l0:]]
1179 elif t == '\xb2': #= counter
1180 self.stack.append(self.counter)
1181 self.counter += 1
1182 elif '\xc8' <= t <= '\xcb': # save
1183 self.regs[ord(t) & 3] = self.stack[-1]
1184 elif '\xcc' <= t <= '\xcf': # put
1185 self.regs[ord(t) & 3] = self.stack.pop()
1186 elif '\xd0' <= t <= '\xd3': # get
1187 self.stack.append(self.regs[ord(t) & 3])
1188 elif '\xd4' <= t <= '\xd7': # nip
1189 self.regs[ord(t) & 3] = self.stack.pop(-2)
1190 elif '\xd8' <= t <= '\xdb': # tuck
1191 self.stack.insert(-1, self.regs[ord(t) & 3])
1192 elif '\xdc' <= t <= '\xdf': # show
1193 self.stack.append(to_gs(show(self.regs[ord(t) & 3])))
1194 else:
1195 raise ValueError('invalid token %r' % t)
1196
1197 def eval_map(self, f, x):
1198 l0 = len(self.stack)
1199 for i in x:
1200 self.stack.append(i)
1201 self.evaluate(f)
1202 self.stack[l0:] = [self.stack[l0:]]
1203
1204 def eval_filter(self, f, x):
1205 l0 = len(self.stack)
1206 for i in x:
1207 self.stack.append(i)
1208 self.evaluate(f)
1209 if self.stack.pop():
1210 self.stack.append(i)
1211 self.stack[l0:] = [self.stack[l0:]]
1212
1213 if __name__ == '__main__':
1214 if len(sys.argv) <= 1:
1215 print >> sys.stderr, 'usage: python %s [-d] <code file>' % sys.argv[0]
1216 sys.exit(1)
1217
1218 if sys.argv[1] == '-d':
1219 DEBUG = True
1220 sys.argv.pop(1)
1221
1222 code = open(sys.argv[1], 'rb').read()
1223 stdin = '' if sys.stdin.isatty() else sys.stdin.read()
1224 GS2(code, stdin).run()