The Unlikely Programming Language

Overview

Unlikely is a programming language with the following traits:

• Unlikely conflates objects with continuations, and methods with labels. All classes are subclasses of the root class Continuation. Every object can be continued at any method. Every method, except for the continue method on the built-in class Stop, must continue some other method at the end of its definition.
• All Unlikely program structures are exposed as objects with commensurate inheritance relationships. For example, every Unlikely program is a subclass of Program, and the classes If and Switch are both subclasses of the abstract base class Branch.
• Unlikely takes dependency injection to the logical extreme. Dependency injection is an increasingly popular modern object-oriented program construction technique which allows the specific classes which will be used by some class ("dependencies") to be specified ("injected") when that class is instantiated. Unlikely goes one step further by requiring that all specific classes used by some class are specified during instantiation.

Semantics

Classes

A class is a schema describing a set of objects. Instantiating a class produces a new object of that class. When a class is instantiated, all classes that are referenced by the class (dependant classes) must be named (injected) by the instantiating code (the instantiator). For each requested dependant class, any subclass of it may be supplied by the instantiator, further specifying and constraining behaviour (a technique called dependency injection). In this way, classes are inherently parameterized.

When a class refers to itself, it is considered a dependant class of itself; it (or a subclass) must be injected by the instantiator.

All specified dependant classes must be unique (no dependant class may be specified more than once.) Final classes need not and may not be specified as dependant classes because, being final, there is no subclass that the instantiator could possibly substitute for them.

Each class may define zero or more properties and zero or more methods.

Inheritance

Whenever a class is defined in Unlikely source code, a superclass must be named; the class being defined is thus a subclass that inherits from that superclass. Its inheritance consists of the properties and methods defined by the superclass and all of its ancestors (i.e. including all properties and methods that the superclass inherited from its own superclasses) as well as the dependant classes of the superclass. The subclass may not inject dependencies when inheriting from a superclass. Only single inheritance is supported.

A subclass may override methods that it inherits from its superclass. It may access the method definition of its direct superclass (or any indirect ancestor class) by naming that superclass explicitly in a continue.

A class may be declared as final, in which case it may not be subclassed. In addition, final dependant classes may not be injected.

A class may also be declared as saturated, in which case it can be subclassed, but subclasses of it must also be declared as saturated, and they cannot define any new methods. They can only override existing methods. In fact, the root class Continuation is declared saturated, so really, all objects have exactly one method, continue.

If a class defines or inherits any abstract methods, that class must be declared as abstract. Abstract classes cannot be instantiated. Any subclass of an abstract class must define all inherited abstract methods in order to be considered concrete and thus instantiatable.

Properties

Each property has a particular type, which is a class. The values it may take on are objects of that class, or of its subclasses.

Each object has its own instances of the properties defined on the class, and each of these properties may take on different values.

All state of an object is stored in its properties. Properties are effectively public; they can be modified by code in any method in any class.

The root class Continuation defines one property, accumulator, of type Passive, which all classes inherit.

Subclasses may not override inherited properties.

Methods

A method is a label on a piece of code inside a class. The methods of a class are shared by all objects of that class.

A method may be declared abstract instead of defining code for it. Classes which contain abstract methods must themselves be declared abstract.

Only one thing may be done to a method in code, which is to continue it with respect to some object; this is described in the next section.

A method may declare zero or more arguments. Each argument has a type, which is a class. When a method is continued, a value of the corresponding type (or some subclass of that type) must be given for each argument. In actuality, the arguments merely name properties of the object; they must already be declared in the class before they are listed in the declaration of the method. Passing values in arguments is just shorthand for assigning these properties before continuing the method.

Methods do not have local variables, so for storage must use the properties of the object on which they were continued.

The root class Continuation defines one abstract method which subclasses must implement, called continue(Passive accumulator). By convention, this method is what other methods continue. The accumulator is passed from continuation to continuation, manipulated as execution proceeds.

Code

The code inside a class labelled by a method consists of a series of assignments followed by a continue.

Each assignment consists of an object property on the left-hand side, and an expression on the right-hand side. The the property so named will take on the value resulting from evalulating the given expression. Expressions consist of instantiations of new objects, and references to other object properties.

The continue names a method on an object to which control flow will immediately pass. It may also pass values as arguments to that method; however, this is mere shorthand for assigning properties of the object on which the method being continued is defined. See above under "Methods" for more details.

Passive Data

Passive data values, such as integers and strings, are modelled somewhat specially in Unlikely, in order to strike a balance in language design between "too straightforward" and "too convoluted".

All passive data values are instances of some subclass of the abstract class Passive, which is itself a subclass of Chain. When a passive data value is continued, it passes its own value into the accumulator of the "next" continuation. (It is not necessary, however, to continue the passive data value to obtain its value in all cases.)

