git @ Cat's Eye Technologies Unlikely / master
master

Tree @master (Download .tar.gz)

The Unlikely Programming Language

Overview

Unlikely is a programming language with the following traits:

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

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