Reenigne blog

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.

Designing an entirely new computer language is a ridiculously ambitious thing to attempt as a personal side project, but even so it apparently isn't ambitious enough on its own for me - oh no, I want to write a complete compiler for it as well.

Why would I go to all the trouble of doing that rather than just writing a GCC front end, starting with LLVM or even writing it as a translator to another language?

Well, the short answer is that I want to explore some parts of the design space of both compiler design and languages that I feel have so far gone under-explored. In other words, play around and have some fun.

I do have some specific ideas under that umbrella that I want to try out. Some of these ideas rely on having the entire compiler for my language written in the language itself.

Here is one specific example I've been vaguely thinking about. Suppose we have a compiler that translates ALFE code into an executable binary program. One problem with it is likely to be compilation speed - I'm eliminating separate compilation which is what makes incremental builds possible in C and C++. But I'd also like to have the edit-compile-test cycle be as quick as possible, even for large programs. For large programs, even C/C++ incremental builds are slow because the entire link step has to be done from scratch.

So how can ALFE, which doesn't even have separate compilation, have incremental build times even close to that of C/C++?

What I really need seems to be a daemonic compiler - one that hangs around in memory all the time and keeps all the state from the previous build so that instead of accepting a complete input file it accepts a diff between the input currently in memory and the desired input. The output could be a binary diff but for most of these edit-compile-test cycles we won't even care about the output binary - what we'll really want is a diff in the list of which testcases passed and which failed. It would be great if the compiler could figure out which testcases could possibly be affected by an input diff and only rerun those testcases. It might even be possible to make it sufficiently fast that that it could (asynchronously) recompile with each keystroke in a text editor, so you'll know instantly if your fix makes the broken test pass and if it breaks any other tests. That would be a fantastic boon to productivity - with the right set of tests, updates can be nearly instantaneous once the problem is found!

Such a system would improve reliability of software as well - if the edit-compile-test cycle is that much shorter then any manual testing would be a much greater fraction of it, so programmers would have a much greater incentive to make automated testcases for every bug fix, and test coverage would rapidly improve.

Writing a compiler is hard enough on its own, but taking a normal compiler and modifying it to transform diffs to diffs seems to be task of similarly daunting magnitude. But that's not necessarily the case if we have a compiler that is written in the language that it understands. Modifying the compiler to make it output a diff-to-diff compiler should, I think, be much easier than modifying the compiler to be a diff-to-diff compiler, since I wouldn't have to modify every part of the compiler - it would be a pass on the intermediate form that transformed transformations from f(x)->y form to f(x+dx)->y+dy form. Of course, that's still much easier said than done, but I think it takes it from the realm of the impossible to the realm of the merely very difficult.

I'm very impressed with WordPress as a piece of software in general, and particularly at how it's managed to implement a text editor inside a web browser. However, as a text editor it's kind of annoying. It doesn't work terribly well in Internet Explorer for one thing. Even on Firefox and Chrome, it suffers from "one scrolling window inside another" syndrome which is common on many complicated "web applications". Once you've got a got more than a screenful of text in the edit box, you get an inner scrollbar to scroll it up and down. Being a keyboard-oriented sort of person, I usually use the PgUp and PgDn keys for this. PgDn works fine on the inner edit box until you get to the bottom, at which point it stops swallowing the PgDn keypresses and passes them on to the outer window, which then scrolls the top of the edit box off the window. I can't undo this with PgUp because that goes to the inner edit box! This behavior breaks the idea that PgUp and PgDn should do opposite things.

One way to fix this would be to make the edit box expand to fit the text instead of scrolling. There's probably a plugin for this (I've been able to solve just about every other WordPress problem I've had by installing a plugin) but I have no idea how to find it - the obvious searches didn't help. So most of the time I write blog posts in my preferred editor and paste them in. However, I still end up doing a pass over the text in WordPress to fix up the line breaks.

ALFE's closest ancestor is probably C++ (or possibly D, though I don't have much experience of that language). Though it also draws inspiration from such disparate corners as C#, PHP and Haskell. But there are several C++ features I'm planning on leaving out of ALFE:

