implementations/Python/joy.py

   1 #!/usr/bin/env python
   2 # -*- coding: utf-8 -*-
   3 #
   4 #    Copyright © 2022 - 2023 Simon Forman
   5 #
   6 #    This file is part of Thun
   7 #
   8 #    Thun is free software: you can redistribute it and/or modify
   9 #    it under the terms of the GNU General Public License as published by
  10 #    the Free Software Foundation, either version 3 of the License, or
  11 #    (at your option) any later version.
  12 #
  13 #    Thun is distributed in the hope that it will be useful,
  14 #    but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 #    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 #    GNU General Public License for more details.
  17 #
  18 #    You should have received a copy of the GNU General Public License
  19 #    along with Thun.  If not see <http://www.gnu.org/licenses/>.
  20 #
  21 '''
  22 ████████╗██╗  ██╗██╗   ██╗███╗   ██╗
  23 ╚══██╔══╝██║  ██║██║   ██║████╗  ██║
  24    ██║   ███████║██║   ██║██╔██╗ ██║
  25    ██║   ██╔══██║██║   ██║██║╚██╗██║
  26    ██║   ██║  ██║╚██████╔╝██║ ╚████║
  27    ╚═╝   ╚═╝  ╚═╝ ╚═════╝ ╚═╝  ╚═══╝
  28
  29 This script implements an interpreter for a dialect of Joy.
  30
  31 Joy is a programming language created by Manfred von Thun that is easy to
  32 use and understand and has many other nice properties. This Python
  33 package implements an interpreter for a dialect of Joy that attempts to
  34 stay very close to the spirit of Joy but does not precisely match the
  35 behaviour of the original version(s) written in C. The main difference
  36 between Thun and the originals, other than being written in Python, is
  37 that it works by the “Continuation-Passing Style”.
  38
  39 Here is an example of Joy code:
  40
  41
  42     [   [[abs] ii <=]
  43         [
  44             [<>] [pop !-] ||
  45         ] &&
  46     ]
  47     [[    !-] [[++]] [[--]] ifte dip]
  48     [[pop !-]  [--]   [++]  ifte    ]
  49     ifte
  50
  51 This function accepts two integers on the stack and increments or
  52 decrements one of them such that the new pair of numbers is the next
  53 coordinate pair in a square spiral (like the kind used to construct an
  54 Ulam Spiral).
  55 '''
  56 from functools import wraps
  57 from inspect import getdoc
  58 from sys import stderr
  59 from traceback import print_exc
  60 import operator
  61
  62
  63 DEFS = '''\
  64 '''.splitlines()
  65
  66
  67 '''
  68 ██╗███╗   ██╗████████╗███████╗██████╗ ██████╗ ██████╗ ███████╗████████╗███████╗██████╗
  69 ██║████╗  ██║╚══██╔══╝██╔════╝██╔══██╗██╔══██╗██╔══██╗██╔════╝╚══██╔══╝██╔════╝██╔══██╗
  70 ██║██╔██╗ ██║   ██║   █████╗  ██████╔╝██████╔╝██████╔╝█████╗     ██║   █████╗  ██████╔╝
  71 ██║██║╚██╗██║   ██║   ██╔══╝  ██╔══██╗██╔═══╝ ██╔══██╗██╔══╝     ██║   ██╔══╝  ██╔══██╗
  72 ██║██║ ╚████║   ██║   ███████╗██║  ██║██║     ██║  ██║███████╗   ██║   ███████╗██║  ██║
  73 ╚═╝╚═╝  ╚═══╝   ╚═╝   ╚══════╝╚═╝  ╚═╝╚═╝     ╚═╝  ╚═╝╚══════╝   ╚═╝   ╚══════╝╚═╝  ╚═╝
  74
  75 The joy() interpreter function is extrememly simple. It accepts a stack,
  76 an expression, and a dictionary, and it iterates through the expression
  77 putting values onto the stack and delegating execution to functions which
  78 it looks up in the dictionary.
  79
  80 '''
  81
  82
  83 def joy(stack, expression, dictionary):
  84     '''
  85     Evaluate a Joy expression on a stack.
  86
  87     This function iterates through a sequence of terms.
  88     Literals are put onto the stack and Symbols are
  89     looked up in the dictionary and the functions they
  90     denote are executed.
  91
  92     :param stack stack: The stack.
  93     :param stack expression: The expression to evaluate.
  94     :param dict dictionary: A ``dict`` mapping names to Joy functions.
  95
  96     :rtype: (stack, dictionary)
  97
  98     '''
  99     expr = push_quote(expression)  # We keep a stack-of-stacks, see below.
 100     while expr:
 101         #print(
 102         #    f'{stack_to_string(stack)} • {expr_to_string(expr)}'
 103         #    )
 104         term, expr = next_term(expr)
 105         if isinstance(term, Symbol):
 106             try:
 107                 func = dictionary[term]
 108             except KeyError:
 109                 raise UnknownSymbolError(term) from None
 110             stack, expr, dictionary = func(stack, expr, dictionary)
 111         else:
 112             stack = term, stack
 113     return stack, dictionary
 114
 115
 116 class UnknownSymbolError(KeyError):
 117     pass
 118
 119
 120 '''
 121 ███████╗████████╗ █████╗  ██████╗██╗  ██╗
 122 ██╔════╝╚══██╔══╝██╔══██╗██╔════╝██║ ██╔╝
 123 ███████╗   ██║   ███████║██║     █████╔╝
 124 ╚════██║   ██║   ██╔══██║██║     ██╔═██╗
 125 ███████║   ██║   ██║  ██║╚██████╗██║  ██╗
 126 ╚══════╝   ╚═╝   ╚═╝  ╚═╝ ╚═════╝╚═╝  ╚═╝
 127
 128 When talking about Joy we use the terms "stack", "quote", "sequence",
 129 "list", and others to mean the same thing: a simple linear datatype that
 130 permits certain operations such as iterating and pushing and popping
 131 values from (at least) one end.
 132
 133     In describing Joy I have used the term quotation to describe all of the
 134     above, because I needed a word to describe the arguments to combinators
 135     which fulfill the same role in Joy as lambda abstractions (with
 136     variables) fulfill in the more familiar functional languages. I use the
 137     term list for those quotations whose members are what I call literals:
 138     numbers, characters, truth values, sets, strings and other quotations.
 139     All these I call literals because their occurrence in code results in
 140     them being pushed onto the stack. But I also call [London Paris] a list.
 141     So, [dup *] is a quotation but not a list.
 142
 143 `"A Conversation with Manfred von Thun" w/ Stevan Apter <http://archive.vector.org.uk/art10000350>`_
 144
 145 There is no "Stack" Python class, instead we use the  `cons list`_, a
 146 venerable two-tuple recursive sequence datastructure, where the empty
 147 tuple ``()`` is the empty stack and ``(head, rest)`` gives the recursive
 148 form of a stack with one or more items on it::
 149
 150     stack := () | (item, stack)
 151
 152 Putting some numbers onto a stack::
 153
 154     Joy       Python
 155     []        ()
 156     [1]       (1, ())
 157     [2 1]     (2, (1, ()))
 158     [3 2 1]   (3, (2, (1, ())))
 159     ...
 160
 161 Python has very nice "tuple packing and unpacking" in its syntax which
 162 means we can directly "unpack" the expected arguments to a Joy function.
 163 We assign the argument stack to the expected structure of the stack and
 164 Python takes care of unpacking the incoming tuple and assigning values to
 165 the names.  (Note that Python syntax doesn't require parentheses around
 166 tuples used in expressions where they would be redundant.)
 167
 168     def dup(stack):
 169         head, tail = stack
 170         return head, (head, tail)
 171
 172
 173 .. _cons list: https://en.wikipedia.org/wiki/Cons#Lists
 174
 175 '''
 176
 177
 178 class StackUnderflowError(Exception):
 179     pass
 180
 181
 182 def list_to_stack(el, stack=()):
 183     '''
 184     Convert a Python list (or other sequence) to a Joy stack::
 185
 186     [1, 2, 3] -> (1, (2, (3, ())))
 187
 188     :param list el: A Python list or other sequence (iterators and generators
 189              won't work because ``reversed()`` is called on ``el``.)
 190     :param stack stack: A stack, optional, defaults to the empty stack. This
 191              allows for concatinating Python lists (or other sequence objects)
 192              onto an existing Joy stack.
 193     :rtype: stack
 194
 195     '''
 196     for item in reversed(el):
 197         stack = item, stack
 198     return stack
 199
 200
 201 def iter_stack(stack):
 202     '''
 203     Iterate through the items on the stack.
 204
 205     :param stack stack: A stack.
 206     :rtype: iterator
 207     '''
 208     while stack:
 209         item, stack = stack
 210         yield item
 211
 212
 213 def concat(quote, expression):
 214     '''
 215     Concatinate quote onto expression.
 216
 217     In joy [1 2] [3 4] would become [1 2 3 4].
 218
 219     :param stack quote: A stack.
 220     :param stack expression: A stack.
 221     :rtype: stack
 222     '''
 223     isnt_stack(quote)
 224     isnt_stack(expression)
 225     return list_to_stack(list(iter_stack(quote)), expression)
 226
 227     ## return (quote[0], concat(quote[1], expression)) if quote else expression
 228     # :raises RuntimeError: if quote is larger than sys.getrecursionlimit().
 229     # This is faster implementation but it would trigger
 230     # RuntimeError: maximum recursion depth exceeded
 231     # on quotes longer than sys.getrecursionlimit().
 232
 233
 234 def get_n_items(n, stack):
 235     '''
 236     Return n items and remainder of stack.
 237     Raise StackUnderflowError if there are fewer than n items on the stack.
 238     '''
 239     assert n > 0, repr(n)
 240     temp = []
 241     while n > 0:
 242         n -= 1
 243         try:
 244             item, stack = stack
 245         except ValueError:
 246             raise StackUnderflowError(
 247                 'Not enough values on stack.'
 248             ) from None
 249         temp.append(item)
 250     temp.append(stack)
 251     return tuple(temp)
 252
 253
 254 def reversed_stack(stack):
 255     '''
 256     Return list_reverseiterator object for a stack.
 257     '''
 258     return reversed(list(iter_stack(stack)))
 259
 260
 261 '''
 262 ███████╗██╗  ██╗██████╗ ██████╗ ███████╗███████╗███████╗██╗ ██████╗ ███╗   ██╗
 263 ██╔════╝╚██╗██╔╝██╔══██╗██╔══██╗██╔════╝██╔════╝██╔════╝██║██╔═══██╗████╗  ██║
 264 █████╗   ╚███╔╝ ██████╔╝██████╔╝█████╗  ███████╗███████╗██║██║   ██║██╔██╗ ██║
 265 ██╔══╝   ██╔██╗ ██╔═══╝ ██╔══██╗██╔══╝  ╚════██║╚════██║██║██║   ██║██║╚██╗██║
 266 ███████╗██╔╝ ██╗██║     ██║  ██║███████╗███████║███████║██║╚██████╔╝██║ ╚████║
 267 ╚══════╝╚═╝  ╚═╝╚═╝     ╚═╝  ╚═╝╚══════╝╚══════╝╚══════╝╚═╝ ╚═════╝ ╚═╝  ╚═══╝
 268 Expression
 269
 270 As elegant as it is to model the expression as a stack, it's not very
 271 efficient, as concatenating definitions and other quoted programs to
 272 the expression is a common and expensive operation.
 273
 274 Instead, let's keep a stack of sub-expressions, reading from them
 275 one-by-one, and prepending new sub-expressions to the stack rather than
 276 concatenating them.
 277 '''
 278
 279
 280 def push_quote(quote, expression=()):
 281     '''
 282     Put the quoted program onto the stack-of-stacks.
 283     '''
 284     return (quote, expression) if quote else expression
 285
 286
 287 def next_term(expression):
 288     '''
 289     Return the next term from the expression and the new expression.
 290     Raises ValueError if called on an empty expression.
 291     '''
 292     (item, quote), expression = expression
 293     return item, push_quote(quote, expression)
 294
 295
 296 '''
 297 ██████╗  █████╗ ██████╗ ███████╗███████╗██████╗
 298 ██╔══██╗██╔══██╗██╔══██╗██╔════╝██╔════╝██╔══██╗
 299 ██████╔╝███████║██████╔╝███████╗█████╗  ██████╔╝
 300 ██╔═══╝ ██╔══██║██╔══██╗╚════██║██╔══╝  ██╔══██╗
 301 ██║     ██║  ██║██║  ██║███████║███████╗██║  ██║
 302 ╚═╝     ╚═╝  ╚═╝╚═╝  ╚═╝╚══════╝╚══════╝╚═╝  ╚═╝
 303 Parser
 304
 305 There is a single function for converting text to joy expressions
 306 as well as a Symbol class and an Exception type.  The Symbol
 307 string class is used by the interpreter to recognize literals by
 308 the fact that they are not Symbol objects.
 309
 310 A crude grammar::
 311
 312     joy := <term>*
 313     term := <integer> | 'true' | 'false' | '[' <joy> ']' | <symbol>
 314
 315 A Joy expression is a sequence of zero or more terms.  A term is a
 316 literal value (integer, Boolean, or quoted Joy expression) or a function symbol.
 317 Function symbols are sequences of non-blanks and cannot contain square
 318 brackets.   Terms must be separated by blanks, which can be omitted
 319 around square brackets.
 320 '''
 321
 322
 323 JOY_BOOL_LITERALS = _F, _T = 'false', 'true'
 324
 325
 326 class ParseError(ValueError):
 327     '''
 328     Raised when there is a error while parsing text.
 329     '''
 330
 331
 332 class Symbol(str):
 333     '''
 334     A string class that represents Joy function names.
 335     '''
 336
 337     __repr__ = str.__str__
 338
 339
 340 def text_to_expression(text):
 341     '''
 342     Convert a string to a Joy expression.
 343
 344     When supplied with a string this function returns a Python datastructure
 345     that represents the Joy datastructure described by the text expression.
 346     Any unbalanced square brackets will raise a ParseError.
 347
 348     :param str text: Text to convert.
 349     :rtype: stack
 350     :raises ParseError: if the parse fails.
 351     '''
 352     frame = []
 353     stack = []
 354
 355     for tok in text.replace('[', ' [ ').replace(']', ' ] ').split():
 356
 357         if tok == '[':
 358             stack.append(frame)
 359             frame = []
 360             continue
 361
 362         if tok == ']':
 363             thing = list_to_stack(frame)
 364             try:
 365                 frame = stack.pop()
 366             except IndexError:
 367                 raise ParseError('Extra closing bracket.') from None
 368         elif tok == _T:
 369             thing = True
 370         elif tok == _F:
 371             thing = False
 372         else:
 373             try:
 374                 thing = int(tok)
 375             except ValueError:
 376                 thing = Symbol(tok)
 377
 378         frame.append(thing)
 379
 380     if stack:
 381         raise ParseError('Unclosed bracket.')
 382
 383     return list_to_stack(frame)
 384
 385
 386 '''
 387 ██████╗ ██████╗ ██╗███╗   ██╗████████╗███████╗██████╗
 388 ██╔══██╗██╔══██╗██║████╗  ██║╚══██╔══╝██╔════╝██╔══██╗
 389 ██████╔╝██████╔╝██║██╔██╗ ██║   ██║   █████╗  ██████╔╝
 390 ██╔═══╝ ██╔══██╗██║██║╚██╗██║   ██║   ██╔══╝  ██╔══██╗
 391 ██║     ██║  ██║██║██║ ╚████║   ██║   ███████╗██║  ██║
 392 ╚═╝     ╚═╝  ╚═╝╚═╝╚═╝  ╚═══╝   ╚═╝   ╚══════╝╚═╝  ╚═╝
 393 Printer
 394 '''
 395
 396
 397 def stack_to_string(stack):
 398     '''
 399     Return a "pretty print" string for a stack.
 400
 401     The items are written right-to-left::
 402
 403         (top, (second, ...)) -> '... second top'
 404
 405     :param stack stack: A stack.
 406     :rtype: str
 407     '''
 408     return _stack_to_string(stack, reversed_stack)
 409
 410
 411 def expression_to_string(expression):
 412     '''
 413     Return a "pretty print" string for a expression.
 414     (For historical reasons this function works on a single quote
 415     not a stack-of-stacks.)
 416
 417     The items are written left-to-right::
 418
 419         (top, (second, ...)) -> 'top second ...'
 420
 421     :param stack expression: A stack.
 422     :rtype: str
 423     '''
 424     return _stack_to_string(expression, iter_stack)
 425
 426
 427 def expr_to_string(expr):
 428     '''
 429     Return a "pretty print" string for a stack-of-stacks expression.
 430     '''
 431     return ' '.join(map(expression_to_string, iter_stack(expr)))
 432
 433
 434 def _stack_to_string(stack, iterator):
 435     isnt_stack(stack)
 436     if not stack:  # shortcut
 437         return ''
 438     return ' '.join(map(_s, iterator(stack)))
 439
 440
 441 def _s(thing):
 442     return (
 443         '[%s]' % expression_to_string(thing)
 444         if isinstance(thing, tuple)
 445         else JOY_BOOL_LITERALS[thing]
 446         if isinstance(thing, bool)
 447         else repr(thing)
 448     )
 449
 450
 451 '''
 452 ██████╗ ███████╗██████╗ ██╗
 453 ██╔══██╗██╔════╝██╔══██╗██║
 454 ██████╔╝█████╗  ██████╔╝██║
 455 ██╔══██╗██╔══╝  ██╔═══╝ ██║
 456 ██║  ██║███████╗██║     ███████╗
 457 ╚═╝  ╚═╝╚══════╝╚═╝     ╚══════╝
 458
 459 Read-Evaluate-Print Loop
 460
 461 '''
 462
 463
 464 def hack_error_message(exception):
 465     '''
 466     Some of the Python exception messages (such as when you attempt to
 467     shift a number by a negative amount of bits) are used as Joy error
 468     messages.  They should start with a capital letter and end with a
 469     period.  This function takes care of that.
 470     '''
 471     message = str(exception)
 472     if message[0].islower():
 473         message = message[0].swapcase() + message[1:]
 474     if '.' != message[-1]:
 475         message += '.'
 476     print(message, file=stderr)
 477
 478
 479 def repl(stack=(), dictionary=None):
 480     '''
 481     Read-Evaluate-Print Loop
 482
 483     Accept input and run it on the stack, loop.
 484
 485     :param stack stack: The stack.
 486     :param dict dictionary: A ``dict`` mapping names to Joy functions.
 487     :rtype: stack
 488
 489     '''
 490     if dictionary is None:
 491         dictionary = {}
 492     try:
 493         while True:
 494             try:
 495                 text = input('joy? ')
 496             except (EOFError, KeyboardInterrupt):
 497                 break
 498             try:
 499                 stack, dictionary = run(text, stack, dictionary)
 500             except UnknownSymbolError as sym:
 501                 print('Unknown:', sym, file=stderr)
 502             except SystemExit as e:
 503                 raise SystemExit from e
 504             except Exception as e:
 505                 hack_error_message(e)
 506             print(stack_to_string(stack))
 507     except SystemExit as e:
 508         raise SystemExit from e
 509     except:
 510         print_exc()
 511     print()
 512     return stack
 513
 514
 515 def run(text, stack, dictionary):
 516     '''
 517     Return the stack resulting from running the Joy code text on the stack.
 518
 519     :param str text: Joy code.
 520     :param stack stack: The stack.
 521     :param dict dictionary: A ``dict`` mapping names to Joy functions.
 522     :rtype: (stack, dictionary)
 523
 524     '''
 525     return joy(stack, text_to_expression(text), dictionary)
 526
 527
 528 def interp(stack=(), dictionary=None):
 529     '''
 530     Simple REPL with no extra output, suitable for use in scripts.
 531     '''
 532     if dictionary is None:
 533         dictionary = {}
 534     try:
 535         while True:
 536             try:
 537                 text = input()
 538             except (EOFError, KeyboardInterrupt):
 539                 break
 540             try:
 541                 stack, dictionary = run(text, stack, dictionary)
 542             except UnknownSymbolError as sym:
 543                 print('Unknown:', sym, file=stderr)
 544             except (
 545                 StackUnderflowError,
 546                 NotABoolError,
 547                 NotAListError,
 548                 NotAnIntError,
 549             ) as e:
 550                 print(e, file=stderr)
 551             except SystemExit as e:
 552                 raise SystemExit from e
 553             except Exception as e:
 554                 hack_error_message(e)
 555             print(stack_to_string(stack))
 556     except SystemExit as e:
 557         raise SystemExit from e
 558     except:
 559         print_exc()
 560     return stack
 561
 562
 563 '''
 564 ██████╗ ██╗ ██████╗████████╗██╗ ██████╗ ███╗   ██╗ █████╗ ██████╗ ██╗   ██╗
 565 ██╔══██╗██║██╔════╝╚══██╔══╝██║██╔═══██╗████╗  ██║██╔══██╗██╔══██╗╚██╗ ██╔╝
 566 ██║  ██║██║██║        ██║   ██║██║   ██║██╔██╗ ██║███████║██████╔╝ ╚████╔╝
 567 ██║  ██║██║██║        ██║   ██║██║   ██║██║╚██╗██║██╔══██║██╔══██╗  ╚██╔╝
 568 ██████╔╝██║╚██████╗   ██║   ██║╚██████╔╝██║ ╚████║██║  ██║██║  ██║   ██║
 569 ╚═════╝ ╚═╝ ╚═════╝   ╚═╝   ╚═╝ ╚═════╝ ╚═╝  ╚═══╝╚═╝  ╚═╝╚═╝  ╚═╝   ╚═╝
 570 Dictionary
 571 '''
 572
 573
 574 # This is the main dict we're building.
 575 _dictionary = {}
 576
 577
 578 def inscribe(function, d=_dictionary):
 579     '''
 580     A decorator to inscribe functions into the default dictionary.
 581     '''
 582     name = function.__name__
 583     if name.endswith('_'):
 584         name = name[:-1]
 585     d[name] = function
 586     return function
 587
 588
 589 def initialize():
 590     '''
 591     Return a dictionary of Joy functions for use with joy().
 592     '''
 593     return _dictionary.copy()
 594
 595
 596 def SimpleFunctionWrapper(f):
 597     '''
 598     Wrap functions that take and return just a stack.
 599     '''
 600
 601     @wraps(f)
 602     def SimpleFunctionWrapper_inner(stack, expr, dictionary):
 603         return f(stack), expr, dictionary
 604
 605     return SimpleFunctionWrapper_inner
 606
 607
 608 @inscribe
 609 def words(stack, expression, dictionary):
 610     '''
 611     Put a list of all the words in alphabetical order onto the stack.
 612     '''
 613     w = ()
 614     for name in reversed(sorted(dictionary)):
 615         if name.startswith('_'):
 616             continue
 617         w = (Symbol(name), ()), w
 618     return (w, stack), expression, dictionary
 619
 620
 621 HELP_TEMPLATE = '''\
 622
 623 ==== Help on %s ====
 624
 625 %s
 626
 627 ---- end ( %s )
 628 '''
 629
 630
 631 @inscribe
 632 def help_(stack, expression, dictionary):
 633     '''
 634     Accepts a quoted symbol on the top of the stack and prints its docs.
 635     '''
 636     ((symbol, _), stack) = stack
 637     word = dictionary[symbol]
 638     print(HELP_TEMPLATE % (symbol, getdoc(word), symbol))
 639     return stack, expression, dictionary
 640
 641
 642 '''
 643  ██████╗ ██████╗ ███╗   ███╗██████╗ ██╗███╗   ██╗ █████╗ ████████╗ ██████╗ ██████╗ ███████╗
 644 ██╔════╝██╔═══██╗████╗ ████║██╔══██╗██║████╗  ██║██╔══██╗╚══██╔══╝██╔═══██╗██╔══██╗██╔════╝
 645 ██║     ██║   ██║██╔████╔██║██████╔╝██║██╔██╗ ██║███████║   ██║   ██║   ██║██████╔╝███████╗
 646 ██║     ██║   ██║██║╚██╔╝██║██╔══██╗██║██║╚██╗██║██╔══██║   ██║   ██║   ██║██╔══██╗╚════██║
 647 ╚██████╗╚██████╔╝██║ ╚═╝ ██║██████╔╝██║██║ ╚████║██║  ██║   ██║   ╚██████╔╝██║  ██║███████║
 648  ╚═════╝ ╚═════╝ ╚═╝     ╚═╝╚═════╝ ╚═╝╚═╝  ╚═══╝╚═╝  ╚═╝   ╚═╝    ╚═════╝ ╚═╝  ╚═╝╚══════╝
 649 Combinators
 650 '''
 651
 652
 653 @inscribe
 654 def branch(stack, expr, dictionary):
 655     '''
 656     Use a Boolean value to select one of two quoted programs to run.
 657
 658     ::
 659
 660         branch == roll< choice i
 661
 662     ::
 663
 664            False [F] [T] branch
 665         --------------------------
 666               F
 667
 668            True [F] [T] branch
 669         -------------------------
 670                  T
 671
 672     '''
 673     then, else_, flag, stack = get_n_items(3, stack)
 674     isnt_stack(then)
 675     isnt_stack(else_)
 676     isnt_bool(flag)
 677     expr = push_quote((then if flag else else_), expr)
 678     return stack, expr, dictionary
 679
 680
 681 @inscribe
 682 def dip(stack, expr, dictionary):
 683     '''
 684     The dip combinator expects a quoted program on the stack and below it
 685     some item, it hoists the item into the expression and runs the program
 686     on the rest of the stack.
 687     ::
 688
 689            ... x [Q] dip
 690         -------------------
 691              ... Q x
 692
 693     '''
 694     quote, x, stack = get_n_items(2, stack)
 695     isnt_stack(quote)
 696     expr = push_quote((x, ()), expr)
 697     expr = push_quote(quote, expr)
 698     return stack, expr, dictionary
 699
 700
 701 @inscribe
 702 def i(stack, expr, dictionary):
 703     '''
 704     The i combinator expects a quoted program on the stack and unpacks it
 705     onto the pending expression for evaluation.
 706     ::
 707
 708            [Q] i
 709         -----------
 710             Q
 711
 712     '''
 713     quote, stack = get_n_items(1, stack)
 714     isnt_stack(quote)
 715     return stack, push_quote(quote, expr), dictionary
 716
 717
 718 S_loop = Symbol('loop')
 719
 720
 721 @inscribe
 722 def loop(stack, expr, dictionary):
 723     '''
 724     Basic loop combinator.
 725     ::
 726
 727            ... True [Q] loop
 728         -----------------------
 729               ... Q [Q] loop
 730
 731            ... False [Q] loop
 732         ------------------------
 733               ...
 734
 735     '''
 736     quote, stack = get_n_items(1, stack)
 737     isnt_stack(quote)
 738     flag, stack = get_n_items(1, stack)
 739     isnt_bool(flag)
 740     if flag:
 741         expr = push_quote((quote, (S_loop, ())), expr)
 742         expr = push_quote(quote, expr)
 743     return stack, expr, dictionary
 744
 745
 746 @inscribe
 747 def quit(stack, expr, dictionary):
 748     '''
 749     Stop the interpreter.
 750     '''
 751     raise SystemExit
 752
 753
 754 '''
 755  ██████╗ ██████╗ ██████╗ ███████╗    ██╗    ██╗ ██████╗ ██████╗ ██████╗ ███████╗
 756 ██╔════╝██╔═══██╗██╔══██╗██╔════╝    ██║    ██║██╔═══██╗██╔══██╗██╔══██╗██╔════╝
 757 ██║     ██║   ██║██████╔╝█████╗      ██║ █╗ ██║██║   ██║██████╔╝██║  ██║███████╗
 758 ██║     ██║   ██║██╔══██╗██╔══╝      ██║███╗██║██║   ██║██╔══██╗██║  ██║╚════██║
 759 ╚██████╗╚██████╔╝██║  ██║███████╗    ╚███╔███╔╝╚██████╔╝██║  ██║██████╔╝███████║
 760  ╚═════╝ ╚═════╝ ╚═╝  ╚═╝╚══════╝     ╚══╝╚══╝  ╚═════╝ ╚═╝  ╚═╝╚═════╝ ╚══════╝
 761 Core Words
 762 '''
 763
 764
 765 @inscribe
 766 @SimpleFunctionWrapper
 767 def clear(stack):
 768     '''
 769     Clear everything from the stack.
 770     ::
 771
 772         clear == stack [pop stack] loop
 773
 774            ... clear
 775         ---------------
 776
 777     '''
 778     return ()
 779
 780
 781 @inscribe
 782 @SimpleFunctionWrapper
 783 def concat_(stack):
 784     '''
 785     Concatinate the two lists on the top of the stack.
 786     ::
 787
 788            [a b c] [d e f] concat
 789         ----------------------------
 790                [a b c d e f]
 791
 792     '''
 793     tos, second, stack = get_n_items(2, stack)
 794     return concat(second, tos), stack
 795
 796
 797 @inscribe
 798 @SimpleFunctionWrapper
 799 def cons(stack):
 800     '''
 801     Given an item and a list, append the item to the list to make a new list.
 802     ::
 803
 804            a [...] cons
 805         ------------------
 806              [a ...]
 807
 808     Cons is a venerable old function from Lisp
 809     ( https://en.wikipedia.org/wiki/Cons#Lists ).
 810     Its inverse operation is uncons.
 811     '''
 812     s0, stack = get_n_items(1, stack)
 813     isnt_stack(s0)
 814     a1, stack = get_n_items(1, stack)
 815     return ((a1, s0), stack)
 816
 817
 818 @inscribe
 819 @SimpleFunctionWrapper
 820 def dup(stack):
 821     '''
 822     "Dup"licate the top item on the stack.
 823     ::
 824
 825            a dup
 826         -----------
 827             a a
 828
 829     '''
 830     a1, stack = get_n_items(1, stack)
 831     return a1, (a1, stack)
 832
 833
 834 @inscribe
 835 @SimpleFunctionWrapper
 836 def first(stack):
 837     '''
 838     Replace a list with its first item.
 839
 840            [a ...]
 841         --------------
 842               a
 843
 844     '''
 845     s0, stack = get_n_items(1, stack)
 846     isnt_stack(s0)
 847     a1, _ = get_n_items(1, s0)
 848     return a1, stack
 849
 850
 851 @inscribe
 852 @SimpleFunctionWrapper
 853 def pop(stack):
 854     '''
 855     Pop the top item from the stack and discard it.
 856
 857            a pop
 858         -----------
 859
 860     '''
 861     try:
 862         _, stack = stack
 863     except ValueError:
 864         raise StackUnderflowError('Cannot pop empty stack.') from None
 865     return stack
 866
 867
 868 @inscribe
 869 @SimpleFunctionWrapper
 870 def rest(stack):
 871     '''
 872     Replace a list with its tail.
 873
 874            [a b c] rest
 875         ------------------
 876               [b c]
 877
 878     '''
 879     s0, stack = get_n_items(1, stack)
 880     isnt_stack(s0)
 881     try:
 882         _, s1 = s0
 883     except ValueError:
 884         raise StackUnderflowError(
 885             'Cannot take rest of empty list.'
 886         ) from None
 887     return s1, stack
 888
 889
 890 @inscribe
 891 @SimpleFunctionWrapper
 892 def stack(stack):
 893     '''
 894     Put the stack onto the stack.
 895
 896               ... c b a stack
 897         ---------------------------
 898            ... c b a [a b c ...]
 899
 900     '''
 901     return stack, stack
 902
 903
 904 @inscribe
 905 @SimpleFunctionWrapper
 906 def swaack(stack):
 907     '''
 908     Swap stack.  Take a list from the top of the stack, replace the stack
 909     with the list, and put the old stack onto it.
 910
 911            1 2 3 [4 5 6] swaack
 912         --------------------------
 913               6 5 4 [3 2 1]
 914
 915     '''
 916     s1, s0 = get_n_items(1, stack)
 917     isnt_stack(s1)
 918     return s0, s1
 919
 920
 921 @inscribe
 922 @SimpleFunctionWrapper
 923 def swap(stack):
 924     '''
 925     Swap the top two items on the stack.
 926
 927            a b swap
 928         --------------
 929              b a
 930
 931     '''
 932     a2, a1, stack = get_n_items(2, stack)
 933     return (a1, (a2, stack))
 934
 935
 936 def BinaryLogicWrapper(f, name=None):
 937     '''
 938     Wrap functions that take two numbers and return a single result.
 939     '''
 940
 941     @wraps(f)
 942     def BinaryLogicWrapper_inner(stack, expression, dictionary):
 943         a, b, stack = get_n_items(2, stack)
 944         isnt_bool(a)
 945         isnt_bool(b)
 946         result = f(b, a)
 947         return (result, stack), expression, dictionary
 948
 949     if name:
 950         BinaryLogicWrapper_inner.__name__ = name
 951
 952     return BinaryLogicWrapper_inner
 953
 954
 955 def BinaryMathWrapper(func):
 956     '''
 957     Wrap functions that take two numbers and return a single result.
 958     '''
 959
 960     @wraps(func)
 961     def BinaryMathWrapper_inner(stack, expression, dictionary):
 962         a, b, stack = get_n_items(2, stack)
 963         isnt_int(a)
 964         isnt_int(b)
 965         result = func(b, a)
 966         return (result, stack), expression, dictionary
 967
 968     return BinaryMathWrapper_inner
 969
 970
 971 def UnaryLogicWrapper(f):
 972     '''
 973     Wrap functions that take one argument and return a single result.
 974     '''
 975
 976     @wraps(f)
 977     def UnaryLogicWrapper_inner(stack, expression, dictionary):
 978         a, stack = get_n_items(1, stack)
 979         isnt_bool(a)
 980         result = f(a)
 981         return (result, stack), expression, dictionary
 982
 983     return UnaryLogicWrapper_inner
 984
 985
 986 def UnaryMathWrapper(f):
 987     '''
 988     Wrap functions that take one argument and return a single result.
 989     '''
 990
 991     @wraps(f)
 992     def UnaryMathWrapper_inner(stack, expression, dictionary):
 993         a, stack = get_n_items(1, stack)
 994         isnt_int(a)
 995         result = f(a)
 996         return (result, stack), expression, dictionary
 997
 998     return UnaryMathWrapper_inner
 999
