# Stack or Quote or Sequence or List…

## `joy.utils.stack`

When talking about Joy we use the terms “stack”, “quote”, “sequence”, “list”, and others to mean the same thing: a simple linear datatype that permits certain operations such as iterating and pushing and popping values from (at least) one end.

There is no “Stack” Python class, instead we use the cons list, a venerable two-tuple recursive sequence datastructure, where the empty tuple `()` is the empty stack and `(head, rest)` gives the recursive form of a stack with one or more items on it:

    stack := () | (item, stack)

Putting some numbers onto a stack:

    ()
    (1, ())
    (2, (1, ()))
    (3, (2, (1, ())))
    ...

Python has very nice “tuple packing and unpacking” in its syntax which means we can directly “unpack” the expected arguments to a Joy function.

For example:

    def dup((head, tail)):
      return head, (head, tail)

We replace the argument “stack” by the expected structure of the stack, in this case “(head, tail)”, and Python takes care of unpacking the incoming tuple and assigning values to the names. (Note that Python syntax doesn’t require parentheses around tuples used in expressions where they would be redundant.)

Unfortunately, the Sphinx documentation generator, which is used to generate this web page, doesn’t handle tuples in the function parameters. And in Python 3, this syntax was removed entirely. Instead you would have to write:

    def dup(stack):
      head, tail = stack
      return head, (head, tail)

We have two very simple functions, one to build up a stack from a Python iterable and another to iterate through a stack and yield its items one-by-one in order. There are also two functions to generate string representations 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 printed left-to-right. These functions are written to support Tracing Joy Execution.

`joy.utils.stack.``concat`(quote, expression)

  Concatinate quote onto expression.

  In joy [1 2] [3 4] would become [1 2 3 4].

  Parameters: | quote (stack) – A stack. expression (stack) – A stack.
  Raises: | RuntimeError – if quote is larger than sys.getrecursionlimit().
  Return type: | stack

`joy.utils.stack.``expression_to_string`(expression)

  Return a “pretty print” string for a expression.

  The items are written left-to-right:

      (top, (second, ...)) -> 'top second ...'

  Parameters: | expression (stack) – A stack.
  Return type: | str

`joy.utils.stack.``iter_stack`(stack)

  Iterate through the items on the stack.

  Parameters: | stack (stack) – A stack.
  Return type: | iterator

`joy.utils.stack.``list_to_stack`(el, stack=())

  Convert a Python list (or other sequence) to a Joy stack:

      [1, 2, 3] -> (1, (2, (3, ())))

  Parameters: | el (list) – A Python list or other sequence (iterators and generators won’t work because `reverse()` is called on `el`.) stack (stack) – A stack, optional, defaults to the empty stack.
  Return type: | stack

`joy.utils.stack.``pick`(s, n)

  Return the nth item on the stack.

  Parameters: | s (stack) – A stack. n (int) – An index into the stack.
  Raises: | ValueError – if `n` is less than zero. IndexError – if `n` is equal to or greater than the length of `s`.
  Return type: | whatever

`joy.utils.stack.``stack_to_string`(stack)

  Return a “pretty print” string for a stack.

  The items are written right-to-left:

      (top, (second, ...)) -> '... second top'

  Parameters: | stack (stack) – A stack.
  Return type: | str