Felix - a fast scripting language

Internally such arrays have a special representation which allows arrays of 100,000 values, something which could never be represented by a tuple type (and still get reasonable compile times :)

Probably the single biggest feature was the introduction of Haskell style type classes as a way to systematically provide "generic" features like comparisons and conversions to string which are de rigueur in dynamically typed scripting languages.

Less obvious but quite important was switching the parser from Ocamlyacc to Dypgen combined with OCScheme, which together put the grammar in user space, allowing almost the entire grammar to be put in the library. A lot of new features were added with very little or no change to the compiler by just adding some EBNF grammar and suitable Scheme action code to the parser.

This can be very effective. For example, with only one extra term in the compiler, I added a dynamic object system that looks a lot like Java with objects and interfaces including "implements" and "extends" stuff. It just uses records of closures (the compiler mod added record extension), but the syntax is neat and almost immediately I used it to factor the webserver into separately compiled plugins. I originally implemented this as a kind of joke, to show off the expressive power in respect of Domain Specific Sub-Languages, but not intended for use. The joke was on me :)

When a function is inlined, there are two things you can do with the arguments: assign them to variables representing the parameters (eager evaluation) or just replace the parameters in the code with the arguments (lazy evaluation).

Substitution doesn't just apply to functions: a sequence of straight line code with assignments can be converted into an expression by replacing occurrences of the variables with the initialising expressions.

For a small number of uses, substitution is the usually the most efficient. For many uses, lifting the common expressions to a variable is more efficient. If we're dealing with a function (in C++ the model is a class) for which a closure is formed (in C++ the model is an object of the class) lazy evaluation is very expensive because the argument itself must be wrapped in an object to delay evaluation.

By default, Felix val's and function arguments use indeterminate evaluation semantics, meaning the compiler gets to choose the strategy. This leads to high performance, but it also means we need a way to enforce a particular strategy: for example vars and var parameters always trigger eager evaluation. This leads to some complication in the language.

Felix also does other optimisations, for example it does the usual self-tail call optimisation. This one works best if you do inlining at the right point to convert a non-self tail call (which cannot be represented for functions in C) into a self-tail call (which is replaced by a goto).

Felix also does parallel assignment optimisation.

It ensures type-classes have zero cost (unlike Haskell which, by supporting separate compilation, may have to pass dictionaries around).

There is quite a lot more: eliminating useless variables, functions, unused arguments, etc. There are even user specified optimisations based on semantics, such as

  reduce idem[T]  (x:list[T]) : list[T] = x.rev.rev => x;

Actually one important aspect to the optimisation process: by default a function is a C++ class with an apply() method. This allows forming a closure (object). The object is usually allocated on the heap. However Felix "knows" when it can get away with allocating such an object on the machine stack instead (saving a malloc and garbage collection). Furthermore, Felix "knows" when it can get away with a plain old C function, and generates one of those instead if it can. And all of that occurs only if the function wasn't entirely eliminated by inlining all the calls.

So although you should think of Felix functions and procedures as objects of C++ classes allocated on the heap and garbage collected, any significant program implemented with this model without optimisations would just drop dead.