Hue is one of my latest hobby projects that didn’t die after a week. It’s a functional programming language, in a sense. There are no statements in this language, but everything is an expression. An expression does something funky and returns something—hopefully—even funkier. That includes if..then..else as well as logical tests and functions.

Anyhow, this hobby language of mine is still very much in flux and I’ll probably change its syntax and behavior a few times before I’m really happy with it. Haskell, Erlang and Clojure all have some pretty cool features but I’ve never been friends with their syntaxes. Me wants something closer to Python. Me write language.

A programming language is in its essence a Human-Computer Interface. I’ve done these things in the past, for example the Move programming language. This time I wanted to write everything myself, starting at the instructions that the computer executes and all the way up to the runtime library, idioms, design opinions and concepts.

So far I’ve spent evenings and weekends during the last five weeks hacking on this, bust more so I’ve been reading conceptual stuff, like Joe Armstrong’s thesis paper “Making reliable distributed systems in the presence of software errors” (chapters 1 and 2), where Joe dissects the inherent problems with trying to model the real world using a non-1:1 mapping (e.g. imperative programming that fakes concurrency) and so forth.

From Hue to target assembly

A simple and completely useless program that contains a function which multiplies two integers with 9 and each other, then divides that with 4 and returns the result:

foo = ^(x, y Int) Int: z = x * y * 9
                       z / 4
a = 19
b = foo 4 (5*10*a)  # => 8550

Note a few things:

• Whitespace is significant. Like in the Python programming language, a colon “:” character denotes that a block of expressions follow. When the line indentation level drops from whatever level the expression that owns the “:” character is at, the block is terminated. The foo function’s block contains two expressions.

• Types are inferred. The language is strongly typed and in case the compiler is unable to infer the type, it will yield a compilation error. No types are inferred at runtime, which means that very few—or even no—errors related to types and value passing can happen when the program is run.

• Functions are expressions and not a “special” thing. Functions can be passed around just like any other value.

• Variables are actually just aliases and usually “folded” (removed and their values is just put in place) by the compiler.

Let’s compile this program:

hue hello.hue hello.ll

And look at the LLVM IR code that the Hue compiler generates:

define i64 @main() nounwind {                               # 1
  %foo_res = call i64 @"hello$foo"(i64 4, i64 950)          # 2
  ret i64 0                                                 # 3
}

define private i64 @"hello$foo"(i64 %x, i64 %y) nounwind {  # 4
  %multmp = mul i64 %x, %y                                  # 5
  %multmp1 = mul i64 %multmp, 9                             # 6
  %divtmp = sdiv i64 %multmp1, 4                            # 7
  ret i64 %divtmp                                           # 8
}

The Hue compiler generates LLVM intermediate representation code. Similar to what is output by e.g. Java and .NET compilers when an object file/program is built. LLVM is an amazing piece of compiler infrastructure software that enables a whole slew of features like native machine code generation, code optimization, etc. Going back to the above IR code, we see what actually happened to our program. I’ve given the lines above numbers, which we are referring to here:

1. @main() is the entry point of our module. Or program in this case.

2. We call the function hello$foo with two 64-bit integer values 4 and 5. We expect a return value that is a single 64-bit integer value, which we give the alias “%foo_res”. Notice how the a = 19 and (5*10*a) expressions where folded into 950 (“i64 950” in the IR above). Because values are constant, the compiler can “execute” obvious isolated parts of the program.

3. Our module returns control, with the 64-bit integer value 0, to whatever called it (in this case, our program exists with status 0).

4. This is where our function lives. “private” means that the function is only used inside this module, and “i64” means it returns a 64-bit integer value (Hue’s “Int” type is a 64-bit integer). The function takes two parameterized arguments which both are 64-bit integers and gives those parameters the aliases “%x” and “%y”.

5. We ask the computer to multiply the two values behind the aliases “%x” and “%y” and give the resulting value an alias of “%multmp”.

6. Again, we instruct the computer (these are so called “instructions”) to multiply two values: The result of multiplying “%x” and “%y”, which we did at line 5, with the number 9 and alias the result as “%multmp1”.

7. We divide the “%multmp1” value with the number 4 and alias the result as “%divtmp”.

8. We return the value behind “%divtmp” to the caller.

If we generate assembly for x86_64 (basically machine instructions), we get roughly the following:

  .section __TEXT,__text,regular,pure_instructions
  .globl  _main
  .align  4, 0x90
