Better Operator Overloading

This is a followup to Extreme Operator Overloading, and attempts to describe the language idea more formally than the previous time.

Values

The language manipulates non-mutable values (in that they can be created, but not changed or assigned to). Values fall into three categories:

• Literals. These are things like 42, 3.141592f, "Hello", 'x' or false. They also include "constructed literals", such as string(12,'x'), array(42,"Hello").
• Objects. These are in fact fieldsets (bindings between field-names and field-values), such as (name -> "Joe", age -> 35). Some of the fields may bear the extend keyword, which (as shown later) indicates that the object may "decay" to that field when used in a context where that field could be used but the object couldn't: (name -> extend "Joe", age -> 35) means that the program will use the name whenever a string could be used but the object couldn't. Objects also include tuples, of the form ("Joe",35), and everything may be mixed: (extend "Joe", age -> 35). An unnamed field automatically receives the name fieldi for the smallest i > 0 that causes no collision with the other names, the names for unnamed fields being alotted left-to-right.
• Singletons. These objects are unique and different from every other object in the program. A singleton named X is created with the new X; statement, which will create a new singleton every single time it's evaluated. Singletons have no default properties and cannot be used by default to do anything at all.

Grammar

The basic building block of the grammar is the expression. Expressions fall into two categories: overloadable and non-overloadable. Expressions are (with the expected priorities wherever applicable):

expr =
 | x                       // Variable name, literal or object creation.
 | expr.field              // Field access. Overloadable.
 | expr:expr               // Satisfying a contract. Specially overloadable.
 | expr[expr]              // Subscripting. Oveloadable.
 | expr expr               // Function application. Overloadable.
 | expr op expr            // Binary operation (+,-,&&,^,%,<<,== etc). Overloadable.
 | op expr                 // Unary operation (-,*,!). Overloadable.
 | { decl* } expr          // Declaration list. 
 | expr as expr            // Explicit value casting. Overloadable.
 | using(expr) expr        // Using declarations. Specially overloadable.
 | if expr then expr else expr

For instance: if is_odd n then (10,22).field2 * using(rational) 1 / 2 else -3 A declaration describes the behaviour or existence of a given overloadable expression. It takes an extremely simple form:

decl =
  | conditions {{ expr }} = expr;          // Conditional definition.
  | conditions {{ using(x) }} = { decl* }; // 'Using' definition.
  | new x;                                 // Singleton declaration.
  | using x;                               // Using a list of declarations.

conditions =
  | ε                      // No conditions
  | for(x:expr) conditions // Universal quantifier
  | if(expr) conditions    // Restriction

The expression between the {{ }} must be a construct made of overloadable expressions, and its terminal members must be variables names, non-constructed literals or objects constructed from these. For instance: new max; for(x:int,y:int) if (x >= y) {{ max (x,y) }} = x; for(x:int,y:int) if (x < y) {{ max (x,y) }} = y; The using(e) e expression is specially overladable: its declaration only incorporates the object between parentheses, and describes a set of declarations as opposed to an expression. Note that the e:e expression is also specially overloadable, but may not be placed in a declaration. This expression is automatically overloaded when e as e is overloaded, following the simple rule that y : t is true if and only if there exists a value x such that x as t yields y (for obvious reasons, this is undecidable and the compiler may decide to arbitrarily complain about it if the definition of e as t is too complex). A file is considered to be a list of declarations decl*. For syntactic sugar reasons, declarations may be factored (so for(a) b; and for(a) c; can be folded into for(a) {b; c;} and the same, intuitively, for if and else). Also, using(a,b) e is meant to mean using(a) using(b) e and new a,b; means new a; new b;.

Compiling

If file filename.ext contains code code, then compiling code into a library or program creates a binary containing the equivalent of:

new filename;
{{ using(filename) }} = { code };

