The Xoomonk Programming Language

Language version 1.0

Abstract

Xoomonk is a programming language in which malingering updatable stores are first-class objects. Malingering updatable stores unify several language constructs, including procedure activations, named parameters, and object-like data structures.

-> Tests for functionality "Interpret Xoomonk program"

Description

Overall, Xoomonk looks like a "typical" imperative language. The result of evaluating an expression can be assigned to a variable, and the contents of a variable can be used in a subsequent expression.

| a := 1
| b := a
| print b
= 1

Like most typical imperative languages, a block (delimited by curly braces) may contain a sequence of imperative statements. However, such blocks may appear as terms in expressions; here they evaluate to entire updatable stores.

| a := {
|   c := 5
|   d := c
| }
| print a
= [c=5,d=5]

Once created, a store can be updated and accessed.

| a := {
|   c := 5
|   d := c
| }
| print a
| a.d := 7
| print a
| print a.c
= [c=5,d=5]
= [c=5,d=7]
= 5

A store can also be assigned to a variable after creation. Stores are accessed by reference, so this creates two aliases to the same store.

| a := {
|   c := 5
|   d := c
| }
| b := a
| b.c := 17
| print a
| print b
= [c=17,d=5]
= [c=17,d=5]

To create an independent copy of the store, the postfix * operator is used.

| a := {
|   c := 5
|   d := c
| }
| b := a*
| b.c := 17
| print a
| print b
= [c=5,d=5]
= [c=17,d=5]

Empty blocks are permissible.

| a := {}
| print a
= []

Once a store has been created, only those variables used in the store can be updated and accessed — new variables cannot be added.

| a := { b := 6 }
| print a.c
? Attempt to access undefined variable c

| a := { b := 6 }
| a.c := 12
? Attempt to assign undefined variable c

In the outermost level, as well, a variable cannot be used before it has been assigned.

| print r
| r := 5
? Attempt to access undefined variable r

Stores and integers are the only two data types in Xoomonk. However, there are some special forms of the print statement, demonstrated here, which allow for textual output.

| a := 65
| print char a
| print string "Hello, world!"
| print string "The value of a is ";
| print a;
| print string "!"
= A
= Hello, world!
= The value of a is 65!

Xoomonk enforces strict block scope. Variables can be shadowed in an inner block.

| a := 14
| b := {
|   a := 12
|   print a
| }
| print a
= 12
= 14

We now present today's main feature.

It's important to understand that a block need not define all the variables used in it. That is, a block may contain variables which are used, but never assigned a value, in the block. Such blocks do not immediately evaluate to a store. Instead, they evaluate to an object called an unsaturated store.

Or, to put it another way:

If, in a block, you refer to a variable which has not yet been given a value in that updatable store, the computations within the block are not performed until that variable is given a value. Such a store is called an unsaturated store.

| a := {
|   d := c
| }
| print a
= [c=?,d=0]

An unsaturated store behaves similarly to a saturated store in certain respects. In particular, unsaturated stores can be updated. If doing so means that all of the undefined variables in the store are now defined, the block associated with that store is evaluated, and the store becomes saturated. In this sense, an unsaturated store is like a promise, and this bears some resemblance to lazy evaluation (thus the term malingering).

| a := {
|   print string "executing block"
|   d := c
| }
| print a
| a.c := 7
| print a
= [c=?,d=0]
= executing block
= [c=7,d=7]

Once a store has become saturated, the block associated with it is not executed again.

| a := {
|   d := c
| }
| a.c := 7
| print a
| a.c := 4
| print a
= [c=7,d=7]
= [c=4,d=7]

Saturating one copy of an unsaturated store will not saturate the other copy.

| a := {
|   print string "saturated"
|   d := c
| }
| b := a*
| print a
| print b
| a.c := 7
| print a
| print b
| b.c := 5
| print b
= [c=?,d=0]
= [c=?,d=0]
= saturated
= [c=7,d=7]
= [c=?,d=0]
= saturated
= [c=5,d=5]

Unassigned variables cannot be accessed from an unsaturated store.

| a := {
|   d := c
| }
| x := a.c
? Attempt to access unassigned variable c

Assigned variables can be accessed from an unsaturated store, but they have the value 0 until the store is saturated.

| a := {
|   d := c
| }
| print a.d
= 0

This is true, even if the variable is assigned a constant expression inside the block.

| a := {
|   b := 7
|   d := c
| }
| print a.b
= 0

