The Freya Programming Language

Enter Lyra

2008-09-07T15:41:00.033+02:00

Let me state this loud and clear: I'm proud of Freya and the Freya compiler. I think my goals, or almost all of them, has been achieved: there's a working implementation of a powerful general programming language, running on a powerful interesting framework. What's more: I have great plans for Freya, including the addition of some interesting features not found in similar languages.

There's a catch, however: Freya is a complex language, requiring a complex implementation. And I'm virtually alone, by my own decision, developing the language, the compiler and a simple IDE for testing... and that shows. For instance: almost all relevant features from C^# 2.0 has already been included and implemented in Freya, and we already have some features from C^# 3.0, as extension methods, and object and collection initializers. Nevertheless, there are some equally important features still missing, such as anonymous methods and complex type inference for lambdas (type inference for generic method calls, however, is already working). And the worst part is that we'll need to rewrite the type attribution from the compiler in order to accommodate the powerful inference engine required for these enhancements.

So enter Lyra (pronounced as lie-rah). Lyra is a fully developed and independent programming language derived from Freya. Its syntax is almost identical to Freya's, but we have introduced some simplifications, in order to make it easier to understand and implement. These are some of the differences:

Implementation in Lyra takes place along with declaration. No more separated implementation for sections, for including executable content.
Property and event implementations have changed accordingly. The new implementation syntax is very compact and easy to understand, and uses four new special "keywords": get:, set:, add: and remove:. Semicolons are an integral part of the corresponding tokens, and they avoid both those dirty contextual keywords and disturbing valid identifiers in existing code.
Interface delegation is supported, but it has moved to the implementing member declaration.
Constructor calls now requires parentheses, except when followed by a list initializer.
In compensation, constructor calls can now start an object path.
Local variable declarations have been moved to the statement list, as declaration statements. This trick avoids some syntactic anomalies while defining properties and events.

Let's see an example showing how to write properties in Lyra:

property Items[Index: Integer]: Boolean;
get:
    // Compound assignments are not expressions.
    Index -= Min;
    // then is optional before a keyword.
    if Index < 0 or Index > High
        raise new ArgumentException("Index");
    // Symbolic and literal operators are both allowed.
    Result := (Bits[Index div 32] &
        (1 << (Index mod 32))) <> 0
set:
    Index -= Min;
    if Index < 0 or Index > High
        raise new ArgumentException("Index");
    if Value then
        Bits[Index div 32] |= 1 << (Index mod 32)
    else
        Bits[Index div 32] &= ~(1 << (Index mod 32))
end

Of course, we can still use most of the Freya tricks, such as expression-based methods and properties (and operators, and iterators), the abbreviated syntax for constructor chains, implicitly implemented properties (I think Freya/Lyra's trick is better than C^#'s). Assertions are fully supported, even when declared in an interface type. Numeric types are still implicitly extended with static members from the Math class. Lyra, in other words, is as powerful as Freya... but probably more elegant, too.

In the next months, all our research and implementation effort will concentrate on Lyra. These are some of our planned tasks:

Anonymous methods and lambdas are still missing. Probably, I'll implement only one of the syntactic varieties, but I still have some troubles with the syntax: C#'s lambdas, when implemented verbatim, don't make a valid LALR(1) grammar.
I still believe in the usefulness of access sentinels: wrapping code that would be inserted by the compiler around methods that access some class members. This is a safe form of Aspect Oriented Programming (and no, properties don't do the same trick!)
Lyra will feature mixins declared with interfaces. You'll be able to add common implementation methods to interfaces, as in this example:

IStack = interface[X]
    property Count: Integer; readonly;
    method Push(Value: X);
    method Pop: X;

    // These are the new "mixins":

    property IsEmpty: Boolean =>
        Count = 0;

    method Push(Values: IEnumerable[X]);
    begin
        for v in Values do Push(v)
    end

    method Clear;
    begin
        while Count > 0 do Pop
    end
end

It's some kind of funny that extension methods (that's what mixins are, at the end of the day), access sentinels and assertions are related by their implementations. For instance, pre and postconditions are implemented in Freya as extension methods. Class invariants' implementation, on the other hand, uses a similar approach as data sentinels to avoid firing in internal call boundaries.
I must acknowledge that most assertion implementations I know, beyond Eiffel, are shallow, incomplete or plainly wrong. Most of them don't handle inheritance and don't support assertion on interface types. Assertions in Freya addressed these problems, and Lyra will continue enhancing assertions support.
I have to complete the "Intellisense" compiler. This is a second (lighter) compiler that must take care of class navigation and code completion. I can't use the main compiler: it performs some code generation tasks very early in the compiling process.
Of course, Visual Studio integration is still an important item in the shopping list, just as CodeDOM support is.
Compiling must be moved to an isolated application domain, in order to avoid problems when unloading compiled assemblies.
Dynamic methods and "dynamic programming" support, you said? Huh, I hate the very concept! But you were kidding, weren't you?

Let me insist, anyway: Freya development hasn't been abandoned. As soon as Lyra moves to the next level, we'll update Freya in order to keep the pace.

Mean and lean

2008-09-07T14:11:00.012+02:00

Wouldn't be a good thing if you were allowed to define functions like these in C#?

public long fact(int n) =>
    n <= 1 ? 1 : n * fact(n - 1);

operator+(Complex c1, Complex c2) =>
    new Complex(c1.Re + c2.Re, c1.Im + c2.Im);

Actually, you are allowed even riskier tricks when dealing with inline lambdas. The uniformity principle states that, at least, some of these tricks should be accepted while defining regular functions. And that's what Freya does.

By the way, there are no omissions in the operator definition... by Freya standards, of course. Operators are always public and static, so why bother the user with stating this each and every time. On the other hand, the return type has been omitted: it can be statically deduced from the defining expression. Freya has precise rules for these static inferences: you can omit the return type when the expression is a constructor call, a typecast or, recursively, when it's a common expression block wrapping an expression with static inferable return type or a conditional with identical inferred types in both of its branches.

Jump!

2007-11-21T21:45:00.000+01:00

A fair share of the algorithms implemented by the peephole optimizer has to do with jump optimization. The compiler has already been carefully crafted to produce the best possible code before reaching this pass, but some optimizations may reintroduce small inefficiencies, that must be solved one way or another.

This is a summary of the tasks performed by our optimizer:

Chained jumps detection

A chained jump is a branch instruction that jumps into an unconditional branch. In some pathological cases, the chain may extend through several jumps. When the optimizer detects such a chain, it substitutes all intermediate targets by the target at the end of the chain. We must be careful in order to avoid circular jumps.

Jumps to return

An unconditional branch may land on a return operation code. Execution time is saved by substituting the original branch with a return.

Common branch suffixes

As already explained here, this is a space-saving optimization that detects repeated code at the end of converging executing paths. Since time is more important than space, this pass is executed after jump to return detection.

Unreachable code detection

Code is symbolically executed, marking all instructions reached by some execution path. Then, all non-marked instructions are deleted.

Trivial jumps removal

As a side effect of the previous pass, code is compacted and some trivial jump patterns may be introduced. For instance, we could have a jump to the immediately next instruction in the code stream, or a conditional branch skipping an unconditional branch, which could be substituted by a single inverted conditional branch.

Peephole optimization, properly speaking

Now we scan the instruction stream searching for some short code sequences that can be simplified. For instance, we look for consecutive assignments on the same field, leaving just the last assignment. Consecutive assignments may be generated by automatic transformations, such as the algorithm for generating iterators. If a local variable is written and then read, and if this is the only use of that local variable, we can drop both the read and the write operations. This seemingly silly pattern is frequently generated by for/in loops.

Tail recursion

Then, we look for recursive calls before a return operation code. When some security conditions are met, we scan back the code that pushes the parameters for that call, in order to modify the arguments in the current stack frame, and then we substitute the method call by a jump to the beginning of the method. We never use the tail prefix from the IL instruction set, since it's not efficiently implemented.

Branch operand size tuning

Our last pass assigns offsets for each surviving operations, and computes distances for each remaining jumps. Then, branch codes are changed into short jumps whenever possible. Full size jumps requires five bytes, while a short jump is codified in just two bytes.

Stating the obvious

2007-11-20T18:04:00.001+01:00

