The World as Information: Part 3

Welcome to part 3 of this series on modeling the World in terms of information structure. The theory in part 2 gives a basis for representing information structure but there isn’t a way to define structures and combine them into larger structures. Nor are there any practical modifications. For example, in the real world we need the concept of a string. In this part we develop a notation, “Proteus”, for representing any possible infon system. As a bonus, our notation will be computer readable and even streamable so that computers can interactively apply the models in useful ways.

An important fact to consider when reading the following is that infons are immutable. They do not change. The “next state” of a system is a new piece of information. Also, comments are like // to end of line OR /* … */

There are three different types of low level infon. The idea is that these three are enough to allow the development of any other type. They are numeric infons, lists and a special list where every item has 256 states, that is, a string of bytes. If you program this is obviously familiar.

Before we look at these, there is an important point; it is important to be able to assert that there is a piece of information that we do not know. For numbers we use an underscore “_” to represent “unknown”. Note that “_” is not NULL. NULL is sometimes used in programming to mean the value is not available. Here it means that there is a value, but it is not given here for whatever reason.

Bare infons are when a value is given but not a size. Here are examples of bare numeric infons and string infons that illustrate the possibilities:

• 123 // a bare number infon

• 0xffff // a number in hex

• 0B00011101 // a number in binary

• _ // an unknown number

• “A bare string infon”

• ‘Another \‘string\’ with escapes\n’

• $ // an unknown string

NOTES:

• Numbers and strings can be arbitrarily long.

• Strings can contain Unicode but they are measured in bytes.

• There are also here-doc strings and string syntax for streaming large binary strings.

• Later, after we can map states to them, we will add rational forms and decimals.

There is a special syntax for an infon where even the type is not known. It is mostly used internally when processing infons but it can also be used explicitly. It’s very simple. An infon of unknown type and unknown value is written

?

Suppose we want to declare an infon of 12 states that is in state 3. We use the * and + symbols like this:

*12 +3   // A 12 state infon in state 3

Here is a 12 state infon in an unknown state:

*12 +_

And here is an infon in state 3 but the size is unknown:

*_ +3

We can make a list by using curly braces like so:

{ *4+2 *3+1 }

That list represents a compound infon of 12 states. But it is divided into a 4 state component and a three state component. To find the state of the whole, we do the arithmetic from left to right. We start with zero:

0 * 4 + 2 * 3 + 1

Thus the whole undivided system is:

*12 +7

Lists can be arbitrarily long. And the list items can be any infon. Note that the state arithmetic only works with numeric infons.

{ *255+22 “abc”  {2 4 3} }

Here is an unknown list:

{…}

And a partially unknown list:

{ 1 2 … 6 7 … 9 }

An unknown list with 200 elements:

*200 + {…}

While the state arithmetic does not work with strings and lists, the size notation is still useful. Thus:

*4 + “hello”  = “hell”

Note that without the *4, the size of “hello” would default to 5. This applies to any list, not just strings.

We can assert that two infons are identical, that is, they contain the same information, with “=”:

*12+_ = *12+5

That is a trivial example but, just as with the equal sign in regular math, identities are the primary way of making inferences with information models like Proteus models.

Here is a slightly better example:

{ 1 2 … 6 7} = {_ _ 3 4 5 _ _}

In this case we can use identity to infer the entire list.

To be precise, identity means that the size of the identical infons is the same, as well as the contents and the ordering of the contents.

Identity also usually implies that the types are the same. If we need to assert that the underlying information is the same but that the interpretation may be different we can use two equal signs “==”.

*256 +65 == “A”

Because ASCII “A” is 65.

Lastly, if we add a : to the end of the equal symbol, it means that the length of the left side may be shorter than that’s of the right side. This is useful for parsing strings or lists.

“hell” =: “hello”

If we want to concatenate the items in a list we can enclose it in parentheses. In the case of numeric infons in a list this has the effect of calculating the size and state number of the whole system. For example:

