stack library

joshsh edited this page Mar 10, 2012 · 13 revisions

The stack: library contains stack- and list-oriented primitives, most of which were inherited from the [Joy](http://en.wikipedia.org/wiki/Joy_(programming_language) programming language.

List operations

Most of the stack and list primitives in Ripple are borrowed from Joy, although their semantics in some cases has been extended to fit Ripple's multiple-valued style of evaluation. Since lists are equivalent to programs in Ripple, any "list" argument to one of these primitives may just as well be any program (even an atomic program such as another primitive). Where the operation calls for dequoting a list, the program is executed instead.

at

This primitive finds the item at a specified position in a list. It expects two arguments at the top of the stack: a list and an integer index i. It pops the arguments from the stack, then pushes the item at index i in the list (where lists are 1-indexed), provided that the index is in range.

Examples:

1)  ("a" "b" "c" "d") 2 at.

  [1]  "b"

cat

This primitive concatenates two lists. It expects two arguments at the top of the stack, both lists. It pops the lists from the stack, concatenates them, and pushes the result to the stack.

Examples:

1)  (42) () cat.

  [1]  (42)

2)  (1 2) (3 4) cat.

  [1]  (1 2 3 4)

3)  (1 (2 3)) apply cat..

  [1]  1 2 3

cons

This primitive adds an item to a list. It expects two arguments at the top of the stack: an item and a list. It pops the arguments from the stack, then prepends the item to the list and pushes the result.

Examples:

1)  42 () cons.

  [1]  (42)

2)  42 (1 2 3) cons.

  [1]  (42 1 2 3)

3)  42 dup cons..

  [1]  42 42

drop

This primitive removes the first n items from a list. It expects two arguments at the top of the stack: a list and the number n. It pops the arguments from the stack, then removes the first n items from the list and pushes it onto the stack.

Examples:

1)  ("a" "b" "c" "d") 2 drop.

  [1]  ("c" "d")

2)  ("a" "b" "c" "d") 4 drop.

  [1]  ()

empty

This primitive checks whether a list is empty. It expects a single argument at the top of the stack: a list or an item which can be coerced to a list. It pops the list from the stack, then pushes true if the list is empty, otherwise false.

Examples:

1)  (1 2 3) empty.

  [1]  false

2)  rdf:nil empty.

  [1]  true

has

This primitive searches tests for the presence of an item in a list. It expects two arguments at the top of the stack: a list and an item to search for. It pops the arguments from the stack, then pushes true if an item equal (according to Ripple's natural order) to the specified item is present in the list, otherwise false.

Examples:

1)  (1 2 3) 2 has.

  [1]  true

2)  (1 2 3) 4 has.

  [1]  false

in

This primitive checks for the presence of an item in a list, like has (see above), the only difference being the order of arguments. It expects two arguments at the top of the stack: an item to search for, and a list. It pops the arguments from the stack, then pushes true if an item equal (according to Ripple's natural order) to the specified item is present in the list, otherwise false.

Examples:

1)  2 (1 2 3) in.

  [1]  true

2)  4 (1 2 3) in.

  [1]  false

max

This primitive finds the maximum item in a list according to Ripple's natural order. It expects a single argument at the top of the stack: a list. It pops the argument off of the stack, then pushes the maximum item in the list to the stack.

Examples:

1)  (1 4 6 4 1) max.

  [1]  6

min

This primitive finds the minimum item in a list according to Ripple's natural order. It expects a single argument at the top of the stack: a list. It pops the argument off of the stack, then pushes the minimum item in the list to the stack.

Examples:

1)  (1 3 1) min.

  [1]  1

of

This primitive finds the item at a specified position in a list, like at (see above), the only difference being the order of arguments. It expects two arguments at the top of the stack: an integer index i and a list. It pops the arguments from the stack, then pushes the item at index i in the list (where lists are 1-indexed), provided that the index is in range.

Examples:

1)  3 ("a" "b" "c" "d") of.

  [1]  "c"

size

This primitive finds the size, or length of a list. It expects a single argument on top of the stack: a list. It pops the list from the stack, then pushes the size of the list.

Example:

1)  (1 2 3) size.

  [1]  3

2)  () size.

  [1]  0

3)  rdf:nil size.

  [1]  0

take

This primitive takes and retains the first n items in a list. It is complementary to drop (see above). It expects two arguments at the top of the stack: a list and a number n. It pops the arguments from the stack, then finds the first n elements in the list, pushing the resulting list to the stack.

Example:

1)  ("a" "b" "c" "d") 3 take.

  [1]  ("a" "b" "c")

2)  (1 2 3) dup. 2 take. swap. 2 drop. cat.

  [1]  (1 2 3)

uncons