If, however, the unsaturated store contains some unassigned variables that have been updated since the store was created, those variable may be accessed, even if the store is still unsaturated.

| a := {
|   print string "executing block"
|   p := q
|   d := c
| }
| a.q := 7
| print a.q
= 7

It is possible to assign a variable in an unsaturated store which is assigned somewhere in the block. When the store becomes saturated, however, that variable will be overwritten.

| a := {
|   b := 7
|   d := c
| }
| a.b := 4
| print a
= [b=4,c=?,d=0]

| a := {
|   b := 7
|   d := c
| }
| a.b := 4
| a.c := 4
| print a
= [b=7,c=4,d=4]

It's important to note that a block is considered saturated when all the variables used in the block are assigned somewhere in the block. If, in a block, a variable is used before it is assigned, the block will still be executed, if saturated.

| a := {
|   c := b
| }
| a.b := 5
| print a
= [b=5,c=5]

| a := {
|   b := b
| }
? Attempt to access undefined variable b

A way to work around this is to add an extra unassigned variable, to keep the store unsaturated.

| a := {
|   print string "executing block"
|   l := b
|   b := 3
|   l := 3
| }
| print string "saturating store"
| a.b := 5
| print a
? Attempt to access undefined variable b

| a := {
|   print string "executing block"
|   l := b
|   b := 3
|   l := c
|   l := 3
| }
| print string "saturating store"
| a.b := 5
| a.c := 9
| print a
= saturating store
= executing block
= [b=3,c=9,l=3]

We now describe how this language is (we reasonably assume) Turing-complete.

Firstly, there is a built-in special store called $, which is a Special Name which is magically available in every scope and which cannot be assigned to, but which can be modified.

| $ := 4
? Cannot assign to $

| $.foo := 4
| print string "ok"
= ok

Since $ is available in every scope, it can be thought of as being the "global scope", and can be conveniently used to communicate values across scopes.

| $.r := 4
| q := {
|   print string "hello"
|   c := $.r
|   j := d
| }
| q.d := 5
| print q.c
= hello
= 4

Operations are accomplished with certain built-in unsaturated stores. For example, there is a store called add, which can be used for addition. These built-in stores are all located in the $ store.

| print $.add
= [result=0,x=?,y=?]

| a := {
|   print $.add
| }
= [result=0,x=?,y=?]

| $.add.x := 3
| $.add.y := 5
| print $.add.result
| print $.add
= 8
= [result=8,x=3,y=5]

Because using a built-in operation store in this way saturates it, it cannot be used again. Typically, you will want to make a copy of the store first, and use that copy, leaving the built-in store unmodified.

| o1 := $.add*
| o1.x := 4
| o1.y := 7
| o2 := $.add*
| o2.x := o1.result
| o2.y := 9
| print o2.result
= 20

Since Xoomonk is not a strictly minimalist language, there is a selection of built-in stores which provide useful operations: $.add, $.sub, $.mul, $.div, $.gt, and $.not.

| o1 := $.sub*
| o1.x := 7
| o1.y := 4
| print o1.result
= 3

| o1 := $.mul*
| o1.x := 7
| o1.y := 4
| print o1.result
= 28

| o1 := $.div*
| o1.x := 29
| o1.y := 4
| print o1.result
= 7

| o1 := $.gt*
| o1.x := 29
| o1.y := 4
| print o1.result
= 1

| o1 := $.gt*
| o1.x := 4
| o1.y := 4
| print o1.result
= 0

| o1 := $.not*
| o1.x := 29
| print o1.result
= 0

| o1 := $.not*
| o1.x := 0
| print o1.result
= 1

Decision-making is also accomplished with a built-in store, $.if. This store contains variables caled cond, then, and else. cond should be an integer, and then and else should be unsaturated stores where x is unassigned. When the first three are assigned values, if cond is nonzero, it is assigned to x in the then store; otherwise, if it is zero, it is assigned to x in the else store.

| o1 := $.if*
| o1.then := {
|   y := x
|   print string "condition is true"
| }
| o1.else := {
|   y := x
|   print string "condition is false"
| }
| o1.cond := 0
= condition is false

| o1 := $.if*
| o1.then := {
|   y := x
|   print string "condition is true"
| }
| o1.else := {
|   y := x
|   print string "condition is false"
| }
| o1.cond := 1
= condition is true

