Reenigne blog

This is part of the ALFE types series.

Bottom is a special type that has no values associated with it. So declaring a variable or member of type Bottom is forbidden. It's useful for using as the return type of a function that doesn't ever return normally (i.e. a function that always throws an exception or terminates the process).

[Bottom] is also another name for Null (or maybe it's a different one-element type, I haven't decided yet).

Another way of writing Bottom is Either<> (i.e. an algebraic data type with no types being summed).

I might end up calling it something different - the name has slightly too many connotations of anatomy and (worse) type theory for my taste. I'm not sure what would be better, though. Empty isn't quite explanatory enough, and NoReturn doesn't quite capture the full range of Bottom's behavior.

This is part of the ALFE types series.

Foo[2], Foo[3], Foo[4] etc. are arrays whose length is fixed at compile time (not to be confused with [Foo] whose length is unknown and possibly undefined even at runtime). Passing around a value of array type copies the entire array (arrays don't decay to pointers). Operations defined on the elements can also be applied (element-wise) to the array itself, so you can write things like:

Int[2] centre(Int[2] topLeft, Int[2] bottomRight)
{
    return (topLeft + bottomRight)/2;
}

Foo[2] also has a template form, but since template arguments can only be types and not integers like they can in C++, there is a twist: Array<Foo, Class {Int n=2;}>. Any type can be used for the second argument as long as it has a public member named n of type Int with value known at compile time. This allows templates to work generically with arrays of different lengths.

Foo[n] can be indexed by an integer to yield an (RValue or LValue) Foo. It can also be indexed by a sequence (whose values are known at run time) to yield a slice of the array.

An array can be coerced to a sequence, and the compiler will box up the element count and pointer as necessary.

This is part of the ALFE types series.

[Foo] is the type of an immutable sequence of Foo values (the sequence itself is immutable but the values in it are not necessarily immutable). It is syntactic sugar for Sequence<Foo>. It has methods "Boolean isEmpty()", "Foo first()" and "[Foo] rest()". As usual the actual implementation is up to the compiler (and may even be different for the same sequence in different parts of the same program). Values like [], [foo] and [foo1, foo2] are allowed.

There is also a special operator for creating sequences of consecutive integers: "..". It's closed on the left and open on the right, so 0..5 is equivalent to [0, 1, 2, 3, 4]. Infinite sequences like 0.. are also allowed, since there's no need in the Sequence<> interface to know how many elements there are up front. I'd like to have consecutive sequences that count up in steps other than 1, but I haven't decided on a good syntax for that yet. Python's extended slicing syntax is quite nice, but I think ".." is more natural than ":", and I already have quite a lot of meanings for the latter.

The sequence type can also be used as the return type for a generator function:

[Int] primes()
{
    Primes = Class : [Int] {
        construct(Int m = 2) { n = m; }
        Boolean isEmpty() { return false; }
        Int first() { return n; }
        [Int] rest()
        {
            for (Int m in (n+1)..) {
                Int i = 2;
                while (m/i >= i) {
                    if (m % i == 0)
                        break;
                    ++i;
                }
                done
                    return Primes(m);
            }
        }
        Int n;
    };
    return Primes;
}

Disregarding the usage of trial division instead of a more efficient sieve of Eratosthenes, it may seem terribly inefficient to create a whole new Primes object each time we get the next element of the sequence. However, it is the expectation that the compiler should inline the entire rest function into the calling loop so that all the object creation and destruction is optimized away.

This is part of the ALFE types series.

(Foo, Bar) is a "product" type, aka Tuple<Foo, Bar> or a structure with unnamed fields. Tuple is another variadic template, so (Foo, Bar, Baz) is syntactic sugar for Tuple<Foo, Bar, Baz>. Values of Tuple type are written in the same way as the type itself, except with values instead of types inside the parentheses: (foo, bar). You can have tuples of LValues as well as RValues, which is handy for functions that return Tuple values:

(foo, bar) = getFooBar();

You can also have a tuple of declarations:

(Foo foo, Bar bar) = getFooBar();

(Foo) is identical to Foo just as it is in C, but in ALFE it's also a 1-tuple (so 1-tuplifying is really just a no-op). There is also a single 0-tuple type () aka Tuple<> which is another name for Null. There is a single value inhabiting this type, which is also (by slight abuse of notation that took me a while to determine wasn't too amiguous or confusing) called () and Null (a type specifier can be used as a value if it is default-constructable).

