1 # -*- coding: utf-8 -*-
3 # Copyright © 2014, 2015, 2017 Simon Forman
5 # This file is part of Thun
7 # Thun is free software: you can redistribute it and/or modify
8 # it under the terms of the GNU General Public License as published by
9 # the Free Software Foundation, either version 3 of the License, or
10 # (at your option) any later version.
12 # Thun is distributed in the hope that it will be useful,
13 # but WITHOUT ANY WARRANTY; without even the implied warranty of
14 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 # GNU General Public License for more details.
17 # You should have received a copy of the GNU General Public License
18 # along with Thun. If not see <http://www.gnu.org/licenses/>.
21 When talking about Joy we use the terms "stack", "quote", "sequence",
22 "list", and others to mean the same thing: a simple linear datatype that
23 permits certain operations such as iterating and pushing and popping
24 values from (at least) one end.
26 There is no "Stack" Python class, instead we use the `cons list`_, a
27 venerable two-tuple recursive sequence datastructure, where the
28 empty tuple ``()`` is the empty stack and ``(head, rest)`` gives the
29 recursive form of a stack with one or more items on it::
31 stack := () | (item, stack)
33 Putting some numbers onto a stack::
41 Python has very nice "tuple packing and unpacking" in its syntax which
42 means we can directly "unpack" the expected arguments to a Joy function.
46 def dup((head, tail)):
47 return head, (head, tail)
49 We replace the argument "stack" by the expected structure of the stack,
50 in this case "(head, tail)", and Python takes care of unpacking the
51 incoming tuple and assigning values to the names. (Note that Python
52 syntax doesn't require parentheses around tuples used in expressions
53 where they would be redundant.)
55 Unfortunately, the Sphinx documentation generator, which is used to generate this
56 web page, doesn't handle tuples in the function parameters. And in Python 3, this
57 syntax was removed entirely. Instead you would have to write::
61 return head, (head, tail)
64 We have two very simple functions, one to build up a stack from a Python
65 iterable and another to iterate through a stack and yield its items
66 one-by-one in order. There are also two functions to generate string representations
67 of stacks. They only differ in that one prints the terms in stack from left-to-right while the other prints from right-to-left. In both functions *internal stacks* are
68 printed left-to-right. These functions are written to support :doc:`../pretty`.
70 .. _cons list: https://en.wikipedia.org/wiki/Cons#Lists
75 from builtins import map
76 def list_to_stack(el, stack=()):
77 '''Convert a Python list (or other sequence) to a Joy stack::
79 [1, 2, 3] -> (1, (2, (3, ())))
81 :param list el: A Python list or other sequence (iterators and generators
82 won't work because ``reverse()`` is called on ``el``.)
83 :param stack stack: A stack, optional, defaults to the empty stack.
87 for item in reversed(el):
92 def iter_stack(stack):
93 '''Iterate through the items on the stack.
95 :param stack stack: A stack.
103 def stack_to_string(stack):
105 Return a "pretty print" string for a stack.
107 The items are written right-to-left::
109 (top, (second, ...)) -> '... second top'
111 :param stack stack: A stack.
114 f = lambda stack: reversed(list(iter_stack(stack)))
115 return _to_string(stack, f)
118 def expression_to_string(expression):
120 Return a "pretty print" string for a expression.
122 The items are written left-to-right::
124 (top, (second, ...)) -> 'top second ...'
126 :param stack expression: A stack.
129 return _to_string(expression, iter_stack)
132 def _to_string(stack, f):
133 if not isinstance(stack, tuple): return repr(stack)
134 if not stack: return '' # shortcut
135 return ' '.join(map(_s, f(stack)))
139 '[%s]' % expression_to_string(s) if isinstance(s, tuple)
144 def concat(quote, expression):
145 '''Concatinate quote onto expression.
147 In joy [1 2] [3 4] would become [1 2 3 4].
149 :param stack quote: A stack.
150 :param stack expression: A stack.
151 :raises RuntimeError: if quote is larger than sys.getrecursionlimit().
154 # This is the fastest implementation, but will trigger
155 # RuntimeError: maximum recursion depth exceeded
156 # on quotes longer than sys.getrecursionlimit().
158 return (quote[0], concat(quote[1], expression)) if quote else expression
160 # Original implementation.
162 ## return list_to_stack(list(iter_stack(quote)), expression)
164 # In-lining is slightly faster (and won't break the
165 # recursion limit on long quotes.)
169 ## item, quote = quote
171 ## for item in reversed(temp):
172 ## expression = item, expression
177 def dnd(stack, from_index, to_index):
179 Given a stack and two indices return a rearranged stack.
180 First remove the item at from_index and then insert it at to_index,
181 the second index is relative to the stack after removal of the item
184 This function reuses all of the items and as much of the stack as it
185 can. It's meant to be used by remote clients to support drag-n-drop
186 rearranging of the stack from e.g. the StackListbox.
188 assert 0 <= from_index
190 if from_index == to_index:
192 head, n = [], from_index
199 assert len(head) == from_index
200 # now we have two cases:
201 diff = from_index - to_index
204 # so the destination index is still in the stack
211 # so the destination is in the head list
213 stack = head.pop(), stack
217 stack = head.pop(), stack
223 Return the nth item on the stack.
225 :param stack stack: A stack.
226 :param int n: An index into the stack.
227 :raises ValueError: if ``n`` is less than zero.
228 :raises IndexError: if ``n`` is equal to or greater than the length of ``stack``.