(*4+2 *3+1) = *12+7

With strings and lists, the same operation is concatenation.

NOTES:

• If there are different types of item in the ( ), the type of the first item is the type of the result.

• If there is only 1 item in the ( ), it is just itself, but this means that parentheses can also be used in the traditional way to specify the order of operations.

There is another list-item operation that will be useful. If we precede a list inside another list with “&”, it mean that the list is not a sub-list but a list of elements on the same level. An example will illustrate this.

Notice that the list

{  1 2 {5 4 3 } }

has 3 items in it. The list at the end counts as a single item. But if we add a & before it, the 5, 4 and 3 become members of the parent list. Thus the following list has 7 items:

{ 1 2 &{ 5 4 3 } } = { 1 2 5 4 3 }

This will be very useful later when we want to describe things that happen for a while then stop and something else happens.

What if we want to say something about all the items in a list. For example what if we want to say that all the elements in a list are 3 character strings. That is, each member of the list is like *3+$. (Recall that $ is an unknown string.)

We can put the template at the front of the list followed by a |. Here declares a list of 3 character strings:

{ *3+$ | … }

We can actually do a little parsing with this!

{ *3+$ | … } == “cathatbatdog”

This would result in the list:

{ “cat” “hat” “bat” “dog” }

Using what we have learned so far, how would we turn it back into the original string?

If we enclosed it in ( ) to concatenate it we would get the same list back because the list is a single item. However if we mark it with &, we get the desired effect. See if you can work through this:

( &{ *3+$ | … } == “cathatbatdog” )

A fully unknown numeric infon is represented by ‘_’. But often we know something about an infon. Using what we have so far we can express partial knowledge by using ‘_’ in an expression. Here are some examples:

A 10 state system in a state from 0 to 4:

*10 +(*5+_)

A 10 state system in a state from 2 to 6:

*10 +(*5+_+2)

A 10 state system in a state from 2 to 9:

*10 +(2+_)

A system with 5 or more states:

*(5+_)+_

A system with at least 2 but no more than 6 states:

*(5+_+2)+_

Much more complex partial knowledge is possible. As an exercise, how would we represent that the value is even?

We will go over this in great detail in future articles. For completeness, note that if a list has a ‘T’ immediately after the opening brace it is a temporal list and some more rules apply. A temporal list might look like this:

{T
  state1
  state2
  &{someAction_to_repeat | …}
  …
  futureState
  …
}

In this part we went over the basics of representing infons.

• There are three types: numeric, string and list

• They can be written in the normal ways

• The types are merely interpretations

• If not even the type is known, write ‘?’

• A string is a list like: { *256+_ | … }

• Identity can be asserted with = or ==. The latter means that the type may change. Adding a : to the = or == mean the size may be smaller.

• A list in ( ) has its elements concatenate into an infon with the type of the first item.

• ( ) can be used to specify the order of evaluation.

• Partial knowledge of a number can be expressed with ‘_’ in an expression.

• In a list, a sub-list marked by ‘&’ becomes a list of elements in the parent.

• A listSpec is an infon template that declares something about all the elements in a list. It is at the beginning of the list and is followed by a bar ‘|’.

• ListSpecs provide the declarative equivalent of repetitions or loops.

The next part will see defining the remaining parts of the Proteus Language. Examples will start to illustrate just how Proteus works.

We will start by defining one more list syntax that can be used in many ways including asserting conditional situations as well as acting as a function.

At that point we will have quite a bit: We’ll have a declarative syntax for the equivalent of: variables, assignment, repetitions, and conditionals or “ifs”. All we need is abstractions to be complete.

To round it off we will develop a simple but very flexible way of abstracting infons. Later, we will be able to abstract infons that represent the equivalent of nouns, verbs, adjectives, and so on. Indeed we can abstract over any other such construct if, for example, we find a language that doesn't work that way.

Lastly we will use what has been learned to describe a file structure that could be used both to parse and to construct a file format or streaming protocol.