Spaces

A space allows to store information using a simple yet general graph model.

To execute the examples of this manual, a recent JDK for J2SE and a recent release of the library »ram.jar« is required.

Spaces

A memory space is a memory-based implementation of a space. This will allow fast space operations, but the size of the space is limited by the heap memory size. (Another implementation of a space might be backed by a data base to store more information.)

The following program shows the creation of a memory space.

Main.java

public class Main
{

  public static void main( final java.lang.String[] args ) 
  {

    final de.dclj.ram.system.space.Space space = 
    new de.dclj.ram.system.space.MemorySpace(); }}

System.out

(no output)

String Points

A point can be given as a string. For example, a string point is given by the letter »A«.

A visual representation of a string point

*
|
|
V
A

The following example shows the creation of a string point within a space.

Main.java

public class Main
{

  public static void main( final java.lang.String[] args ) 
  {

    final de.dclj.ram.system.space.Space space = 
    new de.dclj.ram.system.space.MemorySpace();

    final de.dclj.ram.system.space.Point pointA = 
    space.point( "A" ); }}

System.out

(no output)

Uniqueness of String Point Location

A string point is a function of its string: If two strings are equal, their points will be equal.

But the value »space.point( "A" )« is not the actual point, but a handle to it. To compare the point referred to with another point, one uses the method name »is« as shown in the next example

Main.java

public class Main
{
  public static void main( final java.lang.String[] args ) 
  {

    final de.dclj.ram.system.space.Space space = 
    new de.dclj.ram.system.space.MemorySpace();

    java.lang.System.out.println( space.point( "A" ).is( space.point( "A" ))); 
    java.lang.System.out.println( space.point( "A" ).is( space.point( "B" ))); }}

System.out

true
false

This feature can be used to create a point in the space using a string as an index or to locate a string point that has been created before by its string.

Pair Points

Another kind of point is a pair point. It is a function of two other points.

The following program creates and prints a pair point.

Main.java

public class Main
{

  public static void main( final java.lang.String[] args ) 
  {

    final de.dclj.ram.system.space.Space space = 
    new de.dclj.ram.system.space.MemorySpace();

    java.lang.System.out.println
    ( space.point( space.point( "A" ), space.point( "B" ))); }}

System.out

( A; B )

A pair point can be thought of as an edge of a graph. A visual representation of a pair point

   *
   |
   |
   V
A ---> B

Pair points also can be compared with »is«. Two pair points are the same, if they have the same components.

Main.java

public class Main
{

  public static void main( final java.lang.String[] args ) 
  {

    final de.dclj.ram.system.space.Space space = 
    new de.dclj.ram.system.space.MemorySpace();

    java.lang.System.out.println
    ( space.point( space.point( "A" ), space.point( "B" )).is
      ( space.point( space.point( "A" ), space.point( "B" ))));

    java.lang.System.out.println
    ( space.point( space.point( "A" ), space.point( "B" )).is
      ( space.point( space.point( "A" ), space.point( "C" ))));

    java.lang.System.out.println
    ( space.point( space.point( "A" ), space.point( "B" )).is
      ( space.point( "A" ))); }}

System.out

true
false
false

Edges as Points

In a space, edges are points, too. (A description of a graph with such a capability was not found in the literature, yet. Therefore, the name of such a graph is not known.)

A pair point can be interpreted as an edge  or an arrow, and an arrow to a string can be interpreted as a label. Thus, The graph system being described so far can be used to label both string points and arrows.

The following program prints an edge from the edge point »( A; B )« to the string point »C«.

Main.java

public class Main
{

  public static void main( final java.lang.String[] args ) 
  {

    final de.dclj.ram.system.space.Space space = 
    new de.dclj.ram.system.space.MemorySpace();

    java.lang.System.out.println
    (

      space.point
      ( space.point( space.point( "A" ), space.point( "B" )), 
        space.point( "C" ))); }}

System.out

( ( A; B ); C )

A visual representation of an edge starting at another edge

      *
      |
      |
      |
      |
      |
      |
A     |
|     v
|----------->C
|
V
B

This can also be thought of as a binary tree.

Another visualization of the same structure

        *
       / \
      /   \
     /     \
    /\      C
   /  \
  /    \
 A      B

