Calideas – a programming language inspired by A Calculus of Ideas … and a genus of insects!

 

This Note is under revision: See Calideas – species 0.1.1.

 
 

         iNaturalist.org · Genus Calidea

 

“Amongst the exotic species, those comprising the genus Calidea deserve mention on account of their brilliant metallic colors.”

An Introduction to the Modern Classification of Insects: Founded on the Natural Habits and Corresponding Organization of the Different Families
(in Two Volumes, Volume 2)
pg. 487

 

Introduction

This note (in draft publication form) describes the elements of an experimental programming language: Calideas. The name – “Cal”+”ideas” – is derived from the title of


A Calculus of Ideas: A Mathematical Study of Human Thought
by Ulf Grenander
Publisher: World Scientific Publishing Company (2012)
ISBN13: 9789814383189
goodreads.com/book/show/14737547-a-calculus-of-ideas
 

The genus Calidea is a type of bug. Here’s some of what Google Images returns for “genus Calidea”:

 
GenusCalidea
 
 

While the programming language Calideas borrows concepts from the book A Calculus of Ideas, what is defined here does not depend directly on it, and should be understandable apart from it. But the reader should check out the book – hereinafter referred to as CoI (the format I have is a Nook Book) – for inspiration.

What will follow in this preliminary note is a basis (initial generation) for the language:

      Calideas (species 0.1)

Evolving “species” (“version”s as it’s called in other languages) of Calideas will incorporate more ideas from the book by Grenander.

 

Generators

The fundamental elements of Calideas are generators. They have diagrammatic and programmatic (code) representations. Here is an example:


Fig_1

 

defgen genX {x,y,zu,v | "micro"code};

 

