This Note presents a revision of the language defined in Calideas – a programming language inspired by A Calculus of Ideas … and a genus of insects! … thus evolving from species 0.1 to 0.1.1.
Genus Calidea (iNaturalist.org)
“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)
The genus Calidea is a type of bug. Here’s some of what Google Images returns for “genus Calidea”:
This Note describes the elements of an experimental programming language: Calideas. The name – Cal+ideas – is derived from the title of
by Ulf Grenander
Publisher: World Scientific Publishing Company (2012)
The terminology of that book – hereinafter abbreviated as CoI – generators, bonds, configurations, … – comes originally from the author’s works in pattern theory, cf.
by Ulf Grenander
Publisher: Oxford University Press, USA (1994)
(hereinafter GPT), and
by Ulf Grenander
While the programming language Calideas (species 0.1.1) borrows ideas from CoI and GPT, what is defined here does not depend directly on them, and is meant to be understandable by a programmer with no previous reading of them. But an interested reader reader might want to start with CoI. (The format I have is the Nook Book.) Evolving species (versions as it’s typically called for other languages) of Calideas could incorporate more ideas from CoI and GTP.
The basic elements of Calideas are generators. They have diagrammatic (picture) and programmatic (code) representations.
Here is a diagrammatic example (shown in two ways):
Fig_1 : (HTML table)
|[ x ]||[ y ]|
|[ z ]||→3||genX||1→||[ u ]|
|[ v ]|
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 generator 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 generator). The generator’s “micro”code is intended to be a small bit of :native” code. 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:
Parametric generators have, in addition to arity arguments, a list of parameters. More details below.
type_name(#in_bonds,#out_bonds, param1, param2, ...)
The Calideas programming language (referred to as Calideas) has two forms of expression:
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.
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 nonempty, it empties its in bonds and computes the next bond values for its out bonds. It suspends until all out bonds have been emptied (by other generators), and then places the newly computed bond values on the out bonds. (It can’t overwrite out bond values.)
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.
Restated: A generator removes items (terms) from its input shelves as they appear. When all of its inputs have been collected, it selects the rule to apply and computes its output items (terms). But it suspends in placing them on its output shelves (they are buffered) until all of its output shelves have been cleared. Each shelf has at most one in-arrow and at most one out-arrow.
Think of Calideas “bugs” – terms – running around from nook to nook, with one bug at most in each nook.
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, … → loc_1 = f_1(…), … | 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, 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 generator 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.
X → Y=X+1 | Y
X → Y=X+Z | Y
The generator 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 generator version of the first.
X → printchar(X) |
→ X=readchar() | X
X → X,X
X → X
store(X), _ → X, X
recall, X → X, X
Consider the diagram (configuration):
[ store(X) | recall ] ↓1 [ 0 ] →2 mem →1 [ _ ] ↑1 ↓2 eq ←1 [ _ ]
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.
The above is an example of a parametric generator: variable arguments (parameters) after the two arity (#in, #out) numbers. When a generator is created, a term can be passed in. For example, a generator const(0,1,100) represents the constant 100.
Calideas interpreter commands
The Calideas interpreter (Calip) reads commands entered by a user to define generators and build configurations.
defgen gen_type(#in,#out,param_1, ...)
The user enters one or more rules for this gen_type.
Used to build a configuration (program) using gen, bond, clone commands.
A clone is a block of code within the config being defined that is a copy of another config.
Adds a generator to the current configuration.
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 generator. (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 generator given, the bond value is initialized but no bond with another generator takes place.
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).
inspect inx1 idx2
Ends a config or block.
Runs a configuration.
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.
Calideas 0.1.1 interpreter
X → X<•.•>
bond 1 in:1 2 out:1 'H'<•.•>
bond 2 in:1 4 out:1 'e'<•.•>
bond 4 in:1 6 out:1 'l'<•.•>
bond 6] in:1 8 out:1 'l'<•.•>
bond 8 in:1 10 out:1 'o'<•.•>
bond 10 in:1 12 out:1 ' '<•.•>
bond 12 in:1 14 out:1 'w'<•.•>
bond 14 in:1 16 out:1 'o'<•.•>
bond 16 in:1 18 u0t:1 'r'<•.•>
bond 18 in:1 20 out:1 'l'<•.•>
bond 20 in:1 22 out:1 'd'<•.•>
bond 22 in:1 '!'<•.•>
‘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 generator 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.
block N 2 12<•.•>
bond 1 in:1 2 out:1 'H'<•.•>
bond 2 in:1 3 out:1 'e'<•.•>
bond 3 in:1 4] out:1 'l'<•.•>
bond 4 in:1 5 out:1 'l'<•.•>
bond 5 in:1 6 out:1 'o'<•.•>
bond 6 in:1 7] out:1 ' '<•.•>
bond 7 in:1 8 out:1 'w'<•.•>
bond 8 in:1 9 out:1 'o'<•.•>
bond 9 in:1 10 u0t:1 'r'<•.•>
bond 10 in:1 11 out:1 'l'<•.•>
bond 11 in:1 12 out:1 'd'<•.•>
bond 12 in:1 '!'<•.•>
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 cell
set(X),_ → X,X
get,X → X,X
bond store_idx in:2 store_idx out:1 0
store_idx references the same store generator. (Example of a generator bonded to itself.)
eq ← [ _ ] ↓ [ 1 ] ↑ ↘ sum → [ _ ] → print ↗ [ 1 ] ↓ ↑ eq ← [ _ ]
X,Y → X+Y,X+Y,Y
// alt: X,Y → Z=X+Y | Z,Z,Y
Enter lines into interpreter that matches this diagram.
Configuration definitions extended by a list of of parameters. These will appear in the definition of the configuration to be set with
config foo(A, B, ...)
clone foo(term1, term2, ...)
run foo(term1, term2, ...)
Given a set of terms, a parametric configuration class is formed.
Next generation: Calideas interpreter commands represented as terms (metaprogramming).
Appendix: Calideas vocabulary
- Calip: Calideas interpreter
- term: a lexical unit of Calideas
- grule: a generator rule
- stote: a stream of terms
- generator: a mapping of multiple stotes to multiple stotes via a set of term-matching grules
- configuration: an assembly of generators via topological bonding rules
- image: a snapshot of outputs (bond values) produced by a configuration run
- cine: a stream of images
- pattern: images from the same parametric configuration class
- genre: cines from the same parametric configuration class