The whole graph the can be thought of as a forest of binary trees (if a single string point is deemed a binary tree of depth 0).

Reading From The Space

Information can be read from a space by enumerating the out-edge set of a point, which here also is called a “rac” of the point. (The out-edge set is the set of all out-edges of a point. An out-edge of a point, is an edge of the graph with the point as its first component.)

The »rac« of a point is the set of all pairs, where this point is the first component. It is the set of all outgoing arrows of this point, the out-edge set.

The method »rac« of a point will enumerate its out-edge set. In the following program, it calls the method »of« for all the out-edges of the string point »"A"« (there is only one such edge).

»de.dclj.ram.Operation<T>« is an interface with a single signature »boolean of(T)«. The implementation of the signature can be anything, a false result can be used to request termination of a outer loop.

The following program creates and prints a pair point. But it does not print the pair using the creating expression as before, instead it finds the pair starting at its left point and using »rac« to find the pair from this left point.

Main.java

public class Main
{

  public static void main( final java.lang.String[] args )
  {

    final de.dclj.ram.system.space.Space space =
    new de.dclj.ram.system.space.MemorySpace();

    space.point( space.point( "A" ), space.point( "B" ));

    space.point( "A" ).rac
    ( new de.dclj.ram.Operation<de.dclj.ram.system.space.Pair>()
      { public boolean of( final de.dclj.ram.system.space.Pair edge )
        { java.lang.System.out.println( edge ); return true; }} ); }}

System.out

( A; B )

The rac of a point

 the rac of A
      |
      |
      v
A----------->B
     edge

Simple Predicates

A point »letter« can be interpreted to represent the predicate “is a letter”.

A visual representation of an arrow point

letter -------> A

All points marked as letters are the cdrs of the rac of »letter«. The next program shows how to enumerate and print all of them.

Two Letters in a graph with an explicit notation of their letter property

        .-----> A
letter-:
        '-----> B

Main.java

public class Main
{

  public static void main( final java.lang.String[] args )
  {

    final de.dclj.ram.system.space.Space space =
    new de.dclj.ram.system.space.MemorySpace();

    space.point( space.point( "letter" ), space.point( "A" ));
    space.point( space.point( "letter" ), space.point( "B" ));

    space.point( "letter" ).rac
    ( new de.dclj.ram.Operation<de.dclj.ram.system.space.Pair>()
      { public boolean of( final de.dclj.ram.system.space.Pair edge )
        { java.lang.System.out.println( edge.cdr() ); return true; }} ); }}

System.out

A
B

Relations

Because pairs are also points, a pair can become part of another pair. This allows one to model relations, like »is_orbited_by« in the example program below.

Orbits (with triplets)

                  orbits
the_earth  -------------------> the_sun

                  orbits
the_venus  -------------------> the_sun

                  orbits
the_moon   -------------------> the_earth

The triplets from the assertions above are represented by pairs as shown below.

Orbits (with pairs)

              
( orbits --> the_sun   )--> the_earth

( orbits --> the_sun   )--> the_venus

( orbits --> the_earth )--> the_moon

To query all what is known about the earth, one can start at the earth and recursively follow all racs and rdcs (avoiding loops). Whenever one encounters an out-neighbor of »true«, on can print is as an assertion about the earth.

Pseudocode

see( x, path )
{ if( true( x ))accept( x, path ); }

track( x, seen, path, direction )
{ path.add( direction );
  if( !seen( y ))follow( y, seen, path ); }

follow( x, seen, path )
{ see( x, path ); seen.add( x );
  for( y in rac( x ))track( y, seen, path, "rac" );
  for( y in rdc( x ))track( y, seen, path, "rdc" ); }

Main.java

