Posset

Posset is BarryNL's attempt to create the perfect programming language and the name is an abbreviation from Possibility Set. The programming language itself and also this wiki page are still under construction.

Introduction

Its features:

• Pattern matching
• Implicit parallelism
• It only has types. Instances are nothing but very specific types.
• Partially constrained possets (borrowed from the elegant partially applied functions in Haskell)

It has similarities with:

• Constraint programming
• Relation algebra
• Prolog
• Query by Example

It is inspired by:

• The NIAM modellling method triggered the desire to bridge the gap between modelling and programming.

Possets

The language's basic building block is the possibility set (posset). A posset is an opaque set of tuples with a predefined and fixed cardinality where each tuple represents a possibility (possy). The language distinguishes between prime possets and derived possets. A prime posset is a posset whose cardinality is a prime number. Two prime possets can be combined using the product operation. The result is a derived posset in which every tuple from the first prime posset is concatenated with every tuple from the second prime posset. Its cardinality is the product of the cardinality of the two prime possets. Because of Integer factorization it is possible to create possets with any finite cardinality. Every prime posset with n possies is called 'n (pronounced as: prime n) and every derived posset is given a custom name. Derived possets can be constructed from any combination of prime or derived possets and this method is used to define the program.

Variables

Although variables are typically used in programming languages to name memory locations (on either the stack or the heap), the semantics of variables is different in the posset programming language. Variables are used to identify and relate portions of the nested structure of possets described in the previous section. When combining possets (either prime or derived) into a new derived posset, variables can placed on any posset at any level within the nested structure. Having these variables in place allows the developer to either manually filter the posset's possies (if it is a prime posset) or tie two or more possets together if they share the same variable. Filtering is used to restrict or prune the possies created by the product of possets and can be seen as the fundamental assumptions or definitions of the program. While tying two or more possets together restricts them to always iterate in sync. This means that in all possies of this newly derived posset, the tuple portion of the sub possets that share a variable will always be the same.

Runtime