Should we always state the obvious? Interface types can only declare methods, properties and events (and assertions, since we're talking about Freya!). Fields, in any case, are not allowed inside an interface declaration.

Properties, however, are designed most of the times to resemble fields. Why should we stick to the property keyword when declaring properties for an interface type?

IScene = interface
   Sampler: ISampler; readonly;
   Camera: ICamera; readonly;
   Root: IShape; readonly;
   Lights: Array[ILight]; readonly;

   method Render: PixelMap;
   method Render(Row, Col: Integer): Pixel;
end

Of course, if you feel uneasy about dropping the keyword, you can still use it. Notice that there's no possible confusion, even with the declaration of Lights: that's a property returning an array, not an array property.

By the way, the above code fragment shows another omission: that of the final semicolon after the type declaration. Freya syntax has been relaxed to use optional semicolons in several places: after the end keyword in a complex type declaration and after the statement block in a method implementation. We're not going as far as Eiffel, where semicolons are optional almost everywhere, but our new syntax makes easier manual code translation from C# into Freya.

Common branch suffixes

2007-11-20T14:21:00.000+01:00

Another little enhancement has made its way into the Freya optimizer: common branch suffix detection. This technique detects repeated operation codes in code paths converging in a single point, and moves the branching instruction to take advantage of the common code. It's a trick for reducing code size without affecting its speed, at least, in a direct way. Of course, less code means faster JIT translation and better CPU cache performance.

Let's say we must generate code for this statement:

if condition then
   a.m(p₁, p₂, q)
else
   a.m(p₃, p₄, q)

The translation scheme would be as follows:

    EVAL(condition)
    br.false @@else
    EVAL(a)
    EVAL(p₁)
    EVAL(p₂)
    EVAL(q)
    callvirt m
    br @@continue
@@else:
    EVAL(a)
    EVAL(p₃)
    EVAL(p₄)
    EVAL(q)
    callvirt m
@@continue:

It's hard for the compiler to detect the common code in the Abstract Syntax Tree, so this is a task for our peephole optimizer. The optimizer kicks in after each unconditional jump, and scans backwards in parallel, from the branching point and the branch target. The above translation scheme is simplified this way:

    EVAL(condition)
    br.false @@else
    EVAL(a)
    EVAL(p₁)
    EVAL(p₂)
    br @@continue
@@else:
    EVAL(a)
    EVAL(p₃)
    EVAL(p₄)
@@continue:
    EVAL(q)
    callvirt m

In almost all situations, this change won't affect speed. There is, however, a case where we must be careful: suppose our conditional was the last statement in a method. In that case, the unconditional branch would jump into a return code, and the peephole optimizer would have substituted the jump with a direct return, saving the time consumed by the jump. To prevent this, common branch suffixes are always detected after the jump optimizer has finished its own duty.

About the impact of this optimization in real-world applications, please note that our example can't benefit from Freya's conditional expressions. What's more, the automatically generated code for iterators typically contains many assignments to the state field that can be factored out with our technique.

Ranges

2007-11-17T16:09:00.000+01:00

Range expressions may appear, in Freya, in three different contexts:

As case labels.
In for statements.
As the right operand of the in operator.

Of course, the original source was the case statement:

case expression of
    0, 3..20, 23: Console.WriteLine('Howdy');
    50..6000: Console.WriteLine('Silly');
end;

Please note that Freya, imitating C#, also supports case statements with string expressions, but in that case, ranges are not allowed, due to the underlying implementation, which depends on hash dictionaries. That's not a satisfactory situation. It could be acceptable for C#, where there're no ranges in its switch, but not for Freya. The solution, perhaps, could be the adoption of a new data structure for implementing ranges. But that's another story.

Membership

From the very first drafts, Freya featured an in operator, designed to work with collections. An expression like this:

x in A

is translated this way:

ICollection[T](A).Contains(x)

where T is the compiling time type of x. There's even a sort of "contains pattern", in the line of the "enumerable pattern", which allows any type with a suitable Contains method to be used as the right operand of the in operator.

We evaluated then several techniques for extending the in operator so it could act on ranges. The obvious technique was allowing ranges inside the brackets of array literals, imitating Pascal sets:

x in [1, 2, 5..10, 16]

After some tests, we discarded the idea. Implementing Pascalian bit sets was not an option: it would have required a core Freya assembly, and that's a scary idea. Another problem had to do with the places you could use an array literal with ranges inside. My intuition was crying aloud that the way was far from adding new data structures, like bitsets or extended enumerable interfaces.

Right now, I think ranges must exists as themselves in the language. The first hint came from the for statement. One day, I found myself writing loops like this:

for i in low .. high do
    Console.WriteLine(i);

Of course it is a cheap syntactic variant of the ascending numerical for, but there was another possible interpretation: the range expression was an iterator expression, i.e., a IEnumerable[T] expression. Why shouldn't we allow expressions like this?

if i in low..high and
   j not in low..high then ...

Each range check is translated as two comparisons. For instance:

// This expression...
x in e₁ .. e₂
// is translated as
x >= e₁ and x <= e₂
// and this one...
x + 1/x in e₁ .. e₂
// is translated as:
using temp := x + 1/x do
    temp >= e₁ and temp <= e₂

As a side effect, we now must allow in with an IEnumerable[T] right operand... expanding it as an inline search loop. But this variant is not implemented yet.

The existence test

There's an interesting and natural variant of the membership test:

if * in collection then
    // The collection is not empty.

You can also use the negated variant:

if * not in collection then
    // The collection is not empty.

In two of the possible cases, the implementation is trivial. For instance, if the existence test is applied to a range, you have a simple comparison involving the boundaries:

// This expression...
* in e₁ .. e₂
// is translated as
e₁ <= e₂

When the right side implements the IList[X] generic interface, the test is based on the Count property:

// This expression...
* in list
// is translated as
list.Count > 0

However, there's a case where the existence test is really useful. The right operand may only implement the so called enumeration pattern, as in the foreach statement, or one of the IEnumerable interfaces. Let's say the right operand implements IEnumerable[X]:

// This expression...
* in enumerable
// is translated as this expression:
using e := enumerable.GetEnumerator do
    e.MoveNext

Please note, first, that we have here a using expression, not a statement. Second: we need a using expression because the value returned by GetEnumerator may implement IDisposable. In that case, we need a resource protection block to dispose the enumerator after the test. Actually, our new existence test is saving you from writing a for/in statement:

var result := false;
for v in enumerable
begin
    result := true;
    break
end;

Elisions

2007-08-22T21:46:00.000+02:00

Less typing means faster programming, and simple syntactic changes can save a lot of keystrokes. The newest Freya syntax allows you to drop the do and then keywords when they precede a statement starting with another keyword.

In this fragment, both the for and the while statements have dropped their do's:

method GetPrimes(Max: Integer): BitsArray;
begin
    Result := new BitsArray(2, Max);
    for i in 2..Max div 2 : not Result[i]
    begin
        var j := i + i;
        while j <= Max
        begin
            Result[j] := true;
            j += i;
        end;
    end;
    Result.Invert;
end;

Note that we have also dropped the for var combination that used to mark local variable type inference in previous versions.

There is another interesting detail in the above code:

    for i in 2..Max div 2 : not Result[i]

First, there's a seemingly innocent variation of the classical for/to numerical loop: we have disguised it as if we were iterating over a numerical range. We still cannot eliminate the classical statement, since this "iterator" does not substitute the downto loop.

However, the real purpose of this change has to do with the Boolean expression after the semicolon. It acts as a filter, and it can be used both with virtual numerical ranges and with real iterators.

At the end, an iterating filter translate as a nested if statement... but you have saved some typing, and your code is a little more expressive, since you don't have to look for a matching else before understanding the purpose of that nested if.

Be constructive

2007-07-08T02:37:00.000+02:00

We have already seen how useful can be expression based method implementations. Is there anything similar for constructors? Constructors have no return value, so they cannot directly benefit from expression based implementations... but it turns out there's a surprisingly similar feature at our reach.

In a sense, a constructor can be viewed as a static function (a method returning some value). The returned value is, of course, a new instance from the class the constructor belongs. In any case, there are a couple of constraints for constructors that regular methods have not: the return type must always be the same, inside a given class, and the returned instance must always be a new instance.

Note: It could make sense to remove the latter restriction. It's an important part of the contract for languages with explicit memory deallocation. Now think how you must implement an instance cache for a given class: since you cannot overload the new operator as in classic C++, you must search all creation expressions along the whole application to substitute them with method calls.

Given the previous constraints, and the fact that constructor calls are functional calls, we can find the equivalent to expression-based implementations: chained calls to sibling or parent constructors... a feature that was there all the time:

Stack = class[X]
private
    Items: Array[X];
    Count: Integer;
public
    constructor(Capacity: Integer);
    begin
        Items := new Array[X](Capacity);
    end;

    constructor : Self(128);

    // ...
end;

It's true it looks so different from regular expression-based implementations, but it's a historical consequence: chaining has been available in C++ from long time ago. The only novelty is that you can omit the whole method block from that point on.

It's recommendable to write always this kind of "bodiless" chaining in the class declaration, instead of using an implementation section. Neither C# nor Freya supports default parameter values, so it's very frequent to find a handful of constructors in a given type, each of them removing some parameters from the signature's tail. We can use chaining to implement all of them, except the first:

Metal = sealed class(IMaterial)
public
    constructor(Color: Pixel;
        MinRefl, MaxRefl, Diffuse: Double;
        PhongAmount, PhongSize: Double);

    constructor(Color: Pixel;
        MinRefl, MaxRefl, Diffuse: Double) :
        Self(Color, MinRefl, MaxRefl, Diffuse, 0, 1);
    constructor(Color: Pixel;
        MinRefl, MaxRefl: Double) :
        Self(Color, MinRefl, MaxRefl, 1, 0, 1);
    constructor(Color: Pixel; MinRefl: Double) :
        Self(Color, MinRefl, 1, 1, 0, 1);
    constructor(Color: Pixel) :
        Self(Color, 0.1, 1, 1, 0, 1);
end;

There's a second related question: is there any similar feature for iterators? I have an affirmative answer, but the syntactic details still need some boiling...

Though it's not an official Freya feature, it could also make sense to bring back another old C++ feature: field initialization in constructors. We could have written the previously shown Stack constructors like this:

// This is not Freya... yet...
constructor(Capacity: Integer)
    : Items(new Array[X](Capacity));
constructor
    : Self(128);

Of course, this enhances the expressivity of chaining, but that's not the main point. The main reason to bring this feature back has to do with programming by contract: this kind of field initialization may be necessary for implementing not nullable reference types, as in Spec#.

Notepad Oriented Programming

2007-07-07T12:13:00.000+02:00

One of the shameless goals of Freya is to become a Notepad Oriented Programming Language: you must be able to write Freya applications with the Notepad and little more (Reflector, perhaps?). But that's a pretty hard goal when you're designing a language inspired by the Algol/Pascal lineage. It's not only that you must use those begin/end blocks instead of curly braces. If you must keep method declarations apart from their implementations, as in Delphi, then you'll have to type a lot... or lean on an editor that replicates the missing implementations by user request.

I think we have achieved the above stated goal. Right now, you can write Freya code that looks as compact and easy as C# code, and in some circumstances, the Freya variant may be even shorter than the C# equivalent. To illustrate this, let's take a look at C# and Freya operators. Let's say we're writing a Complex class in C#. Here you have two user defined operators on that class:

// C#
public static Complex operator+(Complex c1, Complex c2)
{
    return new Complex(c1.Re + c2.Re, c1.Im + c2.Im);
}

public static Complex operator-(Complex c1, Complex c2)
{
    return new Complex(c1.Re - c2.Re, c1.Im - c2.Im);
}

In a first attempt, those two operators would be translated to Freya this way:

public
    static operator+(c1, c2: Complex): Complex;
    begin
        Result := new Complex(
            c1.Re + c2.Re, c1.Im + c2.Im);
    end;

    static operator-(c1, c2: Complex): Complex;
    begin
        Result := new Complex(
            c1.Re - c2.Re, c1.Im - c2.Im);
    end;

There's nothing to be especially proud of in the above example: our fragment is longer in Freya than in C#. It's true that we have spared ourselves from some Delphi.NET eccentricities. For instance, we have written inline implementations, avoiding those nasty duplications imposed by the interface/implementation artificial split. We have also saved something in constructor calls: we use new as in C#, instead of calling some named constructor, as Delphi requires. It has nothing to do with saving two or three characters in each call (we're loosing that tiny advantage by using static instead of class, as in Delphi), but our syntax makes easier to translate existing code from C# to Freya. Last, but no least, we can use symbolic names for the operators, instead of Add and Subtract, as in Delphi or Chrome.

Expression based implementations will let us simplify the above listing:

public
    operator+(c1, c2: Complex): Complex =>
        new Complex(c1.Re + c2.Re, c1.Im + c2.Im);

    operator-(c1, c2: Complex): Complex =>
        new Complex(c1.Re - c2.Re, c1.Im - c2.Im);

We have deleted both begin/end blocks, and both assignations to Result. Since operators are always public and static in .NET, we have also dropped the static modifier. We now have code comparable to C# in length, and maybe even shorter. But we can keep shortening our example:

public
    operator+(c1, c2: Complex) => new Complex(
        c1.Re + c2.Re, c1.Im + c2.Im);

    operator-(c1, c2: Complex) => new Complex(
        c1.Re - c2.Re, c1.Im - c2.Im);

We are showing the last addition to Freya: return type inference for expression-based implementations. This is not a full featured type inference, as in functional languages or a modern language as Nemerle. The Freya compiler only allows the omission of the return type when it finds an expression based implementation, and when the implementing expression is an instantiation expression. We think that complex inferences are not a good thing, at least with a language as Freya, so we have added some inference... up to a sensible point.

We can use return type inference in yet another case, as this example shows:

operator/(c1, c2: Complex) =>
    using r2 := c2.Re.Sqr + c2.Im.Sqr do
        new Complex(
            (+c1.Re * c2.Re + c1.Im * c2.Im) / r2,
            (-c1.Re * c2.Im - c1.Im * c2.Re) / r2);

In this case, we have a common expression block containing a new expression, so we can safely deduce the return type before resolving the whole expression.

Of course, you won't be forced to write code in this style: if you want your code to look like good old Pascal, you still can write it that way... and I'm not being sarcastic. There's an important problem with compact code: how you get there. When you write programs by assembling small pieces into bigger ones, the result will contain extra code and glue that you probably won't need. The most frequent reason has to do with the fact that modular code, as you store it in your mental pattern library, must deal with a yet unknown context, so it probably has extra checks for handling extreme cases and such. When you adapt those code pieces for a given task, some special cases render improbable, and the corresponding guarding code can be deleted.

A second source of redundant coding is gluing. How do you compute the square root of the Zipperstein-Marmaduke Formula? First, you must evaluate the ZMF and then you'll have to find that pesky square root. In your first attempt, it's highly probable that the ZMF return value was stored in a local variable. There are two possibilities about the final code: either you can keep a separate line for dealing with ZMF, just to keeping what your code does, or you can merge both computations in a single expression. It's up to you to decide.

The consequence: compact code may be easier to read than to write... as the failure of functional programming languages to gain enough users has shown. Freya doesn't require you to write the shortest possible code, but that's still an option you have once you master the language.

... by the way, now we can write the Ray class as follows:

Ray = sealed class
public
    Origin, Direction: Vector;

    property Items[Time: Double] => new Vector(
        Origin.X + Time * Direction.X,
        Origin.Y + Time * Direction.Y,
        Origin.Z + Time * Direction.Z);
end;

It is more blessed to yield than to return

2007-06-07T15:51:00.000+02:00

Yield statements in Freya must be associated with expressions with the same type as the return value from the iterator:

BinaryTree[X].TreeNode = class
public
    property Value: X;
    property Left, Right: TreeNode;

    iterator InOrder: X;
    begin
        if Left <> nil then
            for var v in Left.InOrder do
                yield v;
        yield Value;
        if Right <> nil then
            for var v in Right.InOrder do
                yield v;
    end;

    // ...
end;

Since InOrder returns an X in each step, each yield expression must also belong to this type. Let's see what happens if we allow attaching an IEnumerable[X] to yield:

BinaryTree[X].TreeNode = class
public
    property Value: X;
    property Left, Right: TreeNode;

    iterator InOrder: X;
    begin
        if Left <> nil then
            yield Left.InOrder;
        yield Value;
        if Right <> nil then
            yield Right.InOrder;
    end;

    // ...
end;

I think it's easy to tell both uses of yield. When the yield expression has type IEnumerable[X], instead of X, the compiler translates the statement into a for/in loop, saving the programmer a lot of keystrokes.

Finally, let's take a second look on the code that dropped from the iterator:

for var v in Right.InOrder do
    yield v;

It's easy to see that the compiler can generate better code for this special kind of loops: there's no need to allocate a explicit variable to hold the value returned by the (nested) iterator in each step. In other words, the above fragment can be translated like this (ignoring the final call to Dispose):

var en := Right.InOrder.GetEnumerator;
while en.MoveNext do
    yield en.Current;

Our compiler now detects this case and generates efficient code for it. You should realize that, though the loop variable v looks like a local variable, it is implemented via fields, since the code is part of an iterator.

A whiter shade of a functional flavor

2007-06-01T09:43:00.000+02:00

Take a look at this example:

// Yes, this is still Freya!
method Factorial(n: Integer): LongInt =>
    if n <= 1 then 1 else n * Factorial(n - 1);

There are two new features in those three lines. The first one is inline implementation of executable members via expressions. The second one is the conditional expression. The former leads to the latter, so that's the order I will follow for explaining it.

First of all, why do we need inline implementation? Freya started as a Delphi/Pascal mutation, and adopted the splitting style: you must group your declarations in one place, and all executable code is written in a different section of the same file. This approach has its pros and cons. It's easy to extract a "contract form" from the source, without sophisticated edition tools. Bad news has to do with projects featuring a lot of small classes: the syntactic overhead may be greater than the real code. The following Ray class is a good example:

public

    Ray = sealed class
    public
        Origin, Direction: Vector;
        property Items[Time: Double]: Vector;
    end;

implementation for Ray is

    property Items(Time: Double): Vector;
    begin
        Result.X := Origin.X + Time * Direction.X;
        Result.Y := Origin.Y + Time * Direction.Y;
        Result.Z := Origin.Z + Time * Direction.Z;
    end;

end;

A first step could be moving the implementation part inside the own Ray class. Gains are small, however:

Ray = sealed class
public
    Origin, Direction: Vector;
    property Items[Time: Double]: Vector;

implementation

    property Items(Time: Double): Vector;
    begin
        Result.X := Origin.X + Time * Direction.X;
        Result.Y := Origin.Y + Time * Direction.Y;
        Result.Z := Origin.Z + Time * Direction.Z;
    end;

end;

This still looks more Delphic than Eiffel-like. And I must confess I love Eiffel. So, we can reunite the Items implementation with its declaration:

Ray = sealed class
public
    Origin, Direction: Vector;

    property Items[Time: Double]: Vector;
    begin
        Result.X := Origin.X + Time * Direction.X;
        Result.Y := Origin.Y + Time * Direction.Y;
        Result.Z := Origin.Z + Time * Direction.Z;
    end;

end;

This explains the inline implementation bit. Now take a look at this record:

Vector = record
public
    property X, Y, Z: Double;

    property Length: Double;
    begin
        Result := (X.Sqr + Y.Sqr + Z.Sqr).Sqrt;
    end;

end.

X, Y and Z are field-based properties, since they have no explicit implementations. Our vector type features another read-only property, Length, which we have already implemented inline. The getter body is very simple: a single statement, actually a return statement. Déjà vu, anyone?

... yes, this is a situation we will find again when dealing with anonymous methods. C# 2 introduced anonymous methods, but the syntax was too heavy for simple methods like our get_Length. For this reason, C# 3 introduced lambda expressions: a simplified syntax for writing anonymous methods with only a return statement in their bodies. Of course, C# 3's lambdas has more interesting features than merely this syntactic trick (more powerful type inference, for instance).

C# has a Spartan syntax, but Pascal heirs are a lot more verbose, so this simplification is even more important for us. Now ask yourself, why limit the benefits of the lambda style to writing anonymous methods:

Vector = record
public
    property X, Y, Z: Double;

    property Length: Double =>
        (X.Sqr + Y.Sqr + Z.Sqr).Sqrt;
end.

We have "shaven" all the begin/end unnecesary junk, and the assumed assignment to Result. The final code is a lot more readable and less error prone. Now you know what does "expression-based inline implementation" meant.

There remains a question: why did we add such a filthy nasty feature such as a stinky conditional expression inspired by C? In my defense, please note that our conditional expression smells more like Haskell or Miranda than good old C. There's also a good hidden signal: the LALR generator did not complain for the duplicated use of if/then/else. Chances to confuse the expression and the statement are, thus, minimal. But the main reason is power: once we have single expression lambdas, we want to make this feature as powerful as possible. Thanks to this, we have been able to reduce Factorial's implementation to a single inlined expression, as already shown.

Of course, there are more things that we could do for enhancing expressions. This method returns a "normalized" copy of a vector:

method Normalized: Vector;
begin
    var L := Self.Length;
    Result := if L = 0
        then Self
        else new Vector(X / L, Y / L, Z / L);
end;

We are already using a conditional expression, but that's not enough to reduce this simple implementation to a single expression. What we need are "real" lambdas: I mean, inline anonymous functions... wait... that's what C# 3 now provides, isn't it? Not exactly: now we can embed lambdas inside the "imperative" side of C#, but not inside its brand-new, functional-like personality. I want something like this (provisional syntax):

method Normalized: Vector =>
    if L = 0 then Self
    else new Vector(X / L, Y / L, Z / L)
    where L := Self.Length;

Why do I have used now an assignment instead of the => keyword? To make short a long story: an assignment means a single evaluation, no matter how many times the defined symbol is used. On the contrary, => means substituting the symbol with its definition each time. This is not a concern for a functional programming language, since they have, or they shouldn't have any side effects. See this:

static I: Double;

property A: Double = I + 1;
property B: Double => I + 1;

A is a field based property (a read/write one, by the way), and the underlying field is initialized as I + 1 when an instance of the declaring class is created. On the other hand, B is a read only, inline implemented property. Each time you read from B, the expression I + 1 is reevaluated. Something similar happens with interface delegations:

MyClass = class(IEnumerable)
    // ...
implementation
    interface IEnumerable = GetArray();
end.

For the above class, the compiler creates a hidden IEnumerable field, and initializes it with the value return by the call to GetArray. This is an alternative:

MyClass = class(IEnumerable)
    // ...
implementation
    interface IEnumerable is GetArray();
end.

Each time we apply a method from IEnumerable on a MyClass instance, GetArray is reevaluated, and the method call is redirected to the value returned by GetArray.

Extension methods in Freya

2007-02-18T20:10:00.000+01:00

I'm working right now on extension methods for Freya. These methods must be declared as part of static classes, with a special syntax:

public
    MathTools = static class
    public
        method Abs: Double for Self: Double;
    end

This is a (trivial) implementation for Abs:

implementation for MathTools is

    method Abs: Double for Self: Double;
    begin
        Result := Math.Abs(Self);
    end;

end;

The above declaration is translated like this:

public
    MathTools = static class
    publi
        method Abs(Self: Double): Double;
    end

implementation for MathTools is

    method Abs(Self: Double): Double;
    begin
        Result := Math.Abs(Self);
    end;

end;

There's no mistery: the bizarre "with Self" parameter has been moved to the head of the parameter list. In our example, our parameter list was initially empty, but that's an accident, not a requirement.

Let's see now how we would use the extension method:

var
    d: Double;
begin
    d := -1.0;
    Console.WriteLine(d.Abs);
end;

It looks like the Double class had defined an Abs instance method from the first time. However, we both know that Abs was defined later, in an extension class. Of course, you can also use MathTools.Abs as a static method:

var
    d: Double;
begin
    d := -1.0;
    Console.WriteLine(MathTools.Abs(d));
end;

This feature has a relatively long history. As far as I know, it appeared in Delphi 8, mainly as a way to add "predefined" methods to the Object base class. I didn't like the new feature. Then, it has reappeared in the C# 3.0 draft, probably as a syntatic sugar for some LINQ features. I still dislike extension methods.

There're still some loosing ends. The C# 3.0 draft suggests that extension classes are automatically registered via using clauses. I suppose there will be some kind of attribute mark at class level for telling appart extension classes from regular classes, in order to avoid full member reading in the compiler at initialization time.

Field-based properties

2007-02-13T21:28:00.000+01:00

Freya already supports field-based properties. If you declare a property, but you don't provide an implementation, the compiler adds automatically a hidden field and implements the property using the new field. Even if the property is declared as read only, you can assign values to the hidden field using the property name, as long as your code is located inside the declaring class or inside another class nested in the declaring class.

I was declaring the hidden field as private, but I have realized that it's better to declare it as an internal field, so any class compiled inside the same assembly could access the field instead of the property. Of course, if the property is read only, any other class still can not write on the field. Another constraint has to do with virtual properties: if the property is declared as virtual, it's not safe to reference the field instead of the property.

Predefined extensions

2007-01-23T17:19:00.000+01:00

Freya will have to implement something like C# 3.0's extension methods. I'm not an extension method's fan, and some details still wait for a decision. Meanwhile, we have added some predefined extension methods to the predefined double type, so you can write this:

property Length: Double;
begin
    Result := (x.Sqr + y.Sqr + z.Sqr).Sqrt;
end;

Every method defined in the static System.Math class can be used as an instance method on any System.Double instance. On the other hand, there's no Math.Sqr method at all: it's just an intrinsic method, requiring some compiler magic. Another "intrinsic" method extension: the Ord method applied to a Char expression.

Another addition to the compiler: a "peephole" optimizer. This is an optimizer that works on a IL representation. Right now, the optimizer choose between short and long branch codes, eliminates jumps in cascade, remove some useless data writes (most of them induced by the Result variable) and detects unreachable code.

Collection initializers

2007-01-05T22:29:00.000+01:00

Freya have another new feature borrowed from C# 3.0: collection initializers.

var L := new List[Integer]![1, 2, 3, 4];

As you can see, an array literal can be appended to the creation of any class implementing the generic ICollection[T] interface type. But, this time, the array literal doesn't generates an array at runtime. Instead, for each item in the literal, a call to the method Add, from the collection, is generated.

In order to realize why we need collection initializers, you must weight the alternative method:

var L := new List[Integer]([1, 2, 3, 4]);

In this case, the array literal is passed as a parameter to the constructor call. However, the parameter is declared as IEnumerable[T]. Can you see what it means? A temporal array must be generated and initialized, item by item. Then, the array must be casted as a IEnumerable[T] reference, which will be passed to the constructor. Inside the constructor, GetEnumerator is called, and a second temporal object is created. Finally, a loop is performed, in order to add an item for each enumerated item.

Indexers

2006-03-28T20:35:00.000+02:00

I had postponed any decision on Freya indexers until I could find a better model for representing name overloading in the symbol table. The original data structure was borrowed from Blue, and it was based in a clever trick: each context table contained a "group symbol" entry, which associated a name like WriteLine to the list of overloaded methods. At the same time, each of these methods was included independently. Since the context table is a kind of hash dictionary, method names were "decorated" or mangled, adding information from the parameter types.

I started with a version of Blue without indexers, and that's the reason why the symbol table only considered overloading for methods, but not for properties. There was another problem with explicit and implicit user defined conversions. The raw op_Implicit and op_Explicit methods violate one important rule in Freya and C#: they cannot be distinguished by the parameters signature! Suppose you write this in C#:

public static operator explicit double(Complex);
public static operator explicit float(Complex);

They translate to something like this:

public static double op_Explicit(Complex);
public static float op_Explicit(Complex);

Both methods have identical parameter lists, and they only differ in their return types. Of course, this is forbidden in C# and Freya... but is supported by the CLR. But the decorated parameter trick was inappropiate for representing this situation.

I have solved the problem by only including the group name for user defined conversions and indexers. Probably, there's no reason for including decorated method names in the hash table, but I won't mess right now with such a far reaching change in the compiler.

Finally, Freya has full functional indexers, following Visual Basic.NET. The reason:

The VB model is the most general.
Surprisingly, you can access secondary indexers from a C# application.
So far, I haven't discovered any important drawback in the VB model.

I have also added lifted operators to Freya: these are automatic extensions for predefined and user operators for dealing with nullable types, and they imitate the behavior of SQL operators when they act on null values.

Operating with operators

2006-03-07T18:17:00.000+01:00

Let's do a quick review of operators in Freya. Operators must be declared, as usual, in public static sections:

static public
    method+(c1, c2: Complex): Complex;
    operator-(c1, c2: Complex): Complex;

As you see, method and operator are equivalent when defining a "symbolic" operator. No syntax ambiguity arises in these cases, and the method keyword is friendlier, in my humble opinion.

However, operator is required when the operator name is a keyword or an identifier:

    operator True(c: Complex): Boolean;

Technically, True is an operator in Freya, following C#. We cannot proceed as in Pascal and consider True an enumerative constant, since in that case, both Freya and C# would require the class name as qualifier: Boolean.True.

Even when the operator name is a keyword, there's no syntactic ambiguity. The real reason for keeping the operator keyword is this:

    operator Explicit(c: Complex): Double;
    operator Implicit(d: Double): Complex;

Though both explicit and implicit are C# keywords, they are not keywords in Freya. We could have allowed this:

   method Explicit(c: Complex): Double;

But I thought it would be dangerous, since you cannot tell whether the programmer intention was declaring a full featured operator or a regular method called Explicit.

Operator implementation is straightforward, as usual:

implementation for Complex is

    operator Implicit(d: Double): Complex;
    begin
        Result := new Complex(d, 0.0);
    end;

More on interface delegations

2006-01-15T22:46:00.000+01:00

As I explained here, Freya allows the programmer to implement an interface type by delegating the implementation of methods from the interface to an instance of an already existing implementation. This trick is borrowed from Delphi, and it's an effective and easy technique for reusing interface implementations. Then, I used this example:

// WARNING: THE SYNTAX HAS CHANGED!!!
public

  Foo = class(IEnumerable)
  end;

implementation for Foo is

  // A private instance field.
  var Items: array of String := ['Freya', 'rules'];

  // Just an implementation detail!
  interface IEnumerable is Items;

end.

Our Foo class must implement the IEnumerable interface type, and it does it by delegating the implementation to a string array; all array types implement that interface, don't they? The delegation member contains a mention to the private field Items... but our real interest is the value stored in that field and, since our field is already initialized, it's highly probable that Items won't be referenced from other methods in this class. Why, then, should we need to declare Items at all?

This is a new alternative technique for delegating interface implementation:

implementation for Foo is

  interface IEnumerable := ['Freya', 'rules!'];

end.

Now we can merge all what we need for the delegation in a single clause! Just think in all that can be done with this new feature. We have used a string list in our example, but it will be more common to find a regular constructor call as initializer:

implementation for Foo is

  interface IEnumerator := new DriveEnumerator;

end.

In short, now we have two kinds of delegation clauses. One of them refers to a field or property in the same class. In this case, you can initialize the field or property in a constructor, or using a field or property initializer. The second and shorter form assigns directly a value in the delegation clause using an initializer. In this case, the compiler declares a hidden field inside the class and takes care of its initialization.

Enhancing code quality

2006-01-13T18:00:00.000+01:00

It's an open question whether a compiler writer targeting the CLR should waste some time optimizing generated code. After all, the JIT compiler in .NET 2.0 is almost a miracle of software engineering. In any case, I think it pays, at least when we talk about very simple optimizations with an immediate impact in code.

If you're compiling a Pascal-like language as Freya, function result assignment may introduce extra bytes in the code stream. Consider this simple access method:

// From a generic stack implementation.
property Top: X;
begin
  Result := Items[Count - 1];
end;

This was the output from the initial compiler implementation, as reported by Reflector:

  // Code size: 22 bytes
  .maxstack 3
  .locals init(!0 local1)
  ldarg.0
  ldfld !0[] Stack`1::Items
  ldarg.0
  ldfld int32 Stack`::Count
  ldc.i4.1
  sub
  ldelem.any !0
  stloc.0
  ldloc.0
  ret

What's that local1 local variable? That's simply a direct and naive implementation of the old and good Result! As you can see, there's a silly store/load code sequence at the end of the method.

I've just added to the Freya compiler a very simple and fast algorithm to detect proper function returns, in true C/C# fashion. Now, the compiler generates this code for the same Freya method:

  // Code size: 20 bytes
  .maxstack 3
  ldarg.0
  ldfld !0[] Stack`1::Items
  ldarg.0
  ldfld int32 Stack`::Count
  ldc.i4.1
  sub
  ldelem.any !0
  ret

There's no need now for a local variable, and the code stream is two bytes shorter. How will this affect the JIT output? Well, it's highly probable that the JIT compiler would have detected the redundant sequence in the first example and removed it. However, with the new compiled code, the JIT compiler has less work to perform and the application will load faster. You should note that our algorithm is able to detect the return pattern in code like this:

method Silly(Value: Integer): String;
begin
  Console.WriteLine(Value);
  case Value of
    v1..v2: Result := 'Whatever';
    v3: Result := 'Oops';
    v150..v300:
      if Value = 200 then
        Result := 'Yikes'
      else
        Result := 'Uh-oh';
  else
    Result := 'That''s all...'
  end
end;

Let's see another simple and useful optimization. How would you translate this?

if Value <> 0 then
  DoSomething;

My initial implementation would have missed the fact we are comparing for equality with the zero constant, and would have generated something like this:

  // Load Value...
  ldc.i4.0
  beq @@1
  // DoSomething...
@@1:

Actually, this is a lot better, and it's just what we're doing now:

  // Load Value...
  brtrue @@1
  // DoSomething...
@@1:

Despite the fact that the CLR offers a "decent" type for Boolean, IL code still allows you to use a non null constant as an equivalent of true. In this case, we're saving just a byte. But remember: the shorter code, the faster it loads...

Debugging Freya applications

2006-01-07T18:46:00.000+01:00

I have just added PDB file generation to the Freya compiler, to support debugging. Piece of cake! It has been extremely easy… so far.

Mark the dynamic assembly with DebuggableAttribute, passing both the DisableOptimizations and Default constants to the attribute constructor.
Create the dynamic module as "debuggable", passing true as the last parameter for AssemblyBuilder.DefineDynamicModule.
Associate an ISymbolDocumentWriter to each source file in the project. Use the DefineDocument method from MethodBuilder for this task.
Since every node in the Abstract Syntax Tree has a SourceRange field pointing to its source file, each AST node, including statement nodes, may access their corresponding ISymbolDocumentWriter instance.
Code generation for statements is achieved by calling the Generate virtual method defined at the root AstStatement class. I just inserted a call to ILGenerator.MarkSequencePoint at the very beginning of the base Generate method. This Reflection.Emit method requires an ISymbolDocumentWriter as its first parameter, and a range inside the source file... and both things can be extracted from the SourceRange stored at the node.
Additionally, local variables declared by the programmed must apply the SetLocalSymInfo method to their local variable builders, since IL code does not contain metadata about the names of local variables.

This is all what you need to load a Freya source file in Microsoft's CLR Debugger, as shown in this image:

You can find more information on this topic at Mike Stall's .NET Debugging blog. Of course, this is just a first step towards integrating the compiler in the Visual Studio 2005 IDE.

Object initializers

2006-01-02T15:51:00.000+01:00

Take a look at this code:

// C# 3.0
var a = new Point { X = 0, Y = 1 };

This fragment has been copied from the C# 3.0 specification preview. According to that document, the above instruction should be interpreted as:

// C# 3.0
var a = new Point();
a.X = 0;
a.Y = 1;

So, we have a "normal" instance construction followed by property or field assignments. Does this remind you any other existing C# feature? Sure, that's how custom attributes are instantiated. Custom attributes mix positional parameters corresponding to constructor parameters, and named parameters, which must be translated as post-construction assignments. We could extend the syntax from custom attributes to object creation:

// A proposal
var a = new Point(X = 0, Y = 1);

Of course: I know object initializers were proposed for C# 3.0 as part of the support for anonymous types. In C# 3.o, you could drop the "constructor part" like this:

// Anonymous types in C# 3.0
var p1 = new {
    Name = "Lawnmower", Price = 495.00 };

But then, why not this?

// Anonymous types in C# 3.0: a proposal
var p1 = new(
    Name = "Lawnmower", Price = 495.00 );

Is this a good idea? I still have to check the 3.0 proposal, to see whether there is any other reason to prefer the curly braces initializers (nested initializers, for instance). In any case, I think it's better for Freya to adopt the "custom attribute initialization syntax" for object initializers: the literal translation of C#'s curly braces would be a begin/end pair. So, we could initialize a Point object in Freya this way:

// A proposal for Freya 1.0
var p := new Point(X := 0, Y :=0);
var tb := new DataTable(
  'Customers', CaseSensitive := true);

How do you like it?

It works!

2005-12-17T00:32:00.000+01:00

I've just connected the code required for generating generic type definitions in the Freya compiler... and it works fine! Freya has been consuming imported generic types for a while, but now we can also compile our own generic type definitions.

Using a statement

2005-12-14T16:06:00.000+01:00

Does StringBuilder implements IDisposable? No, it doesn't. And, what about SqlDataReader? Can you remember which classes implement a given interface? Is there any simple way to find it without interrupting your workflow to check the inline help? Then, why does using fails to compile when the instance type doesn't implement that interface?

In Freya, this is no longer a requirement. When the instance type in a using statement does not implement IDisposable, the compiler does not complain, but no finalization is generated for the statement:

using var sb := new StringBuilder do
begin
    sb.Append(month);
    sb.Append('/');
    sb.Append(day);
    sb.Append('/');
    sb.Append(year);
    Console.WriteLine(sb);
end;

Another new experimental feature is shown in the previous example: inline variable declaration, in true C# 3.0 fashion. Actually, this kind of simple type inference was already present in Freya. What's new is the presence of var to make clear we are introducing a (block scoped) local variable.

for var i := 0 to list.Count - 1 do
    // See note below...
    with var item := list[i] do
    begin
        Console.Write(item);
        Console.Write(': ');
        Console.WriteLine(integer(item));
    end;

Without var, it would be hard to tell whether we are using an already declared control variable, or just asking for a new local control variable in statements like this:

// See note below...
for i := low to high do ...

Have you noticed the change in the with statement? We have sacrificed the old semantics of the traditional Pascalian with. Now, this statement is used to introduce new local variables and an associated scope for them, but there's no assumed prefix as in Pascal and Delphi.

Updated:The with statement has been dropped from Freya, since it could be substituted by our "extended" using statement. However, we had to make another change in the semantics of using: value type variables declared at the header are no longer read only. That's not a great deal, since IDisposable is almost always implemented by classes instead of records. Finally, Freya, as C#, requires a dedicated variable in for statement. You cannot "recycle" anymore an already existing local, as in Delphi.

And this is another example of type inference for local variables:

for var color in [Colors.White, Colors.Blue] do
    if color in [Colors.Red, Colors.Blue] then
    begin
        Console.WriteLine('Match!');
        Break;
    end;

Brackets are used to construct arrays, and the in operator in the conditional statement translates as a call to ICollection<>.Contains, in the most general case. In this simple example, the compiler optimizes the check and inlines the expression.

Forced typecasts

2005-11-08T12:13:00.000+01:00

The design of the typecasting operators for Freya has been troublesome:

Delphi uses the as operator as a "forced typecast": it checks first whether the conversion is possible, and when it's not, it throws an exception.
The other typecast operation is an unchecked conversion (actually, it's a compile time cast): just do what I say, even when it's plainly wrong. Syntactically, you must use the type name as a monoparametric function.
There's no "atomic" tentative typecast in Delphi. To simulate it, test the source type using the is operator, and if the answer is affirmative, proceed with the compile time typecast.

On the contrary, this is what happens in C#:

Tentative casting is implemented by the as operator.
The widely known compile-time typecast inherited from C, is now the "forced" typecast operator.
There's also an is operator in C#, but there is no compile-time, unchecked typecast.

I felt inclined from the first time to use as as in C#, but I was worried about the confusion this could cause in a Delphi programmer. And then, how should I implement the functional style typecast?

Our final design resembles the design decisions in C#:

Tentative casting in Freya is implemented by the as operator.
The functional style typecast means a forced typecast in Freya: if the conversion is not possible, it throws an exception.
Of course, we keep the meaning of the is operator.

Let's see some code:

var
   o: Object;
   b: Button;
begin
   o := new Label;
   // A tentative typecast.
   // A nil reference is stored.
   b := o as Button;
   // A forced typecast.
   // An exception is raised.
   b := Button(o);
end;

Of course, I'm writing this after implementing the support for this operations in the Freya compiler.

There's a time and a place...

2005-07-13T00:54:00.000+02:00

I've been lazy for a while. Actually, I've been working in a new book on ASP.NET v2.0 and some courses. Anyway, I haven't found enough time for Freya, but I'm back...

We have a new "logo" for Freya! Nothing to be proud of, but we have finally a logo. The capital F has been drawn with the French Script font. It has been sheared, rotated and bevelled using Xara X1 (heartily recommended!). There's a full update of the Freya's home on the way, and it should be ready by the end of this week.

I still have to move the compiler source to the Visual Studio beta 2; right now, it compiles with the Visual C# Express beta 2. Next, I will implement the code to enforce accessibility levels. That's a funny feature of the CLR: even if your compiler doesn't check your access rights regarding a class member, the runtime will detect the violation and will signal it as a runtime error. There's no way for cheating encapsulation in the framework.

The Merging Pot

2005-05-15T15:55:00.000+02:00

Since Freya is a split language, the compiler must merge different parts of the source code. We have a handful of syntactic structures that require merging:

First, each class declaration must find its corresponding implementation section. Both parts should be located in the same source file.
Each event, property and method must match its implementation.
Methods, events and properties from the implementation that don’t match with a declared class member, are added as private members of the class.
Finally, there are features that always belong to the implementation section: class constructors, and interface delegations.

Easy? Well, not at all. Suppose we have this declaration:

method WhatEver(I: Integer): String;

Does this method match with the following implementation?

method WhatEver(I: System.Int32): System.String;
begin
    ...
end;

Now you can see the problem: a type reference may omit the namespace thanks to a using clause, and several primitive types have synonyms. That’s the reason why we can’t merge method implementations when we match a class with its implementation section. We must register namespaces and types, both from the referenced assemblies and user declarations.

Please note that we face a similar challenge when identifying a class implementation section. This is the easiest case:

namespace Freya.DataStructures;
public
    MyClass = class;
implementation for MyClass is
    ...
end.

But, what happens when we find this?

implementation for Freya.DataStructures.MyClass is

To avoid complications, Freya requires that the type reference in the implementation header should not include the namespace part.

Another Freya feature complicates things: nested type references. You can declare a nested type along with the enclosing class, as in C#, but you can also put a simple stub inside the enclosing class declaration and declare the actual type later.

LinkedList = class[X]
protected
    Node = class;
    ...
end;

LinkedList[X].Node = class
    ...
end;

The implementation section for the linked node class should be like this:

implementation for LinkedList[X].Node is

Have you noticed I didn’t mention merging any namespaces? I could declare types belonging to the namespace Freya.DataStructures in several source files? Should we merge those “partial” namespace sections? No, we shouldn’t. Each namespace section may have different using clauses, and these clauses plays an important role in the resolution algorithm.

Actually, we’re missing another merging algorithm: gathering parts from a partial class. So far, we haven’t added partial class support to Freya. We’re planning their design and implementation in the short term.

On properties and events

2005-05-14T23:12:00.000+02:00

The simplest way to declare an event in C#, only requires from you to provide the event declaration:

event EventHandler Click;

Then, the C# compiler adds the implementation:

A private field of the corresponding delegate type.
A method called add_Click for adding handlers to the delegate chain.
A symmetric remove_Click method, for removing handlers.

Outside the declaring class, the only operations you can perform with the event is adding and removing event handlers, using the now famous shortcut:

myClass.Click += myClickHandler;

By the way, you can’t fire the event from outside the declaring class! That’s encapsulation. However, things are different inside the class. The compiler generates a private field, and it doesn’t let you access that field... apparently. Actually, whenever you mention the event identifier from inside the declaring class, the compiler handles the identifier as if it were the private field. You’re free to do with the event identifier whatever it’s allowed with a delegate type field.

Events in Freya are identical to C# events. We also implemented a variant of this trick to be used with properties (credits belong to the authors of Chrome, another .NET language inspired in Delphi). When you’re designing a class, you often declare fields that should be transformed later into properties… or, on the contrary, you start with properties that map directly to a naked field with the same type. How much code do you need to write in this very simple and frequent case? A lot, if you’re using C#. You must declare the field, then the property and most of the times, both access methods.

In Freya, you only need to declare the property:

property Caption: string;

If we don’t provide an implementation for Caption, Freya will generate a private field and two access methods with proper signatures. Outside the declaring class, you will only see the property. However, inside the class, any reference to the property will be translated as a reference to the underlying field. In our previous example, Caption is a read/write property. If you want a read only property, you only need to add the readonly keyword to the declaration:

property Caption: string; readonly;

You could even declare an initializer for the property:

property Caption: string := 'Form1';

That’s an internal access, of course, and the compiler just moves the initializer to the private field. Of course, you can also “initialize a property” when the property has an explicit setter, but then, the initialization code calls the setter method when creating a new object instance.

As a final remark, we allow grouping related properties in a single declaration:

property X, Y: Double := 0;

The initializer applies to both properties, of course, and it should be evaluated only once.

Just an implementation detail...

2005-05-14T22:06:00.000+02:00

One of my favorite features in Freya is the syntax of compiling units. Freya was initially inspired in Delphi, so it inherited what I call the “split organization”: declarations and implementations belong to different sections. Every compiling unit in Delphi has just an interface and an implementation section. Freya features a mutation of this structure. Every file in Freya is divided into one or more declaration sections, and zero or more implementation sections. Declaration sections are very similar to interface sections in Delphi… except that Freya doesn’t use the interface keyword. Declaration sections always start with public or private, and each section may contain several type declarations.

Implementation sections deviate more from the Delphi’s way. Each implementation section is associated to a single type declaration. Thus, all methods from the same type are always grouped together.

namespace Freya.Compiler;
public
    Class01 = ...
    Class02 = ...

implementation for Class01 is

implementation for Class02 is

end.

Besides forcing a better grouping of method bodies, there’s another immediate advantage in this organization: you don’t need to repeat the type name in the headers of method implementations, as in Delphi and C++:

implementation for Class01 is

    method Method01: string; ...

    iterator Items: WhatEver; ...

But this is only the beginning. This syntax allows what I call the “just an implementation detail” attitude. Let’s say you need a private field for Class01. Why should you include its declaration in the class declaration? It’s just an implementation detail, after all! Consequently, Freya allows you to declare the field in the implementation section of Class01:

implementation for Class01 is

    var Field01: Double;

    method Method01: string ...

This trick can be repeated with constants, methods, constructors and even properties. The rule is: whenever you find a member in an implementation section that hasn’t be declared with the class, the compiler will consider it as a private member of that class.

More? In a previous post, I demonstrated interface implementation by delegation:

public
    Class02 = class(IEnumerable);

implementation for Class02 is

    var strings: array of string =
        ['Freya', 'rules!'];

    interface IEnumerable = strings;

end.

The implementation of an interface is a private business, so its place is the implementation section for the class. What about explicit method implementations, as in C#? Another implementation detail! You don’t have to declare the method in the class declaration (actually, you can’t):

implementation for Class02 is

    method IEnumerable.GetEnumerator: IEnumerator;
    begin
        ...
    end;

By the way, there’s an interesting link between how we designed this Freya feature and Quenya! But that’s a different story, and it deserves another post...

Creation statements

2005-05-12T01:02:00.000+02:00

A minor but useful enhancement: take a look to this common code written in C#:

Dictionary<int,string> d =
    new Dictionary<int,string>();

Why do we have to write the type name twice? Well, put the blame in polymorphism. In our example, the declared type of the local variable and the type of the created instance are the same. But we could have specified a class descending from Dictionary, if any, in the right side expression. Easy, huh?

However, most of the times both types will be the same. Could we avoid the duplication? If you're using Freya, the answer is YES:

var
  d: Dictionary[Integer,String];
begin
  new d;
  // Now, a parameterized constructor:
  new d(1024);
end;

A useful time saver, isn't it?

Updated: We have dropped the new statement after the publication of the first draft for C# 3.0. Now we have variable declarations with implicit types, as in the C# 3.0 proposal.

Arrays, sets, brackets and curly braces

2005-05-09T01:09:00.000+02:00

I'm afraid there're some big changes on the way, in order to accommodate both array and set literal constructors in Freya. We gave priority to the implementation of arrays, in order to match C#'s functionality as soon as possible. You can write "literal arrays" in Freya using a bracket-delimited list:

[1, 2, i]

That would be the equivalent of C#'s:

new int[] { 1, 2, i }

Freya's notation is shorter, but we have to check yet how it behaves together with method overloading. C#'s on-the-fly arrays has a clear hint about the array type. I'm already inferring the array type from the item types. This is not a problem with assignments. As in C#'s, Freya arrays are covariant. When a covariant array assignment is detected, the compiler checks whether the right side is a literal array constructor, as above, in order to perform the conversion at compile time.

Why do I mention method overloading? Well, overload resolution has a very detailed specification for C#, and most of it has been borrowed by Freya. I still have to prove that the potential ambiguity introduced by these array expressions doesn't break the algorithm. I hope it won't, since all examples tried by hand have succeeded.

And, what about sets? One of the goals for Freya is preserving the Set data type from Pascal, with some minor changes, such as introducing an imaginary Set[X] generic class, and a big change: Freya sets won't be limited to integer subranges and enumerative types.

One of our problems is how we will write literal set constructors. Pascal uses brackets as delimiters, and Freya could do the same. That would bring more ambiguity to bracket delimited expressions, and I'm not happy with the preliminary results. That's the reason why I'm thinking about reintroducing curly braces as set delimiters (the role they already play in mathematical notation!). This would imply changes in multiline comments. Delphi borrowed single line comments from C++, so I don't see any reason why I shouldn't use C# delimiters for multiline comments in Freya:

/* A Freya multiline comment */
if i in {1,2,3} then
    if j in [1, 2, 3] then
        // ...

Note that we already allow the in operator along with arrays. The second condition is translated this way:

if [1,2,3].IndexOf(j) <> -1 then
    // ...

Of course, since this example features a constant array, the actual translation would be:

if j = 1 or j = 2 or j = 3 then
     // ...

Note that, thanks to our new and sounder precedence rules, we didn't need any parenthesis in the Boolean expression.

More about constants

2005-04-30T16:24:00.000+02:00

Constants implementation finished... It has been hard, because Freya must admit this kind of declarations:

const Pi = 3.14;

It is the constant type what's missing in this example, as it happens in Pascal. C# always requires the type declaration:

public const double Pi = 3.14;

Of course, Freya also admits this syntax:

const Pi: Double := 3.14;

The problem with implicit types in constants is that you face two challenges at the same time: finding the data type and then, evaluating the expression. It's already solved, but it could have been easier without this kind of declarations.

Constant symbols

2005-04-29T15:26:00.000+02:00

I'm working right now in the implementation of constant symbols. This is how constants are declared in Freya:

MathHelper = class
public
    const Pi: Double := 3.141592653589;
    const E = 2.718281828459;
end;

Constant can be declared inside a method implementation too:

method TrySave;
const
    MAX_ATTEMPTS = 3;
begin
    // ...
end;

Local constants are easy to implement, since they only exist at compile time, and member constants don't use them in their own definitions. On the other hand, member constants require a careful implementation. The expression in a constant declaration may contain references to other constants, as long as these references don't cause circular dependences. This is a simple example:

Trigonometry = static class
public
    const PiOver2 = MathHelper.Pi / 2.0;
    // ...
end;

MathHelper = class
public
    const Pi: Double := 3.141592653589;
    // ...
end;

I think I'll handle constant definitions right before performing "body resolution" on the Abstract Syntax Tree. Probably, I'll gather all constants from the compiling project in a single list, to execute a topological sort on this list. I have a vague idea about a brute force algorithm for topological sort, but I'm afraid I'll have to check my copy of The Art of Computer Programming for a better approach.

Raison d'être

2005-04-29T11:11:00.000+02:00

There are a lot of programming languages already running in the .NET Framework. The CLR leaves almost no freedom to the designer of the object model. The "official" .NET languages are quite good and comprehensive. If you enjoy curly braces and esoteric operators, C# is your language. If you hate curly braces, you could choose a face lifted VB.NET, with its new support for operator overloading and generic types. Is there any chance for Freya in this hard competition?

First of all, don't get fooled: VB.NET is still a line oriented language, and that's not a minor issue. Though the newest VB.NET has almost nothing to do with Vintage Basic, I think it's not a real alternative for those, like me, who prefer a language inspired in the Algol family. The natural alternative should have been Delphi, a language also designed by Anders Hejlsberg but, alas, Borland decided that Delphi.NET should keep the compatibility with existing "native" Delphi code, and the result is a hybrid scaring monster.

Freya has, indeed, a winning card in the sleeve: it has been designed for .NET v2.0. You can spell it this way: Freya supports generic types since its first version, and this allows a more sound and complete type system. For instance, Freya array types are no longer special types in any sense: they are just closed generic types built over a mythical generic Array[X] class. I say "mythical" because there's no such class in the CLR: System.Array is a non generic class. Another example? Take the retorted syntax for managing delegate types in .NET v1.x languages:

new EventHandler(button1_Click)

There you have a constructor using a non existing type: what's the type of the constructor parameter? Sure, it is a "method group". Could you use a "method group" elsewhere in your own classes? No, you can't. It's true that C# v2.0 has simplified this syntax, so you could omit the explicit constructor call. In Freya, you can always use a method name as it were a delegate type value.

Also, there are several minor syntactic details favoring Freya, but I will only mention one of them here: the distinctive marker for class members, a common feature in the Algol/Pascal family languages:

method DoThis(UsingThis: Integer);
method ReturnThat: String;
// The class name may be ommitted
constructor MyClass;
destructor MyClass;
iterator LoopOverThis: DataRow;

On the contrary, C/C++/C# has to fiddle with a cryptic and limiting syntax that imposes serious limitations in C# and even in the old good C++. How do you write a destructor in C++/C#?

~ MyClass() {}

This is probably the ugliest thing in language design you will ever meet! And how C# manages to declare an iterator? Actually, there is not such a thing in C#! Sure, we have something called "iterator blocks". How do we identify an iterator block? Well, you must read the whole block looking for yield statements. Nice, huh? And then, you have to tell between yield break and yield return. Now, let's see an iterator in Freya:

// This is real code, drawn
// from the Freya's compiler
iterator Members[X(AstMember)]: X;
// A generic iterator, with a
// base class constraint in the
// generic type parameter.
begin
  for M: AstMember in AllMembers do
  begin
    Result := M as AstMember;
    if Result <> nil then Yield;
  end;
end;

Of course, there are more reasons than those I have presented here. For instance, I'm fond of the Freya solution for class declarations/implementations and the whole attitude I call "just an implementation detail". But there's a time and a place...

Implementing interface mappings

2005-04-28T19:39:00.000+02:00

Freya has three techniques for implementing interface types:

Implicit implementation: a public method in the class with the proper signature.
Explicit implementation: an implicitly private method, with a compound name including the interface type name and the interface method name, just as in C#.
Implementation by delegation: this is a feature borrowed from Delphi. It’s a simple but effective technique for reusing implementations, and it makes easy to change the behavior of an instance by plugging a different implementation, at runtime.

I'll show you an example of implementation by delegation:

using System, System.Collections;
public
    // All Foo features are private
    Foo = class(IEnumerable)
    end;

implementation for Foo is
    // A private instance field.
    var Items: Array[String] = ['Freya', 'rules'];

    // Just an implementation detail!
    interface IEnumerable = Items;

end.

In this example, all calls to methods from IEnumerable methods are dispatched to the implementation of IEnumerable already available in Items. This is possible because there’s an implicit conversion from any array type to IEnumerable.

Native Delphi implemented this feature with a clever trick, by modifying the typecast operation. Our current implementation is probably not as efficient as native Delphi’s one, but it’s easy to code. When an interface delegation is found by the compiler, it synthesizes the required methods in the implementing class. Since these are very short methods, chances are high that the CIL loader will translate them as inline method calls.

We are trying another complementary solution: whenever possible, those method thunks call the target implementation using “tail calls”. Tail calls are supported by the CIL through an instruction prefix that can precede the “call” and “callvirt” operation codes. This prefix instructs the CLR to discard the current stack frame before jumping to the target method. There are no guarantees that this hint will be honored by the CIL loader, however. We still have to run the corresponding benchmarks before deciding the best translation for this useful feature.

Update: I didn't realize then, but tail calls have no effect when performed on virtual methods, so, after some tests, this "optimization" was discarded.

By the way, tail calls are only generated when the method signature does not include any reference or out parameters. That’s because a reference could point to a variable in the current stack frame, so the CLR has no way to verify whether a given call is safe or not. When all parameters are passed by value, tail calls are considered a safe operation.

Freya says Hi!

2005-04-28T16:07:00.000+02:00

Hello World!

This blog is dedicated to the Freya Programming Language, a new object oriented language specially designed for running on the .NET Framework, version 2.0 and higher, when available.

In the next few days, I'll post more information about Freya features and, mainly, about its ongoing implementation. I will appreciate any comments, suggestions and proposals.

Freya is a join effort by Moebius Ootics (www.moebiusootics.com) and Intuitive Sight, a.k.a IntSight (www.intsight.com), my own company.

Best regards, and keep in touch!

Ian Marteens