This item separates a list from its first item. It is complementary to cons (see above). It expects a single argument at the top of the stack: a list. It pops the list from the stack, removes the first item from the list and pushes it to the stack, then pushes the remainder of the list.

Example:

1)  (1 2 3) uncons.

  [1]  1 (2 3)

2)  (1 2 3) uncons. cons.

  [1]  (1 2 3)

Stack shufflers

These primitives permute the order of items on the stack, and/or remove items from the stack.

dup

This primitive duplicates an item. It expects one argument at the top of the stack. It pops the argument from the stack, then pushes two references to the object onto the stack.

Examples:

1)  "foo" dup.

  [1]  "foo" "foo"

2)  10 dup. mul.

  [1]  100

dupd

This primitive duplicates an item immediately below the topmost item on the stack. It expects two arguments at the top of the stack: the item to be duplicated, and any other item. It pops both arguments from the stack, then pushes two references to the item of interest, then pushes the other item.

Example:

1)  1 2 dupd.

  [1]  1 1 2

pop

This primitive pops the topmost item from the stack and yields the remaining stack as a solution.

Example:

1)  1 2 3 pop.

  [1]  1 2

popd

This primitive removes the second-to-topmost item from the stack. It expects a stack with two arguments: the item to be removed, and a don't-care item. It pops both arguments from the stack, then pushes the don't care item back to the stack.

Example:

1)  1 2 3 popd.

  [1]  1 3

rolldown

This primitive permutes the order of the top three items on the stack, shifting them down and carrying the deepest item up to the top of the stack. It expects a stack with three arguments i1, i2, and i3. It pops the arguments from the stack, then replaces them in the order i2, i3, i1.

Example:

1)  1 2 3 4 rolldown.

  [1]  1 3 4 2

rolldownd

This primitive permutes the order of the three items below the topmost item on the stack, shifting them down and carrying the deepest item up to the second-to-top position in the stack. It expects a stack with four arguments i1, i2, i3, and i4. It pops the arguments from the stack, then replaces them in the order i2, i3, i1, i4.

Example:

1)  1 2 3 4 rolldownd.

  [1]  2 3 1 4

rollup

This primitive permutes the order of the top three items on the stack, shifting them up and moving the topmost item down below the other two. It expects a stack with three arguments i1, i2, and i3. It pops the arguments from the stack, then replaces them in the order i3, i1, i2.

Example:

1)  1 2 3 4 rollup.

  [1]  1 4 2 3

rollupd

This primitive permutes the order of the three items below the topmost item on the stack, shifting them up and moving the second-to-top item on the stack down beneath the other two. It expects a stack with four arguments i1, i2, i3, and i4. It pops the arguments from the stack, then replaces them in the order i3, i1, i2, i4.

Example:

1)  1 2 3 4 rollupd.

  [1]  3 1 2 4

rotate

This primitive permutes the order of the top three items on the stack, swapping the first and third items. It expects a stack with three arguments i1, i2, and i3. It pops the arguments from the stack, then replaces them in the order i3, i2, i1.

Example:

1)  1 2 3 4 rotate.

  [1]  1 4 3 2

rotated

This primitive permutes the order of the three items beneath the top-most item on the stack, swapping the first and third items. It expects a stack with four arguments i1, i2, i3, and i4. It pops the arguments from the stack, then replaces them in the order i3, i2, i1, i4.

Example:

1)  1 2 3 4 rotated.

  [1]  3 2 1 4

self

This primitive is the identity mapping, transmitting a stack unaltered. It takes any stack and produces the same stack as a solution.

This primitive is its own inverse.

Example:

1)  1 2 3 self.

  [1]  1 2 3

swap

This primitive swaps the two items at the top of a stack. It expects two arguments at the top of the stack, which it pops off and pushes back in the opposite order.

Example:

1)  "a" "b" "c" swap.

  [1]  "a" "c" "b"

swapd

This primitive swaps the two items immediately beneath the top of a stack. It expects three arguments at the top of the stack. It pops the topmost item from the stack, then pops the other two items and pushes them back in the opposite order. Finally, it restores the original topmost item to the stack.

Example:

1)  "a" "b" "c" swapd.

  [1]  "b" "a" "c"

top

This primitive preserves the topmost item on the stack, throwing away the rest of the stack.

Example:

1) "a" top.

  [1] "a"

2) "a" "b" "c" top.

  [1] "c"

Mixed list/stack operations

These are convenience primitives.

swons

This primitive has the effect of a swap operation followed by a cons operation.

Example:

1)  (1 2 3) 42 swons.

  [1]  (42 1 2 3)

unswons

This primitive has the effect of an uncons operation followed by a swap operation.

Example:

1)  (1 2 3) unswons.

  [1]  (2 3) 1

2)  (1 2 3) unswons. swons.

  [1]  (1 2 3)