public class Main 
implements de.dclj.ram.event.Accept<de.dclj.ram.system.space.Point>
{

  public void run( final java.lang.String[] args ) 
  { 

    x( x( x( "orbits" ), x( "earth" )), x( "sun"   ));
    x( x( x( "orbits" ), x( "venus" )), x( "sun"   ));
    x( x( x( "orbits" ), x( "moon"  )), x( "earth" ));

    space.point( "earth" ).rdc
    ( new de.dclj.ram.event.Accept<de.dclj.ram.system.space.Point>()
      { public boolean accept
        ( de.dclj.ram.system.space.Point point )
        { print( point );
          return true; }}); }

  de.dclj.ram.system.space.Space space = 
  new de.dclj.ram.system.space.MemorySpace();

  public de.dclj.ram.system.space.Point x
  ( final java.lang.String string )
  { return this.space.point( string ); }

  public de.dclj.ram.system.space.Point x
  ( final de.dclj.ram.system.space.Point car,
    final de.dclj.ram.system.space.Point cdr )
  { return this.space.point( car, cdr ); }

  int count = 0;
  int nest;

  public boolean accept
  ( final de.dclj.ram.system.space.Point point )
  { ++count; ++nest;
    if( nest < 2 )
    { this.print( point ); }
    --nest;
    return true; }

  void print
  ( final de.dclj.ram.system.space.Point point )
  { int old = count; count = 0;
    point.rac( this );
    point.rdc( this );
    if( count == 0 )
    java.lang.System.out.println( point ); 
    count = old; }

  public static void main( final java.lang.String[] args ) 
  { new Main().run( args ); }}

System.out

( ( orbits; earth ); sun )
( ( orbits; moon ); earth )

A problem with this approach is to tell simple pairs from assertions. The next section will introduce a special assertion marker to make this become easier.

Simple True Assertions

To make the recognition of assertions more unique, now, we want to implement a special assertion mark »true«: Each true assertion will be a direct successor of the node »true«.

true ------->(( R -> O )-> S )

We will restrict the first implementation to assertions of the form „relation, object, subject“. The first part »( R -> O )« of an assertion here will be called the “predicate” P of an assertion, so that an assertion »(( R -> O )-> S )« also can be written as »( P -> S )«.

Now we want to develop a program that shows those assertions about any object, where the object is a direct successor of the predicate. We will intentionally miss the other relations about any object (but the reader can add code for them as an exercise).

As a first step, let's enumerate all string entries o and then all their incoming arrows ( r -> o ), in order to find all predicates p.

Main.java

public class Main 
{

  public void run( final java.lang.String[] args ) 
  { x( x( "true" ), x( x( x( "orbits" ), x( "earth" )), x( "sun"   )));
    x( x( "true" ), x( x( x( "orbits" ), x( "venus" )), x( "sun"   )));
    x( x( "true" ), x( x( x( "orbits" ), x( "moon"  )), x( "earth" )));
    space.forStringEntries
    ( new de.dclj.ram.Operation<de.dclj.ram.system.space.Point>()
      { public boolean of( final de.dclj.ram.system.space.Point o )
        { java.lang.System.out.println( o ); 
          o.rdc
          ( new de.dclj.ram.Operation<de.dclj.ram.system.space.Point>()
            { public boolean of( final de.dclj.ram.system.space.Point p )
              { java.lang.System.out.println( "  " + p ); 
                return true; }} );
          return true; }} ); }

  de.dclj.ram.system.space.Space space = 
  new de.dclj.ram.system.space.MemorySpace();

  public de.dclj.ram.system.space.Point x
  ( final java.lang.String string )
  { return this.space.point( string ); }

  public de.dclj.ram.system.space.Point x
  ( final de.dclj.ram.system.space.Point car,
    final de.dclj.ram.system.space.Point cdr )
  { return this.space.point( car, cdr ); }

  public static void main( final java.lang.String[] args ) 
  { new Main().run( args ); }}

System.out

moon
  ( orbits; moon )

orbits

true

earth
  ( orbits; earth )
  ( ( orbits; moon ); earth )

sun
  ( ( orbits; earth ); sun )
  ( ( orbits; venus ); sun )

venus
  ( orbits; venus )

This first output shows the rdc-list of every string point of the graph, that is, it shows the incoming edges for every string point. Some of these edges are assertions and some are not (they are predicates). For example, »( orbits; moon )« is a predicate, while »( ( orbits; moon ); earth )« is an assertion.

(This section is yet incomplete. It will be completed later to show how to find all assertions about any topic. Following sections will show how to represent complex objects [like „the relation between coffee and sleep“], and how to represent sources of utterances, so that the net can contain information like „Peter said the sun orbits the earth.“ and „Lisa said that the earth orbits the sun.“. – The features needed to do this already are implemented in the library, but this tutorial is not yet written to show how to do this. But possibly, until the tutorial is more complete, the reader can find out how to do this.)