The Calideas Framework (Introduction)

 
         iNaturalist.org · Genus Calidea
         Genus Calidea (iNaturalist.org)
 
 

Calideas (or the Calideas Framework) is a language-general, multigrain-parallel programming framework. What was originally defined as the Calideas programming language [1][2]) is decoupled into:

  1. Calideas – the programing framework
  2. GRuELGenerator Rule Expression Language
  3. CalipCalideas interpreter (or Calideas processor)

The Calideas Framework (Calideas for short) is described in this Note. (Calidas for particular languages, e.g. Python, as well as GRuEL and Calip – used in combination with Calideas – to be further described in future Notes.) By making Calideas a framework, “breeds” of Calideas can be made available for various “host” languages (functional, procedural). Examples of Calideas programs can be found in the previous Notes.

(As referenced in the previous Notes, the name “Calideas” comes from A Calculus of Ideas, a book by by Ulf Grenander, and the biological genus Calidea, a member of Jewel Bugs. Conceptually, Calideas is inspired by the pattern-theoretic entities defined in A Calculus of Ideas, and, hopefully, can be ultimately useful as a programmatical approach paralleling the mathematical theory.)

 

Calideas terminology

  • germ – A genoid term. Germs are the lexical objects that are passed as bond values. For example, in GRuEL they are Prolog-like terms, e.g,,

       sentence(np(john),vp(verb(likes),np(hamburgers))))

    but could be Lisp-like s-expressions (in Clojure or Racket), JSON objects, etc. Simple, as opposed to complex, germs are numbers, characters, etc.

  • genoid – A function (written in the “host” language, or in GRuEL) that maps a tuple of germs (the input) to a tuple of germs (the output). genoids can be parametric: genoids can have a set of parameters (germs) that fix the genoid to be a specific function. The tuples of inputs and outputs of genoids is represented by a list of buffers, denoted by left and right brackets [ ] , enclosing a single germ. An array of buffers (a sequence of bracket pairs), can be abbreviated by comma-separated data (e.g., [x,y,z] for [x][y][z]). The empty buffer is denoted with an underscore: [ _ ]. Examples of non-empty (or filled) buffers:
    [ likes(jim,movies) ], [ 6.7 ], [ 'Hello' ], ... .

     
    gen(g, param(1,g) ..., param(#params(g)):
        g - > [in_germ(1,g),...,in_germ(#in(g))]
               -> [out_germ(1,g),...,out_germ(#out(g))]
     

    An example of a parametric genoid:

    gen(g,A,B,C): g -> [ X ] -> [ A*X^2 + B*X + C ]
     
  •  

    Note: The use of genoid in the context of Calideas differs from the use of generator in pattern theory: A Calideas genoid maps multiple streams to multiple streams (of bond values, or germs), but mainly so as not be confused with the use of generator in computer programming.

  • bond – A site that stores a germ, plus (unique) input and output genoid index, argument index pairs.

    bond(b):
      b ->
       [germ(b)] in(ingen(b),inidx(b)) out(outgen(b),outidx(b))
     

    Example:

    [ foo(bar) ] in(7, 2) out(3,1) = (genoid 7 input 2) bonded to (genoid 3 output 1)

  •  

    Input and output buffers in genoid definitions are differentiated from bond sites, though both use the bracket notation to enclose their value. A bond site can be seen as a temporary holding cell for the transfer of germs from one genoid to another.

     
  • configuration – A collection of genoids g = 1,…,G and bonds b = 1,…,B.
     

    parametric configuration – Parameters of a configuration are the union of the parameters of the genoids in the configuration.

  • Each bond has at most one in genoid and at most one out genoid.

 

Calidea runtime

The visualization of Calideas is that bond sites are used to transfer germs (the bond values) from the genoid output buffers to (other) genoid input buffers. A configuration thus represents a program, where streams of germs are configured to pass between genoids.

When all input buffers are filled and all output buffers are empty, the genoid executes, placing outputs in output buffers and emptying input buffers.

When a genoid output buffer is filled and its bond site is empty, the germ is transferred. (The output buffer is then empty and the bond site is filled.)

When a genoid input buffer is empty and a bond site is filled, the germ is transferred. (The input buffer is then filled and the bond site is filled.)

Alternatively (genoids and bonds as asynchronous processes):

  • For each genoid: When all input buffers are filled and all output buffers are empty, the genoid computes new output germs, fills the output buffers, and empties the input buffers.
  • For each bond: When the bond site is empty and its associated genoid output buffer is filled: (1) If the and input buffer is empty, it transfers the germ from the output buffer to the input buffer, emptying the output buffer; (2) If the input buffer is filled, it transfers the germ to its own site, emptying the output buffer. When the bond site is filled and its associated input buffer is empty, it transfers its germ to the input buffer, emptying itself.
 

Calideas can also be used potentially as a programming framework for chemical and biological computing — where germs are no longer symbolic-numerical entities of conventional computing, but synthetic biochemical/molecular entities of unconventional computing.

 

Higher-order definitions

  • image – A snapshot at a particular time step of a configuration of bond sites (containing germs, or bond values).
  • pattern – A class of images generated by a (similarity) group of parameter values.
  • cine – A stream of images.
  • genre – A class of cines generated by a (similarity) group of parameter values.
 
 

Calideas (high-level) description

A configuration is an arrangement* of sites that transform (deterministically or stochastically) and transport streams of germs by means of parametric genoids and bonds.

A snapshot of site values (germs) at a given time step is an image, and for multiple time steps (streams of germs) is a cine.

For a symmetry group of genoid parameters: the resulting class of images (taken at the same time step) is a pattern, and for cines (multiple time steps) is a genre.

 

* A future Calideas Framework to incorporate dynamic bonding and learning (rule-modifiable genoids), and probabilistic configuration spaces (genoids with stochastic rules).

 
 

Calideas diagrams

The Calideas Framework has two forms of expression:

  • diagrammatic
  • programmatic

The diagrammatic form consists of names (in bold type), brackets ([ and ]), and arrows. The bold-type names in a diagram correspond to a genoid type, and each one with the same name corresponding to a particular genoid. Each genoid type has a fixed number of arrows pointing in, and a fixed number of arrows pointing out. This pair (#in,#out) is called the arity of the genoid type. Brackets correspond to genoid bonds, and what can appear inside the brackets correspond to bond values. Arrows can appear only between a genoid and a bond, and a bond can have at most only one arrow in and one arrow out. Bond values in Calideas (0.1.1) are terms, which are defined below. There is one special notation: The underscore inside brackets [ _ ] indicates an empty bond (i.e., no bond value).

The entire diagram (of genoids and bonds) is a configuration. A configuration thus corresponds to a program. Calideas itself can then be seen as a programming language that makes configurations, i.e. programs.

Here is a diagrammatic example (shown in two ways):


Fig_1
 

Fig_1 : (HTML table)

[ x ] [ y ]
1 2
[ z ] 3 genX 1 [ u ]
2
[ v ]
 
 
 

In the diagram, the type of the genoid is shown in bold (genX in this example). Around the genoid type are numbered arrows (inputting into and outputting from the type). On the other ends of these arrows are brackets enclosing a bond value. (More on what “bond” means in a bit.) The program for this diagram defined using a defgen, which defines the functional relationship between the input bond values and output bond values. A genoid rule has two parts: the input variables and output variables (separated by a right arrow) and a bit of code (the “micro”code for the genoid). The genoid’s “micro”code is intended to be a small bit of :native” code. The arity of a genoid is a pair (#in,#out) of number of input and output bonds. A genoid type name may be associated with different arities, so the entire type name plus arity is the signature of the genoid:

     type_name(#in_bonds,#out_bonds)

 
 

Calideas for a host language

Calideas for a particular host language — Python — will be defined in a following Note. The Framework’s implementation for other languages should follow.

The interface between Calideas and Python consists of the following capabilities:

  1. defining genoids as functions that input a list (representing buffers) of germs (Python objects) and outputs a list of germs
  2. defining configurations and bonds according to the functionality defined by config and bond in Calip (described below)
  3. implementing the runtime behavior of Calip
 
 

GRuEL

Germs (bond value terms) can be

  • numbers: 666, 3.1415, …
  • literals (one or more characters between single quotes): ‘Hello’, ‘world’, …
  • atomic terms, or atoms (words beginning with a lower-case letter): fooBar, goo89, …
  • compound terms (built from atoms): happy(‘John’), married(‘John’, ‘Jim’), …

The program for a genoid consists of a list of rules of the form

      in_1, in_2, … loc_1 = f_1(…), … | out_1, out_2, …

where the number of inputs and outputs matches the arity of the genoid type. To the left of → are the input arguments, and to the right are the output arguments, and possible local variable assignments before the “guard” |. The f_s are builtin functions (such as basic arithmetic, readchar, writechar). Each input argument is a Calideas term (defined above) with the following extension:

  • variables (words beginning with a capital-case letter): X, Y, Stream, …

One restriction: A variable cannot be repeated in the input arguments.

Each output argument is

  • an extended term, but any variables in it appear in the input arguments
  • can contain simple arithmetic expressions (to be evaluated in place)

The genoid operates by finding a the first rule that matches (assigning variables in input arguments to terms in the input bonds).

The above describes a deterministic rule selection. Future considerations: nondeterministic, probabilistic, and superpositional (quantum mechanical) rule selection.

Examples:

 


incr(1,1):
      X → Y=X+1 | Y

 


incr(1,1,Z):
      X → Y=X+Z | Y

The genoid type incr has arity (1,1) and takes an input (expected to be a number) and outputs a number (by adding 1). This is an example of a rule with temporary variable assignment and a builtin function call. The second is the parametric genoid version of the first.

 


print(1,0):
      X → printchar(X) |

 


read(0,1):
      → X=readchar() | X

 


dup(1,2):
      X → X,X

 


q(1,1):
      X → X

 


mem(2,2):
      store(X), _ → X, X
      recall, X → X, X

 

Consider the diagram (configuration):

              [ store(X) | recall ] 
                         ↓1      
               [ 0 ] →2 mem1  [ _ ] 
                 ↑12
                 eq1 [ _ ]

The mem genoid can input two bond-value forms: a store(X) and a recall. It can store a value X and then recall it.

 


const(0,1,X):
      → X

The above is an example of a parametric genoid: variable arguments (parameters) after the two arity (#in, #out) numbers. When a genoid is created, a term can be passed in. For example, a genoid const(0,1,100) represents the constant 100.

 
 
 
 

Calip

The Calideas interpreter (Calip) reads commands entered by a user to define genoids and build configurations.

  1. defgen gen_type(#in,#out,param_1, ...)

    The user enters one or more rules for this gen_type.

  2. config config_id

    Used to build a configuration (program) using gen, bond, clone commands.

  3. clone config_id

    A clone is a block of code within the config being defined that is a copy of another config.

  4. gen gen_type(#in,#out[,params])

    Adds a genoid to the current configuration.

  5. bond idx[.idx]* in:bond_idx idx[.idx]* out:bond_idx init_val

    Bonds two generations (indexed within the config), using the keywords :in and :out to select bond direction of each genoid. (In the case that there is a reference to a clone, the index following the period ‘.’ indexes into the clone block. [.idx]* indicates a sequence of zero or more indexes, with more indicating embedded configurations (clones) within ‘this’ one.) This is followed by an initial bond value (optional). If there is only one genoid given, the bond value is initialized but no bond with another genoid takes place.

  6. block var inx1 idx2

    A block of code within the config is made, where var steps by 1 from <idx1 and inx2, and the lines in the block are repeated (with var as a parameter).

  7. inspect inx1 idx2

    forthcoming

  8. end

    Ends a config or block.

  9. run config_id

    Runs a configuration.

  10. reset config_id

    Resets a configuration to its initial state.

 

 

When the Calideas interpreter (Calip) is run from the user’s OS, <•.•> is the interpreter prompt for the user to enter a Calideas command.

 
% Calip

Calideas 0.1.1 interpreter

<•.•> defgen eq(1,1)
eq.1
<•.•> X → X
eq.2
<•.•> end
<•.•> config helloWorld
helloWorld.1
<•.•> gen print(1,0)
helloWorld.2
<•.•> gen eq(1,1)
helloWorld.3
<•.•> bond 1 in:1 2 out:1 'H'
helloWorld.4
<•.•> gen eq(1,1)
helloWorld.5
<•.•> bond 2 in:1 4 out:1 'e'
helloWorld.6
<•.•> gen eq(1,1)
helloWorld.7
<•.•> bond 4 in:1 6 out:1 'l'
helloWorld.8
<•.•> gen eq(1,1)
helloWorld.9
<•.•> bond 6] in:1 8 out:1 'l'
helloWorld.10
<•.•> gen eq(1,1)
helloWorld.11]
<•.•> bond 8 in:1 10 out:1 'o'
helloWorld.12
<•.•> gen eq(1,1)
helloWorld.13
<•.•> bond 10 in:1 12 out:1 ' '
helloWorld.14
<•.•> gen eq(1,1)
helloWorld.15
<•.•> bond 12 in:1 14 out:1 'w'
helloWorld.16
<•.•> gen eq(1,1)
helloWorld.17
<•.•> bond 14 in:1 16 out:1 'o'
helloWorld.18
<•.•> gen eq(1,1)
helloWorld.19
<•.•> bond 16 in:1 18 u0t:1 'r'
helloWorld.20
<•.•> gen eq(1,1)
helloWorld.21
<•.•> bond 18 in:1 20 out:1 'l'
helloWorld.22
<•.•> gen eq(1,1)
helloWorld.23
<•.•> bond 20 in:1 22 out:1 'd'
helloWorld.24
<•.•> bond 22 in:1 '!'
helloWorld.25
<•.•> end
<•.•> run helloWorld

Hellow_config

 

‘Run’ning the diagram above: print takes an item (character) off its input shelf and prints it. That shelf is then empty, so that the eq genoid with output bonded to the print puts the item it took off its input shelf there. And so on, down the chain. This process continues untill all shelves are emptied.

 

Alternatively:

 

<•.•> config helloWorld2
helloWorld2.1
<•.•> gen print(1,0)
helloWorld2.2
<•.•> block N 2 12
                
<•.•> gen eq(1,1)
                
<•.•> end
helloWorld2.13
<•.•> bond 1 in:1 2 out:1 'H'
helloWorld2.14
<•.•> bond 2 in:1 3 out:1 'e'
helloWorld2.15
<•.•> bond 3 in:1 4] out:1 'l'
helloWorld2.16
<•.•> bond 4 in:1 5 out:1 'l'
helloWorld2.17
<•.•> bond 5 in:1 6 out:1 'o'
helloWorld2.18
<•.•> bond 6 in:1 7] out:1 ' '
helloWorld2.19
<•.•> bond 7 in:1 8 out:1 'w'
helloWorld2.20
<•.•> bond 8 in:1 9 out:1 'o'
helloWorld2.21
<•.•> bond 9 in:1 10 u0t:1 'r'
helloWorld2.22
<•.•> bond 10 in:1 11 out:1 'l'
helloWorld2.23
<•.•> bond 11 in:1 12 out:1 'd'
helloWorld2.24
<•.•> bond 12 in:1 '!'
helloWorld2.25
<•.•> end
<•.•> run helloWorld2

There is also a way to code HelloWorld using just the literal ‘Hello World!’ rather than the single characters! But thie above example is meant to show how the interpreter works.

 
 

Example: Storage site


defgen store(2,2)

      set(X),_ → X,X
      get,X → X,X

bond store_idx in:2 store_idx out:1 0

where store_idx references the same store genoid. (Example of a genoid bonded to itself.)

 
 

Example: Fibonacci

            eq   ←     [ _ ] 
             ↓
           [ 1 ]         ↑     
                    ↘   
                        sum  →  [ _ ] → print
                    ↗
              [ 1 ]       ↓
                ↑                
               eq   ←   [ _ ]

sum(2,3):
      X,Y → X+Y,X+Y,Y

// alt:       X,Y → Z=X+Y | Z,Z,Y

Enter lines into interpreter that matches this diagram.

 
 
 
 

Philip Thrift

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s