Each immediate subclass of Passive gives a data type of values, such as Integer or String. Each of these type-classes has a countably infinite number of subclasses, one for each possible value of that type. It is these classes that are instantiated to acquire a passive value object. For example, three = new 3() instantiates the value 3. When the continue method on this object is continued, the value that it represents will be passed down the chain to the continuation assigned to its next property. For example, three.next = new Print() would cause 3 to be printed when three was continued.

None of the direct subclasses of Passive can be further subclassed. In effect, they are final (despite being abstract!) because all possible subclasses of them already exist.

Syntax

Overview

The overall schema of a class definition is:

class ClassName(ClassName,ClassName) extends ClassName {
  ClassName propname;
  method methodname(ClassName propname, ClassName argname) {
    propname = new ClassName(ClassName,ClassName);
    propname.propertyname = argname;
    goto expr.methodname(expr,expr);
  }
}

Grammar

A somewhat more formal definition of the syntactic structure of Unlikely code is given in the following EBNF-like grammar.

ClassBase   ::= {ClassDefn}.
ClassDefn   ::= "class" ClassName<NEW> "(" [ClassName {"," ClassName}] ")" "extends" ClassName
                ["{" {PropDefn} {MethodDefn} "}"] ["is" ClassMod {"and" ClassMod}].
ClassMod    ::= "final" | "saturated" | "abstract".
PropDefn    ::= ClassName PropName<NEW> ";".
MethodDefn  ::= "method" MethodName<NEW> "(" [ParamDecl {"," ParamDecl}] ")"
                ("{" {Assignment} Continue "}" | "is" "abstract").
ParamDecl   ::= ClassName PropName.
Assignment  ::= QualName "=" Expr ";".
Continue    ::= "goto" PropName "." MethodName "(" [Expr {"," Expr}] ")" ";".
Expr        ::= ConstrExpr | QualName.
ConstrExpr  ::= "new" (ClassName | Constant) "(" [ClassName {"," ClassName}] ")".
QualName    ::= PropName {"." PropName}.
ClassName   ::= <<sequence of alphabetic characters>> | Constant.
Constant    ::= <<sequence of decimal digits>> | <<sequence of arbitrary characters between double quotes>>.

Note that multiple ClassDefns for a single class may appear; each may partially define the class. In this way a "forward declaration" of a class may occur. This may give its name, superclass, and dependant classes, so these can be consumed by some following class that requires them, before the methods of this class are defined. The dependant classes are cumulative over successive partial definitions; they need not be repeated. However the same superclass must be specified for all partial definitions of a class.

Built-in Classes

• Continuation

  The abstract base class that is the superclass of all Unlikely classes, and which can't be instantiated. Declares the property Passive accumulator, and the abstract method continue(Passive accumulator), which all concrete subclasses must implement. Is declared saturated, so no subclass may declare or define any additional methods.

  • Program

    An abstract continuation that provides the guarantee that it can be started (that is, that its continue method can be initially continued) from the operating system. It can be reasonably expected that the accumulator will be assigned a value provided by the user, perhaps via a command-line argument.

    • Stop

      A concrete continuation which exits to the operating system when continued. The accumulator is used as the exit code, assuming the operating system supports this.

    • Chain

      An abstract continuation which defines the property Continuation next. When a subclass of Chain is continued, it will generally continue the continuation assigned to its next property after doing something.

      • Passive

        The abstract final base class representing passive data values. Discards whatever accumulator was passed to it, and passes its own value into the accumulator when it continues the continuation assigned to its next property.

        • Boolean

          The abstract final base class representing boolean values.

          • True, False

            Final classes representing particular boolean values.

        • Integer

          The abstract final base class representing integer values.

          • 0, 1, 2...

            Final classes representing particular integer values. Note that only positive constants are available; negative values must be computed by subtracting from 0.

        • String

          The abstract final class representing string values.

          • "", "a", "b", "aa"...

            Final classes representing particular string values.

      • BinaryOperation

        A continuation which posesses a property value and which yields a value when continued by applying some operation to value (treated as LHS) and the accumulator (treated as RHS.)

        • Add

          A concrete binary operation which adds value to the accumulator and passes the result when continuing next.

        • Subtract

          A concrete binary operation which subtracts the accumulator from value and passes the result when continuing next.

        • Multiply

          A concrete binary operation which multiplies value by the accumulator and passes the result when continuing next.

        • Divide

          A concrete binary operation which divides value by the accumulator and passes the result when continuing next.

        • Condition

          A BinaryOperation which yields a boolean value.

          • Equal

            A concrete binary operation which compares value to the accumulator and passes True when continuing next only if they are equal.

          • GreaterThan

            A concrete binary operation which compares value to the accumulator and passes True when continuing next only if value is greater.

      • Print

        A concrete continuation which displays the value of the accumulator to the user before continuing its next property.

      • Input

        A concrete continuation which obtains a value from the user, and passes this value in the accumulator when continuing its next property.

      • Branch

        An abstract continuation which continues one of the continuations assigned to its properties, based on some other information. Defines the Chain property else which represents the basic alternate continuation that can be continued instead of next.

        • If

          A continuation which continues one of two continuations assigned to its properties, next and else, based on whether the accumulator is an instance of True or False.

        • Switch

          An abstract continuation whose behaviour differs on subsequent times it is continued. This is implemented by means of a state property which changes values each time the switch is continued; depending on the value of state, different things happen.

          • Loop

            An abstract continuation which is intended to implement a loop. However, this is not automatic; some continuation chain leading from this continuation must lead back to this continuation in order for actual repetition to take place.

            • WhileLoop

              A concrete Loop which, on odd visits continues its test property. It is assumed that some continuation down that chain continues this WhileLoop object with a boolean value in the accumulator. On these even visits, it will behave like an If: when the boolean is a True, next is continued, otherwise else.

            • ForLoop

              A concrete Loop which defines value, delta, and finish properties, all Integers. On each visit, it checks if value equals finish; if not, it adds delta to value and continues next. But if so, it simply continues else.