Executing a posset program either consists of an iterator or a constrainer. The iterator generates the tuples of the top-level derived posset called main (isn't this contrary to possets being opaque?), while the constrainer keeps the main posset in memory as a constraining structure on external resources and ensure that these constraints defined by the program remain satisfied by propagating changes to these external resources throughout the in-memory structure.

Iterator

The current implementation of the posset programming language (see github repo below) creates an optimized (by collapsing variables) iterator over all possies (possibilities) of the main derived posset and while doing so might influence or be influenced by external resources (I/O not yet implemented).

Constrainer

The constrainer is not yet built, but would hold all the possies of the main posset in memory (hopefully in some optimized form). These possies reflect the constraints defined by the program and influence or are influenced by external resources. Whenever changes occur within external resources (i.e. mouse movements or keys pressed), these changes are propagated throughout the in-memory semantic structure of the program possibly causing other external resources (i.e. display, console) to change accordingly. Multiple changes are propagated in parallel and the posset programming language design makes sure these concurrent processes do not have to wait for each other. The constrainer runtime would give rise to full (or almost full) implicit parallelism where posset programs can utilize parallel processing without the developer of the program having to worry about anything.

Examples

This section contains some example code. The full javacc description of the syntax can be found here.

Boolean
(
	'2 first;
)

The code above defines a new derived posset called Boolean using the prime 2 posset (i.e. the atomic possibility set with two possibilities). first is the unique name of the '2 posset within the scope of the Boolean definition. When materialized, this posset consists of the following elements: {(#1),(#2)}.

Test
(
	Boolean first[A];
	Boolean second[A];
)

The example above shows the use of the variable A to make two possets synchronize. In this case the Test posset consists of the product of two Boolean possets. Without the A variable on both, they would not stay in sync when iterating the Test posset and this would result in a cardinality of 4. However, with the A's in place, the Test posset has a cardinality of 2.

False
(
	Boolean first
	(
		first[A];
	)
)
{
	(A)
	(#2)
}

Using the Boolean posset definition, the code above defines a new derived posset called False that limits or filters the '2 posset named first in Boolean to possy #2. Every possy of every prime posset 'n can be referenced using the #k syntax, where 0 < k <= n. Note that the A represents a variable tied to the first posset and used in the lower part to target the filter. When materialized, this posset consists of the following elements: {(#2)}. The posset above is also an example of how the Posset programming language does not distinguish between types and instances. In a typical programming language there is the distinction between the type `boolean` and an instance with that type `false`. However, in Posset both are possets where `False` is derived from `Boolean`.

Or
(
	Boolean first ( first[A]; )
	Boolean second ( first[B]; )
	Boolean third ( first[C]; )
)
{
	(A,B,C)
	(#1,#1,#1)
	(#1,#2,#1)
	(#2,#1,#1)
	(#2,#2,#2)
}

The same technique can be used to define a derived posset named Or that represents the OR operation. The variables A, B and C target the three '2s of each Boolean. These variables are again used to filter (i.e. constrain or limit) the possies of the Or posset to the correct semantics.

Digit
(
	'2 d1;
	'5 d2;
)

Zero(Digit o1(d1[Y];d2[Z];)){(Y,Z)(#1,#1)}
One(Digit o1(d1[Y];d2[Z];)){(Y,Z)(#1,#2)}
Two(Digit o1(d1[Y];d2[Z];)){(Y,Z)(#1,#3)}
Three(Digit o1(d1[Y];d2[Z];)){(Y,Z)(#1,#4)}
Four(Digit o1(d1[Y];d2[Z];)){(Y,Z)(#1,#5)}
Five(Digit o1(d1[Y];d2[Z];)){(Y,Z)(#2,#1)}
Six(Digit o1(d1[Y];d2[Z];)){(Y,Z)(#2,#2)}
Seven(Digit o1(d1[Y];d2[Z];)){(Y,Z)(#2,#3)}
Eight(Digit o1(d1[Y];d2[Z];)){(Y,Z)(#2,#4)}
Nine(Digit o1(d1[Y];d2[Z];)){(Y,Z)(#2,#5)}

In a similar fashion the above code defines digits. More single digit definitions such as addition and greater than and smaller than can be found here.

Performance

The most important performance issue that the posset programming language is prone to is the combinatory explosion. Because the product operation is used for combining possets, derived possets quickly contain many millions of possies that take way too long to iterate. Instead of trying to prevent the combinatory explosion and giving the developer tools to prune the possies (such as the cut operator in Prolog), the language provides no such tools and optimize the interpreter (for example by collapsing variables) and hope this will in the end be enough.

Collapsed variables

As mention above, one way of improving the performance is by *collapsing the variables* in a posset.

Collapsing variables

The picture above shows this process in the simple Test posset of the examples above. Figure (A) is the structure of the Test posset before the variables are collapsed. Materializing the Test posset in the (A) situation would mean combining the possies of both Boolean possets and keeping those where they are the same. However, the semantics of the Test posset would not change if these two Boolean possets would be replaced by a single one, since the A variable forces them to be in sync anyway. In (B) it is illustrated that possets that share a variable can be replaced by a single posset. This is not only possible with variable on exactly the same possets, but also possets that have a common ancestor, although some caution is required to make sure their path to this ancestor is respected. Since the number of prime possets are reduced, materializing the Test posset after the process of collapsing the variables is considerably more performant. This process is also possible on vastly more complex possets where the semantics can stay the same while improving the performance by a lot. The process also cause multiple variables (that are defined at different levels within the posset) to be collapsed into a single posset, because the variable overlap.

Turing completeness

The language should be Turing complete but proving this failed when trying to implement a brainfuck compiler with it. The source code of this attempt can be found here. What was missing was a way to represent list-like data structures and aggregation like functions.

Todo

Topics yet to be described:

• Parallelism and data dependency
• I/O
• Implicit parallelism
• Sets and aggregation

More information

• Source code: GitHub repo

Disclaimer

The description of the posset programming language above does not contain any equivocal language although it should, because it contains many speculative and bold claims that are not yet backed up by any evidence. The author has been (slowly) thinking about and working on this programming language since early 2000 and is looking for some insight of why the above is nothing special or revolutionary at all. Although ignorance can be bliss, feedback is very welcome from the many programming language enthusiasts and experts on this wiki!