In the diagram, the type of the generator is shown in bold (genX in this example). Around the generator 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 defgen has two parts: the input variables and output variables (separated by a right arrow) and a bit of code (the “micro”code for the generator). The generator’s “micro”code is intended to be a small bit of :native” code. The examples below will indicate this further. There will be some “builtin” generators to begin, so one can write programs without defgens. The arity of a generator is a pair (#in,#out) of number of input and output bonds. A generator type name may be associated with different arities, so the entire type name plus arity is the signature of the generator:

     type_name(#in_bonds,#out_bonds)

Instances of generators are created as follows.

a = new genX(_,_,_→_,_);
b = new genX(_,10,_→ _,_);
 

The _ indicates an empty value. Otherwise, the bond value is initialized as indicated.

Alternately,

b = new genX(_,_,_→_,_);
b[in:2] = 10;
 

How generators execute

A generator (shown in bold) consumes bond values on its inputs and produces bond values on its outputs. (For the species 0.1 of Calideas, only integers and characters will be bond values.) The empty bond value is indicated by an underscore: _. Bond values appear within brackets: [ ]. Numbered arrows indicate input and output bonds. (A future species of Calideas will generalize this to labels.)

A generator is blocked until all inputs are nonempty and all outputs are empty. One can think of bond values (the integers or characters appearing within brackets) as being put on or taken off a shelf, with the underscore _ being the empty shelf. When the generator us unblocked, it takes the input values off the input shelves, computes the outputs, and puts them on the output shelves. What is produced is a stream of bond values making configurations dynamic entities. Below, the bonding operator :: is defined, which will “share” a shelf between the output of one generator with the output of another (or itself, for that matter). Key idea: Only one item can be on a shelf, hence the fine-graininess of Calideas.

(There’s something about shelves and bugs!)

 

Bonding (forming configurations)

Calideas interpreter commands

  1. config config_id
  2. clone config_id
  3. gen type(in1,in2,…→out1,out2)
  4. bond *[gen_idx][out:bond_idx] *[gen_idx][in:bond_idx]
  5. loop var inx1 idx2
  6. end
  7. run config_id
  8. reset config_id

* indicates ‘this’ config (and can be omitted), or it’s a sequence of one or more [clone_idx]s, indicating embedded configurations (clones) within ‘this’ one.

Next species of Calideas: bond values can be symbols (beyond integers and characters); metaprogramming (a config as a program is also a config of symbols).

Generators are combined into configurations with :: (to bond out bonds to in bonds). Equality is the bond relation. Here is an example (diagram and program):

Fig_3
 

c100 = new const(→100);
incrA = new incr(0→_,_);
lessA = new less(_,_→_,_);
printA = new print(_→);
copyA = new copy(_→_);
haltA = new halt (_→);

configA =

c100[out:1]::lessA[in:1],
copyA[out:1]::incrA[in:1],
incrA[out:2]::lessA[in:1],
lessA[out:1]::printA[in:1],
incrA[out:2]::copyA[in:1],
lessA[out:2]::haltA[in:1];
 

run(configA);

What :: returns is a configuration, and the “comma” (,) operator returns is the last configuration formed.

% calideas

Calideas 0.1 interpreter

<•.•> config print1to100
print1to100[1] <•.•> gen const(→100)
print1to100[2] <•.•> gen incr(0→_,_)
print1to100[3] <•.•> gen less(_,_→_,_)
print1to100[4] <•.•> gen print(_→);
print1to100[5] <•.•> gen copy(_→_)
print1to100[6] <•.•> gen halt (_→)
print1to100[7] <•.•> bond *[1][out:1] *[3][in:1]
print1to100[8] <•.•> bond *[5][out:1] *[2][in:1]
print1to100[9] <•.•> bond *[2][out:2] *[3][in:1]
print1to100[10] <•.•> bond *[3][out:1] *[4][in:1]
print1to100[11] <•.•> bond *[2][out:2] *[5][in:1]
print1to100[12] <•.•> bond *[3][out:2] *[6][in:1]
print1to100[13] <•.•> end
<•.•> run print1to100

* stands for (config) print1to100
<•.•> is the Calideas interpreter prompt

figure of next step of above diagram

Fig_1_1

 
 

A Calideas program consists of forming configurations and then running then (with run).

 

Arrays and loops

genX_array = new genX[10];

produces an array of 10 genXs.

loop i 1 10 { ... } defined.

 

Builtins definitions

const

The output of const never changes.

remove this image and deprecate const

Fig_2

incr
less
print
copy

Copies input to outputs. (Can have multiple outputs.)

sum
halt

Example: Hello world! (Click to enlarge diagram.)

Fig_4

 

helloWorld =

(new print(_→))[in:1]::(g = new copy(_→'H'))[out:1],
g[in:1]::(g1 = new copy(_→'e'))[out:1], g = g1,
g[in:1]::(g1 = new copy(_→'l'))[out:1], g = g1,
g[in:1]::(g1 = new copy(_→'l'))[out:1], g = g1,
g[in:1]::(g1 = new copy(_→'o'))[out:1], g = g1,
g[in:1]::(g1 = new copy(_→' '))[out:1], g = g1,
g[in:1]::(g1 = new copy(_→'W'))[out:1], g = g1,
g[in:1]::(g1 = new copy(_→'o'))[out:1], g = g1,
g[in:1]::(g1 = new copy(_→'r'))[out:1], g = g1,
g[in:1]::(g1 = new copy(_→'l'))[out:1], g = g1,
g[in:1]::(new copy('!'→'d'))[out:1];
 

run(helloWorld);

 

% calideas

Calideas 0.1 interpreter

<•.•> config helloWorld
helloWorld[1] <•.•> gen print(_→)
helloWorld[2] <•.•> gen copy(_→'H')
helloWorld[3] <•.•> gen copy(_→'e')
helloWorld[4] <•.•> gen copy(_→'l')
helloWorld[5] <•.•> gen copy(_→'l')
helloWorld[6] <•.•> gen copy(_→'l')
helloWorld[7] <•.•> gen copy(_→'o')
helloWorld[8] <•.•> gen copy(_→' ')
helloWorld[9] <•.•> gen copy(_→'W')
helloWorld[10] <•.•> gen copy(_→'o')
helloWorld[11] <•.•> gen copy(_→'r')
helloWorld[12] <•.•> gen copy(_→'l')
helloWorld[13] <•.•> gen copy('!'→'d')
helloWorld[14] <•.•> loop i 1 13
helloWorld[14]     <•.•> bond *[i][in:1] *[i+1][out:i+1]
helloWorld[15]     <•.•> end
helloWorld[16] <•.•> end
<•.•> run helloWorld

Example: Fibonacci

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

gendef sum { x, y → z1, z2 | z1 = x+y; z2 = y; }

 
 

Calideas – a programming language inspired by A Calculus of Ideas … and colorful bugs!

Calideas can be seen as a language for fine-grained parallelism where programs (configurations) are dynamically formed by operations of structuring (TBD) and bonding (::) of generators, and then run until a halt generator executes.

 

Note: A “snapshot” of a running configuration (program), where the bond values are set at a single time instance, would be a single configuration in the sense of CoI. The entire run of a Calideas configuration produces a trajectory in a CoI configuration space. The terminology (generators, bonds, configurations, …) in Grenander’s CoI comes originally from the author’s pattern theory, cf.


General Pattern Theory: A Mathematical Study Of Regular Structures
by Ulf Grenander
Publisher: Oxford University Press, USA (1994)
ISBN13: 9780198536710
goodreads.com/book/show/4818744-general-pattern-theory
 
 
 

to be continued … including higher-order structures (beyond integers and characters!), metaprogramming and reflection in future Calideas species …

 

This note defines a revision of the language Calideas – species 0.1.

Calideas – species 0.1.1

The Calideas programming language (referred to as Calideas) 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 generator type, and each one with the same name corresponding to a particular generator. Each generator 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 generator type. Brackets correspond to generator bonds, and what can appear inside the brackets correspond to bond values. Arrows can appear only between a generator 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 generators 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.

Calideas terms

Terms (bond values) 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 operational semantics of a Calideas diagram

At each time step, the diagram’s bonds have values (appearing within the brackets) that are empty ([ _ ]) or are a term. When a generator’s in bonds are all nonempty (with one exception: an input argument indicated by the empty symbol, _, as described below) and all of its out bonds are empty, the generator can execute: It removes the bond values from its in bonds (making them empty), computes the bond values for its out bonds (according to a set of rules, described below), and puts them there. In terms os implementation, the generator could peek at its inputs and begin computation even before its outputs are not cleared yet by other generators. But it can’t actually execute until its outputs have been emptied.

A metaphor for this semantics is that of looking at the brackets as a small shelf or nook. One generator puts something on a shelf. Another generator takes it off and uses it, possibly in combination with other items on other shelves, to produce items to put on its “output” shelves. But it can’t do that until all of its output shelves are empty, and all of its input shelves have an item ready.

Generator rules

This section begins the programmatic form for Calideas.

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

      in_1, in_2, ... → out_1, out_2, ...

where the number of inputs and outputs matches the arity of the generator type. To the left of → are the input arguments, and to the right are the output arguments. 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 generator operates by finding a the first rule that matches (assigning variables in input arguments to terms in the input bonds).

Examples:

 


incr(1,1):

      X → X+1

The generator type incr has arity (1,1) and takes an input (expected to be a number) and outputs a number (by adding 1).

 


dup(1,2):

      X → X,X

 


eq(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 generator can input two bond-value forms: a store(X) and a recall. It can store a value X and then recall it.

Calideas interpreter commands

  1. config config_id
  2. clone config_id
  3. gen type(in1,in2,…→out1,out2)
  4. bond *[gen_idx][out:bond_idx] *[gen_idx][in:bond_idx]
  5. loop var inx1 idx2
  6. end
  7. run config_id
  8. reset config_id

* indicates ‘this’ config (and can be omitted), or it’s a sequence of one or more [clone_idx]s, indicating embedded configurations (clones) within ‘this’ one.

% calideas

Calideas 0.1 interpreter

<•.•> config helloWorld
helloWorld[1] <•.•> gen print(_→)
helloWorld[2] <•.•> gen eq(_→'H')
helloWorld[3] <•.•> gen eq(_→'e')
helloWorld[4] <•.•> gen eq(_→'l')
helloWorld[5] <•.•> gen eq(_→'l')
helloWorld[6] <•.•> gen eq(_→'l')
helloWorld[7] <•.•> gen eq(_→'o')
helloWorld[8] <•.•> gen eq(_→' ')
helloWorld[9] <•.•> gen eq(_→'W')
helloWorld[10] <•.•> gen eq(_→'o')
helloWorld[11] <•.•> gen eq(_→'r')
helloWorld[12] <•.•> gen eq(_→'l')
helloWorld[13] <•.•> gen eq('!'→'d')
helloWorld[14] <•.•> loop i 1 13
helloWorld[14]     <•.•> bond *[i][in:1] *[i+1][out:i+1]
helloWorld[15]     <•.•> end
helloWorld[16] <•.•> end
<•.•> run helloWorld

Example: Fibonacci

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

gendef sum { x, y → z1, z2 | z1 = x+y; z2 = 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