_main:                          ## 1
  pushq   %rax
  movl    $4, %edi              ## 2 (1/4) 
  movl    $950, %esi            ## 2 (1/4)
  callq   L_hello$foo           ## 2 (1/4)
  xorl    %eax, %eax            ## 3 (2/3)
  popq    %rdx                  ## 3 (3/3)
  ret                           ## 3 (4/3) ...
  .align  4, 0x90
L_hello$foo:
  imulq   %rsi, %rdi            
  leaq    (%rdi,%rdi,8), %rcx
  movq    %rcx, %rax
  sarq    $63, %rax
  shrq    $62, %rax
  addq    %rcx, %rax
  sarq    $2, %rax
  ret

Yeah, I know. This code gets scarier and scarier, but we can see how closely LLVM IR maps to target assembly, but we also understand the complexity of modeling something simple as the initial Hue program on x86_64 assembler.

We can run our program, which by the way doesn’t really do anything, either straight through LLVM as JIT-ed code using lli hello.ll or generate an object file and link it as a program:

llvm-as -o=- hello.ll | llvm-ld -native -o=hello -
./hello

Functional programming has for a long time been the toolbox of mathematicians and CS ninjas with beards (Johan and Erik — I’m lookin’ at you). My guess is that math people—clever fellas—invented these things and created syntaxes that fell natural to them. I never really payed attention to math in school and have no math education beyond the very basics, like multiplication, yet I have come to realize the awesomeness of math and its concepts. So how about we take the awesomeness of functional programming—high modularity and code re-use, testability, stability, etc—to us programming peasants of Python, JavaScript, BASIC and Java? Perhaps this project will be an attempt on that, or perhaps not.

A performant immutable & persistent vector implementation

Besides rambling about some yet-another-hobby-language, I wanted to talk about this one awesome, concrete thing that has come out of this project: An immutable persistent vector inspired by and partly ported from Clojure’s PersistentVector. With this approach, you can freely manipulate a vector data structure concurrently without locking and more importantly without causing imperative situations where expected state is different depending on outside, out-of-our-control circumstances.

Impressive numbers: Starting with the empty vector and appending one single item at a time until we reach one million takes roughly 200ms on a single 3.4 GHz i7 core. That is an average of 200 nanoseconds per append operation. Keep in mind that an append operation effectively creates a new vector — this data structure is in fact immutable, so we have to create a new, derived structure every time we “modify” it. With a traditional array-style structure, where we have N items in a uniform sequence, is cheap to copy when N is reasonably small (like 100 or so), but becomes a real bottleneck (and a problem for concurrent operations) when N grows.

Now, writing to and updating vectors are usually less common that accessing items in them. Pretty convenient then that this implementation offers almost-constant time random access. Technically is a little less than constant, but it’s negligible in my opinion (see comments in Vector.h for more info).

The source for this implementation is available from the Hue GitHub repository together with some unit tests (look in the “test” directory or run the “test” make target).

Numbers from running make clean test_vector_perf:

• N = 100 (this run takes the unfortunate initial impact of lazy-loaded symbols)
  • Inserting 100 values: 0.028 ms (avg 280 ns/insert)
  • Accessing all 100 values: 0.002 ms (avg 20 ns/access)
• N = 100 000
  • Inserting 100000 values: 20.722 ms (avg 207.22 ns/insert)
  • Accessing all 100000 values: 0.531 ms (avg 5.31 ns/access)
• N = 1 000 000
  • Inserting 1000000 values: 204.391 ms (avg 204.391 ns/insert)
  • Accessing all 1000000 values: 5.171 ms (avg 5.171 ns/access)
• N = 10 000 000
  • Inserting 10000000 values: 2002.78 ms (avg 200.278 ns/insert)
  • Accessing all 10000000 values: 59.592 ms (avg 5.9592 ns/access)
• N = 100 000 000
  • Inserting 100000000 values: 19741.9 ms (avg 197.419 ns/insert)
  • Accessing all 100000000 values: 674.349 ms (avg 6.74349 ns/access)

We can reason that for N up to at least 100 million, both insertion and random access is close to constant time complexity. It’s not nearly as fast as a traditional mutable vector which grows uniform regions of memory (e.g. std::vector or a plain C array), but given it’s immutable property, this is very good.

Source code and other goodies are available at github.com/rsms/hue.