This is part of the ALFE types series.

Foo? is a "Maybe" type, also known as an option type. It is syntactic sugar for Maybe<Foo>. This type has values of Null (a type with only one value) and Just<Foo> (which is derived from Foo) - it's equivalent to Null | Just<Foo>.

This is particularly handy if Foo is a pointer type, since ALFE's usual pointer type is not nullable, so this template will give you back C pointer semantics (except with more safety, since it'll force you to explicitly check for Null before dereferencing). Because of the Just<> template, it's possible to stack Maybes - so you can have Foo?? with two separate sentinels, Null and Just<Null>. If Foo is a pointer type, the compiler can implement the sentinels just as pointer values that are guaranteed not to point at real objects, just as C and C++ do, so there's no loss of efficiency.

This is part of the ALFE types series.

Foo | Bar is a "sum" type, in other words a type that can have any values that Foo can as well as any values that Bar can. Also known as a tagged union or an algebraic data type.

Foo | Bar acts like a base class (supertype) of both Foo and Bar, since either of the latter are Liskov-substitutable for the former, and the downcast required to convert from the former to the latter is identical that required for casting from a base class. Foo | Baz also acts like a (completely separate) base class of Foo, so sum types provide something almost, but not quite, entirely unlike multiple inheritance.

Foo | Bar has all the methods and members of the most derived common base class of Foo and Bar (and, if that common base class has no other subclasses not derived from Foo or Bar, it'll be identical to Foo | Bar. In particular, Foo | Foo is identical to Foo).

Foo | Bar is syntactic sugar for a special template Either<Foo, Bar>. Similarly, Foo | Bar | Baz is syntactic sugar for Either<Foo, Bar, Baz> - Either is a variadic template. Either<Foo> is just another name for Foo.

How Either is actually implemented is up to the compiler, but some kind of boxing will probably be necessary in the case when Foo and Bar are not both pointers to types with vtable pointers.

This is part of the ALFE types series.

Foo(Bar) is a function type - the type of a function taking Bar and returning Foo. It is syntactic sugar for Function<Foo, Bar>. Similarly, the zero-argument function type Foo() is short for Function<Foo> and the two-argument function Foo(Bar, Baz) is short for Function<Foo, Bar, Baz> so Function is a variadic template, a curious kind of type constructor which I'll talk more about in a future post.

A function type is a bit unusual in that it is not of definite size, so you can't declare a variable of this type on the stack or as a member of another type (the syntax for doing so would be too similar to declaring an actual local function or method instead). However, pointers to functions like Foo()* work fine, just as they do in C and C++ (albeit with an easier to understand syntax). Function types can also be used as template arguments. Raw function types might also come in handy for run-time code generation, but I haven't yet finalized the syntax for that.

Bar -> Foo is yet another way of writing Foo(Bar). I'm not sure if there's much of advantage to having this syntax as well as the other, but there might be some circumstances in which it makes more sense.

This is part of the ALFE types series.

As a high-performance language with C++ heritage, it should not be at all surprising that ALFE has pointers.

Given a type Foo, the type of a pointer that points to values of that type is Foo*.

In C and C++, the grammar binds the asterisk to the variable name rather than the type. So (particularly in C) declarations of pointers look like this:

Foo *foo;

That was very confusing to me when I first started learning C. Once I thought of it as:

Foo* foo;

instead, the whole thing made much more sense. In C++, this style is idiomatic, due to C++'s emphasis on types over expressions. However, the grammar hasn't caught up so:

Foo* foo, bar;

declares a Foo* called foo and a Foo called bar.

ALFE fixes this once and for all:

Foo* foo;

declares a real Foo* called foo rather than an imaginary Foo called *foo.

The second difference between ALFE and C++ is that pointers are by default not nullable. In other words, Foo* carries the connotation of pointing to an actual Foo, so null checking is not required (or even possible, since comparing a Foo* to Null will always yield false). In other words, ALFE fixes Tony Hoare's billion dollar mistake. Put like that, it's a no-brainer.

Of course, in practice there will be such things as an uninitialized Foo*, one that points to a Foo that went out of scope or one that points to one past the end of an array. However, those aren't things that could be checked for by a function which just takes a Foo* as an argument - if the pointer might be invalid there would have to be an out of band signalling mechanism saying whether it is safe to dereference that pointer or not. I'll be talking about an ideally suited mechanism in a future post in this series.

Foo* is syntactic sugar for the template instantiation Pointer<Foo>. This is mostly to simplify the implementation of the compiler, but it does also mean that the type constructor Pointer could be passed to some template that has a parameter of kind <>. Not sure why you might want to do such a thing, but it's there is somebody does find a use for it.

I want to write a series of posts about the rich type system I want to implement for ALFE. This post will serve as an index to them.

I recently tried doing a bit of programming in Haskell, and although I didn't produce anything worth showing off, I did get a bit of a feel for the language and how it works. One of my favorite things about Haskell is the rich type system, and I want to use some of its ideas in ALFE. Some of the ALFE types below are inspired by Haskell types.

Given types Foo, Bar and Baz I would like ALFE to have the following types:

• Foo* - a pointer type.
• Foo(Bar) (aka Foo -> Bar) - a function type.
• Foo | Bar - a "sum" type.
• Foo? - a "Maybe" type.
• (Foo, Bar) - a "product" type.
• [Foo] - a "sequence" type.
• Foo[2] - a fixed length array type.
• Bottom - the "bottom" type.
• Variant - the "variant" type.
• Label - the "label" type.
• Complex<Foo> - a complex number type.
• Rational<Foo> - a rational type.
• String - the string type (usually represented in memory as UTF-8 in some form).
• CodePoint - a type capable of holding any Unicode code point.
• Fixed<Foo, Bar> - a fixed point fractional type.
• Boolean - the boolean type.
• Int1, Int2, Int4, Int8, Byte, Int16, Int32, Int64, Int128, Int256, Int512, UInt1, UInt2, UInt4, UInt8, UByte, UInt16, UInt32, UInt64, UInt128, UInt256, UInt512, NInt1, NInt2, NInt4, NInt8, NByte NInt16, NInt32, NInt64, NInt128, NInt256, NInt512 - fixed-width integer types.
• Word, Int, HalfWord, QuarterWord, DoubleWord, QuadWord, UWord, UInt, UHalfWord, UQuarterWord, UDoubleWord, UQuadWord, NWord, NInt, NHalfWord, NQuarterWord, NDoubleWord, NQuadWord, FastInt1, FastInt2, FastInt4, FastInt8, FastByte, FastInt16, FastInt32, FastInt64, FastInt128, FastInt256, FastInt512, FastUInt1, FastUInt2, FastUInt4, FastUInt8, FastUByte, FastUInt16, FastUInt32, FastUInt64, FastUInt128, FastUInt256, FastUInt512, FastNInt1, FastNInt2, FastNInt4, FastNInt8, FastNByte FastNInt16, FastNInt32, FastNInt64, FastNInt128, FastNInt256, FastNInt512 - machine-dependent integer types.
• WordString, Integer, Unsigned - arbitrary-precision integer types.
• Float16, Float32, Float64, Float128 - fixed-length floating-point types.
• Float - machine-dependent floating point types.
• Floating - arbitrary-precision floating point type.
• Concrete (possibly also specializations like Length, Time, Area, MagneticFluxDensity etc.)

There's still a lot about this that isn't finalized. For example, I might use some templates to avoid having all those fixed-width and machine-dependent types.