• C compatibility - this is the cause of a great many of the complexities of C++, though is quite probably also the only reason why C++ has been as successful as it has.
• Separate compilation - another huge source of complexities in C++. The ALFE compiler will have a built in linker, so it will be able to generate an executable binary in a single instantiation. Actually I'm not entirely getting rid of separate compilation - you'll still be able to create and consume object files, but doing so will require explicitly specifying the ABI to use. The problems that are solved by separate compilation I'm planning to solve in different ways, which I'll write about in future posts.
• Declarations. Declaring something separately from its definition is useful if you have separate compilation, or if you're writing a compiler that can compile programs too big to fit in RAM. RAM is pretty cheap nowadays so this isn't a particularly important use case - certainly not important enough to make programmers duplicate information and have an extra place to modify things when they change. The only things which look like declarations in ALFE will be for things like calling a function declared in an external binary, such as for platform ABI calls. I go to great lengths to minimize the number of declarations in my C++ programs.
• The preprocessor. Well, macros specifically (anything you might want to use macros for in C or C++ will be done better with features of the core language in ALFE). Header files will still exist but will have rather different semantics. In particular, they won't be included until the code in them is needed - if you put an include statement inside a class definition and then no instance of that class is ever used, the file won't even be opened. That should drastically improve the time it takes to compile files while making it very simple to use the standard library (whose classes will all be included this way by default).
• The post-increment and post-decrement operators. These do have some merit in C - you can write things like "while (*p != 0) *q++ = *p++;" much more concisely than would otherwise be possible. The first chapter of Beautiful Code has a nice example. However, I don't think these bits of code should be the ones we're making as concise as possible - such a piece of code should be written once, wrapped up as a highly optimized library function and thoroughly documented.
• Digraphs and trigraphs. You'll need the full ASCII character set to write ALFE, which is probably not much of a hardship any more.
• Unexpected exceptions (and run-time exception specifications). Exception specifications are a great idea as a compile time check but they make no sense as a run-time check, which is why most coding standards recommend against using them. But the reason that C++ needs exception specifications to be a run-time check instead of a compile-time check is because of separate compilation - there's no way to tell what what exceptions will actually be propagated from any particular function. With compile time exception specifications it's trivial to force the exception specification for destructors to be "nothrow" and thereby make propagating an error from a destructor be a compiler error, which is a much better solution than the "unexpected exception" mechanism in C++.
• Multiple inheritance. I gave this one a lot of thought before deciding on it. Multiple implementation inheritance is something that seems to get used very little in proportion to the amount by which is complicates the language. I've only seen one even slightly compelling example (the BBwindow etc. classes in chapter 12 of The C++ Programming Language by Stroustoup) and the rationale for that goes away when you have control over all the parts of the program (i.e. you're not consuming code that you can't modify). ALFE actually goes one step further and disallows multiple interface implementation as well on the grounds that if you have a single class implementing more than one interface, it's a violation of the separation of concerns. From an implementation point of view, inheritance is a special case of composition - the parent object is just in the first position. That suggests a good way to simulate multiple interface inheritance - compose the class out of inner classes which implement the various interfaces - pointers to these inner classes are retrieved via method calls rather than casts. I might even add some syntax to streamline this if it gets too verbose. And I might still change my mind and introduce multiple (interface) inheritance if my plan doesn't work.
• The main() function. Instead the statements in the file passed to the compiler are executed in order from the top - i.e. there is an implicit "main()" wrapped around the entire compilation unit. Command line arguments and environment variables are accessed via library functions (or possibly global variables), which means they don't have to be passed through the call chain from main() to whatever piece of code interprets the command line arguments. That greatly reduces the amount of boilerplate code.
• public/private/protected/friend. Instead I'm planning to implement "accessibility sections", which are kind of like public/private/protected but specify which classes are allowed to access the members in the section. That way you don't have to give all your friends access to all your private parts, which is possibly the most innuendo-laden complaint about C++.
• int to bool conversion. The condition in "while" and "if" statements must have boolean type. If you want C semantics you have to add "!= 0" explicitly. I've been doing this anyway in my own C/C++ code and I don't find it to be a source of excess verbosity - if anything it clarifies my intents.
• Assignments (and increment/decrement) as expressions. This solves the "if (a=b)" problem that C and C++ have, in a far more satisfactory way than the "if (1==b)" abomination that some recommend. I've also been avoiding using assigments as expressions in my C and C++ code and I don't miss them - I think the code I write is clearer without them.
• C strings (responsible for so many security bugs). ALFE will have a first-class String type, possibly consisting of a pointer to a reference counted buffer, an offset into that buffer and a length, but I'll probably try a few things to see what performs best, and the compiler might even decide to use different representations in different places if there's a performance advantage in doing so.
• References. I can see why these were necessary in C++ but I think for ALFE they will be unnecessary because of the lack of a fixed ABI, and the "as if" rule (the compiler is allowed to use whatever implementation strategy it likes as long as the semantics don't change). So the rule for deciding how to pass an argument is simple: pass by value if it's strictly an input, pass by pointer if it the function might need to change the output. The compiler will decide whether to actually pass by value or pointer depending on what is fastest on the target architecture for the kind of object being passed.
• Array to pointer decay. In ALFE, fixed-length arrays are first class types, so passing one to a function declared as (e.g.) "Int foo(Int[4] x)" passes by value, i.e. copies the entire array. Getting a pointer to the first element requires explicitly taking its address: "Int* p = &x[0];"

Every computer language has its design philosophies. Here are ALFEs:

• Imperative rather than purely functional. This, this and this have some good points about why functional programming isn't a panacea. However, I'm hoping to implement some features which help to keep the purely functional parts of a program separate from the parts with side effects - the compiler will be able to keep track of which functions are supposed to be pure and prevent them from calling impure functions (with appropriate escapes for things like debugging and encapsulating high performance libraries behind functional interfaces).
• Statically typed rather than dynamically typed. A type annotation is like a compiler-enforced comment and a unit test rolled into one, at an almost trivial cost. In fact, being used to static typing I now find that when I'm programming in a dynamic language I spend more time wondering what values a variable is supposed to have and tracking down errors that the type system would have caught than I do typing and modifying type annotations in static languages. Plus they're not even compulsory - I'm planning to give ALFE a Variant type which can hold any value (although most of the standard library functions will probably be statically typed so dynamic typing won't have first-class status). Some form of Hindley-Milner style type inference is also something I'd like to do.
• Strict rather than lazy evaluation. ALFE is a high performance language and general performance characteristics are considered to be an observable behavior. Of course, lazy evaluation as a strategy for particular pieces of code is still possible - I remember when I first understood lazy evaluation reading about strategies for implementing continued fraction arithmetic in HAKMEM and thought it was tremendously clever, though unfortunately I've never had a good reason for implementing it.
• No garbage collection. Also, the space of garbage collected languages has also been pretty thoroughly explored.
• Rich in features at the expense of simplicity and ease of learning. In fact, if this language is so complicated that I'm the only one who can use it, that would not in itself cause it to fail to achieve what I'd like to achieve with it.
• It's primarily a compiled language for maximum speed. Though I am currently planning on having a built in interpreter for the build system. A REPL might come in handy too.
• The core language is not minimalist - even if some feature could be added as a library, it may still get language support if that would improve it in some way.
• Text is for input and output, not processing.

I might come back and add some more things to this list as I think of them.

As regular readers of this blog know, I have a long-term on-and-off project to design my own computer language in which I can be super productive at all parts of the development cycle. I have occasionally referred to this language as Unity (given my hope that it will be useful for many purposes), but since picking that name I have learned of several other software projects by that name (including a another programming language), so I've renamed my project to ALFE. I've updated all the references I could find (including the URLs, which I didn't think I'd be able to do - WordPress has a plugin for everything). If you spot any more lurking in the dark corners of the blog please let me know.

ALFE stands for "A Language For Everything". Which has more than one meaning. One is that ALFE itself can be used for any purpose. Another is that (via the built in parser generator and code generator) you can use it to create powerful domain-specific languages.

ALFE is also the name of the standard library that is included with the language, though when it's referring to the library, it stands for "A Library For Everything".