1000
1001 def UnaryWrapper(f):
1002     '''
1003     Wrap functions that take one argument and return a single result.
1004     '''
1005
1006     @wraps(f)
1007     def UnaryWrapper_inner(stack, expression, dictionary):
1008         a, stack = get_n_items(1, stack)
1009         result = f(a)
1010         return (result, stack), expression, dictionary
1011
1012     return UnaryWrapper_inner
1013
1014
1015 for F in (
1016     ## ██████╗ ██████╗ ███╗   ███╗██████╗  █████╗ ██████╗ ██╗███████╗██╗ ██████╗ ███╗   ██╗
1017     ##██╔════╝██╔═══██╗████╗ ████║██╔══██╗██╔══██╗██╔══██╗██║██╔════╝██║██╔═══██╗████╗  ██║
1018     ##██║     ██║   ██║██╔████╔██║██████╔╝███████║██████╔╝██║███████╗██║██║   ██║██╔██╗ ██║
1019     ##██║     ██║   ██║██║╚██╔╝██║██╔═══╝ ██╔══██║██╔══██╗██║╚════██║██║██║   ██║██║╚██╗██║
1020     ##╚██████╗╚██████╔╝██║ ╚═╝ ██║██║     ██║  ██║██║  ██║██║███████║██║╚██████╔╝██║ ╚████║
1021     ## ╚═════╝ ╚═════╝ ╚═╝     ╚═╝╚═╝     ╚═╝  ╚═╝╚═╝  ╚═╝╚═╝╚══════╝╚═╝ ╚═════╝ ╚═╝  ╚═══╝
1022     BinaryMathWrapper(operator.eq),
1023     BinaryMathWrapper(operator.ge),
1024     BinaryMathWrapper(operator.gt),
1025     BinaryMathWrapper(operator.le),
1026     BinaryMathWrapper(operator.lt),
1027     BinaryMathWrapper(operator.ne),
1028     ##██╗      ██████╗  ██████╗ ██╗ ██████╗
1029     ##██║     ██╔═══██╗██╔════╝ ██║██╔════╝
1030     ##██║     ██║   ██║██║  ███╗██║██║
1031     ##██║     ██║   ██║██║   ██║██║██║
1032     ##███████╗╚██████╔╝╚██████╔╝██║╚██████╗
1033     ##╚══════╝ ╚═════╝  ╚═════╝ ╚═╝ ╚═════╝
1034     UnaryWrapper(bool),  # Convert any value to Boolean.
1035     # (The only polymorphic function.)
1036     BinaryLogicWrapper(operator.xor, name='_\\/_'),
1037     BinaryLogicWrapper(operator.and_, name='/\\'),
1038     BinaryLogicWrapper(operator.or_, name='\\/'),
1039     UnaryLogicWrapper(operator.not_),
1040     ##███╗   ███╗ █████╗ ████████╗██╗  ██╗
1041     ##████╗ ████║██╔══██╗╚══██╔══╝██║  ██║
1042     ##██╔████╔██║███████║   ██║   ███████║
1043     ##██║╚██╔╝██║██╔══██║   ██║   ██╔══██║
1044     ##██║ ╚═╝ ██║██║  ██║   ██║   ██║  ██║
1045     ##╚═╝     ╚═╝╚═╝  ╚═╝   ╚═╝   ╚═╝  ╚═╝
1046     BinaryMathWrapper(operator.lshift),
1047     BinaryMathWrapper(operator.rshift),
1048     BinaryMathWrapper(operator.add),
1049     BinaryMathWrapper(operator.floordiv),
1050     BinaryMathWrapper(operator.mod),
1051     BinaryMathWrapper(operator.mul),
1052     BinaryMathWrapper(operator.pow),
1053     BinaryMathWrapper(operator.sub),
1054     UnaryMathWrapper(abs),
1055     UnaryMathWrapper(operator.neg),
1056 ):
1057     inscribe(F)
1058
1059
1060 for alias, name in (
1061     ('+', 'add'),
1062     ('-', 'sub'),
1063     ('/', 'floordiv'),
1064     ('%', 'mod'),
1065     ('*', 'mul'),
1066     ('>', 'gt'),
1067     ('<', 'lt'),
1068     ('>=', 'ge'),
1069     ('<=', 'le'),
1070     ('!=', 'ne'),
1071     ('<>', 'ne'),
1072     ('=', 'eq'),
1073     ):
1074     try:
1075         _dictionary[alias] = _dictionary[name]
1076     except KeyError:
1077         pass
1078
1079
1080 '''
1081 ██████╗ ███████╗███████╗██╗███╗   ██╗██╗████████╗██╗ ██████╗ ███╗   ██╗███████╗
1082 ██╔══██╗██╔════╝██╔════╝██║████╗  ██║██║╚══██╔══╝██║██╔═══██╗████╗  ██║██╔════╝
1083 ██║  ██║█████╗  █████╗  ██║██╔██╗ ██║██║   ██║   ██║██║   ██║██╔██╗ ██║███████╗
1084 ██║  ██║██╔══╝  ██╔══╝  ██║██║╚██╗██║██║   ██║   ██║██║   ██║██║╚██╗██║╚════██║
1085 ██████╔╝███████╗██║     ██║██║ ╚████║██║   ██║   ██║╚██████╔╝██║ ╚████║███████║
1086 ╚═════╝ ╚══════╝╚═╝     ╚═╝╚═╝  ╚═══╝╚═╝   ╚═╝   ╚═╝ ╚═════╝ ╚═╝  ╚═══╝╚══════╝
1087 Definitions
1088 '''
1089
1090
1091 class Def(object):
1092     '''
1093     Definitions are given by equations:
1094
1095         name foo bar baz ...
1096
1097     When a definition symbol is evaluated its body expression is put onto
1098     the pending expression.
1099     '''
1100
1101     # tribar = '\u2261'  # '≡'
1102
1103     def __init__(self, name, body):
1104         self.__doc__ = f'{name} {expression_to_string(body)}'
1105         self.__name__ = name
1106         self.body = body
1107
1108     def __call__(self, stack, expr, dictionary):
1109         return stack, push_quote(self.body, expr), dictionary
1110
1111     @classmethod
1112     def load_definitions(class_, stream, dictionary):
1113         '''
1114         Given an iterable of lines (strings) and a dictionary put
1115         definitions into the dictionary.
1116         '''
1117         for line in stream:
1118             name, body = text_to_expression(line)
1119             if name not in dictionary:
1120                 # filthy hack
1121                 if name.endswith('_'):
1122                     name = name + '_'
1123                     # See, I want to define some Python functions and use inscribe()
1124                     # as a decorator and get the Joy symbol from the name of the
1125                     # Python function.  But some Joy names are the same as some
1126                     # Python names, so to differentiate them I decided on a convention
1127                     # of putting an underscore after the Python function name and
1128                     # stripping it off in inscribe().  But now that there's a definition
1129                     # that ends with an underscore ('_\/_' logical Boolean xor) it's
1130                     # getting stripped off (to make '_\/'.)  So, rather than deal with
1131                     # all that in a reasonable way, I'm just going to hack it here and
1132                     # add an extra underscore for inscribe() to pick off.
1133                     # As I say, it's a filthy hack, but it works, and it took less time
1134                     # to write than this note explaining it.  :)
1135                 inscribe(class_(name, body), dictionary)
1136
1137
1138 '''
1139 ████████╗██╗   ██╗██████╗ ███████╗     ██████╗██╗  ██╗███████╗ ██████╗██╗  ██╗███████╗
1140 ╚══██╔══╝╚██╗ ██╔╝██╔══██╗██╔════╝    ██╔════╝██║  ██║██╔════╝██╔════╝██║ ██╔╝██╔════╝
1141    ██║    ╚████╔╝ ██████╔╝█████╗      ██║     ███████║█████╗  ██║     █████╔╝ ███████╗
1142    ██║     ╚██╔╝  ██╔═══╝ ██╔══╝      ██║     ██╔══██║██╔══╝  ██║     ██╔═██╗ ╚════██║
1143    ██║      ██║   ██║     ███████╗    ╚██████╗██║  ██║███████╗╚██████╗██║  ██╗███████║
1144    ╚═╝      ╚═╝   ╚═╝     ╚══════╝     ╚═════╝╚═╝  ╚═╝╚══════╝ ╚═════╝╚═╝  ╚═╝╚══════╝
1145 Type Checks
1146
1147 Simple guard functions, for type inference see the Prolog versions.
1148 '''
1149
1150
1151 class NotAListError(Exception):
1152     '''
1153     Raised when a stack is expected but not received.
1154     '''
1155
1156
1157 class NotAnIntError(Exception):
1158     pass
1159
1160
1161 class NotABoolError(Exception):
1162     pass
1163
1164
1165 def isnt_int(i):
1166     '''
1167     Raise NotAnIntError if i isn't an integer.
1168     (Booleans are not integers in Joy.)
1169     '''
1170     if not isinstance(i, int) or isinstance(i, bool):
1171         raise NotAnIntError('Not an integer.')
1172     return i
1173
1174
1175 def isnt_bool(b):
1176     '''
1177     Raise NotABoolError if b isn't a Boolean.
1178     '''
1179     if not isinstance(b, bool):
1180         raise NotABoolError('Not a Boolean value.')
1181     return b
1182
1183
1184 def isnt_stack(el):
1185     '''
1186     Raise NotAListError if el isn't a stack/quote/list.
1187     '''
1188     if not isinstance(el, tuple):
1189         raise NotAListError('Not a list.')
1190     return el
1191
1192
1193 # Put these into the dictionary so users can, uh, use them.
1194 # Not as decorators because we want to use the unwrapped
1195 # functions in our python code.
1196 inscribe(UnaryWrapper(isnt_int))
1197 inscribe(UnaryWrapper(isnt_bool))
1198 inscribe(UnaryWrapper(isnt_stack))
1199
1200
1201 '''
1202 ███████╗██╗  ██╗████████╗██████╗  █████╗
1203 ██╔════╝╚██╗██╔╝╚══██╔══╝██╔══██╗██╔══██╗
1204 █████╗   ╚███╔╝    ██║   ██████╔╝███████║
1205 ██╔══╝   ██╔██╗    ██║   ██╔══██╗██╔══██║
1206 ███████╗██╔╝ ██╗   ██║   ██║  ██║██║  ██║
1207 ╚══════╝╚═╝  ╚═╝   ╚═╝   ╚═╝  ╚═╝╚═╝  ╚═╝
1208 '''
1209
1210
1211 @inscribe
1212 def trace(stack, expr, dictionary):
1213     '''Evaluate a Joy expression on a stack and print a trace.
1214
1215     This function is just like the `i` combinator but it also prints a
1216     trace of the evaluation
1217
1218     :param stack stack: The stack.
1219     :param stack expression: The expression to evaluate.
1220     :param dict dictionary: A ``dict`` mapping names to Joy functions.
1221     :rtype: (stack, (), dictionary)
1222
1223     '''
1224     quote, stack = get_n_items(1, stack)
1225     isnt_stack(quote)
1226     history = []
1227     append = history.append
1228     local_expr = push_quote(quote)
1229     try:
1230         while local_expr:
1231             if len(history) > 1000:
1232                 break
1233             append((stack, local_expr))
1234             term, local_expr = next_term(local_expr)
1235             if isinstance(term, Symbol):
1236                 try:
1237                     func = dictionary[term]
1238                 except KeyError:
1239                     print(trace_to_string(history))
1240                     raise UnknownSymbolError(term) from None
1241                 stack, local_expr, dictionary = func(stack, local_expr, dictionary)
1242             else:
1243                 stack = term, stack
1244     except:
1245         print(trace_to_string(history))
1246         raise
1247     append((stack, local_expr))
1248     print(trace_to_string(history))
1249     return stack, expr, dictionary
1250
1251
1252 def trace_to_string(history):
1253     max_stack_length = 0
1254     lines = []
1255     for stack, expression in history:
1256         stack = stack_to_string(stack)
1257         expression = expr_to_string(expression)
1258         length = len(stack)
1259         max_stack_length = max(max_stack_length, length)
1260         lines.append((length, stack, expression))
1261     return '\n'.join(
1262         # Prefix spaces to line up '•'s.
1263         (' ' * (max_stack_length - length) + f'{stack} • {expression}')
1264         for i, (length, stack, expression) in enumerate(lines)
1265         )
1266
1267
1268 S_swaack = Symbol('swaack')
1269 S_genrec = Symbol('genrec')
1270 S_ifte = Symbol('ifte')
1271 S_infra = Symbol('infra')
1272 S_first = Symbol('first')
1273 S_primrec = Symbol('primrec')
1274 S_choice = Symbol('choice')
1275 S_i = Symbol('i')
1276 S_cond = Symbol('cond')
1277 S_step = Symbol('step')
1278 S_times = Symbol('times')
1279
1280 _ifte_ = (S_infra, (S_first, (S_choice, (S_i, ()))))
1281
1282
1283 def dnd(stack, from_index, to_index):
1284     '''
1285     Given a stack and two indices return a rearranged stack.
1286     First remove the item at from_index and then insert it at to_index,
1287     the second index is relative to the stack after removal of the item
1288     at from_index.
1289
1290     This function reuses all of the items and as much of the stack as it
1291     can.  It's meant to be used by remote clients to support drag-n-drop
1292     rearranging of the stack from e.g. the StackListbox.
1293     '''
1294     assert 0 <= from_index
1295     assert 0 <= to_index
1296     if from_index == to_index:
1297         return stack
1298     head, n = [], from_index
1299     while True:
1300         item, stack = stack
1301         n -= 1
1302         if n < 0:
1303             break
1304         head.append(item)
1305     assert len(head) == from_index
1306     # now we have two cases:
1307     diff = from_index - to_index
1308     if diff < 0:
1309         # from < to
1310         # so the destination index is still in the stack
1311         while diff:
1312             h, stack = stack
1313             head.append(h)
1314             diff += 1
1315     else:
1316         # from > to
1317         # so the destination is in the head list
1318         while diff:
1319             stack = head.pop(), stack
1320             diff -= 1
1321     stack = item, stack
1322     while head:
1323         stack = head.pop(), stack
1324     return stack
1325
1326
1327 def pick(stack, n):
1328     '''
1329     Return the nth item on the stack.
1330
1331     :param stack stack: A stack.
1332     :param int n: An index into the stack.
1333     :raises ValueError: if ``n`` is less than zero.
1334     :raises IndexError: if ``n`` is equal to or greater than the length of ``stack``.
1335     :rtype: whatever
1336     '''
1337     if n < 0:
1338         raise ValueError
1339     while True:
1340         try:
1341             item, stack = stack
1342         except ValueError:
1343             raise IndexError
1344         n -= 1
1345         if n < 0:
1346             break
1347     return item
1348
1349
1350 @inscribe
1351 def inscribe_(stack, expression, dictionary):
1352     '''
1353     Create a new Joy function definition in the Joy dictionary.  A
1354     definition is given as a quote with a name followed by a Joy
1355     expression. for example:
1356
1357         [sqr dup mul] inscribe
1358
1359     '''
1360     (name, body), stack = stack
1361     inscribe(Def(name, body), dictionary)
1362     return stack, expression, dictionary
1363
1364
1365 @inscribe
1366 @SimpleFunctionWrapper
1367 def getitem(stack):
1368     '''
1369     ::
1370
1371         getitem == drop first
1372
1373     Expects an integer and a quote on the stack and returns the item at the
1374     nth position in the quote counting from 0.
1375     ::
1376
1377            [a b c d] 0 getitem
1378         -------------------------
1379             a
1380
1381     '''
1382     n, (Q, stack) = stack
1383     return pick(Q, n), stack
1384
1385
1386 @inscribe
1387 @SimpleFunctionWrapper
1388 def drop(stack):
1389     '''
1390     ::
1391
1392         drop == [rest] times
1393
1394     Expects an integer and a quote on the stack and returns the quote with
1395     n items removed off the top.
1396     ::
1397
1398            [a b c d] 2 drop
1399         ----------------------
1400                [c d]
1401
1402     '''
1403     n, (Q, stack) = stack
1404     while n > 0:
1405         try:
1406             _, Q = Q
1407         except ValueError:
1408             raise StackUnderflowError
1409         n -= 1
1410     return Q, stack
1411
1412
1413 @inscribe
1414 @SimpleFunctionWrapper
1415 def take(stack):
1416     '''
1417     Expects an integer and a quote on the stack and returns the quote with
1418     just the top n items in reverse order (because that's easier and you can
1419     use reverse if needed.)
1420     ::
1421
1422            [a b c d] 2 take
1423         ----------------------
1424                [b a]
1425
1426     '''
1427     n, (Q, stack) = stack
1428     x = ()
1429     while n > 0:
1430         try:
1431             item, Q = Q
1432         except ValueError:
1433             raise StackUnderflowError
1434         x = item, x
1435         n -= 1
1436     return x, stack
1437
1438
1439 @inscribe
1440 def gcd2(stack, expression, dictionary):
1441     '''Compiled GCD function.'''
1442     (v1, (v2, stack)) = stack
1443     tos = True
1444     while tos:
1445         v3 = v2 % v1
1446         tos = v3 > 0
1447         (v1, (v2, stack)) = (v3, (v1, stack))
1448     return (v2, stack), expression, dictionary
1449
1450
1451 @inscribe
1452 @SimpleFunctionWrapper
1453 def choice(stack):
1454     '''
1455     Use a Boolean value to select one of two items.
1456     ::
1457
1458            A B false choice
1459         ----------------------
1460            A
1461
1462
1463            A B true choice
1464         ---------------------
1465              B
1466
1467     '''
1468     (if_, (then, (else_, stack))) = stack
1469     assert isinstance(if_, bool), repr(if_)
1470     return then if if_ else else_, stack
1471
1472
1473 @inscribe
1474 @SimpleFunctionWrapper
1475 def select(stack):
1476     '''
1477     Use a Boolean value to select one of two items from a sequence.
1478     ::
1479
1480            [A B] false select
1481         ------------------------
1482             A
1483
1484
1485            [A B] true select
1486         -----------------------
1487               B
1488
1489     The sequence can contain more than two items but not fewer.
1490     Currently Python semantics are used to evaluate the "truthiness" of the
1491     Boolean value (so empty string, zero, etc. are counted as false, etc.)
1492     '''
1493     (flag, (choices, stack)) = stack
1494     (else_, (then, _)) = choices
1495     return then if flag else else_, stack
1496
1497
1498 @inscribe
1499 @SimpleFunctionWrapper
1500 def max_(S):
1501     '''Given a list find the maximum.'''
1502     tos, stack = S
1503     return max(iter_stack(tos)), stack
1504
1505
1506 @inscribe
1507 @SimpleFunctionWrapper
1508 def min_(S):
1509     '''Given a list find the minimum.'''
1510     tos, stack = S
1511     return min(iter_stack(tos)), stack
1512
1513
1514 @inscribe
1515 @SimpleFunctionWrapper
1516 def sum_(S):
1517     '''
1518     Given a quoted sequence of numbers return the sum.
1519     ::
1520
1521         sum == 0 swap [+] step
1522
1523     '''
1524     tos, stack = S
1525     return sum(iter_stack(tos)), stack
1526
1527
1528 @inscribe
1529 @SimpleFunctionWrapper
1530 def remove(S):
1531     '''
1532     Expects an item on the stack and a quote under it and removes that item
1533     from the the quote.  The item is only removed once.  If the list is
1534     empty or the item isn't in the list then the list is unchanged.
1535     ::
1536
1537            [1 2 3 1] 1 remove
1538         ------------------------
1539              [2 3 1]
1540
1541     '''
1542     (item, (quote, stack)) = S
1543     return _remove(item, quote), stack
1544
1545
1546 def _remove(item, quote):
1547     try: head, tail = quote
1548     except ValueError: return quote
1549     return tail if head == item else (head, _remove(item, tail))
1550
1551
1552 @inscribe
1553 @SimpleFunctionWrapper
1554 def unique(S):
1555     '''Given a list remove duplicate items.'''
1556     tos, stack = S
1557     I = list(iter_stack(tos))
1558     return list_to_stack(sorted(set(I), key=I.index)), stack
1559
1560
1561 @inscribe
1562 @SimpleFunctionWrapper
1563 def sort_(S):
1564     '''Given a list return it sorted.'''
1565     tos, stack = S
1566     return list_to_stack(sorted(iter_stack(tos))), stack
1567
1568
1569 @inscribe
1570 @SimpleFunctionWrapper
1571 def disenstacken(stack):
1572     '''
1573     The disenstacken operator expects a list on top of the stack and makes that
1574     the stack discarding the rest of the stack.
1575     '''
1576     return stack[0]
1577
1578
1579 @inscribe
1580 @SimpleFunctionWrapper
1581 def reverse(S):
1582     '''
1583     Reverse the list on the top of the stack.
1584     ::
1585
1586         reverse == [] swap shunt
1587     '''
1588     (tos, stack) = S
1589     res = ()
1590     for term in iter_stack(tos):
1591         res = term, res
1592     return res, stack
1593
1594
1595 @inscribe
1596 @SimpleFunctionWrapper
1597 def shunt(stack):
1598     '''
1599     Like concat but reverses the top list into the second.
1600     ::
1601
1602         shunt == [swons] step == reverse swap concat
1603
1604            [a b c] [d e f] shunt
1605         ---------------------------
1606                [f e d a b c]
1607
1608     '''
1609     (tos, (second, stack)) = stack
1610     while tos:
1611         term, tos = tos
1612         second = term, second
1613     return second, stack
1614
1615
1616 @inscribe
1617 @SimpleFunctionWrapper
1618 def zip_(S):
1619     '''
1620     Replace the two lists on the top of the stack with a list of the pairs
1621     from each list.  The smallest list sets the length of the result list.
1622     '''
1623     (tos, (second, stack)) = S
1624     accumulator = [
1625         (a, (b, ()))
1626         for a, b in zip(iter_stack(tos), iter_stack(second))
1627         ]
1628     return list_to_stack(accumulator), stack
1629
1630
1631 @inscribe
1632 @SimpleFunctionWrapper
1633 def succ(S):
1634     '''Increment TOS.'''
1635     (tos, stack) = S
1636     return tos + 1, stack
1637
1638
1639 @inscribe
1640 @SimpleFunctionWrapper
1641 def pred(S):
1642     '''Decrement TOS.'''
1643     (tos, stack) = S
1644     return tos - 1, stack
1645
1646
1647 @inscribe
1648 @SimpleFunctionWrapper
1649 def pm(stack):
1650     '''
1651     Plus or minus
1652     ::
1653
1654            a b pm
1655         -------------
1656            a+b a-b
1657
1658     '''
1659     a, (b, stack) = stack
1660     p, m, = b + a, b - a
1661     return m, (p, stack)
1662
1663
1664 @inscribe
1665 @SimpleFunctionWrapper
1666 def divmod_(S):
1667     '''
1668     Similarly to pm ("Plus or minus") this function computes
1669     both the
1670     ::
1671
1672               a b divmod
1673         ---------------------
1674            a b div a b mod
1675         ---------------------
1676                  q r
1677
1678     Where: q * b + r == a
1679
1680     '''
1681     y, (x, stack) = S
1682     q, r = divmod(x, y)
1683     return r, (q, stack)
1684
1685
1686 @inscribe
1687 def sharing(stack, expression, dictionary):
1688     '''Print redistribution information.'''
1689     print("You may convey verbatim copies of the Program's source code as"
1690     ' you receive it, in any medium, provided that you conspicuously'
1691     ' and appropriately publish on each copy an appropriate copyright'
1692     ' notice; keep intact all notices stating that this License and'
1693     ' any non-permissive terms added in accord with section 7 apply'
1694     ' to the code; keep intact all notices of the absence of any'
1695     ' warranty; and give all recipients a copy of this License along'
1696     ' with the Program.'
1697     ' You should have received a copy of the GNU General Public License'
1698     ' along with Thun.  If not see <http://www.gnu.org/licenses/>.')
1699     return stack, expression, dictionary
1700
1701
1702 @inscribe
1703 def warranty(stack, expression, dictionary):
1704     '''Print warranty information.'''
1705     print('THERE IS NO WARRANTY FOR THE PROGRAM, TO THE EXTENT PERMITTED BY'
1706     ' APPLICABLE LAW. EXCEPT WHEN OTHERWISE STATED IN WRITING THE'
1707     ' COPYRIGHT HOLDERS AND/OR OTHER PARTIES PROVIDE THE PROGRAM'
1708     ' "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED OR'
1709     ' IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES'
1710     ' OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE'
1711     ' ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS'
1712     ' WITH YOU. SHOULD THE PROGRAM PROVE DEFECTIVE, YOU ASSUME THE'
1713     ' COST OF ALL NECESSARY SERVICING, REPAIR OR CORRECTION.')
1714     return stack, expression, dictionary
1715
1716
1717 @inscribe
1718 def x(stack, expr, dictionary):
1719     '''
1720     ::
1721
1722         x == dup i
1723
1724         ... [Q] x = ... [Q] dup i
1725         ... [Q] x = ... [Q] [Q] i
1726         ... [Q] x = ... [Q]  Q
1727
1728     '''
1729     quote, _ = stack
1730     isnt_stack(quote)
1731     return stack, push_quote(quote, expr), dictionary
1732
1733
1734 @inscribe
1735 def b(stack, expr, dictionary):
1736     '''
1737     ::
1738
1739         b == [i] dip i
1740
1741         ... [P] [Q] b == ... [P] i [Q] i
1742         ... [P] [Q] b == ... P Q
1743
1744     '''
1745     q, (p, (stack)) = stack
1746     isnt_stack(q)
1747     isnt_stack(p)
1748     expr = push_quote(q, expr)
1749     expr = push_quote(p, expr)
1750     return stack, expr, dictionary
1751
1752
1753 @inscribe
1754 def ii(stack, expr, dictionary):
1755     '''
1756     ::
1757
1758            ... a [Q] ii
1759         ------------------
1760             ... Q a Q
1761
1762     '''
1763     quote, (a, stack) = stack
1764     isnt_stack(quote)
1765     expr = push_quote((a, quote), expr)
1766     expr = push_quote(quote, expr)
1767     return stack, expr, dictionary
1768
1769
1770 @inscribe
1771 def dupdip(stack, expr, dictionary):
1772     '''
1773     ::
1774
1775         [F] dupdip == dup [F] dip
1776
1777         ... a [F] dupdip
1778         ... a dup [F] dip
1779         ... a a   [F] dip
1780         ... a F a
1781
1782     '''
1783     quote, stack = stack
1784     isnt_stack(quote)
1785     a = stack[0]
1786     expr = push_quote((a, ()), expr)
1787     expr = push_quote(quote, expr)
1788     return stack, expr, dictionary
1789
1790
1791 @inscribe
1792 def infra(stack, expr, dictionary):
1793     '''
1794     Accept a quoted program and a list on the stack and run the program
1795     with the list as its stack.  Does not affect the rest of the stack.
1796     ::
1797
1798            ... [a b c] [Q] . infra
1799         -----------------------------
1800             c b a . Q [...] swaack
1801
1802     '''
1803     quote, aggregate, stack = get_n_items(2, stack)
1804     isnt_stack(quote)
1805     isnt_stack(aggregate)
1806     expr = push_quote((stack, (S_swaack, ())), expr)
1807     expr = push_quote(quote, expr)
1808     return aggregate, expr, dictionary
1809
1810
1811 @inscribe
1812 def genrec(stack, expr, dictionary):
1813     '''
1814     General Recursion Combinator.
1815     ::
1816
1817                   [if] [then] [rec1] [rec2] genrec
1818         ---------------------------------------------------------------------
1819            [if] [then] [rec1 [[if] [then] [rec1] [rec2] genrec] rec2] ifte
1820
1821     From "Recursion Theory and Joy" (j05cmp.html) by Manfred von Thun:
1822     "The genrec combinator takes four program parameters in addition to
1823     whatever data parameters it needs. Fourth from the top is an if-part,
1824     followed by a then-part. If the if-part yields true, then the then-part
1825     is executed and the combinator terminates. The other two parameters are
1826     the rec1-part and the rec2-part. If the if-part yields false, the
1827     rec1-part is executed. Following that the four program parameters and
1828     the combinator are again pushed onto the stack bundled up in a quoted
1829     form. Then the rec2-part is executed, where it will find the bundled
1830     form. Typically it will then execute the bundled form, either with i or
1831     with app2, or some other combinator."
1832
1833     The way to design one of these is to fix your base case [then] and the
1834     test [if], and then treat rec1 and rec2 as an else-part "sandwiching"
1835     a quotation of the whole function.
1836
1837     For example, given a (general recursive) function 'F':
1838     ::
1839
1840         F == [I] [T] [R1] [R2] genrec
1841
1842     If the [I] if-part fails you must derive R1 and R2 from:
1843     ::
1844
1845         ... R1 [F] R2
1846
1847     Just set the stack arguments in front, and figure out what R1 and R2
1848     have to do to apply the quoted [F] in the proper way.  In effect, the
1849     genrec combinator turns into an ifte combinator with a quoted copy of
1850     the original definition in the else-part:
1851     ::
1852
1853         F == [I] [T] [R1]   [R2] genrec
1854           == [I] [T] [R1 [F] R2] ifte
1855
1856     Primitive recursive functions are those where R2 == i.
1857     ::
1858
1859         P == [I] [T] [R] tailrec
1860           == [I] [T] [R [P] i] ifte
1861           == [I] [T] [R P] ifte
1862
1863     '''
1864     rec2, rec1, then, if_, stack = get_n_items(4, stack)
1865     isnt_stack(if_)
1866     isnt_stack(then)
1867     isnt_stack(rec1)
1868     isnt_stack(rec2)
1869     F = (if_, (then, (rec1, (rec2, (S_genrec, ())))))
1870     else_ = concat(rec1, (F, rec2))
1871     stack = (else_, (then, (if_, stack)))
1872     expr = push_quote((S_ifte, ()), expr)
1873     return stack, expr, dictionary
1874
1875
1876 @inscribe
1877 def map_(stack, expr, dictionary):
1878     '''
1879     Run the quoted program on TOS on the items in the list under it, push a
1880     new list with the results in place of the program and original list.
1881     '''
1882     quote, aggregate, stack = get_n_items(2, stack)
1883     isnt_stack(quote)
1884     isnt_stack(aggregate)
1885     if not aggregate:
1886         return (aggregate, stack), expr, dictionary
1887     batch = ()
1888     for term in iter_stack(aggregate):
1889         s = term, stack
1890         batch = (s, (quote, (S_infra, (S_first, batch))))
1891     stack = (batch, ((), stack))
1892     expr = push_quote((S_infra, ()), expr)
1893     return stack, expr, dictionary
1894
1895
1896 @inscribe
1897 def primrec(stack, expr, dictionary):
1898     '''
1899     From the "Overview of the language JOY":
1900
1901     > The primrec combinator expects two quoted programs in addition to a
1902     data parameter. For an integer data parameter it works like this: If
1903     the data parameter is zero, then the first quotation has to produce
1904     the value to be returned. If the data parameter is positive then the
1905     second has to combine the data parameter with the result of applying
1906     the function to its predecessor.::
1907
1908         5  [1]  [*]  primrec
1909
1910     > Then primrec tests whether the top element on the stack (initially
1911     the 5) is equal to zero. If it is, it pops it off and executes one of
1912     the quotations, the [1] which leaves 1 on the stack as the result.
1913     Otherwise it pushes a decremented copy of the top element and
1914     recurses. On the way back from the recursion it uses the other
1915     quotation, [*], to multiply what is now a factorial on top of the
1916     stack by the second element on the stack.::
1917
1918         n [Base] [Recur] primrec
1919
1920            0 [Base] [Recur] primrec
1921         ------------------------------
1922               Base
1923
1924              n [Base] [Recur] primrec
1925         ------------------------------------------ n > 0
1926            n (n-1) [Base] [Recur] primrec Recur
1927
1928     '''
1929     recur, base, n, stack = get_n_items(3, stack)
1930     isnt_stack(recur)
1931     isnt_stack(base)
1932     if n <= 0:
1933         expr = push_quote(base, expr)
1934     else:
1935         expr = push_quote(recur, expr)
1936         expr = push_quote((S_primrec, ()), expr)
1937         stack = recur, (base, (n - 1, (n, stack)))
1938     return stack, expr, dictionary
1939
1940
1941 @inscribe
1942 def ifte(stack, expr, dictionary):
1943     '''
1944     If-Then-Else Combinator
1945
1946
1947                 ... [if] [then] [else] ifte
1948        -------------------------------------------------------
1949           ... [else] [then] [...] [if] infra first choice i
1950
1951
1952     Has the effect of grabbing a copy of the stack on which to run the
1953     if-part using infra.
1954     '''
1955     else_, then, if_, stack = get_n_items(3, stack)
1956     expr = push_quote(_ifte_, expr)
1957     stack = (if_, (stack, (then, (else_, stack))))
1958     return stack, expr, dictionary
1959
1960
1961 @inscribe
1962 def cond(stack, expr, dictionary):
1963     '''
1964     This combinator works like a case statement.  It expects a single quote
1965     on the stack that must contain zero or more condition quotes and a
1966     default quote.  Each condition clause should contain a quoted predicate
1967     followed by the function expression to run if that predicate returns
1968     true.  If no predicates return true the default function runs.
1969
1970     It works by rewriting into a chain of nested `ifte` expressions, e.g.::
1971
1972            [[D]] cond
1973         ----------------
1974              D
1975
1976            [[[IF] THEN] [D]] cond
1977         ---------------------------- (with single condition, same as ifte)
1978             [IF] [THEN] [D] ifte
1979
1980
1981               [[[IF] THEN] ...] cond
1982         ----------------------------------- (multiple conditions)
1983            [IF] [THEN] [[...] cond] ifte
1984
1985
1986     The middle case isn't actually implemented.  It's implied by the
1987     base case and the "multiple conditions" case.
1988     '''
1989     conditions, stack = get_n_items(1, stack)
1990     isnt_stack(conditions)
1991     if not conditions:
1992         raise StackUnderflowError('cond without default clause')
1993
1994     condition_clause, conditions = conditions
1995     isnt_stack(condition_clause)
1996
1997     if not conditions: # This is the default clause, run it.
1998         expr = push_quote(condition_clause, expr)
1999     else:
2000         if_, then = get_n_items(1, condition_clause)
2001         isnt_stack(if_)
2002         else_ = (conditions, (S_cond, ()))
2003         stack = (else_, (then, (if_, stack)))
2004         expr = push_quote((S_ifte, ()), expr)
2005
2006     return stack, expr, dictionary
2007
2008
2009 @inscribe
2010 def dipd(stack, expr, dictionary):
2011     '''
2012     The dipd combinator is like dip but expects two items.
2013
2014            ... y x [Q] dipd
2015         ----------------------
2016              ... Q y x
2017
2018     '''
2019     quote, x, y, stack = get_n_items(3, stack)
2020     isnt_stack(quote)
2021     expr = push_quote((y, (x, ())), expr)
2022     expr = push_quote(quote, expr)
2023     return stack, expr, dictionary
2024
2025
2026 @inscribe
2027 def dipdd(stack, expr, dictionary):
2028     '''
2029     The dipdd combinator is like dip but expects three items.
2030
2031            ... y x z [Q] dipdd
2032         -------------------------
2033              ... Q y x z
2034
2035     '''
2036     quote, x, y, z, stack = get_n_items(3, stack)
2037     isnt_stack(quote)
2038     expr = push_quote((z, (y, (x, ()))), expr)
2039     expr = push_quote(quote, expr)
2040     return stack, expr, dictionary
2041
2042
2043 @inscribe
2044 def cmp_(stack, expr, dictionary):
2045     '''
2046     cmp takes two values and three quoted programs on the stack and runs
2047     one of the three depending on the results of comparing the two values:
2048     ::
2049
2050            a b [G] [E] [L] cmp
2051         ------------------------- a > b
2052             G
2053
2054            a b [G] [E] [L] cmp
2055         ------------------------- a = b
2056                 E
2057
2058            a b [G] [E] [L] cmp
2059         ------------------------- a < b
2060                 L
2061     '''
2062     L, E, G, b, a, stack = get_n_items(5, stack)
2063     isnt_stack(L)
2064     isnt_stack(E)
2065     isnt_stack(G)
2066     isnt_int(b)
2067     isnt_int(a)
2068     expr = push_quote(G if a > b else L if a < b else E, expr)
2069     return stack, expr, dictionary
2070
2071
2072 @inscribe
2073 def step(stack, expr, dictionary):
2074     '''
2075     Run a quoted program on each item in a sequence.
2076     ::
2077
2078            ... [] [Q] step
2079         ---------------------
2080                  ...
2081
2082
2083            ... [a] [Q] step
2084         ----------------------
2085                ... a Q
2086
2087
2088             ... [a b c] [Q] step
2089         ----------------------------
2090            ... a Q [b c] [Q] step
2091
2092     The step combinator executes the quotation on each member of the list
2093     on top of the stack.
2094     '''
2095     quote, aggregate, stack = get_n_items(2, stack)
2096     isnt_stack(quote)
2097     isnt_stack(aggregate)
2098     if not aggregate:
2099         return stack, expr, dictionary
2100
2101     head, tail = aggregate
2102     stack = head, stack
2103     if tail:
2104         expr = push_quote((tail, (quote, (S_step, ()))), expr)
2105     expr = push_quote(quote, expr)
2106     return stack, expr, dictionary
2107
2108
2109 @inscribe
2110 def times(stack, expr, dictionary):
2111     '''
2112     times == [-- dip] cons [swap] infra [0 >] swap while pop
2113     ::
2114
2115            ... n [Q] times
2116         ---------------------  w/ n <= 0
2117                  ...
2118
2119
2120            ... 1 [Q] times
2121         ---------------------
2122                 ... Q
2123
2124
2125               ... n [Q] times
2126         ---------------------------  w/ n > 1
2127            ... Q (n-1) [Q] times
2128
2129     '''
2130     # times == [-- dip] cons [swap] infra [0 >] swap while pop
2131     quote, n, stack = get_n_items(2, stack)
2132     isnt_stack(quote)
2133     isnt_int(n)
2134     if n <= 0:
2135         return stack, expr, dictionary
2136     n -= 1
2137     if n:
2138         expr = push_quote((n, (quote, (S_times, ()))), expr)
2139     expr = push_quote(quote, expr)
2140     return stack, expr, dictionary
2141
2142
2143 @inscribe
2144 @SimpleFunctionWrapper
2145 def _Tree_add_Ee(stack):
2146   """
2147   ::
2148
2149     ([a4 a5 ...1] a3 a2 a1 -- [a2 a3 ...1])
2150
2151   """
2152   (a1, (a2, (a3, ((a4, (a5, s1)), s2)))) = stack
2153   return ((a2, (a3, s1)), s2)
2154
2155
2156 @inscribe
2157 @SimpleFunctionWrapper
2158 def _Tree_delete_R0(stack):
2159   """
2160   ::
2161
2162     ([a2 ...1] a1 -- [a2 ...1] a2 a1 a1)
2163
2164   """
2165   (a1, ((a2, s1), s2)) = stack
2166   return (a1, (a1, (a2, ((a2, s1), s2))))
2167
2168
2169 @inscribe
2170 @SimpleFunctionWrapper
2171 def _Tree_delete_clear_stuff(stack):
2172   """
2173   ::
2174
2175     (a3 a2 [a1 ...1] -- [...1])
2176
2177   """
2178   ((a1, s1), (a2, (a3, s2))) = stack
2179   return (s1, s2)
2180
2181
2182 @inscribe
2183 @SimpleFunctionWrapper
2184 def _Tree_get_E(stack):
2185   """
2186   ::
2187
2188     ([a3 a4 ...1] a2 a1 -- a4)
2189
2190   """
2191   (a1, (a2, ((a3, (a4, s1)), s2))) = stack
2192   return (a4, s2)
2193
2194
2195 @inscribe
2196 @SimpleFunctionWrapper
2197 def ccons(stack):
2198   """
2199   ::
2200
2201     (a2 a1 [...1] -- [a2 a1 ...1])
2202
2203   """
2204   (s1, (a1, (a2, s2))) = stack
2205   return ((a2, (a1, s1)), s2)
2206
2207
2208 ##def cons(stack):
2209 ##  """
2210 ##  ::
2211 ##
2212 ##    (a1 [...0] -- [a1 ...0])
2213 ##
2214 ##  """
2215 ##  try: s0, stack = stack
2216 ##  except ValueError: raise StackUnderflowError('Not enough values on stack.')
2217 ##  if not isinstance(s0, tuple): raise NotAListError('Not a list.')
2218 ##  try: a1, s23 = stack
2219 ##  except ValueError: raise StackUnderflowError('Not enough values on stack.')
2220 ##  return ((a1, s0), s23)
2221
2222
2223 ##def dup(stack):
2224 ##  """
2225 ##  ::
2226 ##
2227 ##    (a1 -- a1 a1)
2228 ##
2229 ##  """
2230 ##  (a1, s23) = stack
2231 ##  return (a1, (a1, s23))
2232
2233
2234 @inscribe
2235 @SimpleFunctionWrapper
2236 def dupd(stack):
2237   """
2238   ::
2239
2240     (a2 a1 -- a2 a2 a1)
2241
2242   """
2243   (a1, (a2, s23)) = stack
2244   return (a1, (a2, (a2, s23)))
2245
2246
2247 @inscribe
2248 @SimpleFunctionWrapper
2249 def dupdd(stack):
2250   """
2251   ::
2252
2253     (a3 a2 a1 -- a3 a3 a2 a1)
2254
2255   """
2256   (a1, (a2, (a3, s23))) = stack
2257   return (a1, (a2, (a3, (a3, s23))))
2258
2259
2260 ##def first(stack):
2261 ##  """
2262 ##  ::
2263 ##
2264 ##    ([a1 ...1] -- a1)
2265 ##
2266 ##  """
2267 ##  ((a1, s1), s23) = stack
2268 ##  return (a1, s23)
2269
2270
2271 @inscribe
2272 @SimpleFunctionWrapper
2273 def first_two(stack):
2274   """
2275   ::
2276
2277     ([a1 a2 ...1] -- a1 a2)
2278
2279   """
2280   ((a1, (a2, s1)), s2) = stack
2281   return (a2, (a1, s2))
2282
2283
2284 @inscribe
2285 @SimpleFunctionWrapper
2286 def fourth(stack):
2287   """
2288   ::
2289
2290     ([a1 a2 a3 a4 ...1] -- a4)
2291
2292   """
2293   ((a1, (a2, (a3, (a4, s1)))), s2) = stack
2294   return (a4, s2)
2295
2296
2297 @inscribe
2298 @SimpleFunctionWrapper
2299 def over(stack):
2300   """
2301   ::
2302
2303     (a2 a1 -- a2 a1 a2)
2304
2305   """
2306   (a1, (a2, s23)) = stack
2307   return (a2, (a1, (a2, s23)))
2308
2309
2310 ##def pop(stack):
2311 ##  """
2312 ##  ::
2313 ##
2314 ##    (a1 --)
2315 ##
2316 ##  """
2317 ##  try:
2318 ##    (a1, s23) = stack
2319 ##  except ValueError:
2320 ##    raise StackUnderflowError('Cannot pop empty stack.')
2321 ##  return s23
2322
2323
2324 @inscribe
2325 @SimpleFunctionWrapper
2326 def popd(stack):
2327   """
2328   ::
2329
2330     (a2 a1 -- a1)
2331
2332   """
2333   (a1, (a2, s23)) = stack
2334   return (a1, s23)
2335
2336
2337 @inscribe
2338 @SimpleFunctionWrapper
2339 def popdd(stack):
2340   """
2341   ::
2342
2343     (a3 a2 a1 -- a2 a1)
2344
2345   """
2346   (a1, (a2, (a3, s23))) = stack
2347   return (a1, (a2, s23))
2348
2349
2350 @inscribe
2351 @SimpleFunctionWrapper
2352 def popop(stack):
2353   """
2354   ::
2355
2356     (a2 a1 --)
2357
2358   """
2359   (a1, (a2, s23)) = stack
2360   return s23
2361
2362
2363 @inscribe
2364 @SimpleFunctionWrapper
2365 def popopd(stack):
2366   """
2367   ::
2368
2369     (a3 a2 a1 -- a1)
2370
2371   """
2372   (a1, (a2, (a3, s23))) = stack
2373   return (a1, s23)
2374
2375
2376 @inscribe
2377 @SimpleFunctionWrapper
2378 def popopdd(stack):
2379   """
2380   ::
2381
2382     (a4 a3 a2 a1 -- a2 a1)
2383
2384   """
2385   (a1, (a2, (a3, (a4, s23)))) = stack
2386   return (a1, (a2, s23))
2387
2388
2389 ##def rest(stack):
2390 ##  """
2391 ##  ::
2392 ##
2393 ##    ([a1 ...0] -- [...0])
2394 ##
2395 ##  """
2396 ##  try:
2397 ##    s0, stack = stack
2398 ##  except ValueError:
2399 ##    raise StackUnderflowError
2400 ##  if not isinstance(s0, tuple):
2401 ##    raise NotAListError('Not a list.')
2402 ##  try:
2403 ##    _, s1 = s0
2404 ##  except ValueError:
2405 ##    raise StackUnderflowError('Cannot take rest of empty list.')
2406 ##  return (s1, stack)
2407
2408
2409 @inscribe
2410 @SimpleFunctionWrapper
2411 def rolldown(stack):
2412   """
2413   ::
2414
2415     (a1 a2 a3 -- a2 a3 a1)
2416
2417   """
2418   (a3, (a2, (a1, s23))) = stack
2419   return (a1, (a3, (a2, s23)))
2420
2421
2422 @inscribe
2423 @SimpleFunctionWrapper
2424 def rollup(stack):
2425   """
2426   ::
2427
2428     (a1 a2 a3 -- a3 a1 a2)
2429
2430   """
2431   (a3, (a2, (a1, s23))) = stack
2432   return (a2, (a1, (a3, s23)))
2433
2434
2435 @inscribe
2436 @SimpleFunctionWrapper
2437 def rrest(stack):
2438   """
2439   ::
2440
2441     ([a1 a2 ...1] -- [...1])
2442
2443   """
2444   ((a1, (a2, s1)), s2) = stack
2445   return (s1, s2)
2446
2447
2448 @inscribe
2449 @SimpleFunctionWrapper
2450 def second(stack):
2451   """
2452   ::
2453
2454     ([a1 a2 ...1] -- a2)
2455
2456   """
2457   ((a1, (a2, s1)), s2) = stack
2458   return (a2, s2)
2459
2460
2461 @inscribe
2462 @SimpleFunctionWrapper
2463 def stack(stack):
2464   """
2465   ::
2466
2467     (... -- ... [...])
2468
2469   """
2470   s0 = stack
2471   return (s0, s0)
2472
2473
2474 @inscribe
2475 @SimpleFunctionWrapper
2476 def stuncons(stack):
2477   """
2478   ::
2479
2480     (... a1 -- ... a1 a1 [...])
2481
2482   """
2483   (a1, s1) = stack
2484   return (s1, (a1, (a1, s1)))
2485
2486
2487 @inscribe
2488 @SimpleFunctionWrapper
2489 def stununcons(stack):
2490   """
2491   ::
2492
2493     (... a2 a1 -- ... a2 a1 a1 a2 [...])
2494
2495   """
2496   (a1, (a2, s1)) = stack
2497   return (s1, (a2, (a1, (a1, (a2, s1)))))
2498
2499
2500 ##def swaack(stack):
2501 ##  """
2502 ##  ::
2503 ##
2504 ##    ([...1] -- [...0])
2505 ##
2506 ##  """
2507 ##  try:
2508 ##    (s1, s0) = stack
2509 ##  except ValueError:
2510 ##    raise StackUnderflowError('Not enough values on stack.')
2511 ##  if not isinstance(s1, tuple):
2512 ##    raise NotAListError('Not a list.')
2513 ##  return (s0, s1)
2514
2515
2516 ##def swap(stack):
2517 ##  """
2518 ##  ::
2519 ##
2520 ##    (a1 a2 -- a2 a1)
2521 ##
2522 ##  """
2523 ##  try:
2524 ##    (a2, (a1, s23)) = stack
2525 ##  except ValueError:
2526 ##    raise StackUnderflowError('Not enough values on stack.')
2527 ##  return (a1, (a2, s23))
2528
2529
2530 @inscribe
2531 @SimpleFunctionWrapper
2532 def swons(stack):
2533   """
2534   ::
2535
2536     ([...1] a1 -- [a1 ...1])
2537
2538   """
2539   (a1, (s1, s2)) = stack
2540   return ((a1, s1), s2)
2541
2542
2543 @inscribe
2544 @SimpleFunctionWrapper
2545 def third(stack):
2546   """
2547   ::
2548
2549     ([a1 a2 a3 ...1] -- a3)
2550
2551   """
2552   ((a1, (a2, (a3, s1))), s2) = stack
2553   return (a3, s2)
2554
2555
2556 @inscribe
2557 @SimpleFunctionWrapper
2558 def tuck(stack):
2559   """
2560   ::
2561
2562     (a2 a1 -- a1 a2 a1)
2563
2564   """
2565   (a1, (a2, s23)) = stack
2566   return (a1, (a2, (a1, s23)))
2567
2568
2569 @inscribe
2570 @SimpleFunctionWrapper
2571 def uncons(stack):
2572   """
2573   ::
2574
2575     ([a1 ...0] -- a1 [...0])
2576
2577   """
2578   ((a1, s0), s23) = stack
2579   return (s0, (a1, s23))
2580
2581
2582 @inscribe
2583 @SimpleFunctionWrapper
2584 def unit(stack):
2585   """
2586   ::
2587
2588     (a1 -- [a1 ])
2589
2590   """
2591   (a1, s23) = stack
2592   return ((a1, ()), s23)
2593
2594
2595 @inscribe
2596 @SimpleFunctionWrapper
2597 def unswons(stack):
2598   """
2599   ::
2600
2601     ([a1 ...1] -- [...1] a1)
2602
2603   """
2604   ((a1, s1), s2) = stack
2605   return (a1, (s1, s2))
2606
2607
2608 def default_defs(dictionary):
2609     Def.load_definitions(DEFS, dictionary)
2610
2611
2612 if __name__ == '__main__':
2613     import sys
2614
2615     J = interp if '-q' in sys.argv else repl
2616     dictionary = initialize()
2617     default_defs(dictionary)
2618     try:
2619         stack = J(dictionary=dictionary)
2620     except SystemExit:
2621         pass
2622 ##    jcode = "5 10 [>][++][*]ifte"
2623 ##    jcode = '1 2 [[+]] cond'
2624 ##    jcode = '1 2 [[[>] -] [[<] +] [*]] cond'
2625 ##    jcode = '2 1 [[[>] -] [[<] +] [*]] cond'
2626 ##    jcode = '3 3 [[[>] -] [[<] +] [*]] cond'
2627 ##    jcode = '3 dup [dup mul] times'
2628 ##    jcode = '0 [1 2 3] [add] step'
2629 ##    stack, _ = run(jcode, (), dictionary)
2630     ##print(stack_to_string(stack))