Monday, June 22, 2015

SHA1 compile time checked literals: F# vs Nemerle vs D

I've always been interested in metaprogramming. Sooner or later, I'm starting to feel constrained within a language without it. F# is a really nice language, but I'm afraid I'd have got bored with it if it'd not have Type Providers, for example. Why metaprogramming is so important? Because it allows changing a language without cracking the compiler. It allows making things which seemed to be impossible to implement.

I'm dealing with cryptography hashes a lot at work, nothing rocket since, just MD5, SHA-1 and so on. And I write tons of tests where such hashes are used in form of string literals, like this:

The problem with this code is that the compiler cannot guarantee that the hex string in the last line represents a valid SHA-1. If it does not, the test will fail at runtime for a reason it's not intended to.

OK, now we can formulate our task: provide a language construct to enforce a string literal being a valid SHA-1 hexadecimal, at compile time. We will explore how much work it's required to implement such a simple feature in F#, Nemerle and D. It's also interesting how well the development workflow is for each of this languages - IDE integration, error reporting and testing cycle.


Using Type Providers is the only way to check (at compile time) that a string is a valid hex one and that it's length is exactly 40 characters (SHA-1 is a 20-bytes hash). Actually, I've written this type provider before. The interesting part looks like this:

It includes caching, and `HexParser` module is not shown, but those details are not important here. It's simple and it generates Value property which directly returns byte array, created in compile-time.

Error reporting:


Nemerle has full fledged macros, which strictly more powerful than F#'s Type Providers. Let's see if they allow solving the task in an elegant way:

Error reporting:


The code does not use any unusual stuff and does not manipulate AST. Just plane D code. Very elegant. Note that the template is defined in the same file as its usage. Contrast this with F# and Nemerle where you have to place your Type Provider / macros into a dedicated assembly.

Error reporting:

The error is located in the template itself, not at the instantiation point though.


I added 1000 usages of the TP, macro and template and measured compilation time.

  • F# - 5 seconds
  • Nemerle - 2 seconds
  • D - the compiler crashes with "Error: out of memory" after 1 minute work.

Saturday, June 20, 2015

Fib: C++, C# and GDC

As a reference implementation, I added C++ one:

It's execution time is 1.33 seconds, which surprisingly is not the best result so far.
A C# version:

Also, I compiled this D code with GDC compiler and it executed in 990 ms, which is the best result:

  • D (GDC) - 0.990
  • C# - 1.26
  • D (DMD) - 1.3
  • C++ - 1.33
  • F# - 1.38
  • Nemerle - 1.45
  • Rust - 1.66
  • Go - 2.38
  • Haskell - 2.8
  • Clojure - 9
  • Erlang - 17
  • Ruby - 60
  • Python - 120

Unfortunately, I have not managed to compile the D code with LDC compiler, it returns the following error:

Building: DFib (Release)
Performing main compilation...
Current dictionary: d:\git\DFib\DFib
D:\ldc2-0.15.2-beta1-win64-msvc\bin\ldc2.exe -O3 -release "main.d"   "-od=obj\Release" "-of=d:\git\DFib\DFib\bin\Release\DFib.exe"
LINK : fatal error LNK1181: cannot open input file 'kernel32.lib'
Error: C:\Program Files (x86)\Microsoft Visual Studio 12.0\VC\bin\link.exe failed with status: 1181
Exit code 1181