stream library

joshsh edited this page Feb 20, 2012 · 6 revisions

The stream: library deals specifically with the stream-oriented aspect of Ripple. It contains primitives for stream splitting and intersection, deduplication and pruning. It also contains "closed world" primitives for counting and ranking solutions.

both

This primitive forks a stream based on the top two items on the stack. It pops its two arguments from the stack, then produces two solutions: a stack formed by pushing the first argument back onto the rest of the stack, and another by pushing the second argument.

Example:

1)  1 2 3 both.

  [1]  1 3
  [2]  1 2

count

This is a closed-world primitive which applies a mapping and counts the number of solutions. It expects a single argument at the top of the stack: a mapping. It pushes the op operator to the top of the stack in order to activate the mapping, then applies Ripple's default lazy evaluator to that stack and gathers all solutions. It then pops the mapping from the original stack and replaces it with an integer representing the number of solutions found.

Examples:

1)  1000 2000 both count.

  [1]  1000 2000 2

2)  "One, two, three stacks! Ah ah ah!" ("," split. each.) count.

  [1]  "One, two, three stacks! Ah ah ah!" 3

3) @list danny: <http://identi.ca/user/114>
4)  "Danny knows " (:danny. foaf:knows.) count. concat. " people" concat.

  [1]  "Danny knows 76 people"

distinct

This primitive filters out solutions which have already been produced. Two solutions (stacks) are identical if they are equal according to Ripple's natural order. The Ripple Java implementation uses space-saving memo structures to keep track of sets of stacks. The primitive takes no arguments, but allows the rest of the stack to be evaluated before memoizing solutions.

Examples:

1)  42 (1 1 2 1 2 2) each.

  [1]  42 1
  [2]  42 1
  [3]  42 2
  [4]  42 1
  [5]  42 2
  [6]  42 2

2)  42 (1 1 2 1 2 2) each. distinct.

  [1]  42 1
  [2]  42 2

each

This primitive produces a solution for each item in a list. It expects one argument on the top of the stack: a list of items. It pops the list from the stack, then for each item in the stack, it pushes the item to the rest of the stack, producing the resulting stack as a solution.

Examples:

1)  (1 2 3) each.

  [1]  1
  [2]  2
  [3]  3

2)  "the rest of the stack" (1 2 3) each.

  [1]  "the rest of the stack" 1
  [2]  "the rest of the stack" 2
  [3]  "the rest of the stack" 3

intersect

This primitive finds the intersection of two streams, in terms of shared solutions. It expects two arguments at the top of the stack, which are interpreted as mappings. It pops the arguments from the stack, then for each mapping, applies the mapping to the rest of the stack. This produces two streams of solutions. The solutions which appear in both streams are produced as top-level solutions. This primitive uses the same strategy as distinct (see above) for memoizing solutions.

Example:

1)  1 2 both.

  [1]  2
  [2]  1

2)  2 3 both.

  [1]  3
  [2]  2

3)  (1 2 both.) (2 3 both.) intersect.

  [1]  2

limit

This primitive enforces a limit on the number of solutions produced. It can be used in order to save time and to avoid exponential branching and memory issues. It expects a single argument on the top of the stack: the number of solutions to allow. It pops that number from the stack, then allows the rest of the stack to be evaluated. If the number of solutions reaches the limit, a last solution is produced and the computational branch is terminated.

Examples:

1)  (1 2 3) each. 2 limit.

  [1]  1
  [2]  2

2)  <http://identi.ca/user/114> foaf:knows. foaf:name. distinct. 5 limit.

  [1]  "Jim Hughes"
  [2]  "Keith Alexander"
  [3]  "John Goodwin"
  [4]  "Ross Singer"
  [5]  "Jim Hughes"

order

This is a closed-world primitive which produces its solutions according to Ripple's total order. It takes any stack and applies Ripple's default lazy evaluator to that stack. After all solutions have been gathered, it sorts the solution set and produces it in order of lowest to highest.

Examples:

1)  <http://identi.ca/rss> rss:items. members. dup. dc11:date.

  [1]  <http://identi.ca/rss> "2011-05-20T09:30:03+00:00"
  [2]  <http://identi.ca/notice/73943871> "2011-05-20T09:29:05+00:00"
  [3]  <http://identi.ca/notice/73943704> "2011-05-20T09:27:26+00:00"
  [4]  <http://identi.ca/notice/73943707> "2011-05-20T09:27:27+00:00"
  [5]  <http://identi.ca/notice/73943897> "2011-05-20T09:29:18+00:00"
  [...]

2)  <http://identi.ca/rss> rss:items. members. dup. dc11:date. order.

  [1]  <http://identi.ca/notice/73943376> "2011-05-20T09:25:04+00:00"
  [2]  <http://identi.ca/notice/73943410> "2011-05-20T09:25:21+00:00"
  [3]  <http://identi.ca/notice/73943419> "2011-05-20T09:25:22+00:00"
  [4]  <http://identi.ca/notice/73943420> "2011-05-20T09:25:23+00:00"
  [5]  <http://identi.ca/notice/73943450> "2011-05-20T09:25:28+00:00"
  [...]

scrap

This is the simplest possible primitive: it requires no arguments and it produces no solutions, regardless of its input. It just makes the stack go away. Like control:require, it is useful for filters in which some solutions are accepted, while others are discarded.

Examples:

1)  @list no-odd: dup. 2 mod. 0 equal. id scrap branch.
2)  137 :no-odd.

3)  42 :no-odd.

  [1]  42

Ranking

In order to rank resources in a graph, Ripple uses non-monotonic operations for gathering resources together in weighted vectors. The weight of a resource represents its ranking vis-a-vis the universe of all resources. The primitives currently supported by Ripple are geared towards random walk algorithms in semantic networks. See also Gremlin for extensive examples of ranking traversals.

In Ripple, a ranking traversal spawns a new, closed-world evaluator which maintains a weighted vector of all resources. Initially, the weight of each resource in the vector is zero. The initial path of the evaluator is given an energy equal to one. As evaluation proceeds, the traversal may branch off into any number of paths, whose energy may be amplified or (more commonly) attenuated along the way. When a result (an object at the top of a stack) is finally produced at the end of the path, the energy of the path is added to the object's weight. The final state of the weighted vector is the ranking result of the traversal.

amp

This primitive amplifies or attenuates the energy of the current path in a ranking traversal. It expects a single argument at the top of the stack: a number indicating the degree of attenuation (for example, a typical value in a PageRank-like traversal is 0.85). It pops the number off of the stack and yields the rest of the stack, having first multiplied the energy of the current path by the given number.

See the extras:rank example below.

rank

This primitive performs a closed-world ranking traversal following a given program. It expects a single argument at the top of the stack: a number indicating the number of computational steps to use in the traversal. For high precision, use more steps. For speed, use less. It pops the number off of the stack, then treats the rest of the stack as a traversal program. After executing the traversal for the given number of steps, it produces one new stack for each non-zero entry in the resulting weighted vector. It pushes first the resource, then the weight of the resource for each entry in the resulting vector.

Example:

1) @list danny: <http://identi.ca/user/114>

2) :danny. (foaf:knows. 0.85 amp.)* 10 rank.

  [1]  <http://identi.ca/user/114> 10.3925E0
  [2]  <http://identi.ca/user/512> 6.5025E0
  [3]  <http://identi.ca/user/36165> 6.035E0
  [4]  <http://identi.ca/user/46430> 4.59E0
  [5]  <http://identi.ca/user/13549> 4.335E0
  [6]  <http://identi.ca/user/226> 3.8674999999999997E0
  [...]