Implementations

There is not currently a reference implementation of Unlikely. Any contradictions and/or grey areas in this document will therefore have nowhere to turn to to be cleared up.

There is, however, a partial and non-normative implementation of Unlikely, a static analyzer written in Python called Coldwater. It parses Unlikely programs and identifies many type errors and other statically-detectable invalid programs. It is meant to give some body to the ideas present in Unlikely, without actually going so far as implementing it in full.

The construction of Coldwater helped clear up some of the fuzzier corners of the language. However, there are probably several areas that remain fuzzy and render the language unsuitable for anything but the most trivial programming. Extending Coldwater to be a full-fledged Unlikely interpreter will probably help define the language. However that project has been deferred as future work, and any clarifications that come from it will be incorporated only in a future language version.

Discussion

This section contains some random thoughts and reflections on the Unlikely programming language.

There is a rough analogy between Unlikely's requisite dependency injection class parameters, and value parameters in languages without global variables. There is no implicit referent when you say Foo; Foo must name some parameter that has been passed into scope.

Because all the parts of the language are modelled as objects, the language's execution model has some resemblance to an object-oriented AST interpreter for itself. Except, of course, these objects are continuations, so it is not like a recursive, depth-first walk of the AST; it is much closer to the technique of threading the AST and following that thread.

At one point I included the constraint that the set of dependant classes specified by a class must be mutually disjoint; that is, no dependant class in the set could be a subclass of some other dependant class in the set. I am not entirely sure why I introduced that constraint, since it could well be valuable to refine two classes by injection even when one of those classes is a subclass of the other. I took it out.

Because properties cannot be redefined in subclasses, and because parameters to methods are just syntactic sugar for properties, methods cannot be overloaded. In particular continue must always work on a Passive parameter, although of course it is mere convention that the method works on the accumulator property anyway.

Unlikely is Turing-complete. (I will assert this because it seems reasonable to me, but I do not have a proof, so I may be wrong.) The Unlikely language is not minimal. In particular, the Loop class and its subclasses WhileLoop and ForLoop could be removed, and the resulting language would still be Turing-complete. In fact, WhileLoop and ForLoop could probably be implemented in Unlikely and provided in an extension class library.

The idea to conflate contintuations and objects was inspired by the data-structure representation of continuations in Chapter 7 of Essentials of Programming Languages, 2nd ed., which embodies a tiny measure of inheritance. The idea that language constructs have commensurate inheritance relationships (WhileLoop and ForLoop are subclasses of Loop, etc.) was borrowed from Steve Yegge's article Scheming is Believing. The idea that all programs are subclasses of Program, which dovetails so nicely with that, was borrowed from Brian Connors' "Sulawesi" language design. The idea that every concrete value has its own class, leading to abstract final classes with countably infinite subclasses, was pure desperation.

For the purpose of defining computable functions, the Unlikely-Calculus could be considered as a variant of Unlikely without Print or Input classes. The Stop class would be there redefined to yield the value passed to the accumulator as the result of evaluation, rather than as an operating system exit code.

It's a safe bet that there is at least one person out there who will be disappointed that this language is named Unlikely yet contains no probabilistic design features.

Happy object-method-continuing!
Chris Pressey
March 15, 2009
Bellevue, WA