Repetition is also accomplished with a built-in store, $.loop. This store contains an unassigned variable called do. When it is assigned a value, assumed to be an unsaturated store, a copy of that unsaturated store is made. The variable x inside that copy is assigned the value 0. This is supposed to saturate the store. The variable continue is then accessed from the store. If it is nonzero, the process repeats, with another copy of the do store getting 0 assigned to its x, and so forth.

| l := $.loop*
| $.counter := 5
| l.do := {
|   y := x
|   print $.counter
|   o := $.sub*
|   o.x := $.counter
|   o.y := 1
|   $.counter := o.result
|   continue := o.result
| }
| print string "done!"
= 5
= 4
= 3
= 2
= 1
= done!

Because the $.loop construct will always execute the do store at least once (even assuming its only unassigned variable is x), it acts like a so-called repeat loop. It can be used in conjunction with $.if to simulate a so-called while loop. With this loop, the built-in operations provided, and variables which may contain unbounded integer values, Xoomonk should be uncontroversially Turing-complete. (Although admittedly, using an unbounded integer or two to simulate a Turing machine's tape, especially with Xoomonk's arithmetic operations, would be fairly cumbersome.)

Finally, there is no provision for defining functions or procedures, because malingering stores can act as these constructs.

| perimeter := {
|   o1 := $.mul*
|   o1.x := x
|   o1.y := 2
|   o2 := $.mul*
|   o2.x := y
|   o2.y := 2
|   o3 := $.add*
|   o3.x := o1.result
|   o3.y := o2.result
|   result := o3.result
| }
| p1 := perimeter*
| p1.x := 13
| p1.y := 6
| print p1.result
| p2 := perimeter*
| p2.x := 4
| p2.y := 1
| print p2.result
= 38
= 10

Grammar

Xoomonk ::= { Stmt }.
Stmt    ::= Assign | Print.
Assign  ::= Ref ":=" Expr.
Print   ::= "print" ("string" <string> | "char" Expr | Expr) [";"].
Expr    ::= (Block | Ref | Const) ["*"].
Block   ::= "{" { Stmt } "}".
Ref     ::= Name {"." Name}.
Name    ::= "$" | <alphanumeric>.
Const   ::= <integer-literal>.

Discussion

There is some similarity with Wouter van Oortmerssen's language Bla, in that function environments are very close cousins of updatable stores. But Xoomonk, quite unlike Bla, is an imperative language; once created, a store may be updated at any point. And, of course, this property is exploited in the introduction of malingering stores.

The original idea for Xoomonk had an infix operator &, which took two stores as its arguments (at least one of which must be saturated) and evaluated to a third store which was the result of merging the two argument stores. This result store may be saturated even if only one of the argument stores was saturated, if the saturated store gave all the values that the unsaturated store needed. This operator was dropped because it is mostly just syntactic sugar for assigning each of the desired variables from one store to the other. However, it does admittedly provide a very natural syntax, which orthogonally includes "named arguments", when using unsaturated stores as procedures:

perimeter = {
  # see example above
}
g := perimeter* & { x := 13 y := 6 }
print g.result

Xoomonk 0.1 had slightly more sophisticated semantics for unsaturated stores than Xoomonk 1.0 has. Specifically, there was a (fuzzy) idea that a variable could be "unresolved", that is, assigned a value derived from variables which were unassigned. Xoomonk 1.0 simplified this to assigned variables having the value 0 until the store is saturated, and a store being saturated when all of its unassigned variables have been given a value, even if some assigned variables are used in the block before they have ever been assigned. Xoomonk 1.0 also dropped the idea that the main program was a block.

In addition, in Xoomonk 0.1, $ was an prefix operator rather than a Special Name, and the Special Name ^ allowed access to the lexically enclosing store of a block. While there is a certain elegance to this, it was deemed overkill, and in Xoomonk 1.0, $ was changed to a Special Name which referred to a global store (which can be used to communicate values between scopes without messing about with lexically enclosing "upvalues".)

Xoomonk, as a project, was also an early experiment in test-driven language design. When Xoomonk 0.1 was released, the language was described only with the set of examples (above) written in Falderal format, each of which both illustrates some aspect of the language, and is used as a test case. When a reference interpreter was implemented for Xoomonk 1.0, this made implementation much easier. (Since Xoomonk 0.1 was released, I've used this technique successfully for several other languages as well.)

Happy malingering!

-Chris Pressey
Cat's Eye Technologies
August 7, 2011
Evanston, IL