The only exception is when there is already a definition of new filename; in the file. In that case, the compiler does not generate a new wrapper and uses the existing one instead (throwing errors for any errors that do not relate to filename. This allows:

// minmax.ext
new minmax;
{{ minmax }} = (

  min -> { 
    new min; 
    for (x:int,y:int) 
      if (x < y) {{ min (x,y) }} = x;
      else       {{ min (x,y) }} = y; 
  } min,

  max -> { 
    new max;
    for (x:int,y:int) 
      if (x < y) {{ max (x,y) }} = y;
      else       {{ max (x,y) }} = x; 
  } max

);

// otherfile.ext
minmax.min(1,2)

Linking libraries together simply concatenates the code equivalent of the libraries into a single code (in the order that libraries were linked in) then compiles the result as if it were a new file (thus adding another level of using indirection).

Semantics

The meaty part. Evaluating an expression, when its arguments are all values (as opposed to other expressions) consists in replacing the expression with a value according to certain rules. When the arguments are other expressions, then these expressions are evaluated in unspecified order, so they become values, and the encompassing expression can be evaluated. The rules for evaluating an expression are conceptually simple (the devil is in the details): the evaluator looks for a corresponding expression definition within the environment (the set of definitions visible from where the expression is), replaces the expression with the expression it's defined as and (if it's not a value) evaluates the result until it's a value. For instance, consider the evaluation of 1 + (max (1+2,4)), with the max function defined above.

• To evaluate the sum, the max expression must be reduced to a value, which means the tuple must be reduced to a value, which means 1+2 must be reduced to a value. In the environment, {{ 1 + 2 }} = 3; and so the tuple becomes (3,4). This is a clean and nice value, so we can move on.
• To evaluate max (3,4), the evaluator has two definitions. The first is invalid here, because it violates constraint 3 >= 4, but the second is usable. Thus, the entire term evaluates to y where (x = 3, y = 4), which means 4.
• Then, {{ 1 + 4 }} = 5; is applied to obtain the final value, 5.

There are four difficult concepts to understand: environment layers, overloading, environment taint and environment injection.

Environment Layers

Environments are ordered sets of definitions and new expressions, each of them being a layer. Whenever a new definition is encountered, it is added at the top of the set (it becomes the topmost layer). Layers added at a given time will disappear from the environment when the expression they were in disappears.

• using(e) x: the using(e) statement is executed, which may add any number of layers on top of the environment. These layers disappear as soon as x is fully evaluated.
• { d; } x: the d definitions are added to the environment, and disappear when x is fully evaluated.
• { a; b; } x is actually interpreted as { a; } { b; } x, so that the layer created by definition a is usable when within the definition b, and all of them disappear when xis evaluated.

Overloading

Several definitions may exist for any given expression. These definitions differ by the constraints imposed on the arguments: are they integers? Tuples? Must they satisfy a given property? One must also take into account the existence of extends fields in objects, which let objects masquerade as other objects. When no definitions may be made to fit an expression, throw an error. When exactly one definition can fit an expression, use it. When more than one definition can fit an expression, things get ugly. First, the one which requires the least extends conversions to be applied is used. Then if ambiguity remains, the highest layer of all is used.

Environment Taint

This is the most difficult rule, which can be described as: "If a definition may affect the value of an expression, then it doesn't disappear from the environment for that value." The definition remains in the environment, specialized for that value only, and other definitions may disappear from under it. However, this definition in turn may reference other definitions, at which point they, too, remain in the environment in the same order. The objective of this rule is to allow returning objects along with their intended behaviour, instead of just their value. Otherwise, returning functions would be impossible.

new add;
for (x:int) {{add x}} = { 
  new closure; 
  for (y:int) {{closure y}} = x + y;
} closure;

In the example above, it is necessary for the {{ closure y }} definition to remain available. The environment taint rule performs this by keeping that definition alive until the returned value disappears. The rule is called taint because building a definition around a given value effectively taints the value with the definition forever. So, one of the funny things that you can do is this:

new strange;
for (x:int) {{strange x}} = {
  for (y:int) {{x + y}} = 0;
} x; 

Environment Injection

This is the complex consequence of Environment Layers and Overloading. It explains that the behaviour of an object inside a definition depends on the environment in which the definition is used (as opposed to usual languages where the environment in which the definitions is defined is actually used). Consider:

new succ;
for (x:int) {{succ x}} = x + 1;

new poly;
for (x:int) {{poly x}} = (succ x) * (succ x); 

  // Returns 3*3 = 9
  ... poly 2 ...

  // Returns 2*2 = 4
  ... { for(x:int) {{succ x}} = x; } poly 2 ...

It's arguably not quite sane, but it has its uses. Besides, library writers can always protect themselves by reloading the correct layer of definitions on top of the layer defined by the user before the call:

// filename.ext
new succ;
for (x:int) {{succ x}} = x + 1;

new poly;
for (x:int) {{poly x}} = using(filename) (succ x) * (succ x); 

// somewhereelse.ext
using (filename);

  // Returns 3*3 = 9
  ... { for(x:int) {{succ x}} = x; } poly 2 ...

Static Checking

Well, this is still giving me trouble. I'll post more about this when I actually manage to think through it.