Ela, functional programming language

• Download latest Ela Platform

Introduction

Ela is a functional programming language with dynamic typing and syntax that is heavily inspired by ML/Haskell. Dynamic stands for a type system that uses a "don't do it until the last moment" type inference algorithm. In other words, type information in Ela comes available at run-time, which has its own drawbacks, but gives programmer a lot of flexibility. Functional means that all operations in Ela can be seen in the light of combinations of functions. You can surely write imperative code in Ela - like you can in merely all functional languages including Haskell - however, in most cases, Ela is not the right tool for that.

The core part of the language is pure. Ela doesn't provide a support for mutation of state - it even doesn't have variables. The language is primarily oriented towards pure functional programming style. Stateful programming is a possibility as well, but all side effecting code can only be presented through foreign functions (e.g. in C#).

Ela shares a lot of peculiarities of functional programming languages such as - everything being as expression, first class and higher order functions, immutability of names and data structures, pattern matching, algebraic types, and so on. Currently, Ela comes with an Ela Console utility that can be used to execute and compile Ela code, and fully supports interactive mode as well. Also a graphical development environment is available for Windows.

In this article, I will give a short overview of Ela implementation and some core language features.

Implementation

Parser

Ela is fully written in C#. Its current implementation consists of four loosely coupled major components: a parser, a compiler, a linker, and a virtual machine.

The parser is written using CoCo/R that can generate LL(1) parsers. CoCo/R does offer some additional tools to resolve conflicts that don't fall under LL(1) strategy; however, these tools are pretty limited. Luckily, Ela grammar is pretty straightforward. The language mostly lacks any context depending constructs (of which there are many in the language in which Ela itself is written), and as a result, Ela grammar fits pretty well into the LL(1) requirements.

In case you haven't heard about parser generators before, these are tools that can turn a pretty complicated task such as a manual parser implementation into a relatively simple one. The idea behind them is as follows - you provide a declarative language grammar as an input and get a generated parser as an output.

A grammar consists of tokens (such as identifiers, integers, strings, etc.) and productions that describe a particular language construct.

For example, this is how a well known conditional operator looks like in Ela:

IfExpr = 
    "if" Expr "then" Expr "else" Expr.

LL(1) describes a specific type of a parser that can be created by CoCo/R. This one works from left to right, and can look ahead for a single symbol. It does introduce certain limitations; however, as I mentioned before, Ela grammar is not too complex and therefore Ela is totally OK with just LL(1) parser. At the same time, parsers generated by CoCo/R are lightning fast and the whole tool is comparably easy to use which renders CoCo/R as a good candidate if you need to generate a parser in C#.

Except for just formal language grammar, a parser definition also contains so called semantic actions - these are places where you create an object model that represents your code (an abstract syntax tree, AST). Ela uses its own language specific AST that reflects some of the language peculiarities such as everything including the whole program being an expression.

Unlike some language implementations (e.g., Ruby 1.8) that interpret code by walking the AST, Ela goes in a slightly different way and generates an intermediate byte code based on the object model that comes from the parser.

That is something that Ela compiler is responsible for.

Compiler

Ela compiler uses a recursive descend to process the AST and generate the appropriate byte code instructions. Besides that, it also generates debug information that is used in such tasks as generation of exception stack traces.

Basically, the compiler is responsible for plenty of things - it calculates the size of the evaluation stack, the size of the "heap" used to store non-temporary objects. Also, Ela supports lexical scope like C or Haskell, and that is what the Ela compiler does as well - it tracks declarations of names, allows names from enclosing scopes to shadow each other, and so on.

Ela byte code (called EIL) contains approximately one hundred instructions and is somewhat inspired by MSIL. However, unlike MSIL which is more or less an object-oriented assembly language, EIL doesn't provide any specific support for OOP, but favors functional paradigm instead, and providers a set of high-level instructions that can be used to create closures, treat functions as first class values, etc.

EIL is a stack based assembly language. For example, a simple expression like (2 + 2) * 3 will be compiled into the following EIL:

PushI4 2
PushI4 2
Add
PushI4 3
Mul

I hope it's clear what actually happens here. The compiler processes an expression from left to right and pushes specific values on the stack. The Add (addition) and Mul (multiplication) operations pop two values from the stack each, perform a calculation, and push the result back to the stack. Once the Add instruction is executed, we have just a single value of 4 on the stack; the same after the Mul instruction which pushes on the stack the result of the whole expression evaluation.

All EIL instructions have a fixed stack behavior (e.g., what changes on the stack this instruction performs - like Add that pops two values and pushes a single one back to the stack). Also, EIL instructions have a strict size in bytes. That is basically the reason why byte code is called so. In EIL, a length of an instruction can be either one byte (this is true for all instructions that lack arguments, like Add, Mul, Pop, etc., and this byte is reserved for the instruction code itself) or five bytes (this is true for instructions with arguments, like PushI4 that pushes an integer value on the stack and has a four byte integer as its argument).

You are probably wondering how Ela can deal with data types that don't fit into four bytes - and does it even have any? Let's see what code is generated when you try to compile a 64-bit integer literal 0x7fffffffffffffffL:

PushI4 -1
PushI4 2147483647
NewI8

As you can see, a 64-bit integer value is pushed on the stack in two turns, and then gets assembled using a built-in NewI8 instruction. A more complicated example - creation of a record in the form {x = 1, y = 2} in Ela (records can somewhat resemble anonymous types in C#):

Newrec 2
PushI4 1
Pushstr "x"
Reccons 0
PushI4 2
Pushstr "y"
Reccons 1

As you can see, this is a whole list of instructions - the first one creates an empty record with reserved slots for two fields, and the rest initialize a particular field by pushing its value and name onto the stack. Reccons is a built-in instruction that is used for record construction. It accepts a record field index as its argument and pops a field name and a field value from the top of the stack.

OK, we have generated byte code. But now we need to interpret it - and that is what a virtual machine is responsible for.

Virtual machine

Ela has a stack based virtual machine (which is obvious as you definitely can't use a Registry based one to interpret stack oriented byte code). Ela VM is a deterministic finite state machine. It is thread safe - Ela functions can be executed in different physical threads and this is a fully legal scenario. Also, unlike some other stack based VM implementations, Ela machine uses two stacks - an evaluation stack where all calculations are performed, and a call stack that stores structures that describe a currently executing function.

Except for several high level instructions that include function calls, built-in data type creation, etc., most of Ela byte code commands are pretty atomic, and as a result, Ela machine surprisingly appears to be a simpler component than a compiler.

Let's see how it works. For example, we need a simple VM that can only operate with integers and supports two operations - addition and multiplication. This is how it might look like:

public int Eval(Op[] ops, int[] args)
{
    var offset = 0;
    var stack = new Stack<Int32>();

    for (;;)
    {
        var op = ops[offset];
        var arg = args[offset];
        
        switch (op)
        {
            case Op.PushI4:
                stack.Push(arg);
                break;
            case Op.Add:
                {
                    var right = stack.Pop();
                    var left = stack.Pop();
                    stack.Push(left + right);
                }
                break;
            case Op.Mul:
                {
                    var right = stack.Pop();
                    var left = stack.Pop();
                    stack.Push(left * right);
                }   
                break;
            case Op.Stop:
                return stack.Pop();
                break;
        }
    }
}

That is really it. As you can see, we have a function that accepts an array of byte code instructions presented through an enumeration for convenience and an array of instruction arguments. For the simplification of instruction decoding, these arrays are always of the same length. If an instruction doesn't have an argument, then there is still a slot for it in the arguments array that contains zero. We also use just a single evaluation stack in this example (Ela has its own stack implementation for the sake of performance, but here we are using a standard class from System.Collections.Generic). The Stop instruction is the one that should always be the very last in our program - this instruction terminates an execution and returns a value that is currently on the top of the stack (we assume that a correct program should always have one). Thanks to the Stop instruction, the core part of the function Eval can be implemented as an endless cycle with no conditions to be evaluated on each iteration, which also boosts performance a little bit.

And that is really it. Simple, isn't it?

Linker

Linker is the last component that I will describe here. It is less complex than the previous components, and its sole purpose is to assemble separate Ela modules into a solid assembly that is actually executed.

Each module in Ela can reference other modules using the open instruction, like so:

open math

res = sum 2 2

The linker task is to locate all referenced modules, build them, and to finally combine everything into a single code assembly ready for execution.

Ela linker uses two other components - a parser and a compiler - to build Ela modules. However, it also supports deserialization of Ela byte code from binary (or so called object) files. If it sees that a target directly contains an object file, it will try to read it instead of parsing and compiling the raw code. In many cases, this can dramatically increase the build performance.

Embedding Ela

You can use the Ela interpreter within your .NET application. For such purposes, you only need to reference a single small library - Ela.dll.

You can use the parser and compiler directly from your code as standalone components, but normally you would only need a linker and an Ela machine to execute Ela code.

Ela provides two implementations of a linker. The one that is named ElaIncrementalLinker is used to support interactive mode. It allows you to build and execute Ela code chunk by chunk. The incremental linker is also useful if you want to evaluate Ela code in a string representation. If this is not what you need, you can use a regular Ela linker. This is a sample in C# that shows how to execute Ela code from a string:

var l = new ElaIncrementalLinker(new LinkerOptions(), CompilerOptions.Default());
l.SetSource(elaSourceCode);
var res = l.Build();

if (res.Success)
{
    var vm = new ElaMachine(res.Assembly);
    vm.Run();
}

In many cases, you might need to provide some arguments to Ela code. Here is a full example of an Eval function in C# that uses an anonymous class to capture arguments and their names:

public static object Eval(string source, object args)
{
        var l = new ElaIncrementalLinker(new LinkerOptions(), CompilerOptions.Default());
        
        foreach (var pi in args.GetType().GetProperties())
            l.AddArgument(pi.Name, pi.GetValue(args, null));
            
        l.SetSource(source);
        var res = l.Build();

        if (res.Success)
        {
                var vm = new ElaMachine(res.Assembly);
                return vm.Run().ReturnValue.AsObject();
        }
        else
        {
                var sb = new StringBuilder();

                foreach (var m in res.Messages)
                        sb.AppendLine(m.ToString());

                throw new ElaTranslationException(sb.ToString());
        }
}

//sample usage
var r = Eval("fun x y", new { 
        fun = ElaFunction.Create<int,int,int>((x,y) => x + y), 
        x = 2, 
        y = 4 
        });

You can also create Ela modules in C# (or any other .NET language). This is an example of a simple module:

public class MyMathModule : Ela.Linking.ForeignModule
{
    public override void Initialize()
    {  
        base.Add<Int32,Int32,Int32>("rnd", Randomize);  
    }
    
    public int Randomize(int seed, int max)
    {
        var rnd = new Random(seed);
        return rnd.next(max);
    }
}

And this is what you need to do to make this module available in Ela:

var l = new ElaIncrementalLinker(CompilerOptions.Default, new LinkerOptions());
    l.ModuleResolve += (o,e) => {
                if (e.Module.ModuleName == "mymath")
                        e.AddModule(new MathModule());
        };
    l.SetSource(source);
    var res = l.Build();

And now you can seamlessly use this module from Ela:

open mymath

r = rnd 0 42

You can also compile your module into a regular .NET assembly, reference Ela.dll, and specify the following attribute:

[assembly:ElaModule("mymath", typeof(MyMathModule)]

Now you don't have to manually add this module into the collection of modules. The Ela linker will be able to find it without your help. But you will have to specify the DLL name in your open directive like so: open math#mymathdll.

Distinctive features

Syntax

As I have mentioned before, the Ela syntax is heavily inspired by the ML family of languages and Haskell. Ela uses a layout based (or indentation driven) syntax as F# or Haskell.

The top level in Ela can contain name declarations, module include directives or even regular expressions. For example, the following code is fully correct:

x = 2
y = 2
x + y

Basically the whole Ela program can be seen as a single expression (e.g., 5, "Hello, world!", 2 + 2 are valid Ela programs).

As you can see, declaration of names doesn't require any specific keywords. The same for functions:

sum x y = x + y

doubleMe x = x + x

Ela fully supports pattern matching which can be described as an old fashioned switch/case construct on steroids - with an ability to match against any value and to compare and bind names within the single expression:

xs = [1,2,3,4]
x = match xs with
          [1,2,x,y] = x + y
          _         = 0

Besides regular match expression, Ela also supports function definition by pattern matching - pretty similar to the one used in Haskell. Here is an example of a well known map function implemented in Ela:

map f (x::xs) = f x :: map f xs
map _ []    = []

Local names can be declared using let keyword. There is also another option to introduce local names - the where construct. Here is a tail recursive implementation of Fibonacci function in Ela:

fib = fib' 0 1
      where fib' a b 0 = a
            fib' a b n = fib' b (a + b) (n - 1)

The where binding is not always equivalent to let. For example, where allows you to declare names that are scoped to a specific entry in the pattern matching construct:

filter _ [] = []
filter f (x::xs) | r    = x :: filter f xs
                 |  else = filter f xs
                 where r = f x

You can also declare several names by identing declarations at the same level (this is available for both let and where bindings):

x + y
    where x = 2
          y = 3

let x = 2
    y = 3
 in x + y

All bindings in (both local and top level) are mutually recursive:

take (x::xs) = x :: skip xs
take []      = []
 
skip (_::xs) = take xs
skip []      = []

sum x = x + y
y = 2

Of course, it is difficult to describe all the peculiarities of Ela syntax in this section, especially if you don't know any ML style language. To those who want to know more, I can recommend to read a book about Ela that deals with the syntax in more detail.

Curried functions

All functions in Ela can accept only a single argument. Don't panic - this is not a weird Ela limitation, but a pretty typical behavior of functional languages.

A function application operation in Ela is a simple juxtaposition of a function and its argument. The function is always applied to just a single argument. Also, the function application has one of the highest priorities in the language and is left associative. Therefore, when you see code like sum 2 3, this is:

1. a valid Ela code, and
2. not a function call with two arguments but two function calls.

Here, we call a sum function with a single argument 2, assume that this function call returns another function, and call it once more with an argument 3.

It actually unveils the way how Ela deals with multiple argument functions. These are basically functions that return other functions (that also might return other functions, and so on). For example, this is how our sum function can be defined using the anonymous function syntax:

sum = \x -> \y -> x + y

That is equivalent to the following code in C#:

Func<Int32,<Func<Int32,Int32>> sum(int x)
{
    return x => y => x + y;
}

Of course, it is not always convenient to define functions in such a manner - that is why Ela supports special syntax sugar:

sum x y = x + y //This is fully equivalent to \x -> \y -> x + y

Functions as the sum function above are called curried functions. You probably have heard about this concept before. Curried functions give you a possibility to partially apply functions. As all our functions are just nested closures, you don't have to specify all of the arguments when you call them. A call like sum 2 is fully legal, and returns a new function for one argument that can sum this argument to the number 2.

This feature is usually called partial application, and it is very essential to the functional programming paradigm.

Infix, prefix, postfix

Those three are notations that are used for a function call. Most languages use prefix notation when a function is placed before its arguments. With operators, you usually use infix notation when an operator is placed between its arguments. Postfix notation is less common - it assumes that a function is placed after its arguments.

Prefix notation is widely used in Ela and is the default one. However, sometimes it is more visual to use infix form - that is to place a function between its arguments. And here is the trick - in Ela, even regular functions can be called using infix form.

There are several cases when this possibility can be useful. Let's say that we have an elem function. This function accepts an element, a list, and tests if a given element exists in a given list. This is how this function can be defined:

any f [] = false              
any f (x::xs) = f x or any f xs
              
elem x = any (==x)

OK, but what is so specific about this elem function? Mostly nothing. With the only exception that the application of elem is probably easier to read when it is written in infix form:

elem 5 [1..100]
42 `elem` [1..100]

However, functions are not the only entities that can escape from prefix to infix form. Operators that are applied using infix form by default, can also be called in the same manner as functions:

res1 = 2 + 2

res2 = (+) 2 2

And finally - you can also apply both functions and operators using postfix form. Postfix means that an argument is placed before the function or operator name. This is how it might look:

isEven x = x % 2 == 0
res1 = 12 `isEven`
res2 = 13 `isEven`

The same for operators:

f = (2+) //this is a partial application of + operator
sum2 = (2+)
res = sum2 3 //the result is 5

The support for postfix form is really important when it comes to operators as it unveils a very convenient way to partially apply operators. If you partially apply an operator using postfix form, then the very first argument gets "fixed". If you use a prefix form, then the second argument is "fixed":

div1 = (5-)
res1 = div1 3 //the result is 2
div2 = (-5) //this is equivalent to: (-) 5
res2 = div2 7 //the result is 2

All these tricks work with regular functions as well; however, they are a little bit more common with operators.

As a result, with all this variety of application forms and ability to switch between them, we finally come to a conclusion that there is no real difference between operators and functions. Or to say more precisely - operators are functions that use a different calling convention by default.

And that is really true for most of the standard Ela operators. Which again leads us to another conclusion: if a difference is, well, basically non-existent, why not give users the ability to define their own operators? And this is possible in Ela:

//Safe division function
x /. 0 = None
x /. y = Some (x/y)
res = 12 /. 0//take the element with index 2 from the array

Types

Ela comes with a rich and extensible collection of types out of the box. Ela has four numeric types, strings, chars, immutable linked lists, tuples, records, variants, and more. Ela standard library also provides additional types.

Numeric types include 32-bit and 64-bit integers and 32-bit and 64-bit floating point numbers:

i4 = 42
i8 = 42L
r4 = 12.2
r8 = 123.12D

Strings and chars use C style literals and escape codes:

str = "Hello,\r\n\"Dr. Smith\"!"
ch = str:0
ch2 = '\t'

Single linked lists can be constructed either using list literals or the list construction operator :: similar to the one used in F#:

lst = [1,2,3]
lst2 = 1::2::3::[]

Tuples are grouped sequences of elements that are useful if you want, for example, to fetch several values from a function:

tup = (1,2,3,4)
res = (1,2) + (3,4) //equals to (4,6)

Records are tuples that provide the possibility to access an element by its name:

let rec = { x = 2, y = 42, str = "string value" }
rec.y

There are many other data types as well.

The key thing to know about the Ela type system is that most of standard operations in Ela are polymorphic.

As you have seen above, it is absolutely legal to perform arithmetic operations on tuples. Also, strings in Ela are implemented as indexed arrays (like in .NET Framework), but you can also fold them as lists:

foldl f z (x::xs) = foldl f (f z x) xs
foldl _ z []      = z

reverse = foldl (flip (::)) []
revStr = reverse "Hello, world!"

Variants

Polymorphic variants are yet another data type in Ela. Their title might sound somewhat complex, but the concept itself is pretty straightforward. The idea comes from the OCaml language, but the Ela approach is somewhat different.

Polymorphic variants simply give you a way to "tag" a value:

tagged = Even 12

You can think of them as a tool that allows you to associate some additional information with a value and to use this information further - for example, in pattern matching:

res = match tagged with
            Even x = "The number is even!"
            Odd x  = "The number is odd!"
            _       = "Something is wrong here..."

Thunks and lazy lists

Thunks are a tool that allows you to do lazy computations. Thunk is a special expression with a leading ampersand that is not evaluated immediately but only when its value is actually needed:

t = & 2 + 2
res = t * 2

In the example above, the name t is not initialized with the result of the evaluation of the expression 2 + 2. Instead, Ela creates a hidden closure that contains the above calculation. This closure is called the first time the value of a thunk is needed - after that, the value is memorized and no calculation is performed the next time you refer to the t variable.

You can achieve a similar behavior by passing a function that calculates a value instead of an actual value, but thunks have two distinctive features here: first, they perform memorization when regular functions obviously don't, and second, they can be used transparently in your code as you can see from the code sample above.

It means that you can implement a function that performs some operations with its arguments, such as simple arithmetic, and you can pass to this function either actual values or thunks - they both will perfectly do.

Lazy lists in Ela are constructed with the help of thunks by using a thunk instead of a list tail. Here is a small example of a function that generates an infinite list of integers:

ints n = nn :: (& ints nn) 
         where nn = n + 1

res = ints 0

Ranges and list comprehensions

Ranges in Ela are arithmetic sequences that can be used to create lists. You only have to specify a first element, a last element, and (optionally) a second element in a sequence that will be used to calculate stepping:

r1 = [1..5] //[1,2,3,4,5]
r2 = [1,3..10] //[1,3,5,7,9]
r3 = [100,87..1] //[100,87,74,61,48,35,22,9]

You can also generate infinite lists using ranges by omitting the last sequence element:

inf1 = [1..] //[1,2,3,4,5...]
inf2 = [3,2..] //[3,2,1,0,-1,-2..]

List comprehensions in Ela resemble the classical mathematical set builder notation. They can be used to generate new sequences from existing sequences by providing selection conditions and projection code. You can also pattern match in list comprehensions:

xs = [x + y \\ (x,y) <- [(1,2)..(4,5)] | x > 2] //The result is [7,9]

Here, we are taking a list of tuples, selecting only those where the first element is greater than 2, and returning a new list whose elements are the sum of the tuple elements. Imagine how much code you would need to write to do the same thing in an imperative language.

First class modules

Modules are first class values in Ela - you can pass them as arguments to functions, and so on:

open math
open symbolMath

doSum x y mod = mod.sum x y
res1 = math <| doSum 2 2
res2 = symbolMath <| doSum 2 2

User types

Ela also provides an ability to define your own data types like so:

type foobar
  where foo x = Foo x
        bar x = Bar x

In fact all standard Ela types such as integers, floating point numbers, strings, etc. are declared in the same way in prelude module (which is an initialization script that gets executed prior to the rest of the code).

A type declaration consists of a type name and a set of type constructors which can be functions or just constants. A typical way to present a type instance is through a variant like in the example above. Type instances can be analyzed using pattern matching like so:

fb = foo 42
(Foo x) = fb
x //Evaluates to 42

Of course you can do exactly the same thing with just variants. And at this point user types seem to be a redundant feature in the language. But wait, there is a reason, why they exist.

Classes

OK, that is a long talk, but I will try to keep it short so let's move directly to the subject.

First of all this have nothing to do with object oriented programming. A class in Ela can be described as a class of operations. It can be compared with interfaces in C# and does share with them several peculiarities (e.g. it doesn't allow to provide implementations) but it is different in many other aspects.

First of all a class in Ela is used to declare global bindings. Let's say that we have declared a class like so:

class Mapable a
    where gmap _->a

Now we have one global function gmap that is not different from regular Ela functions - it is a first class value, it is curried, etc. Well, in fact one thing is actually different about it. A run-time environment allows for this function to have several implementations.

In order to provide an implementation one should write an instance of a class for a specific type. If you try to call a gmap function without a proper instance you will get a run-time error:

gmap (*2) [1..10]

//Error ELA820: Function 'gmap' is not implemented for 'list'.

In order to make this code work we have to implement an instance for type list:

instance Mapable list
    where gmap f (x::xs) = f x :: gmap f xs
          gmap _ [] = []

gmap (*2) [1..10] //[2,4,6,8,10,12,14,16,18,20]

It is not much different from a regular map function yet, but as soon as gmap is defined as a class member we can easily implement another instance for it - for a different data type such as tuple:

instance Mapable tuple
    where gmap f tup = map 0
               where len = length tup
                     map n | n == len - 1 = (e,)
                           | else = (e,) ++ map (n+1)
                           where e = f (tup:n)

gmap (*2) (1,2,3,4,5) //(2,4,6,8,10)

I hope now you can see a couple of important differences from an object oriented approach.

First, functions and data are kept separated and because of that you loose none of the properties of regular functions with member functions. Then in languages like C# you have to implement all interfaces at the point when you define your type and its obviously impossible to "add" interface implementations to the types that already exist, such as standard types. Classes in Ela, as you can see from code samples above, don't have such a limitation. You can write instances for built-in types in the same way as you write instances for custom types. And, finally, the dispatch rules for member functions in Ela is different.

You probably have noticed that a declaration of gmap function in Mapable class has a weird signature "_->a" right next to it. This signature is used to specify overloading rules for a function. An "a" element in it is a type parameter that can appear at any place in a function signature - unlimited number of times, but at least once. An "_" placeholder means that any value is accepted here.

In C# (as in many other object oriented languages) a function is selected at run-time based on the type of the first argument (which is then passed to this function implicitly as "this" argument). Ela is again more flexible here as it allows you to specify overloading rules for each member function. (In fact overloading by first argument wouldn't work in Ela at all. All functions in Ela are curried which naturally affects the order of function arguments. For example, gmap function from our example accepts a projection function as its first argument and a list as a second argument (while in C# you would probably reverse the argument order). This allows to partially apply gmap by providing only a projection function, e.g.: gmap (*2)).

Most of standard functions from Ela prelude module are in fact class members. For example, there are classes Eq (that defines equality functions), Ord (comparison functions), Num (arithmetic functions), etc. You can always declare your own classes or implement standard classes for any types, including built-ins.

If you are interested, more information about classes is available in language reference.

Benchmarks

I have spent quite a while thinking what would be the best test for Ela. Ela is a functional language, therefore we should have a functional style test. And it is really not a trivial task to find a good candidate to be compared with Ela. Ela is not really indented to write imperative code when most of popular dynamic languages are mostly imperative (with some, usually limited, support of functional programming paradigm). I believe it is pretty pointless to imitate imperative code in Ela (which is not always trivial by the way) just in order to run a speed comparison. Why do you need a benchmark for a code that you are never going to write?

The second problem is that I definitely want Ela to look the best it can. However Ela is not the fastest interpreted dynamic language but it is not the slowest also. And there is a temptation to compare Ela execution speed with a language that is known to be not too fast. Such as - no offense - Ruby. But Ruby currently doesn't have its own virtual machine and the test will be unfair.

So I decided to stick with Python.

Please understand that what I am doing here is not exactly a benchmark. I am just trying to show Ela execution speed based on the comparison. In reality Python is faster than Ela - which is of no surprise as soon as Python is written in C which tends to generate faster code than C# and JIT compiler. But in most cases you will notice it only when you write pretty low level imperative code. And when it comes to functional code the situation is much more interesting.

OK, let's get started. I am using a Core i7 620M CPU and Windows 7. Ela 0.11 and Python 2.7. Both Python and Ela are running in 32-bit mode. I am running each test 10 times and calculating an average.

The task is - generate a sequence of integers and sum all integers in this sequence. Here is Python code:

def foldl(func, start, seq):
    if len(seq) == 0:
        return start
    return foldl(func, func(start, seq[0]), seq[1:])

foldl ((lambda x, y: x + y), 0, range(1, 5001))

And here is Ela solution:

foldl f z (x::xs) = foldl f (f z x) xs
foldl _ z []      = z
    
_ = foldl (+) 0 [1..5000]

And the results:

OK, this looks surprising. Moreover in order to run this code in Python I had to explicitely increase the allowed recursion limit. Still if I set the size of a collection to contain 10000 elements Python interpreter crashes with no obvious reason. I have taken the foldl function definition from official Python documentation (see Functional Programming HOWTO), so it shouldn't be broken, right?

Well, let's be frank. Function foldl is a tail recursive function and Ela can optimize tail recursion and elimitate unnecessary function calls when Python obviously can not. As a result the comparison is not very fair. Let's modify Ela code:

foldr f z (x::xs) = f x (foldr f z xs)
foldr _ z []      = z

_ = foldr (+) 0 [1..5000]

Function foldr processes a list from right to left and is not tail recursive. As a result Ela won't be able to optimize it. As soon as we are just calculating a sum of elements foldr will work exactly the same as foldl so I am not even going to change Python code. So, the second run:

As you can see it doesn't help Python. Ela is still much faster. Also even the version with foldr works nicely with a list of 1 million elements, when Python crashes on a collection of ten thousand elements.

So you can probably agree with me that Ela is not the worst programming language if you want to write functional code.

Why do I need it?

Or why do we need yet another programming language when there are plenty of them already? We really do have a lot of programming languages but Ela has its own unique features.

First of all Ela is a dynamic functional language. This is not a typical combination as soon as most of modern functional languages are statically typed. Dynamic typing simplifies language a lot. If you want to learn functional programming paradigm Ela is here to teach you, and with Ela you will truly learn functional programming not the limitations and peculiarities of a particular type system.

Moreover Ela is one of very few true functional languages with dynamic typing. I know that you are not going to agree with me as there are some traditionally respected languages that - for some of us - even represent functional programming paradigm. But let's be objective. Do you think that a functional language can go without immutability? Or that a functional language should use imperative cycles as a primary control structure? Or crash unexpectedly when you use functional patterns for other than toy samples? Or favor side effects - through built-in types and other supported paradigms? Can you imagine a functional language that doesn't have any built-in mechanism for partial function application? Well, you can surely imagine as there are many but why do we call them functional? When functional programming is all about combining functions which is not an easy task when a language lacks any built-in tools for that.

Taking all that I don't think that Python is functional. I don't think that JavaScript is functional. I doubt that - yes, shoot me - Lisp is functional. Yes, Lisp is a father-and-mother of functional programming but that is the language in which this paradigm basically started to develop. If you look at it from the standpoint of an ML programmer you can hardly find any real reasons to call it functional. First class functions? Python also has them. Mutable linked lists? Well, I am not even going to comment on that.

Ela follows the traditions of ML\Haskell. Of course there are many ways to understand and define functional programming but if you prefer to stick with ML tradition than Ela is a right choice for you as soon as it takes functional paradigm in the same way.

But I haven't answered a question - why do you need it? Well there may be a number of reasons:

1. Learn functional programming. Ela is really a good choice to learn functional paradigm. It has a much lower entry cost than other popular functional languages but will teach you almost the same. You will definitely be able to reuse your knowledge when learning other languages such as OCaml, F#, Haskell, etc. after Ela.
2. Embedding. Ela virtual machine doesn't have an internal state maintained through static variables, you can run two instances in the same process and application domain. It is also thread-safe and easy to use from .NET code. Moreover it doesn't require any installation and implementation of the language is contained in a single DLL.
3. Prototyping. As with many dynamic language prototyping is one of the key areas where Ela can show its best. In Ela you don't have to design your types and prove to the compiler the correctness of your program. You just implement your tasks.
4. Potentially all the tasks where dynamic typing is a blessing, not a curse. Such as web applications, database clients, administrative scripts, etc. Ela standard library is somewhat limited at the moment - however you can always implement your own modules for Ela which is a pretty straightforward task.
5. Mathematics and research projects. Ela gives you the best from the functional world and is very flexible and extendable at the same moment. With Ela run-time environment you can for example implement a support for symbolic equatations just on a library level. I am not even speaking about such things as theorem provers - these are the things that functional languages are intended for.
6. Domain-specific languages. Ela provides a limited support for extending its syntax but what you have out of box is already flexible and expressive enough for your own DSL. And as usual it is really easy to build DSL with Ela. Moreover Ela is an interpreted language that runs on its own virtual machine - it is not the same as a language dynamically compiled to machine-code. With Ela your DSL will be much safer and could be freely executed in low trust environments.

A good example of Ela capabilities can be an espec module from standard library. This module implements a DSL for test specifications that allows you to write tests in a form close to natural language and generates detailed test results with tracing for each step.

This is an example of a simple test specification in espec:

test1 = 
  test "Demonstration of espec"
  given [1..5]
    should contain 1
    shouldn't contain 3
    shouldn't contain 6
    do reverse
    should be [5,4..1]
    do tail
    should be [3,2..1]
    do head
    should be 4

Test session started.

Test "Demonstration of espec" (failed 2, errors 0):
  given [1,2,3,4,5]
    should contain 1 -> success
    shouldn't contain 3 -> failed (got [1,2,3,4,5])
    shouldn't contain 6 -> success
    do reverse -> [5,4,3,2,1]
    should be [5,4,3,2,1] -> success
    do tail -> [4,3,2,1]
    should be [3,2,1] -> failed (got [4,3,2,1])
    do head -> 4
    should be 4 -> success

Total tests:1 Failed: 1

Thanks to flexible syntax and dynamic typing that enables to write functions which type is calculated "on the fly" (and which would be impossible to present in a statically typed system) Ela allows you to write really expressive and flexible code. This is "functional programming unleashed" without the limitations of clumsy syntax or static typing.

Conclusion

Ela is still under active development - currently, I am working on the documentation and the standard library. The Ela source code is freely available under GPL v2 license, and can be found in the Google Code repository (see the Links section below). You can also download the latest binary releases and read the documentation that describes the language features in more detail. I am always glad to hear any feedback and comments, and help you if you will decide to use Ela in your application.

Links

• Book about Ela
• Library and language reference
• Source code
• Latest binary releases
• Online interpreter